數(shù)據(jù)結構第一次實驗報告

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

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

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

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

(三)詳細設計1．元素類型，結點類型和指針類型：

typedefstructLnode{ intdata; structLnode*next;}Lnode;

2．每個模塊的分析：（1）主程序模塊：intmain(){ Lnode*La,*Lb; Lnodelist1,list2; La=&list1; Lb=&list2; printf("請輸入鏈表La數(shù)據(jù)：\n"); creat(La,I);printf("請輸入鏈表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）建立鏈表并輸入每個人信息模塊；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ù)調用關系圖main()creat()add（）output（）3．完整的程序：(見源文件).(四)程序使用說明及測試結果1．程序使用說明（1）本程序的運行環(huán)境為VC6.0。（2）進入演示程序后即顯示提示信息：請輸入3個鏈表La數(shù)據(jù)并按回車鍵結束：135請輸入5個鏈表Lb數(shù)據(jù)并按回車鍵結束：234692．測試結果合成鏈表數(shù)據(jù)：12334569Pressanykeytocontinue3．VC6.0原始運行界面（五）、實驗總結(實驗心得)在本次試驗中我總共花了2個小時來完成上機實驗，其中有半個小時左右的時間在紙上設計