staticlinkedlist.h

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

#ifndef SLINKEDLIST
#define SLINKEDLIST
#include<iostream>
using namespace std;
const int DefaultSize = 10;			//在staticList.h文件中 
const int maxData =32767;

template <class T>
struct Element {					//静态链表元素类定义
	T key;							//排序码,其它信息略
	int link;						//结点的链接指针
	Element () : link(0) { } 		//构造函数
	Element (T x, int next = 0) : key(x), link(next) { }
	//构造函数	
};

template <class T>

class staticLinkedList {			//静态链表的类定义
public:
	staticLinkedList (int sz = DefaultSize) {
		maxSize = sz;  n = 0; 
		Vector = new Element<T>[sz];
	}
	Element<T>& operator [](int i) {return Vector[i];}
	void build();					//自定义函数，用于输入一个链表
	void show();					//自定义函数，用于输出一个链表
	int Length(){return n;}			//自定义函数，返回表长
private:
	Element<T> *Vector;				//存储元素的向量
	int maxSize;	     			//最大元素个数
	int n;							//当前元素个数
};

template <class T>
void staticLinkedList<T>::build(){
	cout<<"输入元素个数："<<endl;
	int c;
	cin>>c;
	for(int i=1;i<=c;i++)
	{
		cout<<"输入元素值：";
		cin>>Vector[i].key;
		Vector[i].link=i+1;
	}
	Vector[c].link=0;
	Vector[0].link=1;
	n=c;
}
template <class T>
void staticLinkedList<T>::show(){
	int p=Vector[0].link;
	for(int i=0;i<n;i++)
	{
		cout<<Vector[p].key<<"  ";
		p=Vector[p].link;
	}
}

template <class T>
void insertSort (staticLinkedList<T>& L) {
	//对L.Vector[1],...,L.Vector[n]按其排序码key排序,
	//L.Vector[0] 做为排序后各个元素所构成的有序循
	//环链表的附加头结点使用
	L[0].key = maxData;   
	L[0].link = 1;   L[1].link = 0;
	//形成只有一个元素的循环链表
	int i, pre, p;
	for (i = 2; i <= L.Length(); i++) {	
		//每趟向有序链表中插入一个结点
		p = L[0].link;			//p是链表检测指针
		pre = 0;			//pre指向p的前驱
		while (L[p].key <= L[i].key)    //循链找插入位置
		{ pre = p;  p = L[p].link; }
		L[i].link = p;  L[pre].link = i;   //结点i链入
	}
};

template <class T>
void selectSort (staticLinkedList<T>& L) {
	//L.Vector[0]作为表头结点使用,L.Vector[1].data
	//到L.Vector[n].data存放数据
	int f = L[0].link, p, q, r, s;  
	L[0].link = 0;
	while (f != 0) {     		//原始链表未扫描完
		p = s = f;  q = r = 0;		//s指示当前最大元素
		while (p != 0) {
			if (L[p].key > L[s].key ) { s = p;  r = q; }
			//记忆当前找到的排序码最大结点
			q = p;  p = L[p].link;
		}
		if (s == f ) f = L[f].link; 	    //结点s从链中摘下
		else L[r].link = L[s].link;
		L[s].link = L[0].link;
		L[0].link = s;
		//结点s插入到结果链表的前端
	}
};     

template <class T>
int ListMerge (staticLinkedList<T>& L, int s1, int s2) {
	//两个有序链表中第一个结点的下标分别为s1和s2
	//将它们归并, 得到一个有序链表, 并返回其第一个
	//结点的下标。L[0]是工作单元。
	int k = 0,  i = s1,  j = s2; 
	while (i != 0 && j != 0)		//做两两比较
		if (L[i].key <= L[j].key)		//i所指排序码小
		{ L[k].link = i;  k = i;  i = L[i].link; }
		else
		{ L[k].link = j;  k = j;  j = L[j].link; }
		if (i == 0) L[k].link = j;	//i链检测完, j链接上
		else L[k].link = i;		//j链检测完, i链接上
		return L[0].link;		//返回结果链头指针
};

template <class T>
int rMergeSort (staticLinkedList<T>& L,
				const int left, const int right) {
					//对链表L.Vector[left..right]进行排序。各个结点中
					//的链域link应初始化为0,rMergeSort返回排序后
					//链表第一个结点的下标,L.Vector[0]是工作单元
					if (left >= right) return left;
					int mid = (left+right)/2;
					L[mid].link=0;
					return ListMerge (L, rMergeSort (L,left, mid),
						rMergeSort (L, mid+1,right));
}; 


#endif