《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告班級(jí):10011107姓名:李維庭學(xué)號(hào):2011302550E-mail:1510209219@日期:2012年10月9日◎?qū)嶒?yàn)題目:合并兩個(gè)鏈表◎?qū)嶒?yàn)?zāi)康模簩⒔o定的兩個(gè)鏈表合并為一個(gè)鏈表◎?qū)嶒?yàn)內(nèi)容：設(shè)A與B分別為兩個(gè)帶有頭結(jié)點(diǎn)的有序循環(huán)鏈表（所謂有序是指鏈接點(diǎn)按數(shù)據(jù)域值大小鏈接，本題不妨設(shè)按數(shù)據(jù)域值從小到大排列），list1和list2分別為指向兩個(gè)鏈表的頭指針。請(qǐng)寫(xiě)出將這兩個(gè)鏈表合并為一個(gè)帶頭結(jié)點(diǎn)的有序循環(huán)鏈表的算法。一、需求分析首先建立兩個(gè)帶有頭結(jié)點(diǎn)的有序循環(huán)鏈表，list1和list2分別為鏈表的頭指針。然后將兩個(gè)鏈表合并為一個(gè)有序循環(huán)鏈表。1、輸入的形式和輸入值的范圍：輸入值為一切正整數(shù)。2、輸出的形式：輸出值為合并鏈表的順序數(shù)據(jù)，全為正整數(shù)。3、程序所能達(dá)到的功能：將兩個(gè)有序循環(huán)鏈表合并為一個(gè)有序循環(huán)鏈表，并輸出。4、測(cè)試數(shù)據(jù)：根據(jù)面板提示輸入程序首部定義的有序整數(shù)。輸出依舊為有序整數(shù)。若輸入數(shù)據(jù)為無(wú)序則可能出錯(cuò)。二概要設(shè)計(jì)本程序中用到的抽象數(shù)據(jù)類(lèi)型為線性鏈表。主程序的流程為建立鏈表，合并鏈表以及輸出鏈表。各程序模塊之間互不調(diào)用，統(tǒng)一由主函數(shù)調(diào)用。三詳細(xì)設(shè)計(jì)

實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類(lèi)型：結(jié)點(diǎn)定義：typedefstructLnode{ intdata; structLnode*next;//定義指針}Lnode;//節(jié)點(diǎn)具體操作有：建立鏈表：intcreat(Lnode*L,intj){初始條件：頭指針L；操作結(jié)果：以L為頭結(jié)點(diǎn)的鏈表；}合并鏈表：intadd(Lnode*La,Lnode*Lb){初始條件：兩個(gè)含有有序元素的鏈表；操作結(jié)果：合并為一個(gè)有序鏈表；}輸出鏈表：intoutput(Lnode*L){初始條件：一個(gè)合成的有序鏈表；合并鏈表主函數(shù)操作結(jié)果：將鏈表元素輸出到屏幕上；主函數(shù)}畫(huà)出函數(shù)的調(diào)用關(guān)系：

建立鏈表 輸出鏈表四使用說(shuō)明、測(cè)試分析及結(jié)果1、打開(kāi)程序，編譯，連接以及運(yùn)行。之后根據(jù)提示輸入數(shù)據(jù)，點(diǎn)擊回車(chē)鍵。2、測(cè)試結(jié)果與分析：在輸出的鏈表數(shù)據(jù)中可以看到輸入兩個(gè)鏈表的數(shù)據(jù)有序排列。3、調(diào)試過(guò)程中遇到的問(wèn)題是如何解決提以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析：在調(diào)試時(shí)出現(xiàn)該地址不能釋放的信息，經(jīng)檢查是由于人為釋放了定義的地址所致，之后便可以成功運(yùn)行。4、運(yùn)行界面：為c程序原始的運(yùn)行界面。五、實(shí)驗(yàn)總結(jié)1、算法的時(shí)空分析和改進(jìn)設(shè)想。示例：(一)需求分析1．本程序中，第一個(gè)鏈表的數(shù)據(jù)應(yīng)為I個(gè)，第二個(gè)鏈表的數(shù)據(jù)是J個(gè)。輸入后由循環(huán)依次連接到鏈表中。2．演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤(pán)上輸入相應(yīng)數(shù)據(jù)（每個(gè)鏈表的數(shù)據(jù)）由程序自動(dòng)鏈接。合并之后輸出結(jié)果。3．程序執(zhí)行的命令包括：（1）建立鏈表；（2）輸入數(shù)據(jù)；（3）合并鏈表；（4）輸出鏈表；（5）結(jié)束。4．測(cè)試數(shù)據(jù)I=3，J=5時(shí)輸入鏈表為數(shù)據(jù)為《1,3,5》，《2,3,4,6,9》輸出結(jié)果為《1,2,3,3,4,5,6,9》符合題目的要求。(二)概要設(shè)計(jì)為了實(shí)現(xiàn)上述操作，應(yīng)以單向循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)?；静僮鳎篿ntcreat(Lnode*L,intj){初始條件：頭指針L；操作結(jié)果：以L為頭結(jié)點(diǎn)的鏈表；}intadd(Lnode*La,Lnode*Lb){初始條件：兩個(gè)含有有序元素的鏈表；操作結(jié)果：合并為一個(gè)有序鏈表；}intoutput(Lnode*L){初始條件：一個(gè)合成的有序鏈表；操作結(jié)果：將鏈表元素輸出到屏幕上；}2．本程序包含三個(gè)模塊：（1）主程序模塊；（2）構(gòu)造鏈表并輸入每個(gè)人信息模塊；（3）合并鏈表模塊；（4）輸出鏈表模塊；（4）模塊調(diào)用圖：

主程序模塊建立鏈表并輸入每個(gè)人信息模塊合并鏈表模塊輸出鏈表模塊

(三)詳細(xì)設(shè)計(jì)1．元素類(lèi)型，結(jié)點(diǎn)類(lèi)型和指針類(lèi)型：

typedefstructLnode{ intdata; structLnode*next;}Lnode;

2．每個(gè)模塊的分析：（1）主程序模塊：intmain(){ Lnode*La,*Lb; Lnodelist1,list2; La=&list1; Lb=&list2; printf("請(qǐng)輸入鏈表La數(shù)據(jù)：\n"); creat(La,I);printf("請(qǐng)輸入鏈表Lb數(shù)據(jù)：\n"); creat(Lb,J);printf("鏈表La數(shù)據(jù)：\n");printf("鏈表Lb數(shù)據(jù)：\n");add(La,Lb);printf("合成鏈表數(shù)據(jù)：\n"); output(La); return1;}（2）建立鏈表并輸入每個(gè)人信息模塊；intcreat(Lnode*L,intj){ inti; Lnode*p,*q; q=L; for(i=0;i<j;i++) {p=(Lnode*)malloc(sizeof(Lnode));if(!p)return0;scanf("%d",&p->data);q->next=p;q=p; } q->next=L; return1;}合并鏈表模塊intadd(Lnode*La,Lnode*Lb){ Lnode*p,*q,*r; p=La->next; q=Lb->next; r=La; for(;(p!=La)&&(q!=Lb);) { if((p->data)<(q->data)) { r->next=p; r=p; p=p->next; } else { r->next=q; r=q; q=q->next; } } if(p!=La)r->next=p; else for(;q!=Lb;r=q,q=q->next) r->next=q; r->next=La; return1;}輸出鏈表模塊intoutput(Lnode*L){ Lnode*p; p=L->next; for(;p!=L;p=p->next) { printf("%d",p->data); } printf("\n"); return1;}（5）函數(shù)調(diào)用關(guān)系圖main()creat()add（）output（）3．完整的程序：(見(jiàn)源文件).(四)程序使用說(shuō)明及測(cè)試結(jié)果1．程序使用說(shuō)明（1）本程序的運(yùn)行環(huán)境為VC6.0。（2）進(jìn)入演示程序后即顯示提示信息：請(qǐng)輸入3個(gè)鏈表La數(shù)據(jù)并按回車(chē)鍵結(jié)束：135請(qǐng)輸入5個(gè)鏈表Lb數(shù)據(jù)并按回車(chē)鍵結(jié)束：234692．測(cè)試結(jié)果合成鏈表數(shù)據(jù)：12334569Pressanykeytocontinue3．VC6.0原始運(yùn)行界面（五）、實(shí)驗(yàn)總結(jié)(實(shí)驗(yàn)心得)在本次試驗(yàn)中我總共花了2個(gè)小時(shí)來(lái)完成上機(jī)實(shí)驗(yàn)，其中有半個(gè)小時(shí)左右的時(shí)間在紙上設(shè)計(jì)