C++如何实现静态链表

这篇文章主要讲解了C++如何实现静态链表，内容清晰明了，对此有兴趣的小伙伴可以学习一下，相信大家阅读完之后会有帮助。

为卢龙等地区用户提供了全套网页设计制作服务，及卢龙网站建设行业解决方案。主营业务为网站建设、网站设计、卢龙网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

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

（1）动态链表：

C++如何实现静态链表

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

C++如何实现静态链表

二、思路：

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 
struct SLinkNode {
 T data; // 结点数据
 int link; // 结点链接指针
};
 
template 
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 elem[maxSize];
 int avil; // 当前可分配空间首地址
};
 
template 
void StaticList::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 
int StaticList::Length() {
 // 计算静态链表的长度
 int p = elem[0].link;
 int i = 0;
 
 while(p != -1) {
 p = elem[p].link;
 i++;
 }
 return i;
}
 
template 
int StaticList::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 
int StaticList::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 
bool StaticList::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 
bool StaticList::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 
bool StaticList::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 
bool StaticList::isEmpty() {
 // 判链表空否？
 if(elem[0].link == -1)
 return true;
 return false;
}
 
#endif /* StaticList_h */

看完上述内容，是不是对C++如何实现静态链表有进一步的了解，如果还想学习更多内容，欢迎关注创新互联行业资讯频道。

本文标题：C++如何实现静态链表
网页路径：http://cqcxhl.com/article/jijppe.html

重庆分公司，新征程启航

C++如何实现静态链表

其他资讯