數(shù)據(jù)結構與算法分析課程設計指導書

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

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

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

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

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

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

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

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

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

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

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

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

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

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