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

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

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

3、,n;LinkListH=(LinkList)malloc(sizeof(LNode);LinkListP=H;P->next=NULL;doprintf("請輸入鏈表的長度:");scanf("%d",&n);if(n<=0)printf("輸入有誤請重新輸入！n");while(n<=0);printf("請輸入各個元素: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中插入一個新結(jié)點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中的某一個結(jié)點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é)點并返回其位置StatusLocateList(LinkListL,ElemTypevalue)(LinkListq=L;inti=0,t;while(q!=NULL)(i+;if(q->data=value)(printf("該結(jié)點在鏈表中的位置為第d4Vn",i);returnOK;q=q->next;printf("該鏈表中沒有該結(jié)點！n");returnERROR;(5)打印輸出La中的結(jié)點元素值StatusPrint(LinkListL)(LinkListq=L;printf("該鏈表的每個元素為:

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("請輸入要插入的結(jié)點的值和插入的位置:");scanf("%d%d",&i,&j);InsertList(L,j,i);break;case 2:printf("請輸入要刪除的結(jié)點的位置:");scanf("%d",&i);DeleteList(L,i);break;cas

9、e 3:printf("請輸入要查找的結(jié)點的值:");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)造兩個帶有表頭結(jié)點的有序單鏈表La、Lb,編寫程序?qū)崿F(xiàn)將La、Lb合并成一個有序單鏈表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 .如果上面實驗內(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 .如何將一個帶頭結(jié)點的單鏈表La分解成兩個同樣結(jié)構(gòu)的單鏈表Lb,Lc,使得Lb中只含La表中奇數(shù)結(jié)點,Lc中含有La表的偶數(shù)結(jié)點？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;六、實驗測試1.編寫程序完成單鏈表的以下根本操作:口344bbb上成功IS66

14、789901005:?的何百：X值!45為簞4個1U0用人篇零1,Ai.iAAL2fi3BL>.,J.-2功結(jié)的的用除要時加人義工翳入盒SAm點中上膏表襄ss曾皆律四的的的中出衣嚼值卷位iiiii,Rs至S入八點S1HMLL工4-.-'.-.7.點tllniF用"rliSH孌的1L人小單表L2.3,4.5flr.11點船的寓siMSI點靛結(jié)功的的*中川曾Mi使！芳功入醯雪翳人成他加岬相甄.點中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("請輸入鏈表的長度:");scanf("%d",&n);if(n<=0)printf("輸入有誤請重新輸入！n");while(n<=0);printf("請輸入各個元素: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é)點在鏈表中的位置為第d4Vn",i);returnOK;)q=q->next;)printf("該鏈表中沒有該結(jié)點！n");returnERROR;)StatusPrint(LinkListL)(LinkListq=L;printf("該鏈表的每個元素為: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é)點n");printf("2.刪除鏈表中的結(jié)點n");printf("3.查找結(jié)點n");printf("4.輸出鏈表n");