《数据结构与算法》课程设计任务书——赫夫曼编码/译码器
《數據結構與算法》課程設計
（2019/2020學年第一學期） 指導教師：孫麒、霍戌文《數據結構與算法》課程設計
任務書
《數據結構與算法》是計算機科學與技術專業重要的核心課程之一，在計算機專業的學習過程中占有非常重要的地位。《數據結構與算法課程設計》就是要運用本課程以及到目前為止的有關課程中的知識和技術來解決實際問題。特別是面臨非數值計算類型的應用問題時，需要選擇適當的數據結構，設計出滿足一定時間和空間限制的有效算法。
本課程設計要求同學獨立完成一個較為完整的應用需求分析。并在設計和編寫具有一定規模程序的過程中，深化對《數據結構與算法》課程中基本概念、理論和方法的理解；訓練綜合運用所學知識處理實際問題的能力，強化面向對象的程序設計理念；使自己的程序設計與調試水平有一個明顯的提高。
一、赫夫曼編碼/譯碼器
問題描述
利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發送端通過一個編碼系統對待傳輸數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站編寫一個赫夫曼碼的編/譯碼系統。
基本要求
一個完整的系統應具有以下功能：
(1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立赫夫曼樹，并將它存于文件hfmTree中。
(2) E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。
(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件Textfile中。
以下為選做：
(4) P：打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。
(5) T：打印赫夫曼樹（Tree printing）。將已在內存中的赫夫曼樹以直觀的方式（比如樹）顯示在終端上，同時將此字符形式的赫夫曼樹寫入文件TreePrint 中。
測試要求
（1）已知某系統在通信聯絡中只可能出現八種字符，其頻率分別為0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，試設計赫夫曼編碼。
(2) 用下表給出的字符集和頻度的實際統計數據建立赫夫曼樹，并實現以下報文的編碼和譯碼：“THIS PROGRAME IS MY FAVORITE”。
字符 A B C D E F G H I J K L M
頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符 N O P Q R S T U V W X Y Z
頻度 57 63 15 1 48 51 80 23 8 18 1 16 1
實現提示
(1) 編碼結果以文本方式存儲在文件Codefile中。
(2) 用戶界面可以設計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。
(3) 在程序的一次執行過程中，第一次執行I，D或C命令之后，赫夫曼樹已經在內存了，不必再讀入。每次執行中不一定執行I命令，因為文件hfmTree可能早已建好。
二、具體要求：
課程設計成果的內容必須由以下四個部分組成，缺一不可。
(1) 上交源程序：學生按照實驗題目的具體要求所開發的所有源程序（應該放到一個文件夾中），然后打包壓縮后上交；
(2) 上交程序的說明文件：（保存在.txt中）在說明文檔中應該寫明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝第三方軟件才能運行，要有第三方程序的安裝使用說明；（可以在報告中體現）
(3) 設計報告：（電子版本，保存在word 文檔中，文件名要求： 按照“學號_姓名_設計題目”起名，如文件名為“XXX_張三_赫夫曼編碼 ”.doc或.docx）。
其中包括:
1） 題目；
2） 實驗目的；
3） 需求分析：在該部分中敘述實現的功能要求；
4） 概要設計：
在此說明每個部分的算法設計說明（可以是描述算法的流程圖），每個程序中使用的存儲結構設計說明（如果指定存儲結構請寫出該存儲結構的定義）；
5） 詳細設計
各個算法實現的源程序，對每個題目要有相應的源程序（可以是一組源程序，每個功能模塊采用不同的函數實現）。源程序要按照寫程序的規則來編寫。要結構清晰，重點函數的重點變量，重點功能部分要加上清晰的程序注釋；
6） 調試分析
測試數據，測試輸出的結果，時間復雜度分析，和每個模塊設計和調試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進設想；
7） 總結：
總結可以包括 : 設計過程的收獲、遇到問題及解決問題過程的思考、程序調試能力的思考、對數據結構這門課程的思考、在設計過程中對《數據結構》課程的認識等內容。
（4）單獨上交電子版本的“課程設計答辯記錄表”，命名方法同上；
三、工作內容及工作計劃：一周
時間 地點 工作內容 指導教師
11.13/11 上午 10-414/413/409 實驗要求，需求分析 孫麒、霍戌文
下午 10-414/413/409 查找資料，總體結構設計 孫麒、霍戌文
11.20/12 上午 10-414/413/409 算法設計，用戶界面設計 孫麒、霍戌文
下午 10-414/413/409 算法設計，用戶界面設計 孫麒、霍戌文
11.27/13 上午 10-414/413/409 詳細設計 孫麒、霍戌文
下午 10-414/413/409 詳細設計 孫麒、霍戌文
12.04/14 上午 10-414/413/409 測試分析與完善設計 孫麒、霍戌文
下午 10-414/413/409 測試分析與完善設計 孫麒、霍戌文
12.11/15 上午 10-414/413/409 上機檢查，答辯 孫麒、霍戌文
下午 10-414/413/409 上機檢查、答辯 孫麒、霍戌文
四、考核成績評定標準：
本課程在理論課完成后進行，最終成績按五級評分：優、良、中、及格、不及格。
五個級別對應的百分之關系為：
A: 成績>=90；
B: 90>成績>=80；
C: 80>成績>=70；
D: 70>成績>=60；
E: 60<成績。
本課程設計的評價由四部分部分組成，包括面試成績（40%），課程設計報告（40%），實踐操作表現（10%），考勤與課堂表現（10%）。其中，課程設計報告40%，根據學生提交的報告完成情況及質量，進行考評；面試成績占40%，學生提交實驗程序，教師提出相關問題，根據學生回答問題的清晰度、準確性、敏捷性，進行考評；實踐操作成績占10%，根據學生在課程設計中分析解決問題的能力、完成任務的速度和質量、提問的質量等進行評分；到課率占10%，以課堂出勤率和課內討論參與度為評分依據。
具體考核與評估標準如下表所示：
考核方式
或途徑 考核要求 考核權重 評估級別
課程設計報告 內容設計合理、完整，格式規范 40% 格式規范、內容完整最高得10分；方案及類的設計最優得10分；代碼實現及風格最高10分；遇到問題解決、改正優化心得最高10分。
面試成績 程序功能設計合理、完整，能夠正常運行，類的設計合理，能夠準確得回答老師提出的問題 40% 能夠根據要求正確完成演示最高得10分；能夠對方案進行清晰完整的進行闡述最高10分；對老師提出的問題回答及時、準確，最高得10分；綜合表現最高10分。
實踐操作表現 具備一定的解決問題的能力，能在規定的時間內順利完成任務 10% 課程設計項目本身的問題，在課程設計考核前完成，得8分；2分為答辯或者爭取優秀的，老師隨機給出小的程序修改問題，完成得2分。
考勤與課堂表現 課堂出勤率和課內討論參與度 10% 8分為出勤，2分為課內參與度，出勤才有扣分制，簽到和隨機點名，未被點到1次扣1分，本項最低0分；課內參與采用加分支，參與一次加1分，最高2分。
總結
以上是生活随笔為你收集整理的《数据结构与算法》课程设计任务书——赫夫曼编码/译码器的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 浅谈主流内存发展历史
- 下一篇： C++——赫夫曼编码-译码器(Huffm