2013級軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計方案V10

1、2013 級軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計方案 V1.0一、課程任務(wù)要求獨立完成一個或多個較為完整的應(yīng)用需求分析， 在完成設(shè)計 和編程大型作業(yè)的過程中， 深化對數(shù)據(jù)結(jié)構(gòu)課程中概念、 理論和方法 的理解；訓(xùn)練綜合運用所學(xué)知識處理實際問題的能力， 強化面向?qū)ο?的程序設(shè)計理念；使同學(xué)的程序設(shè)計與調(diào)試水平有一個明顯的提高； 經(jīng)過查找參考資料、 技術(shù)手冊和撰寫文檔的實踐， 進一步培養(yǎng)軟件工 程師的綜合素質(zhì)。二、具體要求1. 每人應(yīng)至少獨立完成一道題目并撰寫課程報告， 具體題目由任 課老師組織分配，題目一旦選定，未經(jīng)老師同意，不得私自更換，否 則總評成績?yōu)槿背煽儭?. 按時出勤，曠課 2次直接取消答辯資格

2、， 曠課 1 次總評成績降 低 1 個等級。3. 聽從值班老師安排，按所選題目分區(qū)坐在指定位置。4. 按時提交課程設(shè)計資料，未按格式或未在規(guī)定時間提交資料 的，總評成績?yōu)槿背煽?。三、具體安排1. 時間： 18周周一至周五上午、下午2. 地點：4-312（1、2、3題）、4-313（4、5、6 題）3. 答辯時間： 19周周 1上午、下午4. 課程設(shè)計具體考核標準和流程由題目指導(dǎo)老師負責(zé)。四、課程設(shè)計題目與內(nèi)容1. 數(shù)據(jù)壓縮與解壓縮利用哈夫曼編碼完成數(shù)據(jù)的壓縮與解壓縮，具體要求如下:(1)哈夫曼編碼的動畫顯示，程序運行界面如下：(40 分)Enter a teziShow HuHrnari Tr

3、ee亠1吸曲丁在上面文本框中輸入待編碼的字符串，點擊“Show Huffman Tree按鈕輸入，生成哈夫曼樹并顯示該字符串的哈夫曼編碼。如下圖所示：在下面文本框中輸入二進制哈夫曼串，點擊“Decode Text ”能夠還原為原來的字符。比如輸入"001"顯示"w"，輸入"01001"顯示"ow"，如下圖所示：（2）在上面程序的基礎(chǔ)上，編與程序，在控制臺或GUI中輸入文件名（如file name.dat）,通過哈夫曼數(shù)據(jù)壓縮算法生成 file name .new, 同時，使用數(shù)組存儲每個字符哈夫曼編碼，通過對象輸出

4、流將該數(shù)組寫入文件filename.huf中。（30分）（3）在上面程序的基礎(chǔ)上，通過文件filename.huf解壓文件file name. new,生產(chǎn)文件 file name.txt。（ 30 分）2. 全國交通咨詢模擬問題描述處于不同目的的旅客對交通工具有不同的要求。例如，因公出差 的旅客希望在旅途中的時間盡可能的短，出門旅游的游客則期望旅費 盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。設(shè)計要求（1）提供對城市信息進行編輯（如：添加或刪除）的功能（2）城市之間有兩種交通工具：火車和飛機。提供對列車時刻 表和飛機航班進

5、行編輯（增設(shè)或刪除）的功能。（3）提供兩種最優(yōu)決策：最快到達和最省錢到達。全程只考慮 一種交通工具。（4）旅途中耗費的總時間應(yīng)該包括中轉(zhuǎn)站的等候時間。（5） 咨詢以用戶和計算機的對話方式進行。 由用戶輸入起始站、 終點站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長時間才 能到達或者最少需要多少旅費才能到達，并詳細說明依次于何時乘坐 哪一趟列車或哪一次班機到何地。實現(xiàn)提示（1） 對全國城市交通圖和列車時刻表及飛機航班表進行編輯，應(yīng) 該提供文件形式輸入和鍵盤輸入兩種方式。飛機航班表的信息應(yīng)包括：起始站的出發(fā)時間、終點站的到達時間和票價；列車時刻表則需 根據(jù)交通圖給出各個路段的詳細信息，例如：對

6、從北京到上海的火車， 需給出北京至天津、天津至徐州及徐州至上海各段的出發(fā)時間、 到達 時間及票價等信息。（2）以鄰接表作交通圖的存儲結(jié)構(gòu)，表示邊的結(jié)構(gòu)內(nèi)除含有鄰接 點的信息外，還應(yīng)包括交通工具、路程中耗費的時間和花費以及出發(fā) 和到達的時間等多種屬性。（3）增加旅途中轉(zhuǎn)次數(shù)最少的最優(yōu)決策。3. 24點撲克牌游戲題目背景:一副牌中抽去大小王剩下 52張（如果初練也可只用110這40張牌），任意抽取4張牌（稱牌組），用加、減、乘、除（可加括號） 把牌面上的數(shù)算成24。每張牌必須用一次且只能用一次，如抽出的 牌是 3、8、8、9,那么算式為（9-8） 8X3 或 3X8+ （9-8）或（9- 8 8）

7、 X3等。本題主要考查棧、集合、數(shù)組、遞歸、窮舉等知識。可參考：http:/baike.baidu.eom/l in k?url=2KyoNLQJM9hd_KrFOTSNbwoN bbsM854nWlYHKe7qK61 YSiUZYeAsjORV oqsu81MteLCviY4Tf8CCX HG5 nWftTKhttp:/bbs.esd n.n et/topies/390499220http:/blog.si .c n/s/blog_5f3e269a0100dm5a.html http:/www.doei 版本1 :滿分30分從52張牌中任意選取4張撲克牌，如下圖，每張牌表示一個數(shù) 字輸入由四

8、張被選擇的撲克牌牌面的四個數(shù)字構(gòu)成的一個表達式10*（8-6）+4，如下圖點擊驗證按鈕，顯示消息:如輸入的表達式為10+8+6-4,得不到正確的結(jié)果，顯示消息:如輸入的數(shù)據(jù)與紙牌數(shù)據(jù)不同，顯示消息:點擊刷新按鈕，得到另外4張牌。版本2:滿分40分如果存在多個解，顯示這樣的多個解。如解有：6+(8+1)*2, 8*(6-2-1),8, 6, 2, 1,可能的如果不存在解，顯示無解消息。改進版本1，如果解存在，就顯示該解L釦 21 Point Card G日mt?IFind d SuluUai(9* U>* 12/11Renesh由用戶輸入1到13之間的4個數(shù)，檢查是否有解。rli¥

9、;)kilfour nurrb4rcbatw»An 1 to 13432(3+2+1 f4Fluid h Sillnrioiil- I 24-Poinl Qrd Gsme |l 24 Point Ordlnt> l numbers betwteii 1 to 1313 13 13 73No solutionfind a版本4:滿分30分從52張牌中選擇4張牌，這4張牌可能無解 從52張牌中選擇4張牌的挑選次數(shù)是多少？ 在這些所有可能的選擇中，有多少有解？Total nu mber of comb in ati ons is 270725Total nu mber of comb

10、 in ati ons with soluti ons is 217781The solution ratio is 0.8044362360328747成功的幾率是多少? 編程求解上述問題。4. 16枚硬幣的反面問題題目背景：教材中的9枚硬幣問題使用的是3*3的矩陣，假設(shè)在一個4*4的 矩陣中放置了 16枚硬幣。該問題可進一步變化為如 2*3，2*4，3*4 等等任意結(jié)構(gòu)的情形。本題主要考查對圖的結(jié)構(gòu)和圖的廣度優(yōu)先遍歷操作的掌握。版本1 :滿分30分參考9枚硬幣反面問題的模型，建立16枚硬幣反面問題的模型, 以及其他結(jié)構(gòu)的模型。版本2:滿分40分參考9枚硬幣反面問題的解決方法，解決16枚硬幣

11、的反面問題進一步解決其它結(jié)構(gòu)的反面問題。版本3:滿分30分修改硬幣翻轉(zhuǎn)規(guī)則，如規(guī)則改為對角線上的鄰居被翻轉(zhuǎn)，或者任意自定義的翻轉(zhuǎn)規(guī)則。重新解決上述問題。5. 線性表、樹、圖的操作和演示(1)線性表：滿分40分實現(xiàn)接口 MyList、抽象類MyAbstractList、基于順序存儲線性表 MyArrayList、基于鏈式存儲的線性表 MyLinkedList。實現(xiàn)方式如下：給出MyArrayList和MyLinkedList操作的動畫演示，如下圖:Ent ET 3 VaXtiE thie adtsjxl$ Ecter wi index：:町Il >EltDe ±1eIntiD4

12、A xnde±!9| faisolTrimtaisuft實現(xiàn)棧MyStack和隊列MyQueue。實現(xiàn)方式如下:給出MyStack和MyQueue的動畫操作，如下圖:Enter a value:6 巳少 | Pop But er a value：244 EngLiauE | PequiSMe樹：滿分20分設(shè)計實現(xiàn)二叉查找樹，并以動畫形式演示在其上的插入、查找、刪除等操作。313懂Eo slonCnitaao"'nriDeriFijrXHziue：£Ht-并用動畫方式顯示無權(quán)圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷;圖：滿分40分設(shè)計 實現(xiàn)接口 Graph、抽象類 A

13、bstractGraph、具體類UnweightedGraph 和 WeightedGraph類。實現(xiàn)方式如下:誦紳圻# PFS TfrtSiarrijig Ciiyt |DFSTfer| SwchRt*ne*t11»111*1 U nweii b tcdGraphGraph Q. AbfracKjtaph QIIIIiIi»I1llntsrfiiccAbstract Clus*-WeiflhledGraph使用動畫方式顯示帶權(quán)圖的最小生成樹、最短路徑:Vhiihx hditie： K-Louidindte. jf<QQrdinatc;VHlnJf IJVei tex v liradexWeight (in*Starting Crt/tiding CrtfDisplay ShOElsst Aatn6. 模擬瀏覽器版本1滿分（30分）編寫程序，將一個Java文件轉(zhuǎn)換為HTML 個文件。在HTML 文件中，關(guān)鍵字、注釋和字面值分別用粗體的深藍色、綠色和藍色顯 示。使用命令行參數(shù)傳遞Java文件和HTML文件。運行顯示如下：/ This application program prints Welcome to Java public class Welcome