C++ 实现静态链表的简单实例
用数组描述的链表，即称为静态链表。
在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标cur。
这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。
下图表示了静态链表的一中存储结构：
图中用彩色途上的是两个头结点，不存放数据，分别用来记录第一个备用节点和第一个数据节点的下标。
下面给出静态链表的C++实现代码：
首先给出头文件：StaticList.h:
|
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
|
#include<iostream>#include<assert.h>using namespace std;#define MAXSIZE 20 // 静态链表（数组）默认长度#define ElemType int // 值类型class StaticList;//节点类typedef class StaticListNode // 静态链表的节点类型（数组元素类型）{ friend class StaticList;private: ElemType data; // 值域 int cur; // 游标 （指示当前节点的下一个元素下标）}StaticListNode;// 静态链表类</strong></span>class StaticList{public: StaticList() { for(int i = 2; i<MAXSIZE-1; ++i) space[i].cur = i+1; space[i].cur = 0; //整个链表结束 space[0].cur = 2; space[1].cur = 0; //数据节点头的游标为空，没有数据 } ~StaticList() {}// 尾部插入法 void push_back(const ElemType &x) { int i = Malloc_SL(); if(0 == i) // 空间申请失败 { cout<<"已满！"<<x<<"不能插入"<<endl; return ; } space[i].data = x; space[i].cur = 0; int k = 1; while(0!=k && 0!=space[k].cur) // 找到最后一个节点 k = space[k].cur; space[k].cur = i; // 把刚申请的下标为i的节点链到最后一个节点后面 }// 头部插入法 void push_front(const ElemType &x) { int i = Malloc_SL(); if(0 == i) // 同上，空间申请失败 { cout<<"已满！"<<x<<"不能插入"<<endl; return ; } space[i].data = x; // 把x放入刚申请的节点中 space[i].cur = space[1].cur; // 此时刚申请的节点i的游标指向第一个数据节点，称为第一个结点 space[1].cur = i; // 使头结点指向第一个数据节点 }// 尾部删除 void pop_back() { int i = space[1].cur; int j = 0; for(; 0!=space[i].cur; j = i, i = space[i].cur) {} // 找到最后一个节点以及倒数第二个节点 space[j].cur = 0; // 倒数第二个节点的游标赋空 Free_SL(i); // 最后一个节点被释放 }// 头部删除 void pop_front() { int i = space[1].cur; // i是第一个数据节点的下标 space[1].cur = space[i].cur; // 头结点指向第二个数据节点的下标 Free_SL(i); // i 节点被释放 } void show_list() { for(int i = space[1].cur; i!=0; i = space[i].cur) cout<<space[i].data<<" "; cout<<"Over"<<endl; } /* 静态链表从小到大排序的前提下，插入x */ void insert_val(const ElemType &x) { int k = 1; while(0!=k && 0!=space[k].cur && space[space[k].cur].data<x) k = space[k].cur; //在下标k之后插入 if(0 == space[k].cur) // 如果k指向最后一个节点，执行尾插 push_back(x); else if(k == 1) // 如果k指向第一个节点，执行头插 push_front(x); else // 在中间任意位置插入x { int i = Malloc_SL(); assert(0 != i); space[i].data = x; space[i].cur = space[k].cur; // i节点的游标指向k节点后面的一个节点 space[k].cur = i; // k节点的游标指向新开辟的i节点 } } /* 返回key的前一个节点下标*/ int find(const ElemType &key) { int i = 1; while(0!=i && space[space[i].cur].data!=key) i = space[i].cur; if(0 == i) { cout<<"没找到 "<<key<<endl; return -1; } return i; } /* 删除给定的值key所在节点，若没找到则返回 */ void delete_val(const ElemType &key) { int i = find(key); if(-1 == i) // 说明静态链表中没有元素key return ; else if(1 == i) // key 处于下标为2的节点(第一个数据节点) pop_front(); else if(0 == space[i].cur) // key处于最后一个节点 pop_back(); else // key 处于中间任意位置 { int k = space[i].cur; // 记录要删除位置的下标 space[i].cur = space[k].cur; // 脱离出要删除节点 Free_SL(k); // 删除key所在节点 } } /* sl1 和 sl2已存在，把它们糅合到另一个链表，使之按非递减排列 */ void merge(StaticList &sl1, StaticList &sl2) { sl1.sort(); sl2.sort(); if(0==sl1.length() || 0==sl2.length()) return ; int p = sl1.space[1].cur; int q = sl2.space[1].cur; while(0!=p && 0!=q) { // 哪个数据较小，就把该数据尾插到新链表中，并使游标指向下一个 if(sl1.space[p].data < sl2.space[q].data) { push_back(sl1.space[p].data); p = sl1.space[p].cur; } else { push_back(sl2.space[q].data); q = sl2.space[q].cur; } } while(0!=p) { // 因为sl1已经有序，如果sl1还没有全部插入新链表，就把剩下的全部插入 push_back(sl1.space[p].data); p = sl1.space[p].cur; } while(0!=q) { // 因为sl2已经有序，如果sl2还没有全部插入新链表，就把剩下的全部插入 push_back(sl2.space[q].data); q = sl2.space[q].cur; } } /* 如果静态链表无序，使其按非递减顺序排列 */ void sort() { int s = space[1].cur; int p = space[s].cur; if(0 == p) return ; space[s].cur = 0; int k = 1; int k1 = 0; while(0 != p) { s = p; p = space[p].cur; k = 1; // 找到一个位置k, 在k后插入s所指节点的数据 while(0!=k && space[space[k].cur].data < space[s].data) { k1 = k; //如果k==0,用k1记录最后一个数据节点 k = space[k].cur; //在下标k之后插入 } if(0 == k) //尾插 { space[k1].cur = s; space[s].cur = 0; } else //头插和中间插 { space[s].cur = space[k].cur; space[k].cur = s; } } } /* 逆置静态链表 */ void reserve() { int s = space[1].cur; int p = space[s].cur; if( 0==p ) return ; space[s].cur = 0; while(0 != p) { s = p; p = space[p].cur; space[s].cur = space[1].cur; // 把s所指节点 头插进原有链表 space[1].cur = s; // s成为第一个数据节点 } } /* 清空静态链表 */ void clear() { for(int i = 2; i<MAXSIZE-1; ++i) space[i].cur = i+1; space[i].cur = 0; space[0].cur = 2; // 下标2成为第一个备用节点 space[1].cur = 0; // 第一个数据节点为空 } /* 返回表长 */ int length() { if(0 == space[1].cur) return 0; int i = 1; int count = -1; do { ++count; i = space[i].cur; }while(0 != i); return count; } /* 返回下标为k的节点的下一个节点下标 在静态链表中用处不大*/ int next(const int k) { if(0==k || 1==k) return -1; return space[k].cur; } /* 返回下标为k的节点的上一个节点下标 */ int prio(const int k) { if(0==k || 1==k) return -1; int p = 1; while(0!=p && space[p].cur!=k) p = space[p].cur; return p; }protected: /* 用来申请一个空间，返回该节点的下标 */ int Malloc_SL() { int i = space[0].cur; // 0下标的游标指向第一个备用节点 if(space[0].cur) space[0].cur = space[i].cur; // 修改头结点保存的第一个备用节点下标 return i; } /* 释放下标为k的节点 */ void Free_SL(int k) { space[k].cur = space[0].cur; // 该节点的游标指向第一个备用节点 space[0].cur = k; // 该节点称为第一个备用节点 }private: StaticListNode space[MAXSIZE];}; |
下面是测试代码：Main.cpp
|
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
|
#include"StaticList.h"void main(){ StaticList SL; StaticList SL1; //测试merge() StaticList SL2; SL1.push_back(1); SL1.push_back(9); SL1.push_back(0); SL1.push_back(6); SL1.push_back(999); SL2.push_back(5); SL2.push_back(8); SL2.push_back(100); ElemType Item = 0; int select = 1; while(select) { cout<<"********************************************"<<endl; cout<<"*[1] push_back [2] push_front *"<<endl; cout<<"*[3] show_list [4] pop_back *"<<endl; cout<<"*[5] pop_front [6] insert_val *"<<endl; cout<<"*[7] length [8] find *"<<endl; cout<<"*[9] merge [10] delete_val *"<<endl; cout<<"*[11] sort [12] reserve *"<<endl; cout<<"*[13] next [14] prio *"<<endl; cout<<"*[15] clear [16] destroy *"<<endl; cout<<"*[0] quit_sys *"<<endl; cout<<"********************************************"<<endl; cout<<"请选择：》"; cin>>select; switch(select) { case 1: cout<<"输入要尾插的数据:(-1结束)>"; while(cin>>Item && -1 != Item) SL.push_back(Item); break; case 2: cout<<"输入要头插的数据:(-1结束)>"; while(cin>>Item && -1 != Item) SL.push_front(Item); break; case 3: SL.show_list(); break; case 4: SL.pop_back(); break; case 5: SL.pop_front(); break; case 6: cout<<"输入要插入的数据:>"; cin>>Item; SL.insert_val(Item); break; case 7: cout<<"链表长度为："<<SL.length()<<endl; break; case 8: cout<<"输入要查找的数据:>"; cin>>Item; SL.find(Item); break; case 9: SL.merge(SL1, SL2); break; case 10: cout<<"输入要删除的数据:>"; cin>>Item; SL.delete_val(Item); break; case 11: SL.sort(); break; case 12: SL.reserve(); break; case 13: SL.next(0); break; case 14: SL.prio(0); break; case 15: SL.clear(); break; case 16: SL.~StaticList(); break; default: break; } }} |
下面是测试截图：
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/chengzi_comm/article/details/51397522
