C++实现单链表(模版类).doc
如有侵权，请联系网站删除，仅供学习与交流C+实现单链表(模版类)【精品文档】第 5 页C+模版类实现单链表先上代码/*线性表抽象类的定义*/template <class dataType>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.h"template <class dataType>class linkList:public list<dataType> /公有继承自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 <iostream>using namespace std;template <class dataType>linkList<dataType>:linkList() head=new node; tail=new node; head->next=tail; currentLength=0; cout<<"nCreate list success!n"template <class dataType>void linkList<dataType>:empty() node* nowPos=head->next; while(nowPos!=tail) node* tmp=nowPos; nowPos=nowPos->next; delete tmp; head->next=tail; currentLength=0; cout<<"nEmpty list success!n"template <class dataType>int linkList<dataType>:getLength() return currentLength;template <class dataType>void linkList<dataType>:insert(int i,const dataType& x) if(i<0|i>currentLength) cout<<"nThe index is out of range!n" return; node* add=new node(x); if(i=0) add->next=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; cout<<"nInsert data success!n"template <class dataType>void linkList<dataType>:remove(int i) if(i<0|i>=currentLength) cout<<"nThe index is out of range!n" return; if(i=0) node* tmp=head->next->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; cout<<"nDelete data success!n"template <class dataType>int linkList<dataType>:search(const dataType& x) node* nowPos=head; int i; for(i=0;i<currentLength;+i) nowPos=nowPos->next; if(nowPos->data=x) break; if(i=currentLength) return -1; return i;template <class dataType>dataType linkList<dataType>:visit(int i) /下标越界抛出异常值0 if(i<0|i>=currentLength) throw 0; /找到第i个节点 node* nowPos=head->next; while(i-) nowPos=nowPos->next; return nowPos->data;template <class dataType>void linkList<dataType>:traverse() if(currentLength=0) cout<<"nThe list is empty!n" return; node* nowPos=head->next; cout<<nowPos->data; nowPos=nowPos->next; while(nowPos!=tail) cout<<" "<<nowPos->data; nowPos=nowPos->next; cout<<endl;template <class dataType>linkList<dataType>: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文件里，只能放在.txt文件里；4、涉及的知识主要分为三大方面：（1）单链表的实现原理；（2）类的设计、封装；（3）设计抽象类list并让单链表继承自list，是为了和顺序表、双链表配合，利用（纯）虚函数实现多态。如果只用到单链表您可以自己设计一个类解决，也可以直接用上面的代码。
