// 链表.cpp :
//written by JYK
#include "stdafx.h"
#include<iostream>
using namespace std;
template <class Type> class List;
template <class Type> class ListNode
{
friend class List<Type>;
public:
ListNode();
ListNode(const Type & x);
static ListNode<Type> *creat(Type value,ListNode<Type> *next);
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(int i);
int insert(Type data,int i);
Type *remove(int i);
Type *get(int i);
void print();
private:
ListNode<Type> *first,*last;
};
template <class Type>ListNode<Type>::ListNode()
{
link=NULL;
}
template <class Type>ListNode<Type>::ListNode(const Type &x)
{
data=x;
link=NULL;
}
template <class Type>ListNode<Type>* ListNode<Type>::creat(Type value, ListNode<Type> *next)
{
ListNode<Type> *p=new ListNode<Type>(value);
p->link=next;
return p;
}
template <class Type> List<Type>::~List()
{
MakeEmpty();
delete first;
}
template<class Type>void List<Type>::MakeEmpty()
{
ListNode<Type> *p;
while(first->link!=NULL)
{
p=first->link;
first->link=p->link;
delete p;
}
last=first;
}
template <class Type>int List<Type>::length()const
{
int count=0;
ListNode<Type> *p=first->link;
while(p!=NULL)
{
p=p->link;
count++;
}
return count;
}
template <class Type>ListNode<Type>* List<Type>::Find(int i)
{
int count=0;
if(i<-1)
return NULL;
if(i==-1)
return first;
ListNode<Type> *p=first->link;
while(p!=NULL&&count<i)
{
p=p->link;
count++;
}
return p;
}
template <class Type>int List<Type>::insert(Type data,int i)
{
ListNode<Type> *p=Find(i-1);
if(p==NULL)
return 0;
ListNode<Type> *newnode=ListNode<Type>::creat(data,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;
if(q==last)
last=p;
Type *temp=new Type(q->data);
delete q;
return temp;
}
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;
}
template <class Type>void List<Type>::print()
{
ListNode<Type> *p=first->link;
while(p!=NULL)
{
cout<<p->data<<' ';
p=p->link;
}
cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
List <int> a(10);
for(int i=0;i<10;i++)
a.insert(i,i);
cout<<"length:"<<a.length()<<endl;
a.print();
cout<<"get(5):"<<*(a.get(5))<<endl;
a.remove(3);
a.print();
a.insert(88,6);
a.print();
char b[]="abcdefghijkmn";
List<char> m('$');
for(int i=0;i<12;i++)
m.insert(b[i],i);
cout<<"length:"<<m.length()<<endl;
m.print();
cout<<"get(5):"<<*(m.get(5))<<endl;
m.remove(3);
m.print();
m.insert('&',6);
m.print();
return 0;
}