模板链表_02b.h

模板链表的类定义

//EXAMPLE9_02B.H
#ifndef EXAMPLE9_02B_H
#define EXAMPLE9_02B_H
#include <iostream>
#include "EXAMPLE9_02.H"
//结点类带参数构造函数的实现
using namespace std;
template<class T>
ListNode<T>::ListNode(const T& nItem, ListNode<T> *ptrNext):
Data(nItem),ptrNext(ptrNext)
{}

//返回指向后续结点的指针
template<class T>
ListNode<T> *ListNode<T>::NextListNode() const
{
      return ptrNext;
}

template<class T>
void ListNode<T>::InsertAfter(ListNode<T> *ptr)
{
      ptr->ptrNext=ptrNext;     //将ptr的ptrNext指针指向本结点的后续结点
      ptrNext=ptr;//本结点的ptrNext指针指向ptr
}

template<class T>
ListNode<T> *ListNode<T>::DeleteAfter()
{
      ListNode<T> *ptrTemp=ptrNext;
      if(ptrNext==NULL)     //处理本结点为尾结点时的情况
            return NULL;
      ptrNext=ptrTemp->ptrNext;    //一般情况
      return ptrTemp;
}

//链表类构造函数,4个私有指针成员设置为空,链表初始长度设置为0,初始当前结点
//初始位置为-1
template<class T>
LinkedList<T>::LinkedList(void):ptrFront(NULL),ptrTail(NULL),
                  ptrPrev(NULL),ptrCurr(NULL),nListLength(0),nPosition(-1)
{ }

//重载"="号运算符
template<class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& list)
{
	if(this!=&list)
      {
            DeleteAll();
            CopyList(list);
      }

      return *this;
}

//拷贝构造函数
template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& list)
{
      CopyList(list);
}

//重新设置当前指针的位置
template<class T>
void LinkedList<T>::Reset(int nPos)
{
      int nStartPos;
	  if(!ptrFront)        //如果当前指针为空,链表为空直接返回
      {
            return;
      }
      if(nPos>=nListLength||nPos<0)      //位置越界检查
      {
            cerr<<"Invalid Position!"<<endl;
            return;
      }
      if(nPos==0)        //置当前指针为头结点
      {
            ptrPrev=NULL;
            ptrCurr=ptrFront;
            nPosition=0;
      }
      else       //一般情况
      {
            ptrCurr=ptrFront->NextListNode();
            ptrPrev=ptrFront;
            nStartPos=1;
            for(nPosition=nStartPos;nPosition!=nPos;nPosition++)
                                             //寻找该位置并使当前指针指向该位置
											 {
                  ptrPrev=ptrCurr;
                  ptrCurr=ptrCurr->NextListNode();
            }
      }
}

//当前指针指向当前结点的后续结点
template<class T>
void LinkedList<T>::Next()
{
      if(ptrCurr)
      {
            ptrPrev=ptrCurr;
            ptrCurr=ptrCurr->NextListNode();
            nPosition++;
      }
}

//将数据为nItem的结点插入到链表头
template<class T>
void LinkedList<T>::InsertFront(const T& nItem)
{
      ListNode<T> *newListNode=GetListNode(nItem);  //获得一个封装有该数据
						        //的结点
      newListNode->SetNext(ptrFront);
      ptrFront=newListNode;
      nListLength++;
}

//将数据为nItem的结点插入到链表尾
template<class T>
void LinkedList<T>::InsertTail(const T& nItem)
{
      ListNode<T> *newListNode;

      if(ptrCurr==NULL) InsertFront(nItem);   //若链表为空,使之成为头结点
					       //(也是尾结点)
      else    //一般情况
      {
            while(ptrCurr->NextListNode())     //寻找尾结点
                  ptrCurr=ptrCurr->NextListNode();
			newListNode=GetListNode(nItem);
            ptrCurr->InsertAfter(newListNode);
      }
}

//将数据为nItem的结点插入到链表的当前位置之前
template<class T>
void LinkedList<T>::InsertAt(const T& nItem)
{
      ListNode<T> *newListNode;

      if(!ptrPrev)    //插入到头结点
      {
            newListNode=GetListNode(nItem,ptrFront);
            newListNode->SetNext(ptrFront);
            ptrFront=newListNode;
                  
            nListLength++;
      }
      else          //一般情况
      {	
		  newListNode=GetListNode(nItem);
          ptrPrev->InsertAfter(newListNode);

      }
      if(ptrPrev==ptrTail)
      {
            ptrTail=newListNode;
            nPosition=nListLength;
      }
      ptrCurr=newListNode;
      
}

//将数据为nItem的结点插入到链表当前结点之后
template<class T>
void LinkedList<T>::InsertAfter(const T& nItem)
{
      ListNode<T> *newListNode;

      if(!ptrCurr)        //处理空链表的情况，如果当前链表为空
      {
		  newListNode=GetListNode(nItem);
            ptrCurr=newListNode;
            ptrFront=ptrCurr;
      }
      else     //一般情况
      {    
            newListNode=GetListNode(nItem);
            ptrCurr->InsertAfter(newListNode);
      }
      if(ptrPrev==ptrTail)
      {
            ptrTail=newListNode;
            nPosition=nListLength;
      }
      ptrCurr=newListNode;
      nListLength++;
}

//删除链表中的当前结点
template<class T>
void LinkedList<T>::DeleteCurr()
{
      ListNode<T> *ptr;
      if(!ptrCurr)    //处理空链表的情况
      {
            cerr<<"The List is empty!"<<endl;
            exit(1);
      }
      if(!ptrPrev)    //删除头结点的情况
      {
            ptr=ptrFront;
            ptrFront=ptrFront->NextListNode();
      }
      else    //一般情况
	  {ptr=ptrPrev->DeleteAfter();}
      if(ptr==ptrTail)
      {
            ptrTail=ptrPrev;
            nPosition--;
      }
      ptrCurr=ptr->NextListNode();
      FreeListNode(ptr);
	  nListLength--;
}

//删除链表中所有结点并释放资源
template<class T>
void LinkedList<T>::DeleteAll()
{
      ListNode<T> *ptrCurrPos,
                    *ptrNextPos;

      ptrCurrPos=ptrFront;
      while(ptrCurrPos)        //循环处理删除链表中的各个结点
      {
            ptrNextPos=ptrCurrPos->NextListNode();
            FreeListNode(ptrCurrPos);
            ptrCurrPos=ptrNextPos;
      }
      ptrFront=NULL;
      ptrTail=NULL;
      ptrPrev=NULL;
      ptrCurr=NULL;
	  nListLength=0;
      nPosition=-1;
}

//删除链表的头结点
template<class T>
int LinkedList<T>::DeleteHead()
{
      ListNode<T> *ptr=ptrFront;
      if(ptrFront)
      {
            ptrFront=ptrFront->NextListNode();
            delete ptr;
      nListLength--;
      return 1;
      }
      else           //处理链表为空的情况
      {
            cout<<"The List is empty!"<<endl;
            return 0;
      }
}
//获得链表中当前结点的数据
template<class T>
T& LinkedList<T>::GetData()
{
      if(nListLength==0||!ptrCurr)        //空链表的处理
      {
            cerr<<"Invalid!"<<endl;
            exit(1);
      }

      return ptrCurr->ShowData();
}

//逐项拷贝链表中的各个结点
template<class T>
void LinkedList<T>::CopyList(const LinkedList<T> &list)
{
      ListNode<T> *ptr=list.ptrFront;
      ptrCurr=NULL;

      while(ptr)      //遍历list并创建新链表
		  {
            InsertAfter(ptr->ShowData());
            ptr=ptr->NextListNode();
      }

      if(nPosition==-1)      //list为空
            return;

      ptrPrev=NULL;
      ptrCurr=ptrFront;

      for(int nPos=0;nPos!=list.CurrPosition();nPos++)
                             //将新链表的各个数据成员设置与原链表相同
      {
            ptrPrev=ptrCurr;
            ptrCurr=ptrCurr->NextListNode();
      }
      nPosition=nPos;
      nListLength=list.ListLength();
}			
//获得下一个新结点,返回新结点地址
template<class T>
ListNode<T> *LinkedList<T>::GetListNode(const T& nItem, ListNode<T> *preNext)
{
      ListNode<T> *newListNode;
      newListNode=new ListNode<T>(nItem,preNext);
      if(!newListNode)
      {
            cerr<<"Memory allocation failure!"<<endl;
            exit(1);
      }
      return newListNode;
}

//输出链表中的各个结点数据
template<class T>
void LinkedList<T>::DisplayList()
{
	ListNode<T> *p;
      p=ptrFront;
      cout<<endl<<"（";
	  while(p)        //遍历链表
      {
            cout<<p->ShowData()<<",";	
			p=p->NextListNode();
      }
	  cout<<"）"<<endl;
}

//在链表中查找数据
template<class T>
int LinkedList<T>::Find(T& nItem)
{
      ptrCurr=ptrFront;
      ptrPrev=NULL;
      while(ptrCurr)
      {
            if(ptrCurr->ShowData()==nItem)
                  return 1;
            ptrPrev=ptrCurr;
            ptrCurr=ptrCurr->NextListNode();
			nPosition++;                      //控制当前指针位置
      }
      return 0;
}

//删除链表中满足条件的结点
template<class T>
void LinkedList<T>::Delete(T key)
{
      ptrCurr=ptrFront;
      ptrPrev=NULL;
      if(!ptrCurr)
            return;
      while(ptrCurr&&ptrCurr->ShowData()!=key)      //查找相应的结点
      {
            ptrPrev=ptrCurr;
            ptrCurr=ptrCurr->NextListNode();
            nPosition++;
      }

      if(ptrCurr)      //如果找到该结点,删除它
      {
            if(!ptrPrev) ptrFront=ptrFront->NextListNode();
            else ptrPrev->DeleteAfter();
            delete ptrCurr;
      }
}

template<class T>
void LinkedList<T>::InsertOrder(T nItem)
{
      ListNode<T> *newListNode,
                    *next,         //用于遍历链表
                      *prev;      //next指向结点的前一个结点的指针
      ptrPrev=NULL;
      ptrCurr=ptrFront;
      prev=ptrCurr;
      next=ptrCurr->NextListNode();

      while(prev->ShowData()==next->ShowData()&&(next))
                                  //判断原链表的排序方式,升序或者降序
      {
            prev=next;
            next=next->NextListNode();
      }

    if(!next) InsertFront(nItem);        //如果原链表中所有结点均相等,则将结点
				//作为原链表的首结点
      else if(prev->ShowData()>next->ShowData())  //降序排列时
      {
		  while(ptrCurr)            //寻找插入位置
            {
                  if(nItem>=ptrCurr->ShowData()) break;
                  ptrPrev=ptrCurr;
                  ptrCurr=ptrCurr->NextListNode();
            }

            if(!ptrPrev) InsertFront(nItem);
            else
            {
                  newListNode=GetListNode(nItem);
                  ptrPrev->InsertAfter(newListNode);
            }
      }
      else     //升序排列时
      {
            while(ptrCurr)    //寻找插入位置
            {
                  if(nItem<=ptrCurr->ShowData()) break;
                  ptrPrev=ptrCurr;
                  ptrCurr=ptrCurr->NextListNode();
            }
			            if(!ptrPrev) InsertFront(nItem);
            else
            {
                  newListNode=GetListNode(nItem);
                  ptrPrev->InsertAfter(newListNode);
            }
      }

}
#endif