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

1、算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書.12目 錄第一部分 算法與數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)概述1一實(shí)驗(yàn)?zāi)康?二實(shí)驗(yàn)要求22.1實(shí)驗(yàn)步驟22.2實(shí)驗(yàn)報(bào)告格式3第二部分 上機(jī)實(shí)驗(yàn)內(nèi)容4實(shí)驗(yàn)一 迷宮問題4實(shí)驗(yàn)二 錦標(biāo)賽問題5實(shí)驗(yàn)三 Kruskal算法的設(shè)計(jì)7實(shí)驗(yàn)四 哈夫曼編碼8實(shí)驗(yàn)五 樹和二叉樹9實(shí)驗(yàn)六 查找和排序11附：實(shí)驗(yàn)（設(shè)計(jì)）報(bào)告封面12附：實(shí)驗(yàn)（設(shè)計(jì)）報(bào)告參考格式13其中實(shí)驗(yàn)一、實(shí)驗(yàn)二選擇其中一題完成，實(shí)驗(yàn)三、實(shí)驗(yàn)四選擇其中一題完成。第一部分 算法與數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)概述一實(shí)驗(yàn)?zāi)康乃惴ㄅc數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的主干課程和必修課程之一，其目的是讓大家學(xué)習(xí)、分析和研究數(shù)據(jù)對(duì)象特征，掌握數(shù)據(jù)組織方法和計(jì)算機(jī)的表示方法，以

2、便選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)相應(yīng)的運(yùn)算操作，把現(xiàn)實(shí)世界中的問題轉(zhuǎn)化為計(jì)算機(jī)內(nèi)部的表示與處理的方法，要求掌握算法的時(shí)間、空間復(fù)雜度分析基本技術(shù)，培養(yǎng)良好的程序設(shè)計(jì)風(fēng)格，掌握進(jìn)行復(fù)雜程序設(shè)計(jì)的技能。在計(jì)算機(jī)科學(xué)領(lǐng)域，尤其是在系統(tǒng)軟件和應(yīng)用軟件的設(shè)計(jì)和應(yīng)用中要用到各種數(shù)據(jù)結(jié)構(gòu)，因此，掌握數(shù)據(jù)結(jié)構(gòu)對(duì)提高軟件設(shè)計(jì)和程序編制水平有很大的幫助。二實(shí)驗(yàn)要求2.1實(shí)驗(yàn)步驟 設(shè)計(jì)步驟的規(guī)范不但可以培養(yǎng)學(xué)生科學(xué)的工作方法和作風(fēng)，而且還能有效地減少錯(cuò)誤，提高工作效率。因此必須嚴(yán)格執(zhí)行良好的實(shí)驗(yàn)步驟規(guī)范（包括上機(jī)操作規(guī)范）。本課程實(shí)驗(yàn)的基本步驟是： 2.1.1問題分析 充分地分析和理解問題本身，明確問題要求

3、做什么。對(duì)問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是對(duì)所需完成的任務(wù)作出明確的回答。例如；輸入、輸出數(shù)據(jù)的類型、值的范圍以及形式等。同時(shí)為調(diào)試程序準(zhǔn)備好測試數(shù)據(jù)，包含合法的輸入數(shù)據(jù)和非法形式輸入的數(shù)據(jù)。2.1.2設(shè)計(jì)和編碼設(shè)計(jì)即是對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，定義主程序模塊和各抽象數(shù)據(jù)類型；定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各過程和函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試。 編碼即把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序，寫出源程序。對(duì)程序中的疑問應(yīng)作出記號(hào)，以便上機(jī)時(shí)注意解決。每個(gè)明確的功能模塊程序一般不超過60行，程序的每一行不得

4、超過60個(gè)字符，否則要進(jìn)一步劃分。 2.1.3上機(jī)前程序靜態(tài)檢查 上機(jī)前程序靜態(tài)檢查可有效提高調(diào)試效率，減少上機(jī)調(diào)試程序時(shí)的無謂錯(cuò)誤。 靜態(tài)檢查主要有兩種途徑：用一組測試數(shù)據(jù)手工執(zhí)行程序；通過閱讀或給別人講解自己的程序而深入全面地理解程序邏輯。把程序中的明顯錯(cuò)誤事先排除。2.1.4上機(jī)調(diào)試程序上機(jī)實(shí)驗(yàn)時(shí)要帶上C語言教材、數(shù)據(jù)結(jié)構(gòu)教材、數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)指導(dǎo)書，調(diào)試最好分模塊進(jìn)行，自底向下，即先調(diào)試低層過程或函數(shù)。調(diào)試過程中應(yīng)多動(dòng)手確定疑點(diǎn)，通過修改程序來證明。調(diào)試正確后，認(rèn)真整理源程序及其注釋，寫出或打印出帶有完整注釋的且格式良好的源程序清單和結(jié)果。2.1.5完成上機(jī)實(shí)驗(yàn)報(bào)告2.2實(shí)驗(yàn)報(bào)告格式

5、見附錄。第二部分 上機(jī)實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)一 迷宮問題實(shí)驗(yàn)?zāi)康?熟悉棧用法；2掌握回朔法及試探法程序設(shè)計(jì)技能； 預(yù)習(xí)要求1.認(rèn)真閱讀教材或參考書, 掌握棧和回朔法；2.寫出求解本實(shí)驗(yàn)的程序；3.設(shè)計(jì)好相應(yīng)的測試用例。實(shí)驗(yàn)提示設(shè)迷宮中數(shù)組的元素為1表示該點(diǎn)道路主的阻塞，為0表示可通。設(shè)maze11為入口，mazemn 為出口。在maze11和mazemn的元素值必為0。在任意時(shí)刻，老鼠在迷宮中的位置可以用所在點(diǎn)的行下標(biāo)與列下標(biāo)（i,j）來表示，這樣，老鼠在迷宮中的某點(diǎn)mazeij時(shí)，其可能的運(yùn)動(dòng)方向有八個(gè)。下圖表示某時(shí)刻老鼠所在的位置（i,j）,相鄰的八個(gè)位置分別標(biāo)以N、NE、E、SE、S、SW、W、N

6、W（分別代表點(diǎn)的北、東北、東、東南、南、西南、西、西北方向）；同時(shí)，相對(duì)于（i,j），這八個(gè)相鄰位置的坐標(biāo)的值都可以計(jì)算出來。但是，并非迷宮中的每一個(gè)點(diǎn)都有八個(gè)方向可走，四個(gè)角上就只有三個(gè)方向可供選擇，邊上只有五個(gè)方向可供選擇。為了不在算法中每次都去檢查這些邊界條件，在迷宮外面套上一圈，其元素值均為1。實(shí)驗(yàn)步驟1 先設(shè)計(jì)好迷宮，并測試你的程序，直至正確為止；2 將你的程序和實(shí)錄的界面存盤備用。 實(shí)驗(yàn)報(bào)告要求1 闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容；2 提交模塊化的實(shí)驗(yàn)程序源代碼；3 簡述程序的測試過程，提交實(shí)錄的輸入、輸出文件；思考與練習(xí) 寫出用隊(duì)列求解迷宮問題的算法。實(shí)驗(yàn)二 錦標(biāo)賽問題 實(shí)驗(yàn)?zāi)康?. 基本

7、掌握分治算法的原理.2. 能用程序設(shè)計(jì)語言求解錦標(biāo)賽等問題的算法;預(yù)習(xí)要求1. 認(rèn)真閱讀數(shù)據(jù)結(jié)構(gòu)教材和算法設(shè)計(jì)教材,了解分治算法原理;2. 設(shè)計(jì)用分治算法求解背包問題的數(shù)據(jù)結(jié)構(gòu)與程序代碼.實(shí)驗(yàn)題【問題描述】設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：（1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次； （2）每個(gè)選手一天只能參賽一次； （3）循環(huán)賽在n-1天內(nèi)結(jié)束。 請按此要求將比賽日程表設(shè)計(jì)成有n行和n-1列的一個(gè)表。在表中的第i行，第j列處填入第i個(gè)選手在第j天所遇到的選手。其中1in，1jn-1。 實(shí)驗(yàn)提示我們可以按分治策略將所有的選手分為兩半，則n個(gè)選手的比賽

8、日程表可以通過n/2個(gè)選手的比賽日程表來決定。遞歸地用這種一分為二的策略對(duì)選手進(jìn)行劃分，直到只剩下兩個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這兩個(gè)選手進(jìn)行比賽就可以了。12345671234567821436785341278561234321856712345678143212143658721431234127856321421432187654321（1） （2） （3）圖1 2個(gè)、4個(gè)和8個(gè)選手的比賽日程表圖1所列出的正方形表（3）是8個(gè)選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對(duì)位置

9、抄到右下角，又將左下角小塊中的所有數(shù)字按其相對(duì)位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個(gè)比賽日程表推廣到具有任意多個(gè)選手的情形。 實(shí)驗(yàn)步驟1. 設(shè)計(jì)并實(shí)現(xiàn)算法并準(zhǔn)備測試用例,修改并調(diào)試程序,直至正確為止;2. 應(yīng)用設(shè)計(jì)的算法和程序求錦標(biāo)賽問題;3. 去掉測試程序,將你的程序整理成功能模塊存盤備用. 實(shí)驗(yàn)報(bào)告要求1. 闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容;2. 闡述分治算法原理;3. 提交實(shí)驗(yàn)程序的功能模塊;4. 記錄最終測試數(shù)據(jù)和測試結(jié)果。思考與練習(xí)考慮n（n0，為任意自然數(shù)）個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽的問題實(shí)現(xiàn)。 實(shí)驗(yàn)三 Kruskal算法的設(shè)

10、計(jì)實(shí)驗(yàn)?zāi)康? 根據(jù)算法設(shè)計(jì)需要, 掌握連通網(wǎng)的靈活表示方法;. 掌握最小生成樹的Kruskal算法;. 基本掌握貪心算法的一般設(shè)計(jì)方法;. 進(jìn)一步掌握集合的表示與操作算法的應(yīng)用.預(yù)習(xí)要求. 認(rèn)真閱讀算法設(shè)計(jì)教材和數(shù)據(jù)結(jié)構(gòu)教材內(nèi)容, 熟習(xí)連通網(wǎng)的不同表示方法和最小生成樹算法;. 設(shè)計(jì)Kruskal算法實(shí)驗(yàn)程序. 實(shí)驗(yàn)步驟1. 設(shè)計(jì)測試問題,修改并調(diào)試程序, 輸出最小生成樹的各條邊, 直至正確為止;2. 待各功能子程序調(diào)試完畢, 去掉測試程序, 將你的程序整理成功能模塊存盤備用.實(shí)驗(yàn)報(bào)告要求1. 闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容;2. 闡述Kruskal算法的原理方法;3. 提交實(shí)驗(yàn)程序的功能模塊;4. 提

11、供測試數(shù)據(jù)和相應(yīng)的最小生成樹.思考與練習(xí) 用C語言實(shí)現(xiàn)Prim算法. 實(shí)驗(yàn)四 哈夫曼編碼 實(shí)驗(yàn)?zāi)康? 根據(jù)算法設(shè)計(jì)需要,掌握哈夫曼編碼的二叉樹結(jié)構(gòu)表示方法;. 編程實(shí)現(xiàn)哈夫曼編譯碼器;. 掌握貪心算法的一般設(shè)計(jì)方法。預(yù)習(xí)要求1. 認(rèn)真閱讀數(shù)據(jù)結(jié)構(gòu)教材和算法設(shè)計(jì)教材內(nèi)容, 熟悉哈夫曼編碼的原理;2. 設(shè)計(jì)和編制哈夫曼編譯碼器。 實(shí)驗(yàn)步驟1. 設(shè)計(jì)SetTree的測試方案和程序,輸入測試數(shù)據(jù),修改并調(diào)試程序,直至正確為止;2. 設(shè)計(jì)EnCode的測試方案和程序,輸入測試數(shù)據(jù),修改并調(diào)試程序,直至正確為止;3. 設(shè)計(jì)DeCode的測試方案和程序,輸入測試數(shù)據(jù),修改并調(diào)試程序,直至正確為止;4. 將你

12、的程序整理成功能模塊存盤備用。實(shí)驗(yàn)報(bào)告要求1. 闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容;2. 提交實(shí)驗(yàn)程序的功能模塊;3. 記錄最終測試數(shù)據(jù)和測試結(jié)果。思考題1. 試證明哈夫曼問題具有貪心選擇性質(zhì)；2. 試證明哈夫曼問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。實(shí)驗(yàn)五 樹和二叉樹一、 實(shí)驗(yàn)?zāi)康?. 掌握二叉樹，二叉樹排序數(shù)的概念及存儲(chǔ)方法。2. 掌握二叉樹的遍歷算法。3. 熟練掌握編寫實(shí)現(xiàn)樹的各種運(yùn)算的算法。4.熟悉圖的各種存儲(chǔ)方法。5.掌握遍歷圖的遞歸和非遞歸的算法。6. 理解圖的有關(guān)算法。二、實(shí)驗(yàn)內(nèi)容1. 用二叉樹表示代數(shù)表達(dá)式并輸出代數(shù)表達(dá)式的前綴式和后綴式要求及提示：編寫一個(gè)程序，用二叉樹來表示代數(shù)表達(dá)式，樹的每個(gè)結(jié)點(diǎn)包括

13、一個(gè)運(yùn)算符，代數(shù)表達(dá)式由輸入得到（其中只包含=，+，-，*，/和用一個(gè)字母表示的數(shù)且沒有錯(cuò)誤，并且按照先乘除后加減的原則），試編寫程序輸出表達(dá)式的前綴式和后綴式。實(shí)驗(yàn)數(shù)據(jù)：X:=(-b+(b2-4*a*c)0.5)/(2*a)2. 求二叉樹中從根結(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑要求及提示對(duì)于1中的代數(shù)表達(dá)式二叉樹，分別用遞歸和非遞歸的方法編寫程序完成如下功能：1 輸出所有的葉子結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)值。2 輸出所有從葉子節(jié)點(diǎn)到根結(jié)點(diǎn)的路徑3. 實(shí)現(xiàn)圖的鄰接矩陣和鄰接表存儲(chǔ)要求及提示對(duì)于下圖所示的有向圖G，編寫一個(gè)程序完成如下功能：1 建立G的鄰接表存儲(chǔ)結(jié)構(gòu)2 輸出下圖的拓?fù)渑判蛐蛄? 編寫一個(gè)程序輸出從頂點(diǎn)0開始的

14、深度優(yōu)先遍歷序列（遞歸算法）和廣度優(yōu)先遍歷序列（非遞歸算法）。實(shí)驗(yàn)六 查找和排序?qū)嶒?yàn)?zāi)康?. 掌握順序查找，二分法查找，分塊查找的算法。2掌握各種排序算法及其性能的比較實(shí)驗(yàn)內(nèi)容1編寫一個(gè)程序輸出在順序表13，22，35，43，54，68，71，82，98，1005中采用順序方法和折半方法查找某個(gè)關(guān)鍵字的過程。2編寫一個(gè)程序?qū)崿F(xiàn)直接插入排序過程，并輸出94，28，57，66，35，84，63，42，71，10的排序過程3編寫一個(gè)程序?qū)崿F(xiàn)快速排序算法，并輸出94，28，57，66，35，84，63，42，71，10的排序過程。實(shí)驗(yàn)報(bào)告要求1. 闡述實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)內(nèi)容;2. 提交實(shí)驗(yàn)程序的功能模塊;3. 記錄最終測試數(shù)據(jù)和測試結(jié)果。附：實(shí)驗(yàn)（設(shè)計(jì)）報(bào)告封面信息科學(xué)與工程學(xué)院 實(shí)驗(yàn)報(bào)告 系 別 專 業(yè) 年 級(jí) 姓 名 學(xué) 號(hào) 指導(dǎo)教師 學(xué)年 第 學(xué)期附：實(shí)驗(yàn)（設(shè)計(jì)）報(bào)告參考格式設(shè)計(jì)一題目一、 設(shè)計(jì)目的二、 設(shè)計(jì)內(nèi)容1 任務(wù)描述2 問題的表示方案3 主要數(shù)據(jù)類型與變量typedef NodeNumber int; /* 節(jié)點(diǎn)編號(hào) */typedef CostType int; /* 成本值類型 */（必要時(shí)，可對(duì)數(shù)據(jù)類型和變量進(jìn)一步解釋或說明，增加可讀性）4 算法或程序模塊int FindForward(CostType *costn, No