/*在双向循环链表结构上实现ADT5-1*/(带头结点)
/*************************在vc2005中编译通过***************************************/
/************************* **************************************/
#include
#include
using namespace std;
enum ResultCode{OVERFLOW,UnderFlow,OutOfBounds};
template
struct Node
{
Node(const T& x=T(),Node* next=NULL)
{
element=x;
link=next;
}
T element;
Node* link;
};
template
class List;
template
class LinkList;
template
ostream& operator<<(ostream& out,const LinkList& x);
template
istream& operator>>(istream& in,LinkList& x);
template
class List
{
public:
virtual void Insert(int pos,const T&x)=0;
virtual void Remove(int pos)=0;
virtual void Retrieve(int pos, T &x)=0;
virtual void Replace(int pos,const T& x)=0;
virtual int Length() const=0;
virtual bool IsEmpty() const=0;
virtual bool IsFull() const=0;
virtual void Clear()=0;
};
template
class LinkList:public List
{
public:
LinkList()
{
head=new Node(0,NULL);
head->link=head;
}
~LinkList(){Clear();}
void Insert(int pos,const T& x);
void Remove(int pos);
void Retrieve(int pos, T& x);
void Replace(int pos,const T& x);
int Length() const
{
int i=0;
Node* temp=head->link;
for(;temp->link!=head;temp=temp->link)
++i;
return i;
}
bool IsEmpty() const
{
return (head->link==head);
}
bool IsFull()const
{
Node* temp=new Node(0,head);
if(temp==NULL)
return true;
else
return false;
}
void Clear()
{
Node* first=head;
for(Node* temp=head->link;temp!=first;temp=head)
{
head=head->link;
delete temp;
}
}
private:
Node* head;
Node* SetPose(int i);
void Output(ostream& out)const;
friend ostream& operator<<<>(ostream& out,const LinkList& x);
friend istream& operator>><>(istream& in,LinkList& x);
};
template
Node* LinkList::SetPose(int i)
{
if(i==0)
return head;
else
{
Node* temp=head->link;
for(;temp!=head,i>1;temp=temp->link)
--i;
if(i>1) throw OutOfBounds;
return temp;
}
}
template
void LinkList::Insert(int pos,const T& x)
{
Node* temp=new Node(x,NULL);
Node* before=SetPose(pos-1);
Node* after=SetPose(pos+1);
before->link=temp;
temp->link=after;
}
template
void LinkList::Remove(int pos)
{
Node* before=SetPose(pos-1);
Node* after=SetPose(pos+1);
before->link=after;
}
template
void LinkList::Retrieve(int pos, T &x)
{
Node* temp=SetPose(pos);
x=temp->element;
}
template
void LinkList::Replace(int pos,const T& x)
{
Node* temp=SetPose(pos);
temp->element=x;
}
template
void LinkList::Output(ostream& out)const
{
Node* temp=head->link;
if(IsEmpty())
out<<"The List is empty";
else
{
out<<"the list contains:"< for(;temp!=head;temp=temp->link)
out<element<<",";
}
}
template
ostream& operator<<(ostream& out,const LinkList& x)
{
x.Output(out);
return out;
}
template
istream& operator>>(istream& in,LinkList& x)
{
cout<<"please input the member of list:"< char c=0;
Node* temp=x.head;
T i;
while(c!='\n')
{
cin>>i;
temp->link=new Node(i,NULL);
temp=temp->link;
c=getchar();
}
temp->link=x.head;
return in;
}
int main()
{
LinkList x;
cin>>x;
cout< system("pause");
return 0;
}
/********************************************************************************************************************************************************************/
/*在双向循环链表结构上实现ADT5-1*/(不带头结点)
#include
#include
using namespace std;
enum ResultCode{OVERFLOW,UnderFlow,OutOfBounds};
template
struct Node
{
Node(const T& x=T(),Node* next=NULL)
{
element=x;
link=next;
}
T element;
Node* link;
};
template
class List;
template
class LinkList;
template
ostream& operator<<(ostream& out,const LinkList& x);
template
istream& operator>>(istream& in,LinkList& x);
template
class List
{
public:
virtual void Insert(int pos,const T&x)=0;
virtual void Remove(int pos)=0;
virtual void Retrieve(int pos, T &x)=0;
virtual void Replace(int pos,const T& x)=0;
virtual int Length() const=0;
virtual bool IsEmpty() const=0;
virtual bool IsFull() const=0;
virtual void Clear()=0;
};
template
class LinkList:public List
{
public:
LinkList()
{
head=NULL;
}
~LinkList(){Clear();}
void Insert(int pos,const T& x);
void Remove(int pos);
void Retrieve(int pos, T& x);
void Replace(int pos,const T& x);
int Length() const
{
if(IsEmpty()) return 0;
int i=1;
Node* temp=head->link;
for(;temp!=head;temp=temp->link)
++i;
return i;
}
bool IsEmpty() const
{
return (head==NULL);
}
bool IsFull()const
{
Node* temp=new Node(0,NULL);
if(temp==NULL)
return true;
else
return false;
}
void Clear()
{
Node* first=head;
for(Node* temp=head;temp!=first;)
{
head=head->link;
delete temp;
temp=head;
}
}
private:
Node* head;
Node* SetPose(int i);
void Output(ostream& out)const;
friend ostream& operator<<<>(ostream& out,const LinkList& x);
friend istream& operator>><>(istream& in,LinkList& x);
};
template
Node* LinkList::SetPose(int i)
{
if(i==0)
return head;
else
{
Node* temp=head;
for(;temp!=head,i>1;temp=temp->link)
--i;
if(i>1) throw OutOfBounds;
return temp;
}
}
template
void LinkList::Insert(int pos,const T& x)
{
Node* temp=new Node(x,NULL);
Node* before=SetPose(pos-1);
Node* after=SetPose(pos+1);
before->link=temp;
temp->link=after;
}
template
void LinkList::Remove(int pos)
{
Node* before=SetPose(pos-1);
Node* after=SetPose(pos+1);
before->link=after;
}
template
void LinkList::Retrieve(int pos, T &x)
{
Node* temp=SetPose(pos);
x=temp->element;
}
template
void LinkList::Replace(int pos,const T& x)
{
Node* temp=SetPose(pos);
temp->element=x;
}
template
void LinkList::Output(ostream& out)const
{
Node* temp=head;
if(IsEmpty())
out<<"The List is empty";
else
{
out<<"the list contains:"< for(;temp->link!=head;temp=temp->link)
out<element<<",";
out<element<
}
}
template
ostream& operator<<(ostream& out,const LinkList& x)
{
x.Output(out);
return out;
}
template
istream& operator>>(istream& in,LinkList& x)
{
cout<<"please input the member of list:"< char c=0;
T i;
Node* p=NULL;
Node* r=NULL;
while(c!='\n')
{
cin>>i;
if(x.head==NULL)
{
x.head=new Node(i,NULL);
p=x.head;
cout<element< }
else
{
r=new Node(i,NULL);
p->link=r;
p=r;
}
c=getchar();
}
p->link=x.head;
return in;
}
int main()
{
LinkList x;
cin>>x;
cout< system("pause");
return 0;
}
阅读(1571) | 评论(0) | 转发(0) |
