哈夫曼編譯碼系統(tǒng)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說明書 哈夫曼樹編碼譯碼 學(xué)院（部）： 計(jì)算機(jī)科學(xué)與工程學(xué)院專業(yè)班級： 物聯(lián)網(wǎng)工程12-2班 學(xué) 號： 2012303285 學(xué)生姓名： 陳喜慧 指導(dǎo)教師： 郝偉 起止時間： 2013年12月29日至2014年01月09日安徽理工大學(xué)課程設(shè)計(jì)（論文）任務(wù)書 計(jì)算機(jī)科學(xué)與工程 學(xué)院 學(xué) 號2012303285學(xué)生姓名陳喜慧 專業(yè)（班級）物聯(lián)網(wǎng)工程12-2班設(shè)計(jì)題目 哈夫曼碼的編/譯碼系統(tǒng) 設(shè)計(jì)技術(shù)參數(shù)（1）用C+或C語言實(shí)現(xiàn)設(shè)計(jì)任務(wù)；（2）所設(shè)計(jì)的程序可讀性好，執(zhí)行效率高；（3）有良好的操作界面；（4）設(shè)計(jì)說明書能很好地反映設(shè)計(jì)內(nèi)容設(shè)計(jì)要求（1）要求小組成員熟練掌握數(shù)據(jù)結(jié)構(gòu)的基本

2、知識和技能； （2）基本掌握數(shù)據(jù)結(jié)構(gòu)的基本思路和方法； （3）能夠利用所學(xué)的數(shù)據(jù)結(jié)構(gòu)基本知識和技能，解決簡單的相關(guān)的問題；（5）熟練掌握樹的遍歷；（6）利用哈夫曼樹進(jìn)行通信的二進(jìn)制編碼。工作量課程設(shè)計(jì)報(bào)告要求不少于3000字。源程序要求不少于300行工作計(jì)劃2013.12.30-14.01.05 根據(jù)課程設(shè)計(jì)大綱的要求，查找相關(guān)資料，完成需求分析；2014.01.06 進(jìn)行系統(tǒng)的概要設(shè)計(jì)；2014.01.07 進(jìn)行系統(tǒng)的詳細(xì)設(shè)計(jì)和源代碼的書寫；2014.01.08-14.01.09 對系統(tǒng)進(jìn)行調(diào)試分析，寫出課程設(shè)計(jì)報(bào)告。參考資料1 嚴(yán)蔚敏,吳偉民編著.數(shù)據(jù)結(jié)構(gòu)（C語言版）,北京:清華大學(xué)出版社

3、,2002；2 嚴(yán)蔚敏,吳偉民,米寧編著.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）北京:清華大學(xué)出版社,1996；指導(dǎo)教師簽字教研室主任簽字 2014年 01 月 09日 學(xué)生姓名： 陳喜慧 學(xué)號： 2012303285 專業(yè)班級: 物聯(lián)網(wǎng)工程12-2班 課程設(shè)計(jì)題目： 哈夫曼碼的編/譯碼系統(tǒng) 指導(dǎo)教師評語：1：文檔不要出現(xiàn)空白頁2：目錄需要重新引用，更新不對3：多余的標(biāo)點(diǎn)符號需要刪除4：分頁符的放置位置不合理重新編輯5：需求分析下應(yīng)該插入引言6：測試數(shù)據(jù)這個標(biāo)題應(yīng)該改一下，有歧義7：標(biāo)題上不能加括號8：詳細(xì)設(shè)計(jì)下需要插入引言9：文檔不要有空行10：參考文件需要再添加幾個11：系統(tǒng)運(yùn)行這一小節(jié)可以放到運(yùn)行調(diào)試

4、下面12：不需要完整源碼，不需要用附錄形式輸出 （見評分表）成績： 指導(dǎo)教師： 年 月 日安徽理工大學(xué)課程設(shè)計(jì)（論文）成績評定表課程設(shè)計(jì)評分表課程設(shè)計(jì)評分標(biāo)準(zhǔn)分為前言、分析設(shè)計(jì)、主體內(nèi)容、參考文獻(xiàn)和排版五部分內(nèi)容，每部分的得分標(biāo)準(zhǔn)參見下表。內(nèi)容標(biāo)準(zhǔn)得分范圍得分前言（10分）思路清晰，描述清楚。9-10思路基本清晰，描述基本清楚。6-8思路混亂，描述不清。0-5分析設(shè)計(jì)（30分）問題分析清楚，設(shè)計(jì)合理。25-30能夠基本分析出關(guān)鍵問題，設(shè)計(jì)上基本能夠滿足要求。18-24分析問題有偏差，設(shè)計(jì)上存在問題。9-17分析有誤，設(shè)計(jì)不能滿足需求。0-8主體內(nèi)容（30分）內(nèi)容詳實(shí)，能夠充分表達(dá)整個課程設(shè)計(jì)的

5、內(nèi)容。25-30內(nèi)容完整，能夠基本表達(dá)清楚課程設(shè)計(jì)的主要內(nèi)容。18-24內(nèi)容有缺失，無法清楚完整表達(dá)整個設(shè)計(jì)內(nèi)容。9-17內(nèi)容空洞，無法表達(dá)設(shè)計(jì)內(nèi)容。0-8參考文獻(xiàn)（10分）參考文獻(xiàn)在10篇以上，引用合理。9-10參考文獻(xiàn)5-9篇，基本與設(shè)計(jì)內(nèi)容相符。6-8參考文獻(xiàn)少于5篇，且內(nèi)容相關(guān)性差。0-5排版（20分）嚴(yán)格按課程設(shè)計(jì)模板要求排版。17-20基本按照課程設(shè)計(jì)模板要求排版，有部分錯誤。12-16與課程設(shè)計(jì)模板有大量不符，排版存在很多錯誤。0-11總 分注1：整個課程設(shè)計(jì)內(nèi)容必需完整，如果缺少某部分，該部分按0分處理。注2：主體內(nèi)容包括總結(jié)或心得體會部分。評分人： 日 期： 目錄1需求分析6

6、1.1問題描述61.2基本要求61.3測試要求71.4實(shí)現(xiàn)提示72總體設(shè)計(jì)92.1哈夫曼編譯碼器的算法思想92.2簡單函數(shù)92.3利用簡單操作實(shí)現(xiàn)的復(fù)雜功能92.4顯示格式的實(shí)現(xiàn)103詳細(xì)設(shè)計(jì)113.1編碼函數(shù)123.2譯碼函數(shù)134調(diào)試分析155小結(jié)19參考文獻(xiàn)201需求分析在這次課程設(shè)計(jì)中，所進(jìn)行的實(shí)驗(yàn)是：哈夫曼編碼和編譯器。對哈夫曼樹進(jìn)行建立，由節(jié)點(diǎn)的權(quán)值建立最小二叉樹，哈夫曼樹haftree，并由所建立的哈夫曼樹進(jìn)行編碼，求出各個節(jié)點(diǎn)的編碼。在由所求的哈夫曼樹，輸入一段二進(jìn)制電文，能夠輸出那所建立的哈夫曼樹中的節(jié)點(diǎn)。建立的haftree用圖形化表示出來。在整個代碼實(shí)現(xiàn)中，窗體的實(shí)現(xiàn)，功

7、能的完善，哈夫曼樹的建立，哈夫曼樹的編碼，遇到了許多難題haftree，對象數(shù)組的分配空間，節(jié)點(diǎn)的屬性等都比較困難。在整個過程中，用的是C#語言，包的應(yīng)用，字符串?dāng)?shù)組的空間分配，在計(jì)算每個字符的權(quán)值時，用的是sizeOf()檢索整個字符串，計(jì)算字符的權(quán)值，建立字符出現(xiàn)頻度的表格，根據(jù)表格中每個字符頻度建立起哈夫曼樹。從根節(jié)點(diǎn)出發(fā)檢索每個節(jié)點(diǎn)的左右孩子，如果是左孩子遍歷左邊，路徑為0，然后左孩子為根節(jié)點(diǎn)；如果是右孩子，遍歷右孩子，路徑為1，然后右孩子為根節(jié)點(diǎn)。在重新上述方法，直到所有的節(jié)點(diǎn)都遍歷完，每個節(jié)點(diǎn)的編碼就確定后輸出來。在譯碼過程中，由所輸入的二進(jìn)制電文，根據(jù)所建立的哈夫曼樹，如果是0走

8、左邊，如果是1，走右邊，直到節(jié)點(diǎn)的左右孩子為空時，輸出給節(jié)點(diǎn)的信息，在回到根節(jié)點(diǎn)重新遍歷后面的二進(jìn)制電文，直到所有電文都遍歷完為止，輸出所有從電文中譯碼出來的信息。關(guān)鍵詞：編譯器；頻度；譯碼1.1問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。1.2基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：（1）I:初始化（Initialization）。從終

9、端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E:編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3）D:譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4）P:打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。（5）T:打印哈夫曼樹（Tree printin

10、g）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。1.3測試要求（1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY

11、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.4實(shí)現(xiàn)提示（1） 編碼結(jié)果以文本方式存儲在文件CodeFile中。（2） 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運(yùn)行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3） 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，

12、D或E命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。 2總體設(shè)計(jì)2.1哈夫曼編譯碼器的算法思想 本程序分為統(tǒng)計(jì)字符頻度，構(gòu)造哈夫曼樹，確定哈夫曼碼，翻譯哈夫曼碼四部統(tǒng)計(jì)字符頻度：逐一輸入字符，如沒出現(xiàn)過則建立一結(jié)點(diǎn)存儲此字符，并建立另一結(jié)點(diǎn)存儲其頻度為1。如出現(xiàn)過則使那個字符的頻度結(jié)點(diǎn)加1；構(gòu)造哈夫曼樹：首先找到parent為0且weight最小的兩個結(jié)點(diǎn)，并將他們合并為一個結(jié)點(diǎn)代替，weight為兩者之和。在重復(fù)找parent為0且weight最小的兩個結(jié)點(diǎn)。如此重復(fù)直到最后剩一個結(jié)點(diǎn)作為哈夫曼根結(jié)點(diǎn)；確定哈夫曼碼：從葉子到根逆向

13、求編碼，如是父結(jié)點(diǎn)的左孩子則碼為“0”，如是父結(jié)點(diǎn)的右孩子則碼為“1”；翻譯哈夫曼碼：接受“0”，“1”字符，從根結(jié)點(diǎn)開始，遇0訪問左孩子，遇1訪問右孩子，如果訪問的是葉結(jié)點(diǎn)，則返回到根結(jié)點(diǎn)，繼續(xù)查找。最后顯示樹狀結(jié)構(gòu)。 2.2簡單函數(shù) CreatHfmTree( weight, ch, n,HafNode) 操作結(jié)果：生成哈夫曼樹 HaffmanCode (HafNode, n,Code) 操作結(jié)果：對哈弗曼樹編碼 InitHfmTree(weight, ch) 操作結(jié)果：初始化哈夫曼樹 PrintCodeFile() 操作結(jié)果：打印代碼文件 PrintTreeCode(HafNode *,

14、 n, p,FILE *) 操作結(jié)果：打印哈夫曼樹結(jié)點(diǎn) 2.3利用簡單操作實(shí)現(xiàn)的復(fù)雜功能 FileCoding() 操作結(jié)果：對文件進(jìn)行哈弗曼編碼 PrintTree() 操作結(jié)果：打印哈夫曼樹 2.4顯示格式的實(shí)現(xiàn) Sheet() 操作結(jié)果：實(shí)現(xiàn)哈夫曼編譯碼器的操作表單3詳細(xì)設(shè)計(jì)算法思想：1： void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) /w存放n個字符的權(quán)值(均0),構(gòu)造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC。首先初始化結(jié)點(diǎn)的成員，然后在HT1.i-1選擇parent為0且weight最小的兩

15、個結(jié)點(diǎn)，其序號分別為S1和S2開始建哈夫曼樹，在這里為了區(qū)別葉子結(jié)點(diǎn)字符及方便以后操作，把非葉子結(jié)點(diǎn)的字符都初始化為“？”。最后從葉子到根逆向求每個字符的赫夫曼編碼。2. void Initialization(HuffmanTree &HT, HuffmanCode &HC, int &n)/初始化,注意加引用符號。先判斷hfmTree.txt文件是否存在，如果不存在就直接從終端讀入字符集大小n，以及n個字符和n個權(quán)值，調(diào)用上述函數(shù)建立哈夫曼樹，否則就讀到內(nèi)存中。由于字符可能是空格，所以要用getchar() 函數(shù)讀入字符。用到的文本文件讀寫操作如下：ifstream fin(hfmTree

16、.txt, ios:in);/讀出ofstream fout(hfmTree.txt, ios:out);/寫入3. void Encoding(HuffmanCode & HC,int n)/對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。首先把正文用getline()函數(shù)一行一行讀入字符串str中。編碼過程，一個字符一個字符來，算法如下： for(i=0;stri!=0;i+)/編碼過程，一個字符一個字符來 j=1; while(chj!=stri&j=n) j+; if(j=n) foutHCj;4 void Decoding(HuffmanTree HT,

17、 int n)/將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。由于文件中代碼全是0、1，無空格，所以可以直接讀入字符串str，譯碼過程，從根出發(fā)，按字符0或1確定找左孩子或右孩子，直至葉子結(jié)點(diǎn)，算法如下： i=0; j=m; while(ilen ) /len=str.size() if(stri=0) j=HTj.lchild; else j=HTj.rchild; if(HTj.lchild=0) fout0;l-) /m為根結(jié)點(diǎn)的權(quán)值 for(i=1;i=2*n-1;i+) if(HTi.weight=l) for(j=0;jk;j+) /k 表示層數(shù),r表示每

18、層的結(jié)點(diǎn)數(shù) cout ; fout ; /控制每層前面的空格 if(chi!=?) /如果是葉子結(jié)點(diǎn)就直接輸出，否則輸出權(quán)重 if(chi= ) chi=#;/標(biāo)記為空的字符 coutchiendl; foutchiendl; else coutHTi.weightendl; foutHTi.weightendl; p+;/p 表示每層的非葉子結(jié)點(diǎn)數(shù) q+;/q 記錄每層的結(jié)點(diǎn)數(shù)目 if(q=r) k+; r=2*p; p=0; q=0; /如果該層的結(jié)點(diǎn)滿了，就到下一層，即k+1 3.1編碼函數(shù) 以下是源程序中實(shí)現(xiàn)編碼的部分：void Encoding(HuffmanCode & HC,in

19、t n) /編碼 int i,j; string str,str1; ifstream fin(ToBeTran.txt,ios:in);/打開文件 ofstream fout(CodeFile.txt,ios:out); if(fin.fail() cout文件ToBeTran.txt打開失??！endl; getline(fin,str);/讀入一行，可以讀入空格 while(!fin.eof()/文件不結(jié)束 getline(fin,str1); str=str+str1; fin.close(); for(i=0;stri!=0;i+)/編碼過程，一個字符一個字符來 j=1; while(

20、chj!=stri&j=n) j+; if(j=n) foutHCj; foutendl; fout.close();3.2譯碼函數(shù) 以下函數(shù)是源程序中實(shí)現(xiàn)譯碼部分： void Decoding(HuffmanTree HT,int n)/譯碼 int j,len,m; string str; m=2*n-1; ifstream fin(CodeFile.txt,ios:in); ofstream fout(TextFile.txt,ios:out); if(fin.fail() cout文件CodeFile.txt打開失??！str; fin.close(); len=str.size();

21、i=0;j=m; while(ilen) /從根出發(fā)，按字符0或1確定找左孩子或右孩子，直至葉子結(jié)點(diǎn) if(stri=0) j=HTj.lchild; else j=HTj.rchild; if(HTj.lchild=0) foutchj; j=m; i+; foutendl;4調(diào)試分析源碼編寫完成后經(jīng)過調(diào)試無錯誤可以運(yùn)行，進(jìn)行運(yùn)行：選擇操作I：哈夫曼樹已成功存入文件htmTree中建立ToBeTran.txt文件選擇操作E：對文件ToBeTran中的內(nèi)容編碼成功并成功存入文件CodeFile中選擇操作D：對文件CoDeFile中的內(nèi)容譯碼成功并成功存入文件TextFile中選擇操作P:50個

22、代碼形式的代碼成功編碼并并成功寫入文件CodePrint中選擇操作T:哈夫曼樹以凹入表的形式成功寫入文件TreePrint中選擇操作Q：退出系統(tǒng) 在我自己課程設(shè)計(jì)中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了：（1） 在定義頭文件時可多不可少，即我們可多寫些頭文件，肯定不會出錯，但是若沒有定義所引用的相關(guān)頭文件，必定調(diào)試不通過。（2） 在執(zhí)行譯碼操作時，不知什么原因，總是不能把要編譯的二進(jìn)制數(shù)與編譯成的字符用連接號連接起來，而是按順序直接放在一起，視覺效果不是很好。（3） 由于對指針的

23、使用不夠靈活，使程序調(diào)試時費(fèi)時不少。在權(quán)值的單行、換行和空格輸入，也花了一些時間，不過最終能實(shí)現(xiàn)單個空格的輸入。（4） 本程序有些代碼重復(fù)出現(xiàn)，從而減少了空間的利用率和增加了程序代碼的雜亂性，把多次用到的代碼分別寫成一個函數(shù)，然后就可以直接調(diào)用了。（5） ToBeTran.txt開始并沒有意識到要建立，以為是程序自己運(yùn)行生成的導(dǎo)致總是讀取失敗，浪費(fèi)了不少時間。（6） 算法的時空分析在此程序中，存儲字符串都用了指針，先動態(tài)申請空間，然后再存，這樣就有效的利用了空間。而對于哈夫曼樹算法本身，由于這里只是一個靜態(tài)的，所以當(dāng)進(jìn)行網(wǎng)絡(luò)傳輸時，可能會顯得效率比較低。（7） 本實(shí)驗(yàn)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序分為5個模塊，使得設(shè)計(jì)時思路清晰，實(shí)現(xiàn)時調(diào)試可以順利完成，各模塊具有較好的可重用性，確實(shí)得到了一次良好的程序設(shè)計(jì)訓(xùn)練。5小結(jié) 通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了不少之前上課沒懂的知識。并在老師指導(dǎo)下，我對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一