數(shù)據(jù)結(jié)構(gòu)大型實(shí)驗(yàn)要求

1、大型實(shí)驗(yàn)指導(dǎo)面向?qū)ο蟮某淘O(shè)計(jì)（OOP）方法與一般的設(shè)計(jì)方法不同，它使編程人員可以把精力集中在操作的對(duì)象而不是軟件要完成的功能上。它將系統(tǒng)看作是對(duì)象的集合，通過(guò)對(duì)象之間的相互作用（消息傳遞）完成任務(wù)，通過(guò)類和對(duì)象把數(shù)據(jù)和處理數(shù)據(jù)的操作結(jié)合為一個(gè)整體。對(duì)復(fù)雜軟件系統(tǒng)的設(shè)計(jì)，幾乎所有的設(shè)計(jì)方法都采用某種分而治之的策略。面向?qū)ο蟮某绦蛟O(shè)計(jì)以對(duì)象作為設(shè)計(jì)的基礎(chǔ)，具有一下優(yōu)點(diǎn)： 便于重復(fù)使用已有代碼，節(jié)省開(kāi)發(fā)時(shí)間。 程序具有較好的結(jié)構(gòu)性。 可以以類為單位獨(dú)立進(jìn)行程序測(cè)試。 容易根據(jù)用戶的需要進(jìn)行擴(kuò)充。設(shè)計(jì)步驟需求分析和任務(wù)定義軟件設(shè)計(jì)編碼及靜態(tài)檢查測(cè)試總結(jié)和書(shū)寫(xiě)大型實(shí)驗(yàn)報(bào)告需求分析 和任務(wù)定義 問(wèn)題要做什

2、么？限制條件是什么？ 對(duì)所需要完成的任務(wù)作出明確的回答 輸入數(shù)據(jù)的要求 輸出數(shù)據(jù)的要求 界面的要求 解決問(wèn)題的途徑，確定具體算法 確定合法的和非合法的測(cè)試數(shù)據(jù)系統(tǒng)設(shè)計(jì)在設(shè)計(jì)這一步驟中分?jǐn)?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、對(duì)象設(shè)計(jì)和消息設(shè)計(jì)：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。確定主要的數(shù)據(jù)結(jié)構(gòu)，包括元素類型（對(duì)象）以及相關(guān)的操作。對(duì)象設(shè)計(jì)。定義內(nèi)部類，為類屬性確定具體的數(shù)據(jù)結(jié)構(gòu)，并確定類之間的關(guān)系。消息設(shè)計(jì)。使用對(duì)象間的協(xié)作和對(duì)象-關(guān)系模型，設(shè)計(jì)消息模型。綜合考慮系統(tǒng)功能，對(duì)系統(tǒng)進(jìn)行求精操作：使得系統(tǒng)類結(jié)構(gòu)清晰、合理、便于操作和易于測(cè)試；對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作的規(guī)格說(shuō)明做出進(jìn)一步的求精，補(bǔ)充類的屬性和操作；對(duì)操作算法進(jìn)行規(guī)范性描述（用圖形

3、工具進(jìn)行算法描述）。在求精過(guò)程中，盡量避免陷入語(yǔ)言細(xì)節(jié)，不必過(guò)早表述輔助存儲(chǔ)結(jié)構(gòu)和局部變量。編碼實(shí)現(xiàn)和靜態(tài)檢查編碼是把系統(tǒng)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言的過(guò)程。源代碼除了要實(shí)現(xiàn)具體的算法外，還必須一定的組織結(jié)構(gòu)和視覺(jué)效果： 每個(gè)函數(shù)體，一般不超過(guò)80行，最長(zhǎng)不超過(guò)100行，否則應(yīng)分割成較小的函數(shù)； 給源代碼相應(yīng)的程序段或語(yǔ)句加上適當(dāng)?shù)淖⑨?；源代碼采用縮格書(shū)寫(xiě)。認(rèn)真的靜態(tài)檢查是必不可少的：源代碼是否真正實(shí)現(xiàn)具體的算法描述；在源代碼易于理解的基礎(chǔ)上，簡(jiǎn)化及優(yōu)化源代碼；用一組測(cè)試數(shù)據(jù)手工執(zhí)行程序；通過(guò)閱讀或給別人見(jiàn)解自己的程序而深入全面地理解程序邏輯，在這個(gè)過(guò)程中加入一些新的注釋和斷言。在靜態(tài)檢

4、查中對(duì)于非法的數(shù)據(jù)輸入和操作要加以控制和處理。測(cè)試的目的是為了發(fā)現(xiàn)軟件中存在的問(wèn)題，并加以修正。面向?qū)ο蟮臏y(cè)試可以分為兩個(gè)部分：對(duì)象測(cè)試，在對(duì)象設(shè)計(jì)階段進(jìn)行測(cè)試，檢查成員函數(shù)對(duì)各種輸入?yún)?shù)能否正確完成設(shè)計(jì)的功能，得到正確的結(jié)果。消息傳遞測(cè)試，測(cè)試各對(duì)象之間的函數(shù)調(diào)用與被調(diào)用聯(lián)系，以確保消息傳遞的正確性。測(cè)試的一般步驟包括： 設(shè)計(jì)一組或幾組測(cè)試用例，包括合法的和非法的測(cè)試數(shù)據(jù)； 根據(jù)測(cè)試用例，得到預(yù)期的結(jié)果； 將測(cè)試用例作為輸入數(shù)據(jù)代入軟件系統(tǒng)并運(yùn)行系統(tǒng)。如果運(yùn)行結(jié)果與預(yù)期的結(jié)果一致，則說(shuō)明算法或源代碼正確；否則，要修改算法和源代碼。上機(jī)準(zhǔn)備和上機(jī)測(cè)試上機(jī)準(zhǔn)備包括：高級(jí)語(yǔ)言文本的擴(kuò)充和限制；熟悉

5、機(jī)器的操作系統(tǒng)和語(yǔ)言集成環(huán)境的用戶手冊(cè)，尤其是常用的命令的操作；掌握調(diào)試工具，考慮調(diào)試方案，設(shè)計(jì)測(cè)試數(shù)據(jù)并手工得出正確結(jié)果。上機(jī)測(cè)試時(shí)，要帶一本高級(jí)語(yǔ)言教材或手冊(cè)。首先，在每個(gè)對(duì)象設(shè)計(jì)時(shí)要進(jìn)行對(duì)象測(cè)試；然后，在程序流程調(diào)試時(shí)要測(cè)試對(duì)象之間的關(guān)系和作用。往往整個(gè)測(cè)試過(guò)程是以上兩個(gè)部分的反復(fù)迭代過(guò)程。測(cè)試后，認(rèn)真整理源程序及其注釋，印出帶有完整注釋的且格式良好的源程序清單和結(jié)果。實(shí)習(xí)報(bào)告規(guī)范1 軟件需求分析1.1 軟件達(dá)到的目的1.2 軟件功能說(shuō)明1.3 設(shè)計(jì)環(huán)境2 系統(tǒng)設(shè)計(jì)2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2.1.1 主要數(shù)據(jù)結(jié)構(gòu)類型的選擇2.1.2 數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)對(duì)象以及具體的操作的確定2.2 對(duì)象設(shè)計(jì)

6、2.2.1 系統(tǒng)中的類及對(duì)象2.2.2 類圖設(shè)計(jì)2.3 消息設(shè)計(jì)2.3.1 對(duì)象之間的消息傳遞說(shuō)明2.3.2 關(guān)鍵算法設(shè)計(jì)2.4 界面設(shè)計(jì)3 系統(tǒng)實(shí)現(xiàn)3.1 類的定義3.2 關(guān)鍵源代碼的實(shí)現(xiàn)3.2.1 主函數(shù)源代碼3.2.2 （其他功能源代碼實(shí)現(xiàn)）3.3 軟件測(cè)試4 結(jié)果分析與總結(jié)4.1 結(jié)果分析4.2 總結(jié)大型實(shí)驗(yàn)課題集合運(yùn)算及實(shí)現(xiàn)校園導(dǎo)游咨詢系統(tǒng)的實(shí)現(xiàn) 哈夫曼編/譯碼器的實(shí)現(xiàn)航空客運(yùn)訂票系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)小型圖書(shū)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)內(nèi)部排序的實(shí)現(xiàn)及比較課程管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)停車場(chǎng)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)集合的運(yùn)算及實(shí)現(xiàn)【問(wèn)題描述】 實(shí)現(xiàn)集合的基本操作：并、差、交及包含判斷?！净疽蟆?1、集

7、合中數(shù)據(jù)的規(guī)范約定（按字符序列排列） 2、兩個(gè)集合的并、差、交運(yùn)算 3、集合包含判斷（子集判斷） 4、元素的包含判斷 5、各種操作提示明確。【測(cè)試數(shù)據(jù)】 由合法的或非法的數(shù)據(jù)產(chǎn)生規(guī)范的集合 【實(shí)現(xiàn)提示】 1.用帶表頭結(jié)點(diǎn)的順序表或鏈表有序存儲(chǔ)集合中元素； 2.采用合適的算法提高集合的操作，例如交集可以用差集實(shí)現(xiàn)；順序表中查詢可以二分查找方法，等等。 校園導(dǎo)游咨詢系統(tǒng)的實(shí)現(xiàn)【問(wèn)題描述】 設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢服務(wù)。各種操作提示明確?！净疽蟆?1、設(shè)計(jì)你的學(xué)校的校園的平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑

8、，存放路徑長(zhǎng)度。 2、為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。 3、為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)間的一條最短的簡(jiǎn)單路徑。 4、景點(diǎn)可以添加或者刪除。【測(cè)試數(shù)據(jù)】 根據(jù)實(shí)際情況指定（以學(xué)院為例）。【實(shí)現(xiàn)提示】 一般情況下，校園的單路是雙向通的，為了簡(jiǎn)化設(shè)計(jì)，可設(shè)校園平面圖是一個(gè)有向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。哈夫曼編碼/譯碼器的實(shí)現(xiàn)【問(wèn)題描述】 設(shè)計(jì)一個(gè)哈夫曼的編碼/譯碼器?！净疽蟆?1、 初始化：建立一棵哈夫曼樹(shù)。 2、 編碼：利用建立好的哈夫曼樹(shù)進(jìn)行編碼，結(jié)果存入字符串code中。 3、利用哈夫曼樹(shù)將code中的代碼進(jìn)行譯碼，結(jié)果存入字符串text中。 4、

9、區(qū)分譯碼失敗的各種情況。 5、各種操作提示明確。【測(cè)試數(shù)據(jù)】 可以利用教科書(shū)中實(shí)例調(diào)試程序【實(shí)現(xiàn)提示】 1、用順序表存儲(chǔ)哈夫曼樹(shù) 2、用二叉鏈表存儲(chǔ)哈夫曼樹(shù) 航空客運(yùn)訂票系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)【問(wèn)題描述】 航空客運(yùn)訂票的業(yè)務(wù)活動(dòng)包括：查詢航線、預(yù)訂票和退票等。【基本要求】 1、 每條航線所擁有的信息有：航班號(hào)、終點(diǎn)、乘員定額、余票量、已訂票量和已訂票客戶名單（包括姓名、身份證號(hào)碼、電話、訂票量）。 2、 系統(tǒng)主要實(shí)現(xiàn)的功能有： (1) 初始化：輸入每條航線的原始信息，訂票客戶名單為空； (2) 查詢航線和訂票信息：根據(jù)客戶提出的終點(diǎn)，輸出相關(guān)信息； (3) 訂票：根據(jù)用戶提出的要求（終點(diǎn)站名，訂票數(shù)

10、額）查詢航班號(hào)及余票額情況，若尚有余票，則為用戶辦理訂票手續(xù)；若余票額少于訂票數(shù)額，則不予辦理; (4) 退票 ：根據(jù)客戶提出的要求，為客戶辦理退票手續(xù)。 3、要有簡(jiǎn)明的界面，且各種操作的提示明確。 【 測(cè)試數(shù)據(jù)】 對(duì)輸入數(shù)據(jù)要有合法和非法約定【實(shí)現(xiàn)提示】 航線信息基本不變，可以用順序表實(shí)現(xiàn)，而訂票客戶名單可以考慮用有序鏈表實(shí)現(xiàn)，便于插入和刪除和查詢。小型圖書(shū)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)【問(wèn)題描述】 圖書(shū)管理基本業(yè)務(wù)包括：對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等?！净疽蟆?1、 每種書(shū)的登記內(nèi)容至少包括：書(shū)號(hào)、書(shū)名、作者、現(xiàn)存量和總庫(kù)存量。 2、 系統(tǒng)實(shí)現(xiàn)的功能如下： （1）采編入庫(kù)：將新書(shū)添

11、加到圖書(shū)帳目中。如果書(shū)已存在，則只增加總庫(kù)存量。 （2）清除庫(kù)存：將指定的書(shū)從圖書(shū)帳目中刪除。 （3）借閱：若現(xiàn)存量大于0，則登記借閱信息及歸還日期。 （4）歸還：注銷對(duì)借閱者的登記，改變現(xiàn)存量。 3、各種操作的提示明確?！緶y(cè)試數(shù)據(jù)】 對(duì)輸入數(shù)據(jù)要有合法和非法約定【實(shí)現(xiàn)提示】 1、確定系統(tǒng)中所有類，并確定類之間關(guān)系； 2、用順序表或者鏈表存儲(chǔ)相關(guān)信息； 3、根據(jù)具體信息的存儲(chǔ)結(jié)構(gòu)確定相關(guān)操作算法。內(nèi)部排序的實(shí)現(xiàn)及比較【問(wèn)題描述】 設(shè)定隨機(jī)數(shù)據(jù)比較指定排序算法的關(guān)鍵字比較和關(guān)鍵子移動(dòng)次數(shù)。【基本要求】 1、對(duì)以下6中排序方法進(jìn)行比較： 起泡排序、直接插入排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆

12、排序。 2、 用隨機(jī)函數(shù)產(chǎn)生不少于100個(gè)11000的整數(shù)關(guān)鍵字。 3、輸出排序后的序列（每行輸出10個(gè)）。 4、輸出各排序方法的比較次數(shù)和移動(dòng)次數(shù)的比較結(jié)果?！緶y(cè)試數(shù)據(jù)】 數(shù)據(jù)由隨機(jī)產(chǎn)生器生成?！緦?shí)現(xiàn)提示】 根據(jù)不同排序方法確定不同的存儲(chǔ)結(jié)構(gòu)。課程管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)【問(wèn)題描述】 設(shè)計(jì)一個(gè)簡(jiǎn)易的課程管理系統(tǒng)，有求對(duì)學(xué)生的課程成績(jī)可以進(jìn)行查詢、輸入以及輸出?！净疽蟆?1、輸入基本信息，如班級(jí)信息、學(xué)生信息以及課程信息 2、可以以個(gè)人或班級(jí)名義查詢指定或所有課程成績(jī) 3、輸入指定班級(jí)的某個(gè)課程成績(jī) 4、修改個(gè)別學(xué)生的課程成績(jī) 5、如學(xué)生退學(xué)或別的原因，可以刪除學(xué)生信息或課程成績(jī) 6、各種操作提示明確。【測(cè)試數(shù)據(jù)】 輸入數(shù)據(jù)的格式規(guī)范要求 【實(shí)現(xiàn)提示】 1、確定系統(tǒng)中所有類，并確定類之間關(guān)系； 2、用順序表或者鏈表存儲(chǔ)相關(guān)信息； 3、根據(jù)具體信息的存儲(chǔ)結(jié)構(gòu)確定相關(guān)操作算法。 停車場(chǎng)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)【問(wèn)題描述】 假設(shè)停車場(chǎng)是個(gè)多個(gè)單向通道，設(shè)計(jì)一個(gè)簡(jiǎn)易的停車場(chǎng)收費(fèi)系統(tǒng)管理車輛的進(jìn)出及等候停車操作，并計(jì)算停車費(fèi)用?！净疽蟆?1、停車及計(jì)時(shí)：按照停車通道序號(hào)進(jìn)行停車，停車成功后開(kāi)始計(jì)時(shí)（只需記錄整時(shí)） 2、離開(kāi)及收費(fèi)：