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;
}
