哈夫曼編譯碼器設(shè)計任務(wù)書

1、信息與計算科學(xué)本科專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書（10級）題目：哈夫曼編譯碼器設(shè)計學(xué)生姓名： 學(xué)號： 班級： 題目類型： 指導(dǎo)教師： 一 題目簡介利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。通過該題目的設(shè)計過程，可以加深理解樹及二叉樹的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，掌握樹及二叉樹上基本運算的實現(xiàn)。進一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會如何把學(xué)到的

2、知識用于解決實際問題，培養(yǎng)學(xué)生的動手能力。二 主要任務(wù)1、查閱文獻資料，一般在3篇以上；2、設(shè)計哈夫曼碼的編/譯碼系統(tǒng)，建立數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；3、完成相應(yīng)算法的設(shè)計；4、完成測試工作；5、撰寫設(shè)計說明書；6、做好答辯工作。三 主要內(nèi)容、功能及技術(shù)指標(biāo)（1）分別使用動態(tài)和靜態(tài)存儲結(jié)構(gòu)，主要功能有：建立哈夫曼樹、利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件中的正文進行編碼并輸出編碼、對文件中的代碼進行譯碼、顯示輸出等功能；（2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE

3、”。字符 空格 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算法對于合法的輸入數(shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果；（3）算法對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；對算法實現(xiàn)過程中的異常情況能給出有效信息；（4）較高要求：實現(xiàn)圖形化操作界面，以多種輸出格式顯示哈夫曼樹。四 提交的成果1. 設(shè)計說明書一份，內(nèi)容包括：1 中文摘要100

4、字；關(guān)鍵詞3-5個；2 序言；3）采用類c語言定義相關(guān)的數(shù)據(jù)類型4）各模塊流程圖及偽碼算法5）函數(shù)的調(diào)用關(guān)系圖6）調(diào)試分析a、調(diào)試中遇到的問題及對問題的解決方法；b、算法的時間復(fù)雜度和空間復(fù)雜度。7）測試結(jié)果8）源程序（帶注釋）9 設(shè)計總結(jié)、參考文獻、致謝等。2. 刻制光盤一張。五 主要參考文獻1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社.2 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.清華大學(xué)出版社.3 DATA STRUCTURE WITH C+. William Ford,William Topp .清華大學(xué)出版社（影印版）. 4 譚浩強.c語言程序設(shè)計. 清華大學(xué)出版社. 5數(shù)據(jù)結(jié)構(gòu)與算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 張銘,劉曉丹譯電子工業(yè)出版社 2001 年1月六 各階段時間安排（共2周）周次日期內(nèi)容地點完成情況教師簽字第1周星期一教師講解設(shè)計要求，準(zhǔn)備參考資料教室星期二三分析設(shè)計要求，進行數(shù)據(jù)結(jié)