C++如何实现静态链表

发布时间:2020-07-29 15:04:09 作者:小猪
来源:亿速云 阅读:123

这篇文章主要讲解了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 <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 */

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

推荐阅读:
  1. 静态链表详解
  2. c++如何实现递归

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++ 静态链 c+

上一篇:C++实现十进制数转为其它进制数的方法

下一篇:C++如何实现双向冒泡排序算法

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》