线性表的两个非递减集合求并集

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;

#include 
using namespace std;
struct List 
{
    int _length;
    int _capacity;
    int* _data;

    List(int capacity) 
    {
        _capacity = capacity;
        _length = 0;
        _data = new int[_capacity];
    }

    ~List()
    {
        delete[] _data;
    }
};

bool Insert(List& list, int value) 
{
    //表满--无法插入
    if (list._length == list._capacity)
    {
        return false;
    }
    //插入值比前一个值小 重新输入
    if (list._length > 0 && value < list._data[list._length - 1]) 
    {
        return false;
    }
    //正常插入
    list._data[list._length] = value;
    list._length++;

    return true;
}


List Merge(const List& listA, const List& listB)
{
    List listC(listA._capacity + listB._capacity);
    int i = 0, j = 0;
    while (i < listA._length && j < listB._length) 
    {
        if (listA._data[i] < listB._data[j]) 
        {
            Insert(listC, listA._data[i]);
            i++;
        }
        else 
        {
            Insert(listC, listB._data[j]);
            j++;
        }
    }
    while (i < listA._length) 
    {
        Insert(listC, listA._data[i]);
        i++;
    }
    while (j < listB._length)
    {
        Insert(listC, listB._data[j]);
        j++;
    }

    return listC;
}

void Printf(const List& list) 
{
    for (int i = 0; i < list._length; i++) 
    {
        cout << list._data[i] << " ";
    }
    cout << endl;
}

int main()
{
    int ALen;
    cin >> ALen;

    List listA(ALen);
    for (int i = 0; i < listA._capacity; i++) 
    {
        int value;
        cin >> value;
        if (!Insert(listA, value)) 
        {
            cout << "输入错误，请重新输入该值：";
            i--;
        }
    }

    int BLen;
    cin >> BLen;

    List listB(BLen);
    for (int i = 0; i < listB._capacity; i++) 
    {
        int value;
        cin >> value;
        if (!Insert(listB, value)) 
        {
            cout << "输入错误，请重新输入该值：";
            i--;
        }
    }

    Printf(listA);
    Printf(listB);

    List listC = Merge(listA, listB);
    Printf(listC);

    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128