数据结构实验1_顺序表的操作

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
306
307
308
309
310
/*
实验要求：
写出
Status initlist(sqlist &L)
Status listinsert( sqlist &L,
int i,
int e )
Status listindele( sqlist &L,
int i,
int &e )
Status listinprint( sqlist L)
void MergeList(sqlist La, sqlist Lb, sqlist &Lc)
等几个函数，实验手工创建两个非递减序列存放于La和
Lb中，并调用MergeList实现数据的合并。
关于程序健壮性的内容：
1、对于插入与删除位置若不合法请给出适当提醒
2、若输入的数据不是非递减排列可通过自己写的sort()函数排序后再进行后续操作
*/
#include<stdio.h>
#include<stdlib.h>
const int size=100,add=20;//初始大小和增加大小
struct sqlist
{
int *base;//存储空间首地址
int lenth;//长度
int maxlenth;//容量
};
void init_list(sqlist &list)//创建和初始化顺序表
{
list.base=new int[size];
list.lenth=0;
list.maxlenth=size;
printf("创建顺序表完成！请继续操作！n");
return;
}
void list_insert(sqlist &list,int i,int x)//在第 i 个位置插入元素 x
{
if(i>0&&i<=list.lenth)//长度合法
{
int temp=list.lenth,k;
if(list.lenth==list.maxlenth)// 否则就拓展
{
printf("空间不足，是否拓展内存？n 1：是 2：否n");
int key;
scanf("%d",&key);
if(key==1)
{
int *newbase=(int *)realloc(list.base,(list.maxlenth+add)*sizeof(int));
if(!newbase)
{
printf("计算机内存不足，空间分配失败！请重新操作！n");
return;
}
list.base=newbase;
list.maxlenth+=add;
}
else
{
printf("操作已取消，请重新操作！n");
return;
}
}
for(k=temp;k>=i;--k)
{
list.base[k]=list.base[k-1];
}
list.base[i-1]=x;
++list.lenth;
printf("操作完成，请继续操作！n");
}
else
{
printf("操作请求失败，请重新操作！n");
}
}
void list_delete(sqlist &list,int i,int &x)//删除第 i 个元素，保存在 x 中
{
if(i>0&&i<list.lenth)
{
x=list.base[i-1];
for(int k=i-1;k<list.lenth+1;++k)
{
list.base[k]=list.base[k+1];
}
--list.lenth;
printf("删除第%d个元素 %d 成功，请继续操作！n",i,x);
}
else
{
printf("操作请求失败，请重新操作！n");
}
}
void list_print(sqlist list)//输出线性表中元素
{
if(list.lenth)
{
printf("%d",list.base[0]);
for(int i=1;i<list.lenth;++i)
{
printf(" %d",list.base[i]);
}
printf("n输出完成，请重新操作！n");
}
else
{
printf("n顺序表为空，请重新操作！n");
}
}
void sort(int a[],int low,int high)//快速排序
{
int i=low,j=high-1,k,temp=a[i];
if(low<high)//控制递归的出口
{
while(i<j)
{
while((a[j]>=temp)&&(i<j))//查找比标志小的
{
j--;
}
a[i]=a[j];//挪动位置
while((a[i]<=temp)&&(i<j))//查找比标志大的
{
i++;
}
a[j]=a[i];//继续挪动位置
}
a[i]=temp;//移动标志
sort(a,low,i);//分部分递归
sort(a,j+1,high);
}
}
void merge_list(sqlist la,sqlist lb,sqlist &lc)//线性表元素集合的有序合并
{
init_list(lc);
int *pa=la.base,*pb=lb.base,*pc=lc.base,*pa_end,*pb_end;
pa_end=pa+la.lenth;pb_end=pb+lb.lenth;
while((pa<pa_end)&&(pb<pb_end))//归并元素
{
while(*pa==*pc)//去掉lc 中相同的元素
{
*pa++;
}
while(*pb==*pc)
{
*pb++;
}
if(*pa<*pb)//小的排在前面
{
*pc++=*pa++;
}
else if(*pa>*pb)//大的排在后面
{
*pc++=*pb++;
}
else//相同的只保留一个
{
*pc++=*pa++;
*pb++;
}
++lc.lenth;
}
while(pa<pa_end)//连接la最后可能剩下的部分
{
*pc++=*pa++;
++lc.lenth;
}
while(pb<pb_end)//连接lb最后可能剩下的部分
{
*pc++=*pb++;
++lc.lenth;
}
printf("合并完成，请继续操作！n");
}
int main()
{
sqlist list[3];
int come=1,kase=0,key,ok=0;
while(1)
{
printf("*****|请输入操作指令|*****n");
printf("*****|0:退出*****n");
printf("*****|1:创建*****n");
printf("*****|2:插入*****n");
printf("*****|3:删除*****n");
printf("*****|4:输出*****n");
printf("*****|5:合并*****nn");
printf("请输入操作指令:n");
scanf("%d",&come);
if(come==0)
{
printf("退出成功，谢谢使用！n");
return 0;
}
else if(!kase&&come==1)//创建
{
int n;
init_list(list[1]);init_list(list[2]);
printf("请输入表 1 的元素个数(0<=n<=%d)：n",list[1].maxlenth);
//	p[1]=list[1].base;p[2]=list[2].base;
scanf("%d",&n);
list[1].lenth=n;
printf("请输入表中元素：n");
for(int i=0;i<n;++i)
{
scanf("%d",&list[1].base[i]);
}
printf("请输入表 2 的元素个数(0<=n<=%d)：n",list[2].maxlenth);
scanf("%d",&n);
list[2].lenth=n;
printf("请输入表中元素：n");
for(int i=0;i<n;++i)
{
scanf("%d",&list[2].base[i]);
}
kase=1;//标记是否创建过顺序表
printf("操作完成，请继续操作！n");
printf("请输入指令：1 返回主程序n");
scanf("%d",&key);
if(key==1)
{
system("cls");
}
}
else if(kase&&come==2)//插入
{
int n,i,x;
printf("请输入需要操作的对象(表 n(0<=n<=%d))，插入位置，插入元素：n",ok+1);
//控制处理对象的范围
scanf("%d%d%d",&n,&i,&x);
if(n>=0&&n<=ok+1)
{
list_insert(list[n],i,x);
}
else
{
printf("操作错误，请重新输入！n");
}
printf("请输入指令：1 返回主程序n");
scanf("%d",&key);
if(key==1)
{
system("cls");
}
}
else if(kase&&come==3)//删除
{
int n,i,x;
printf("请输入需要操作的对象(表 n(0<=n<=%d))，删除位置：n",ok+1);
scanf("%d%d",&n,&i);
if(n>=0&&n<=ok+1)
{
list_delete(list[n],i,x);
}
else
{
printf("操作错误，请重新输入！n");
}
printf("请输入指令：1 返回主程序n");
scanf("%d",&key);
if(key==1)
{
system("cls");
}
}
else if(kase&&come==4)//输出
{
int n;
printf("请输入需要操作的对象(表 n(0<=n<=%d))n",ok+1);
scanf("%d",&n);
if(n>=0&&n<=ok+1)
{
list_print(list[n]);
}
else
{
printf("操作错误，请重新输入！n");
}
printf("请输入指令：1 返回主程序n");
scanf("%d",&key);
if(key==1)
{
system("cls");
}
}
else if(kase&&come==5)//合并
{
sort(list[1].base,0,list[1].lenth);//对表排序
sort(list[2].base,0,list[2].lenth);
merge_list(list[1],list[2],list[0]);//合并
ok=1;//改变对象的个数
printf("请输入指令：1 返回主程序n");
scanf("%d",&key);
if(key==1)
{
system("cls");
}
}
else
{
printf("操作错误，请重新输入！n");
printf("请输入指令：1 返回主程序n");
scanf("%d",&key);
if(key==1)
{
system("cls");
}
}
}
return 0;
}