linlist.h

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

#include <iostream.h>
#include <stdlib.h>

template <class T> class LinList;	

template <class T>
class ListNode
{	
   friend class LinList<T>;
public:             //***************************************
   ListNode<T> *next;        //结点链接指针
   T data;     //结点数据
public: 
   ListNode(ListNode<T> *ptrNext=NULL);
   ListNode (const T& item, ListNode<T> *ptrNext=NULL);	   
};

//链表结点部分操作的实现
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
{
 protected:    //***********************************************
    ListNode<T> *head;		
	int size;
	ListNode<T> *currPtr;
 public:    
	LinList(void );		//构造函数            
    ~LinList(void);	    //析构函数

   int ListSize(void) const;
   int ListEmpty(void) const;
   ListNode<T> *Index(int pos); 
   void Insert(const T&item,int pos);
   T Delete(int pos);
   T GetData(int pos);
   void ClearList(void);
 
   ListNode<T> *Reset(int pos=0);
   ListNode<T> *Next (void);
   int EndOfList(void) const;
   T GetData(void);   //取当前结点的值
};

//链表的公共操作
template <class T> 
LinList<T>::LinList( )
{
	head=new ListNode<T>();
	size=0;
}

template <class T> 
LinList<T>::~LinList(void)   //析构函数
{
     ClearList();  
	 delete head;
}

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

template <class T>
int LinList<T>::ListEmpty(void) const
{
	return size==0;
}

template <class T>
ListNode<T>* LinList<T>::Index(int pos) 
{
	if(pos<-1||pos>(size-1))
	{
		cerr<<"参数pos越界出错!"<<endl;
		exit(1);
	}
	if(pos==-1) return head;
	ListNode<T> *p=head->next;  
    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)
{
//将含item的新元素插入到链表pos位置
  ListNode<T> *p=Index(pos-1);
  ListNode<T> *newNode=new ListNode<T>(item,p->next);
  p->next=newNode;
  size++;
}

template <class T> 
T LinList<T>::Delete(int pos)
{
 if(size==0)
 {
	 cerr<<"链表已为空表！"<<endl;
	 exit(1);
 }
 ListNode<T> *q,*p=Index(pos-1);
 q=p->next;
 p->next=p->next->next;
 T data=q->data;
 delete q;
 size--;
 return data;
}

template <class T> 
T LinList<T>::GetData(int pos)
{
 //提取第i个结点的数据
  ListNode<T> *p=Index(pos);
 // p 指向链表第 i 个结点
  return p->data;
}

template <class T> 
void LinList<T>::ClearList(void)
{
//删去链表中除表头结点外的所有其他结点
    ListNode<T> *p,*p1;
	p=head->next;
    while(p!=NULL) 
	{
         p1=p;
		 p=p->next;
         delete p1;        //释放它 
    }
    size=0;
    head->next=NULL;
}					

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

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