數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計(jì)指導(dǎo)書

1、 數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計(jì)指導(dǎo)書 （共4題） 實(shí)驗(yàn)學(xué)時(shí)： 60 實(shí)驗(yàn)類型： 綜合型前修課程(含實(shí)踐環(huán)節(jié))名稱：高級語言程序設(shè)計(jì)及其課程設(shè)計(jì)，離散數(shù)學(xué)。適用專業(yè)：計(jì)算機(jī)軟件及應(yīng)用專業(yè)。一. 課程設(shè)計(jì)的目的課程設(shè)計(jì)的目的是訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問題分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)和編程實(shí)現(xiàn)等軟件開發(fā)全過程的綜合實(shí)踐能力。鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。二. 課程設(shè)計(jì)的要求在處理每個(gè)題目時(shí)，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思算法、通過類的設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完

2、整的分析報(bào)告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī)調(diào)試工作的效率。在程序設(shè)計(jì)階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。三. 課程設(shè)計(jì)的內(nèi)容題目1 0樹練習(xí)問題描述用四叉樹表示某圖像卷積的映射分量，設(shè)各分量值已經(jīng)求出；需要在一定帶寬條件下傳輸樹上接點(diǎn)中表示的圖像信息到目標(biāo)地，最后在目標(biāo)地重新恢復(fù)具有壓縮了的信息的四叉樹?；疽笤O(shè)可以手工或通過文件輸入數(shù)據(jù)，生成四叉樹，并且調(diào)用方法可以顯示樹。然后按選擇1的要求實(shí)現(xiàn)后面的功能：(有精力的同學(xué)可以選擇實(shí)現(xiàn)問題討論中的功能)選擇1. 按層次遍歷樹可以得到結(jié)點(diǎn)信息，但是只需要傳輸樹上 n (比如n=3)層結(jié)點(diǎn)的信息；最后在目標(biāo)地根據(jù)傳輸過來的信

3、息恢復(fù)被截短了的四叉樹。 測試數(shù)據(jù) 提供不同的數(shù)據(jù)文件，文件中數(shù)據(jù)值按先根順序排列。實(shí)現(xiàn)提示第一次生成樹用先根次序生成；根據(jù)實(shí)現(xiàn)的功能要求設(shè)計(jì)樹結(jié)點(diǎn)的結(jié)構(gòu)，包括是否考慮結(jié)點(diǎn)在樹中與其它結(jié)點(diǎn)的聯(lián)系關(guān)系；按層次遍歷時(shí)可以用隊(duì)列作輔助結(jié)構(gòu)；可以用分層分組的字符形式來顯示樹，要能表示結(jié)點(diǎn)的數(shù)據(jù)值和各結(jié)點(diǎn)之間的拓?fù)潢P(guān)系。問題討論在生成四叉樹后，實(shí)現(xiàn)的功能還可以更強(qiáng)，以下兩種選擇可以供大家考慮實(shí)現(xiàn)：選擇2. 設(shè)最多只能傳 w 個(gè)結(jié)點(diǎn)的數(shù)據(jù)，按層次遍歷，依次傳輸結(jié)點(diǎn)數(shù)據(jù)，直到傳夠w 個(gè)結(jié)點(diǎn)信息，但是注意數(shù)據(jù)值小于 x 的結(jié)點(diǎn)及其子樹的信息不傳，這樣的結(jié)點(diǎn)不在 w 中計(jì)數(shù)。在目標(biāo)地根據(jù)傳輸過來的信息恢復(fù)被修剪

4、過了的四叉樹。在恢復(fù)的樹中，保留的結(jié)點(diǎn)仍在原來的層次和位置。選擇3. 設(shè)最多只能傳 w 個(gè)結(jié)點(diǎn)的數(shù)據(jù)，按層次遍歷，選擇數(shù)據(jù)值較大的 w 個(gè)結(jié)點(diǎn)信息傳輸，遇到數(shù)據(jù)值小于 x的結(jié)點(diǎn)的子樹中有數(shù)據(jù)值較大且能擠入前w個(gè)的結(jié)點(diǎn)也要傳輸相應(yīng)的信息。在目標(biāo)地根據(jù)傳輸過來的信息恢復(fù)被修剪過了的四叉樹。在恢復(fù)的樹中，保留的結(jié)點(diǎn)仍在原來的層次和位置。例子： 初始生成的四叉樹題目2：以隊(duì)列實(shí)現(xiàn)的仿真技術(shù)預(yù)測理發(fā)館的經(jīng)營狀況 問題描述 ：理發(fā)館一天的工作過程如下：1) 理發(fā)館有N把理發(fā)椅，可同時(shí)為N位顧客進(jìn)行理發(fā)。2) 理發(fā)師分三個(gè)等級（一級、二級、三級），對應(yīng)不同的服務(wù)收費(fèi)。3) 當(dāng)顧客進(jìn)門時(shí)，需選擇某級別理發(fā)師，

5、只要該級別的理發(fā)師有空椅，則可立即坐下理發(fā)，否則需排隊(duì)等候。4) 一旦該級別的理發(fā)師有顧客理發(fā)完離去，排在隊(duì)頭的顧客便可開始理發(fā)。5) 若理發(fā)館每天連續(xù)營業(yè)T分鐘，求（1） 一天內(nèi)顧客在理發(fā)館內(nèi)的平均逗留時(shí)間；（2） 顧客排隊(duì)等候理發(fā)的隊(duì)列長度平均值；（3） 營業(yè)時(shí)間到點(diǎn)后仍需完成服務(wù)的收尾工作時(shí)間；（4） 統(tǒng)計(jì)每天的營業(yè)額；（5） 統(tǒng)計(jì)每天不同級別理發(fā)師的創(chuàng)收。 基本要求 ：1) 模擬理發(fā)館一天的工作過程：必須采用事件驅(qū)動(dòng)的離散模型（參考教科書3.5節(jié)離散事件模擬p65）；2) 每個(gè)顧客到達(dá)和下一顧客到達(dá)時(shí)間的間隔應(yīng)是隨機(jī)的；3) 理發(fā)師編號、理發(fā)師級別和每天的營業(yè)時(shí)間由用戶輸入；4) 某顧

6、客挑選某一個(gè)級別的理發(fā)師而不得時(shí)，選第一個(gè)隊(duì)列排隊(duì)等待 ；5) 每個(gè)顧客進(jìn)門時(shí)將生成三個(gè)隨機(jī)數(shù):(1) durtime:進(jìn)門顧客理發(fā)所需服務(wù)時(shí)間（簡稱：理發(fā)時(shí)間）；(2) intertime:下一顧客將到達(dá)的時(shí)間間隔（簡稱：間隔時(shí)間）；(3) select:服務(wù)選項(xiàng) 。6) 服務(wù)收費(fèi)：應(yīng)包含服務(wù)時(shí)間和理發(fā)師級別兩個(gè)因素。7) 除了輸出統(tǒng)計(jì)的數(shù)據(jù)外，還需要顯示理發(fā)館的狀態(tài)，可以采用文本方式（橫向顯示每張椅編號、理發(fā)師級別?？v向表示等待該理發(fā)師理發(fā)的排隊(duì)長度）。 測試數(shù)據(jù) ：用戶輸入每位理發(fā)師編號、級別號和營業(yè)的時(shí)間，結(jié)合隨機(jī)數(shù)進(jìn)行測試。 實(shí)現(xiàn)提示 1) 顧客進(jìn)門和出門這兩個(gè)時(shí)刻發(fā)生的事情稱“事件

7、”，按事件的先后次序逐個(gè)處理事件的工作方式稱“事件驅(qū)動(dòng)模擬”。離散事件驅(qū)動(dòng)模型的特點(diǎn)是只關(guān)注和刻畫事物的狀態(tài)變化(即事件)，不關(guān)心變化的過渡過程。模型靠每一個(gè)事件引發(fā)其它事件的方式來維持運(yùn)轉(zhuǎn)。每個(gè)事件都有發(fā)生時(shí)間，模型的運(yùn)轉(zhuǎn)實(shí)際就是按事件發(fā)生時(shí)間順序逐個(gè)處理事件，處理將產(chǎn)生新的事件。因此，建模的關(guān)鍵就是全面分析事物的主要特點(diǎn)，抽象出幾種能反映本質(zhì)的事件和它們之間的驅(qū)動(dòng)關(guān)系。系統(tǒng)時(shí)間就是當(dāng)前事件的事件發(fā)生時(shí)間，它不是等間隔變化而是跳躍變化的。2) 數(shù)據(jù)結(jié)構(gòu)：本題設(shè)計(jì)兩個(gè)抽象數(shù)據(jù)類型l 隊(duì)列抽象數(shù)據(jù)類型：登錄排隊(duì)等候理發(fā)的顧客情況。每個(gè)元素應(yīng)包括顧客進(jìn)門時(shí)刻、理發(fā)師級別、理發(fā)所需時(shí)間。N把椅子對應(yīng)

8、N個(gè)隊(duì)列。l 事件鏈表抽象數(shù)據(jù)類型：登錄顧客進(jìn)門事件、出門事件。每個(gè)事件應(yīng)包括事件類型（進(jìn)門事件類型為0，出門事件類型按N把椅子所排隊(duì)列分為為1、2、.N）和事件發(fā)生的時(shí)刻occurtime。為便于按事件發(fā)生先后順序逐一處理事件，事件表應(yīng)按“時(shí)刻”有序。3） 對理發(fā)椅需要進(jìn)行編號，使不同級別的理發(fā)師與編號的理發(fā)椅相對應(yīng)。 問題討論 ：1) 顧客排隊(duì)前，可以在等待該級別各個(gè)理發(fā)師的各個(gè)隊(duì)列中，選擇最短隊(duì)列；2) 更進(jìn)一步,顧客可以選擇最快隊(duì)列（設(shè)計(jì)選最快的策略）3) 可以發(fā)揮創(chuàng)造性，采用更直觀漂亮的圖形方式顯示理發(fā)館的狀態(tài)。題目3、使用哈希表技術(shù)判別兩個(gè)源程序的相似性問題描述對于兩個(gè)C語言的源程

9、序清單，用哈希表的方法分別統(tǒng)計(jì)兩個(gè)程序中使用C語言關(guān)鍵字的情況，并最終按定量的計(jì)算結(jié)果，得出兩份源程序清單的相似性?；疽驝語言關(guān)鍵字的哈希表可以自建，也可以利用數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程（嚴(yán)蔚敏 陳文博編著 清華大學(xué)出版社）書中8。10的哈希表。此題的工作主要是掃描給定的源程序，累計(jì)在每個(gè)源程序中C語言關(guān)鍵字出現(xiàn)的頻度。在掃描源程序過程中，每遇到關(guān)鍵字就查找哈希表，并累加相應(yīng)關(guān)鍵字出現(xiàn)的頻度。為保證查找效率，建議自建哈希表的平均查找長度ASL不大于2。掃描兩個(gè)源程序所統(tǒng)計(jì)的所有關(guān)鍵字不同頻度，可以得到兩個(gè)向量。如下面簡單的例子所示：VoidIntForCharIfElsewhile434370

10、24254521關(guān)鍵字程序1種關(guān)鍵字頻度程序2種關(guān)鍵字頻度哈希地址 0 1 2 3 4 5 6 7 8 9X1=4,3,0,4,3,0,7,0,0,2 X2=4,2,0,5,4,0,5,2,0,1通過計(jì)算向量X1和X2的相對距離來判斷兩個(gè)源程序的相似性，相對距離的計(jì)算方法是，T表示向量的轉(zhuǎn)置。按例子所給的數(shù)據(jù)，s 0.13。顯然當(dāng)X1=X2時(shí)，s=0,反映出可能是同一個(gè)程序；s值越大，則兩個(gè)程序的差別可能也越大。測試數(shù)據(jù)做幾個(gè)編譯和運(yùn)行都無誤的C程序，程序之間有相近的和差別大的，用上述方法求s,并對比差異程度。實(shí)現(xiàn)提示 本題的很大工作量將是對源程序掃描，區(qū)分出C程序的每一關(guān)鍵字?？梢詾镃語言關(guān)

11、鍵字集建一棵鍵樹，掃描源程序和在鍵樹中查找同步進(jìn)行，以取得每一個(gè)關(guān)鍵字。問題討論這種判斷方法只是提供一種輔助手段，即便s=0也可能不是同一個(gè)程序，s的值很大，也可能算法是完全一樣的。例如，一個(gè)程序使用while語句，另一個(gè)使用for語句，但功能完全相同。事實(shí)上，當(dāng)發(fā)現(xiàn)s的值很小時(shí)，就應(yīng)該以人工干預(yù)來區(qū)分。題目4. 救護(hù)車調(diào)度模擬系統(tǒng)問題描述用Turbo-C語言設(shè)計(jì)實(shí)現(xiàn)一個(gè)用事件驅(qū)動(dòng)的“救護(hù)車調(diào)度”離散模型，模擬120急救中心響應(yīng)每個(gè)病人的呼救信號統(tǒng)一調(diào)度救護(hù)車運(yùn)行的情況。我們對問題作適當(dāng)簡化，假設(shè)：某城市共有m個(gè)可能的呼救點(diǎn)(居民小區(qū)、工廠、學(xué)校、公司、機(jī)關(guān)、單位等)，分布著n所醫(yī)院(包含在m

12、個(gè)點(diǎn)中)，有k輛救護(hù)車分派在各醫(yī)院待命，出現(xiàn)呼救病人時(shí)，由急救中心統(tǒng)一指派救護(hù)車接送至最近的醫(yī)院救治。救護(hù)車完成一次接送任務(wù)后即消毒，并回原處繼續(xù)待命。假定呼救者與急救中心、急救中心與救護(hù)車之間的通訊暢通無阻，也不考慮道路交通堵塞的影響?？梢杂胢個(gè)頂點(diǎn)的無向網(wǎng)來表示該城市的各地點(diǎn)和道路。時(shí)間可以分鐘為單位，路段長可表示為救護(hù)車行駛化費(fèi)的分鐘數(shù)。要求 模擬每一起病人呼救派車往救接人回院的過程：顯示每輛救護(hù)車的狀態(tài)(待命、往救、送院可能還有返點(diǎn))和每個(gè)病人的狀態(tài)(待派車、待接、送院途中)，顯示各醫(yī)院的待命救護(hù)車隊(duì)列，實(shí)時(shí)顯示當(dāng)前的病人平均接送時(shí)間和平均派車延遲時(shí)間以及已送達(dá)病人數(shù)。救護(hù)車應(yīng)按最快的

13、路線接送病人。 呼救事件發(fā)生的間隔時(shí)間和地點(diǎn)都是隨機(jī)的(其發(fā)生頻度先給一個(gè)省缺值，可實(shí)時(shí)調(diào)整)。點(diǎn)數(shù)m、點(diǎn)名、路段數(shù)e和每段長度以及醫(yī)院點(diǎn)的名稱都由教師以文本文件形式給出，格式為： ABCDEFGH (m個(gè)點(diǎn)名稱，大小寫代表不同點(diǎn))AEGHK (n個(gè)醫(yī)院名稱)AB11,AC15,EG9, FK24, (e條路段及長度)救護(hù)車總數(shù)及分派方案在運(yùn)行前從鍵盤輸入。 1.基本要求是救護(hù)車只接本醫(yī)院的病人，病人求救時(shí)該院無車就只能等待。(70)2.進(jìn)一步要求是：最近的醫(yī)院無車時(shí)，派最近的待命救護(hù)車。最好還能權(quán)衡一下： 是否等待該院的車回來更快？(85)3.還可改進(jìn)：除了可派正在待命的車外，還可派遣送達(dá)外

14、院病人后正在返點(diǎn)的車， 有時(shí)它比待命地點(diǎn)離病人更近。難度更高，實(shí)際要求這種情況下救護(hù)車逐路段地 返回，每到一個(gè)點(diǎn)都生成一個(gè)事件，較麻煩。4.顯示界面還可改為更直觀漂亮的圖形模式，設(shè)計(jì)更好的顯示方案。提示：1. 可以設(shè)3種事件：病人呼救，救護(hù)車到病人家，救護(hù)車到醫(yī)院。一個(gè)事件隊(duì)列，一個(gè)呼救等待隊(duì)列，n個(gè)救護(hù)車待命隊(duì)列。2. 初始化時(shí)設(shè)置第一個(gè)病人呼救事件插入事件隊(duì)列，以啟動(dòng)系統(tǒng)運(yùn)行。處理病人呼救事件時(shí)，將這個(gè)呼救排入呼救等待隊(duì)列，同時(shí)產(chǎn)生下一個(gè)病人呼救事件。3. 無向網(wǎng)可用鄰接多重表。求出每個(gè)醫(yī)院到其他各點(diǎn)的最短路徑，每個(gè)點(diǎn)設(shè)一個(gè)由近到遠(yuǎn)的醫(yī)院列表。4. 參考教科書中第3章第5節(jié)：離散事件模擬。 四設(shè)備、環(huán)境 采用PC計(jì)算機(jī)，Turbo C(或Turbo C+)開發(fā)環(huán)境五. 課程設(shè)計(jì)步驟 1.上機(jī)前要求認(rèn)真分析題目要求,完成書面的總體設(shè)計(jì)和詳細(xì)設(shè)計(jì). 其中: -總體設(shè)計(jì)包括問題分析和總體方案設(shè)計(jì)(基本數(shù)據(jù)結(jié)構(gòu)、算法思路、功能設(shè)計(jì)、模塊劃 分). 形式可用圖表,文字說明. -詳細(xì)設(shè)計(jì)包括:每個(gè)模塊的功能,入出信息,處理邏輯,以及關(guān)鍵技術(shù)問題的具體解決 辦法. 2.完成