linlist.h

数据结构的一些教程....比较适于初学者

/*这是单链类(模板)的定义与实现(教材P.67-72)的改写：把单循环链表类CirList
作为链表类LinList的派生类，这样需要把它的析构函数改写，另外还把有关遍历
的函数声明为虚成员函数 */
#ifndef LINLIST_H
#define LINLIST_H
#include "iostream.h"
#include "stdlib.h"


template<class T> 
struct  ListNode  //定义链表结点结构(模板)
 { 		
		ListNode *next;     //指向下一个结点的指针
        T data;        //原教材此句放在public段
		ListNode(ListNode<T> *ptrNext=NULL) //用于构造头结点
		{	next=ptrNext;   }
        ListNode(const T& item, ListNode<T> *ptrNext=NULL) //用于构造非头结点
		{   data=item; next=ptrNext; }
};

    //单链表类的定义
template<class T> class LinList {
protected:
	ListNode<T> *head;      //表头指针
	int size;               //链表长度
	ListNode<T> *currPtr;   //当前结点指针
 public:
	 LinList(void);         //构造函数
	 virtual ~LinList(void);//析构函数

	 //以下是表操作成员函数
	 int ListSize(void) const;  //返回表大小（元素个数）
	 ListNode<T>* CurrPtr()    //返回当前结点指针
	 { return currPtr; }
	 bool ListEmpty(void) const;  //判别表是否为空
	 virtual ListNode<T>  *Index(int pos); //返回指向第pos个结点的指针
	 virtual void Insert(const T& item,int pos); //在第pos结点前插入一结点
	 virtual void Insert(const T& item);     //在当前结点之后插入一结点
	 virtual T Delete(int pos); //删除第pos结点,并将它的data值返回
	 T GetData(int pos); //获取第pos结点的data值
	 T GetData()const   //获取当前结点的data值,原教材没有此成员
	 {  return currPtr->data; }
	 void  ClearList(void);  // 清空表为初始状态

	 //遍历链表的成员函数
	 ListNode<T> *Reset(int pos=0); //使currPtr指向第pos结点并返回currPtr
	 virtual ListNode<T> *Next(void);  //使currPtr指向下一个结点
 //查找其数据域为data的结点,找到返回true,并使currPtr指向它,否则返回false
	virtual bool  Find(const T data);   //在表中查找元素。原教材没有此成员
	virtual bool EndOfList(void) const; //判别当前指针是否到了表尾
};

  //单链表类LinList的实现
template<class T>
LinList<T>::LinList()
{
	head=new ListNode<T>();  //建一个头结点
	size=0;        //空链表
	currPtr=head;           //当前结点初始化
}

template<class T>
LinList<T>::~LinList()      //这个方法的代码是重写的
{
    ListNode<T>  *p=head->next, *q;
	while(size!=0)
	{
		q=p; p=p->next;
		delete q;
		size--;
	}
	delete head;    //释放头结点
	head=NULL;
	currPtr=0;
}

template<class T>
int LinList<T>::ListSize() const
{ return size;  }

template<class T>
bool LinList<T>::ListEmpty() const
{
	return size==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;
	ListNode<T> *p=head->next;  //p指向第一个结点
	int i=0;
	while(p!=NULL && i<pos)
	{	p=p->next; i++;  }
	return p;
}

template<class T>
void LinList<T>::Insert(const T& item, int pos)
{//在第pos个元素之前插入一个结点
	ListNode<T> *p=Index(pos-1); //使P指向第pos个元素之前一个结点
	ListNode<T> *newNode=new ListNode<T>(item,p->next); //调用第二个构造函数
	p->next=newNode;
	size++;
}

template<class T>
void LinList<T>::Insert(const T& item)     //在当前结点之后插入一结点
{
	ListNode<T> *p;
	p=new ListNode<T>(item,NULL);
	if(p==0)
	{
		cerr<<"内存分配出错! "<<endl;
		exit(0);
	}
	p->next=currPtr->next;
	currPtr->next=p;
	size++;
}


template<class T>
T LinList<T>::Delete(int pos)//删除第pos个结点
{
	if(size==0)
	{
		cerr<<"链表已空,无元素可删除!"<<endl;
		exit(1);
	}

	ListNode<T> *q, *p=Index(pos-1);
	q=p->next;     //q指向p所指的后一个结点
	p->next=q->next;
	T data=q->data;
	delete q;
	size--;
	return data;
}

template<class T>
T LinList<T>::GetData(int pos)  //读第pos个元素的数据
{
	ListNode<T> *p=Index(pos);
	return p->data;
}

template<class T>
void LinList<T>::ClearList()    //清空表
{
	ListNode<T> *p,*p1;
	p=head->next;
	while(size!=0)
	{
		p1=p; p=p->next;
		delete p1;
		size--;
	}
}

template<class T>
ListNode<T>* LinList<T>::Reset(int pos)
{//使currPtr指向第pos个结点，pos为-1时，使返回头结点指针
	if(pos<-1 || pos>size)
	{
		cerr<<"参数出错!"<<endl;
		exit(1);
	}
	if(pos==-1)	currPtr=head;
	
	if(pos==0) currPtr=head->next;
	else currPtr=Index(pos);
	
	return currPtr;
}

template<class T>
ListNode<T>* LinList<T>::Next()     //使currPtr指向下一个结点
{
	if(currPtr!=NULL) currPtr=currPtr->next;
	return currPtr;
}

template<class T>
bool LinList<T>::EndOfList() const    //判别当前指针是否到了表尾
{
	return currPtr==0;
}

template<class T>
bool LinList<T>::Find(const T data)   //在表中查找元素。
{
	ListNode<T> *p=head->next;
	while(p!=NULL)
    	if(p->data==data)
		{
			currPtr=p;
			return true;
		}
		else p=p->next;
	return false;
}
#endif //LINLIST_H