【实验目的】

帮助学生熟练掌握线性表的顺序存储结构（顺序表）的基本操作及其简单应用，实现两个有序表的合并操作。

【实验内容及要求】

  1. 实现顺序表的各种基本操作，包括创建顺序表、插入和删除指定序号的元素、读取表元、获取最大和最小值元素、查找元素、表元素的排序、表元素逆置、顺序表的输入和输出等等；
  2. 实现两个有序顺序表的合并。问题描述：创建两个有序的顺序表L1和L2，表中元素值由键盘随机输入，再将它们合并为一个新的顺序表L3,合并后L3仍然有序（重复元素只保留一个），最后输出顺序表中的各个元素值。
  3. 设计测试用例，测试基本操作和合并操作的正确性。
  4. 实现说明：这是第一个上机描述和实现的数据结构类型，旨在让学生加深对数据结构、逻辑结构、存储结构和算法及算法时间复杂度等概念的理解。

    【实验代码】

    第一题

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include <iostream>
using namespace std;

#define Maxlength 20

typedef struct
{
    //int data[Maxlength]; // 顺序表元素
    int * data;
    int length; // 当前长度
}SqList; // 结构体定义

void createList(SqList &L, int n); // 创建顺序表
bool inputNum(SqList &L, int x, int n); // 修改指定位置元素的数据
void showNum(SqList &L); // 展示顺序表元素
bool insertNum(SqList &L, int x, int n); // 在指定位置插入元素
bool deleteNum(SqList &L, int n); // 删除指定位置元素
bool checkNum(SqList &L,int n); // 读取指定位置元素的数据
bool getMaxAndMinNum(SqList &L,int &max, int&min); //获取最大和最小元素，并分别赋值给max和min
int findNum(SqList &L, int x); // 查找指定元素的索引，并返回他在顺序表中的位置
void sortList(SqList &L); // 排序表元素
void inverseList(SqList &L); // 逆置顺序表

int main() {
    SqList sqList; // 定义顺序表

    createList(sqList, 10); // 创建顺序表
    showNum(sqList); // 展示顺序表元素

    inputNum(sqList,110,5); // 修改顺序表的第5个元素的值
    showNum(sqList); // 展示顺序表元素

    checkNum(sqList,5); // 读取顺序表中的第5个元素

    insertNum(sqList,120,4); // 在顺序表的第4个位置插入元素
    showNum(sqList); // 展示顺序表元素

    sortList(sqList); // 将顺序表排序
    showNum(sqList); // 展示顺序表元素

    deleteNum(sqList,10); // 删除顺序表中的第10号元素
    showNum(sqList); // 展示顺序表元素

    findNum(sqList,5); // 寻找顺序表中是否有元素12

    int maxNum, minNum;
    getMaxAndMinNum(sqList,maxNum,minNum);
    cout << "此顺序表的最大元素是" << maxNum << ", 最小元素是" << minNum << endl;

    inverseList(sqList);
    showNum(sqList);

    return 0;
}

void createList(SqList &L, int n) // 创建顺序表
{
    L.data = new int[Maxlength];
    for(int i = 0; i < n; i++)
    {
        L.data[i] = i;
    }
    L.length = n;
}

bool inputNum(SqList &L, int x, int n) // 修改指定位置元素的数据
{
    if(n < 1 || n > L.length)
    {
        cout << "索引异常，无法修改" << endl;
        return false; //修改失败，返回false
    }

    L.data[n-1] = x;
    return true; // 修改成功，返回true
}

void showNum(SqList &L) // 展示顺序表元素
{
    cout << "顺序表的元素依次为: ";
    for(int i = 0; i < L.length; i++)
    {
        cout << L.data[i] << " ";
    }
    cout << endl;
}

bool insertNum(SqList &L, int x, int n) // 在指定位置插入元素
{
    if(L.length == Maxlength)
    {
        cout << "顺序表元素已满，无法添加!" << endl;
        return false; // 插入失败，返回false
    }

    if(n < 1 || n > L.length)
    {
        cout << "索引异常，无法添加" << endl;
        return false; // 插入失败，返回false
    }

    for(int i = L.length -1; i >= n - 1; i--)
    {
        L.data[i+1] = L.data[i];
    }

    L.data[n-1] = x;
    L.length++;
    cout << "插入成功!" << endl;

    return true; // 插入成功，返回true
}

bool deleteNum(SqList &L, int n) // 删除指定位置元素
{
    if(L.length == 0)
    {
        cout << "顺序表无元素，无法删除" << endl;
        return false; // 删除失败，返回false
    }

    if(n < 1 || n > L.length)
    {
        cout << "索引异常，无法删除" << endl;
        return false; // 删除失败，返回false
    }

    for(int i = n-1; i < L.length - 1; i++)
    {
        L.data[i] = L.data[i+1];
    }
    L.length--;
    cout << "删除成功!" << endl;

    return true; // 删除成功，返回true
}

bool checkNum(SqList &L,int n) // 读取指定位置元素的数据
{
    if(L.length == 0)
    {
        cout << "顺序表的长度为0，无法查找" << endl;
        return false; // 读取失败，返回false
    }
    if(n < 1 || n > L.length)
    {
        cout << "您指定的元素索引超出了范围" << endl;
        return false; // 读取失败，返回false
    }

    cout << "第" << n << "号元素为: " << L.data[n-1] << endl;
    return true;
}

bool getMaxAndMinNum(SqList &L,int &max, int&min) //获取最大和最小元素，并分别赋值给max和min
{
    if(L.length <= 0)
    {
        cout << "顺序表为空，无最值！" << endl;
        return false;
    }
    max = min = L.data[0];

    for(int i = 1; i < L.length; i++)
    {
        if(max < L.data[i])
        {
            max = L.data[i];
        }

        if(min > L.data[i])
        {
            min = L.data[i];
        }
    }

    return true;
}

int findNum(SqList &L, int x) // 查找指定元素的索引，并返回他在顺序表中的位置
{
    for(int i = 0; i < L.length; i ++)
    {
        if(L.data[i] == x)
        {
            cout << "元素" << x << "是顺序表中的第" << i + 1 << "个元素" << endl;
            return i+1;
        }
    }

    cout << "元素" << x << "不在顺序表中!" << endl;
    return -1; // 此元素不在表中
}

void sortList(SqList &L) // 排序表元素
{
    for(int end = L.length - 1; end > 0; end--)
    {
        for(int j = 0; j < end; j++)
        {
            if(L.data[j] > L.data[j+1])
            {
                int temp = L.data[j];
                L.data[j] = L.data[j+1];
                L.data[j+1] = temp;
            }
        }
    }

    cout << "排序完成!" << endl;
}

void inverseList(SqList &L) // 逆置顺序表
{
    for(int i = 0; i < L.length / 2; i ++)
    {
        int temp = L.data[i];
        L.data[i] = L.data[L.length - 1 - i];
        L.data[L.length - 1 - i] = temp;
    }
    cout << "逆置成功！" << endl;
}

第二题

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
129
130
#include <iostream>
using namespace std;

#define Maxlength 20

typedef struct
{
    int * data; // 顺序表元素
    int length; // 当前长度
}SqList; // 结构体定义

void createList(SqList &L, int n); // 创建顺序表
void showNum(SqList &L); // 展示顺序表元素
bool combineList(SqList L1, SqList L2, SqList &L); // 合并顺序表
void eliminateRepeatingElements(SqList &L); // 消除重复元素
void sortList(SqList &L); // 排序表元素

int main()
{
    SqList L1, L2, L3;
    int n1, n2;
    cout << "请依次输入你的第一个和第二个顺序表的长度: " << endl;
    cin >> n1 >> n2;
    createList(L1,n1);
    createList(L2,n2);
    combineList(L1,L2,L3);
    showNum(L3);
    return 0;
}

void createList(SqList &L, int n) // 创建顺序表
{
    L.data = new int[Maxlength];
    cout << "请依次输入你要为顺序表填充的值: " << endl;
    for(int i = 0; i < n; i++)
    {
        cin >> L.data[i];
    }
    L.length = n;
}

void showNum(SqList &L) // 展示顺序表元素
{
    cout << "顺序表的元素依次为: ";
    for(int i = 0; i < L.length; i++)
    {
        cout << L.data[i] << " ";
    }
    cout << endl;
}

bool combineList(SqList L1, SqList L2, SqList &L) // 合并顺序表
{
    if (L1.length + L2.length > Maxlength)
    {
        cout << "合并的两个顺序表长度超出范围，无法合并!" << endl;
        return false;//超出最大存储空间
    }

    L.data = new int[Maxlength]; // 为新顺序表分配空间
    int index1 = 0, index2 = 0, index = 0; // 根据序号依次为三顺序表的实际下标
    while(index1 < L1.length && index2 < L2.length)
    {
        if(L1.data[index1] < L2.data[index2])
        {
            L.data[index++] = L1.data[index1++];
        }else if(L1.data[index1] == L2.data[index2])
        {
            L.data[index] = L1.data[index1];
            index++;
            index1++;
            index2++;
        } else
        {
            L.data[index++] = L2.data[index2++];
        }
    }

    while(index1 < L1.length)
    {
        L.data[index++] = L1.data[index1++];
    }

    while(index2 < L2.length)
    {
        L.data[index++] = L2.data[index2++];
    }
    L.length = index;
    sortList(L);
    eliminateRepeatingElements(L);

    return true;
}

void sortList(SqList &L) // 排序表元素
{
    for(int end = L.length - 1; end > 0; end--)
    {
        for(int j = 0; j < end; j++)
        {
            if(L.data[j] > L.data[j+1])
            {
                int temp = L.data[j];
                L.data[j] = L.data[j+1];
                L.data[j+1] = temp;
            }
        }
    }

    //cout << "排序完成!" << endl;
}

void eliminateRepeatingElements(SqList &L) // 消除重复元素
{
    for(int i = 0; i < L.length; i++)
    {
        for(int j = i - 1; j >= 0; j--)
        {
            if(L.data[i] == L.data[j])
            {
                for(int k = i + 1; k < L.length; k++)
                {
                    L.data[k-1] = L.data[k];
                }
                L.length--;
            }
        }
    }
    //cout << L.length << endl;
}