C++实现双链表(模版类).doc

C+模版类实现双链表先上代码/*线性表抽象类的定义*/template class list public: virtual void empty()=0; /清空线性表 virtual int getLength()=0; /求表的长度 virtual void insert(int i,const dataType& x)=0; /在表中第i个位置插入值为x的元素 virtual void remove(int i)=0; /删除表中第i个位置的元素 virtual int search(const dataType& x)=0; /查找并返回值为x的元素在表中的位置 virtual dataType visit(int i)=0; /访问表中第i个元素的值 virtual void traverse()=0; /遍历线性表;/*双链表类的定义*/#include list.htemplate class dLinkList:public list /公有继承自list类 public: dLinkList(); /构造函数，创建对象时生成空链表 void empty(); /清空链表（除头尾节点以外） int getLength(); /求链表的长度 void insert(int i,const dataType& x); /在表中第i个位置插入值为x的元素 void remove(int i); /删除表中第i个节点 int search(const dataType& x); /查找并返回值为x的元素在表中的位置 dataType visit(int i); /访问表中第i个元素的值 void traverse(); /将表中的元素逐一输出 dLinkList(); /析构函数 private: /定义节点 struct node dataType data; /节点中保存的数据 node* prior; /节点的前驱 node* next; /节点的后继 node():prior(NULL),next(NULL); /构造函数 node(dataType d):data(d),prior(NULL),next(NULL); /构造函数 ; node* head; /链表头 node* tail; /链表尾 int currentLength; /链表长度;/*双链表类的实现*/#include using namespace std;template dLinkList:dLinkList() head=new node; tail=new node; head-prior=NULL,head-next=tail; tail-prior=head; currentLength=0; coutnCreate list success!n;template void dLinkList:empty() node* nowPos=head-next; while(nowPos!=tail) node* tmp=nowPos; nowPos=nowPos-next; delete tmp; head-next=tail; tail-prior=head; currentLength=0; coutnEmpty list success!n;template int dLinkList:getLength() return currentLength;template void dLinkList:insert(int i,const dataType& x) if(icurrentLength) coutnext=head-next,head-next-prior=add; add-prior=head,head-next=add; else /找到第i-1个节点 node* nowPos=head-next; while(-i) nowPos=nowPos-next; add-prior=nowPos,add-next=nowPos-next; nowPos-next-prior=add,nowPos-next=add; +currentLength; coutnInsert data success!n;template void dLinkList:remove(int i) if(i=currentLength) coutnext; while(i-) nowPos=nowPos-next; nowPos-prior-next=nowPos-next; nowPos-next-prior=nowPos-prior; delete nowPos; -currentLength; coutnDelete data success!n;template int dLinkList:search(const dataType& x) node* nowPos=head; int i; for(i=0;inext; if(nowPos-data=x) break; if(i=currentLength) return -1; return i;template dataType dLinkList:visit(int i) /i越界时抛出异常值0 if(i=currentLength) throw 0; /找到第i个节点 node* nowPos=head-next; while(i-) nowPos=nowPos-next; return nowPos-data;template void dLinkList:traverse() if(currentLength=0) coutnext; coutdata; nowPos=nowPos-next; while(nowPos!=tail) cout data; nowPos=nowPos-next; coutendl;template dLinkList:dLinkList() empty(); delete head; delete tail;注意1、这段代码是从线性表工程包里抽出来的，有必要可以去这里下载，工程包的内容如下：list.h-线性表抽象类的定义seqList.h-顺序表类的定义seqList.txt-顺序表类的实现linkList.h-单链表类的定义linkList.txt-单链表类的实现dLinkList.h-双链表类的定义dLinkList.txt-双链表类的实现test.h -测试类的定义test.txt-测试类的实现2、大家可以把这些代码作为参考，想要提高能力还是要自己写的；3、所有的类都是模版类，如果想把模版类的定义与实现分离要注意，模版类的实现