本文实例为大家分享了C++实现静态链表的具体代码，供大家参考，具体内容如下
一、动态链表和静态链表区别：
（1）动态链表：
（2）静态链表： 应用：二叉树
二、思路：
1.结点设置：T data；
int link;
2.链表要用一个avil来保存可分配空间的首地址；
3.初始化：引入头结点：elem[0]；
头结点先指向空NULL， 用-1表示；
avil存储空分配的空间的首地址1；
然后让其它可分配空间的结点的link指向坐标大一的结点；
三、实现程序：
|
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
|
#ifndef StaticList_h#define StaticList_hconst int maxSize = 100; // 静态链表大小template <class T>struct SLinkNode { T data; // 结点数据 int link; // 结点链接指针}; template <class T>class StaticList {public: void InitList(); // 初始化 int Length(); // 计算静态链表的长度 int Search(T x); // 在静态链表中查找具有给定值的结点 int Locate(int i); // 在静态链表中查找第i个结点 bool Append(T x); // 在静态链表的表尾追加一个新结点 bool Insert(int i, T x); // 在静态链表第i个结点后插入新结点 bool Remove(int i); // 在静态链表中释放第i个结点 bool isEmpty(); // 判链表空否？private: SLinkNode<T> elem[maxSize]; int avil; // 当前可分配空间首地址}; template <class T>void StaticList<T>::InitList() { // 初始化 elem[0].link = -1; avil = 1; // 当前可分配空间从1开始建立带表头结点的空链表 for(int i = 1; i < maxSize - 1; i++) elem[i].link = i + 1; // 构成空闲链接表 elem[maxSize-1].link = -1;} template <class T>int StaticList<T>::Length() { // 计算静态链表的长度 int p = elem[0].link; int i = 0; while(p != -1) { p = elem[p].link; i++; } return i;} template <class T>int StaticList<T>::Search(T x) { // 在静态链表中查找具有给定值的结点 int p = elem[0].link; // 指针p指向链表第一个结点 while(p != -1) { // 逐个结点检测查找给定的值 if(elem[p].data == x) break; else p = elem[p].link; } return p;} template <class T>int StaticList<T>::Locate(int i) { // 在静态链表中查找第i个结点 if(i < 0) // 参数不合理 return -1; if(i == 0) return 0; int j = 1, p = elem[0].link; while(p != -1 && j < i) { // 循链查找第i号结点 p = elem[p].link; j++; } return p;} template <class T>bool StaticList<T>::Append(T x) { // 在静态链表的表尾追加一个新结点 if(avil == -1) // 没有分配到存储空间 return false; int q = avil; // 分配结点 avil = elem[avil].link; // 指向下一个可分配的结点 elem[q].data = x; elem[q].link = -1; int p = 0; // 查找表尾 while(elem[p].link != -1) p = elem[p].link; elem[p].link = q; // 追加 return true;} template <class T>bool StaticList<T>::Insert(int i, T x) { // 在静态链表第i个结点后插入新结点 int p = Locate(i); if(p == -1) // 找不到结点 return false; int q = avil; // 分配结点 avil = elem[avil].link; elem[q].data = x; elem[q].link = elem[p].link; // 链入 elem[p].link = q; return true;} template <class T>bool StaticList<T>::Remove(int i) { // 在静态链表中释放第i个结点 int p = Locate(i-1); if(p == -1) // 找不到结点 return false; int q = elem[p].link; // 第i号结点 elem[p].link = elem[q].link; elem[q].link = avil; // 释放,让q的link指向原可分配的结点 avil = q; // avil指向q return true;} template <class T>bool StaticList<T>::isEmpty() { // 判链表空否？ if(elem[0].link == -1) return true; return false;} #endif /* StaticList_h */ |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/chuanzhouxiao/article/details/85992920
