数据结构实验之单链表的创建

《数据结构实验之单链表的创建》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验四:单链表的创建［实验题目］首先建立一个单链表，然后建立主程序测试：将1T0个整数放入这个链表，从键盘上任意输入一个整数，判断这个整数是否在链表内，然后再将链表内所以数据输出出来。［概要分析］建一个LinearList类的头文件LinearList.h,将相应的方法设虚写在public中，再建一个子类SingleList类的头文件SingleList,h将其父类的方法具体实现，最后再建立主程序测试即可。［详细设计］1.类的结构classClassModelT:classNode+element:T+link:Node

2、*T:classSingleListfirst:Node*+Delete(int):bool+Find(int,T&):bool{query}+lnsert(inttT):bool+IsEmptyO:bool{query}+Length():int{query}+Output(ostream&):void{query}+Search(T):int{query}+SingleList()+~SingleList()+Update(intfT):boolT:classLinearList#n:int+Delete(int):

3、bool+Find(int9T&):bool{query}+lnsert(int9T):bool+IsEmptyO:bool{query}+Length():int{query}+Output(ostrearr)&丿:void{query}+Search(T):int{query}+Update(intfT):bool电子二班1305012035马璐瑶2.核心代码(1)插入思路:范围不对不能插入if(i<-l

4、

5、i>n-l){returnfalse;}正常插入时找到第i个结点for(intj=O;jl

6、ink;J①在表头插入：if(i==-1){t->link=first;first=t;}②在表中插入:if(i>-l){t->link=p->link;p->link=t;}最后不要忘记了总的长度加一：n++;具体代码：templateboolSingleList::Insert(inti,Tx){Node*p=first,*t;t=newNode;t->clcmcnt=x;t->link=NULL;if(i<-l

7、

8、i>n-l){returnfalse;}for(intj=O;j

9、+){p=p->link;}if(i==-l){t->link=first;first=t;}else{t->link=p->link;p->link=t;}n++;returntrue;}(2)删除思路:为空不能删if(IsEmpty()){returnfalse;}范围不对不能删if(i<()

10、

11、i>n-l){returnfalse;}正常删除先找至ljq的位置for(intj=O;jlink;}①在表头删除:if(i==0){first=first->link;deletep;}②在表中删除

12、:if(i>0){p=q->link;q->link=p->link;deletep;}最后不耍忘记了总的长度加一：n-・；具体代码：templateboolSingleList::Delete(inti)Nodc*p=first,*q=first;if(IsEmptyO)returnfalse;}if(i<()

13、

14、i>n-l){returnfalse;}for(intj=O;jlink;}if(i==0){first=first->link;deletep;}else

15、{p=q->link;q->link=p->link;deletep;}n・・；returntrue;}［程序代码］l.LinearList.h#ifndefLinearList_h#defineLinearList_h#includetemplateclassLinearList{public:virtualboolIsEmptyOconst=0;virtualintLength()const=0;virtualboolFind(inti,T&x)const=0;virtualintS

16、earch(Tx)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostrcam&out)const=0