linkedlist.h

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

//单链表类定义及实现
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
template <class T, class E>   //定义在“LinkedList.h”
struct LinkNode {	 	       //链表结点类的定义
	E data;			       //数据域
	LinkNode<T, E> *link;     //链指针域
	LinkNode() { link = NULL; }     //构造函数
	LinkNode(E item, LinkNode<T, E> *ptr = NULL)
	{ data = item;  link = ptr; }     //构造函数
	bool operator== (E x) { return data == x; }
	//重载函数，判相等
	bool operator != (E x) { return data != x; }
};
template <class T, class E>
class List{
protected:
	LinkNode<T, E> *first;	 //表头指针
public:
	List() { first = new LinkNode<T, E>; }  //构造函数
	List(E x) { first = new LinkNode<T, E>(x); }
	List( List<T, E>& L);		//复制构造函数
	~List(){ }				//析构函数
	void makeEmpty();		//将链表置为空表
	int Length() const;		//计算链表的长度
	LinkNode<T, E> *Search(E x);	//搜索含x元素
	LinkNode<T, E> *Locate(int i);	//定位第i个元素
	bool Insert (int i, E x);		    //在第i元素后插入
	bool Remove(int i, E& x);	    //删除第i个元素
	bool IsEmpty() const 		    //判表空否
	{ return first->link == NULL ? true : false; }
	E getData(int i);			//取出第i元素值
	void setData(int i, E x);		//更新第i元素值
	LinkNode<T, E> *getFirst() const { return first; } 
	void setFirst(LinkNode<T, E> *f ) { first = f; }
	void show();  //输出
};
template <class T, class E> 							
void List<T, E>::makeEmpty() {
	LinkNode<T, E> *q;
	while (first->link != NULL) {
		q = first->link;              //保存被删结点
		first->link = q->link;    //从链上摘下该结点
		delete q;		        //删除
	}
};
template <class T, class E>
int List<T, E> :: Length ( ) const {
	ListNode<T, E> *p = first->link;
	//检测指针 p 指示第一号结点
	int count = 0; 
	while ( p != NULL ) {      //逐个结点检测
		p = p->link;  count++;
	}			
	return count;
}
template <class T, class E>
E List<T,E>::getData(int i)
{
	if (i <= 0) return NULL; //i值太小
	LinkNode<T,E> *current = Locate(i);
	if (current == NULL) return NULL; //i值太大
	else return current->data;
};
template <class T, class E>
LinkNode<T, E> *List<T, E>::Search(E x) {
	//在表中搜索含数据x的结点, 搜索成功时函数返
	//该结点地址; 否则返回NULL。
	LinkNode<T, E> *current = first->link;
	while ( current != NULL && current->data != x ) 		current = current->link;  	
	//沿着链找含x结点
	return current;
};
template <class T, class E>
LinkNode<T, E> *List<T, E>::Locate ( int i ) {
	//函数返回表中第 i 个元素的地址。若i < 0或 i 超
	//出表中结点个数，则返回NULL。
	if (i < 0) return NULL;		//i不合理
	LinkNode<T, E> *current = first;  int k = 0;
	while ( current != NULL && k < i )
	{ current = current->link;	k++; }
	return current;	    //返回第 i 号结点地址或NULL
};
template <class T, class E>
bool List<T, E>::Insert (int i, E x) {
	//将新元素 x 插入在链表中第 i 个结点之后。
	LinkNode<T, E> *current = Locate(i);
	if (current == NULL) return false;	   //无插入位置
	LinkNode<T, E> *newNode = 
		new  LinkNode<T, E>(x);	   //创建新结点
	newNode->link = current->link;        //链入
	current->link = newNode;			
	return true; 				  //插入成功
};
template <class T,class E>
void List<T,E>::setData(int i, E x) {
	//给链表中第i个元素赋值x。
	if (i <= 0) return; //i值太小
	LinkNode<T> *current = Locate(i);
	if (current == NULL) return; //i值太大
	else current->data = x;
};
template <class T, class E>
bool List<T, E>::Remove (int i, E& x ) {
	//删除链表第i个元素, 通过引用参数x返回元素值
	LinkNode<T, E> *current = Locate(i-1);
	if ( current == NULL || current->link == NULL)   
		return false; 	//删除不成功 	
	LinkNode<T, E> *del = current->link; 
	current->link = del->link;
	x = del->data;	delete del;	
	return true;
};

template <class T, class E>
void List<T, E>::show()
{
	LinkNode<T,E> *current = first->link;
	while (current != NULL) { 
		cout << current->data <<" ";
	current = current->link;
	}
	cout<<endl;
};

template <class T, class E>//建立单链表
void build(E endTag, List<T, E>& L) {
	LinkNode<T, E> *newNode, *last;  E val;
	last = new LinkNode<T, E>;	  //建立链表的头结点
	L.setFirst(last);	  	            //为链表L的first赋值
	cout<<"输入结点数据: ";
	cin >> val;
	while ( val != endTag ) {   	 //last指向当前的表尾
		newNode = new LinkNode<T, E>(val);
		last->link = newNode;   last = newNode;
		cout<<"输入下一个结点数据: ";
		cin >> val;			//插入到表末端
	}
	last->link = NULL;              	//表收尾     
}; 

#endif;