list.h

这是清华大学出版社的《数据结构》的电子文档讲义

#include<iostream.h>
#include<assert.h>
#include<stdlib.h>
template<class Type> class list;							//前视的类定义
template<class Type> class listIterator;            		//链表游标类的前视定义

template<class Type> class listNode {						//链表结点类的定义
    friend class list<Type>;								// list类作为友元类定义
	friend class listIterator<Type>;						//友元
    public:
        listNode();											//不带值的结点构造函数
      	listNode(const Type& item);							//带值的结点构造函数
      	listNode<Type>* nextNode( ) { return link;}		//返回下一个结点地址
      	void insertAfter(listNode<Type> * p);				//在当前结点后插人结点
      	listNode<Type>* getNode(Type& item, listNode<Type>* next);
															//建新结点并返回其指针
      	listNode<Type>* removeAfter();					//摘除下一结点,返回其地址
    private:
      	Type data;											//值域
      	listNode<Type>* link;								//链指针域
	};

template<class Type>listNode<Type>::listNode()
	:link(NULL){ }												//构造无值结点,link空

template<class Type>listNode<Type>::listNode(const Type &item)
	:data(item),link(NULL){ }		    						//构造有值结点,link空

template<class Type>void listNode<Type>::insertAfter(listNode<Type>* p){
    p->link = link;  link = p; 		//将p所指示的结点链接成为当前结点(*this)的后继结点。
    }

template<class Type>listNode<Type>* listNode<Type>::
	getNode(Type& item, listNode<Type>* next= NULL){
    			//以item, next(可缺省)为数据和指针参数,建新结点,并返回新结点地址。
    listNode<Type>* newnode = new listNode<Type>(item);
	newnode->link = next;
    return  newnode;
	}

template<class Type>listNode<Type>* listNode<Type>::removeAfter(){
    						//摘下当前结点的下一结点,并为释放其空间而返回其地址。
    listNode<Type>* tempptr = link;						//保存要被删除结点的地址．
    if ( link == NULL)  return  NULL;						//当前结点无后继,返回NULL
    link = tempptr->link;                                 	//将被删结点从链中摘下
    return  tempptr;
	}

template<class Type> class list{							//单链表类定义
    friend class listIterator<Type>;
	friend ostream& operator<<(ostream& out, list<Type>&);
	public:
      	list (const Type& value){							//构造函数
			first = new listNode<Type> (value);
			last = first;}	
		~list();
		int length() const;
      	void makeEmpty();									//清空表
		void insertAtHead(Type value);						//value插人链首
		Type removeAtHead();								//删除链首元素
		void insertAtTail(Type value);						//value插人链尾
		void inverse();										//逆转表的结点

		listNode<Type>* findPtrValue(Type v);
		listNode<Type>* findPtrIndex(int i);								//搜索链表中第i个元素的值
		Type& findValueIndex(int i);
		int insert(Type value, int i);						//将新元素value插人在链表中第i个位置
		Type * remove(int i);								//摘除第i个元素,返回其地址
      	Type * get(int i);									//返回指向链表中第i个元素的指针
	private:
		listNode<Type> * first, * last;					//链表的表头指针,表尾指针
    };

template<class Type>list<Type>::~list(){					//析构函数
    makeEmpty();											//先置为空表
	delete first;	}										//释放表头结点空间

template<class Type>void list<Type>::makeEmpty(){			//将链表置为空表
    listNode<Type> * q;
  	while ( first->link != NULL) {							//链不空时,删去链中所有结点
      	q = first->link; 	first->link = q->link;
      	delete q;  	}                              		//除表头结点外,循链逐个删除
    last = first;											//表尾指针指向表头结点
	}

template<class Type>int list<Type>::length()const{			//计算带表头结点的单链表长度
    listNode<Type>*p = first->link;
	int count = 0;
  	while(p != NULL){p = p->link;  count ++;}				//循链扫描,寻找链尾
    return  count;
	}

template<class Type>void list<Type>::insertAtHead(Type value){	//value插人链首
  	listNode <Type >* newnode;
    newnode = new listNode<Type>(value);					//创建含value的结点
	newnode->link = first->link;							//插入链首，链后指针
  	if(first->link==NULL) last=newnode;						//若原表空，修改链尾指针
	first->link =newnode;									//插入链首，链前指针
	}

template<class Type>Type list<Type>::removeAtHead(){			//删除链首元素
	assert(length()>0);
	listNode <Type >*q;										//定位到链表首部
	q=first->link;
	first->link=q->link;									//摘除链首结点
	Type value = (*q).data;									//保存值
	delete q;												//释放结点
	if(first->link==NULL) last = first;						//若表成空，改尾指针
	return value;											//返回值
	}

template<class Type>void list<Type>::insertAtTail(Type value){	//value插人链表尾部
  	listNode <Type >*newnode;								//定位到链表尾部
    newnode = new listNode<Type>(value);					//创建含value的结点
	newnode->link = last->link;								//接到链尾，链后指针
  	last->link =newnode;									//接到链尾，链前指针
	last = last->link;										//修改链尾指针
	}

template<class Type>listNode<Type> * list<Type>::findPtrValue(Type value){
										//在单链表中搜索含数据value的结点,搜索成功时,
										//函数返回该结点地址;否则返回NULL值。
    listNode<Type>* p = first->link;
  	while(p != NULL && p->data != value) p = p->link;   	//循链找含value结点
    return  p;
	}

template<class Type>listNode<Type> *  list<Type>::findPtrIndex(int i){
										//定位函数。函数返回链表中第i个元素的地址。
										//若i< -1或i超出表中结点个数,则返回NULL。
  	if(i<-1) return NULL;									// i值不合理
  	if ( i == -1) return first;								// i = -1时函数返回表头结点地址
  	listNode<Type> * p = first->link;  int j=0;          	//检测指针p指向表中第一个结点
  	while ( p != NULL &&  j<i){p = p->link;  j = j++;}		//寻找第i个结点的地址
  	return p;							//函数返回第i个结点地址,若返回NULL,表示i值大于实际结点数。
	}

template<class Type>Type& list<Type>::findValueIndex(int i){
  	listNode<Type> * p = first->link;  int j=0;          	//检测指针p指向表中第一个结点
  	while ( p != NULL &&  j<i){p = p->link;  j = j++;}		//寻找第i个结点的地址
  	return p->data;											//函数返回第i个结点值。
	}

template<class Type>int list<Type>::insert(Type value,int i){
														//将新元素value插人链表中第i个位置。
  	listNode<Type>* p = findPtrIndex(i-1);						//定位第i -1个元素(i :0)
  	if (p == NULL)return 0;                  			//参数i的值不合理,函数返回。
    listNode<Type>* newnode = new listNode<Type>(value);
	newnode->link = p->link;
	//listNode<Type>* newnode = listNode<Type>::getNode(value, p->link);	//创建含value的结点
  	if(p->link == NULL)last = newnode;
  	p->link = newnode;									//插入成功,函数返回1
    return 1;
	}

template<class Type>Type * list<Type>::remove(int i){
					//将链表中的第i个元素删去,通过函数返//回该元素。若i不合理,则返回NULL。
  	listNode<Type> * p = findPtrIndex(i-1), *q;             // p定位于第i -1个元素
  	if ( p = NULL || p->link == NULL ) return  NULL;    // i的值不合理或空表,返回NULL
	q = p->link;  p->link = q->link;                   	// q指向被删结点,重新拉链
    Type*  valuePtr = new Type(q->data);					//保存待删结点中的数据值的副本
    if ( q == last) last = p;							//删表尾结点时,先修改表尾指针
	delete q;											//删结点i
	return valuePtr;									//返回被删元素值副本的地址
	}

template<class Type>Type * list<Type>::get(int i){   	//返回链表中第i个元素数据的地址
	listNode<Type> * p = find(i);						//定位于第i个元素
    if ( p == NULL || p == first )  return NULL;		//空表或参数i值不合理返回NULL
    else return & p->data;								//返回第i个元素数据的地址
	}

template<class Type>void list<Type>::inverse(){
	listNode<Type> *q=first->link;
	if(q==NULL) return;
	last=q;									//先改尾指针
	listNode<Type> *p=q->link, *pr=NULL;
	while(p!=NULL){
		q->link=pr;
		pr=q;	q=p;	p=p->link;
		}
	q->link=pr;	first->link=q;
	}

enum Boolean{False,True};

template< class Type> class listIterator{				//链表游标类的类声明
	public:
    	listIterator(const list<Type> & li):list (li),current(li.first){ }	//构造遍历器对象
    	Boolean NotNull();								//判基类对象非空
   		Boolean NextNotNull();							//判尚未遍历完
  		Type * First();									//初始化,返回第一个元素指针
		Type& currentValue();							//返回当前元素的值
  		Type * Next();									//返回下一个元素指针
	private:
    	const  list< Type> & list;						//引用已存在的链表作为基类
    	listNode< Type> * current;						//指向链表中当前结点的指针
	};

template<class Type>Boolean listIterator<Type>::NotNull(){//检查链表中当前元素是否非空。
  	if(current != NULL)return True;						//链表当前结点指针非空
	else  return  False;
	}

template<class Type>Boolean listIterator<Type>::NextNotNull(){
								//检查链表中下一元素是否非空。
    if(current != NULL && current->link != NULL)return  True;
    else  return  False;
	}

template<class Type>Type * listIterator< Type>::First(){
						//返回指向链表中第一个结点数据的指针(假定链表中没有表头结点)。
  	if(list.first->link != NULL){ current = list.first->link;  return &current->data;}
  	else{current = NULL;  return  NULL;}
	}

template<class Type>Type* listIterator< Type>::Next(){	//返回指向下一个结点数据的指针。
    if(current != NULL && current->link != NULL){
            current = current-> link;  return &current->data;}
    else{current= NULL;	return NULL;}
    }

template<class Type>Type& listIterator< Type>::currentValue(){   //返回当前结点数据的值。
	return current->data;
	}

template<class Type>ostream& operator<<(ostream& out, list<Type>&l1){
	listIterator< int> lit1(l1);			//定义lit为链表对象l1的游标对象
	int value = * lit1.First();				//取得第一个元素的值
	cout<<value<<", ";
	while ( lit1.NextNotNull() ) {			//只要还有下一个结点,
		lit1.Next();						//到下一结点
		cout<<lit1.currentValue()<<", ";	//输出当前结点值大
		}
	cout<<endl;								//换行
	return out;
	}

int sum(const list<int> &li){						//对链表li求和
	listIterator< int> lit ( li );                	//定义lit为链表对象li的游标对象
	if (!lit.NotNull()) return 0;         			//若li为空链表,返回0
	int retvalue = * lit.First();					//取得第一个元素的值
	while ( lit.NextNotNull() ) {					//只要还有下一个结点,
		lit.currentValue() *= 2;						//当前结点数据乘2
		cout<<lit.currentValue()<<", ";				//输出
		retvalue += * lit.Next();					//到下一结点继续累加
		}
	lit.currentValue() *= 2;							//处理最后结点
	cout<<lit.currentValue()<<endl;					//输出最后结点
    return retvalue;								//返回累加值
	}