链表和顺序表的实现c++版（绝对能用）

最近在重新复习C++基础知识点，复习到链表和顺序表，把之前的代码整理出来给大家参考；

 

我的注释算是比较详细的，所以就不做过多解释了；

 

贴代码的话只把具体实现贴出来，如果想要完整代码的我已经提供下载链接了哦，希望对大家有帮助：

 

首先是纯虚函数，两个表都继承此函数：headlist.h

#ifndef LISTHEAD_H

#defineLISTHEAD_H

 

#include<iostream>

usingnamespace std;

template <classElem> classlisthead{

public:

      virtualvoidclear() = 0;

      virtualboolinsert(Elem&,int i) = 0;

      virtualboolappend(Elem&) = 0;

      virtualboolremove(Elem&) = 0;

      virtualvoidsetStart() = 0;

      virtualvoidsetEnd() = 0;

      virtualvoidprev() = 0;

      virtualvoidnext() = 0;

      virtualintleftLength() const = 0;

      virtualintrightLength() const = 0;

      virtualboolsetPos(int pos) = 0;

      virtualboolgetValue(Elem&) const = 0;

      virtualvoidprint() const = 0;

};

#endif

 

顺序表实现：

//顺序表：

#ifndef ALIST_H

#defineALIST_H

#include"listhead.h"

#include"Link.h"

template <classElem> classAlist : publiclisthead<Elem>

{

private:

      int maxSize;

      int listSize;

      int fence;

      Elem* listArray;

 

public:

      Alist(int size);

      ~Alist();

      boolchangeMaxSize(int newMaxsize);//改变顺序表最大长度

      boolinsert(Elem& it, int num);//插入元素

      boolappend(Elem& item);//在末端添加元素

      boolremove(Elem& item);//删除元素

      voidsetStart();//将栅栏放置在开始处

      voidsetEnd();//将栅栏放置在末端

      voidprev();//栅栏前移

      voidnext();//栅栏后移

      voidclear();//清空队列

      intleftLength() const;

      intrightLength() const;

      boolsetPos(int pos);

      boolgetValue(Elem& it) const;

      voidprint() const;//打印

      voidreverlist();//逆置

};

 

      template<classElem>

      Alist<Elem>::Alist(intsize){

           maxSize = size;

           listSize = fence = 0;

           listArray = newElem[maxSize];

      }

      template<classElem>

      Alist<Elem>::~Alist(){

           delete[] listArray;

           listSize = fence = 0;

           listArray = newElem[maxSize];

      }

      template<classElem>

      boolAlist<Elem>::changeMaxSize(intnewMaxsize){

           Elem* newlistArray;

           newlistArray = new  Elem[newMaxsize];

           for (int i = 0; i < newMaxsize; i++){

                 newlistArray[i] = listArray[i];

           }

           listArray = newlistArray;

           if (listSize>newMaxsize){

                 listSize = newMaxsize;

 

            }

           if (fence > listSize){

                 fence = listSize;

           }

           maxSize = newMaxsize;

//         delete[] newlistArray;

           returntrue;

      }

      template<classElem>

      boolAlist<Elem>::insert(Elem& it, intnum){

           if (listSize == maxSize || num<0 || num > listSize){

                 returnfalse;

           }

           else

           {

                 for (int i = listSize; i > num; i--){

                      listArray[i] = listArray[i - 1];

                 }

                 listArray[num] = it;

                 listSize++;

                 fence = num;

                 returntrue;

           }

      }

      template<classElem>

      boolAlist<Elem>::append(Elem& item){

           if (listSize == maxSize){

                 returnfalse;

           }

           listArray[listSize++] = item;

           returntrue;

      }

 

      template<classElem>

      boolAlist<Elem>::remove(Elem& item){

           if (rightLength() == 0){

                 returnfalse;

           }

           for (int i = 0; i < listSize; i++){

                 if (listArray[i] == item){

                      fence = i;

                      break;

                 }

           }

           item = listArray[fence];

           for (int i = fence; i<listSize - 1; i++){

                 listArray[i] = listArray[i + 1];

           }

           listSize--;

           returntrue;

      }

      template<classElem>

      voidAlist<Elem>::setStart(){

           fence = 0;

      }

      template<classElem>

      voidAlist<Elem>::setEnd(){

           fence = listSize;

      }

      template<classElem>

      voidAlist<Elem>::prev(){

           if (fence != 0)

                 fence--;

      }

      template<classElem>

      voidAlist<Elem>::next(){

           if (fence <= listSize - 1)

                 fence++;

      }

      template<classElem>

      intAlist<Elem>::leftLength() const{

           return fence;

      }

      template<classElem>

      intAlist<Elem>::rightLength() const{

           return listSize - fence;

      }

      template<classElem>

      boolAlist<Elem>::setPos(intpos){

           if ((pos >= 0) && (pos <= listSize)){

                 fence = pos;

           }

           return (pos >= 0) && (pos <= listSize);

      }

      template<classElem>

      boolAlist<Elem>::getValue(Elem& it) const{

           if (rightLength() == 0) returnfalse;

           else

           {

                 it = listArray[fence]; returntrue;

           }

      }

      template<classElem>

      voidAlist<Elem>::print() const

      {

           int temp = 0;

           cout << "<";

           while (temp<fence){ cout << listArray[temp++] << " "; }

           cout << " | ";

          

           while (temp<listSize){ cout << listArray[temp++] << " "; }

           cout << " \n";

           cout << listSize << " "<<fence<<endl;

      }

      template<classElem>

      voidAlist<Elem>::reverlist(){

           int i;

           for (i = 0; i<listSize / 2; i++){

                 listArray[listSize + 1] = listArray[i];

                 listArray[i] = listArray[listSize - i - 1];

                 listArray[listSize - i - 1] = listArray[listSize + 1];

           }

      }

      //删除列表中的数据

      template<classElem>

      void  Alist<Elem>::clear(){

      }

#endif

 

链表实现：

//节点

#ifndef LINK_H

#defineLINK_H

#include"listhead.h"

template <classElem> classLink{

public:

      Elem element;//节点元素

      Link *next;//指向下一个元素

      Link(constElem& elemval,Link* nextval =NULL){

      element = elemval;next = nextval;

      }

    Link(Link* nextval =NULL){

      next = nextval;

      }

};

#endif

 

#ifndef ALIST_L

#defineALIS_L

#include"listhead.h"

template<classElem> classLList:publiclisthead<Elem>{

private:

      Link<Elem> *head;//头节点（不存数据）

      Link<Elem> *tail;//尾节点

      Link<Elem> *fence;//栅栏

      int leftcnt;

      int rightcnt;

      int size;//链表长度

      voidinit(){//初始化

           fence = tail = head = newLink<Elem>;

           leftcnt = rightcnt = 0;

           size = 1;

      }

      voidremoveall(){//清空所有

           while (head != NULL)

           {

                 fence = head;

                 head = head->next;

                 delete fence;

           }

      }

public:

      LList( intsize = DefaultListSize){

           init();

      }

      ~LList(){

           removeall();

      }

      voidclear(){

           removeall();init();

      }

      boolinsert(Elem&,int i);

      boolappend(Elem&);

      boolremove(Elem&);

      voidsetStart(){

           fence = head;

           rightcnt +=leftcnt;

           leftcnt = 0;

      }

      voidsetEnd(){

           fence = tail;

           leftcnt += rightcnt;

           rightcnt = 0;

      }

      voidprev();//前驱

      voidnext(){//后继

           if(fence!=tail){

                 fence =fence ->next;rightcnt--;leftcnt++;

           }

      }

      intleftLength() const{return leftcnt;}

      intrightLength() const{return rightcnt;}

      boolsetPos(int pos);

      boolgetValue(Elem& it) const{

           if(rightLength()==0)returnfalse;

           it = fence->next->element;

           returntrue;

      }

      voidprint() const;

    voidreverlist();//逆置

};

template<classElem>

boolLList<Elem>::insert(Elem& item, inti){//插入操作

      if (i<1||i>size){

           returnfalse;

      }

      else{

           int n = 0;

           Link<Elem>*  temp = head;

           while(n<i-1){

                 temp = temp->next;

                 n++;

           }

           temp->next = newLink<Elem>(item, temp->next);

           size++;

           returntrue;

      }

 

}

template<classElem>

boolLList<Elem>::append(Elem& item){//添加在末端

      tail = tail ->next = newLink<Elem>(item,NULL);

      rightcnt++;

      size++;

      returntrue;

}

template<classElem>

boolLList<Elem>::remove(Elem& it){//删除某元素

      bool del = false;

      Link<Elem>*  temp = head;

      while(temp->next!=NULL){

           if (temp->next->element == it){

                 temp->next = temp->next->next;

                 del = true;

                 leftcnt--;

                 size--;

           }

           else{

                 temp = temp->next;

           }

 

      }

      return del;

}

template<classElem>

voidLList<Elem>::prev(){

      Link<Elem>*  temp = head;

      if(fence == head) return;

      while (temp->next!=fence) temp = temp->next;

      fence = temp;

      leftcnt--; rightcnt++;

}

template<classElem> boolLList<Elem>::setPos(intpos){

      if((pos<0)||(pos>rightcnt+leftcnt)) returnfalse;

      fence = head;

      for(int i=0;i<pos;i++){

           fence = fence->next;

      }

      returntrue;

}

template<classElem>

voidLList<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 ";

}

template <class  Elem>

voidLList<Elem>::reverlist()

{

Link<Elem>* p,*q;

p=head->next;

head->next=NULL;//链式线性表分为两部分

while(p!=NULL){

q=p;

p=p->next;

q->next=head->next;

head->next=q;

}

}

#endif