《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)教學(xué)任務(wù)書

1、在世界上我們只活一次，所以應(yīng)該愛惜光陰。必須過真實(shí)的生活，過有價(jià)值的生活。巴甫洛夫 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)任務(wù)書 計(jì)算機(jī)2007-1 課程設(shè)計(jì)周數(shù)：第20周 指導(dǎo)老師：劉文娟 一、課程設(shè)計(jì)的目的 數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對象在計(jì)算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)

2、學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要達(dá)到以下目的： * 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力； * 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能； * 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力； * 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。 二、課程設(shè)計(jì)的基本要求 1、獨(dú)立思考，獨(dú)立完成：課程設(shè)計(jì)中各任務(wù)的設(shè)計(jì)和調(diào)試要求獨(dú)立完成，遇到問題可以討論，但不可以拷貝。 2、做好上機(jī)準(zhǔn)備：每次上機(jī)前，要事先編制好準(zhǔn)備調(diào)試的程序，認(rèn)真想好調(diào)試步驟和有關(guān)環(huán)境的設(shè)

3、置方法，準(zhǔn)備好有關(guān)的文件。 3、按照課程設(shè)計(jì)的具體要求建立的功能模塊，每個(gè)模塊要求按照如下幾個(gè)內(nèi)容認(rèn)真完成； 其中包括： a）需求分析： 在該部分中敘述，每個(gè)模塊的功能要求 b）概要設(shè)計(jì) 在此說明每個(gè)部分的算法設(shè)計(jì)說明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說明（如果指定存儲(chǔ)結(jié)構(gòu)請寫出該存儲(chǔ)結(jié)構(gòu)的定義）。 c）詳細(xì)設(shè)計(jì) 各個(gè)算法實(shí)現(xiàn)的源程序，對每個(gè)題目要有相應(yīng)的源程序（可以是一組源程序，每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)） 源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。 d）調(diào)試分析 測試數(shù)據(jù)，測試輸出的結(jié)果，時(shí)間復(fù)雜度分析，和每

4、個(gè)模塊設(shè)計(jì)和調(diào)試時(shí)存在問題的思考（問題是哪些？問題如何解決？），算法的改進(jìn)設(shè)想。 e）課程設(shè)計(jì)總結(jié)：（保存在word文檔中）總結(jié)可以包括：課程設(shè)計(jì)過程的收獲、遇到 問題、遇到問題解決問題過程的思考、程序調(diào)試能力的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在課程設(shè)計(jì)過程中對數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識(shí)等內(nèi)容； 4、每組實(shí)現(xiàn)的結(jié)果必須進(jìn)行檢查和演示；程序源代碼和程序的說明文件必須上交，作為考核內(nèi)容的一部分；（上交時(shí)每人交一份，文件夾的取名規(guī)則為："學(xué)號(hào) 姓名"，如"200413498 高魁"。該文件夾下至少包括："源代碼"、"課程設(shè)計(jì)報(bào)告"

5、;、"可執(zhí)行文件"。由學(xué)習(xí)委員收集刻盤按規(guī)定時(shí)間統(tǒng)一上交）。 5、報(bào)告提交 時(shí)間：第20周星期五檢查，第20周星期五下午5點(diǎn)之前由學(xué)習(xí)委員收集上交，遲交無成績。 形式：課程設(shè)計(jì)報(bào)告(要求打?。┖碗娮游臋n(統(tǒng)一刻盤）。 三、課程設(shè)計(jì)內(nèi)容： 1、排序算法演示系統(tǒng) 【問題描述】 設(shè)計(jì)一個(gè)測試程序比較幾種內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)以取得直觀感受。 【基本要求】 (1實(shí)現(xiàn)各種內(nèi)部排序。包括冒泡排序，直接選擇排序，希爾排序，快速排序，堆排序。 (2 待排序的元素的關(guān)鍵字為整數(shù)。其中的數(shù)據(jù)要用隨機(jī)數(shù)產(chǎn)生(如10000個(gè)，至少用5組不同的數(shù)據(jù)做比較，再使用各種算法對其進(jìn)行排序，

6、記錄其排序時(shí)間，再匯總比較。 (3 演示程序以人機(jī)對話的形式進(jìn)行。每次測試完畢顯示各種比較指標(biāo)值的列表，用餅圖或條形圖進(jìn)行表示，以便比較各種排序的優(yōu)劣。 (4 界面友好，易與操作。采用菜單方式進(jìn)行選擇。 【選做內(nèi)容】 (1 對不同表長進(jìn)行比較； (2 驗(yàn)證各算法的穩(wěn)定性； (3 輸出界面的優(yōu)化。 (4 使用漢字顯示。 2、校園導(dǎo)游咨詢系統(tǒng) 【問題描述】 設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。 【基本要求】 (1 設(shè)計(jì)安徽理工大學(xué)的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。 (2 為來訪客人

7、提供圖中任意景點(diǎn)相關(guān)信息的查詢。 (3 為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡單路徑。 【選做內(nèi)容】 (1 系統(tǒng)功能的完善； (2 提供求任意兩個(gè)景點(diǎn)之間的所有路徑的功能； (3 提供校園圖中多個(gè)景點(diǎn)的最佳訪問路線查詢，即求途經(jīng)這多個(gè)景點(diǎn)的最佳（短）路徑。 (4 使用漢字顯示。 3、通訊錄 【問題描述】 設(shè)計(jì)散列表實(shí)現(xiàn)通訊錄查找系統(tǒng)。 【基本要求】 (1 設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址； (2 從鍵盤輸入各記錄，分別以電話號(hào)碼為關(guān)鍵字建立散列表； (3 采用線性探測再散列法解決沖突； (4 查找并顯示給定電話號(hào)碼的記錄； (5 通訊錄信息文件

8、保存 ； (6 要求人機(jī)界面友好，使用圖形化界面； 【選做內(nèi)容】 (1 系統(tǒng)功能的完善； (2 設(shè)計(jì)不同的散列函數(shù)，比較沖突率； (3 在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。 (4 使用漢字顯示。 【實(shí)現(xiàn)提示】 如果不用界面編程，可用以下函數(shù)實(shí)現(xiàn)： 主函數(shù)：根據(jù)選單的選項(xiàng)調(diào)用各函數(shù)，并完成相應(yīng)的功能。 Menu(的功能：顯示英文提示選單。 Quit(的功能：退出選單。 Create(的功能：創(chuàng)建新的通訊錄。 Append(的功能：在通訊錄的末尾寫入新的信息，并返回選單。 Find(：查詢某人的信息，如果找到了，則顯示該人的信息，如果沒有則提示通訊錄中沒

9、有此人的信息，并返回選單。 Alter(的功能：修改某人的信息，如果未找到要修改的人，則提示通訊錄中沒有此人的信息，并返回選單。 Delete(的功能：刪除某人的信息，如果未找到要?jiǎng)h除的人，則提示通訊錄中沒有此人的信息，并返回選單。 List(的功能：顯示通訊錄中的所有記錄。 Save(的功能：保存通訊錄中的所有記錄到指定文件中。 Load(的功能：從指定文件中讀取通訊錄中的記錄。 4、哈夫曼編碼/譯碼器 【問題描述】 設(shè)計(jì)一個(gè)哈夫曼編碼/譯碼系統(tǒng)，對一個(gè)文本文件中的字符進(jìn)行哈夫曼編碼，生成編碼文件（壓縮文件，后綴名.cod）；反過來，可將一個(gè)壓縮文件譯碼還原為一個(gè)文本文件(.txt。 【基本

10、要求】 (1 輸入一個(gè)待壓縮的文本文件名， 統(tǒng)計(jì)文本文件中各字符的個(gè)數(shù)作為權(quán)值，生成哈夫曼樹； (2 將文本文件利用哈夫曼樹進(jìn)行編碼，生成壓縮文件（后綴名cod）， (3 輸入一個(gè)待解壓的壓縮文件名稱,并利用相應(yīng)的哈夫曼樹將編碼序列譯碼； (4 顯示指定的壓縮文件和文本文件； (5 界面友好，易與操作。采用菜單方式進(jìn)行選擇。 【選做內(nèi)容】 (1 把哈夫曼編碼用二進(jìn)制位緊縮到一個(gè)變量中，利用位運(yùn)算進(jìn)行真正的數(shù)據(jù)壓縮，并求壓縮比。 (2 顯示哈夫曼樹； (3 使用漢字顯示。 在世界上我們只活一次，所以應(yīng)該愛惜光陰。必須過真實(shí)的生活，過有價(jià)值的生活。巴甫洛夫 5、二叉樹遍歷算法集成 功能要求： （1

11、） 界面友好，易于操作?？刹捎貌藛位蚱渌藱C(jī)對話方式進(jìn)行選擇。 （2） 實(shí)現(xiàn)各種二叉樹的遍歷。包括先序遍歷、中序遍歷、后序遍歷的遞歸或非遞歸算法。 （3） 要求能查找任一結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼。 （4） 演示程序以人機(jī)對話的形式進(jìn)行。每次測試完畢正確顯示各種遍歷序列。 在上交資料中請寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程 問題描述： n只猴子要選大王，選舉方法是：所有猴子按1，2，.，n編號(hào)圍坐一圈，從第1號(hào)開始按1，2，.，m報(bào)數(shù)，凡報(bào)到m號(hào)的退出圈外，如此循環(huán)報(bào)數(shù)，直到圈內(nèi)剩下一只猴子時(shí)，這只猴子就是大王。 基本要求： 分別選擇順序表和單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬整

12、個(gè)過程，并依次輸出出列的各猴子的編號(hào)和最終所選出猴王的編號(hào)。 12、停車場管理 問題描述： 設(shè)停車場是一個(gè)可以停放n輛汽車的狹長通道，且只有一個(gè)大門可以供車輛進(jìn)出。車輛按到達(dá)停車場時(shí)間的早晚依次從停車場最里向大門口處停放（最先到達(dá)的第一輛車放在停車場的最里面）。如果停車場已放滿n輛車，則后來的車只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進(jìn)入停車場。停車場內(nèi)如有某輛車要開走，在它之后進(jìn)入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進(jìn)場。每輛車在離開停車場時(shí)，都應(yīng)根據(jù)它在停車場內(nèi)停留的時(shí)間長短交費(fèi)。如果停留在便道上的車未進(jìn)停車場

13、就要離去，允許其離去，不收停車費(fèi)，并且仍然保持在便道上等待的車輛次序。編制一程序模擬該停車場的管理。 提示： 停車場采用棧式結(jié)構(gòu)，停車場外的便道采用隊(duì)列結(jié)構(gòu)（即便道就是等候隊(duì)列）。 13、文本編輯器 功能要求：運(yùn)用鏈表與數(shù)組來處理字符串的各項(xiàng)操作。如插入，刪除，查找，替換，顯示等等。 提示：對于自定義的文本文件"*.txt"，其每一行表示一個(gè)結(jié)點(diǎn)用單鏈表來實(shí)現(xiàn)，可以進(jìn)行一行的修改，刪除，添加等；每一行中的字符可用一維數(shù)組來存儲(chǔ)，這樣可以利用數(shù)組的特性方便地進(jìn)行插入，刪除，替換，甚至可以進(jìn)行排序操作！ 14、迷宮問題 問題描述: 在迷宮中求從入口到出口的一條簡單路徑。 提示：

14、 迷宮用一個(gè)二維字符數(shù)組maze來表示，用x表示縱坐標(biāo)，y表示橫坐標(biāo)。 （1）定義探索迷宮的四個(gè)方向：RIGHT為向右，DOWN向下，LEFT向左，UP向上，用Switch語句根據(jù)當(dāng)前的位置坐標(biāo)來判斷下一步要探索的方向求出下一步要走的位置坐標(biāo)。 （2） 探索迷宮的四個(gè)方向的坐標(biāo)表示：RIGHT（x,y+1）, DOWN(x+1,y, LEFT(x,y-1, UP(x-1,y。 （3）對每個(gè)方向探索時(shí)，用0表示可通過，用1表示不能通過是障礙，對探索過的位置加以標(biāo)記。把每一個(gè)可以通過的位置坐標(biāo)放入棧中，最后打印輸出路徑。 （4）根據(jù)二維字符數(shù)組和加標(biāo)記的位置坐標(biāo)，輸出迷宮的圖形。 15、電梯模擬運(yùn)

15、行 問題描述： 模擬我校九層教學(xué)樓的電梯系統(tǒng)。該樓有一個(gè)自動(dòng)電梯，能在每層停 留。九個(gè)樓層由下至上依次稱為第一層、第二層、.第九層，其中第一層是大樓的進(jìn)出層，即是電梯的"本壘層"，電梯"空閑"時(shí)，將來到該層候命。 乘客可隨時(shí)地進(jìn)出于任何層。對于每個(gè)人來說，他有一個(gè)能容忍的最長等待時(shí)間，一旦等候電梯時(shí)間過長，他將放棄。 模擬時(shí)鐘從0開始，時(shí)間單位為0.1秒。人和電梯的各種動(dòng)作均要消耗一定的時(shí)間單位（簡記為t），比如：有人進(jìn)出時(shí)，電梯每隔40t檢測一次，若無人進(jìn)出，則關(guān)門；關(guān)門和開門各需要20t；每個(gè)人進(jìn)出電梯均需要25t；如果電梯在某層精致時(shí)間超過300t

16、，則駛回1層候命。 基本要求： 按時(shí)序顯示系統(tǒng)狀態(tài)的變化過程，即發(fā)生的全部人和電梯的動(dòng)作序列。 （1）用系統(tǒng)計(jì)時(shí)，每當(dāng)有新的動(dòng)作要輸入時(shí)要暫停計(jì)時(shí)，等輸入完成后即可繼續(xù)計(jì)時(shí)。 （2）輸入各個(gè)動(dòng)作，最后，輸入完畢后，可以保存所有動(dòng)作序列，并有序輸出。 四、上交作業(yè)及成績評定 1、上交要求 上交設(shè)計(jì)報(bào)告和相關(guān)光盤。其中設(shè)計(jì)報(bào)告要以打印文稿的形式上交。光盤內(nèi)容包括程序源碼設(shè)計(jì)報(bào)告的電子文檔。整個(gè)班級(jí)的設(shè)計(jì)均刻在一張光盤上。（上交時(shí)每人交一份，文件夾的取名規(guī)則為："學(xué)號(hào) 姓名"，如"200711111 王文"。該文件夾下至少包括："源代碼"、"