单链表.txt

一些很好用的数据结构

//?ùàà
template <class Elem> class List{
public:
virtual void clear()=0;
virtual bool insert(const Elem&)=0;
virtual bool append(const Elem&)=0;
virtual bool remove(Elem&)=0;
virtual void setStart()=0; virtual void setEnd()=0;
virtual void prev()=0;
virtual void next()=0;
virtual int leftLength() const=0;
virtual int rightLength() const=0;
virtual bool setPos(int Pos)=0;
virtual bool getValue(Elem&) const=0;
virtual void print() const=0;
};



//?éà?ó?????±í
template <class Elem> class Link{
 public:
    Elem element;
    Link* next;
    Link(const Elem& elemval, Link *nextval=0)
     {element=elemval; next=nextval;}
    Link( Link *nextval=0)
     { next=nextval;}
};
 
#include"list.h"
#include"link.h"

template <class Elem>class LList:public List<Elem>{
private:
     Link<Elem>* head;
     Link<Elem>* tail;
     Link<Elem>* fence;
     int leftcnt, rightcnt;

     //?ù±???D?±íμ?′′?¨2ù×÷êμ??
     void init()
	 {
           fence=head=tail=new Link<Elem>;
           leftcnt=rightcnt=0;
      }//init
      void removeall()
	  { 
         while(head!=0)
             {fence=head;head=head->next; delete fence;}
      } //removeall 
	  
public:
   LList(int size=DefaultListSize)
   {
	   init();
   }

   ~LList(){removeall();}
   void clear(){removeall();  init();}
   bool insert(const Elem &);
   bool append(const Elem &);
   bool remove(Elem&);
   void setStart(){
         fence=head;rightcnt+=leftcnt;
          leftcnt=0;
     }//setStart; 
    void setEnd()
	{
      fence=tail;leftcnt+=rightcnt;rightcnt=0;
    }//setEnd
    void prev();
    void next()
	{
      if(fence!=tail){fence=fence->next;
       rightcnt--; leftcnt++;}
    }//next;
    int leftLength()const{ return leftcnt;}
    int rightLength() const{return rightcnt;}
    bool setPos(int Pos);
    bool getValue(Elem &it) const
	{
     if(rightLength()==0) return false;
     it=fence->next->element; return true;  
    }//getValue
    void print() const;
};







#include"Alist.h"
#include<iostream>
using namespace std;
//?ù±???D?±í2?è?2ù×÷μ?êμ??
template <class Elem>
bool LList<Elem>::insert(const Elem&item)
  {
    fence->next=new   Link<Elem>(item,fence->next);
   if(tail==fence)tail=fence->next;
    rightcnt++;
    return true;
  }
//?ù±???D?±í???2×·?óêy?Y2ù×÷μ?êμ??
template <class Elem>
bool LList<Elem>::append(const Elem & item)
  {
    tail=tail->next=new Link<Elem>(item,0);
    rightcnt++;
    return true;
  }
//?ù±???D?±íé?3y2ù×÷μ?êμ??
template <class Elem>
 bool LList<Elem>::remove(Elem& it)
 {
   if(fence->next==NULL) return false;
   it=fence->next->element;
   Link<Elem>*Itemp=fence->next;
   fence->next=Itemp->next;
   if(tail==Itemp) tail=fence;
   delete Itemp;
   rightcnt--;
   return true;
  }
template <class Elem>
 void LList<Elem>::prev(){
   Link<Elem> * temp=head;
   if (fence==head) return;
   while(temp->next!=fence)
         temp=temp->next;
  fence=temp;
  leftcnt--; rightcnt++;
}
template <class Elem>
 bool LList<Elem>::setPos(int pos){
  if((pos<0)||(pos>(rightcnt+leftcnt))) 
      return false;
   setStart();
   for(int i=0;i<pos;i++)
      next();   
   return true;
  }
template <class Elem>
 void LList<Elem>::print() const{
  Link<Elem>* temp=head;
  cout<<"<";
  while(temp!=fence){
    cout<<temp->next->element<<"   ";
    temp=temp->next;
    }
 cout<<"|";
 while(temp->next!=NULL)
 {
    cout<<temp->next->element<<"  ";
    temp=temp->next;
 } 
cout<<">\n";
}