數(shù)據(jù)結(jié)構(gòu)課程實驗指導(dǎo)書

1、數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書一、實驗?zāi)康臄?shù)據(jù)結(jié)構(gòu)是計算機學(xué)科一門重要的專業(yè)基礎(chǔ)課程，也是計算機學(xué)科的一門核心 課程。本課程較為系統(tǒng)地論述了軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)與實現(xiàn) 算法，并做了相應(yīng)的性能分析和比較，課程內(nèi)容豐富，理論系統(tǒng)。本課程的學(xué)習(xí)將為后 續(xù)課程的學(xué)習(xí)以及軟件設(shè)計水平的提高打下良好的基礎(chǔ)。由于以下原因，使得掌握這門課程具有較大的難度：1）理論艱深，方法靈活，給學(xué)習(xí)帶來困難；2）內(nèi)容豐富，涉及的知識較多，學(xué)習(xí)有一定的難度；3）側(cè)重于知識的實際應(yīng)用，要求學(xué)生有較好的思維以及較強的分析和解決問題的 能力，因而加大了學(xué)習(xí)的難度；根據(jù)數(shù)據(jù)結(jié)構(gòu)課程本身的特性，通過實驗實踐內(nèi)容的訓(xùn)練，突出構(gòu)

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

3、時，覺得無從下手。實驗中的內(nèi)容和教科書的 內(nèi)容是密切相關(guān)的，解決題目要求所需的各種技術(shù)大多可從教科書中找到，只不過其出現(xiàn)的形式呈多樣化，因此需要仔細(xì)體會，在反復(fù)實踐的過程中才能掌握。(2) 培養(yǎng)學(xué)生軟件設(shè)計的綜合能力平時的練習(xí)較偏重于如何編寫功能單一的 小 算法，而實驗題是軟件設(shè)計的綜合訓(xùn) 練，包括問題分析、總體結(jié)構(gòu)設(shè)計、用戶界面設(shè)計、程序設(shè)計基本技能和技巧，多人合 作，以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。通過實驗使學(xué)生不僅能夠深化理解教學(xué)內(nèi)容，進(jìn)一步提高靈活運用數(shù)據(jù)結(jié)構(gòu)、算法 和程序設(shè)計技術(shù)的能力，而且可以在需求分析、總體結(jié)構(gòu)設(shè)計、算法設(shè)計、程序設(shè)計、 上機操作及程序調(diào)試等基本技能

4、方面受到綜合訓(xùn)練。實驗著眼于原理與應(yīng)用的結(jié)合點， 使學(xué)生學(xué)會如何把書本上和課堂上學(xué)到的知識用于解決實際問題， 從而培養(yǎng)計算機軟件 工作所需要的動手能力。(3) 熟悉程序開發(fā)環(huán)境，學(xué)習(xí)上機調(diào)試程序 一個程序從編輯，編譯，連接到運行，都要在一定的外部操作環(huán)境下才能進(jìn)行。所 謂 環(huán)境 就是所用的計算機系統(tǒng)硬件，軟件條件，只有學(xué)會使用這些環(huán)境，才能進(jìn)行程序開發(fā)工作。通過上機實驗，熟練地掌握程序的開發(fā)環(huán)境，為以后真正編寫計算機程 序解決實際問題打下基礎(chǔ)。同時，在今后遇到其它開發(fā)環(huán)境時就會觸類旁通，很快掌握 新系統(tǒng)的使用。完成程序的編寫，決不意味著萬事大吉。你認(rèn)為萬無一失的程序，實際上機運行時 可能不斷出

5、現(xiàn)麻煩。 如編譯程序檢測出一大堆語法錯誤。 有時程序本身不存在語法錯誤， 也能夠順利運行，但是運行結(jié)果顯然是錯誤的。開發(fā)環(huán)境所提供的編譯系統(tǒng)無法發(fā)現(xiàn)這 種程序邏輯錯誤，只能靠自己的上機經(jīng)驗分析判斷錯誤所在。程序的調(diào)試是一個技巧性 很強的工作，盡快掌握程序調(diào)試方法是非常重要的。分析問題，選擇算法，編好程序， 只能說完成一半工作，另一半工作就是調(diào)試程序，運行程序并得到正確結(jié)果。二、實驗要求常用的軟件開發(fā)方法， 是將軟件開發(fā)過程劃分為分析、 設(shè)計、實現(xiàn)和維護(hù)四個階段。 雖然數(shù)據(jù)結(jié)構(gòu)課程中的實驗題目的遠(yuǎn)不如從實際問題中的復(fù)雜程度度高， 但為了培養(yǎng)一 個軟件工作者所應(yīng)具備的科學(xué)工作的方法和作風(fēng)， 也應(yīng)遵

6、循以下五個步驟來完成實驗題 目：1) 問題分析和任務(wù)定義在進(jìn)行設(shè)計之前，首先應(yīng)該充分地分析和理解問題，明確問題要求做什么?限制條 件是什么。本步驟強調(diào)的是做什么 ?而不是怎么做。對問題的描述應(yīng)避開算法和所涉及 的數(shù)據(jù)類型，而是對所需完成的任務(wù)作出明確的回答。例如：輸入數(shù)據(jù)的類型、值的范 圍以及輸入的形式；輸出數(shù)據(jù)的類型、值的范圍及輸出的形式；若是會話式的輸入，則 結(jié)束標(biāo)志是什么 ?是否接受非法的輸入 ?對非法輸入的回答方式是什么等。 還應(yīng)該為調(diào)試 程序準(zhǔn)備好測試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非法形式的輸入數(shù)據(jù)。2) 邏輯設(shè)計和詳細(xì)設(shè)計 在設(shè)計這一步驟中需分邏輯設(shè)計和詳細(xì)設(shè)計兩步實現(xiàn)。邏輯設(shè)計指的是

7、，對問題描 述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊， 定義主程序模塊和各抽象數(shù)據(jù)類型； 詳細(xì)設(shè)計則為定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的 偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易 于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具 體。作為邏輯設(shè)計的結(jié)果，應(yīng)寫出每個抽象數(shù)據(jù)類型的定義 ( 包括數(shù)據(jù)結(jié)構(gòu)的描述和每 個基本操作的功能說明 ) ，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。詳細(xì) 設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定 義，寫出函數(shù)形式的算法框架。在求精

8、的過程中，應(yīng)盡量避免陷入語言細(xì)節(jié)，不必過早 表述輔助數(shù)據(jù)結(jié)構(gòu)和局部變量。3) 編碼實現(xiàn)和靜態(tài)檢查 編碼是把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。 如果基于詳細(xì)設(shè)計的偽 碼算法就能直接在鍵盤上輸入程序的話，則可以不必用筆在紙上寫出編碼，而將這一步 的工作放在上機準(zhǔn)備之后進(jìn)行，即在上機調(diào)試之前直接用鍵盤輸入。然而，不管你是否寫出編碼的程序，在上機之前，認(rèn)真的靜態(tài)檢查是必不可少的。 靜態(tài)檢查主要有兩種方法，一是用一組測試數(shù)據(jù)手工執(zhí)行程序 (通常應(yīng)先分模塊檢查 ) ； 二是通過對程序深入全面地理解程序邏輯，在這個過程中再加入一些注解和斷言。如果 程序中邏輯概念清楚，后者將比前者有效。4) 上機準(zhǔn)

9、備和上機調(diào)試上機準(zhǔn)備包括以下幾個方面：(1) 注意同一高級語言文本之間的差別 ;(2) 熟悉機器的操作系統(tǒng)和語言集成環(huán)境的用戶手冊，尤其是最常用的命令操作， 以便順利進(jìn)行上機的基本活動 ;(3) 掌握調(diào)試工具，考慮調(diào)試方案，設(shè)計測試數(shù)據(jù)并手工得出正確結(jié)果。應(yīng)該能夠熟練運用高級語言的程序調(diào)試器 DBBU調(diào)試程序；(4) 上機調(diào)試程序時要帶一本高級語言教材或手冊。調(diào)試最好分模塊進(jìn)行，自底向 上，即先調(diào)試低層函數(shù)。在調(diào)試過程中可以不斷借助 DEBU(的各種功能，提高調(diào)試效率。 調(diào)試中遇到的各種異常現(xiàn)象往往是預(yù)料不到的，此時應(yīng)動手確定疑點，通過修改程序來 證實它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其

10、注釋，形成格式和風(fēng)格良好的源程 序清單和結(jié)果。5) 總結(jié)和整理實驗報告實驗結(jié)束后，要整理實驗結(jié)果并認(rèn)真分析和總結(jié)， 根據(jù)教師要求寫出實驗報告。實驗報告一般包括如下內(nèi)容：(1) 實驗內(nèi)容(2) 實驗?zāi)康?3) 程序清單(4) 調(diào)試步驟(5) 分析與思考 :調(diào)試過程及調(diào)試中遇到的問題及解決辦法 ；調(diào)試程序的心得與體會 其他算法的存在與實踐等。 若最終未完成調(diào)試， 要認(rèn)真找出錯誤并分析原因等。三、實驗內(nèi)容實驗一 Joseph 問題求解算法的設(shè)計與實現(xiàn)1、實驗學(xué)時3 學(xué)時2、實驗?zāi)康恼莆真湵淼幕静僮鳎?插入、刪除、查找等運算， 能夠靈活應(yīng)用鏈表這種數(shù)據(jù)結(jié)構(gòu)。3、問題描述約瑟夫(Joseph)問題的一

11、種描述是：編號為1, 2,，n的n個人按順時針方向 圍坐一圈，每人持有一個密碼(正整數(shù))。開始任選一個正整數(shù)作為報數(shù)上限值 m從第 一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他 的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從 1報數(shù)，如此下去， 直至所有人全部出列為止。試設(shè)計一個程序求出出列順序。4、基本要求利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號。5、測試數(shù)據(jù)m的初值為20; n=7, 7個人的密碼依次為：3, 1, 7, 2, 4, 8, 4,首先m值為6 （正確的出列順序應(yīng)為 6， 1， 4， 7， 2， 3， 5）。6

12、、實現(xiàn)提示程序運行后，首先要求用戶指定初始報數(shù)上限值，然后讀取各人的密碼?？稍O(shè)nW30。此題所用的循環(huán)鏈表中不需要“頭結(jié)點” ,請注意空表和非空表的界限。7、選作內(nèi)容向上述程序中添加在順序結(jié)構(gòu)上實現(xiàn)的部分。實驗二 停車場管理1 、實驗學(xué)時5 學(xué)時2、實驗?zāi)康?）深入了解棧和隊列的特性,掌握棧和隊列的存儲方法。2）掌握棧和隊列的基本操作,如初始化、入棧（隊列） 、出棧（隊列）等,并能在 實際問題背景下靈活運用。3、問題描述設(shè)停車場是一個可以停放 n 輛汽車的狹長通道,且只有一個大門可供汽車進(jìn)出。汽 車在停車場內(nèi)按車輛到達(dá)時間的先后順序,依次由北向南排列（大門在最南端,最先到 達(dá)的第一輛車停放在車

13、場的最北端） ,若車場內(nèi)已經(jīng)停滿 n 輛汽車,則后來的汽車只能 在門外的便道上等候,一旦有車開走,則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi) 某輛車要離開時,在它之后進(jìn)入的車輛必須先退出場為它讓路,待該輛車開出大門外, 其他車輛再按次序進(jìn)入車場, 每輛停放在車場的車在它離開停車場時必須按它停留的時 間長短交納費用,試為停車場編制按上述要求進(jìn)行管理的模擬程序。4、基本要求 以棧模擬停車場,以隊列模擬車場外的便道,按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照 號碼以及到達(dá)或離去的時刻。 對一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為： 若是車輛

14、到達(dá), 則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去,則輸出汽車在停車場內(nèi)停 留的時間和應(yīng)交納的費用（在便道上停留的時間不收費） 。棧以順序結(jié)構(gòu)實現(xiàn)。隊列以 鏈表結(jié)構(gòu)實現(xiàn)。5、測試數(shù)據(jù)設(shè) n=2,輸入數(shù)據(jù)為：（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表示到達(dá)（Arrival ）, D 表示離去（Departure ）, E表示輸入 結(jié)束（ End）。6、實現(xiàn)提示 需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而

15、從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。棧中每個元素表示一輛汽車，包 含兩個數(shù)據(jù)項：汽車的牌照號碼和進(jìn)入停車場的時刻。7、選作內(nèi)容1 ）兩個棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？ 2）汽車可以有不同種類，則他們的占地面積不同，收費標(biāo)準(zhǔn)也不同，如1 輛客車和 1 。 5輛小汽車的占地面積相同， 1 輛十輪卡車占地面積相當(dāng)于 3輛小汽車的占地面積。3）汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依 次排到隊尾。4）停放在便道上的汽車業(yè)收費，收費標(biāo)準(zhǔn)比停放在停車場的車低，請思考如何修 改結(jié)構(gòu)以滿足這種要求。實驗三 基于哈夫曼編碼的通信系統(tǒng)的

16、設(shè)計與實現(xiàn)1 、實驗學(xué)時8 學(xué)時2、實驗?zāi)康? ）掌握二叉樹的存儲結(jié)構(gòu)及其相關(guān)操作。2）掌握構(gòu)造哈夫曼樹的基本思想，及其編碼 / 譯碼過程。3、問題描述 利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸 成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳 來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原） 。對于雙工信道（即可以雙向傳輸信息的信道） ，每端都需要一個完整的編 / 譯碼系統(tǒng)。試為這樣的信息收發(fā)站設(shè)計一個基于哈夫曼編碼的通信系統(tǒng)4、基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：1）初始化處理：建立通信系統(tǒng)（1）建立有 100 句中文的信息集合，每個句子稱為一條信息。

17、（2）輸入編碼參數(shù)： 從終端輸入編碼字符集大小n,字符編碼長度m （設(shè)n為4, m為8）; 從終端輸入編碼字符（設(shè)為 A， B， C， D）；（ 3）生成每條信息的字符編碼,構(gòu)造字符編碼集合;（ 4）計算每個字符在字符編碼集合中出現(xiàn)的概率;（ 5）根據(jù)字符概率構(gòu)造哈夫曼樹,求出每個字符的二進(jìn)制編碼。2）發(fā)送端信息編碼（ 1）用戶從信息集合中選擇一條信息,找到該信息對應(yīng)的字符編碼;（ 2）根據(jù)該信息的字符編碼,哈夫曼樹求出的每個字符的二進(jìn)制編碼,構(gòu)造出該信 息的二進(jìn)制編碼,記錄該二進(jìn)制編碼。 （由于是軟件模擬,沒有發(fā)送設(shè)備,發(fā)送端的編 碼工作完成）。3）接受端信息譯碼（ 1）根據(jù)得到的信息的二進(jìn)

18、制編碼,利用哈夫曼樹求出的每個字符的二進(jìn)制編碼, 還原出信息的字符編碼;（ 2）根據(jù)信息的字符編碼,找到對應(yīng)的信息。5、實現(xiàn)提示1）本試驗涉及到通訊學(xué)科的編碼理論和信息學(xué)科的數(shù)據(jù)壓縮技術(shù)。2）根據(jù)參數(shù)生成的通信系統(tǒng)的所有信息的有效存儲問題。3）信息字符編碼可參考隨機數(shù)的方式生成,且要求保持唯一性。實驗四 基于二叉排序樹的商品信息查詢算法的設(shè)計與實現(xiàn)1、實驗學(xué)時8 學(xué)時2、實驗?zāi)康?熟練掌握順序查找、折半查找及二叉排序樹、平衡二叉樹上的查找、插入和刪除的 方法。3、問題描述查找是數(shù)據(jù)處理的重要操作。請設(shè)計并實現(xiàn)基于二叉排序樹的商品信息查詢算法。 完成信息的查詢、插入、刪除、查詢頻度的統(tǒng)計等功能。4、基本要求1）以鏈表作為存儲結(jié)構(gòu)，設(shè)計并實現(xiàn)基于二叉排序樹的商品信息查詢算法。2）根據(jù)二叉排序樹的動態(tài)變化，進(jìn)行二叉樹的平衡化處理。3）實現(xiàn)信息的查詢、插入、刪除、查詢頻度的統(tǒng)計等功能。5、測試數(shù)據(jù) 隨機生成。6、實現(xiàn)提示1）初始化：以商品名稱為關(guān)鍵字，建立二叉排序樹。2）用戶輸入查詢商品名稱，在二叉排序樹上查找，若找到，則顯示商品的相關(guān)信 息，并在相應(yīng)的表上的相關(guān)字段上增加該商品查找次數(shù)。若未找到，則顯示未找到信息 給用戶，并在相應(yīng)的表上的相關(guān)字段上增加該商