數(shù)據(jù)結(jié)構(gòu)、OOP設(shè)計任務(wù)書

一、課程設(shè)計目的訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識，獨立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識，編寫程序求解指定問題。初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；提高綜合運用和方法所學(xué)的理論知識獨立分析和解決問題的能力；培養(yǎng)學(xué)生運用自頂向下逐層分解的模塊化結(jié)構(gòu)設(shè)計思想、面向?qū)ο蟮脑O(shè)計方法，完成系統(tǒng)的設(shè)計與實現(xiàn)；訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，鞏固、深化學(xué)生的理論知識，提高編程水平，并在此過程中培養(yǎng)他們嚴謹?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。二、課程設(shè)計任務(wù)與要求任務(wù)要求通過設(shè)計，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面加深對課程基本內(nèi)容的理解和綜合運用。設(shè)計題目從任務(wù)書所列選題表中選取。要求在處理每個題目時，要求從分析題目的需求入手，按設(shè)計抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計實現(xiàn)抽象數(shù)據(jù)類型、編制上機程序和上機調(diào)試等若干步驟完成題目，最終寫出完整的分析報告(可參見范例模板)。前期準備工作完備與否直接影響到后序上機調(diào)試工作的效率。在程序設(shè)計階段應(yīng)盡量利用已有的標準函數(shù)，加大代碼的重用率，鼓勵使用C++中的STL或是JAVA中的工具包。設(shè)計的題目要求達到一定工作量(300行以上代碼)，并具有一定的深度和難度。程序設(shè)計語言使用C++/JAVA，程序書寫規(guī)范，源程序需加必要的注釋。每位同學(xué)需提交可獨立運行的程序；每位同學(xué)需獨立提交設(shè)計報告書(每人一份)，要求編排格式統(tǒng)一、規(guī)范、內(nèi)容充實。

三、選題表序號題目名稱1校園導(dǎo)游圖系統(tǒng)2簡單的文本編輯器的實現(xiàn)3運動會分數(shù)統(tǒng)計系統(tǒng)4電梯模擬系統(tǒng)5停車場管理系統(tǒng)6四則運算自動練習(xí)測試軟件7電話號碼查詢系統(tǒng)8哈夫曼編碼、譯碼系統(tǒng)9計算器10九宮格11邏輯判斷12排序效率比較13列車時刻表的表示與查詢14計算幾何中判斷兩直線是否相交，求五邊形面積（向量計算方'式）15字典序查找16數(shù)據(jù)結(jié)果集的查找與分析17網(wǎng)絡(luò)監(jiān)聽信息解析18網(wǎng)絡(luò)防火墻仿真附頁:一、校園導(dǎo)游圖系統(tǒng).問題描述用無向網(wǎng)表示我校的校園景點平面圖，選取若干個有代表性的景點抽象成無向帶權(quán)圖，圖中頂點表示校內(nèi)各頂點，邊上權(quán)值表示路徑長度。.功能需求為來訪客人查詢各景點的相關(guān)信息；為來訪客人查詢圖中任意兩個景點間的最短路徑；為來訪客人查詢圖中任意兩個景點間的所有路徑；為來訪客人修改圖中頂點和邊的信息；為來訪客人增加景點和路徑；為來訪客人刪除景點和路徑；為來訪客人輸出對應(yīng)編號景點的信息；基本要求：建立無向圖G,圖中頂點ver表示主要景點，存放景點編號position>名稱name、簡介introduction等信息，圖中邊arc表示景點間的道路，存放路徑長度信息distanceo二、簡單的文本編輯器的實現(xiàn)問題描述輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行。功能需求分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；刪除某一字符或者子串，并將后面的字符前移。插入某一字符或者子串。查找某一字符或者子串。.基本要求存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式采用：分行輸出用戶輸入的各行字符；分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字數(shù)"輸出刪除某一字符串后的文章。三、運動會分數(shù)統(tǒng)計系統(tǒng).問題描述參加運動會有n個學(xué)校，學(xué)校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m，女子m+1m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。(m<=20，n<=20).功能需求可以輸入各個項目的前三名或前五名的成績；能統(tǒng)計各學(xué)?？偡?；可以按學(xué)校編號、學(xué)?？偡?、男女團體總分排序輸出；可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。.基本要求輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)(如果做得更好可以輸入學(xué)校的名稱，運動項目的名稱)輸出形式：有中文提示，各學(xué)校分數(shù)為整數(shù)；有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。四、電梯模擬系統(tǒng)問題描述模擬某校九層教學(xué)樓的電梯系統(tǒng)。該樓有一個自動電梯，能在每層停留。九個樓層由下全上依次稱為地下層、第一層、第二層、……第八層，其中第一層是大樓的進出層，即是電梯的“本壘層”，電梯“空閑”時，將來到該層候命。乘客可隨機地進出于任何層。2.功能需求對每個人來說，他有一個能容忍的最長等待時間，一旦等候電梯時間過長，他將放棄。電梯一共有七個狀態(tài)，即正在開門(Opening)>已開門(Opened)>正在關(guān)門(Closing)、已關(guān)門(Closed)、等待(Waiting)、移動(Moving)>減速(Decelerate)。模擬時鐘從0開始，時間單位為0.1秒。人和電梯的各種動作均要消耗一定的時間單位(簡記為t)，比如：有人進出時，電梯每隔40t測試一次，若無人進出，則關(guān)門；關(guān)門和開門各需要20t；每個人進出電梯均需要25t；如果電梯在某層靜止時間超過300t，則駛回1層侯命?；疽蟀磿r序顯示系統(tǒng)狀態(tài)的變化過程，即發(fā)生的全部人和電梯的動作序列。五、停車場管理系統(tǒng)問題描述設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序?；疽笠詶ＤM停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。六、四則運算自動練習(xí)測試軟件問題描述設(shè)計一個一年級小學(xué)生學(xué)習(xí)四則運算時自動出題系統(tǒng)。主菜單如圖(可以自行設(shè)計樣式)2.功能需求除法可以有余數(shù)，要求用戶輸入商和余數(shù)。注意被除數(shù)不能為0,除數(shù)要大于被除數(shù)；加法運算流程：系統(tǒng)出題，用戶給出答案，若答案正確，詢問用戶是否繼續(xù)？若用戶回答繼續(xù)，則出下一題，否則返回主菜單；如果用戶同一道題三次做錯，則給出正確答案。然后詢問用戶是否繼續(xù)？若用戶回答繼續(xù)，則出下一題，否則返回主菜單。其他運算流程和加法類似。退出菜單：用戶選擇子菜單“退出”后，出現(xiàn)結(jié)束信息。七、電話號碼查詢系統(tǒng).問題描述設(shè)計哈希表實現(xiàn)電話號碼查詢系統(tǒng)。.功能需求（1） 設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；（2） 從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立哈（3） 采用再哈希法解決沖突；（4） 查找并顯示給定電話號碼的記錄；（5） 查找并顯示給定用戶名的記錄。3.基本要求在哈希函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法（全少兩種），考察平均查找長度的變化。八、哈夫曼編碼、譯碼系統(tǒng)1.問題描述設(shè)計一個哈夫曼編碼、譯碼系統(tǒng)。對一個ASCII編碼的文本文件中的字符進行哈夫曼編碼，生成編碼文件；反過來，可將編碼文件譯碼還原為一個文本文件。功能需求從文件中讀入任意一篇英文短文(文件為ASCII編碼，擴展名為txt)；統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率(空格、換行、標點等也按字符處理)；根據(jù)字符頻率構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼；將文本文件利用哈夫曼樹進行編碼，存儲成壓縮文件(編碼文件后綴名.huf)基本要求(1)用哈夫曼編碼來存儲文件，并和輸入文本文件大小進行比較，計算文件壓縮率；⑵進行譯碼，將huf文件譯碼為ASCII編碼的txt文件，與原txt文件進行比較。九、計算器1.問題描述仿照windows附件完成可視化界面，完成具有優(yōu)先級功能的算術(shù)計算。功能需求按鍵輸入，輸出整數(shù)，小數(shù)的加減乘除計算結(jié)果要求考慮符號的優(yōu)先級。即2+3*5輸出17基本要求（1）可以用可視化界面模擬數(shù)據(jù)顯示屏和按鍵，也可以用鍵盤上的小鍵盤模擬輸入，屏顯利用計算機屏幕（文本方式）（2）設(shè)定開關(guān)鍵ON/OFF，修正鍵CE清除鍵十九宮格三行三列的棋盤落子，三子成一線即可見輸贏十一、命題邏輯判斷1.問題描述命題邏輯的機器判斷是人工智能的重要應(yīng)用。命題是依照一些題設(shè)來得出結(jié)論。功能需求如A、B、C、D為四個整數(shù)，題設(shè)中A>B,并且B>C結(jié)論是A>C。計算機也可依據(jù)題設(shè)得出結(jié)論；如果題設(shè)變?yōu)锳>B并且B>C，C>A，命題有錯誤則輸出“沖突”。基本要求用〉，<之類的關(guān)系表達式作為輸入數(shù)據(jù)，實現(xiàn)4個整數(shù)A，B，C，D之間的關(guān)系結(jié)論，采用合理的數(shù)據(jù)結(jié)構(gòu)描述問題模型。確定正確的存儲關(guān)系。輸入關(guān)系表達式字符串，輸出命題的結(jié)論。對關(guān)系運算增加=，<>號，再進一步設(shè)計相關(guān)的程序代碼。十二、排序效率測試與比較1.問題描述選取四類經(jīng)典排序方法插入排序，交換排序、選擇排序、歸并排序，進行執(zhí)行的時間效率和交換次數(shù)的比較分析。功能需求（1） 實驗分多組進行，分別對待排數(shù)據(jù)500個，1000個、20000個三種不同規(guī)模情況進對比，比運行時間、移動元素的次數(shù)。（2） 隨機數(shù)產(chǎn)生過程中，分四種情況產(chǎn)生數(shù)據(jù)，順序、逆序、基本有序、隨機無序，然后比較次數(shù)?；疽螅?） 數(shù)據(jù)利用隨機數(shù)自動生成，利用時間類庫函數(shù)計算運行時間。（2） 統(tǒng)計移動次數(shù)，并制表列出，書寫報告分析原因。十三、搜索結(jié)果集的并集1.問題描述在當(dāng)前常用的搜索引擎中，輸入關(guān)鍵字空格分隔，表示結(jié)果集的并集功能需求找出同時符合多關(guān)鍵字的記錄，即相似度最高的結(jié)果。其次再輸出符合少量關(guān)鍵字的記錄。依照相似度排序基本要求兩個關(guān)鍵字查詢?yōu)榛疽?，增加關(guān)鍵字，則可加分。十四、列車時刻表的表示與查詢1.問題描述設(shè)計數(shù)據(jù)文件將現(xiàn)行的列車運行詳細信息進行存儲，并支持用戶完成基本查詢。功能需求提供必要的列車車次，途經(jīng)城市站點，列車時刻，運行里程，分段票價的信息查詢。進一步提供城市間一次中轉(zhuǎn)的路線?；疽螅?） 建立合理的數(shù)據(jù)文件，數(shù)據(jù)量能夠滿足常用車次的查詢。（2） 設(shè)計數(shù)據(jù)存儲結(jié)構(gòu)，保證查找效率，完成列車行車信息的基本查詢?yōu)樽罨疽?。?）完成換乘方式下路線導(dǎo)航功能起評分為良十五、拼音輸入法的設(shè)計仿真1.問題描述輸入漢語拼