數(shù)據(jù)結構程2016實驗指導書課案

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

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

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

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

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

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

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

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

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

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

11、0;  (6)分析與思考: 調(diào)試過程及調(diào)試中遇到的問題及解決辦法;調(diào)試程序的心得與體會;其他算法的存在與實踐等。 若最終未完成調(diào)試， 要認真找出錯誤并分析原因等。 三、實驗內(nèi)容實驗一 Joseph問題求解算法的設計與實現(xiàn)1、實驗學時2學時2、實驗目的掌握鏈表的基本操作：插入、刪除、查找等運算，能夠靈活應用鏈表這種數(shù)據(jù)結構。3、問題描述約瑟夫（Joseph）問題的一種描述是：編號為1，2，n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的

12、m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止。試設計一個程序求出出列順序。4、基本要求利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序印出各人的編號。5、測試數(shù)據(jù)m的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，首先m值為6（正確的出列順序應為6，1，4，7，2，3，5）。6、實現(xiàn)提示程序運行后，首先要求用戶指定初始報數(shù)上限值，然后讀取各人的密碼。可設n30。此題所用的循環(huán)鏈表中不需要“頭結點”，請注意空表和非空表的界限。7、選作內(nèi)容向上述程序中添加在順序結構上實現(xiàn)的部分。實驗二 停車場管理1、實驗學時4學時2、實驗目的（1）深入

13、了解棧和隊列的特性，掌握棧和隊列的存儲方法。（2）掌握棧和隊列的基本操作，如初始化、入棧（隊列）、出棧（隊列）等，并能在實際問題背景下靈活運用。3、問題描述設停車場是一個可以停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內(nèi)已經(jīng)停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后進入的車輛必須先退出場為它讓路，待該輛車開出大門外，其他車輛再按次序進入車場，每輛停放在車場的車在它離開停車場時必須按它

14、停留的時間長短交納費用，試為停車場編制按上述要求進行管理的模擬程序。4、基本要求以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現(xiàn)。隊列以鏈表結構實現(xiàn)。5、測試數(shù)據(jù)設n=2，輸入數(shù)據(jù)為：（A，1，5）， （A，2，10）， （D，1，5）， （A，3，20）， （A，4，25），

15、 （A，5，30）， （D，2，35）， （D，4，40）， （E，0，0）。其中：A表示到達（Arrival），D表示離去（Departure），E表示輸入結束（End）。6、實現(xiàn)提示需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。7、選作內(nèi)容（1）兩個棧共享空間，思考應開辟數(shù)組的空間是多少？（2）汽車可以有不同種類，則他們的占地面積不同，收費標準也不同，如1輛客車和1。5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。（

16、3）汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。（4）停放在便道上的汽車業(yè)收費，收費標準比停放在停車場的車低，請思考如何修改結構以滿足這種要求。實驗三 基于哈夫曼編碼的通信系統(tǒng)的設計與實現(xiàn)1、實驗學時5學時2、實驗目的（1）掌握二叉樹的存儲結構及其相關操作。（2）掌握構造哈夫曼樹的基本思想，及其編碼/譯碼過程。3、問題描述利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/

17、譯碼系統(tǒng)。試為這樣的信息收發(fā)站設計一個基于哈夫曼編碼的通信系統(tǒng)4、基本要求一個完整的系統(tǒng)應具有以下功能：1）初始化處理：建立通信系統(tǒng)（1）建立有100句中文的信息集合，每個句子稱為一條信息。（2）輸入編碼參數(shù)： 從終端輸入編碼字符集大小n，字符編碼長度m（設n為4，m為8）； 從終端輸入編碼字符（設為A，B，C，D）；（3）生成每條信息的字符編碼，構造字符編碼集合；（4）計算每個字符在字符編碼集合中出現(xiàn)的概率；（5）根據(jù)字符概率構造哈夫曼樹，求出每個字符的二進制編碼。2）發(fā)送端信息編碼（1）用戶從信息集合中選擇一條信息，找到該信息對應的字符編碼；（2）根據(jù)該信息的字符編碼，哈夫曼樹求出的每個字

18、符的二進制編碼，構造出該信息的二進制編碼，記錄該二進制編碼。（由于是軟件模擬，沒有發(fā)送設備，發(fā)送端的編碼工作完成）。3）接受端信息譯碼（1）根據(jù)得到的信息的二進制編碼，利用哈夫曼樹求出的每個字符的二進制編碼，還原出信息的字符編碼；（2）根據(jù)信息的字符編碼，找到對應的信息。5、實現(xiàn)提示（1）本試驗涉及到通訊學科的編碼理論和信息學科的數(shù)據(jù)壓縮技術。（2）根據(jù)參數(shù)生成的通信系統(tǒng)的所有信息的有效存儲問題。（3）信息字符編碼可參考隨機數(shù)的方式生成，且要求保持唯一性。實驗四 基于二叉排序樹的商品信息查詢算法的設計與實現(xiàn)1、實驗學時6學時2、實驗目的熟練掌握順序查找、折半查找及二叉排序樹、平衡二叉樹上的查找

19、、插入和刪除的方法。3、問題描述查找是數(shù)據(jù)處理的重要操作。請設計并實現(xiàn)基于二叉排序樹的商品信息查詢算法。完成信息的查詢、插入、刪除、查詢頻度的統(tǒng)計等功能。4、基本要求（1）以鏈表作為存儲結構，設計并實現(xiàn)基于二叉排序樹的商品信息查詢算法。（2）根據(jù)二叉排序樹的動態(tài)變化，進行二叉樹的平衡化處理。（3）實現(xiàn)信息的查詢、插入、刪除、查詢頻度的統(tǒng)計等功能。5、測試數(shù)據(jù)隨機生成。6、實現(xiàn)提示（1）初始化：以商品名稱為關鍵字，建立二叉排序樹。（2）用戶輸入查詢商品名稱，在二叉排序樹上查找，若找到，則顯示商品的相關信息，并在相應的表上的相關字段上增加該商品查找次數(shù)。若未找到，則顯示未找到信息給用戶，并在相應的表上的相關字段上增加該商品查找次數(shù)。（3）根據(jù)商品的查找次數(shù)，形成商場的經(jīng)營決策信息，反饋給決策者。（4）進行二叉樹的平衡化處理，提高查找效率。實驗五 內(nèi)部排序算法效率