list.h

用C++实现的“表”（list）类

template < class Record> class Sort_list;  //前视的类定义

template < class Record > class Sort_listNode //链表节点类的定义
{
 friend class Sort_list<Record>;   //Sort_list类作为友元类定义
 public:
  Sort_listNode();      //不给数据的构造函数
  Sort_listNode(const Record&item);  //给数据的构造函数
  Sort_listNode<Record> * NextNode()  //给出当前节点的下一个节点地址
  {
   return link;
  }
  void InsertAfter( Sort_listNode<Record> * p); //当前节点插入
  Sort_listNode<Record> * GetNode(const Record&item,Sort_listNode<Record> * next);//建立一个新节点
  Sort_listNode<Record> * RemoveAfter();   //删除当前节点的下一个节点
 private:
  Record data;     //数据域
  Sort_listNode<Record> *link;  //链指针域
};

template <class Record> class Sort_list //单链表类定义
{
 public:
  Sort_list(const Record & value) //构造函数
  {
   last=first=new Sort_listNode<Record>(value);
  }
  ~Sort_list();     //析构函数
  void MakeEmpty();   //将链表置为空表
  int Length() const;   //计算链表的长度
  Sort_listNode<Record> * Find(Record value);  //在链表中搜索含数据value的结点
  Sort_listNode<Record> * Find(int i);   //搜索链表中第i个元素的地址
  int Insert(Record value,int i);   //将元素value插入在链表中第i个位置
  Record * Remove(int i);     //将链表中的第i个元素删去
  Record * Get(int i);      //取出链表中的第i个元素
 private:
  Sort_listNode<Record>*first,*last;    //链表的表头指针,表尾指针
};

template <class Record> Sort_listNode<Record>::Sort_listNode():link(NULL){}
template <class Record> Sort_listNode<Record>::Sort_listNode(const Record&item):data(item),link(NULL){}
template <class Record> void Sort_listNode<Record>::InsertAfter(Sort_listNode<Record> *p)
{
 p->link=link;
 link=p;
}

template <class Record> Sort_listNode<Record>::GetNode(const Record& item,Sort_listNode<Record> *next=NULL)
{
 Sort_listNode<Record> *newnode=new Sort_listNode<Record>(item);
 newnode->link=next;
 return newnode;
}

template <class Record> Sort_listNode<Record> * Sort_listNode<Record>::RemoveAfter()
{
 Sort_listNode<Record> * tempptr=link;
 if(link==NULL)return NULL;
 link=tempptr->link;
 return tempptr;
}

template <class Record> Sort_list<Record>::~Sort_list()
{
 MakeEmpty();
 delete first;
}

template <class Record> void Sort_list<Record>::MakeEmpty()
{
 Sort_listNode<Record> *q;
 while(first->link!=NULL)
 {
  q=first->link;
  first->link=q->link;
  delete q;
 }
 last=first;
}

template <class Record> int Sort_list<Record>::Length() const
{
 Sort_listNode<Record>*p=first->link;
 int count=0;
 while(p!=NULL){p=p->link;count++;}
 return count;
}

template <class Record> Sort_listNode<Record> * Sort_list <Record>::Find(Record value)
{
 Sort_listNode<Record> *p=first->link;
 while(p!=NULL && p->data!=value)p=p->link;
 return p;
}

template <class Record> Sort_listNode<Record> *Sort_list<Record>::Find(int i)
{
 if(i<-1)return NULL;
 if(i==-1)return first;
 Sort_listNode<Record> *p=first->link;
 int j=0;
 while(p!=NULL && j<i)
 {
  p=p->link;
  j=j++;
 }
 return p;
}

template <class Record> int Sort_list<Record>::Insert(Record value,int i)
{
 Sort_listNode<Record> *p=Find(i-1);
 if(p==NULL)return 0;
 Sort_listNode<Record> * newnode=GetNode(value,p->link);
 if(p->link==NULL)last=newnode;
 p->link=newnode;
 return 1;
}

template <class Record> Record *Sort_list<Record>::Remove(int i)
{
 Sort_listNode<Record> *p=Find(i-1),*q;
 if(p==NULL || p->link==NULL)return NULL;
 q=p->link;
 p->link=q->link;
 Record value=new Record(q->data);
 if(q==last)last=p;
 delete q;
 return &value;
}

template <class Record> Record *Sort_list<Record>::Get(int i)
{
 Sort_listNode<Record> *p=Find(i);
 if(p==NULL || p==first)return NULL;
 else return &p->data;
}