軟件工程專業(yè)數(shù)據(jù)結構課程設計方案V1.

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

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

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

4、.new，生產文件 filename.txt。（30 分）2. 全國交通咨詢模擬 問題描述 處于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能的短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉次數(shù)最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。 設計要求 （1）提供對城市信息進行編輯（如：添加或刪除）的功能。（ 2）城市之間有兩種交通工具：火車和飛機。提供對列車時刻表和飛機航班進行編輯（增設或刪除）的功能。（ 3）提供兩種最優(yōu)決策：最快到達和最省錢到達。全程只考慮一種交通工具。（ 4）旅途中耗費的總時間應該包括中轉站

5、的等候時間。（ 5）咨詢以用戶和計算機的對話方式進行。 由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達， 并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。 實現(xiàn)提示 （1）對全國城市交通圖和列車時刻表及飛機航班表進行編輯， 應該提供文件形式輸入和鍵盤輸入兩種方式。飛機航班表的信息應包括：起始站的出發(fā)時間、終點站的到達時間和票價；列車時刻表則需根據(jù)交通圖給出各個路段的詳細信息， 例如：對從北京到上海的火車，需給出北京至天津、 天津至徐州及徐州至上海各段的出發(fā)時間、 到達時間及票價等信息。（2）以鄰接表作交通圖的存儲結構， 表

6、示邊的結構內除含有鄰接點的信息外，還應包括交通工具、 路程中耗費的時間和花費以及出發(fā)和到達的時間等多種屬性。（3）增加旅途中轉次數(shù)最少的最優(yōu)決策。3. 24 點撲克牌游戲題目背景：一副牌中抽去大小王剩下52 張（如果初練也可只用110 這 40張牌），任意抽取 4 張牌（稱牌組），用加、減、乘、除（可加括號）把牌面上的數(shù)算成24。每張牌必須用一次且只能用一次，如抽出的牌是 3、8、8、9，那么算式為 （9-8）83 或 38+（9-8）或（9- 8 8）3 等。本題主要考查棧、集合、數(shù)組、遞歸、窮舉等知識?？蓞⒖迹?link?url=2KyoNLQJM

7、9hd_KrFOTSNbwoNbbsM854nWlYHKe7qK61YSiUZYeAsj0RV oqsu81MteLCviY4Tf8CCXHG5nWftTK/topics/390499220/s/blog_5f3e269a0100dm5a.html/p-364720041.html版本 1：滿分 30 分從 52 張牌中任意選取4 張撲克牌，如下圖，每張牌表示一個數(shù)字輸入由四張被選擇的撲克牌牌面的四個數(shù)字構成的一個表達式10*(8-6)+4 ，如下圖點 按 ， 示消息：如 入的

8、表達式 10+8+6-4，得不到正確的 果， 示消息：如 入的數(shù)據(jù)與 牌數(shù)據(jù)不同， 示消息：點 刷新按 ，得到另外4 牌。版本 2： 分 40 分改 版本 1，如果解存在，就 示 解。如果存在多個解， 示 的多個解。如 8，6，2， 1，可能的解有： 6+(8+1)*2 ，8*(6-2-1) ，如果不存在解， 示無解消息。由用戶輸入 1 到 13 之間的 4 個數(shù)，檢查是否有解。版本 4：滿分 30 分從 52 張牌中選擇 4 張牌，這 4 張牌可能無解。從 52 張牌中選擇 4 張牌的挑選次數(shù)是多少？在這些所有可能的選擇中，有多少有解？Total number of combinations

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

10、他結構的模型。版本 2：滿分 40 分參考 9 枚硬幣反面問題的解決方法， 解決 16 枚硬幣的反面問題。進一步解決其它結構的反面問題。版本 3：滿分 30 分修改硬幣翻轉規(guī)則， 如規(guī)則改為對角線上的鄰居被翻轉，或者任意自定義的翻轉規(guī)則。重新解決上述問題。5. 線性表、樹、圖的操作和演示(1)線性表：滿分 40 分實現(xiàn)接口 MyList 、抽象類 MyAbstractList 、基于順序存儲線性表MyArrayList 、基于鏈式存儲的線性表MyLinkedList 。實現(xiàn)方式如下：給出 MyArrayList 和 MyLinkedList 操作的動畫演示，如下圖：實現(xiàn)棧 MyStack 和隊

11、列 MyQueue。實現(xiàn)方式如下：MyStackMyArrayListMyQueueMyLinkedList給出 MyStack 和 MyQueue 的動畫操作，如下圖：(2)樹：滿分 20 分設計實現(xiàn)二叉查找樹，并以動畫形式演示在其上的插入、查找、刪除等操作。(3)圖：滿分 40 分設 計 實 現(xiàn) 接 口Graph 、 抽 象 類AbstractGraph 、 具 體 類UnweightedGraph 和 WeightedGraph類。實現(xiàn)方式如下：并用動畫方式顯示無權圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷；使用動畫方式顯示帶權圖的最小生成樹、最短路徑：6. 模擬瀏覽器版本 1：滿分（分）編寫程序，將一個 Java文件轉換為 HTML 一個文件。在 HTML 文件中，關鍵字、 注釋和字