一、动态链表和静态链表区别：
（1）动态链表：
（2）静态链表： 应用：二叉树
二、思路：
1.结点设置：T data；
int link;
2.链表要用一个avil来保存可分配空间的首地址；
3.初始化：引入头结点：elem[0]；
头结点先指向空NULL， 用-1表示；
avil存储空分配的空间的首地址1；
然后让其它可分配空间的结点的link指向坐标大一的结点；
三、实现程序：
#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 */
