如何实现一个静态链表结构？

本文共计1049个文字，预计阅读时间需要5分钟。

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

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

（1）动态链表：（2）静态链表：应用：

二、思路：

1.节点设置

改写后：

本文字例展示了C++实现静态链表的代码示例，供大家参考。主要内容包括：

一、动态链表与静态链表的区别：

（1）动态链表：（2）静态链表：应用：

二、思路：

1.节点设置

本文实例为大家分享了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 */

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