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

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

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

3、為實(shí)現(xiàn)語言，其功能在系統(tǒng)內(nèi)部有源代碼直接完成。通過操作目錄，管理者和老師可以了解本軟件的基本工作原理。管理者和老師只需輸入一些簡單的漢字、數(shù)字，即可達(dá)到自己管理學(xué)生成績的目標(biāo)。 關(guān)鍵字關(guān)鍵字: : 哈夫曼樹 編碼 解碼 數(shù)據(jù)壓縮技術(shù)長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（論文）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è)計(jì)（論文）目 錄摘 要 .IABSTRACT.II第 1 章 緒 論.- 1 -1.1 需求分析.- 1 -1.2 實(shí)驗(yàn)?zāi)康?.- 1 -1.3 實(shí)驗(yàn)內(nèi)容.- 2 -第 2 章 系統(tǒng)總體設(shè)計(jì).- 3 -2.1 基本要求.- 3 -2.2 算法設(shè)計(jì)思想.- 3 -2.3 設(shè)計(jì)要求.- 3 -第三章 系統(tǒng)詳細(xì)設(shè)計(jì).- 4 -哈夫曼編碼/譯碼器源代碼 .- 4 -第四章 總體設(shè)計(jì).- 12 -4.1 設(shè)計(jì)概述.- 12 -4.2 系統(tǒng)

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

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

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

13、 算法設(shè)計(jì)思想1) 分析程序的功能要求，劃分程序功能模塊2) 畫出系統(tǒng)流程3) 代碼的編寫，定義數(shù)據(jù)結(jié)構(gòu)和各個(gè)功能子函數(shù)4) 程序的功能調(diào)試2.3 設(shè)計(jì)要求1. 寫出系統(tǒng)需求分析,并建模。 2. 編程實(shí)現(xiàn),界面友好。 3. 輸出操作前后的結(jié)果。4. 提供測(cè)試報(bào)告長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（論文） - 4 -第三章 系統(tǒng)詳細(xì)設(shè)計(jì)哈夫曼編碼哈夫曼編碼/譯碼器源代碼譯碼器源代碼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è)計(jì)（論文） - 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è)計(jì)（論文） - 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個(gè)字符與其權(quán)值和編碼nendl; char base2;/?ifstream fin(abc.txt); for(i=0;ibase;長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（論文） - 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è)計(jì)（論文） - 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已將字符與對(duì)應(yīng)編碼寫入根目錄下文件 htmTree.txt 中endlendl;void Tree_printing(HuffmanTree HT,int w) HuffmanTree p;長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（論文） - 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)進(jìn)行編碼、譯碼、打印編碼 endl; cout(t)打印哈夫曼樹 endl;長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（論文） - 10 - cout(q)離開 endl; if(flag=0)coutn 請(qǐng)先初始化

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

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

22、的對(duì)應(yīng)的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字符。顯然哈夫曼編碼是前綴編碼，即任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴，否則，編碼就不能進(jìn)行翻譯。分析此次設(shè)計(jì)，是關(guān)于實(shí)現(xiàn)利用哈夫曼算法編碼和譯碼功能的問題，要求能重復(fù)地顯示并處理以下項(xiàng)目，即構(gòu)造哈夫曼樹，編碼及譯碼幾項(xiàng)功能，直到選擇退出為止。本次設(shè)計(jì)就是為這樣的一個(gè)哈夫曼的編/譯碼器。長春建筑學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（論文） - 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)測(cè)試 此次測(cè)試舉例為對(duì)輸入的英文 HAPPYNEWYEAR 應(yīng)用創(chuàng)建的哈夫曼編譯碼器進(jìn)行編碼再譯碼。聲明：程序預(yù)先將 Huffman 編碼解碼所需的 26 個(gè)字母和權(quán)值保存在根目錄下的abc.txt 文件下。a.按照程序提示輸入 i 對(duì) Huffman 進(jìn)行初始化。b.初始化后程序?qū)?abc.txt 文件中的數(shù)據(jù)進(jìn)行讀取并運(yùn)行編碼函數(shù)進(jìn)行哈夫曼編碼。然后將字母、權(quán)值和哈夫曼編碼存在根目錄下的 htmTree.txt 文件中。在屏幕顯示出字符、權(quán)值、編碼。c.輸入 w 進(jìn)入待編碼字符輸入窗口，并鍵入字符串（注意單詞間無空格）“

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