数据结构--顺序表、链表、栈

此代码为笔者数据结构作业，仅供学习使用。

1、顺序表

#include 
#include 
#include 
#include 

using namespace std;

const int defaultSize = 100;
template
class SeqList
{
private:
    T* data;//指向动态内存分配数组的指针
    int maxSize;//动态内存分配数组的容量
    int last;//标识顺序表中最后一个元素的位置(反映顺序表中的元素个数)
    void Resize(int newSize);
public:
    SeqList(int sz=defaultSize);//构造函数
    SeqList(const SeqList& L);//拷贝构造函数
    SeqList& operator=(const SeqList& L);//赋值运算符函数

    ~SeqList();//析构函数

    int Size() const;//返回顺序表的容量
    int Length() const;//返回顺序表中元素的个数
    bool IsEmpty() const;//顺序表是否为空
    bool IsFull() const;//顺序表是否为满
    bool Locate(int i) const;//检验顺序表中是否存在第i个元素
    bool GetData(int i, T& x) const;//获取顺序表中第i个位置的元素
    void SetData(int i, T& x);//将顺序表中第i个位置的元素赋值为x

    int Search(T & x) const;//在顺序表中搜索x
    bool Insert(int i, const T& x) ;//在顺序表的第i个元素的位置插入x
    bool Remove(int i, T&x) ;//删除顺序表第i个位置的元素

    void Sort() ;//对顺序表中元素进行排序
    void Reverse ();//逆置顺序表中的元素
    template
    friend istream& operator>>(istream& in, SeqList<_T> & L);//输入运算符重载
    template
    friend ostream& operator<<(ostream& out, const SeqList<_T>& L);//输出运算符重载

    T & operator[] ( int index );
    const T & operator[] ( int index ) const;
    void Push_Back ( const T& x);
    void Pop_Back( );
    typedef T * iterator;
    typedef const T * const_iterator;
    iterator Begin( )
    {
        return &data[0];
    }
    const_iterator Begin( ) const
    {
        return &data[0];
    }
    iterator End( )
    {
        return &data[ Length() ];
    }
    const_iterator End( ) const
    {
        return &data[ Length() ];
    }
};
template
SeqList::SeqList(int sz)
{

    this->maxSize = sz;

    this->data = new T[maxSize];

    if(data==NULL)
    {
        exit(1);
    }
    else
    {
        cout<<"distribute successfully！"<last = -1;

}
template
void SeqList:: Resize(int newSize)
{
    if(newSizemaxSize = newSize;


    T tempdata = new T[last+1];
    for(int i=0; i<=last; i++)
    {
        tempdata[i] = data[i];
    }
    this->data = new T[newSize];
    if(data==NULL)
    {
        exit(1);
    }
    else
    {
        cout<<"distribute successfully！"<data = tempdata[i];
    }
}
template
SeqList:: SeqList(const SeqList& L)
{

    this->maxSize = L.maxSize;
    this->data = new T[maxSize];
    this->last = L.last;
    for(int i=0; i<=last; i++)
        this->data[i] = L.data[i];

}
template
SeqList&  SeqList::operator=(const SeqList& L)
{

    this->maxSize = L.maxSize;
    delete[] this->data;
    this->data = new T[maxSize];
    if(data==NULL)
    {
        exit(1);
    }
    else
    {
        cout<<"distribute successfully！"<last = L.last;
    for(int i=0; i<=last; i++)
        this->data[i] = L.data[i];
    return *this;

}
template
SeqList::~SeqList()
{

    delete[] this->data;

    this->last = -1;

    this->maxSize=0;

}
template
int SeqList:: Size() const
{
    return this->maxSize;
}
template
int SeqList::Length() const
{
    return this->last+1;
}
template
bool SeqList::IsEmpty() const
{
    if(this->last==-1)
        return true;
    else
        return false;
}
template
bool SeqList::IsFull() const
{

    if((this->last+1) == this->maxSize)
        return true;
    else
        return false;
}
template
bool SeqList::Locate(int i) const
{

    if(i<=0||i>last+1)
        return false;
    else
        return true;
}
template
bool SeqList::GetData(int i, T& x) const
{

    if(i<=0||i>this->last+1)
        return false;
    else
        x = this->data[i-1];
    return true;

}
template
void SeqList::SetData(int i, T& x)
{
    if(i>0&&i<=this->maxSize)
    {
        this->data[i-1] = x;
        return;
    }
    else  if(i==maxSize+1)
    {
        T* temp=new T[last];

        if(temp==NULL)
        {
            exit(1);
        }
        else
        {
            cout<<"distribute successfully！"<data[j];
        }
        this->data = new T[maxSize*3];
        if(data==NULL)
        {
            exit(1);
        }
        else
        {
            cout<<"distribute successfully！"<maxSize = 3*maxSize;
        for(int j=0; jdata[j] = temp[j];
        }
        this->data[i-1]=x;
        last++;
        return;
    }
    else
        exit(1);
}
template
int SeqList::Search(T & x) const
{

    for(int i=0; i<=this->last; i++)
    {

        if(this->data[i]==x)
            return i+1;
    }
    return false;
}
template
bool SeqList::Insert(int i, const T& x)
{

    if(i<=0||i>last+1)
        return false;
    else
    {
        for(int j=last; j>=i-1; j--)
        {
            this->data[j+1]=data[j];
        }
        this->data[i-1]=x;
        last++;
        return true;
    }
}
template
bool SeqList::Remove(int i, T&x)
{

    if(i<=0||i>last+1)
        return false;
    x= this->data[i-1];
    for(int j=i-1; jdata[j]=data[j+1];

    last--;
    return true;

}
template
void SeqList::Sort()
{

    for(int i=0; idata[j+1])
            {
                T temp=data[j];
                data[j] = data[j+1];
                data[j+1]=temp;
            }
        }
}
template
void SeqList::Reverse ()
{
    int j=last;
    for(int i=0; idata[i];
        data[i] = data[j-i];
        data[j-i]=temp;
    }
}
template
istream& operator>>(istream& in, SeqList<_T> & L)
{
int i =1;

    while(i++!=L.maxSize)
    {
        in>>L.data[++L.last];
        if(getchar()=='n')
            break;
    }


    return in;
}
template
ostream& operator<<(ostream& out, const SeqList<_T>& L)
{

    for(int i=0; i<=L.last; i++)
    {

        out< sList;

    cin>>sList;
    int i, val;
    cin>>i>>val;
    sList.Insert(i,val);
    cout<>i;
    sList.Remove(i,val);
    cout<>val;
    i=sList.Search(val);
    if(i==0)
        cout<<"Not found"< 
2、链表
 
#include 
#include 
#include 
using namespace std;
typedef int T;
struct linkNode //结点定义
{
    T data;//数据域
    linkNode* next;//链域
    linkNode(const T& item, linkNode* ptr=NULL)
    {
        data=item;
        next=ptr;
    }
    linkNode(linkNode* ptr=NULL)
    {
        next=ptr;
    }
};
class List
{
private:
    linkNode * first;
public:
    List()//构造函数
    {
        this->first= new linkNode();
    }
    List(const T& x)
    {
        this->first = new linkNode();
        this->first->next = new linkNode(x);
    }

//      List(int n,);
    List(const List& L)//拷贝构造函数
    {
        linkNode* q = this->first =new linkNode();
        for(linkNode *p=L.first->next; p!=NULL; p=p->next)
        {
            q ->next = new linkNode(p->data);
            q= q->next;
        }
    }
    List& operator=(const List& L)//赋值运算符函数
    {
        linkNode* q = this->first =new linkNode();
        for(linkNode *p=L.first->next; p!=NULL; p=p->next)
        {
            q ->next = new linkNode(p->data);
            q= q->next;
        }
        return *this;
    }
    ~List()//析构函数
    {
        this->MakeEmpty();
        delete []first;
    }

    void InputFront(const T& elem)//头插法
    {
        linkNode *pre = this->first->next;

        linkNode* newNode = new linkNode(elem);
        newNode->next = pre;
        this->first->next = newNode;
    }
    void InputRear(const T& elem)//尾插法
    {
        linkNode* p=NULL;

        for( p=this->first->next; p!=NULL; p=p->next) {}

        p=new linkNode(elem);


    }

    void MakeEmpty()//清空链表
    {
        linkNode*p = this->first;

        while(p!=NULL)
        {
            linkNode*q = p->next->next;

            delete p->next;

            p = q;
        }
    }
    int Length() const//返回链表中结点个数
    {
        linkNode *pre = first->next;
        int num=0;
        while(pre!=NULL)
        {
            ++num;
            pre=pre->next;
        }
        return num;
    }

    linkNode* Search(const T& x)//在链表中查找元素x，找到返回它所在结点的地址，否则返回空
    {
        linkNode * p =first->next;

        while(p->data!=x)
        {
            p=p->next;
            if(p==NULL)
	return;
        }
       
        return p;
    }
    linkNode* Locate(int i)//返回链表中第i个结点的地址，i取值不合法则返回空
    {

        if(i<=0||i>this->Length())
        {
            cout<<"输入非法！"<next;
        for(j=1; j!=i; j++)
        {
            p=p->next;
        }
        return p;

    }

    bool GetData(int i, T& x)const//获取链表第i个元素，将它赋值给x
    {
        if(i<=0)
        {
            cout<<"输入非法！"<next;
        for(j=1; j!=i; j++)
        {
            p=p->next;
        }
        x = p->data;
        return true;
    }
    void SetData(int i, const T& x)//设置链表第i个元素为x
    {
        if(i<=0||i>Length())
        {
            cout<<"输入非法！"<next;
        for(j=1; j!=i; j++)
        {
            p=p->next;
        }
        p->data = x;

        return;
    }

    bool Insert(int i, const T& x)//在链表的第i个位置上插入元素x
    {
        if(i<=0)
        {
            cout<<"输入非法！"<next;
        }
        linkNode* newNode = new linkNode(x,p->next);
        if(NULL==newNode)
        {
            cout<<"无足够空间可分配"<next = newNode;
        return true;
    }
    bool Remove(int i, T& x)//删除链表第i个位置的元素，并将它的值赋值给x
    {
        if(i<=0||i>Length())
        {
            cout<<"输入非法！"<next;
        for(j=1; j!=i-1; j++)
        {
            p=p->next;
        }
        linkNode *q = p->next->next;
        x = p->next->data;
        delete p->next;
        p->next = q;
        return true;
    }

    bool IsEmpty() const//返回链表是否为空
    {
        return first->next==NULL;
    }
    bool IsFull() const//返回链表是否为满
    {
        return  (new linkNode)==NULL;
    }
    void CopyList(const List& L)//复制链表
    {
        this->MakeEmpty();
        linkNode* pre = L.first;
        linkNode* prev = first;
        while(pre!=NULL)
        {
            prev->next= new linkNode(pre->next->data);
	pre= pre->next;
        }
    }
    void Sort()//对链表中结点进行排序
    {
        linkNode * p =first->next;
        linkNode *q=NULL;
        if(NULL==p)
            return ;

        int num = this->Length();
        int maxIndex=1;

        int Max =p->data;
        for(int i=1; idata)
               {
                   maxIndex = j;
                   Max = p->data;
               }
               q=p;
                p=p->next;
            }

            SetData(maxIndex,q->data);
            SetData(num,Max);
        }
    }
    friend ostream& operator<<(ostream& out, const List& L)//输出流运算符重载
    {
        linkNode * p =L.first->next;
        while(p!=NULL)
        {
            out<data<<" ";
            p=p->next;
        }
        out<>(istream& in, List& L)//输入流运算符重载
    {
        int x;
        do{

            in>>x;
            L.InputRear(x);
        }
        while(getchar()!='n');

            return in;
    }
};

int main()
{
    List lst;
    srand(time(NULL));
    for(int i=1; i<=2; i++)
        lst.Insert(i,rand()%50);
    lst.Sort();
    cout< 
3、循环链表
 
#include 
#include 
 #include 
using namespace std;
enum InsMod {INF, INR};//头插还是尾插
template class CirclinkNode{
public:
	T data;
	CirclinkNode *link;
	CirclinkNode(CirclinkNode *ptr = NULL){//建立空结点
		link = ptr;
	}
	CirclinkNode(const T &item, CirclinkNode *ptr = NULL){//建立非空结点
		data = item;
		link = ptr;
	}
};

template class CircList{
public:
	CircList()
	{
	    this->first = new CirclinkNode();
	    first->link=first;

        last=first;
	}
	CircList(CircList &L)//复制一个环链表
	{
	    CirclinkNode* p = L.first->link;
	    CirclinkNode*q = this->first->link;
	    while(p!=first)
        {
            q= new CirclinkNode(p->data);
            q=q->link;
            p=p->link;
        }
        last = q;
	}
	~CircList()
	{
	    this->makeEmpty();
	    delete this->first;
	}
	void makeEmpty()
	{
	    CirclinkNode*p = this->first->link;
	    CirclinkNode*q = p->link;
	    while(p!=first)
        {
            delete p;
            p = q;
            q=q->link;
        }
	}
	int Length()const
	{
	    int num =0;
	    CirclinkNode* p = first->link;

	    while(p!=first)
        {
            ++num;
            p=p->link;
        }
        return num;
	}
	CirclinkNode *Search(T x)
	{
	    CirclinkNode* p = first->link;

	    while(p->data!=x)
        {
            p=p->link;
            if(p==first)
                exit(1);
        }
        return p;
	}
	CirclinkNode *Locate(int i)
	{
	    if(i<1||i>Length())
        {
            exit(1);
        }
        int num=0;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
                return p;
            p=p->link;
        }
        return p;
	}
	bool getData(int i,T&x)const
	{
	    if(i<1||i>Length())
        {
            return false;
        }
        int num=0;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
                x = p->data;
            p=p->link;
        }
        return true;
	}
	void setData(int i, T &x)
	{
	    if(i<1||i>Length())
        {
            return;
        }
        int num=0;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
            p->data=x;
            p=p->link;
        }
	}
	bool Insert(int i, T &x)
	{
        if(i<1||i>Length()+1)
        {
            return false;
        }
        CirclinkNode* p =NULL;
        if(i==1)
            p = first;
        else
	     p = Locate(i-1);

	    CirclinkNode* q = p->link;

	    CirclinkNode *newNode = new CirclinkNode(x);

	    p->link = newNode;

	    newNode->link = q;
        if(i==Length()+1)
        {
        last = newNode;
        }
	    return true;

	}
	bool Remove(int i, T &x)
	{
        if(i<=0||i>Length())
        {
            return false;
        }
        int j=0;
        CirclinkNode* p = first;
        for(j=1; jlink;
        }
        CirclinkNode *q = p->link->link;
        x = p->link->data;
        if(i==Length())
            last = p;
        delete p->link;
        p->link = q;
        return true;
	}
	bool IsEmpty()const
	{
	    return first->link==last;
	}
	bool IsFull()const
	{
	    return (new CirclinkNode() )==NULL;
	}
	void Sort()
	{
        CirclinkNode * p =first->link;
        CirclinkNode *q=NULL;
        if(NULL==p)
            return ;

        int num = this->Length();
        int maxIndex=1;

        int Max =p->data;
        for(int i=1; idata)
               {
                   maxIndex = j;
                   Max = p->data;
               }
               q=p;
                p=p->link;
            }

            setData(maxIndex,q->data);
            setData(num,Max);
        }
	}
	void Inverse()//不要返回
	{
        int num = this->Length();
        for(int i=1; i * p = Locate(i);
            CirclinkNode* q = Locate(j);

            T temp = p->data;
            p->data = q->data;
            q->data = temp;
        }
	}
	void input(T endTag, InsMod im = INR)
	{
	    if(im==INR)
        {
        Insert(Length()+1,endTag);
        }
        else{
        Insert(1,endTag);
        }
	}
	void output()
	{
	    CirclinkNode* p =first->link;

	    while(p!=first)
        {
          cout<data<<" ";

          p=p->link;
        }
        cout< &operator = (CircList &L)
	{
	    this->makeEmpty();

    CirclinkNode* q =  L.first->link;
    while(q!=L.first)
    {
        input(q->data,INR);
        q=q->link;
    }

	}
	friend ostream& operator << (ostream &out, CircList &L){
		CirclinkNode *current = L.first->link;
		while (current != L.first){
			out << current->data <<'t';
			current = current->link;
		}
		out<> (istream &in, CircList &L){//重新输入数据，向后生成
		T val;
		L.makeEmpty();//先清空
		while (!in.eof()){
			in >> val;
			L.last->link = new CirclinkNode(val);
			assert(L.last->link);
			L.last = L.last->link;
		}
		L.last->link = L.first;
		in.clear();//当以ctrl_Z结束，流关闭，必须重新打开
		return in;
	}
protected:
	CirclinkNode *first, *last;
	void inputFront(T endTag);
	void inputRear(T endTag);
};


int main(){
	CircList list;
	ifstream fin("D:\cb代码\Data&Structure\list.txt");
	//assert(fin);
	fin >> list;
	cout << "The initial list in the file is:n" << list << endl;
	list.Inverse();
	cout << "Inverse the list, then the list is:n" << list << endl;

	cout << "========================================n";
	int i, elem;
	cout << "Test the Insert, Remove and Search function:n";
	cout << "Each test will terminate by an invaid input.";
	cout << "n----------------------------------------n";

	cout << "1. Test the Insert(int i, T &elem):n";
	while (1){
		cout << "Input the index i and data elem to insert: ";
		cin >> i >> elem;
		if (!cin){//流不正常

			cin.clear();//恢复正常
			cin.ignore(100,'n');
			break;
		}
		if (i < 0)	break;
		if (list.Insert(i, elem)) cout << "Insert successful!n";
		else	cout << "Insert failed!n";
	}
	cout << "nAfter insertedn" << list << endl;

	cout << "----------------------------------------n";
	cout << "2. Test the Remove(int i, T &elem):n";
	while (1){
		cout << "Input the index i in which you want to remove: ";
		cin >> i;
		if (!cin){
			cin.clear();
			cin.ignore(100,'n');
			break;
		}
		if (i < 0)	break;
		if (list.Remove(i, elem))	cout << "The element " << elem << " has been removed!n";
		else	cout << "Remove failed!n";
	}
	cout << "nAfter removedn" << list << endl;

	cout << "----------------------------------------n";
	cout << "3. Test the Search(T &elem):n";
	while (1){
		cout << "Input the element you want to search: ";
		cin >> elem;
		if (!cin){
			cin.clear();
			cin.ignore(100,'n');
			break;
		}
		if (elem < 0)	break;
		CirclinkNode *p = list.Search(elem);
		if (p)	cout << "The element " << elem << " is in the list.n";
		else cout << "The element is not exist!n";
	}
	cout << "n----------------------------------------n";
	cout << "End test!" << endl;
	return 0;
}
 
4、双向循环链表
 
#include 

using namespace std;

template
struct DoublelinkNode
{
      Type data;
      DoublelinkNode* llink;
      DoublelinkNode* rlink;
      DoublelinkNode(DoublelinkNode* pre=NULL,DoublelinkNode*suc=NULL)
      {
            llink=pre;
            rlink=suc;
      }
      DoublelinkNode(const Type& elem, DoublelinkNode* pre=NULL,DoublelinkNode* suc=NULL)
      {
            data=elem;
            llink=pre;
            rlink=suc;
      }
};
template
class CircleDoublelinkedList
{
private:
      DoublelinkNode* first;
public:
      CircleDoublelinkedList()
      {
          first = new DoublelinkNode();
          first->rlink = first;
          first->llink = first;
      }
      void MakeEmpty()
      {
          DoublelinkNode* p = first->rlink;
          DoublelinkNode* q = p;
          while(p->rlink!=first)
          {
              q = p->rlink;
              delete p;
              p = q;
          }

      }

      ~CircleDoublelinkedList()
      {
          this->MakeEmpty();
          delete first;
      }
      int Length()
      {
          int num=0;
          DoublelinkNode* p  = first->rlink;
          while(p!=first)
          {
              ++num;
              p=p->rlink;
          }
          return num;
      }
      void InputRear(const Type& elem)
      {
        Insert(Length()+1,elem,1);
      }
       void CopyList(const CircleDoublelinkedList& lst)
       {
           this->MakeEmpty();
           DoublelinkNode* p  = lst->first->rlink;

           DoublelinkNode* q = first->rlink;

           while(p!=first)
           {
               q = new DoublelinkNode(p->data);
               p=p->rlink;

               q=q->rlink;
           }
       }
      CircleDoublelinkedList(const CircleDoublelinkedList& lst)
      {
        DoublelinkNode* p  = lst->first->rlink;

        DoublelinkNode* q =  first->rlink;

           while(p!=first)
           {
               DoublelinkNode* newNode =  new DoublelinkNode(p->data,q->llink,q->rlink);
               p=p->rlink;
               q = newNode;
               q=q->rlink;
           }
      }
      CircleDoublelinkedList& operator=(const CircleDoublelinkedList& lst)
      {
          CopyList(lst);
          return *this;
      }
      DoublelinkNode* Locate(int loc, int sign)
      {
        if(loc<1||loc>Length()+1)
            exit(1);
        DoublelinkNode* p = first;
          int num=0;
          if(sign)
          {
              p=p->rlink;
              while(p!=first)
              {
                  ++num;
                  if(loc==num)
                    return p;
                  p=p->rlink;
              }
          }else
          {
                p=p->llink;
              while(p!=first)
              {
                  ++num;
                  if(loc==num)
                    return p;
                  p=p->llink;
              }
          }
          return p;
      }
      bool Insert(int loc, const Type& elem,int sign)
      {
          if(loc<1||loc>Length()+1)
            return false;

              DoublelinkNode* p = Locate(loc,sign);
              DoublelinkNode* newNode = new DoublelinkNode(elem);

              newNode->llink = p->llink;
              p->llink->rlink = newNode;
              newNode->rlink = p;
              p->llink = newNode;

        return true;

      }
      bool Remove(int loc, Type& elem, int sign)
      {
          DoublelinkNode* p = Locate(loc,sign);

          p->llink->rlink=p->rlink;
          p->rlink->llink = p->llink;
          delete p;
          return true;
      }
      DoublelinkNode* Search(const Type& elem, int sign) const
      {
          DoublelinkNode* p = first;
          if(sign)
          {
              p=p->rlink;

              while(p!=first)
              {
                if(p->data ==elem)
                    return p;
                    p=p->rlink;
              }
          }
          else
          {
              p=p->llink;
              while(p!=first)
              {
                if(p->data ==elem)
                        return p;
                p=p->llink;
              }
          }
      }
      bool GetData(int loc, Type& elem, int sign) const
      {
          if(loc<1)
            return false;
            DoublelinkNode* p = Locate(loc,sign);
            elem=p->data;
            return true;
      }
      bool SetData(int loc, const Type& elem, int sign)
      {
            if(loc<1)
            return false;
            DoublelinkNode* p = Locate(loc,sign);
            p->data=elem;
            return true;
      }
      void OutPut(int sign=0)
      {
          DoublelinkNode* p = first;
        if(sign)
        {
            p=p->rlink;
            while(p!=first)
            {
                cout<data<<" ";
                p=p->rlink;
            }
            cout<llink;
            while(p!=first)
            {
                cout<data<<" ";
                p=p->llink;
            }
            cout< lst;
    for(int i=1;i<=10;i++)
    {
          lst.Insert(i,i,1);
    }
    lst.OutPut(0);
    lst.OutPut(1);
    if(lst.Search(5,0))
    {
          cout<<"yes"<0;i--)
    {
          lst.Remove(i,val,1);
          lst.OutPut(0);
    }
    return 0;
}
 
5、静态链表
 
#ifndef STATICList_H
#define STATICList_H
#include 
#include 
using namespace std;

const int defaultSize = 100;
template struct SlinkNode{
	T data;
	int link;
};

template class StaticList{
	SlinkNode *elem;
	int maxSize;
	int avil;//可用结点链链首下标
	int *freeIndex;
public:
	StaticList(int sz = defaultSize)
	{
	    elem = new SlinkNode[sz];
	    freeIndex = new int[sz];
	    for(int i=0;iLength())
            return -1;
	    int pre = avil;
	    int num=0;
	    while(pre!=-1)
        {
            ++num;
            if(num==i)
                return pre;
            pre = elem[pre].link;
        }
        return -1;
	}
	bool getelem(int i, T &x)//获取第i个元素的值
	{
	    if(i<1||i>Length())
            return false;
        int num=0;
        int pre = avil;
        while(pre!=-1)
        {
            ++num;
            if(num==i)
            {
                x = elem[pre].data;
                return true;
            }
            pre=elem[pre].link;
        }
        return false;
	}
	bool Append(T x)         //在表尾添加新结点
	{
	    if(maxSize==Length())
            return false;
	    int pre=avil;
	    if(avil!=-1)
        {
	    while(elem[pre].link!=-1)
        {
            pre=elem[pre].link;
        }
        int i=0;
        for(;i0)
                {
                    cout<> (istream& in, StaticList &stl){
		T elem;
		while (!in.eof()){//在原链表后添加，与其他线性表不同
			in >> elem;
			stl.Append(elem);
		}
		return in;
	}
	friend ostream & operator<<(ostream &out, StaticList  &stl){
		int p = stl.elem[0].link;//elem[0]为附加头结点
		while(p != -1){
			cout << stl.elem[p].elem << endl;
			p = stl.elem[p].link;
		}
		cout << endl;
		return out;
	}
};


#endif
int main(){
	StaticList List(10);
	List.Append(25);
	List.Append(92);
	List.Append(57);
	List.Append(36);
	List.Append(78);
	List.Insert(3, 11);
	List.Insert(1, 49);

	// Print the List
	List.output();
	List.output(1);

	cout << "search 36: " << List.Search(36) << endl;
	cout << "search 25: " << List.Search(25) << endl;
	cout << "search 78: " << List.Search(78) << endl;
	cout << "search 50: " << List.Search(50) << endl;
	cout << endl;

	if (List.Remove(5)){
		cout << "Remove the 5th elem:n";
		List.output();
		List.output(1);
	}

	List.Append(11);
	cout << "After Insert 11 in the rear:n";
	List.output();
	List.output(1);
	return 0;
}

 
6、循环链表
 
#include 
#include 
 #include 
using namespace std;
enum InsMod {INF, INR};//头插还是尾插
template class CirclinkNode{
public:
	T data;
	CirclinkNode *link;
	CirclinkNode(CirclinkNode *ptr = NULL){//建立空结点
		link = ptr;
	}
	CirclinkNode(const T &item, CirclinkNode *ptr = NULL){//建立非空结点
		data = item;
		link = ptr;
	}
};

template class CircList{
public:
	CircList()
	{
	    this->first = new CirclinkNode();
	    first->link=first;

        last=first;
	}
	CircList(CircList &L)//复制一个环链表
	{
	    CirclinkNode* p = L.first->link;
	    CirclinkNode*q = this->first->link;
	    while(p!=first)
        {
            q= new CirclinkNode(p->data);
            q=q->link;
            p=p->link;
        }
        last = q;
	}
	~CircList()
	{
	    this->makeEmpty();
	    delete this->first;
	}
	void makeEmpty()
	{
	    CirclinkNode*p = this->first->link;
	    CirclinkNode*q = p->link;
	    while(p!=first)
        {
            delete p;
            p = q;
            q=q->link;
        }
	}
	int Length()const
	{
	    int num =0;
	    CirclinkNode* p = first->link;

	    while(p!=first)
        {
            ++num;
            p=p->link;
        }
        return num;
	}
	CirclinkNode *Search(T x)
	{
	    CirclinkNode* p = first->link;

	    while(p->data!=x)
        {
            p=p->link;
            if(p==first)
                exit(1);
        }
        return p;
	}
	CirclinkNode *Locate(int i)
	{
	    if(i<1||i>Length())
        {
            exit(1);
        }
        int num=0;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
                return p;
            p=p->link;
        }
        return p;
	}
	bool getData(int i,T&x)const
	{
	    if(i<1||i>Length())
        {
            return false;
        }
        int num=0;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
                x = p->data;
            p=p->link;
        }
        return true;
	}
	void setData(int i, T &x)
	{
	    if(i<1||i>Length())
        {
            return;
        }
        int num=0;
        CirclinkNode*p = first->link;
        while(p!=first)
        {
            ++num;
            if(num==i)
            p->data=x;
            p=p->link;
        }
	}
	bool Insert(int i, T &x)
	{
        if(i<1||i>Length()+1)
        {
            return false;
        }
        CirclinkNode* p =NULL;
        if(i==1)
            p = first;
        else
	     p = Locate(i-1);

	    CirclinkNode* q = p->link;

	    CirclinkNode *newNode = new CirclinkNode(x);

	    p->link = newNode;

	    newNode->link = q;
        if(i==Length()+1)
        {
        last = newNode;
        }
	    return true;

	}
	bool Remove(int i, T &x)
	{
        if(i<=0||i>Length())
        {
            return false;
        }
        int j=0;
        CirclinkNode* p = first;
        for(j=1; jlink;
        }
        CirclinkNode *q = p->link->link;
        x = p->link->data;
        if(i==Length())
            last = p;
        delete p->link;
        p->link = q;
        return true;
	}
	bool IsEmpty()const
	{
	    return first->link==last;
	}
	bool IsFull()const
	{
	    return (new CirclinkNode() )==NULL;
	}
	void Sort()
	{
        CirclinkNode * p =first->link;
        CirclinkNode *q=NULL;
        if(NULL==p)
            return ;

        int num = this->Length();
        int maxIndex=1;

        int Max =p->data;
        for(int i=1; idata)
               {
                   maxIndex = j;
                   Max = p->data;
               }
               q=p;
                p=p->link;
            }

            setData(maxIndex,q->data);
            setData(num,Max);
        }
	}
	void Inverse()//不要返回
	{
        int num = this->Length();
        for(int i=1; i * p = Locate(i);
            CirclinkNode* q = Locate(j);

            T temp = p->data;
            p->data = q->data;
            q->data = temp;
        }
	}
	void input(T endTag, InsMod im = INR)
	{
	    if(im==INR)
        {
        Insert(Length()+1,endTag);
        }
        else{
        Insert(1,endTag);
        }
	}
	void output()
	{
	    CirclinkNode* p =first->link;

	    while(p!=first)
        {
          cout<data<<" ";

          p=p->link;
        }
        cout< &operator = (CircList &L)
	{
	    this->makeEmpty();

    CirclinkNode* q =  L.first->link;
    while(q!=L.first)
    {
        input(q->data,INR);
        q=q->link;
    }

	}
	friend ostream& operator << (ostream &out, CircList &L){
		CirclinkNode *current = L.first->link;
		while (current != L.first){
			out << current->data <<'t';
			current = current->link;
		}
		out<> (istream &in, CircList &L){//重新输入数据，向后生成
		T val;
		L.makeEmpty();//先清空
		while (!in.eof()){
			in >> val;
			L.last->link = new CirclinkNode(val);
			assert(L.last->link);
			L.last = L.last->link;
		}
		L.last->link = L.first;
		in.clear();//当以ctrl_Z结束，流关闭，必须重新打开
		return in;
	}
protected:
	CirclinkNode *first, *last;
	void inputFront(T endTag);
	void inputRear(T endTag);
};


int main(){
	CircList list;
	ifstream fin("D:\cb代码\Data&Structure\list.txt");
	//assert(fin);
	fin >> list;
	cout << "The initial list in the file is:n" << list << endl;
	list.Inverse();
	cout << "Inverse the list, then the list is:n" << list << endl;

	cout << "========================================n";
	int i, elem;
	cout << "Test the Insert, Remove and Search function:n";
	cout << "Each test will terminate by an invaid input.";
	cout << "n----------------------------------------n";

	cout << "1. Test the Insert(int i, T &elem):n";
	while (1){
		cout << "Input the index i and data elem to insert: ";
		cin >> i >> elem;
		if (!cin){//流不正常

			cin.clear();//恢复正常
			cin.ignore(100,'n');
			break;
		}
		if (i < 0)	break;
		if (list.Insert(i, elem)) cout << "Insert successful!n";
		else	cout << "Insert failed!n";
	}
	cout << "nAfter insertedn" << list << endl;

	cout << "----------------------------------------n";
	cout << "2. Test the Remove(int i, T &elem):n";
	while (1){
		cout << "Input the index i in which you want to remove: ";
		cin >> i;
		if (!cin){
			cin.clear();
			cin.ignore(100,'n');
			break;
		}
		if (i < 0)	break;
		if (list.Remove(i, elem))	cout << "The element " << elem << " has been removed!n";
		else	cout << "Remove failed!n";
	}
	cout << "nAfter removedn" << list << endl;

	cout << "----------------------------------------n";
	cout << "3. Test the Search(T &elem):n";
	while (1){
		cout << "Input the element you want to search: ";
		cin >> elem;
		if (!cin){
			cin.clear();
			cin.ignore(100,'n');
			break;
		}
		if (elem < 0)	break;
		CirclinkNode *p = list.Search(elem);
		if (p)	cout << "The element " << elem << " is in the list.n";
		else cout << "The element is not exist!n";
	}
	cout << "n----------------------------------------n";
	cout << "End test!" << endl;
	return 0;
}
 
7、双向循环链表
 
#include 

using namespace std;

template
struct DoublelinkNode
{
      Type data;
      DoublelinkNode* llink;
      DoublelinkNode* rlink;
      DoublelinkNode(DoublelinkNode* pre=NULL,DoublelinkNode*suc=NULL)
      {
            llink=pre;
            rlink=suc;
      }
      DoublelinkNode(const Type& elem, DoublelinkNode* pre=NULL,DoublelinkNode* suc=NULL)
      {
            data=elem;
            llink=pre;
            rlink=suc;
      }
};
template
class CircleDoublelinkedList
{
private:
      DoublelinkNode* first;
public:
      CircleDoublelinkedList()
      {
          first = new DoublelinkNode();
          first->rlink = first;
          first->llink = first;
      }
      void MakeEmpty()
      {
          DoublelinkNode* p = first->rlink;
          DoublelinkNode* q = p;
          while(p->rlink!=first)
          {
              q = p->rlink;
              delete p;
              p = q;
          }

      }

      ~CircleDoublelinkedList()
      {
          this->MakeEmpty();
          delete first;
      }
      int Length()
      {
          int num=0;
          DoublelinkNode* p  = first->rlink;
          while(p!=first)
          {
              ++num;
              p=p->rlink;
          }
          return num;
      }
      void InputRear(const Type& elem)
      {
        Insert(Length()+1,elem,1);
      }
       void CopyList(const CircleDoublelinkedList& lst)
       {
           this->MakeEmpty();
           DoublelinkNode* p  = lst->first->rlink;

           DoublelinkNode* q = first->rlink;

           while(p!=first)
           {
               q = new DoublelinkNode(p->data);
               p=p->rlink;

               q=q->rlink;
           }
       }
      CircleDoublelinkedList(const CircleDoublelinkedList& lst)
      {
        DoublelinkNode* p  = lst->first->rlink;

        DoublelinkNode* q =  first->rlink;

           while(p!=first)
           {
               DoublelinkNode* newNode =  new DoublelinkNode(p->data,q->llink,q->rlink);
               p=p->rlink;
               q = newNode;
               q=q->rlink;
           }
      }
      CircleDoublelinkedList& operator=(const CircleDoublelinkedList& lst)
      {
          CopyList(lst);
          return *this;
      }
      DoublelinkNode* Locate(int loc, int sign)
      {
        if(loc<1||loc>Length()+1)
            exit(1);
        DoublelinkNode* p = first;
          int num=0;
          if(sign)
          {
              p=p->rlink;
              while(p!=first)
              {
                  ++num;
                  if(loc==num)
                    return p;
                  p=p->rlink;
              }
          }else
          {
                p=p->llink;
              while(p!=first)
              {
                  ++num;
                  if(loc==num)
                    return p;
                  p=p->llink;
              }
          }
          return p;
      }
      bool Insert(int loc, const Type& elem,int sign)
      {
          if(loc<1||loc>Length()+1)
            return false;

              DoublelinkNode* p = Locate(loc,sign);
              DoublelinkNode* newNode = new DoublelinkNode(elem);

              newNode->llink = p->llink;
              p->llink->rlink = newNode;
              newNode->rlink = p;
              p->llink = newNode;

        return true;

      }
      bool Remove(int loc, Type& elem, int sign)
      {
          DoublelinkNode* p = Locate(loc,sign);

          p->llink->rlink=p->rlink;
          p->rlink->llink = p->llink;
          delete p;
          return true;
      }
      DoublelinkNode* Search(const Type& elem, int sign) const
      {
          DoublelinkNode* p = first;
          if(sign)
          {
              p=p->rlink;

              while(p!=first)
              {
                if(p->data ==elem)
                    return p;
                    p=p->rlink;
              }
          }
          else
          {
              p=p->llink;
              while(p!=first)
              {
                if(p->data ==elem)
                        return p;
                p=p->llink;
              }
          }
      }
      bool GetData(int loc, Type& elem, int sign) const
      {
          if(loc<1)
            return false;
            DoublelinkNode* p = Locate(loc,sign);
            elem=p->data;
            return true;
      }
      bool SetData(int loc, const Type& elem, int sign)
      {
            if(loc<1)
            return false;
            DoublelinkNode* p = Locate(loc,sign);
            p->data=elem;
            return true;
      }
      void OutPut(int sign=0)
      {
          DoublelinkNode* p = first;
        if(sign)
        {
            p=p->rlink;
            while(p!=first)
            {
                cout<data<<" ";
                p=p->rlink;
            }
            cout<llink;
            while(p!=first)
            {
                cout<data<<" ";
                p=p->llink;
            }
            cout< lst;
    for(int i=1;i<=10;i++)
    {
          lst.Insert(i,i,1);
    }
    lst.OutPut(0);
    lst.OutPut(1);
    if(lst.Search(5,0))
    {
          cout<<"yes"<0;i--)
    {
          lst.Remove(i,val,1);
          lst.OutPut(0);
    }
    return 0;
}