linlist.h

数据结构c++-书的一些源代码

#include <iostream.h>
#include <stdlib.h>
template <class T> class LinList;			//前视定义,否则友元无法定义
template <class T>							//模板类型为T
class ListNode
{
		friend class LinList<T>;					//定义类LinList<T>为友元
		private:
			ListNode<T> *next;	    				//指向下一结点的指针
		public:
			T data;								//定义为公有成员方便使用
			//构造函数,主要用于构造头结点
			ListNode(ListNode<T> *ptrNext = NULL);	
			//构造函数,主要用于构造非头结点的结点	
			ListNode(const T& item, ListNode<T> *ptrNext = NULL);
			//返回建立的新结点指针
//			ListNode<T> *GetNode(const T& item, ListNode<T> *ptrNext = NULL);
};

//类ListNode的实现
template<class T>
ListNode<T>::ListNode(ListNode<T> *ptrNext):next(ptrNext)
{}

template<class T>
ListNode<T>::ListNode(const T &item, ListNode<T> *ptrNext)
{
	data = item;
	next = ptrNext;
}

template <class T>
class LinList
{
		private:
			ListNode<T> *head;				//指向表头的指针
			int size;						//单链表的结点个数
			ListNode<T> *currPtr;
    		public:
	    		LinList(void);					//构造函数
			~LinList(void);					//析构函数
			int ListSize(void) const;		//返回链表的结点个数
			int ListEmpty(void) const;		//链表空否,空返回1;否则返回0
			ListNode<T> *Index(int pos);		//返回指向第pos个结点的指针
			//在第pos个结点后插入一个元素值为item的新结点
			void Insert(const T& item, int pos);
			T Delete(int pos);				//删除第pos个结点
			T GetData(int pos);				//返回第pos个结点的data值
			void ClearList(void);			//清空表为初始化状态

		//遍历表的函数
		ListNode<T> *Reset(int pos=0);
		ListNode<T> *Next(void);
		int EndOfList(void) const;
};
 
//链表类的实现  
template <class T> 
LinList<T>::LinList()					//构造函数
{
		head = new ListNode<T>();			//头指针指向头结点
		size = 0;							//定义size的初值为0
}

template <class T>
LinList<T>::~LinList(void)				//析构函数
{ 
		ClearList();							//释放链表的所有非头结点的结点
}

template <class T>
int LinList<T>::ListSize(void) const		//返回链表的结点个数
{
		return size;
}

template <class T>
int LinList<T>::ListEmpty(void) const	//链表空否,空返回1;否则返回0
{
		if(size <= 0) return 1;
		else return 0;
}
	
template <class	T>	
ListNode<T> *LinList<T>::Index(int pos)		//返回指向第pos个结点的指针
{
		if(pos < -1 || pos > size)
		{
			cerr << "参数pos越界出错！" << endl;
			exit(1);
		}

		if(pos == -1) return head;				//pos为-1时返回头指针head

		ListNode<T> *p = head->next;				//p指向第一个结点
		int i = 0;								//从0开始计数
		while(p != NULL && i < pos)				//寻找第pos个结点
		{
			p = p->next;
			i++;
		}
		return p;								//返回第pos个结点指针
}

template <class T>
void LinList<T>::Insert(const T& item, int pos)
//在第pos个结点后插入一个元素值为item的新结点
{
		ListNode<T> *p = Index(pos - 1);			//p为指向第pos-1个结点指针
		//构造新结点newNode，newNode的data域值为item，next域值为 p->next
		ListNode<T> *newNode = new ListNode<T>(item, p->next);
		p->next = newNode;						//新结点插入第pos个结点前
		size++;									//结点个数加1
}

template <class T>
T LinList<T>::Delete(int pos)				//删除第pos个结点
{
		if(size == 0) 
		{
			cerr << "链表已空无元素可删！" << endl;
			exit(1);
		}
		
ListNode<T> *q, *p = Index(pos - 1);		//p为指向第pos-1个结点指针

		q = p->next;								//q指向第pos个结点
		p->next = p->next->next;					//第pos个结点脱链
		T data = q->data;
		delete q;								//释放第pos个结点空间
		size--;									//结点个数减1
		return data;								//返回第pos个结点的data域值
}

template <class T>
T LinList<T>::GetData(int pos)				//返回第pos个结点的data值
{
		ListNode<T> *p = Index(pos);				//p指向第pos个结点
		return p->data;
}

template <class	T>	
void LinList<T>::ClearList(void)				//清空表为初始化状态
{
		ListNode<T> *p, *p1;

		p = head->next;					//p指向第一个结点
		while(p != NULL)					//循环释放结点空间直至初始化状态
		{
        		p1 = p;
			p = p->next;
			delete p1;
		}
		size = 0;						//结点个数置为初始化值0
}

template <class T>
ListNode<T> *LinList<T>::Reset(int pos)
{
	 if(head == NULL) return NULL;
	 if(pos < 0 || pos > size)
	 {
		 cerr << "参数出错!" << endl;
		 return NULL;
	 }
	 if(pos == 0) currPtr = head->next;
	 else
	 {
		 currPtr = head->next;
		 ListNode<T> prevPtr = head;
		 for(int i = 0; i < pos; i++)
		 {
			 prevPtr = currPtr;
			 currPtr = currPtr->next;
		 }
	 }
	return currPtr;
}

template <class T>
ListNode<T> *LinList<T>::Next(void)
{
	if(currPtr != NULL) currPtr = currPtr->next;
	return currPtr;
}
        
template <class T>
int LinList<T>::EndOfList(void) const
{
	if(currPtr == NULL) return 1;
	else return 0;
}