有序表的合并的標準實驗報告

1、軟件工程專業(yè)類課程實驗報告課程名稱：學院專業(yè)： 學生姓名：學號：指導教師： 日期： 電子科技大學計算機學院實驗中心 電 子 科 技 大 學實 驗 報 告一、實驗室名稱：二、實驗項目名稱： 有序單鏈表的合并三、實驗原理：合并單鏈表算法的思想描述，因這是本實驗重點，這里老是就不寫了。四、實驗目的：1. 掌握帶頭結(jié)點的單鏈表建立，插入，刪除，查找等基本操作的設計與實現(xiàn)2. 通過單鏈表的排序編程理解單鏈表與順序表操作的區(qū)別與聯(lián)系3. 理解單鏈表對集合操作的實現(xiàn)4. 掌握有序集合合并的算法設計與存儲結(jié)構(gòu)的關系，及時空復雜度與算法性能的關系五、實驗內(nèi)容：1. 編程實現(xiàn)建立單鏈表的操作2. 編程實現(xiàn)單鏈表的

2、排序3. 編程實現(xiàn)用單鏈表合并有序表，使得合并結(jié)果有序，但是要求不額外增加內(nèi)存空間存放合并后的數(shù)據(jù)，時間開銷盡量少六、實驗器材（設備、元器件）：電腦1臺；XP或者windows 7操作系統(tǒng)Visual studio 2010開發(fā)環(huán)境七、實驗步驟：1. 項目分析與概要設計（1）輸入：第一個單鏈表長度 第一個單鏈表的所有數(shù)據(jù) 第二個單鏈表長度 第二個單鏈表的所有數(shù)據(jù)（2）輸出：2個有序單鏈表合并成一個有序表（3）算法分析與概要設計：a). 實現(xiàn)兩個有序單鏈表的合并，首先要保證輸入的單鏈表有序，因此要判斷單鏈表是否有序，如果無序，要先重新對單鏈表進行排序，然后才能夠做合并操作。b). 因為單鏈表合并

3、后不能增加額外空間，所以原來單鏈表的結(jié)點要串連到新的合并后的單鏈表中，原來的單鏈表合并后將不再存在。原來的單鏈表有2個頭結(jié)點，合并后只有一個單鏈表，因此有一個頭結(jié)點將被釋放。這里選擇A集合的頭結(jié)點為合并后的頭結(jié)點，而原來B集合的頭結(jié)點將被釋放。合并有序單鏈表的算法流程圖見圖1所示。2. 數(shù)據(jù)結(jié)構(gòu)與詳細設計（1）數(shù)據(jù)結(jié)構(gòu)采用帶頭結(jié)點的單鏈表存儲數(shù)據(jù)，結(jié)點結(jié)構(gòu)如下：struct node int value;struct node * next;typedef struct node Node; typedef struct node *ptrList,*List; （2）詳細設計根據(jù)概要設計流程

4、圖，需要實現(xiàn)如下功能：建立帶頭結(jié)點的單鏈表；判斷單鏈表是否有序；單鏈表排序；合并有序表使其仍然有序；打印輸出單鏈表的所有數(shù)據(jù)。下面對這些功能進行詳細設計（這里只演示判斷單鏈表是否有序的詳細設計過程，余下的請同學們自己完成）a). 建立帶頭結(jié)點的單鏈表；b). 判斷單鏈表是否有序；輸入：帶頭結(jié)點的單鏈表輸出：單鏈表有序，返回1；單鏈表無序，返回0算法思想描述：從第二個元素結(jié)點開始，與直接前趨比較，如果比直接前趨結(jié)點元素值小，則返回無序（0）；否則，訪問下一個元素結(jié)點。如果直到單鏈表訪問結(jié)束，所有元素都大于等于直接前趨，則該單鏈表是有序表，返回真（1）。算法詳細設計流程圖見圖2所示。c). 單鏈表

5、排序；d). 合并有序表使其仍然有序；e). 打印輸出單鏈表的所有數(shù)據(jù)3. 源代碼主程序和其他幾個功能的源代碼這里省略了，只演示如何根據(jù)圖2的詳細設計流程圖寫源代碼b). 判斷單鏈表是否有序源代碼；int JudgeListSorted(List header)ptrList p,q;int bSorted=1;p=header->next;if(p=NULL)return bSorted;q=p->next;while(q && bSorted=1)if(p->data<q->data)p=q;q=q->next;elsebSorted=0;return bSorted;八、實驗數(shù)據(jù)及結(jié)果分析：程序測試輸入數(shù)據(jù)分別為下面幾種情況：1. 2個鏈表都不空，但兩個鏈表都有序2. 至少有一個鏈表空，且不空的鏈表有序4. 兩個鏈表都不空，且鏈表無序5. 至少1個鏈表空，且不空的鏈表無序6. 一個鏈表有序，一個鏈表無序針對上面6種情況，分別測試數(shù)據(jù)存在下列因素的情況：7. 鏈表中的數(shù)據(jù)有負數(shù)，正數(shù)，08. 鏈表中的數(shù)據(jù)有重復數(shù)據(jù)9. 2個鏈表都沒有重復數(shù)據(jù)，但是2個鏈表的