《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)指導(dǎo)書

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

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

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

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

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

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

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

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

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

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