《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導書

1、數(shù)據(jù)結(jié)構(gòu)與算法實驗指導書數(shù)據(jù)結(jié)構(gòu)與算法實驗指導書 PAGE PAGE 160數(shù)據(jù)結(jié)構(gòu)與算法實驗指導書實驗 1 順序表一、實驗目的掌握順序表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及描述方式。掌握順序表的定位、插入、刪除等操作。二、實驗要求調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；給出每個問題的算法或畫出流程圖；的掌握及應用，不斷積累編程及調(diào)試經(jīng)驗；做完實驗后給出本實驗的實驗報告。三、實驗設備、環(huán)境奔騰以上計算機，裝有Turbo C 2.0Visual 四、實驗步驟及內(nèi)容實驗步驟： 1上機調(diào)試通過。實驗內(nèi)容：編寫一個函數(shù) print_all_data值。編寫主函數(shù)，從鍵盤輸入順序表，調(diào)用函數(shù)print_all_

2、data，測試結(jié)果。編寫順序表定位操作函數(shù) locata，該函數(shù)的作用是在順序表中查找是否存在數(shù)據(jù)元素的值與變量x 的值相等。如果存在滿足條件的數(shù)據(jù)元素，則返回順序表中和x 值相等的第 1 入順序表，以及變量x 的值，調(diào)用函數(shù)locate，測試結(jié)果。編寫一個函數(shù)insert，該函數(shù)的作用是在遞增有序的順序表中插入一個新結(jié)點x， 以及變量x的值，調(diào)用函數(shù)insert，測試結(jié)果。編寫一個函數(shù) delete，該函數(shù)的作用是刪除順序表中所有等于X 的數(shù)據(jù)元素。若輸出刪除前后順序表狀態(tài)。編寫主函數(shù)，從鍵盤輸入順序表以及變量x 的值，調(diào)用函數(shù)delete，測試結(jié)果。五、討論、思考題1、如何在排列有序的順序

3、表中插入新元素，而保證順序表的有序性？2、如何在排列有序的順序表中刪除某元素，而保證順序表的有序性？實驗 2 單鏈表一、實驗目的掌握單鏈表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及描述方式。掌握單鏈表的定位、插入、刪除等操作。二、實驗要求調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；給出每個問題的算法或畫出流程圖；的掌握及應用，不斷積累編程及調(diào)試經(jīng)驗；做完實驗后給出本實驗的實驗報告。三、實驗設備、環(huán)境奔騰以上計算機，裝有Turbo C 2.0Visual 四、實驗步驟及內(nèi)容實驗步驟： 1上機調(diào)試通過。實驗內(nèi)容：編寫函數(shù) print_all_data編寫主函數(shù)，從鍵盤輸入單鏈表的內(nèi)容，調(diào)用函數(shù)print_all_d

4、ata，測試結(jié)果。編寫函數(shù) x的值，調(diào)用函數(shù)insert，測試結(jié)果。編寫函數(shù)，實現(xiàn)帶頭結(jié)點單鏈表就地逆置的功能，并編寫主函數(shù)測試結(jié)果。五、討論、思考題1、如何在排列有序的單鏈表表中插入新元素，而保證順序表的有序性？2、如何在排列有序的單鏈表中刪除某元素，而保證順序表的有序性？3、如何計算帶有頭結(jié)點的單鏈表的長度，將計算結(jié)果記錄在頭結(jié)點的數(shù)據(jù)域中？實驗 3 堆棧和隊列一、實驗目的掌握應用棧解決問題的方法。掌握利用棧進行表達式求和的算法。二、實驗要求調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；給出每個問題的算法或畫出流程圖；的掌握及應用，不斷積累編程及調(diào)試經(jīng)驗；做完實驗后給出本實驗的實驗報告。三

5、、實驗設備、環(huán)境奔騰以上計算機，裝有Turbo C 2.0Visual 四、實驗步驟及內(nèi)容實驗步驟：根據(jù)題目，編寫程序。上機調(diào)試通過。實驗內(nèi)容：判斷一個算術表達式中開括號和閉括號是否配對。提示：對表達式進行掃描，凡是遇到（就進棧，遇到就退掉棧頂?shù)谋磉_式被掃描完畢時，棧應為空。此時，開閉括號為配對，否則不配對。設單鏈表中存放著n xyzzyx、xyzyx都是中心對稱的字符串。要求用盡可能少的時間完成判斷。提示：將一半字符先依次進棧。要考慮字符串長為奇數(shù)的情況。術表達式求值。要求使用順序堆棧。五、討論、思考題1、如何判斷堆棧（順序棧、鏈棧）棧滿和棧空？2、如何判斷隊列（順序隊列、循環(huán)隊列、鏈隊列）

6、隊滿和隊空？3、如何在堆棧（順序棧、鏈棧）中壓入和彈出元素？4、如何在隊列（順序隊列、循環(huán)隊列、鏈隊列）中插入和刪除元素？實驗 4 串、遞歸算法一、實驗目的掌握串的應用。掌握遞歸算法的設計方法。二、實驗要求調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；給出每個問題的算法或畫出流程圖；的掌握及應用，不斷積累編程及調(diào)試經(jīng)驗；做完實驗后給出本實驗的實驗報告。三、實驗設備、環(huán)境奔騰以上計算機，裝有Turbo C 2.0Visual 四、實驗步驟及內(nèi)容實驗步驟： 1上機調(diào)試通過。實驗內(nèi)容：設字符串采用靜態(tài)數(shù)組存儲結(jié)構(gòu)。編寫輸出字符串s 中值等于字符 ch 符的函數(shù)，并用主函數(shù)測試結(jié)果。設字符串采用靜態(tài)數(shù)

7、組存儲結(jié)構(gòu)。編寫輸出字符串s 中值等于字符 ch 的函數(shù)，并用主函數(shù)測試結(jié)果。s從位置i開始長度為k的子串。測試“漢諾塔”問題。Ackerman函數(shù)的定義如下：AKM(m,n)=n+1AKM(m-1,1)當m=0 時當m0,n=0 時請寫出遞歸算法。AKM(m-1,AKM(m,n-1)當m0,n0 時五、討論、思考題1、串是如何存儲的？2、遞歸算法是如何執(zhí)行的？實驗 5 二叉樹一、實驗目的掌握二叉樹的生成，以及前、中、后序遍歷算法。掌握應用二叉樹遞歸遍歷思想解決問題的方法。二、實驗要求調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；給出每個問題的算法或畫出流程圖；的掌握及應用，不斷積累編程及調(diào)試

8、經(jīng)驗；做完實驗后給出本實驗的實驗報告。三、實驗設備、環(huán)境奔騰以上計算機，裝有Turbo C 2.0Visual 四、實驗步驟及內(nèi)容實驗步驟：根據(jù)題目，編寫程序。上機調(diào)試通過。實驗內(nèi)容：建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。求二叉樹中葉結(jié)點的個數(shù)。*P的前序后繼的算法。832，3，21，10。試為這 8 個字母設計哈夫曼編碼。五、討論、思考題1、二叉樹是如何存儲的？2、二叉樹有哪些遍歷算法？這些遍歷算法有何特點？3、找出分別滿足下面條件的所有二叉樹：前序序列和中序序列相同；前序序列和后序序列相同；后序序列和中序序列相同；4、若以二叉鏈表作存儲結(jié)構(gòu)，如何求二叉樹高度

9、？提示：用遞歸的方法。實驗 6 圖一、實驗目的熟練掌握圖的基本概念、構(gòu)造及其存儲結(jié)構(gòu)。熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。二、實驗要求調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；給出每個問題的算法或畫出流程圖；的掌握及應用，不斷積累編程及調(diào)試經(jīng)驗；做完實驗后給出本實驗的實驗報告。三、實驗設備、環(huán)境奔騰以上計算機，裝有Turbo C 2.0Visual 四、實驗步驟及內(nèi)容實驗步驟：根據(jù)題目，編寫程序。上機調(diào)試通過。實驗內(nèi)容：構(gòu)造一個無向圖，要求用鄰接矩陣表示存儲結(jié)構(gòu)。對上面構(gòu)造的無向圖，進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，分別輸出遍歷序列。PRIM 算法和KRUSKAL 算法構(gòu)

10、造該網(wǎng)絡的最小生成樹。五、討論、思考題1、圖是如何存儲的？2、如何從一個無向圖的鄰接矩陣（或鄰接表）ij3、圖有哪些遍歷算法，這些算法之間有何區(qū)別？實驗 7 排序一、實驗目的歸并排序和基數(shù)排序的基本概念。掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點。二、實驗要求調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；給出每個問題的算法或畫出流程圖；的掌握及應用，不斷積累編程及調(diào)試經(jīng)驗；做完實驗后給出本實驗的實驗報告。三、實驗設備、環(huán)境奔騰以上計算機，裝有Turbo C 2.0Visual 四、實驗步驟及內(nèi)容實驗步驟：根據(jù)題目，編寫程序。上機調(diào)試通過。實驗內(nèi)容：100000 個待排序數(shù)據(jù)元素的關鍵字值。測試下列各排序函數(shù)的機器實際執(zhí)（至少測試兩個（增量為4直接選擇排序、二路歸并排序、堆排序和基于鏈式隊列的基數(shù)排序。五、討論、思考題1、排序方法有哪些？各有哪些特點？2、什么是排序方法的穩(wěn)定性？哪些排序方法是穩(wěn)定的，哪些又是不穩(wěn)定的？實驗 8 查找一、實驗目的掌握順序表查找、有序表查找、索引順序表查找的各種算法。掌握哈希表設計。二、實驗要求調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；給出每個問題的算法或畫出流程圖；的掌握及應用，不斷積累