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 linkList:public list /公有继承自list类 public: linkList(); /构造函数，创建对象时生成空链表 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(); /将表中的元素逐一输出 linkList(); /析构函数 private: /定义节点 struct node dataType data; node* next; node():next(NULL); node(dataType d):data(d),next(NULL); ; node* head; /链表头 node* tail; /链表尾 int currentLength; /链表长度;/*单链表类的实现*/#include using namespace std;template linkList:linkList() head=new node; tail=new node; head-next=tail; currentLength=0; coutnCreate list success!n;template void linkList:empty() node* nowPos=head-next; while(nowPos!=tail) node* tmp=nowPos; nowPos=nowPos-next; delete tmp; head-next=tail; currentLength=0; coutnEmpty list success!n;template int linkList:getLength() return currentLength;template void linkList:insert(int i,const dataType& x) if(icurrentLength) coutnext=head-next; head-next=add; else /找到第i-1个节点 node* nowPos=head-next; while(-i) nowPos=nowPos-next; add-next=nowPos-next; nowPos-next=add; +currentLength; coutnInsert data success!n;template void linkList:remove(int i) if(i=currentLength) coutnext-next; delete head-next; head-next=tmp; else /找到第i-1个节点 node* nowPos=head-next; while(-i) nowPos=nowPos-next; node* tmp=nowPos-next-next; delete nowPos-next; nowPos-next=tmp; -currentLength; coutnDelete data success!n;template int linkList: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 linkList:visit(int i) /下标越界抛出异常值0 if(i=currentLength) throw 0; /找到第i个节点 node* nowPos=head-next; while(i-) nowPos=nowPos-next; return nowPos-data;template void linkList:traverse() if(currentLength=0) coutnext; coutdata; nowPos=nowPos-next; while(nowPos!=tail) cout data; nowPos=nowPos-next; coutendl;template linkList:linkList() 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、所有的类都是模版类，如果想把模版类的定义与实现分离要注意，模版类的实现不能放在.cpp