數(shù)據(jù)結(jié)構(gòu)課程設(shè)計指導(dǎo)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計指導(dǎo)課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 指導(dǎo)老師：歐陽勇課程設(shè)計周（時）數(shù)：1周指導(dǎo)方式：集體輔導(dǎo)與個別輔導(dǎo)相結(jié)合課程設(shè)計適用專業(yè)：計算機(jī)科學(xué)與技術(shù)課程設(shè)計教材及主要參考資料：1、數(shù)據(jù)結(jié)構(gòu)，嚴(yán)蔚敏編著，清華大學(xué)出版社一、課程設(shè)計教學(xué)目的及基本要求1、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力；2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3、提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；4、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。5、設(shè)計的題目要求達(dá)到一定工作量（

2、200行以上代碼），并具有一定的深度和難度。6、編寫出課程設(shè)計說明書，說明書不少于15頁（不包括代碼）。二、課程設(shè)計內(nèi)容及安排1、問題定義與需求分析：根據(jù)設(shè)計題目的要求，充分地分析和理解問題，確定功能需求和限制條件。2、數(shù)據(jù)結(jié)構(gòu)設(shè)計：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型和各抽象數(shù)據(jù)類型，寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，3、總體設(shè)計：采用結(jié)構(gòu)化設(shè)計方法，按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，設(shè)計軟件層次結(jié)構(gòu)和模塊間的調(diào)用關(guān)系，定義主程序，畫出模塊之間的調(diào)用關(guān)系圖。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，4、詳細(xì)設(shè)計

3、：定義數(shù)據(jù)存儲結(jié)構(gòu)，各個主要模塊的算法定義。詳細(xì)設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，用偽碼寫出函數(shù)的算法。5、程序編碼：把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。同時加入一些注解，使程序中邏輯概念清楚。要求用C語言編寫。6、程序調(diào)試與測試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。7、設(shè)計結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析

4、。8、編寫課程設(shè)計報告。題目：學(xué)生成績管理系統(tǒng)(1) 問題描述設(shè)計數(shù)據(jù)結(jié)構(gòu)完成一個學(xué)院學(xué)生相關(guān)信息的存儲，并在此基礎(chǔ)上編寫算法實(shí)現(xiàn)學(xué)生成績管理。(2) 課程設(shè)計目的應(yīng)用線性數(shù)據(jù)結(jié)構(gòu)存儲信息，并能夠合理的應(yīng)用排序及查找算法，學(xué)會應(yīng)用散列法。(3) 基本要求 一個學(xué)院由若干個班組成；所有學(xué)生修相同的考試課和考查課。 管理系統(tǒng)能夠?qū)崿F(xiàn)：學(xué)生加入，學(xué)生畢業(yè)，學(xué)生成績統(tǒng)計，學(xué)生查詢，學(xué)生排名等管理操作。（要考慮考試課和考查課的比重關(guān)系） 為方便查找，要求針對學(xué)生姓名進(jìn)行散列法查找。 管理系統(tǒng)應(yīng)有完整地界面（最好是圖形化界面）。(4) 實(shí)現(xiàn)提示主要集中在散列函數(shù)的構(gòu)造和沖突的解決上。迷宮的生成與路由(1)

5、 問題描述設(shè)計算法生成一個N×M(N行M列)的迷宮，并完成迷宮的組織和存儲。實(shí)現(xiàn)兩種不同的迷宮路由算法：廣度優(yōu)先，深度優(yōu)先算法。并比較(包括理論和實(shí)驗(yàn))三種方法的時空復(fù)雜性。(2) 課程設(shè)計目的理解棧的應(yīng)用，理解深(廣)度優(yōu)先思想，理解問題的理論和實(shí)驗(yàn)分析。(3) 基本要求 N和M是用戶可配置的，缺省值為50和50。 迷宮的入口和出口分別在第0行和第N-1行上，隨機(jī)選擇。 生成的迷宮要求是連通的。 實(shí)現(xiàn)圖形化界面(可用VC+，也可用C語言的圖形庫)。 三種方法的試驗(yàn)比較應(yīng)該在多個迷宮實(shí)例上(尤其可以選一些特定的迷宮)。(4) 實(shí)現(xiàn)提示多考慮棧上的運(yùn)算?！半S機(jī)漫步”問題(1) 問題描述

6、有一類問題總稱為“隨機(jī)漫步”（random walk）問題，這類問題長久以來吸引著數(shù)學(xué)界的興趣。所有這些問題即使是最簡單的解決起來也是極其困難的。而且它們在很大程度上還遠(yuǎn)沒有得到解決。一個這樣的問題可以描述為：在矩形的房間里，鋪有n×m塊瓷磚，現(xiàn)將一只（醉酒的）蟑螂放在地板中間一個指定方格里。蟑螂隨機(jī)地從一塊瓷磚“漫步”到另一塊瓷磚（可能是在找一片阿司匹林）。假設(shè)它可能從其所在的瓷磚移動到其周圍八塊瓷磚中的任何一個（除非碰到墻壁），那么它把每一塊瓷磚都至少接觸一次將花費(fèi)多長時間？雖然這個問題可能很難用純粹的概率技術(shù)來解決，但是使用計算機(jī)的話卻十分容易。使用計算機(jī)解決此問題的技術(shù)稱為“

7、模擬”。這種技術(shù)廣泛應(yīng)用于工業(yè)中，用來預(yù)測運(yùn)輸流量，存貨控制等等。該問題可采用如下方法進(jìn)行模擬：用一個n×m數(shù)組作為計數(shù)器來表示蟑螂到達(dá)每一塊瓷磚的次數(shù)，每個數(shù)組單元的初始值均置為零。蟑螂在地板上的位置用坐標(biāo)（ibug，jbug）表示。蟑螂的八種可能移動用在位置(ibug + imovek，jbug + jmovek)的瓷磚表示，其中0k7，并且 imove0 = -1 jmove0 = 1imove1 = 0 jmove1 = 1imove2 = 1 jmove2 = 1imove3 = 1 jmove3 = 0imove4 = 1 jmove4 = -1imove5 = 0 jm

8、ove5 = -1imove6 = -1 jmove6 = -1imove7 = -1 jmove7 = 0蟑螂向其相鄰的八個方格的隨機(jī)漫步通過產(chǎn)生一個隨機(jī)數(shù)值k(0k7)來模擬。當(dāng)然，蟑螂不能爬出屋外，所以應(yīng)該去掉通往墻壁的坐標(biāo)值并形成一個新的隨機(jī)組合。蟑螂每次進(jìn)入一個方格，該方格的計數(shù)器就增加一，從而計數(shù)器的一個非零元素就表示蟑螂到達(dá)對應(yīng)方格的次數(shù)。當(dāng)每一個方格被至少進(jìn)入一次時，試驗(yàn)就完成了。試編寫程序進(jìn)行上述規(guī)定的模擬試驗(yàn)。（2）設(shè)計目的利用二維數(shù)組解決復(fù)雜的實(shí)際問題；了解實(shí)際問題到計算機(jī)問題的轉(zhuǎn)化；了解算法設(shè)計中邊界條件的重要性(3) 基本要求你的程序必須：（a）能夠處理所有的n和m值

9、, n和m滿足：2<n40，2m20；（b）能夠?qū)Α皀 = 15，m = 15，起始點(diǎn)為（10，10）”和“n = 39，m = 19，起始點(diǎn)為（1，1）”進(jìn)行實(shí)驗(yàn)。（c）具有迭代限制，即實(shí)驗(yàn)過程中蟑螂進(jìn)入方塊的最大次數(shù)為EM =50000時，程序能夠終止。對于每次試驗(yàn)，打?。海╠）蟑螂進(jìn)行的合法移動的總次數(shù)。（e）最終的計數(shù)器數(shù)組，顯示出漫步的“密度”，即在實(shí)驗(yàn)中每一塊瓷磚被接經(jīng)過的次數(shù)。（4）實(shí)現(xiàn)提示 無騎士巡游問題(1) 問題描述國際象棋為許多令人著迷的娛樂提供了固定的框架，這些框架獨(dú)立于游戲本身。其中很多都是基于奇異的騎士“L型”（L-shaped）移動。一個經(jīng)典的例子就是騎士巡

10、游（knight's tour）問題，自從十八世紀(jì)初以來，這個問題吸引了數(shù)學(xué)家們的興趣，也使熱心者們感到困惑。簡而言之，這個問題要求從棋盤上任意給定的方格開始移動騎士，相繼地到達(dá)所有的64個方格，進(jìn)入每個方格一次且僅進(jìn)入一次。通常情況下，我們用如下方法表示一個解：即把數(shù)字0，1，63放入棋盤中的方格來表示到達(dá)這些方格的順序。解決騎士巡游問題更具創(chuàng)意的方法之一是由J. C. Warnsdorff在1823年提出的。其規(guī)則是：騎士總是移向具有最少出口且沒有到達(dá)過的方格之一。（2）設(shè)計目的利用（二維）數(shù)組解決復(fù)雜的實(shí)際問題；了解實(shí)際問題到計算機(jī)問題的轉(zhuǎn)化；了解算法設(shè)計中邊界條件的重要性(3)

11、 基本要求a)使用Warnsdorff規(guī)則，設(shè)計并實(shí)現(xiàn)解決騎士巡游問題的算法；b) 打印棋盤，并顯示騎士巡游問題的解，然后終止算法。（4）實(shí)現(xiàn)提示a) 用一個二維數(shù)組表示國際象棋棋盤；b) 騎士的八種可能移動表示：如果騎士當(dāng)前位于方格（i，j），則騎士可能移到的方格有（i 2，j + 1），（i - 1，j + 2），（i + 1，j + 2），（i + 2，j + 1），（i + 2，j - 1）（i + 1，j -2），（i - 1，j - 2），（i - 2，j - 1）。然而，我們注意到，如果（i，j）處于接近棋盤的邊緣方格，在這些可能的移動中，有些移動就會使騎士移出棋盤，這當(dāng)然是不允

12、許的。我們可以很容易地使用兩個數(shù)組ktmove1和ktmove2把騎士的八種可能移動表示為： ktmove1 ktmove2 -2 1 -1 21 22 12 -1 1 -2 -1 -2 -2 -1于是，位于（i，j）的騎士就可能移到（i + ktmove1k，j + ktmove2k），其中k是介于0和7之間de某個值，且假定新方塊仍然位于棋盤上。稀疏矩陣的完全鏈表表示及其運(yùn)算(1) 問題描述稀疏矩陣的每個結(jié)點(diǎn)包含down，right，row，col和value五個域。用單獨(dú)一個結(jié)點(diǎn)表示一個非零項(xiàng)，并將所有結(jié)點(diǎn)連接在一起，形成兩個循環(huán)鏈表。使得第一個表即行表，把所有結(jié)點(diǎn)按照行序（同一行內(nèi)按列

13、序）用right域鏈接起來。使得第二個表即列表，把所有結(jié)點(diǎn)按照列序（同一列內(nèi)按行序）用down鏈接起來。這兩個表共用一個頭結(jié)點(diǎn)。另外，增加一個包含矩陣維數(shù)的結(jié)點(diǎn)。稀疏矩陣的這種存儲表示稱為完全鏈表表式。實(shí)現(xiàn)一個完全鏈表系統(tǒng)進(jìn)行稀疏矩陣運(yùn)算，并分析下列操作函數(shù)的計算時間和額外存儲空間的開銷。（2）設(shè)計目的認(rèn)識和掌握稀疏矩陣的完全鏈表表示；能夠建立并運(yùn)用這種存儲結(jié)構(gòu)(3) 基本要求建立一個用戶友好、菜單式系統(tǒng)進(jìn)行下列操作，并使用合當(dāng)?shù)臏y試數(shù)據(jù)測試該系統(tǒng)。（a） 讀取一個稀疏矩陣建立其完全鏈表表示（b） 輸出一個稀疏矩陣的內(nèi)容（c） 刪除一個稀疏矩陣（d） 兩個稀疏矩陣相加（e） 兩個稀疏矩陣相減（

14、f） 兩個稀疏矩陣相乘（g） 稀疏矩陣的轉(zhuǎn)置（4）實(shí)現(xiàn)提示 鏈表上的操作。倉庫管理系統(tǒng)（線性表應(yīng)用）問題描述建立一個倉庫管理程序，可以按順序和貨物名稱查詢倉庫存儲情況，也可以增加或刪除貨物以及建立新的倉庫存儲系統(tǒng)。實(shí)現(xiàn)提示可以采用雙向鏈表的存儲結(jié)構(gòu)，如可定義如下的存儲結(jié)構(gòu)：typedef struct dnode /*定義雙向鏈表結(jié)構(gòu)體*/ int number; /*貨物編號*/ char namemax; /*貨物名稱*/ int counter; /*貨物數(shù)量*/ struct dnode *prior,*next; /*定義兩指針，分別指向其前驅(qū)和后繼*/ dlnode;哈夫曼編碼/譯

15、碼系統(tǒng)（樹應(yīng)用）問題描述利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時間，還有一定的保密性?，F(xiàn)在要求編寫一程序模擬傳輸過程，實(shí)現(xiàn)在發(fā)送前將要發(fā)送的字符信息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來的數(shù)據(jù)進(jìn)行譯碼，即將信息還原成發(fā)送前的字符信息。實(shí)現(xiàn)提示在本例中設(shè)置發(fā)送者和接受者兩個功能，發(fā)送者的功能包括：輸入待傳送的字符信息；統(tǒng)計字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率）；根據(jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹；利用以上哈夫曼樹求出各字符的哈夫曼編碼；將字符信息轉(zhuǎn)換成對應(yīng)的編碼信息進(jìn)行傳送。接受者的功能包括：接收發(fā)送者傳送來的編碼信息；利用上述哈夫曼樹對

16、編碼信息進(jìn)行翻譯，即將編碼信息還原成發(fā)送前的字符信息。從以上分析可發(fā)現(xiàn)，在本例中的主要算法有三個：（1）哈夫曼樹的建立；（2）哈夫曼編碼的生成；（3）對編碼信息的翻譯。教學(xué)計劃編制問題（圖的應(yīng)用）問題描述大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。實(shí)現(xiàn)提示1、 輸入?yún)?shù)應(yīng)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號（可以是固定

17、占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號。2、 應(yīng)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。3、 若根據(jù)給定的條件問題無解，則報告適當(dāng)?shù)男畔?；否則將教學(xué)計劃輸出到用戶指定的文件中。計劃的表格格式可以自己設(shè)計。4、 可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設(shè)的課程序列中，則作為錯誤處理。圖書管理系統(tǒng)（查找應(yīng)用）問題描述圖書管理基本業(yè)務(wù)活動包括：對一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計一個圖書管理系統(tǒng)，將上述業(yè)務(wù)活動借助于計算機(jī)系統(tǒng)完成。實(shí)現(xiàn)提示1、 每種書的登記內(nèi)容至少包

18、括書號、書名、著者、現(xiàn)存量和總庫存量等五項(xiàng)。2、 由于圖書管理的基本業(yè)務(wù)活動都是通過書號（即關(guān)鍵字）進(jìn)行的，所以要用對書號 索引，以獲得高效率。3、 系統(tǒng)應(yīng)實(shí)現(xiàn)的基本功能有：l 采編入庫：新購入一種書，經(jīng)分類和確定書號之后登記到圖書帳目中去。如果這兩種書在帳中已有，則只將總庫存量增加。l 清除庫存：某種書已無保留價值，將它從圖書帳目中注銷。l 借閱：如果一種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號和歸還期限。l 歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。l 顯示：以凹入表的形式顯示B樹。這個操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。通信錄查詢系統(tǒng)（查找應(yīng)用）【問題描述】設(shè)計散列表實(shí)現(xiàn)通訊

19、錄查找系統(tǒng)。(1) 設(shè)每個記錄有下列數(shù)據(jù)項(xiàng)：電話號碼、用戶名、地址；(2) 從鍵盤輸入各記錄，分別以電話號碼為關(guān)鍵字建立散列表；(3) 采用二次探測再散列法解決沖突；(4) 查找并顯示給定電話號碼的記錄；(5) 通訊錄信息文件保存；(6) 要求人機(jī)界面友好，使用圖形化界面；【實(shí)現(xiàn)提示】主函數(shù)：根據(jù)選單的選項(xiàng)調(diào)用各函數(shù)，并完成相應(yīng)的功能。Menu()的功能：顯示英文提示選單。Quit()的功能：退出選單。Create()的功能：創(chuàng)建新的通訊錄。Append()的功能：在通訊錄的末尾寫入新的信息，并返回選單。Find()：查詢某人的信息，如果找到了，則顯示該人的信息，如果沒有則提示通訊錄中沒有此人

20、的信息，并返回選單。Alter()的功能：修改某人的信息，如果未找到要修改的人，則提示通訊錄中沒有此人的信息，并返回選單。Delete()的功能：刪除某人的信息，如果未找到要刪除的人，則提示通訊錄中沒有此人的信息，并返回選單。List()的功能：顯示通訊錄中的所有記錄。Save()的功能：保存通訊錄中的所有記錄到指定文件中。Load()的功能：從指定文件中讀取通訊錄中的記錄。藥店的藥品銷售統(tǒng)計系統(tǒng)（排序應(yīng)用）【問題描述】設(shè)計一系統(tǒng)，實(shí)現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進(jìn)行統(tǒng)計，可按藥品的編號、單價、銷售量或銷售額做出排名?！緦?shí)現(xiàn)提示】在本設(shè)計中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。藥品編號共4位，采用字母和數(shù)字混合編號，如：A125，前一位為大寫字母，后三位為數(shù)字，按藥品編號進(jìn)行排序時，可采用基數(shù)排序法。對各藥品的單價、銷售量或銷售額進(jìn)行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計中，對單價的排序