C++静态链表（c语言静态链表）

本文实例为大家分享了C++实现静态链表的具体代码，供大家参考，具体内容如下

一、动态链表和静态链表区别：

（1）动态链表：

C++静态链表（c语言静态链表）

（2）静态链表：应用：二叉树

C++静态链表（c语言静态链表）

二、思路：

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_h const 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 */