中法《數據結構》實驗指導書

1、數據結構實驗指導書一、實驗目的數據結構 是計算機專業(yè)一門重要的專業(yè)技術基礎課程，是計算機專業(yè)的一門核心的關鍵性課程。本課程較系統(tǒng)地介紹了軟件設計中常用的數據結構以及相應的存儲結構和實現算法，介紹了常用的多種查找和排序技術，并做了性能分析和比較，內容非常豐富。本課程的學習將為后續(xù)課程的學習以及軟件設計水平的提高打下良好的基礎。 由于以下原因，使得掌握這門課程具有較大的難度： （ 1 ）內容豐富，學習量大，給學習帶來困難； （ 2 ）所用到的技術多，而在此之前的各門課程中所介紹的專業(yè)性知識又不多，因而加大了學習難度； （ 3 ） 隱含在各部分的技術和方法豐富，也是學習的重點和難點。 根據數據結構課

2、程本身的技術特性，設置數據結構課程實驗實踐環(huán)節(jié)十分重要。通過實驗實踐內容的訓練，突出構造性思維訓練的特征 ， 目的是提高學生組織數據及編寫大型程序的能力。 課程上機實驗的目的， 不僅僅是驗證教材和講課的內容， 檢查自己所編的程序是否正確， 課程安排的上機實驗的目的可以概括為如下幾個方面： 1、加深對課堂講授內容的理解實驗是對學生的一種全面綜合訓練。是與課堂聽講、自學和練習相輔相成的必不可少的一個教學環(huán)節(jié)。通常，實驗題中的問題比平時的習題復雜得多，也更接近實際。實驗著眼于原理與應用的結合點，使學生學會如何把書上學到的知識用于解決實際問題，培養(yǎng)軟件工作所需要的動手能力；另一方面，能使書上的知識變&

3、quot;活"，起到深化理解和靈活掌握教學內容的目的。不少學生在解答習題尤其是算法設計題時，覺得無從下手，做起來特別費勁。實驗中的內容和教科書的內容是密切相關的，解決題目要求所需的各種技術大多可從教科書中找到，只不過其出現的形式呈多樣化，因此需要仔細體會，在反復實踐的過程中才能掌握。2、培養(yǎng)學生軟件設計的綜合能力平時的練習較偏重于如何編寫功能單一的"小"算法，而實驗題是軟件設計的綜合訓練，包括問題分析、總體結構設計、用戶界面設計、程序設計基本技能和技巧，多人合作，以至一整套軟件工作規(guī)范的訓練和科學作風的培養(yǎng)。此外，還有很重要的一點是：機器是比任何教師都嚴厲的檢查者

4、。 通過實驗使學生不僅能夠深化理解教學內容，進一步提高靈活運用數據結構、算法和程序設計技術的能力，而且可以在需求分析、總體結構設計、算法設計、程序設計、上機操作及程序調試等基本技能方面受到綜合訓練。實驗著眼于原理與應用的結合點，使學生學會如何把書本上和課堂上學到的知識用于解決實際問題，從而培養(yǎng)計算機軟件工作所需要的動手能力。 3、熟悉程序開發(fā)環(huán)境，學習上機調試程序     一個程序從編輯，編譯，連接到運行，都要在一定的外部操作環(huán)境下才能進行。所謂"環(huán)境"就是所用的計算機系統(tǒng)硬件，軟件條件，只有學會使用這些環(huán)境， 才能進行程序

5、開發(fā)工作。通過上機實驗，熟練地掌握程序的開發(fā)環(huán)境，為以后真正編寫計算機程序解決實際問題打下基礎。同時，在今后遇到其它開發(fā)環(huán)境時就會觸類旁通，很快掌握新系統(tǒng)的使用。      完成程序的編寫，決不意味著萬事大吉。你認為萬無一失的程序，實際上機運行時可能不斷出現麻煩。如編譯程序檢測出一大堆語法錯誤。有時程序本身不存在語法錯誤，也能夠順利運行，但是運行結果顯然是錯誤的。開發(fā)環(huán)境所提供的編譯系統(tǒng)無法發(fā)現這種程序邏輯錯誤，只能靠自己的上機經驗分析判斷錯誤所在。程序的調試是一個技巧性很強的工作，盡快掌握程序調試方法是非常重要的。分析問題，選擇算法，編好程序，只能說完

6、成一半工作，另一半工作就是調試程序，運行程序并得到正確結果。  二、實驗要求常用的軟件開發(fā)方法，是將軟件開發(fā)過程劃分為分析、設計、實現和維護四個階段。雖然數據結構課程中的實驗題目的遠不如從實際問題中的復雜程度度高，但為了培養(yǎng)一個軟件工作者所應具備的科學工作的方法和作風，也應遵循以下五個步驟來完成實驗題目：1問題分析和任務定義在進行設計之前，首先應該充分地分析和理解問題，明確問題要求做什么?限制條件是什么。本步驟強調的是做什么?而不是怎么做。對問題的描述應避開算法和所涉及的數據類型，而是對所需完成的任務作出明確的回答。例如：輸入數據的類型、值的范圍以及輸入的形式；輸出數據的類型、值的范

7、圍及輸出的形式；若是會話式的輸入，則結束標志是什么?是否接受非法的輸入?對非法輸入的回答方式是什么等。還應該為調試程序準備好測試數據，包括合法的輸入數據和非法形式的輸入數據。2邏輯設計和詳細設計在設計這一步驟中需分邏輯設計和詳細設計兩步實現。邏輯設計指的是，對問題描述中涉及的操作對象定義相應的數據類型，并按照以數據結構為中心的原則劃分模塊，定義主程序模塊和各抽象數據類型；詳細設計則為定義相應的存儲結構并寫出各函數的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結構清晰、合理、簡單和易于調試，抽象數據類型的實現盡可能做到數據封裝，基本操作的規(guī)格說明盡可能明確具體。作為邏輯設計的結果，應寫出

8、每個抽象數據類型的定義(包括數據結構的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調用關系圖。詳細設計的結果是對數據結構和基本操作作出進一步的求精，寫出數據存儲結構的類型定義，寫出函數形式的算法框架。在求精的過程中，應盡量避免陷入語言細節(jié)，不必過早表述輔助數據結構和局部變量。3編碼實現和靜態(tài)檢查編碼是把詳細設計的結果進一步求精為程序設計語言程序。如果基于詳細設計的偽碼算法就能直接在鍵盤上輸入程序的話，則可以不必用筆在紙上寫出編碼，而將這一步的工作放在上機準備之后進行，即在上機調試之前直接用鍵盤輸入。 然而，不管你是否寫出編碼的程序，在上機之前，認真的靜態(tài)檢查是必不可少的

9、。靜態(tài)檢查主要有兩種方法，一是用一組測試數據手工執(zhí)行程序(通常應先分模塊檢查)；二是通過對程序深入全面地理解程序邏輯，在這個過程中再加入一些注解和斷言。如果程序中邏輯概念清楚，后者將比前者有效。4上機準備和上機調試上機準備包括以下幾個方面：(1) 注意同一高級語言文本之間的差別。(2)熟悉機器的操作系統(tǒng)和語言集成環(huán)境的用戶手冊，尤其是最常用的命令操作，以便順利進行上機的基本活動。(3)掌握調試工具，考慮調試方案，設計測試數據并手工得出正確結果。應該能夠熟練運用高級語言的程序調試器DBBUG調試程序。(4)上機調試程序時要帶一本高級語言教材或手冊。調試最好分模塊進行，自底向上，即先調試低層函數。

10、在調試過程中可以不斷借助DEBUG的各種功能，提高調試效率。調試中遇到的各種異常現象往往是預料不到的，此時應動手確定疑點，通過修改程序來證實它或繞過它。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果。5總結和整理實驗報告 實驗結束后， 要整理實驗結果并認真分析和總結， 根據教師要求寫出實驗報告。     實驗報告一般包括如下內容： 1 實驗內容  2 實驗目的  3 程序清單4 調試步驟5 運行結果       原始數據， 相應的

11、運行結果和必要的說明。     6 分析與思考       調試過程及調試中遇到的問題及解決辦法;調試程序的心得與體會;其他算法的存在與實踐等。 若最終未完成調試， 要認真找出錯誤并分析原因等。 實驗一、約瑟夫環(huán)【實驗學時】4學時【實驗目的】掌握鏈表的基本操作：插入、刪除、查找等運算，能夠靈活應用鏈表這種數據結構?！締栴}描述】約瑟夫（Joseph）問題的一種描述是：編號為1，2，n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數）。開始任選一個正整數作為報數上限值m，從第一個人開始按順時針

12、方向自1開始順序報數，報到m時停止報數。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數，如此下去，直至所有人全部出列為止。試設計一個程序求出出列順序?！净疽蟆坷脝蜗蜓h(huán)鏈表存儲結構模擬此過程，按照出列的順序印出各人的編號?！緶y試數據】m的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，首先m值為6（正確的出列順序應為6，1，4，7，2，3，5）?！緦崿F提示】程序運行后，首先要求用戶指定初始報數上限值，然后讀取各人的密碼?？稍On30。此題所用的循環(huán)鏈表中不需要“頭結點”，請注意空表和非空表的界限?！具x作內容】向上述程序中添加在順序結構

13、上實現的部分實驗過程：的車輛必須先退出場為它讓路，待該輛車開出大門外，其他車輛再按次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用，試為停車場編制按上述要求進行管理的模擬程序?！净疽蟆恳詶ＤM停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對一組輸入數據進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現。隊列以鏈表

14、結構實現?！緶y試數據】設n=2，輸入數據為：（A，1，5）， （A，2，10）， （D，1，5）， （A，3，20）， （A，4，25）， （A，5，30）， （D，2，35）， （D，4，40）， （E，0，0）。其中：A表示到達（Arrival），D表示離去（Departure），E表示輸入結束（End）?！緦崿F提示】需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現。輸入數據按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數據項：汽車的牌照號碼和進入停車場的時刻。【選作內容】（1） 兩個棧共享空間，思考應開辟數組的空間是多少？（2） 汽車可以

15、有不同種類，則他們的占地面積不同，收費標準也不同，如1輛客車和1。5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。（3） 汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。（4） 停放在便道上的汽車業(yè)收費，收費標準比停放在停車場的車低，請思考如何修改結構以滿足這種要求。實驗三、哈夫曼編/譯碼器【實驗學時】4學時【實驗目的】（1） 掌握二叉樹的存儲結構及其相關操作。（2） 掌握構造哈夫曼樹的基本思想，及其編碼/譯碼過程。【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼

16、系統(tǒng)對待傳輸數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編/譯碼系統(tǒng)?！净疽蟆恳粋€完整的系統(tǒng)應具有以下功能：（1） I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。（2） E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。（3） D：譯碼（Decoding）。利用

17、已經建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。（4） P：打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼，同時將此字符形式的編碼寫入文件CodePrint中。（5） T：打印哈夫曼樹（Tree printing）。將已經在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。【測試數據】（1） 利用教科書例6-2中的數據調試程序。（2） 用下表給出的字符集和頻度的實際統(tǒng)計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“THIS PROGRAM IS

18、 MY FAVORITE”。字符 A B C D E F G H I J K L M頻度186 64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z 頻度57 63 15 1 48 51 80 23 8 18 1 16 1【實現提示】（1） 編碼結果以文本式存儲在文件CodeFile中。（2） 用戶界面可以設計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3） 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令

19、之后，哈夫曼樹已經在內存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。【選作內容】（1） 上述文件CodeFile中的每個“0”或“1”實際上占用了一個字節(jié)的空間，只起到示意或模擬的作用。為最大限度地利用碼點存儲能力，試改寫你的系統(tǒng)，將編碼結果以二進制形式存放在文件CodeFile中。（2） 修改你的系統(tǒng)，實現對你的系統(tǒng)的源程序的編碼和譯碼（主要是將行尾符編/譯碼問題）。（3） 實現各個轉換操作的源/目的文件，均由用戶在選擇此操作時指定。實驗四、圖遍歷的演示?！緦嶒瀸W時】4學時【實驗目的】（1） 掌握圖的基本存儲方法。（2） 熟練掌握圖的兩種搜索路徑的遍歷方法

20、?！締栴}描述】很多涉及圖上操作的算法都是以圖的遍歷操作為基礎的。試寫一個程序，演示連通的無向圖上，遍歷全部結點的操作。【基本要求】以鄰接多重表為存儲結構，實現連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結點為起點，分別輸出每種遍歷下的結點訪問序列和相應生成樹的邊集?！緶y試數據】教科書圖7.33。暫時忽略里程，起點為北京?！緦崿F提示】設圖的結點不超過30個，每個結點用一個編號表示（如果一個圖有n個結點，則它們的編號分別為1，2，n）。通過輸入圖的全部邊輸入一個圖，每個邊為一個數對，可以對邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點順序不能顛倒。【選作內容】（1） 借助于棧類型（自己定義和實現），用非遞歸算法實現深度優(yōu)先遍歷。（2） 以鄰接表為存儲結構，建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再