鏈表的基本操作數據結構實驗報告

1、大學數據結構實驗報告課程名稱 數據結構實驗 第(四)次實驗 實驗名稱鏈表的基本操作學生姓名于歌專業(yè)班級 學號實驗成績 指導老師(簽名)日期 2018年10月01日一、實驗目的1 .學會定義單鏈表的結點類型，實現(xiàn)對單鏈表的一些基本操作和具體 的函數定義，了解并掌握單鏈表的類定義以及成員函數的定義與調用。2 .掌握單鏈表基本操作及兩個有序表歸并、 單鏈表逆置等操作的實現(xiàn)。二、實驗要求1 .預習c語言中結構體的定義與基本操作方法。2 .對單鏈表的每個基本操作用單獨的函數實現(xiàn)。3 .編寫完整程序完成下面的實驗內容并上機運行。4 .整理并上交實驗報告。三、實驗內容：1.編寫程序完成單鏈表的下列基本操作：

2、(1)初始化單鏈表la(2)在la中插入一個新結點(3)刪除la中的某一個結點(4)在la中查找某結點并返回其位置(5)打印輸出la中的結點元素值(6)清空鏈表(7)銷毀鏈表2構造兩個帶有表頭結點的有序單鏈表 la、lb,編寫程序實現(xiàn)將la、 lb合并成一個有序單鏈表lco四、思考與提高：1 .如果上面實驗內容2中合并的表內不允許有重復的數據該如何操作？2 .如何將一個帶頭結點的單鏈表la分解成兩個同樣結構的單鏈表 lb, lc,使得lb中只含la表中奇數結點，lc中含有l(wèi)a表的偶數結點？五、實驗設計1.編寫程序完成單鏈表的下列基本操作：(1)初始化單鏈表lalinklist initlist

3、()int i,value,n;linklist h=(linklist)malloc(sizeof(lnode);linklist p=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);linklis

4、t new = (linklist)malloc(sizeof(lnode);new->data=value;p->next=new;new->next=null;p=new;printf(" 鏈表建立成功！ n");return h->next;( 2)在la 中插入一個新結點linklist insertlist(linklist l,int i,elemtype value)linklist h,q,t=newlnode(t,value);int x=0;h=q=l;if(i=1)t->next=h, h=t;elsewhile(x+&l

5、t;i-2)q=q->next;t->next=q->next;q->next=t;printf(" 插入成功！ n");return h;3）刪除la 中的某一個結點linklist deletelist(linklist l,int i)linklist h,q,de;int x=0;h=q=l;int t;if(i=1)h=h->next;elsewhile(x+<i-2)q=q->next;de=q->next;if(de->next=null)q->next=null;elseq->next=de-

6、>next;printf(" 刪除成功！ n");return h;( 4)在la 中查找某結點并返回其位置status locatelist(linklist l,elemtype value)linklist q=l;int i=0,t;while(q!=null)i+;if(q->data=value)printf("該結點在鏈表中的位置為第d4vn",i)；return ok;q=q->next;printf(" 該鏈表中沒有該結點！ n");return error;( 5)打印輸出la 中的結點元素值st

7、atus print(linklist l)linklist q=l;printf(" 該鏈表的每個元素為 :n");while(q!=null)printf("%8d",q->data);q=q->next;printf("n");return ok;( 6)清空鏈表linklist emptylist(linklist l)free(l->data);l->next=null;printf(" 清空成功！ n");return l;( 7)銷毀鏈表linklist freelist(li

8、nklist l)printf(" 釋放成功！ n");free(l);( 8)主函數int main()linklist l=initlist();int n,i,j;pr();scanf("%d",&n);while(n>0&&n<7)switch(n)case 1:printf("請輸入要插入的結點的值和插入的位置:");scanf("%d %d",&i,&j);insertlist(l,j,i);break;case 2:printf("請輸入要

9、刪除的結點的位置:");scanf("%d",&i);deletelist(l,i);break;case 3:printf("請輸入要查找的結點的值:");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(" 退出成功！ ")

10、;return 0;2構造兩個帶有表頭結點的有序單鏈表la、 lb ，編寫程序實現(xiàn)將la 、 lb 合并成一個有序單鏈表lclinklist connectlist(linklist la,linklist lb)linklist lc,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->

11、;data<b->data)c->next=a,a=a->next,c=c->next;elsec->next=b,b=b->next,c=c->next;return lc;3 .如果上面實驗內容2中合并的表內不允許有重復的數據該如何操作 linklist connectlist(linklist la,linklist lb)int i=1;linklist lc,a,b,c,q,p;a=la;b=lb;if(la->data<lb->data)lc=la;a=a->next;elselc=lb;b=b->nex

12、t;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->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

13、=c->next;return lc;4 .如何將一個帶頭結點的單鏈表la分解成兩個同樣結構的單鏈表lb, lc,使 得lb中只含la表中奇數結點,lc中含有l(wèi)a表的偶數結點？status partlist(linklist lc)int n1=0,n2=0;linklist la,lb,l;linklist a,b;l=lc;while(l!=null)if(l->data%2=0)if(n1=0)a=la=l;l=l->next; elsea->next=l;l=l->next; elseif(n2=0)b=lb=l;l=l->next; elseb-&

14、gt;next=l;l=l->next;a->next=null;b->next=null;return ok;六、實驗測試1.編寫程序完成單鏈表的下列基本操作:口34 4b bb 上成功is6 678990100 5:?的何百：x值! 45為簞4個1u045用人 篇 零1,ai.iaal2fi3bl>.,j.-2 功結 的的 用除 要時加人義工翳入盒sam點中上膏表襄ss曾 皆律 四的 的的中 出衣 嚼值 卷位i iiii,rs至s入八點s1hmll工4-.-'.-.7.點tllnif用"r li s h孌的1l 人小單表 l2.3,4.5flr.1

15、1點船的寓 si msi點 靛結 功的 的*中 川曾mi使！芳功 入醯雪翳人成 他加岬相甄.點中w0w凄ss匕匕 百 功 的 用 f 益人先出w鑿人成li2.i3.i4.s.ls.l7.ggqg七、總結附錄 1 ：源代碼#include<stdio.h>#include<stdlib.h>#define ok 1#define error 0#define overflow -2typedef int elemtype;typedef int status;typedef struct lnodeelemtype data;struct lnode *next; lno

16、de,*linklist;linklist newlnode(lnode *p,elemtype data)p = (lnode *)malloc(sizeof(lnode);p->data = data;p->next = null;return p;linklist initlist()int i,value,n;linklist h=(linklist)malloc(sizeof(lnode);linklist p=h;p->next=null;doprintf(" 請輸入鏈表的長度:");scanf("%d",&n);i

17、f(n<=0)printf("輸入有誤請重新輸入！ n");while(n<=0);printf(" 請輸入各個元素 :n");for(i=0; i<n; i+)scanf("%d",&value);linklist new = (linklist)malloc(sizeof(lnode);new->data=value;p->next=new;new->next=null;p=new;printf(" 鏈表建立成功！ n");return h->next;link

18、list insertlist(linklist l,int i,elemtype value)linklist h,q,t=newlnode(t,value);int x=0;h=q=l;if(i=1)t->next=h;h=t;elsewhile(x+<i-2)q=q->next;t->next=q->next;q->next=t;printf(" 插入成功！ n");return h;linklist deletelist(linklist l,int i)linklist h,q,de;int x=0;h=q=l;int t;if

19、(i=1)h=h->next;elsewhile(x+<i-2)q=q->next;de=q->next;if(de->next=null)q->next=null;elseq->next=de->next;printf(" 刪除成功！ n");return h;status locatelist(linklist l,elemtype value)linklist q=l;int i=0,t;while(q!=null)i+;if(q->data=value)printf("該結點在鏈表中的位置為第d4vn&

20、quot;,i)；return ok;q=q->next;printf(" 該鏈表中沒有該結點！ n");return error;status print(linklist l)linklist q=l;printf(" 該鏈表的每個元素為 :n");while(q!=null)printf("%8d",q->data);q=q->next;printf("n");return ok;linklist emptylist(linklist l)free(l->data);l->next=null;printf(" 清空成功！ n");return l;linklist freelist(linklist l)printf(" 釋放成功！ n");free(l);void pr()printf("n1. 插入新結點 n");printf("2. 刪除鏈表中的結點 n");printf("3.查找結點n");printf(&qu