數(shù)據(jù)結構實驗及實驗報告規(guī)范

試驗一集合交、并和差運算實現(xiàn)1.試驗性質：設計性試驗2.要求：（1）對兩個集合建立單鏈表存放構造；（2）實現(xiàn)集合交集、并集和差集運算；（3）實現(xiàn)運算時，不另外申請存放空間。3.目標：掌握線性表鏈式存放方式及其操作實現(xiàn)注：根據(jù)自己編程能力，交集、并集和差集運算能夠選擇其中之一進行。1/11試驗二括號匹配

1.試驗性質：設計性試驗2.要求：

輸入帶括號體現(xiàn)式，判斷其中括號是否配對。3.目標：掌握?；静僮鞑谩U展功能：根據(jù)自己編程能力，能夠增加功能，例如

給出配對括號位序和不配對括號位序。2/11試驗三二叉樹綜合操作

1.試驗性質：綜合性試驗2.要求：

A.采取二叉鏈表構造建立二叉樹；

B.顯示對其先、中、后序和層序遍歷成果。3.目標：A.掌握二叉樹二叉鏈表存放方式及二叉樹特性；B.學會應用棧和隊列。

擴展功能：根據(jù)自己編程能力，能夠增加如下功能：

A.

先序/中序/后序遍歷之一必須采取非遞歸實現(xiàn)；B.

求出該樹高度和葉子結點個數(shù)。

C.圖形顯示出該樹。等等….3/111．試驗性質：綜合性試驗2．要求：

A.初始化：從終端讀入字符集大小n,以及n個字符和n個權值，建立哈夫曼樹；B.編碼：根據(jù)哈夫曼樹對樹中葉子結點進行哈夫曼編碼；C.輸出哈夫曼編碼。

3.目標：

掌握哈夫曼樹構造辦法和哈夫曼編碼辦法.

選做功能：（1）對輸入字符串利用上述哈夫曼編碼進行譯碼并輸出譯碼后成果；（2）將已在內存中哈夫曼樹以直觀方式（畫圖）顯示出來。

試驗三哈夫曼編碼實現(xiàn)

(選作)4/11試驗四圖建立和遍歷

1．試驗性質：驗證性試驗2．要求：

A.選擇所建立圖類型（無向圖，有向圖，無向網(wǎng)絡，有向網(wǎng)絡），采取鄰接表存放方式實現(xiàn)；

B.采取深度優(yōu)先/廣度優(yōu)先搜索方式遍歷圖。3.目標：

（1）掌握圖鄰接表存放方式；

（2）掌握圖遍歷方式。5/11試驗五次序查找和折半查找性能比較

1.試驗性質：設計性試驗2.要求：A.對于有序數(shù)組，改善教材上次序查找算法，利用數(shù)組有序性提升查找性能；B.實現(xiàn)折半查找算法；C.對于相同數(shù)組元素，同樣待查值，將上述兩種查找算法進行比較，給出不一樣算法進行比較詳細結論（即比較次數(shù)和移動次數(shù)）。3.目標：

(1)掌握次序查找和折半查找辦法；

(2)比較上述查找辦法性能。6/11試驗五二叉排序樹建立和查找1.試驗性質：設計性試驗2.要求：A.輸入一組整數(shù)構造一棵二叉排序樹；B.二叉排序樹建立過程即是對這組整數(shù)查找和插入過程。3.目標：

掌握二叉排序樹創(chuàng)建、查找和插入操作實現(xiàn)。7/11試驗六多種排序算法時間性能比較1.試驗性質：綜合性試驗2.要求：A.挑選課本中已經(jīng)講過幾個排序算法設計并實現(xiàn)；

B.產(chǎn)生正序和逆序初始排列分別調用上述排序算法，并比較時間性能：

C.產(chǎn)生隨機初始排列分別調用上述排序算法，并比較時間性能。

3.目標:

(1)掌握多種排序算法實現(xiàn)；(2)比較多種排序算法時間性能。8/11試驗六多種排序算法時間性能比較1.試驗性質：綜合性試驗2.要求：A.挑選課本中已經(jīng)講過幾個排序算法設計并實現(xiàn)；

B.產(chǎn)生正序和逆序初始排列分別調用上述排序算法，并比較時間性能：

C.產(chǎn)生隨機初始排列分別調用上述排序算法，并比較時間性能。

注：對于基于比較內排序而言，其時間主要消耗在排序過程中進行元素比較和移動上，因此，統(tǒng)計在相同數(shù)據(jù)狀態(tài)下不一樣排序算法比較次數(shù)和移動次數(shù)，即可實現(xiàn)比較多種排序算法目標。9/11試驗報告規(guī)范一.實驗要求二.實驗目三.設計思想四.主要源代碼五.調試與測試數(shù)據(jù)六.實驗總結開頭：題目班級姓名學號10/11設計思想：將程序提成合理多種模塊（函數(shù)），每個模塊做詳細某一事情,寫出（畫出）設計方案：模塊關系簡圖、流程圖、全局變量、函數(shù)接口等。主要源代碼：函數(shù)調用格式、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間調用關系圖、程序總體執(zhí)行流程圖;主要函數(shù)詳細代碼(加文檔說明).調試與測試數(shù)據(jù)：犯錯次數(shù)、