概述
静态链表是利用数组来模拟存储空间来实现链表的，因为在整个运算过程中它的存储空间的大小不会改变，所以我们称之为 静态链表。
特点：
1.由数组模拟存储空间，实现链表。
2.可以不改变物理位置。通过改变链接来实现链表。
3.每个结点有一个data存放数据，next存放链接，有一个avail指针存放下一个空结点的位置。
图是自己做的，有点简陋，不过还是可以看明白的。
之后简单说一下实现的步骤，基本原理就是新建一个数组，用这个数组来存放节点，而每个节点有两个域，其中data存放数据，next存放链表中下一个节点的位置，注意链表的顺序不一定是和数组的顺序相同的，同时还有一个avail指针指向下一个空的位置，我们每一次插入数据或者删除数据都需要对next和avail的指向进行更新，以保证链表的正常。同时要注意链表表尾元素的next是要赋值为-1表示链表的结束。OK，具体的不再说，看完代码就懂了。
LinkList.h
#ifndef __LK_LIST_H__
#define __LK_LIST_H__
#include "Assistance.h" // 辅助软件包
// 静态链表类
template <class ElemType>
class LinkList
{
protected:
// 静态链表的数据成员
int head;
int maxLength; //最长长度
int avail; //备用指链表表头
struct Data
{
ElemType data;
int next;下一个结点的位置
};
Data *sll; //数组
public:
// 静态链表的函数成员
LinkList(int maxLength=10000); // 构造函数
virtual ~LinkList(); // 析构函数
int GetLength() const; // 求静态链表长度
bool IsEmpty() const; // 判断静态链表是否为空
void Clear(); // 将静态链表清空
void Traverse(void (*Visit)(const ElemType &)) const;// 遍历静态链表
int LocateElem(const ElemType &e) const; // 元素定位
Status GetElem(int position, ElemType &e) const; // 求指定位置的元素
Status SetElem(int position, const ElemType &e); // 设置指定位置的元素值
Status DeleteElem(int position, ElemType &e); // 删除元素
Status InsertElem(int position, const ElemType &e); // 在指定位置插入元素
Status InsertElem(const ElemType &e); // 在表尾插入元素
/*
LinkList(const LinkList<ElemType> &la); // 复制构造函数
LinkList<ElemType> &operator =(const LinkList<ElemType> &la); // 重载赋值运算 */
};
// 静态链表类的实现部分
template <class ElemType>
LinkList<ElemType>::LinkList(int maxLen)
// 操作结果：构造一个空链表
{
maxLength=maxLen;
head=0; //未使用头结点
sll =new Data[maxLength]; //新建空数组
for(int i=0;i< maxLen; i++) //将数组中每个元素指向下个元素
sll[i].next=i+1;
sll[maxLen-1].next=-1; //最后一位指向-1，代表数组结束
avail=1; //链表未使用时avail指向0
}
template <class ElemType>
LinkList<ElemType>::~LinkList()
// 操作结果：销毁静态链表
{
delete []sll;
}
template <class ElemType>
int LinkList<ElemType>::GetLength() const
// 操作结果：返回单链表的长度
{
int length=0;
int j=head;
while(sll[j].next !=-1){
length++;
j=sll[j].next;
}
return length;
}
template <class ElemType>
bool LinkList<ElemType>::IsEmpty() const
// 操作结果：如静态链表为空，则返回true，否则返回false
{
return sll[head].next==-1;
}
template <class ElemType>
void LinkList<ElemType>::Clear()
// 操作结果：清空单链表,删除单链表中所有元素结点
{
int j=head;
int k=1;
for(j=head;sll[j].next!=-1;j=sll[j].next){
sll[j].data='0';
sll[j].next=k;
k++;
}
sll[j].next=k;
sll[head].next=-1;
avail=1;
}
template <class ElemType>
void LinkList<ElemType>::Traverse(void (*Visit)(const ElemType &)) const
// 操作结果：依次对单链表的每个元素调用函数(*visit)访问
{
int j=head;
while (sll[j].next != -1) {
(*Visit)(sll[sll[j].next].data); // 对单链表中每个元素调用函数(*visit)访问
j=sll[j].next;
}
}
template <class ElemType>
int LinkList<ElemType>::LocateElem(const ElemType &e) const
// 元素定位
{
int j=head;
int count = 1;
while (sll[j].next != -1 && sll[j].data != e) {
count++;
j=sll[j].next;
}
if(count-1 > GetLength())
{
if(sll[count-1].data == e||sll[count-2].data == e)
return count-1;
else
return RANGE_ERROR;}
else
return count-1;
}
template <class ElemType>
Status LinkList<ElemType>::GetElem(int i, ElemType &e) const
// 操作结果：当链表存在第i个元素时，用e返回其值，函数返回ENTRY_FOUND,
// 否则函数返回NOT_PRESENT
{
if (i < 1 || i > GetLength())
return RANGE_ERROR;
else {
int j=head;
int count;
for (count = 1; count <= i; count++)
j=sll[j].next; // j指向第i个结点
e=sll[j].data; // 用e返回第i个元素的值
return ENTRY_FOUND;
}
}
template <class ElemType>
Status LinkList<ElemType>::SetElem(int i, const ElemType &e)
// 操作结果：将链表的第i个位置的元素赋值为e,
// i的取值范围为1≤i≤length,
// i合法时函数返回SUCCESS,否则函数返回RANGE_ERROR
{
if (i < 1 || i > GetLength())
return RANGE_ERROR;
else {
int j=head;
int count;
for (count = 1; count <= i; count++)
j=sll[j].next; // 取出指向第i个结点的指针
sll[j].data = e; // 修改第i个元素的值为e
return SUCCESS;
}
}
template <class ElemType>
Status LinkList<ElemType>::DeleteElem(int i, ElemType &e)
// 操作结果：删除链表的第i个位置的元素, 并用e返回其值,
// i的取值范围为1≤i≤length,
// i合法时函数返回SUCCESS,否则函数返回RANGE_ERROR
{
if (i < 1 || i > GetLength())
return RANGE_ERROR; // i范围错
else {
int j=head,k,l;
for (int count = 1; count < i; count++)
j=sll[j].next;
k=sll[sll[j].next].data;
l=sll[sll[j].next].next;
sll[sll[j].next].data='0';
sll[sll[j].next].next=avail;
int temp=sll[j].next;
sll[j].next =l;
avail=temp;
e = k; // 用e返回被删结点元素值
return SUCCESS;
}
}
template <class ElemType>
Status LinkList<ElemType>::InsertElem(int i, const ElemType &e)
// 操作结果：在链表的第i个位置前插入元素e
// i的取值范围为1≤i≤length+1
// i合法时返回SUCCESS, 否则函数返回RANGE_ERROR
{
if (i < 1 || i > GetLength()+1 || GetLength()+1 > maxLength)
return RANGE_ERROR;
else {
int j=head;
int k=avail;
int count;
if(i==GetLength()+1)
InsertElem(e);
else if(i==1){
avail=sll[k].next;
int temp=sll[head].next;
sll[k].data=e;
sll[head].next=k;
sll[k].next=temp;
}
else{
avail=sll[k].next;
for (count = 1; count < i; count++)
j=sll[j].next; // p指向第i-1个结点
int temp=sll[j].next;
sll[j].next=k;
sll[k].data=e;
sll[k].next=temp;
}
return SUCCESS;
}
}
template <class ElemType>
Status LinkList<ElemType>::InsertElem(const ElemType &e)
// 操作结果：在静态链表的表尾位置插入元素e
{
int j=head;
int k=avail;
avail=sll[avail].next;
for (j=head;sll[j].next!=-1 ; j=sll[j].next) ; // 指向表尾结点
sll[j].next=k; // 在链表的表尾位置插入新结点
sll[k].data= e;
sll[k].next= -1;
return SUCCESS;
}
#endif
#ifndef __ASSISTANCE_H__ // 如果没有定义__ASSISTANCE_H__
#define __ASSISTANCE_H__ // 那么定义__ASSISTANCE_H__
// 辅助软件包
// ANSI C++标准库头文件
#include <cstring> // 标准串操作
#include <iostream> // 标准流操作
#include <limits> // 极限
#include <cmath> // 数据函数
#include <fstream> // 文件输入输出
#include <cctype> // 字符处理
#include <ctime> // 日期和时间函数
#include <cstdlib> // 标准库
#include <cstdio> // 标准输入输出
#include <iomanip> // 输入输出流格式设置
#include <cstdarg> // 支持变长函数参数
#include <cassert> // 支持断言
using namespace std; // 标准库包含在命名空间std中
// 自定义类型
enum Status {SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR,
NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED};
// 宏定义
#define DEFAULT_SIZE 1000 // 缺省元素个数
#define DEFAULT_INFINITY 1000000 // 缺省无穷大
// 辅助函数声明
char GetChar(istream &inStream = cin); // 从输入流inStream中跳过空格及制表符获取一字符
template <class ElemType >
void Swap(ElemType &e1, ElemType &e2); // 交换e1, e2之值
template<class ElemType>
void Display(ElemType elem[], int n); // 显示数组elem的各数据元素值
template <class ElemType>
void Write(const ElemType &e); // 显示数据元素
// 辅助类
class Error; // 通用异常类
char GetChar(istream &inStream)
// 操作结果：从输入流inStream中跳过空格及制表符获取一字符
{
char ch; // 临时变量
while ((ch = (inStream).peek()) != EOF // 文件结束符(peek()函数从输入流中接受1
// 字符,流的当前位置不变)
&& ((ch = (inStream).get()) == ' ' // 空格(get()函数从输入流中接受1字符,流
// 的当前位置向后移1个位置)
|| ch == 't')); // 制表符
return ch; // 返回字符
}
// 通用异常类
#define MAX_ERROR_MESSAGE_LEN 100
class Error
{
private:
// 数据成员
char message[MAX_ERROR_MESSAGE_LEN];// 异常信息
public:
// 方法声明
Error(const char *mes = "一般性异常!"); // 构造函数
~Error(void) {}; // 析构函数
void Show() const; // 显示异常信息
};
// 通用异常类的实现部分
Error::Error(const char *mes)
// 操作结果：由mes构构通用异常对象
{
strcpy(message, mes); // 复制异常信息
}
void Error::Show()const
// 操作结果：显示异常信息
{
cout << message << endl; // 显示异常信息
}
template <class ElemType >
void Swap(ElemType &e1, ElemType &e2)
// 操作结果: 交换e1, e2之值
{
ElemType temp; // 临时变量
// 循环赋值实现交换e1, e2
temp = e1; e1 = e2; e2 = temp;
}
template<class ElemType>
void Display(ElemType elem[], int n)
// 操作结果: 显示数组elem的各数据元素值
{
for (int i = 0; i < n; i++)
{ // 显示数组elem
cout << elem[i] << " ";
}
cout << endl;
}
template <class ElemType>
void Write(const ElemType &e)
// 操作结果: 显示数据元素
{
cout << e << " ";
}
#endif
#include "LinkList.h" // 静态链表类
int main(void)
{
LinkList<char> s(10);
char c='*';
char e;
int i;
while (c != '0')
{
cout << endl << "1. 生成静态链表.";
cout << endl << "2. 显示静态链表.";
cout << endl << "3. 取指定位置的元素.";
cout << endl << "4. 设置元素值.";
cout << endl << "5. 删除元素.";
cout << endl << "6. 插入元素.";
cout << endl << "7. 元素定位";
cout << endl << "8. 取静态链表长度";
cout << endl << "0. 退出";
cout << endl << "选择功能(0~8):";
cin >> c;
switch (c)
{
case '1':
s.Clear();
cout << endl << "输入e(e = #时退出):";
cin >> e;
while (e != '#') {
s.InsertElem(e);
if(s.GetLength()>=10)
{cout<<"链表已满"<<endl;break;}
cin >> e;
}
break;
case '2':
s.Traverse(Write<char>);
break;
case '3':
cout << endl << "输入元素位置:";
cin >> i;
if (s.GetElem(i, e) == RANGE_ERROR)
cout << "元素不存在." << endl;
else
cout << "元素:" << e << endl;
break;
case '4':
cout << endl << "输入位置:";
cin >> i;
cout << endl << "输入元素值:";
cin >> e;
if (s.SetElem(i, e) == RANGE_ERROR)
cout << "位置范围错." << endl;
else
cout << "设置成功." << endl;
break;
case '5':
cout << endl << "输入位置:";
cin >> i;
if (s.DeleteElem(i, e) == RANGE_ERROR)
cout << "位置范围错." << endl;
else
cout << "被删除元素值:" << e << endl;
break;
case '6':
cout << endl << "输入位置:";
cin >> i;
cout << endl << "输入元素值:";
cin >> e;
if (s.InsertElem(i, e) == RANGE_ERROR)
cout << "位置范围错." << endl;
else
cout << "成功:" << e << endl;
break;
case '7':
cout << endl << "输入元素的值:";
cin >> e;
if (s.LocateElem(e) == RANGE_ERROR)
cout << "元素不存在." << endl;
else
cout << "元素" << e << "的序号为：" << s.LocateElem(e) << endl;
break;
case '8':
cout << endl << "单链表的长度为:" << s.GetLength() << endl;
break;
}
}
return 0; // 返回值0, 返回操作系统
} 嗯，一切OK。看到这里的孩纸明天要研讨今晚还是早点睡吧，PPT随便做做就行老师不会在意的。
只是自己根据书上讲解，并不一定完全正确，如有漏洞或可优化望请大神指出，谢谢~~
最后
以上就是热情春天为你收集整理的静态链表类模板的实现的全部内容，希望文章能够帮你解决静态链表类模板的实现所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复