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

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)1 順序表一、實(shí)驗(yàn)?zāi)康模?）掌握順序表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及描述方式。（2）掌握順序表的定位、插入、刪除等操作。二、實(shí)驗(yàn)要求（1）調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；（2）給出每個(gè)問題的算法或畫出流程圖；（3）編寫程序要規(guī)范、正確，上機(jī)調(diào)試過程和結(jié)果要有記錄，并注意調(diào)試程序集成環(huán)境的掌握及應(yīng)用，不斷積累編程及調(diào)試經(jīng)驗(yàn)；（4）做完實(shí)驗(yàn)后給出本實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)設(shè)備、環(huán)境奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0或Visual C+軟件四、實(shí)驗(yàn)步驟及內(nèi)容實(shí)驗(yàn)步驟：1根據(jù)題目，編寫程序。2上機(jī)調(diào)試通過。3按照金陵科技學(xué)院實(shí)驗(yàn)報(bào)告格式，撰寫各實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)

2、容：（1）編寫一個(gè)函數(shù)print_all_data，該函數(shù)的作用是逐個(gè)輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)，從鍵盤輸入順序表，調(diào)用函數(shù)print_all_data，測(cè)試結(jié)果。（2）編寫順序表定位操作函數(shù)locata，該函數(shù)的作用是在順序表中查找是否存在數(shù)據(jù)元素的值與變量x的值相等。如果存在滿足條件的數(shù)據(jù)元素，則返回順序表中和x值相等的第1個(gè)數(shù)據(jù)元素在表中的下標(biāo)；如果不存在，則返回1。編寫主函數(shù)，從鍵盤輸入順序表，以及變量x的值，調(diào)用函數(shù)locate，測(cè)試結(jié)果。（3）編寫一個(gè)函數(shù)insert，該函數(shù)的作用是在遞增有序的順序表中插入一個(gè)新結(jié)點(diǎn)x，要求保持順序表的有序性，輸出插入前后順序表狀態(tài)。

3、編寫主函數(shù)，從鍵盤輸入順序表以及變量x的值，調(diào)用函數(shù)insert，測(cè)試結(jié)果。（4）編寫一個(gè)函數(shù)delete，該函數(shù)的作用是刪除順序表中所有等于X的數(shù)據(jù)元素。若順序表中沒有滿足條件的數(shù)據(jù)元素，則輸出合適的信息。若有滿足條件的數(shù)據(jù)元素，則輸出刪除前后順序表狀態(tài)。編寫主函數(shù)，從鍵盤輸入順序表以及變量x的值，調(diào)用函數(shù)delete，測(cè)試結(jié)果。五、討論、思考題1、如何在排列有序的順序表中插入新元素，而保證順序表的有序性？2、如何在排列有序的順序表中刪除某元素，而保證順序表的有序性？實(shí)驗(yàn)2 單鏈表一、實(shí)驗(yàn)?zāi)康模?）掌握單鏈表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及描述方式。（2）掌握單鏈表的定位、插入、刪除等操作。二、實(shí)驗(yàn)要

4、求（1）調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；（2）給出每個(gè)問題的算法或畫出流程圖；（3）編寫程序要規(guī)范、正確，上機(jī)調(diào)試過程和結(jié)果要有記錄，并注意調(diào)試程序集成環(huán)境的掌握及應(yīng)用，不斷積累編程及調(diào)試經(jīng)驗(yàn)；（4）做完實(shí)驗(yàn)后給出本實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)設(shè)備、環(huán)境奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0或Visual C+軟件四、實(shí)驗(yàn)步驟及內(nèi)容實(shí)驗(yàn)步驟：1根據(jù)題目，編寫程序。2上機(jī)調(diào)試通過。3按照金陵科技學(xué)院實(shí)驗(yàn)報(bào)告格式，撰寫各實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容：（1）編寫函數(shù)print_all_data，該函數(shù)的作用是逐個(gè)輸出單鏈表中所有數(shù)據(jù)元素的值。編寫主函數(shù)，從鍵盤輸入單鏈表的內(nèi)容，調(diào)用函數(shù)print

5、_all_data，測(cè)試結(jié)果。（2）編寫函數(shù)insert，在遞增有序的單鏈表中插入一個(gè)新結(jié)點(diǎn)x，保持單鏈表的有序性。編寫主函數(shù)，從鍵盤輸入單鏈表以及變量x的值，調(diào)用函數(shù)insert，測(cè)試結(jié)果。（3）編寫函數(shù)，實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表就地逆置的功能，并編寫主函數(shù)測(cè)試結(jié)果。五、討論、思考題1、如何在排列有序的單鏈表表中插入新元素，而保證順序表的有序性？2、如何在排列有序的單鏈表中刪除某元素，而保證順序表的有序性？3、如何計(jì)算帶有頭結(jié)點(diǎn)的單鏈表的長度，將計(jì)算結(jié)果記錄在頭結(jié)點(diǎn)的數(shù)據(jù)域中？實(shí)驗(yàn)3 堆棧和隊(duì)列一、實(shí)驗(yàn)?zāi)康模?）掌握應(yīng)用棧解決問題的方法。（2）掌握利用棧進(jìn)行表達(dá)式求和的算法。二、實(shí)驗(yàn)要求（1）調(diào)試

6、程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；（2）給出每個(gè)問題的算法或畫出流程圖；（3）編寫程序要規(guī)范、正確，上機(jī)調(diào)試過程和結(jié)果要有記錄，并注意調(diào)試程序集成環(huán)境的掌握及應(yīng)用，不斷積累編程及調(diào)試經(jīng)驗(yàn)；（4）做完實(shí)驗(yàn)后給出本實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)設(shè)備、環(huán)境奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0或Visual C+軟件四、實(shí)驗(yàn)步驟及內(nèi)容實(shí)驗(yàn)步驟：1 根據(jù)題目，編寫程序。2 上機(jī)調(diào)試通過。3 按照金陵科技學(xué)院實(shí)驗(yàn)報(bào)告格式，撰寫各實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容：（1）判斷一個(gè)算術(shù)表達(dá)式中開括號(hào)和閉括號(hào)是否配對(duì)。提示：對(duì)表達(dá)式進(jìn)行掃描，凡是遇到（就進(jìn)棧，遇到）就退掉棧頂?shù)模ǎ磉_(dá)式被掃描完畢時(shí)，棧應(yīng)為空。此時(shí)，開

7、閉括號(hào)為配對(duì)，否則不配對(duì)。（2）設(shè)單鏈表中存放著n個(gè)字符，試編寫算法，判斷該字符串是否有中心對(duì)稱關(guān)系，例如xyzzyx、xyzyx都是中心對(duì)稱的字符串。要求用盡可能少的時(shí)間完成判斷。 提示：將一半字符先依次進(jìn)棧。要考慮字符串長為奇數(shù)的情況。（3）假設(shè)算術(shù)表達(dá)式僅由加減乘除運(yùn)算符組成，編寫一個(gè)函數(shù)對(duì)用后綴表達(dá)式表示的算術(shù)表達(dá)式求值。要求使用順序堆棧。五、討論、思考題1、如何判斷堆棧（順序棧、鏈棧）棧滿和棧空？2、如何判斷隊(duì)列（順序隊(duì)列、循環(huán)隊(duì)列、鏈隊(duì)列）隊(duì)滿和隊(duì)空？3、如何在堆棧（順序棧、鏈棧）中壓入和彈出元素？4、如何在隊(duì)列（順序隊(duì)列、循環(huán)隊(duì)列、鏈隊(duì)列）中插入和刪除元素？實(shí)驗(yàn)4 串、遞歸算法一

8、、實(shí)驗(yàn)?zāi)康模?）掌握串的應(yīng)用。（2）掌握遞歸算法的設(shè)計(jì)方法。二、實(shí)驗(yàn)要求（1）調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；（2）給出每個(gè)問題的算法或畫出流程圖；（3）編寫程序要規(guī)范、正確，上機(jī)調(diào)試過程和結(jié)果要有記錄，并注意調(diào)試程序集成環(huán)境的掌握及應(yīng)用，不斷積累編程及調(diào)試經(jīng)驗(yàn)；（4）做完實(shí)驗(yàn)后給出本實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)設(shè)備、環(huán)境奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0或Visual C+軟件四、實(shí)驗(yàn)步驟及內(nèi)容實(shí)驗(yàn)步驟：1根據(jù)題目，編寫程序。2上機(jī)調(diào)試通過。3按照金陵科技學(xué)院實(shí)驗(yàn)報(bào)告格式，撰寫各實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容：（1）設(shè)字符串采用靜態(tài)數(shù)組存儲(chǔ)結(jié)構(gòu)。編寫輸出字符串s中值等于字符ch的第一個(gè)

9、字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。（2）設(shè)字符串采用靜態(tài)數(shù)組存儲(chǔ)結(jié)構(gòu)。編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。（3）設(shè)字符串采用單字符的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編程刪除串s從位置i開始長度為k的子串。（4）測(cè)試“漢諾塔”問題。（5）Ackerman函數(shù)的定義如下： n+1 當(dāng)m=0時(shí) AKM(m,n)= AKM(m-1,1) 當(dāng)m<>0,n=0時(shí) AKM(m-1,AKM(m,n-1) 當(dāng)m<>0,n<>0時(shí)請(qǐng)寫出遞歸算法。五、討論、思考題1、串是如何存儲(chǔ)的？2、遞歸算法是如何執(zhí)行的？實(shí)驗(yàn)5 二叉樹一、實(shí)驗(yàn)?zāi)康模?）掌握二叉樹的生成，以及前、

10、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問題的方法。二、實(shí)驗(yàn)要求（1）調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；（2）給出每個(gè)問題的算法或畫出流程圖；（3）編寫程序要規(guī)范、正確，上機(jī)調(diào)試過程和結(jié)果要有記錄，并注意調(diào)試程序集成環(huán)境的掌握及應(yīng)用，不斷積累編程及調(diào)試經(jīng)驗(yàn)；（4）做完實(shí)驗(yàn)后給出本實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)設(shè)備、環(huán)境奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0或Visual C+軟件四、實(shí)驗(yàn)步驟及內(nèi)容實(shí)驗(yàn)步驟：1根據(jù)題目，編寫程序。2上機(jī)調(diào)試通過。3按照金陵科技學(xué)院實(shí)驗(yàn)報(bào)告格式，撰寫各實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容：（1）建立一棵二叉樹。對(duì)此樹進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷

11、序列。（2）求二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。（3）寫出在前序線索二叉樹中查找給定結(jié)點(diǎn)*P的前序后繼的算法。（4）假設(shè)通訊電文由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為：7，19，2，6，32，3，21，10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。五、討論、思考題1、二叉樹是如何存儲(chǔ)的？2、二叉樹有哪些遍歷算法？這些遍歷算法有何特點(diǎn)？3、找出分別滿足下面條件的所有二叉樹：（1）前序序列和中序序列相同；（2）前序序列和后序序列相同；（3）后序序列和中序序列相同；4、若以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，如何求二叉樹高度？提示：用遞歸的方法。實(shí)驗(yàn)6 圖一、實(shí)驗(yàn)?zāi)康模?）熟練掌握?qǐng)D的基本概念、構(gòu)造及其存儲(chǔ)結(jié)構(gòu)。（2）熟練掌握對(duì)圖

12、的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。二、實(shí)驗(yàn)要求（1）調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；（2）給出每個(gè)問題的算法或畫出流程圖；（3）編寫程序要規(guī)范、正確，上機(jī)調(diào)試過程和結(jié)果要有記錄，并注意調(diào)試程序集成環(huán)境的掌握及應(yīng)用，不斷積累編程及調(diào)試經(jīng)驗(yàn)；（4）做完實(shí)驗(yàn)后給出本實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)設(shè)備、環(huán)境奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0或Visual C+軟件四、實(shí)驗(yàn)步驟及內(nèi)容實(shí)驗(yàn)步驟：1根據(jù)題目，編寫程序。2上機(jī)調(diào)試通過。3按照金陵科技學(xué)院實(shí)驗(yàn)報(bào)告格式，撰寫各實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容：1構(gòu)造一個(gè)無向圖，要求用鄰接矩陣表示存儲(chǔ)結(jié)構(gòu)。2對(duì)上面構(gòu)造的無向圖，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)

13、先遍歷，分別輸出遍歷序列。3構(gòu)造一個(gè)連通網(wǎng)絡(luò)，分別用PRIM算法和KRUSKAL算法構(gòu)造該網(wǎng)絡(luò)的最小生成樹。五、討論、思考題1、圖是如何存儲(chǔ)的？2、如何從一個(gè)無向圖的鄰接矩陣（或鄰接表）中，判斷圖中有多少條邊？任意兩個(gè)頂點(diǎn)i和j是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？3、圖有哪些遍歷算法，這些算法之間有何區(qū)別？實(shí)驗(yàn)7 排序一、實(shí)驗(yàn)?zāi)康模?）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。（2）掌握以上各種排序的算法。（3）區(qū)分以上不同排序的優(yōu)、缺點(diǎn)。二、實(shí)驗(yàn)要求（1）調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；（2）給出每個(gè)問題的算法或畫

14、出流程圖；（3）編寫程序要規(guī)范、正確，上機(jī)調(diào)試過程和結(jié)果要有記錄，并注意調(diào)試程序集成環(huán)境的掌握及應(yīng)用，不斷積累編程及調(diào)試經(jīng)驗(yàn)；（4）做完實(shí)驗(yàn)后給出本實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)設(shè)備、環(huán)境奔騰以上計(jì)算機(jī)，裝有Turbo C 2.0或Visual C+軟件四、實(shí)驗(yàn)步驟及內(nèi)容實(shí)驗(yàn)步驟：1根據(jù)題目，編寫程序。2上機(jī)調(diào)試通過。3按照金陵科技學(xué)院實(shí)驗(yàn)報(bào)告格式，撰寫各實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容：用隨機(jī)數(shù)產(chǎn)生100000個(gè)待排序數(shù)據(jù)元素的關(guān)鍵字值。測(cè)試下列各排序函數(shù)的機(jī)器實(shí)際執(zhí)行時(shí)間（至少測(cè)試兩個(gè)）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、二路歸并排序、堆排序和基于鏈?zhǔn)疥?duì)列的基數(shù)排序。五、討論、思考題1、排序方法有哪些？各有哪些特點(diǎn)？2、什么是排序方法的穩(wěn)定性？哪些排序方法是穩(wěn)定的，哪些又是不穩(wěn)定的？實(shí)驗(yàn)8 查找一、實(shí)驗(yàn)?zāi)康模?）掌握順序表查找、有序表查找、索引順序表查找的各種算法。（2）掌握哈希表設(shè)計(jì)。二、實(shí)驗(yàn)要求（1）調(diào)試程序要記錄調(diào)試過程中出現(xiàn)的問題及解決辦法；（2）給出每個(gè)問題的算法或畫出流程圖；（3）編寫程序要規(guī)范、正確，上機(jī)調(diào)試過程和結(jié)果要有記錄，并注意調(diào)試程序集成環(huán)境的掌握及應(yīng)用，不斷積累編程及調(diào)試經(jīng)驗(yàn)；（4）做完