C++ 实现静态链表的简单实例
95 浏览量
2021-01-20
05:26:07
上传
评论
收藏 191KB PDF 举报
C++ 实现静态链表的简单实例实现静态链表的简单实例
C++ 实现静态链表的简单实例实现静态链表的简单实例
用数组描述的链表，即称为静态链表。
在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标cur。
这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。
下图表示了静态链表的一中存储结构：
图中用彩色途上的是两个头结点，不存放数据，分别用来记录第一个备用节点和第一个数据节点的下标。
下面给出静态链表的C++实现代码：
首先给出头文件：首先给出头文件：StaticList.h:
#include<iostream>
#include<assert.h>
using namespace std;
#define MAXSIZE 20 // 静态链表（数组）默认长度
#define ElemType int // 值类型
class StaticList;
//节点类
typedef class StaticListNode // 静态链表的节点类型（数组元素类型）
{
friend class StaticList;
private:
ElemType data; // 值域
int cur; // 游标 （指示当前节点的下一个元素下标）
}StaticListNode;
// 静态链表类</strong></span>
class StaticList
{
public:
StaticList()
{
for(int i = 2; i<MAXSIZE-1; ++i)
space[i].cur = i+1;
space[i].cur = 0; //整个链表结束
space[0].cur = 2;
space[1].cur = 0; //数据节点头的游标为空，没有数据
}
~StaticList()
{}
// 尾部插入法
void push_back(const ElemType &x)
{
int i = Malloc_SL();
if(0 == i) // 空间申请失败
{
cout<<"已满！"<<x<<"不能插入"<<endl;
return ;
}
space[i].data = x;
space[i].cur = 0;
int k = 1;
while(0!=k && 0!=space[k].cur) // 找到最后一个节点
k = space[k].cur;
space[k].cur = i; // 把刚申请的下标为i的节点链到最后一个节点后面
}
// 头部插入法
void push_front(const ElemType &x)
评论0
最新资源