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

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

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

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

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

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

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

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

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

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

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

11、運(yùn)行結(jié)果和必要的說明。     6 分析與思考       調(diào)試過程及調(diào)試中遇到的問題及解決辦法;調(diào)試程序的心得與體會(huì);其他算法的存在與實(shí)踐等。 若最終未完成調(diào)試， 要認(rèn)真找出錯(cuò)誤并分析原因等。 實(shí)驗(yàn)一、約瑟夫環(huán)【實(shí)驗(yàn)學(xué)時(shí)】4學(xué)時(shí)【實(shí)驗(yàn)?zāi)康摹空莆真湵淼幕静僮鳎翰迦搿h除、查找等運(yùn)算，能夠靈活應(yīng)用鏈表這種數(shù)據(jù)結(jié)構(gòu)?！締栴}描述】約瑟夫（Joseph）問題的一種描述是：編號為1，2，n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針

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

13、上實(shí)現(xiàn)的部分實(shí)驗(yàn)過程：的車輛必須先退出場為它讓路，待該輛車開出大門外，其他車輛再按次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時(shí)必須按它停留的時(shí)間長短交納費(fèi)用，試為停車場編制按上述要求進(jìn)行管理的模擬程序。【基本要求】以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時(shí)刻。對一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)。隊(duì)列以鏈表

14、結(jié)構(gòu)實(shí)現(xiàn)?！緶y試數(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）。【實(shí)現(xiàn)提示】需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號碼和進(jìn)入停車場的時(shí)刻。【選作內(nèi)容】（1） 兩個(gè)棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？（2） 汽車可以

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

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

17、已經(jīng)建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4） P：打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼，同時(shí)將此字符形式的編碼寫入文件CodePrint中。（5） T：打印哈夫曼樹（Tree printing）。將已經(jīng)在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。【測試數(shù)據(jù)】（1） 利用教科書例6-2中的數(shù)據(jù)調(diào)試程序。（2） 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“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【實(shí)現(xiàn)提示】（1） 編碼結(jié)果以文本式存儲(chǔ)在文件CodeFile中。（2） 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運(yùn)行Quit。請用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3） 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令

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

20、?！締栴}描述】很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個(gè)程序，演示連通的無向圖上，遍歷全部結(jié)點(diǎn)的操作?！净疽蟆恳脏徑佣嘀乇頌榇鎯?chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集?！緶y試數(shù)據(jù)】教科書圖7.33。暫時(shí)忽略里程，起點(diǎn)為北京?！緦?shí)現(xiàn)提示】設(shè)圖的結(jié)點(diǎn)不超過30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號分別為1，2，n）。通過輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對，可以對邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點(diǎn)順序不能顛倒?！具x作內(nèi)容】（1） 借助于棧類型（自己定義和實(shí)現(xiàn)），用非遞歸算法實(shí)現(xiàn)深度優(yōu)先遍歷。（2） 以鄰接表為存儲(chǔ)結(jié)構(gòu)，建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再