staticlist.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//静态链表类
#ifndef STATICLIST
#define STATICLIST
#include<iostream>
using namespace std;
const int maxSize = 200;//静态链表大小
template<class T>
struct SLinkNode{
	T data;                     //结点数据
	int link;                   //结点链接指针
};

template<class T>
class StaticList{
	SLinkNode<T> elem[maxSize];
	int avil;                    //当前可分配空间首地址
public:
	void InitList();
	int Length();				//计算静态链表的长度
	bool Insert(int i, T x);    //第i个结点后插入新结点
	bool Remove(int i);			//释放第i个结点
	bool Search(T x);			//在静态链表中查找具有给定值的结点
	int Locate(int i);			//查找第i个结点
	bool Append(T x);			//表尾追加一个新结点
	bool IsEmpty();				//判链表空否
	void build();				//自定义函数，输入静态链表
	void show();				//自定义函数，输出静态链表
};


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>
bool StaticList<T>::IsEmpty(){
	if(elem[0].link == -1) return true;
	else return false;
};

template<class T>
bool StaticList<T>::Search(T x){
	//查找具有给定值的结点
	int p = elem[0].link;              //链表中第1个结点
	while(p != -1)                      //逐个结点检测查找具有给定值的结点
		if(elem[p].data == x) break;
		else p = elem[p].link;
	if(p!=-1)
		return true;
	else
		return false;
};

template<class T>
int StaticList<T>::Locate(int i){
	if(i < 0) return -1;                  //参数不合理
	if(i == 0) return 0;
	int j = 1, p = elem[0].link;
	while(p != -1 && j < i)
	{p = elem[p].link; j ++;}          //循链查找第i个结点
	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){
	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){
	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;                     //释放
	avil = q;
	return true;
};
template<class T>
void StaticList<T>::build(){
	cout<<"请输入链表结点个数：";
	int n;
	cin>>n;
	T temp;
	for(int i=1;i<=n;i++)
	{
		cout<<"请输入结点数据：";
		cin>>temp;
		elem[i].data=temp;
	}
	avil=n+1;
	elem[0].link=1;
	elem[n].link=-1;
}

template<class T> 
void StaticList<T>::show(){
	cout<<"链表结点数据："<<endl;
	int p = elem[0].link;
	while(p != -1) {
		cout<<elem[p].data<<"  ";
		p = elem[p].link;
	}
}
#endif