數(shù)據(jù)結(jié)構(gòu)課程設(shè)計市公開課一等獎省賽課微課金獎?wù)n件

軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計成都理工大學(xué)信息科學(xué)與技術(shù)學(xué)院第1頁課程設(shè)計基本要求從指定題目中任選一題，獨立完成，不得自行設(shè)計指定題目外其它題目，不得剽竊。成績組成：平時成績30%，點名6次，每次5分。課程設(shè)計答辯，包含演示程序，回答老師提問30%，（假如回答下列問題中發(fā)覺程序不是本人開發(fā)，直接判定不及格）。課程設(shè)計匯報，按照指定格式和模板編寫，不得隨意更改結(jié)構(gòu)。（匯報必須與答辯程序相符，假如不符合或發(fā)覺剽竊，直接判定不及格）第2頁課程設(shè)計匯報撰寫要求匯報內(nèi)容必須包含以下部分選題意義與目標(biāo)（1-2頁）所選題目標(biāo)任務(wù)要求選題意義課程設(shè)計目標(biāo)算法分析，分析所選題目需要用到數(shù)據(jù)結(jié)構(gòu)算法，給出算法基本思緒或原理，繪制相關(guān)圖件（2-3頁）程序設(shè)計與實現(xiàn)（10-15頁）設(shè)計程序整體結(jié)構(gòu)，分析程序中存在類，以及它們之間關(guān)系，繪制UML類圖。對關(guān)鍵數(shù)據(jù)結(jié)構(gòu)類給出詳細(xì)函數(shù)接口說明。對關(guān)鍵數(shù)據(jù)結(jié)構(gòu)算法繪制流程圖，給出函數(shù)實當(dāng)代碼。第3頁課程設(shè)計匯報撰寫要求程序運行結(jié)果，選擇適當(dāng)測試數(shù)據(jù)，對程序進(jìn)行測試，給出測試用例以及對應(yīng)程序運行截圖（2-3頁）結(jié)論，總結(jié)針對所選題目采取數(shù)據(jù)結(jié)構(gòu)、算法和程序設(shè)計思緒，說明取得結(jié)果，論證所述方法正確性，提一點深入研究方向。（1頁）參考文件（不少于5篇）匯報正文采取宋體小四號，1.5倍行距書寫，各個大部分之間要分頁。調(diào)整好版式，每頁不能有太多空白。圖要有標(biāo)號。總頁數(shù)不少于20頁第4頁程序設(shè)計基本要求獨立設(shè)計程序，不得剽竊，不得從網(wǎng)上下載開發(fā)平臺為Windows系列操作系統(tǒng)編程語言推薦C++，也能夠使用Java、C#等主流開發(fā)語言開發(fā)工具對于C++/C#請采取VC6或VS/等微軟系列開發(fā)工具，對于Java請采取Eclipse不論使用何種開發(fā)語言和工具，程序數(shù)據(jù)結(jié)構(gòu)和算法部分不得使用已經(jīng)有類庫或第三方類庫，必須自己編碼實現(xiàn)代碼格調(diào)統(tǒng)一，書寫規(guī)范，關(guān)鍵算法加入注釋程序必須能正確編譯及運行，答辯時程序不能正確編譯或主體功效不正確判定為不及格第5頁題目一：簡單函數(shù)計算器第6頁題目一：簡單函數(shù)計算器允許用戶輸入帶變量x函數(shù)表示式f(x)，而且能夠設(shè)定變量范圍依據(jù)教材3.1.4節(jié)介紹表示式求值算法原理，利用棧實現(xiàn)帶變量表示式求值依據(jù)表示式求值結(jié)果和自變量范圍，離散均勻采樣繪制函數(shù)圖像利用簡單二分法求方程根要求程序含有UI界面能夠繪制函數(shù)圖像假如用戶輸入表示式有誤，能夠提醒錯誤第7頁題目二：簡單文本編輯器第8頁題目二：簡單文本編輯器利用Windows控制臺API函數(shù)開發(fā)一個類似于vi文本編輯器能夠新建或打開已經(jīng)有文本文件在控制模式下按下鍵i，進(jìn)入編輯模型，在編輯模式下能夠用方向鍵或PgUp、PgDn翻動瀏覽文件，能夠插入或刪除字符在編輯模式下按Esc鍵能夠回到控制模式在控制模式下輸入:q能夠退出程序在控制模式下輸入:w能夠保留文件第9頁題目二：簡單文本編輯器在控制模式下輸入:f查找字符串，能夠在文件中查找并定位字符串在控制模式下輸入:r查找字符串替換字符串，能夠替換從當(dāng)前光標(biāo)位置開始第一個匹配字符串在控制模式下輸入:ra查找字符串替換字符串，能夠替換文件中全部匹配字符串全部文件編輯功效實現(xiàn)必須是在文本模式下，不得簡單調(diào)用窗口控件實現(xiàn)文本編輯功效控制臺文本操作基本功效已被封裝，能夠直接使用字符串、列表等數(shù)據(jù)結(jié)構(gòu)必須自行設(shè)計實現(xiàn)，不得使用現(xiàn)有類庫字符串匹配必須使用KMP算法第10頁題目三：哈夫曼編碼壓縮利用哈夫曼樹對文件按字節(jié)進(jìn)行變長編碼，降低平均編碼長度，到達(dá)壓縮文件目標(biāo)首先打開并掃描整個文件，按字節(jié)統(tǒng)計數(shù)0—255出現(xiàn)概率依據(jù)教材7.7節(jié)關(guān)于哈夫曼樹介紹，對0—255進(jìn)行變長編碼，使得最常出現(xiàn)數(shù)含有最短編碼，而最不常出現(xiàn)數(shù)含有最常編碼第11頁題目三：哈夫曼編碼壓縮建立哈夫曼樹后，先將哈夫曼樹存放到目標(biāo)文件中，然后再次掃描源文件，對每個字節(jié)進(jìn)行編碼并寫入到目標(biāo)文件中，實現(xiàn)文件壓縮解壓縮時先從壓縮源文件中讀取哈夫曼樹，然后掃描壓縮文件，利用哈夫曼樹將變長編碼恢復(fù)為原來定長編碼，并寫入到目標(biāo)解壓文件中哈夫曼編碼后變長編碼不是8bit整數(shù)倍，請使用位運算實現(xiàn)變長編碼連續(xù)輸出程序要有UI界面，壓縮和解壓縮過程中應(yīng)顯示正確處理進(jìn)度壓縮后文件應(yīng)比源文件小，解壓恢復(fù)文件應(yīng)和源文件完全一致第12頁題目四：圖文件繪制第13頁題目四：圖文件繪制從文本文件中讀取多個無向圖鄰接矩陣，按要求繪圖圖文件格式以下：24文件中存放鄰接矩陣數(shù)目10圖頂點數(shù)0000001100

圖鄰接矩陣：0表示無邊，1表示有邊000000100100000001000000000011000000001000000000011100000000101000000000011000000101010000…第14頁題目四：圖文件繪制圖繪制要求：用教材8.6.2節(jié)弗洛伊德算法計算頂點間距離，找出最大距離頂點，設(shè)為vi和vj用教材8.6.1節(jié)介紹迪杰斯特拉算法計算vi到vj路徑，用該路徑作為圖主軸方向遍歷路徑上其它頂點，假如頂點度>2，則說明存在分支，假如分支數(shù)為1則向上繪制分支，假如分支數(shù)為2則向上、向下繪制分支，假如分支數(shù)>2則以橫軸為中心，分成上下兩部分，每部分均勻繪制分支第15頁題目四：圖文件繪制輸入文件中存在多個鄰接矩陣，請按照讀入次序按先列后行次序進(jìn)行繪制，直至全部矩陣?yán)L制完成。程序要求有UI界面，經(jīng)過菜單打開圖文件成功打