哈夫曼編譯碼器

1、摘 要隨著計算機的普遍應用與日益發(fā)展,其應用早已不局限于簡單的數(shù)值運算,而涉及到問題的分析,數(shù)據(jù)結構框架的設計以及設計最短路線等復雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結構的學習就是為以后利用計算機資源高效地開發(fā)非數(shù)值處理的計算機程序打下堅實的理論,方法和技術基礎。利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工通信（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)，試設計一個哈夫曼編碼系統(tǒng)。關鍵詞：huffman編碼樹；編碼；譯碼abstractwith

2、the widespread application and the development of computer, its application is not limited to a simple numerical computation, and relates to theproblem analysis, data structure design of the framework for the design and the shortest route of complicated non numerical processing and operation. the al

3、gorithm and data structure of learning for the future is the use of computer resources efficiently to develop computer programs non numerical treatment to lay a solid theoretical foundation, methods and techniques.the use of huffman coding can greatly improve the communication channel utilization, r

4、educe the information transmission time, lower transmission costs.however, this requires the sending end through a coding system for pre encoded data, at the receiving end of data from the decoding (fu yuan). forduplex communication (which can be a two-way channel to transmit information),each side

5、needs a complete encoding / decoding system, try to design a huffman coding system.keywords: huffman coding tree; coding;decoding目 錄1概述11.1設計背景11.2問題分析11.3設計任務21.4總體結構22總體設計32.1總體設計思想、設計方案的選擇32.1.1 最優(yōu)二叉樹（huffman樹）32.1.2構造哈夫曼樹的步驟32.1.3數(shù)據(jù)結構的選擇42.2結構設計42.2.1結構體存儲表示42.2.2主函數(shù)模塊42.2.3系統(tǒng)結構圖53詳細設計73.1構造哈夫曼樹

6、73.2哈夫曼編碼84系統(tǒng)實現(xiàn)與測試94.1錯誤分析94.2運行結果95 總結12參考文獻13致 謝14附 錄151概述1.1設計背景1951年，哈夫曼和他在mit信息論的同學需要選擇是完成學期報告還是期末考試。導師robert m. fano給他們的學期報告的題目是，尋找最有效的二進制編碼。由于無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發(fā)現(xiàn)了基于有序頻率二叉樹編碼的想法，并很快證明了這個方法是最有效的。 由于這個算法，學生終于青出于藍，超過了他那曾經和信息論創(chuàng)立者香農共同研究過類似編碼的導師。哈夫曼使用自底向上的方法構建二叉樹，避免了次優(yōu)算法shannon

7、-fano編碼的最大弊端自頂向下構建樹。哈夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。1.2問題分析哈夫曼在上世紀五十年代初就提出這種編碼時，根據(jù)字符出

8、現(xiàn)的概率來構造平均長度最短的編碼。它是一種變長的編碼。哈夫曼編碼應用廣泛，如jpeg中就應用了哈夫曼編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現(xiàn)概率的大小的逆序排列，則編碼的平均長度是最小的。構造好哈夫曼樹后，就可根據(jù)哈夫曼樹進行編碼。然而怎樣構造一棵哈夫曼樹呢？最具有一般規(guī)律的構造方法就是哈夫曼算法。字符根據(jù)其出現(xiàn)的概率作為權值構造一棵哈夫曼樹后，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字符。顯然哈夫曼編碼是前綴編碼，即任一個字符的編碼都不是另一個字符的編碼的前綴，否則，編碼就不能進行翻譯。分析此次設計，是關于實現(xiàn)利用哈夫曼算法編碼和譯碼功能的

9、問題，要求能重復地顯示并處理以下項目，即構造哈夫曼樹，編碼及譯碼幾項功能，直到選擇退出為止。本次設計就是為這樣的一個哈夫曼的編/譯碼器。1.3設計任務主要內容：設計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，可以接收從鍵盤輸入的字符集大小、字符和權值信息，創(chuàng)建哈夫曼樹生成哈夫曼編碼并能對其進行解碼。功能指標：1.使用二叉鏈表存儲結構，主要功能有：建立哈夫曼樹、利用已建好的哈夫曼樹（如不在內存，則從文件hfmtree中讀入），對文件中的正文進行編碼、對文件中的代碼進行譯碼、顯示輸出等功能；2. 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“this program i

10、s my favorite”.表1.1 字符集和頻度字符abcdefghijklm頻度1866413223210321154757153220字符nopqrstuvwxyz頻度5763151485180238181161算法對于合法的輸入數(shù)據(jù)都能產生滿足規(guī)格說明要求的結果；3. 算法對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結果；對算法實現(xiàn)過程中的異常情況能給出有效信息。1.4總體結構本程序主要分為3個模塊：主模塊，編碼模塊，譯碼模塊。主模塊：程序的主體部分，分別調用各個模塊，實現(xiàn)各項功能。編碼模塊：對每個出現(xiàn)的字符進行編碼。譯碼模塊：將已有編碼譯成字符，使之

11、可以直接被讀出。2總體設計2.1總體設計思想、設計方案的選擇哈夫曼編碼所以能產生較短的碼文，是因為哈夫曼樹具有最小加權路徑長度的二叉樹。如果葉結點的權值恰好是某個需編碼的文本中各字符出現(xiàn)的次數(shù)，則編碼后文本的長度就是該哈夫曼樹的加權路徑長度。譯碼過程為自做向右逐一掃描碼文，并從哈夫曼樹的根開始，將掃到的二進制位串中的相鄰位與哈夫曼樹上標的0，1相匹配，以確定一條從根到葉子結點的路徑，一旦到達葉子，則譯出了一個字符。再回到樹根，從二進位串的下一位開始繼續(xù)譯碼。2.1.1 最優(yōu)二叉樹（huffman樹） 首先給出路徑和路徑長度的概念。從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑，路

12、徑上的分支數(shù)目稱作路徑長度。樹的路徑長度是從樹根到每一結點的路徑長度之和。結點的帶權路徑長度為從該結點到樹根之間的路徑長度與節(jié)點上權的乘積。樹的帶權路徑長度為書中所有葉子結點的帶權路徑長度之和，通常記做。那么假設有個權值，試構造一棵有個葉子結點的二叉樹，每個葉子結點帶權為，則其中帶權路徑長度 最小的二叉樹稱作最優(yōu)二叉樹或huffman 樹。2.1.2構造哈夫曼樹的步驟步驟如下：1、 對給定的n個權值w1,w2,w3,.,wi,.,wn構成n棵二叉樹的初始集合f=t1,t2,t3,.,ti,.,tn，其中每棵二叉樹ti中只有一個權值為wi的根結點，它的左右子樹均為空。（為方便在計算機上實現(xiàn)算法，

13、一般還要求以ti的權值wi的升序排列。）； 2、 選取左右子樹：在f中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。3、 刪除左右子樹：從f中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合f中。 4、重復2、3兩步：重復2和3，直到集合f中只有一棵二叉樹為止。2.1.3數(shù)據(jù)結構的選擇為了建立哈夫曼樹以及實現(xiàn)哈夫曼編碼以及譯碼，因此我們選擇了結點結構體，利用這一結構體，我們定義了一個結構體數(shù)組和一個樹根指針，數(shù)組用來紀錄輸入數(shù)據(jù)的多少，樹根指針用來連接哈夫曼樹。從程序中可以看到使用哈夫曼算法構造哈夫曼樹過程，是從n棵知識一

14、個根結點的樹組成的森林開始的。在算法執(zhí)行中，哈夫曼樹是由若干棵樹組成的森林，通過不斷地合并樹，最后得到一棵哈夫曼樹。2.2結構設計2.2.1結構體存儲表示typedef struct char ch; unsigned int weight;unsigned int parent, lchild, rchild;htnode,*huffmantree; /動態(tài)分配數(shù)組存儲哈夫曼樹typedef char *huffmancode; /動態(tài)分配數(shù)組存儲哈弗曼編2.2.2主函數(shù)模塊在主函數(shù)實現(xiàn)過程，使用開關語句switch（）函數(shù)對函數(shù)的各模塊調用，使得函數(shù)的運行效率大大提高，主函數(shù)實現(xiàn)功能用如下

15、算法表示。main()int num; char *str= abcdefghijklmnopqrstuvwxyz; while(1)printf(n);printf( *赫夫曼編碼/譯碼器 *n); printf( *1 使用默認初始化 *n); printf( *2 使用自定義初始化 *n); printf( *3 編碼 *n); printf( *4 譯碼 *n);printf( *5 退出 *n)printf(n); printf(請輸入您要操作的步驟：);scanf(%d,&num);getchar( );switch(num)case 1 :huffmancoding(ht,wei

16、,27,str);break;case 2:customize();break;case 3 :texttocode();break;case 4 :codetotext();break;case 5 :exit(0);break;return 0;2.2.3系統(tǒng)結構圖程序開始定義一個結構體用來動態(tài)分配數(shù)組存儲哈夫曼樹和哈夫曼編碼，然后定義各個函數(shù)下的變量，初始化程序設計任務中所給字符的權值，通過選擇函數(shù)void select( )選擇所給字符中權值最小的兩個字符作為葉子節(jié)點，運用循環(huán)函數(shù)依次比較把權值最小的節(jié)點賦給定義的變量，同時運用void huffmancoding( )函數(shù)對字母編碼，

17、void customize( )函數(shù)用來用戶自定義權值和字符，void texttocode( )函數(shù)進行編碼，void codetotext( )函數(shù)進行譯碼，最后使用主函數(shù)對給函數(shù)塊進行調用，實現(xiàn)程序的各個功能。如下是哈夫曼編/譯碼器結構框圖。默認初始化自定義初始化編碼譯碼退出主函數(shù) 圖2.1 哈夫曼編/譯碼器結構框圖3詳細設計3.1構造哈夫曼樹如下流程圖（圖3.1）為構造哈夫曼樹的過程，輸入字符的次數(shù)為權值對每個結點賦值，構造哈夫曼樹。ny讀入字符次數(shù)并令i=2n-1找出最小和次小樹s1,s2兩樹合并成新樹n+ii減1i為0開始結束圖3.1 構造哈夫曼樹3.2哈夫曼編碼如下流程圖（圖3

18、.2）是對字符進行哈夫曼編碼的過程，將字符轉化為哈夫曼編碼。記編碼0將得到的編碼存儲左節(jié)點?=該節(jié)點第一個字符，i=1=i=n記編碼1i=i+1開始nn節(jié)點?=根節(jié)點結束yyny n圖3.2 編碼模塊流程圖4系統(tǒng)實現(xiàn)與測試4.1錯誤分析在此程序調試過程中主要遇到以下幾類問題：1、本程序運用了對文件進行操作，一定要注意操作文件的位置，我在做此程序時就是因為操作的文件位置錯了導致程序無法正常運行。2、在函數(shù)內部有時需要多次定義參數(shù)，注意參數(shù)的作用域，而且注意引用調用和傳值調用的區(qū)別，如果不能正確的修改實參的值，就會導致程序運行錯誤。3、本程序用到的外部函數(shù)較多，在調用時一定要注意傳入的參數(shù)是否符合

19、函數(shù)的定義，而且位置也不能錯，這是引用函數(shù)要注意的一點。4、剛開始時清屏函數(shù)運用出錯，導致操作界面消失，使用戶無法操作，因此，在使用一些函數(shù)是一定要注意。4.2運行結果運行程序首先出現(xiàn)界面圖，如圖4.1所示圖4.1 界面圖選擇操作1后，默認初始化，生成哈夫曼樹。系統(tǒng)會顯示每個字符的哈夫曼編碼，但由于截圖不方便，因此選擇操作2用戶自定義初始化，輸入相應的字符個數(shù)大小，字符和權值，生成哈夫曼樹。系統(tǒng)會顯示每個字符的哈夫曼編碼，如圖4.2所示。圖4.2 程序運行截圖圖4.2 程序運行截圖選擇操作3后，系統(tǒng)會顯示用哈夫曼編碼翻譯成的字符，顯示以下界面（圖4.3）供用戶選擇圖4.3 程序運行截圖選擇操作

20、4后，系統(tǒng)會顯示用哈夫曼編碼翻譯成的字符，顯示以下界面（圖4.4）供用戶選擇圖4.4 程序運行截圖選擇操作5后，退出系統(tǒng)，顯示以下界面（圖4.5）圖4.5 程序運行截圖5 總結通過此次課程設計，使我們更加扎實的掌握了有關數(shù)據(jù)結構方面的知識，在設計過程中雖然遇到了一些問題，但經過一次又一次的思考，一遍又一遍的檢查終于找出了原因所在，也暴露出了前期我在這方面的知識欠缺和經驗不足。實踐出真知，通過親自動手制作，使我們掌握的知識不再是紙上談兵。在課程設計過程中，我們不斷發(fā)現(xiàn)錯誤，不斷改正，不斷領悟，不斷獲取。在設計中遇到了很多問題，最后在謝老師的指導下，終于迎刃而解。在今后社會的發(fā)展和學習實踐過程中，

21、一定要不懈努力，不能遇到問題就想到要退縮，一定要不厭其煩的發(fā)現(xiàn)問題所在，然后一一進行解決，只有這樣，才能成功的做成想做的事，才能在今后的道路上劈荊斬棘，而不是知難而退.課程設計誠然是一門專業(yè)課，給我很多專業(yè)知識以及專業(yè)技能上的提升，同時又是一門辯思課，給了我很多思，給了我莫大的空間。同時，設計讓我感觸很深。使我對抽象的理論有了具體的認識。我認為，在這學期的課設中，不僅培養(yǎng)了我獨立思考、動手操作的能力，在各種其它能力上也都有了提高。更重要的是，在實驗課上，我們學會了很多學習的方法。而這是日后最實用的，真的是受益匪淺。在這兩周里，可以說得是苦多于甜，但是可以學到很多很多的東西，同時不僅可以鞏固了以

22、前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。通過這次課程設計使我懂得了理論與實際相結合是很重要的，只有理論知識是遠遠不夠的，只有把所學的理論知識與實踐相結合起來，從理論中得出結論，從而提高自己的實際動手能力和獨立思考的能力。在設計的過程中遇到問題，可以說得是困難重重，但可喜的是最終都得到了解決。 課設過程中，也對團隊精神的進行了考察，讓我們在合作起來更加默契，在成功后一起體會喜悅的心情。果然是團結就是力量，只有互相之間默契融洽的配合才能換來最終完美的結果。此次設計也讓我明白了思路即出路，有什么不懂不明白的地方要及時請教或上網查詢，只要認真鉆研，動腦思考，動手實踐，就沒有弄不懂的知

23、識。參考文獻1 譚浩強.c程序設計教程m.清華大學出版社，2007.062 趙永哲，李雄飛.c語言程序設計m.科學出版社，2006.043 夏寬理，趙子正.c語言程序設計m.中國鐵道出版社，2006.054 譚浩強編著.c程序設計m.清華大學出版社，1991.075 藤國文編著.數(shù)據(jù)結構課程設計m.清華大學出版社，2010.026 嚴蔚敏，吳偉民編著.數(shù)據(jù)結構（c語言版）m.清華大學出版社，2006.037 蘇德富.計算機算法設計與分析m.清華大學出版社，1991.048 曹新譜.算法設計與分析m.湖南科學技術出版社，1984.079 胡學剛.算法與數(shù)據(jù)結構設計指導m.清華大學出版社，1999

24、.0610 張乃孝.數(shù)據(jù)結構c+與面向對象的途徑m.高等教育出版社，2001.07致 謝在這次課程設計的撰寫過程中，我們之所以能夠順利的完成我們的數(shù)據(jù)結構課程設計，要感謝我們的指導老師謝老師，我們的成功離不開她的諄諄教導，在這短暫而又忙碌的兩周里，我們學習收獲了很多。首先我們要感謝謝老師在課程設計上給予我們的指導、提供給我們的支持和幫助，這是我們能順利完成這次報告的主要原因，更重要的是老師幫我們解決了許多技術上的難題，讓我能把系統(tǒng)做得更加完善。在此期間，我不僅學到了許多新的知識，而且也開闊了視野，提高了自己的設計能力。 其次，我要感謝幫助過我的同學，他們也為我解決了不少我不太明白的設計上的難題

25、。同時也感謝學院為我提供良好的做畢業(yè)設計的環(huán)境。 最后再一次感謝所有在設計中曾經幫助過我的良師益友和同學。我們會在以后的求學路上再接再厲，不斷完善自我，提高自我，為以后順利的步入社會打下結實的基礎。由衷的感謝老師和同學們的幫助。附 錄源代碼程序：#include#include#include#includetypedef struct char ch; unsigned int weight;unsigned int parent, lchild, rchild;htnode,*huffmantree;typedef char *huffmancode;int wei27=186,64,13

26、,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1; /186為空格的權值int flag54;static int n,m;huffmantree ht;huffmancode hc;void select(huffmantree ht, int j,int &s1,int &s2) /在1到j 中 選擇雙親為0，并且weight最小的兩個子葉節(jié)點 ,其序號分別為s1,s2int i,mark=0;for(i=1;i=j;i+) /for循環(huán)找到權值最小的節(jié)點 if(flagi=0&mark=0) /第一次

27、把第一個flag未改變的節(jié)點編號 給s1s1=i;mark=1;else if(hti.weighthts1.weight&flagi=0) s1=i; /通過循環(huán)把最小權值節(jié)點給s1mark=0; /mark 歸零flags1=1; /把s1節(jié)點的標記改為1for(i=1;i=j;i+)if(flagi=0&mark=0)s2=i;mark=1;else if(hti.weighthts2.weight&flagi=0)s2=i;flags2=1;void huffmancoding(huffmantree &ht, int w, int s,char *ch) /*1*哈夫曼初始化進行對字

28、母編碼n=s;int i, j, s1, s2, start;char *cd;unsigned int c, f;for(i=0;is*2;i+)flagi=0; /每個對應節(jié)點標記為0 選擇最小節(jié)點時 被選中標記為1if (n=1) return;m=2*n-1; /n個子葉 2*n-1個節(jié)點ht=(huffmantree)malloc(m+1) * sizeof(htnode);/0號單元未用for (i=1; i=n; i+)/哈夫曼樹初始化hti.weight=wi-1; /w對應的權值依次賦給ht每一個葉子節(jié)點hti.ch=chi-1; /ch對應的字母依次賦給 沒一個葉子節(jié)點ht

29、i.parent=0;hti.lchild=0;hti.rchild=0;for (; i=m; i+)hti.weight=0;hti.parent=0;hti.lchild=0;hti.rchild=0;hti.ch= ;printf(n哈夫曼樹的構造過程如下所示：n);for (i=n+1; i=m; i+) /構建哈夫曼樹select(ht, i-1, s1, s2);hts1.parent=i; hts2.parent=i;hti.lchild=s1; hti.rchild=s2;hti.weight=hts1.weight + hts2.weight;printf(n 結點 cha

30、r weight parent lchild rchild); for (j=1; j=i-1; j+)printf(n%4d%6c%8d%8d%8d%8d,j,htj.ch,htj.weight,htj.parent,htj.lchild, htj.rchild);/- 從葉子到根逆向求每個字符的哈夫曼編碼 -hc=(huffmancode)malloc(n+1)*sizeof(char *);cd = (char *)malloc(n*sizeof(char);cdn-1 =0;for (i=1; i=n; +i)start = n-1;for (c=i, f=hti.parent; f!

31、=0; c=f, f=htf.parent)if (htf.lchild=c) cd-start=0;else cd-start = 1;hci=(char *)malloc(n-start)*sizeof(char);strcpy(hci, &cdstart);printf(n每個字母對應的哈夫曼編碼:n);for(int a=1; a1:);scanf(%d,&n);for(int i=0;in;i+)printf(請輸入第%d個字母及對應的權值:,i+1);scanf(%s %d,&chi,&weighti);huffmancoding(ht,weight,n,ch);void texttocode() /*3編碼*char str50;int j;if(ht