C＋＋数据结构中的用模板定义的单链表类

template < class Type> class List;  //前视的类定义

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

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

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

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

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

template <class Type> List<Type>::~List()
{
 MakeEmpty();
 delete first;
}

template <class Type> void List<Type>::MakeEmpty()
{
 ListNode<Type> *q;
 while(first->link!=NULL)
 {
  q=first->link;
  first->link=q->link;
  delete q;
 }
 last=first;
}

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

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

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

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

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

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