【C語言《數(shù)據(jù)結(jié)構(gòu)》實驗報告】鏈表的合并

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗題目: 合并兩個鏈表：設(shè)a與b分別為兩個帶有頭結(jié)點的有序循環(huán)鏈表（所謂有序是指鏈接點按數(shù)據(jù)域值大小鏈接，本題不妨設(shè)按數(shù)據(jù)域值從小到大排列），list1和list2分別為指向兩個鏈表的頭指針。請寫出將這兩個鏈表合并為一個帶頭結(jié)點的有序循環(huán)鏈表的算法。實驗?zāi)康模菏褂庙樞虮淼膭?chuàng)建、插入、刪除、合并等操作編寫關(guān)于數(shù)據(jù)結(jié)構(gòu)的程序。實驗內(nèi)容：寫出程序并上機(jī)調(diào)試、通過。一、需求分析1、演示程序以用戶和計算機(jī)的對話方式執(zhí)行，即在計算機(jī)終端上顯示“please input the first list”時輸入第一個鏈表的元素個數(shù)和元素。當(dāng)出現(xiàn)“please input the second

2、list”時輸入第二個鏈表的元素個數(shù)和元素。然后計算機(jī)終端輸出合并后的鏈表。2、輸出的形式為兩個鏈表中的元素合并成一個鏈表并且其中元素按照遞增的順序排列。3、程序執(zhí)行的命令包括：（1）構(gòu)造含n個元素的循環(huán)鏈表；（2）輸入數(shù)據(jù)；（3）將輸入的數(shù)據(jù)作成循環(huán)鏈表；（4）合并；（5）輸出；（6）結(jié)束。4、本程序能將兩個鏈表合并成一個鏈表。并且合并后的鏈表中的元素是原來兩個鏈表中的元素按照遞增順序的排列。5、輸入及輸出示例：例1：please input the first list41 3 7 9please input the second list51 2 5 6 8output the merg

3、elist1 2 3 5 6 7 8 9press any key to continue 例2：please input the first list51 2 5 9 11please input the second list31 2 8output the mergelist1 2 5 8 9 11press any key to continue 二 概要設(shè)計1基本操作本程序中，用單向有序循環(huán)鏈表作為存儲結(jié)構(gòu)。(1)、node *creatlist (int n)操作結(jié)果：創(chuàng)建含有n個元素的有序循環(huán)鏈表。(2)、node* mergelist(node*la,node*lb)初始條件：

4、循環(huán)鏈表a、b已存在。操作結(jié)果：歸并遞增的鏈表la和lb，得到鏈表lc，使lc也為遞增循環(huán)鏈表。(3)、void printlist(node* l)初始條件：鏈表l已存在操作結(jié)果：輸出鏈表l中的元素。2、模塊調(diào)用圖主程序模塊創(chuàng)建帶頭結(jié)點的循環(huán)鏈表模塊將所有元素插入空鏈表表尾模塊合并鏈表模塊輸出鏈表模塊三 詳細(xì)設(shè)計1、結(jié)點類型：typedef struct nodeint data;struct node *next;node;2、每個模塊：(1) 創(chuàng)建含有n個元素的有序循環(huán)鏈表node *creatlist (int n)/創(chuàng)建含有n個元素的有序循環(huán)鏈表int i,e;node *p,*l,

5、*list;list=(node*) malloc (sizeof(node);list-data=-1;list-next=list;l=list;/建立頭結(jié)點并用list記錄頭結(jié)點的位for(i=n;i0;i-)p=(node*) malloc (sizeof(node);/生成新結(jié)點scanf(%d,&e);/輸入元素值p-data=e;p-next=l-next;l-next=p;l=p;return(list);/返回頭結(jié)點的位置(2) 歸并遞增的鏈表la和lb，得到鏈表lcnode* mergelist(node*la,node*lb) /歸并遞增的鏈表la和lb，得到鏈表lc，使

6、lc也為遞增循環(huán)鏈表node *list1, *list2, *list3,*lc,*s,*p;list1=la-next;list2=lb-next;lc=la;list3=lc;lc-next=lc;/將la的頭結(jié)點作為lc的頭結(jié)點while(list1!=la&list2!=lb)if(list1-datadata) s=list1;list1=list1-next;s-next=list3-next;list3-next=s;list3=s;elseif(list1-data=list2-data) s=list1;list1=list1-next;s-next=list3-next;

7、list3-next=s;list3=s;p=list2;list2=list2-next;free(p); elseif(list1-datalist2-data) s=list2;list2=list2-next;s-next=list3-next;list3-next=s;list3=s;/根據(jù)元素大小將其依次插入lc中 while(list1!=la)list3-next=list1;list3=list1;list1=list1-next;while(list2!=lb)list3-next=list2;list3=list2;list2=list2-next;/將剩余元素插入lc中

8、list3-next=lc;/ 讓lc的尾結(jié)點指向lc的頭結(jié)點使其成為有序循環(huán)鏈表return(lc);/返回合并后的鏈表lc的頭結(jié)點(3)、輸出鏈表l中的元素void printlist(node* l)/輸出鏈表 node *p;p=l-next;while(p!=l)printf(%d ,p-data);p=p-next;printf(n);(4)主函數(shù)void main()node *creatlist (int n);node *mergelist(node*la,node*lb);void printlist(node* l);int m,n;node *linklist1,*li

9、nklist2,*linklist3;printf(please input the first listn);scanf(%d,&m);linklist1=creatlist (m);printf(please input the second listn);scanf(%d,&n);linklist2=creatlist (n);linklist3=mergelist(linklist1,linklist2);printf(output the mergelistn);printlist(linklist3);3、完整函數(shù)#include#includetypedef struct nod

10、eint data;struct node *next;node;void main()node *creatlist (int n);node *mergelist(node*la,node*lb);void printlist(node* l);int m,n;node *linklist1,*linklist2,*linklist3;printf(please input the first listn);scanf(%d,&m);linklist1=creatlist (m);printf(please input the second listn);scanf(%d,&n);link

11、list2=creatlist (n);linklist3=mergelist(linklist1,linklist2); printf(output the mergelistn);printlist(linklist3);node *creatlist (int n)/創(chuàng)建含有n個元素的有序循環(huán)鏈表int i,e;node *p,*l,*list;list=(node*) malloc (sizeof(node);list-data=-1;list-next=list;l=list;/建立頭結(jié)點并用list記錄頭結(jié)點的位for(i=n;i0;i-)p=(node*) malloc (siz

12、eof(node);/生成新結(jié)點scanf(%d,&e);/輸入元素值p-data=e;p-next=l-next;l-next=p;l=p;return(list);/返回頭結(jié)點的位置node* mergelist(node*la,node*lb) /歸并遞增的鏈表la和lb，得到鏈表lc，使lc也為遞增循環(huán)鏈表node *list1, *list2, *list3,*lc,*s,*p;list1=la-next;list2=lb-next;lc=la;list3=lc;lc-next=lc;/將la的頭結(jié)點作為lc的頭結(jié)點while(list1!=la&list2!=lb)if(list1

13、-datadata) s=list1;list1=list1-next;s-next=list3-next;list3-next=s;list3=s;elseif(list1-data=list2-data) s=list1;list1=list1-next;s-next=list3-next;list3-next=s;list3=s;p=list2;list2=list2-next;free(p); elseif(list1-datalist2-data) s=list2;list2=list2-next;s-next=list3-next;list3-next=s;list3=s;/根據(jù)元

14、素大小將其依次插入lc中 while(list1!=la)list3-next=list1;list3=list1;list1=list1-next;while(list2!=lb)list3-next=list2;list3=list2;list2=list2-next;/將剩余元素插入lc中l(wèi)ist3-next=lc;/ 讓lc的尾結(jié)點指向lc的頭結(jié)點使其成為有序循環(huán)鏈表return(lc);/返回合并后的鏈表lc的頭結(jié)點 void printlist(node* l)/輸出鏈表 node *p;p=l-next;while(p!=l)printf(%d ,p-data);p=p-next;printf(n);四 使用說明、測試分析及結(jié)果1、運行界面：microsoft visual c/c+2、測試結(jié)果例1：please input the first list41 3 7 9please input the second list51 2 5