基于哈夫曼樹的哈夫曼編譯碼器設(shè)計與實現(xiàn)

1、長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文）基于哈夫曼樹的哈夫曼編基于哈夫曼樹的哈夫曼編/ /譯碼器設(shè)計與實現(xiàn)譯碼器設(shè)計與實現(xiàn)With the implementation of decoder design based on Huffman tree Huffman encoding 年 級: 學(xué) 號: 姓 名: 專 業(yè): 指導(dǎo)老師: 二零一三年十二月長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文）I摘 要隨著計算機應(yīng)用技術(shù)的快速發(fā)展和日益普及，網(wǎng)絡(luò)也遍及到我們生活的每個角 落，為我們的學(xué)習(xí)和工作帶來極大的方便。很多人都使用過傳統(tǒng)的文字輸入聊天方式，與之不同的另外一種聊天方式就是語音聊天。主要對那些不會使用鍵盤

2、的老年用戶和追求時尚的年輕人，語音聊天是一種非常好的聊天方式，它能增加聊天雙方的親切感和真實感，語音聊天就涉及到語音的傳輸。 本系統(tǒng)主要討論了 Windows系統(tǒng)下網(wǎng)絡(luò)語音的傳輸，主要利用 Windows 系統(tǒng)下的 API 函數(shù)和 SOCKET 函數(shù)以及VC 開發(fā)平臺的強大功能來實現(xiàn)。本系統(tǒng)可以實現(xiàn)網(wǎng)絡(luò)間文字、語音信息的傳輸。信息社會的高科技，商品經(jīng)濟化的高效益，使計算機的應(yīng)用已普及到經(jīng)濟和社會生活的各個領(lǐng)域。計算機雖然與人類的關(guān)系愈來愈密切，還有人由于計算機操作不方便繼續(xù)用手工勞動。為了適應(yīng)現(xiàn)代社會人們高度強烈的時間觀念，學(xué)生成績管理系統(tǒng)軟件為教學(xué)辦公室?guī)砹藰O大的方便。該軟件是以 C 語言

3、為實現(xiàn)語言，其功能在系統(tǒng)內(nèi)部有源代碼直接完成。通過操作目錄，管理者和老師可以了解本軟件的基本工作原理。管理者和老師只需輸入一些簡單的漢字、數(shù)字，即可達到自己管理學(xué)生成績的目標(biāo)。 關(guān)鍵字關(guān)鍵字: : 哈夫曼樹 編碼 解碼 數(shù)據(jù)壓縮技術(shù)長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文）IIAbstractWith the rapid development of computer technology and popularization, network throughout each corner of ourlife, brings great convenience for our study and

4、work.Many people use the traditional text input chat mode,unlike another chat mode is the voice chat. Mainly to the young people who do not use the keyboard to elderly users and the pursuit of fashion, voice chat is a very goodchat mode, it can increase the intimacy and realistic chatbetween the two

5、 sides, voice chat is involved in the transmission of voice. This system is mainly discussed under the Windows system transmission of voice, the main use of Windows system under the API function and SOCKET function as well as the powerful features of the VC platform to achieve. This system can reali

6、ze thenetwork transmission of text, voice information.Information society technology, high benefit of commodity economy, causes the computer the application to the economical and social life each domain.Although the computer and human relations more closely, it was inconvenient for computer operator

7、s continue to use manual labor. In order to adapt to modern society was highly strong concept of time, has brought great convenience to student achievement management system software for teachingoffice. The software is based on C language for the realization of language, its function within the syst

8、em active code directly completed. Through the operation of the directory, administrators and teachers can understand the basic working principle of the software. Managers and teachers only need to input some simple Chinese characters, numbers, and can achieve their goal ofthe management of student

9、achievement.Keywords: Huffman tree coding and decoding data compression長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文）目 錄摘 要 .IABSTRACT.II第 1 章 緒 論.- 1 -1.1 需求分析.- 1 -1.2 實驗?zāi)康?.- 1 -1.3 實驗內(nèi)容.- 2 -第 2 章 系統(tǒng)總體設(shè)計.- 3 -2.1 基本要求.- 3 -2.2 算法設(shè)計思想.- 3 -2.3 設(shè)計要求.- 3 -第三章 系統(tǒng)詳細設(shè)計.- 4 -哈夫曼編碼/譯碼器源代碼 .- 4 -第四章 總體設(shè)計.- 12 -4.1 設(shè)計概述.- 12 -4.2 系統(tǒng)

10、結(jié)構(gòu)圖.- 13 -第五章 系統(tǒng)測試.- 13 -5.1 實驗結(jié)果.- 14 -實驗總結(jié).- 17 -收獲與心得.- 18 -參考文獻.- 19 -長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文）- 1 -第 1 章 緒 論引言：引言： 在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。1.1 需求分析在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視，赫夫曼編碼正是一種應(yīng)用廣泛且非常

11、有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于,它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是赫夫曼編碼。1

12、.2 實驗?zāi)康?.掌握建立哈夫曼樹和哈夫曼編碼的方法2.掌握哈夫曼編碼的實際應(yīng)用方法長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 2 -1.3 實驗內(nèi)容 利用哈夫曼編碼進行通信可以大大提高信道利用率,縮短信息傳輸時間,降低傳輸成本。但是,這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼,在接收端將傳來的數(shù)據(jù)進行譯碼。對于雙工信道(即可以雙向傳輸信息的信道),每端都需要一個完成的編譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 3 -第 2 章 系統(tǒng)總體設(shè)計2.1 基本要求1.硬件：微機和打印機一臺各2.軟件：Visual C+ windows72.2

13、 算法設(shè)計思想1) 分析程序的功能要求，劃分程序功能模塊2) 畫出系統(tǒng)流程3) 代碼的編寫，定義數(shù)據(jù)結(jié)構(gòu)和各個功能子函數(shù)4) 程序的功能調(diào)試2.3 設(shè)計要求1. 寫出系統(tǒng)需求分析,并建模。 2. 編程實現(xiàn),界面友好。 3. 輸出操作前后的結(jié)果。4. 提供測試報告長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 4 -第三章 系統(tǒng)詳細設(shè)計哈夫曼編碼哈夫曼編碼/譯碼器源代碼譯碼器源代碼void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,start; int c,f; HuffmanTr

14、ee p; char *cd; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; 長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 5 - for(;iparent=0; for(i=n+1;i=m;+i) select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs

15、1.weight+HTs2.weight; 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!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 6 - cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,

16、&cdstart); free(cd); void Initialization() flag=1; int num2; cout下面初始化哈夫曼鏈表endl; w=(int*)malloc(n*sizeof(int); z=(char*)malloc(n*sizeof(char); coutn 依次顯示n個字符與其權(quán)值和編碼nendl; char base2;/?ifstream fin(abc.txt); for(i=0;ibase;長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 7 - *(z+i)=*base;/? finnum2; *(w+i)=num2; HuffmanCodin

17、g(HT,HC,w,n); cout字符setw(6)權(quán)值setw(11)編碼endl; for(i=1;i=n;i+) coutsetw(3)*(z+i-1); coutsetw(6)*(w+i-1)setw(12)HCiendl; cout下面將哈夫曼編碼寫入文件endl.endl; FILE *htmTree; char r= ,0; if(htmTree=fopen(htmTree.txt,w)=NULL) cout不能打開文件 endl; return; 長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 8 - for(i=0;in;i+) fputc(*(z+i),htmTree); fp

18、uts(r,htmTree); for(i=0;in;i+) fprintf(htmTree,%6d,*(w+i); fputs(r,htmTree); for(i=1;i=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); cout已將字符與對應(yīng)編碼寫入根目錄下文件 htmTree.txt 中endlendl;void Tree_printing(HuffmanTree HT,int w) HuffmanTree p;長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 9 - p=HT+w; cout下面打印哈夫曼樹endl; co

19、print(p,HT); cout打印工作結(jié)束endl;void main() coutendl; cout 此程序?qū)崿F(xiàn)哈夫曼編碼解碼功能 endl; char choice; while(choice!=q) coutn*endl; cout 哈夫曼編碼解碼 endl; cout* endl; cout(i)初始化哈夫曼表 endl; cout(w)輸入待編碼的字符 endl; cout(e)進行編碼、譯碼、打印編碼 endl; cout(t)打印哈夫曼樹 endl;長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 10 - cout(q)離開 endl; if(flag=0)coutn 請先初始化

20、哈夫曼鏈表,輸入iendl;cout(程序?qū)母夸浵碌?abc.txt 文件中讀出 26 個字母及其權(quán)值并對字母進行編碼)choice; switch(choice) case i: Initialization(); break; case w: InputCode(); break; case e: Encoding(); Decoding();長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 11 - Code_printing(); break; case t: Tree_printing(HT,2*n-1); break; case q: break; default: cout輸入命令錯

21、誤 endl; free(z); free(w); free(HT);長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 12 -第四章 總體設(shè)計4.1 設(shè)計概述 1)問題分析哈夫曼在上世紀五十年代初就提出這種編碼時，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。它是一種變長的編碼。哈夫曼編碼應(yīng)用廣泛，如 JPEG 中就應(yīng)用了哈夫曼編碼。在編碼中，若各碼字長度嚴格按照碼字所對應(yīng)符號出現(xiàn)概率的大小的逆序排列，則編碼的平均長度是最小的。構(gòu)造好哈夫曼樹后，就可根據(jù)哈夫曼樹進行編碼。然而怎樣構(gòu)造一棵哈夫曼樹呢？最具有一般規(guī)律的構(gòu)造方法就是哈夫曼算法。字符根據(jù)其出現(xiàn)的概率作為權(quán)值構(gòu)造一棵哈夫曼樹后，經(jīng)哈夫曼編碼得到

22、的對應(yīng)的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字符。顯然哈夫曼編碼是前綴編碼，即任一個字符的編碼都不是另一個字符的編碼的前綴，否則，編碼就不能進行翻譯。分析此次設(shè)計，是關(guān)于實現(xiàn)利用哈夫曼算法編碼和譯碼功能的問題，要求能重復(fù)地顯示并處理以下項目，即構(gòu)造哈夫曼樹，編碼及譯碼幾項功能，直到選擇退出為止。本次設(shè)計就是為這樣的一個哈夫曼的編/譯碼器。長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 13 -4.2 系統(tǒng)結(jié)構(gòu)圖 main()Initialization（）初始化函數(shù)Input()輸入待編碼字符函數(shù)Encoding（）編碼函數(shù)Decoding（）譯碼函數(shù)Code_printing()

23、打印編碼函數(shù)Tree_printing()打印哈夫曼樹第 5 章 系統(tǒng)測試 此次測試舉例為對輸入的英文 HAPPYNEWYEAR 應(yīng)用創(chuàng)建的哈夫曼編譯碼器進行編碼再譯碼。聲明：程序預(yù)先將 Huffman 編碼解碼所需的 26 個字母和權(quán)值保存在根目錄下的abc.txt 文件下。a.按照程序提示輸入 i 對 Huffman 進行初始化。b.初始化后程序?qū)?abc.txt 文件中的數(shù)據(jù)進行讀取并運行編碼函數(shù)進行哈夫曼編碼。然后將字母、權(quán)值和哈夫曼編碼存在根目錄下的 htmTree.txt 文件中。在屏幕顯示出字符、權(quán)值、編碼。c.輸入 w 進入待編碼字符輸入窗口，并鍵入字符串（注意單詞間無空格）“

24、happynewyear” 。 d.可以看出所獲得的字符串已經(jīng)存入根目錄下的 tobetran.txt 文件中。 e.輸入 e 進行編碼、譯碼和打印編碼功能。f.輸入 t 打印哈夫曼樹。長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 14 -g.輸入 q 退出程序。5.1 實驗結(jié)果長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 15 -長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 16 -長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（論文） - 17 -實驗總結(jié)通過這次課程設(shè)計使我充分的理解了哈夫曼編譯碼問題的基本原理，知道了樹的不同存儲結(jié)構(gòu)的定義和算法描述，同時也學(xué)會了編寫簡單的哈夫曼編譯碼程序。雖然這個程序不是最好的，但是總體還是一個比較能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)知識點能力的程序，當(dāng)然只是相對于我這個初學(xué)者來說。在剛開始