1、實驗作業說明實驗課基本要求實驗課要求到課。自第五周開始，共30學時。實驗時間：周五下午（8，9，10節）。實驗地點：東區老圖書館北樓三層東側機房。實驗內容包括必做題和選做題。 具體如下：序號實驗項目內容類型1線性表應用：一元多項式的創建和運算必做2棧應用：表達式求值必做3二叉樹：哈夫曼編碼、解碼器設計3、4選做一題4二叉樹的創建、遍歷、和應用5圖的應用：遍歷、最短路徑、最小代價生成樹5、6、7選做一題6排序算法的實現及性能比較7哈希表按上述要求完成4個題目（多選不限），并提交實驗報告(word格式)。實驗報告格式模板見后。請將實驗報告和源程序（只要c或c+源程序，不要有VC工程文件和可執行程序

2、等其他文件）打包成一個文檔，文件名格式為“學號+姓名+題號.rar”。 例如：“PB14204003+李明+136.rar”，6月5日之前發送email到 HYPERLINK mailto:dsdblab dsdblab 實驗報告格式 在做完實驗以后寫實驗報告，是整個實驗過程的一個重要環節。報告的撰寫過程實際是對整個實驗的總結與回顧，有助加深對實驗的理解，提高對實驗的認識。下面介紹如何撰寫實驗報告。 2.1 如何撰寫實驗報告 對于每一個實驗中所要求解決的問題，都應該有規范詳細的報告文檔，本實驗要求報告的規范如下： 一、 問題描述 1 實驗題目：一般教材中會給出實驗題目。 2 基本要求：實驗的基

3、本要求，一般也會在教材中給出。 3 測試數據：實驗中要用到的測試數據，部分實驗由教材提供。 二、 需求分析 1 程序所能達到的基本可能。 2 輸入的形式及輸入值范圍 3 輸出的形式 4 測試數據要求 三、 概要設計 1. 所用到得數據結構及其ADT 2. 主程序流程及其模塊調用關系 3. 核心模塊的算法偽碼 四、 詳細設計 1. 實現概要設計中的數據結構ADT 2. 實現每個操作的偽碼，重點語句加注釋 3. 主程序和其他模塊的偽碼 4. 函數調用關系圖 五、 調試分析 1. 設計與調試過程中遇到的問題分析、體會 2. 主要算法的時間和空間復雜度分析 六、 使用說明 簡要給出程序的運行和操作步驟

4、。 七、 測試結果 給出實驗結果，包括輸入和輸出。 八、 附錄 帶注釋的源程序。 2.2 實驗報告模板 一、 問題描述 1. 實驗題目：利用有序鏈表表示正整數集合，實現集合的交、并和差運算。 2. 基本要求：有用戶輸入兩種整數分別作為兩個集合元素，由程序計算它們的交、并和差，并輸出結果。 3. 測試數據： S1=3,5,6,9,12,27,35 S2=5,8,10,12,27,31,42,51,55,63 運行結果應為： S1S2=3,5,6,8,9,10,12,27,31,35,42,51,55,63 S1S2=5,12,27 S1-S2=3,6,9,35 二、 需求分析 1. 本程序用來求

5、出任意兩個正整數集合的交、并、差。 2. 程序運行后顯示提示信息，提示用戶輸入兩組整數，程序需自動顧慮重復的整數和負數。 3. 用戶輸入完畢后，程序自動輸出運算結果。 三、 概要設計 為了實現上述功能，應以有序鏈表表示集合，因此需要有序表和集合兩個抽象數據類型。 1. 有序表抽象數據類型定義： ADT OrderedList 數據對象：D=ai|aiElemType,i=1,2.,n,n0 數據關系：R=|ai-1,aiD, ai-1ai ,i=2,.,n 基本操作： InitList(&L); /構造空線性表 DestroyList(&L); /銷毀線性表 ClearList(&L); /將

6、L置空 ListEmpty(L); /檢查L是否為空 ListLength(L); /返回L中元素個數 GetElem(L,i,&e); /返回L中第i個元素賦予e LocatePos (L,e); /返回L中e的位置 InsertElem(&L,e); /在L中插入e DeleteElem(&L,i); /刪除L中第i個元素 ListTravers(L); /依次輸出L中元素。 ADT OrderedList 2. 集合的抽象數據類型定義： ADT set 數據對象：D=ai|aiElemType,且各不相同，i=1,2.,n,n0 數據關系：R= 基本操作： CreateNullSet(&

7、T); DestroySet(&T); AddElem(&T,e); DelElem(&T,e); Union(&T,S1,S2); Intersection(&T,S1,S2); Difference(&T,S1,S2); PrintSet(T); ADT set 3. 本程序保護模塊： 主程序模塊 集合單元模塊：實現集合的抽象數據類型 有序表單元模塊：實現有序表抽象數據類型 調用關系： 主函數模塊 集合單元模塊 有序表單元模塊四、 詳細設計 1. 元素類型、結點類型和結點指針類型： typedef int ElemType; typedef struct NodeType ElemType

8、 data; NodeType *next; NodeType,*LinkType; 2. 有序表類型： typedef struct LinkType head,tail; int size; int curpos; LinkType current; OrderedList; /部分基本操作的偽碼實現 status InitList(OrderedList &L) L.head=new Nodetype; if(!L.head)retuen false; L.head-data=0; L.head-next=NULL; L.current=L.tail=L.head; L.curpos=L

9、.size=0 ; return true ; /. .(其它略) 3. 集合類Set的實現，利用有序鏈表來實現： typedef OrderedList OrderedSet; status CreateNullSet(OrderedSet &T) if(InitList(T) return true; else return false; / . . (其它略) 4. 主函數的偽碼： void main() coutendl”請輸入 S1:”; CreateSet(S1); coutendl”請輸入 S2:”; CreateSet(S2); PrintSet(S1); PrintSet(S

10、2); Union(T1,S1,S2); coutendl”Union:”; PrintSet(T1); Intersection(T2,S1,S2); coutendl”Intersection:”; PrintSet(T2); Difference(T3,S1,S2); coutendl” Difference:”; PrintSet(T3); Destroy(T1); Destroy(T2); Destroy(T3); Destroy(S1); Destroy(S2); 5. 函數調用關系 （略）五、 調試分析 1. 程序中將紙張的操作封裝在鏈表的類型中，在集合的類型模塊中，只需要引用鏈

11、表的操作實現相應的集合運算即可，從而使集合模塊的調試比較方便。 2. 算法的時空分析： （1） 由于有序表采用帶頭結點的有序鏈表，并增設尾指針和表的長度兩個標示，各種操作的算法時間復雜度比較合理，LocatePos、GetElem和DestroyList等操作的時間復雜度都是O（n），其中n是鏈表的長度。 （2） 構造有序集算法CreateSet讀入n個元素，需要逐個用LocatePos判斷輸入元素是不是有重復且確定插入位置后，調用InsertElem插入到有序鏈表,所以復雜度也是O(n)。求并算法Union將兩個集合共m+n的元素不重復地依次使用InsertElem插入到結果集中，由于插入式

12、按元素值自小到大次序進行，時間復雜度為O(m+n)。類似地，求交算法InterSection和求差算法Difference的時間復雜度也是O(m+n)。 消耗算法DestroySet和輸出PrintSet都是O(n)。 所有算法的空間復雜度都是O(1)。 六、 使用說明 程序運行后用戶根據提示輸入集合S1、S2的元素，元素間以空格或回車分隔，輸入-1表示輸入結束。程序將按照集合內元素從小到大的順序打印出S1和S2，以及他們的并、交和差。 七、 調試結果 使用兩組數據進行了測試： 1. 請輸入S1:35 12 9 12 6 6 -12 3 5 9 9 35 27 -1 請輸入S2:31 27 5 10 8 -20 55 12 63 42 51 -1 3，5，6，9，12，27，35 5，8，10，12，27，31，42，51，55，63 Union:3,5,6,8,9,10,12,27,31,35,42,51,55,63 Intersectio