最近在重新复习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
?
原文：http://448230305.iteye.com/blog/2192197