經(jīng)典：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院12021/8/61. 從指定的題目中任選一題，獨(dú)立完成，不得自行設(shè)計(jì)指定題目外的其它題目，不得抄襲。2. 成績(jī)構(gòu)成： 平時(shí)成績(jī)30%，點(diǎn)名6次，每次5分。 課程設(shè)計(jì)答辯，包括演示程序，回答老師提問30%，（如果回答問題中發(fā)現(xiàn)程序不是本人開發(fā)，直接判定不及格）。 課程設(shè)計(jì)報(bào)告，按照指定格式和模板編寫，不得隨意更改結(jié)構(gòu)。（報(bào)告必須與答辯程序相符，如果不符合或發(fā)現(xiàn)抄襲，直接判定不及格）22021/8/61.報(bào)告內(nèi)容必須包括以下部分 選題的意義與目的（1-2頁）所選題目的任務(wù)要求選題的意義課程設(shè)計(jì)的目標(biāo) 算法分析

2、，分析所選題目需要用到的數(shù)據(jù)結(jié)構(gòu)算法，給出算法的基本思路或原理，繪制相關(guān)圖件（2-3頁） 程序設(shè)計(jì)與實(shí)現(xiàn)（10-15頁）設(shè)計(jì)程序的整體結(jié)構(gòu)，分析程序中存在的類，以及它們之間的關(guān)系，繪制UML類圖。對(duì)核心數(shù)據(jù)結(jié)構(gòu)類給出詳細(xì)函數(shù)接口說明。對(duì)關(guān)鍵數(shù)據(jù)結(jié)構(gòu)算法繪制流程圖，給出函數(shù)實(shí)現(xiàn)代碼。32021/8/6 程序運(yùn)行結(jié)果，選擇合適的測(cè)試數(shù)據(jù)，對(duì)程序進(jìn)行測(cè)試，給出測(cè)試用例以及對(duì)應(yīng)的程序運(yùn)行截圖（2-3頁） 結(jié)論，總結(jié)針對(duì)所選題目采用的數(shù)據(jù)結(jié)構(gòu)、算法和程序設(shè)計(jì)思路，說明取得的成果，論證所述方法的正確性，提一點(diǎn)進(jìn)一步研究的方向。（1頁） 參考文獻(xiàn)（不少于5篇）2. 報(bào)告正文采用宋體小四號(hào)，1.5倍行距書寫，

3、各個(gè)大部分之間要分頁。調(diào)整好版式，每頁不能有太多空白。圖要有標(biāo)號(hào)?？傢摂?shù)不少于20頁42021/8/61. 獨(dú)立設(shè)計(jì)程序，不得抄襲，不得從網(wǎng)上下載2. 開發(fā)平臺(tái)為Windows系列操作系統(tǒng)3. 編程語言推薦C+，也可以使用Java、C#等主流開發(fā)語言4. 開發(fā)工具對(duì)于C+/C#請(qǐng)采用VC6或VS2008/2010等微軟系列開發(fā)工具，對(duì)于Java請(qǐng)采用Eclipse5. 無論使用何種開發(fā)語言和工具，程序數(shù)據(jù)結(jié)構(gòu)和算法部分不得使用已有類庫或第三方類庫，必須自己編碼實(shí)現(xiàn)6. 代碼風(fēng)格統(tǒng)一，書寫規(guī)范，關(guān)鍵算法加入注釋7. 程序必須能正確編譯及運(yùn)行，答辯時(shí)程序不能正確編譯或主體功能不正確判定為不及格52

4、021/8/662021/8/6 允許用戶輸入帶變量x的函數(shù)表達(dá)式f(x)，并且可以設(shè)定變量范圍 根據(jù)教材3.1.4節(jié)介紹的表達(dá)式求值算法原理，利用棧實(shí)現(xiàn)帶變量的表達(dá)式求值 根據(jù)表達(dá)式求值結(jié)果和自變量范圍，離散均勻采樣繪制函數(shù)圖像 利用簡(jiǎn)單的二分法求方程的根要求程序具有UI界面能夠繪制函數(shù)圖像如果用戶輸入表達(dá)式有誤，可以提示錯(cuò)誤72021/8/682021/8/6 利用Windows控制臺(tái)API函數(shù)開發(fā)一個(gè)類似于vi的文本編輯器 能夠新建或打開已有的文本文件 在控制模式下按下鍵i，進(jìn)入編輯模型，在編輯模式下可以用方向鍵或PgUp、PgDn翻動(dòng)瀏覽文件，可以插入或刪除字符 在編輯模式下按Esc鍵

5、可以回到控制模式 在控制模式下輸入:q可以退出程序 在控制模式下輸入:w可以保存文件92021/8/6 在控制模式下輸入:f 查找字符串，可以在文件中查找并定位字符串 在控制模式下輸入:r 查找字符串 替換字符串，可以替換從當(dāng)前光標(biāo)位置開始的第一個(gè)匹配字符串 在控制模式下輸入:ra查找字符串 替換字符串，可以替換文件中所有匹配字符串 所有文件編輯功能實(shí)現(xiàn)必須是在文本模式下，不得簡(jiǎn)單調(diào)用窗口控件實(shí)現(xiàn)文本編輯功能 控制臺(tái)文本操作的基本功能已被封裝，可以直接使用 字符串、列表等數(shù)據(jù)結(jié)構(gòu)必須自行設(shè)計(jì)實(shí)現(xiàn)，不得使用現(xiàn)有類庫 字符串匹配必須使用KMP算法102021/8/6 利用哈夫曼樹對(duì)文件按字節(jié)進(jìn)行變

6、長(zhǎng)編碼，降低平均編碼長(zhǎng)度，達(dá)到壓縮文件的目的 首先打開并掃描整個(gè)文件，按字節(jié)統(tǒng)計(jì)數(shù)0255出現(xiàn)的概率 根據(jù)教材7.7節(jié)關(guān)于哈夫曼樹的介紹，對(duì)0255進(jìn)行變長(zhǎng)編碼，使得最常出現(xiàn)的數(shù)具有最短的編碼，而最不常出現(xiàn)的數(shù)具有最常編碼112021/8/6 建立哈夫曼樹后，先將哈夫曼樹存儲(chǔ)到目標(biāo)文件中，然后再次掃描源文件，對(duì)每個(gè)字節(jié)進(jìn)行編碼并寫入到目標(biāo)文件中，實(shí)現(xiàn)文件壓縮 解壓縮時(shí)先從壓縮源文件中讀取哈夫曼樹，然后掃描壓縮文件，利用哈夫曼樹將變長(zhǎng)編碼恢復(fù)為原來的定長(zhǎng)編碼，并寫入到目標(biāo)解壓文件中哈夫曼編碼后的變長(zhǎng)編碼不是8bit的整數(shù)倍，請(qǐng)使用位運(yùn)算實(shí)現(xiàn)變長(zhǎng)編碼的連續(xù)輸出程序要有UI界面，壓縮和解壓縮過程中應(yīng)

7、顯示正確的處理進(jìn)度壓縮后的文件應(yīng)比源文件小，解壓恢復(fù)的文件應(yīng)和源文件完全一致122021/8/6132021/8/6 從文本文件中讀取多個(gè)無向圖的鄰接矩陣，按要求繪圖 圖文件格式如下： 24 文件中存儲(chǔ)的鄰接矩陣數(shù)目 10 圖頂點(diǎn)數(shù) 0 0 0 0 0 0 1 1 0 0 圖的鄰接矩陣：0表示無邊，1表示有邊 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0

8、0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 142021/8/6 圖的繪制要求： 用教材8.6.2節(jié)的弗洛伊德算法計(jì)算頂點(diǎn)間距離，找出最大距離的頂點(diǎn)，設(shè)為vi和vj 用教材8.6.1節(jié)介紹的迪杰斯特拉算法計(jì)算vi到vj的路徑，用該路徑作為圖的主軸方向 遍歷路徑上其它頂點(diǎn)，如果頂點(diǎn)的度2，則說明存在分支，如果分支數(shù)為1則向上繪制分支，如果分支數(shù)為2則向上、向下繪制分支，如果分支數(shù)2則以橫軸為中心，分成上下兩部分，每部分均勻繪制分支152021/8/6 輸入文件中存在多個(gè)鄰接矩陣，請(qǐng)按照讀入順序按先列后行的順序進(jìn)行繪制，直至所有矩陣?yán)L制完畢。程序要求有UI界面，通過菜單打開圖文件成功打開文件后對(duì)文件