《數(shù)據(jù)結構與算法》實驗指導書2015

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

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

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

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

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

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

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

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

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

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

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

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

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

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