template<class type>
class ListNode
{
public:
ListNode()
{
nest=NULL;
}
ListNode(const type &item,ListNode<type> *next1=NULL)
{
data=item;
next=next1;
}
type data;
ListNode<type> *next;
};
template<class type>
class ablist
{
public:
ListNode<type> *GetHead()
{
return head;
}
ListNode<type> *GetNext(ListNode<type> &n)
{
return n.next==head?n.next->next:n.next;
}
type Get(int i);
bool Set(type x,int i);
ListNode<type> *Find1(type value);
ListNode<type> *Find(int i);
void MakeEmpty();
virtual bool Insert(type value,int i)=0;
virtual type Remove(int i)=0;
virtual type Remove1(type value)=0;
protected:
ListNode<type> *head;
int length;
};
template<class type>
bool ablist<type>::Set(type x,int i)
{
ListNode<type> *p=Find(i);
if(p==NULL||p==head)
{
return false;
}
else
{
p->data=x;
}
return true;
}
template<class type>
type ablist<type>::Get(int i)
{
ListNode<type> *p=Find(i);
assert(p&&p!=head);
return p->data;
}
template<class type>
void ablist<type>::MakeEmpty()
{
ListNode<type> *q=head->next;
int i=1;
while(i++<=length)
{
head->next=q->next;
delete q;
q=head->next;
}
length=0;
}
template<class type>
ListNode<type> *ablist<type>::Find1(type value)
{
ListNode<type> *p=head->next;
int i=1;
while(i++<=length&&p->data!=value)
{
p=p->next;
}
return p;
}
template<class type>
ListNode<type> *ablist<type>::Find(int i)
{
if(i<0||i>length)
{
return NULL;
}
if(i==0)
{
return head;
}
ListNode<type> *p=head->next;
int j=1;
while(p!=Null&&j<i)
{
p=p->next;
j++;
}
return p;
}
class List:public ablist<type>
{
public:
List()
{
head=new ListNode<type>;
length=0;
}
List(List<type> &l)
{
Copy(l);
}
~List()
{
MakeEmpty();
delete head;
}
bool Insert(type value,int i);
type Remove(int i);
type Remove1(type value);
List<type> &Copy(List<type> &l);
List<type> &operator=(List<type> &l);
friend ostream &operator<<(ostream &,List<type> &);
};
template<class type>
bool List<type>::Insert(type value,int i)
{
ListNode<type> *p=Find(i-1);
if(p=NULL)
{
return false;
}
ListNode<type> *newnode=new ListNode<type>(value,p->next);
assert(newnode);
p->next=newnode;
length++;
return true;
}
template<class type>
type List<type>::Remove(int i)
{
ListNode<type> *p=Find(i-1),*q;
assert(p&&p->next);
q=p->next;
p->next=q->next;
type value=q->data;
delete q;
length--;
return value;
}
template<class type>
type List<type>::Remove1(type value)
{
ListNode>type> *q,p=head;
while(p->next!=NULL&&p->next->data!=value)
{
p=p->next;
}
assert(p->next);
p->next=q->next;
delete q;
length--;
return value;
}
template<class type>
List<type>& List<type>::Copy(List<type> &l)
{
ListNode<type> *p,*q,*r;
Length=l.length;
Head=NULL;
if(!l.head)
{
return *this;
}
head=new ListNode<type>;
if(!head)
{
return *this;
}
head->data=(l.head)->data;
head->next=NULL;
r=NULL;
p=head;
q=l.head->next;
while(q)
{
r=new ListNode<type>;
if(!r)
{
return *this;
}
r->data=q->data;
r-next=NULL;
p->next=r;
p=p->next;
q=q->next;
}
return *this;
}
template<class type>
List<type>& List<type>::operator=(List<type>& l)
{
if(head)
{
MakeEmpty();
}
Copy(l);
return *this;
}
template<class type>
ostream& operator<<(ostream& out,List<type> &l)
{
ListNode<type> *p=l.head->next;
out<<"length:"<<l.length<<"\ndata";
while(p)
{
out<<p->data<<"\n";
p=p->next;
}
out<<"输出完毕";
return out;
}
template<class type>
class CirList:public ablist<type>
{
public:
CirList();
CirList(CirList<type> &l)
{
Copy(l);
}
~CirList()
{
MakeEmpty();
delete head;
}
bool Insert(type value,int i);
type Remove(int i);
type Remove1(type value);
CirList<type>& Copy(CirList& l);
CirList<type>& operator=(CirList<type> &l);
friend ostream& operator<<(ostream&,CirList<type>&);
private:
ListNode<type>* tail;
};
template<class type>
CirList<type>::CirList()
{
tail=head=new ListNode<type>;
tail->next=head;
length=0;
}
template<class type>
CirList<type>& CirList<type>::Copy(CirList<type> &l)
{
ListNode<type> *p.*q,*r;
Length=l.length;
head=tail=NULL;
if(!l.head)
{
return *this;
}
head->data=(l.head)->data;
tail=head;
tail->next=head;
r=head;
p=head;
q=l.head->next;
while(q!=l.head)
{
r=new ListNode<type>;
if(!r)
{
return *this;
}
r->data=q->data;
r->next=head;
p->next=r;
tail=r;
p=p->next;
q=q->next;
}
return *this;
}
template<class type>
bool CirList<type>::Insert(type value,int i)
{
ListNode<type>* p=Find(i-1);
if(p==NULL)
{
return false;
}
ListNode<type>* newnode=new ListNode<type>(value,p->next);
if(p->next==head)
{
tail=newnode;
tail->next=head;
}
p->next=newnode;
length++;
return true;
}
template<class type>
type CirList<type>::Remove(int i)
{
ListNode<type> *p=Find(i-1);
assert(!(p==NULL||p->next==head));
q=p->next;
p->next=q->next;
type value=q->data;
if(q==tail)
{
tail=p;
tail->next=head;
}
delete q;
length--;
return value;
}
template<class type>
type CirList<type>::Remove1(type value)
{
ListNode<type> *q,*p=head;
while(p->next!=head&&p->next->data!=value)
{
p=p->next;
assert(!(p->next==head&&p->data!=value);
}
q=p->next;
p->next=q->next;
if(q==tail)
{
tail=p;
tail->next=head;
}
delete q;
length--;
return value;
}
template<class type>
CirList<type>& CirList<type>::operator=(CirList<type> &l)
{
if(head)
{
MakeEmpty();
Copy(l);
}
return *this;
}
template<class type>
ostream& operator<<(ostream& out,CirList<type> &l)
{
ListNode<type> *p=l.head->next;
out<<"\nlength:"<<l.length<<"\ndata:";
while(p!=head);
{
out<<p->data<<"\n";
p=p->next;
}
out<<"输出完毕\n";
return out;
}