数据结构第五章(5-2)

/*补充实现所有单链表存储表示下的线性表(见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) const=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);
 }
 ~LinkList(){Clear();}
 void Insert(int pos,const T& x);
 void Remove(int pos);
 void Retrieve(int pos, T& x)const;
 void Replace(int pos,const T& x);
 int Length() const
 {
  int i=0;
  Node* temp;
  for(temp=head;temp->link!=NULL;temp=temp->link)
   ++i;
  return i;
 }
 bool IsEmpty() const
 {
  return (head->link==NULL);
 }
 bool IsFull()const
 {
  Node* temp=new Node(0,NULL);
  if(temp==NULL)
   return true;
  else
   return false;
 }
 void Clear()
 {
        for(Node* temp=head;temp!=NULL;temp=head)
  {
   head=head->link;
   delete temp;
  }
  delete 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=NULL;
 for(temp=head;temp!=NULL,i>0;temp=temp->link)
 --i;
 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) const
{
 Node* temp=new Node(x,NULL);
 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!=NULL;temp=temp->link)
  out<element<<",";
 }
 delete temp;
}
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();
 }
return in;
}
int main()
{
    LinkList x;
 cin>>x;
 cout<  system("pause");
 return 0;
}