算法与数据结构---单链表的创建.doc

《算法与数据结构---单链表的创建.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》实验报告实验题目：线性表的单链表实现任课教师：学号：姓名：完成日期：需求和规格说明线性表基本操作在单链表上的实现，包括：•（1）创建单链表；•（2）在单链表上查找第i个数据结点，返回其data值；•（3）在单链表第i个位置上插入一个取值为value的新的数据结点；•（4）删除单链表第i个数据结点，并返回该数据结点的取值；•（5）求单链表的长度。•（6）有余力的同学可完成教材单链表定义中的其它功能。测试数据:•（1）线性表中数据元素的取值集合为{1，2，3，4，5，6，7，8}；或线性表中数据元素的取值集合为

2、{1.0，3.0，5.0，6.0，7.0，8.0}，•（2）给出在单链表实现时(a)查找第4个数据结点；(b)在第3个位置插入value=9/9.0；(c)删除第4个数据结点；（d)给出单链表的长度。第9页共9页二.设计2.1算法描述classlink{public:Tdata;link*next;link(constTinfo,link*constnextValue=NULL){data=info;next=nextValue;}link(link*constnextValue=NULL){next=ne

3、xtValue;}};templateclasslnklist{link*head,*tail;public:lnklist(){head=tail=newlink;}voidcreatelist(intn){Tdata;for(inti=0;i>data;insert(i,data);}}link*setpos(inti){intcount=0;if(i==-1)returnhead;link*p=head->next;while(p!=NULL&&count

4、next;count++;}returnp;}boolinsert(constinti,constTvalue){link*p,*q;if((p=setpos(i-1))==NULL){cout<<"非法插入"<(value,p->next);p->next=q;if(p==tail)tail=q;returntrue;}boolDelete(constinti){link*p,*q;if((p=setpos(i-2))==NULL

5、

6、

7、p==tail){cout<<"非法删除"<next;if(q==tail){tail=p;p->next=NULL;deleteq;}elseif(q!=NULL){p->next=q->next;deleteq;}returntrue;}intlength(){intcount=0;link*p=head->next;while(p){p=p->next;count++;}returncount;}voidshow(){link*p;p=head->next;

8、while(p){cout<data;p=p->next;}cout<>data;insert(i,data);}}link*setpos(inti){intcount=0;if(i==-1)returnhead;link*p=head->next;while(p!=NULL&&countnext;count++;}returnp;}boolinsert(constinti,constTvalue){link*p,*q;if((p=setpo

9、s(i-1))==NULL){cout<<"非法插入"<(value,p->next);p->next=q;if(p==tail)tail=q;returntrue;}第9页共9页returntrue;}boolDelete(constintI,T&value){link*p,*q;if((p=setpos(i-2))==NULL

10、

11、p==tail){cout<<"非法删除"<next;if(q==tail){

12、tail=p;value=q->data;cout<next=NULL;deleteq;}elseif(q!=NULL){p->next=q->next;value=q->data;cout<