C++实现静态链表

148 阅读 0 评论 98 点赞

我是靠谱客的博主悦耳香菇，最近开发中收集的这篇文章主要介绍C++实现静态链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

（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 */

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持靠谱客。