题目 C++顺序表合并(数据结构严蔚敏C语言版的C++实现)
求两个线性表La和Lb的并集La = La U Lb （用顺序表实现）
( 要求：“就地运算”，运算结果仍然存放在La中 )
输入：线性表La、线性表Lb
输出：变化了的La
处理方法：扩大线性表La，将存在于线性表Lb 而不存在于线性表La中的数据元素插入到线性表La中去
一、问题分析
需要创建两个线性顺序表La和Lb，先从线性表Lb中依次取得每个数据元素，依值在线性表La中进行遍历比较查访，若La中该元素不存在，则在La的表尾插入。
二、代码
对于问题一进行求解，设计了unionL函数，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
Status unionL(SqList &La,SqList Lb)
{
// 求各表的长度
int La_len = ListLength(La);
int Lb_len = ListLength(Lb);
int e; //初始化e
for (int i = 1; i <= Lb_len; i++)
{
GetElem(Lb,i,e);
if (!LocateElem(La, e))
{
ListInsert(La, ++La_len, e);
}
}
return OK;
}
|
三、分析
通过读表元函数将Lb中的元素读取出来，再对该元素对La进行下标查找，如果查找不到，在表的最后面插入该元素。
四、实验过程记录
这个程序我在码的过程中难点是操作函数的编写，特别是一些自增自减符，写着写着就忘记是先运算再使用还是先使用再运算了，这给我后面写实际解决方案时带来了很大的困难，没有报错却又找不到哪里有错误使得结果有误。
完整代码
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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
|
//显示中文
#define _CRT_SECURE_NO_WARNINGS
#include <windows.h>//用于函数SetConsoleOutputCP(65001);更改cmd编码为utf8
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//初始空间参数
#define LIST_INIT_SIZE 100 //线性表的初始存储空间
#define LISTINCREMENT 10 //线性表的增量空间
#include<iostream>
#include<stdlib.h>
using namespace std;
//设置状态码和数据类型
typedef int Status;
typedef int ElemType;
//定义顺序表
typedef struct SqList{
ElemType *elem; //头指针指向数组首元素
int Length; //线性表的当前长度
int Listsize; //线性表的当前容量
};
//初始化
Status InitList(SqList &L)
{
//给表分配空间
L.elem = new ElemType(LIST_INIT_SIZE);
//判断是否生成
if(!L.elem)
{
return OVERFLOW;
}
else
{
L.Listsize = LIST_INIT_SIZE; //表长度为初始值
L.Length = 0; //表默认长度0
return OK;
}
};
//销毁
Status DestroyList(SqList &L)
{
if(L.elem != NULL)//判断表是否已存在
{
free(L.elem);
L.elem = NULL;
L.Length = 0;
L.Listsize = 0;
return OK;
}
else
{
return ERROR;
}
}
//判空
bool ListEmpty(SqList L)
{
if(L.Listsize == 0)//如果顺序表的长度为0，则表为空
{
return true;
}
else
{
return false;
}
}
//求表长
int ListLength(SqList L)
{
return L.Length;//返回顺序表表长
}
//查找返回下标
int LocateElem(SqList L,ElemType e) //bool compare(int p,int e)
{
int *p,i;
p = L.elem;
i = 1;
while (i <= L.Length && *p++ != e)//后置++高于*
i++;
if (i > L.Length)
i = 0;
return i;
}
//读表元(已经自动转换下标了)
Status GetElem(SqList L,int i,ElemType &e)
{
if(i<1 || i>ListLength(L))
return OVERFLOW;
int *p;
p = &(L.elem[i-1]);
e = *p;
return OK;
}
//打印函数
void Print(SqList L)
{
for (int i = 0; i < L.Length; i++)
{
cout << L.elem[i] << "";
}
cout << endl;
}
//求前驱
ElemType PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)
{
if(L.elem != NULL)
{
int i = LocateElem(L,cur_e);
if(i==0 || i ==1)
{
pre_e = NULL;
}
else
{
pre_e = L.elem[i-2];
}
return pre_e;
}
}
//求后继
ElemType NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{
if(L.elem != NULL)
{
int i = LocateElem(L,cur_e);
if(i==0 || i ==1)
{
next_e = NULL;
}
else
{
next_e = L.elem[i];
}
return next_e;
}
}
//线性表置空
Status ClearList(SqList &L)
{
if(L.elem != NULL)
{
L.Length = 0;
return OK;
}
else
{
return ERROR;
}
}
//赋值
Status PutElem(SqList &L,int i,ElemType &e)
{
if(L.elem != NULL && !i<1 && !i>ListLength(L))
{
L.elem[i] = e;
return OK;
}
else
{
return ERROR;
}
}
//插入元素
Status ListInsert(SqList &L,int i,ElemType e)
{
//判断是否非法
if(i<1||i>L.Length+1)
{
return OVERFLOW;
}
//判断是否满了，如果满动态扩展
if (L.Length >= L.Listsize)
{
//计算新表大小
int newsize = L.Listsize + LISTINCREMENT;
//分配新空间
int *newbase = (ElemType *)realloc(L.elem,newsize*sizeof(ElemType));//已经自动释放原L，并拷贝数据到新空间
//判断是否成功分配
if(!newbase) exit(OVERFLOW);
//更新新空间指向
L.elem = newbase;
//更新容量
L.Listsize += LISTINCREMENT;
}
int *q,*p;
q = &L.elem[i-1];//令q指向ai，静态
for(p = L.elem+L.Length-1; p>=q ;--p)//下标从0开始，第几个元素得减1
{
//从后往前检索，逐个元素后移
*(p+1) = *p;
}
*q = e;
++L.Length;
return OK;
}
//删除元素
Status ListDelete(SqList &L,int i,ElemType &e)
{
if(i<1||i>L.Length)
{
return ERROR; //i非法
}
ElemType *p=L.elem+i-1;//p为被删除元素的位置
e=*p;//被删除元素的值赋给e
ElemType *q=L.elem+L.Length-1;//表尾元素的位置
for(++p;p<=q;++p)
{
*(p-1)=*p; //左移一位
}
L.Length--; //表长减1
return OK;
}
//合并两表
Status unionL(SqList &La,SqList Lb)
{
int La_len = ListLength(La); // 求各表的长度
int Lb_len = ListLength(Lb);
int e; //初始化e
for (int i = 1; i <= Lb_len; i++)
{
GetElem(Lb,i,e); // 取Lb中第i个数据元素赋给e
if (!LocateElem(La, e))
{
ListInsert(La, ++La_len, e);
// La中不存在和 e 相同的数据元素，则插入
}
}
return OK;
}
//实验1
void test01()
{
SqList La;
InitList(La);
int a;
cout << "顺序表La的5个元素：" << endl;
for (int j = 0; j < 5; j++)
{
cin >> a;
ListInsert(La, j+1, a);
}
SqList Lb;
InitList(Lb);
int b;
cout << "顺序表Lb的5个元素：" << endl;
for (int k = 0; k < 5; k++)
{
cin >> b;
ListInsert(Lb, k+1, b);
}
unionL(La,Lb);
cout << "La与Lb的并集为：" << endl;
int l = 0;
while(l<La.Length)
{
cout<<La.elem[l]<<endl;
l++;
}
cout<<endl;
DestroyList(La);
DestroyList(Lb);
}
int main()
{
//显示中文
SetConsoleOutputCP(65001);
//实验1
test01();
system("pause");
return 0;
}
|
