C++之顺序表的基本操作

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

#include <iostream>
using namespace std;
#define Maxsize 100//最大空间
typedef struct
{
int *elem;
int length;//顺序表长度
} SqList;
bool InitList(SqList &L) //构造一个空的顺序表L
{
L.elem = new int[Maxsize];
L.length = 0;
return true;
}
bool CreateList(SqList &L,int a)//创建一个顺序表L
{
int	i;
int p;
for(i=0; i<a; i++)
{
cout<<"请输入第"<<i+1;
cout<<"个元素";
cin>>p;
L.elem[i]=p;
L.length++;
}
return true;
}
bool GetElem(SqList L)
{
int e,i;
cout << "输入整型数i,取第i个元素输出" << endl;
cin >> i;
if (i<1 || i>L.length)
{
return false;
}
e = L.elem[i - 1];//第i-1的单元存储着第i个数据
cout << "第i个元素是：" << e << endl;
return true;
}
void AddElem(SqList &L)
{
int m;
int n=L.length;
cout<<"请输入要添加到元素"<<endl;
cin>>m;
L.elem[n]=m;
L.length++;
}
bool InsertSqList(SqList &L)
{
int i,e;
cout << "请输入要插入的位置和要插入的数据元素e：";
cin >> i >> e;
if (i<1 || i>L.length + 1)
{
return false;//i值不合法
}
if (L.length == Maxsize)
{
return false;//存储空间已满
}
for (int j = L.length - 1; j >= i - 1; j--)
{
L.elem[j + 1] = L.elem[j];//从最后一个元素开始后移，直到第i个元素后移
}
L.elem[i - 1] = e;//将新元素e放入第i个位置
L.length++;//表长加1
return true;
}
bool DeleteSqList(SqList &L)
{
int i;
cout << "请输入要删除的位置i:";
cin >> i;
if ((i < 1) || (i > L.length))
{
return false;//i值不合法
}
for (int j = i; j <= L.length - 1; j++)
{
L.elem[j - 1] = L.elem[j];//被删除元素之后的元素后移
}
L.length--;//表长减少1
return true;
}
void print(SqList &L)
{
cout << "输出顺序表" << endl;
for (int j = 0; j <= L.length - 1; j++)
cout << L.elem[j] << " ";
cout << endl;
}
void PrintNum(SqList &L)
{
int n=L.length;
cout<<"顺序表的元素个数为"<<n;
}
void DestroyList(SqList &L)
{
if (L.elem)
{
delete[]L.elem;//释放存储空间
}
}
void Sort(SqList &L)
{
int i,j;
int temp;
for(i=0;i<L.length;i++)
{
for(j=i+1;j<L.length;j++)
{
if(L.elem[i]<L.elem[j])
{
temp=L.elem[i];
L.elem[i]=L.elem[j];
L.elem[j]=temp;
}
}
}
}
void mergelist(SqList &L,SqList &S,SqList &Sq)
{
int i=0,j=0,k=0;
while((i<=L.length)&&(j<=S.length))
{
if(L.elem[i]<=S.elem[j])
{
Sq.elem[k]=L.elem[i];
i++;
k++;
}
else
{
Sq.elem[k]=S.elem[j];
j++;
k++;
}
}
while(i<=L.length)
{
Sq.elem[k]=L.elem[i];
i++;
k++;
}
while(j<=S.length)
{
Sq.elem[k]=S.elem[j];
j++;
k++;
}
Sq.length=L.length+S.length+1;
}
int main()
{
SqList L;
SqList S;
SqList Sq;
cout << "1.在表尾添加新成员n";
cout << "2.在指定位置前插入新成员 n";
cout << "3.删除指定位置的成员n";
cout << "4.输出指定位置处成员信息n";
cout << "5.输出所有成员信息n";
cout << "6.输出表中成员个数n";
cout << "7.合并两个有序顺序表n";
cout << "8.销毁n";
cout << "0.退出n";
int num = 0;
int choose = -1;
InitList(L);
InitList(S);
InitList(Sq);
cout<<"请输入顺序表的元素个数"<<endl;
cin>>num;
CreateList(L,num);
while (choose != 0)
{
cout << "请选择:";
cin >> choose;
switch (choose)
{
case 1:
AddElem(L);
break;
case 2:
if (InsertSqList(L))
cout << "插入成功！" << endl;
else
cout << "插入失败!" << endl;
break;
case 3:
if (DeleteSqList(L))
cout << "删除成功！" << endl;
else
cout << "删除失败！" << endl;
break;
//查找
case 4:
if (GetElem(L))
{
//cout << "第i个元素是：" << e << endl;
}
else
cout << "顺序表取值失败！" << endl;;
//cout << "第i个元素是：" << e << endl;
break;
case 5:
print(L);
break;
case 6:
PrintNum(L);
break;
case 7:
CreateList(S,num);
Sort(L);
Sort(S);
mergelist(L,S,Sq);
print(Sq);
break;
case 8:
cout << "顺序表销毁·····" << endl;
DestroyList(L);
break;
}
}
return 0;
}