鏈表的基本操作-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)第(四)次實(shí)驗(yàn)實(shí)驗(yàn)名稱鏈表的根本操作學(xué)生姓名于歌專業(yè)班級(jí)學(xué)號(hào)實(shí)驗(yàn)成績指導(dǎo)老師(簽名)日期2021年10月01日一、實(shí)驗(yàn)?zāi)康? .學(xué)會(huì)定義單鏈表的結(jié)點(diǎn)類型,實(shí)現(xiàn)對(duì)單鏈表的一些根本操作和具體的函數(shù)定義,了解并掌握單鏈表的類定義以及成員函數(shù)的定義與調(diào)用.2 .掌握單鏈表根本操作及兩個(gè)有序表歸并、單鏈表逆置等操作的實(shí)現(xiàn).二、實(shí)驗(yàn)要求1 .預(yù)習(xí)C語言中結(jié)構(gòu)體的定義與根本操作方法.2 .對(duì)單鏈表的每個(gè)根本操作用單獨(dú)的函數(shù)實(shí)現(xiàn).3 .編寫完整程序完成下面的實(shí)驗(yàn)內(nèi)容并上機(jī)運(yùn)行.4 .整理并上交實(shí)驗(yàn)報(bào)告.三、實(shí)驗(yàn)內(nèi)容：1.編寫程序完成單鏈表的以下根本操作：(1)初始化單鏈

2、表La(2)在La中插入一個(gè)新結(jié)點(diǎn)(3)刪除La中的某一個(gè)結(jié)點(diǎn)(4)在La中查找某結(jié)點(diǎn)并返回其位置(5)打印輸出La中的結(jié)點(diǎn)元素值(6)清空鏈表(7)銷毀鏈表2構(gòu)造兩個(gè)帶有表頭結(jié)點(diǎn)的有序單鏈表La、Lb,編寫程序?qū)崿F(xiàn)將La、Lb合并成一個(gè)有序單鏈表Lco四、思考與提升：1 .如果上面實(shí)驗(yàn)內(nèi)容2中合并的表內(nèi)不允許有重復(fù)的數(shù)據(jù)該如何操作？2 .如何將一個(gè)帶頭結(jié)點(diǎn)的單鏈表La分解成兩個(gè)同樣結(jié)構(gòu)的單鏈表Lb,Lc,使得Lb中只含La表中奇數(shù)結(jié)點(diǎn),Lc中含有La表的偶數(shù)結(jié)點(diǎn)？五、實(shí)驗(yàn)設(shè)計(jì)1.編寫程序完成單鏈表的以下根本操作：(1)初始化單鏈表LaLinkListInitList()(inti,value

3、,n;LinkListH=(LinkList)malloc(sizeof(LNode);LinkListP=H;P->next=NULL;doprintf("請(qǐng)輸入鏈表的長度:");scanf("%d",&n);if(n<=0)printf("輸入有誤請(qǐng)重新輸入！n");while(n<=0);printf("請(qǐng)輸入各個(gè)元素:n");for(i=0;i<n;i+)scanf("%d",&value);LinkListNEW=(LinkList)malloc

4、(sizeof(LNode);NEW->data=value;P->next=NEW;NEW->next=NULL;P=NEW;printf("鏈表建立成功！n");returnH->next;(2)在La中插入一個(gè)新結(jié)點(diǎn)LinkListInsertList(LinkListL,inti,ElemTypevalue)LinkListh,q,t=NewLNode(t,value);intx=0;h=q=L;if(i=1)t->next=h,h=t;elsewhile(x+<i-2)q=q->next;t->next=q->

5、next;q->next=t;printf("插入成功！n");returnh;(3)刪除La中的某一個(gè)結(jié)點(diǎn)LinkListDeleteList(LinkListL,inti)(LinkListh,q,de;intx=0;h=q=L;intt;if(i=1)h=h->next;else(while(x+<i-2)q=q->next;de=q->next;if(de->next=NULL)q->next=NULL;elseq->next=de->next;printf("刪除成功！n");returnh

6、;(4)在La中查找某結(jié)點(diǎn)并返回其位置StatusLocateList(LinkListL,ElemTypevalue)(LinkListq=L;inti=0,t;while(q!=NULL)(i+;if(q->data=value)(printf("該結(jié)點(diǎn)在鏈表中的位置為第d4Vn",i);returnOK;q=q->next;printf("該鏈表中沒有該結(jié)點(diǎn)！n");returnERROR;(5)打印輸出La中的結(jié)點(diǎn)元素值StatusPrint(LinkListL)(LinkListq=L;printf("該鏈表的每個(gè)元素為:

7、n");while(q!=NULL)(printf("%8d",q->data);q=q->next;printf("n");returnOK;(6)清空鏈表LinkListEmptyList(LinkListL)(free(L->data);L->next=NULL;printf("清空成功！n");returnL;(7)銷毀鏈表LinkListFreeList(LinkListL)(printf("釋放成功！n");free(L);(8)主函數(shù)intmain()(LinkLis

8、tL=InitList();intn,i,j;Pr();scanf("%d",&n);while(n>0&&n<7)(switch(n)(case 1:printf("請(qǐng)輸入要插入的結(jié)點(diǎn)的值和插入的位置:");scanf("%d%d",&i,&j);InsertList(L,j,i);break;case 2:printf("請(qǐng)輸入要?jiǎng)h除的結(jié)點(diǎn)的位置:");scanf("%d",&i);DeleteList(L,i);break;cas

9、e 3:printf("請(qǐng)輸入要查找的結(jié)點(diǎn)的值:");scanf("%d",&i);LocateList(L,i);break;case 4:Print(L);break;case 5:EmptyList(L);break;case 6:FreeList(L);break;Pr();scanf("%d",&n);if(n=7)printf("退出成功！)；return0;2 .構(gòu)造兩個(gè)帶有表頭結(jié)點(diǎn)的有序單鏈表La、Lb,編寫程序?qū)崿F(xiàn)將La、Lb合并成一個(gè)有序單鏈表LcLinkListConnectList(L

10、inkListLa,LinkListLb)LinkListLc,a,b,c;a=La;b=Lb;if(La->data<Lb->data)Lc=La,a=a->next;elseLc=Lb,b=b->next;c=Lc;while(a!=NULL|b!=NULL)if(a=NULL)c->next=b,break;if(b=NULL)c->next=a;break;if(a->data<b->data)c->next=a,a=a->next,c=c->next;elsec->next=b,b=b->nex

11、t,c=c->next;returnLc;3 .如果上面實(shí)驗(yàn)內(nèi)容2中合并的表內(nèi)不允許有重復(fù)的數(shù)據(jù)該如何操作LinkListConnectList(LinkListLa,LinkListLb)inti=1;LinkListLc,a,b,c,q,p;a=La;b=Lb;if(La->data<Lb->data)Lc=La;a=a->next;elseLc=Lb;b=b->next;c=Lc;while(a!=NULL|b!=NULL)if(a=NULL)c->next=b,break;if(b=NULL)c->next=a,break;if(a-&g

12、t;data<b->data)c->next=a,a=a->next,c=c->next;elsec->next=b,b=b->next,c=c->next;c=Lc;q=c->next;while(q!=NULL)if(c->data=q->data)c->next=q->next;c=c->next;q=c->next;returnLc;4 .如何將一個(gè)帶頭結(jié)點(diǎn)的單鏈表La分解成兩個(gè)同樣結(jié)構(gòu)的單鏈表Lb,Lc,使得Lb中只含La表中奇數(shù)結(jié)點(diǎn),Lc中含有La表的偶數(shù)結(jié)點(diǎn)？StatusPartList(L

13、inkListLc)(intn1=0,n2=0;LinkListLa,Lb,L;LinkLista,b;L=Lc;while(L!=NULL)(if(L->data%2=0)(if(n1=0)(a=La=L;L=L->next;)else(a->next=L;L=L->next;)else(if(n2=0)(b=Lb=L;L=L->next;)else(b->next=L;L=L->next;)a->next=NULL;b->next=NULL;returnOK;六、實(shí)驗(yàn)測(cè)試1.編寫程序完成單鏈表的以下根本操作:口344bbb上成功IS66

14、789901005:?的何百：X值!45為簞4個(gè)1U0用人篇零1,Ai.iAAL2fi3BL>.,J.-2功結(jié)的的用除要時(shí)加人義工翳入盒SAm點(diǎn)中上膏表襄ss曾皆律四的的的中出衣嚼值卷位iiiii,Rs至S入八點(diǎn)S1HMLL工4-.-'.-.7.點(diǎn)tllniF用"rliSH孌的1L人小單表L2.3,4.5flr.11點(diǎn)船的寓siMSI點(diǎn)靛結(jié)功的的*中川曾Mi使！芳功入醯雪翳人成他加岬相甄.點(diǎn)中W0W凄SS匕匕百功的用f益人先出W鑿人成LI2.I3.I4.S.ls.l7.ggqg七、總結(jié)附錄1:源代碼#include<stdio.h>#include<s

15、tdlib.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;typedefintStatus;typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;LinkListNewLNode(LNode*P,ElemTypedata)P=(LNode*)malloc(sizeof(LNode);P->data=data;P->next=NULL;returnP;LinkListInitList()inti,value,n;LinkListH

16、=(LinkList)malloc(sizeof(LNode);LinkListP=H;P->next=NULL;doprintf("請(qǐng)輸入鏈表的長度:");scanf("%d",&n);if(n<=0)printf("輸入有誤請(qǐng)重新輸入！n");while(n<=0);printf("請(qǐng)輸入各個(gè)元素:n");for(i=0;i<n;i+)scanf("%d",&value);LinkListNEW=(LinkList)malloc(sizeof(LNod

17、e);NEW->data=value;P->next=NEW;NEW->next=NULL;P=NEW;)printf("鏈表建立成功！n");returnH->next;)LinkListInsertList(LinkListL,inti,ElemTypevalue)(LinkListh,q,t=NewLNode(t,value);intx=0;h=q=L;if(i=1)(t->next=h;h=t;)else(while(x+<i-2)q=q->next;t->next=q->next;q->next=t;)p

18、rintf("插入成功！n");returnh;)LinkListDeleteList(LinkListL,inti)(LinkListh,q,de;intx=0;h=q=L;intt;if(i=1)h=h->next;else(while(x+<i-2)q=q->next;de=q->next;if(de->next=NULL)q->next=NULL;elseq->next=de->next;)printf("刪除成功！n");returnh;)StatusLocateList(LinkListL,El

19、emTypevalue)(LinkListq=L;inti=0,t;while(q!=NULL)(i+;if(q->data=value)(printf("該結(jié)點(diǎn)在鏈表中的位置為第d4Vn",i);returnOK;)q=q->next;)printf("該鏈表中沒有該結(jié)點(diǎn)！n");returnERROR;)StatusPrint(LinkListL)(LinkListq=L;printf("該鏈表的每個(gè)元素為:n");while(q!=NULL)(printf("%8d",q->data);q=

20、q->next;)printf("n");returnOK;)LinkListEmptyList(LinkListL)(free(L->data);L->next=NULL;printf("清空成功！n");returnL;)LinkListFreeList(LinkListL)(printf("釋放成功！n");free(L);)voidPr()printf("n1.插入新結(jié)點(diǎn)n");printf("2.刪除鏈表中的結(jié)點(diǎn)n");printf("3.查找結(jié)點(diǎn)n");printf("4.輸出鏈表n");