哈夫曼樹編碼譯碼實(shí)驗(yàn)報(bào)告

1、精選文檔數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)設(shè)計(jì)題目： 哈夫曼樹編碼譯碼 課題名稱哈夫曼樹編碼譯碼院 系班級(jí)專業(yè)學(xué) 號(hào)姓 名成 績(jī)課題設(shè)計(jì)目的與設(shè)計(jì)意義1、課題設(shè)計(jì)目的：在當(dāng)今信息爆炸時(shí)代，如何接受有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視，哈夫曼編碼正是一種應(yīng)用廣泛且格外有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是依據(jù)每一個(gè)源字符消滅的估算概率而建立起來的。2、課題設(shè)計(jì)意義：哈夫曼編

2、碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支商定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進(jìn)制代碼，輸入二進(jìn)制代碼時(shí)可以編譯成字符串。指導(dǎo)老師：年 月 日目錄第一章 需求分析1其次章 設(shè)計(jì)要求1第三章 概要設(shè)計(jì)2（1）其主要流程圖如圖1-1所示。3（2）設(shè)計(jì)包含的幾個(gè)方面4第四章 具體設(shè)計(jì)4（1）哈夫曼樹的存儲(chǔ)結(jié)構(gòu)描述為：4（2）哈弗曼編碼5（3）哈弗曼譯碼7（4）主函數(shù)8（5）顯示

3、部分源程序：8第五章 調(diào)試結(jié)果10第六章 心得體會(huì)12第七章 參考文獻(xiàn)12附錄：12第一章 需求分析在當(dāng)今信息爆炸時(shí)代，如何接受有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視，哈夫曼編碼正是一種應(yīng)用廣泛且格外有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是依據(jù)每一個(gè)源字符消滅的估算概率而建立起來的（消滅概率高的字符使用較短的編碼，反之消滅概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的

4、平均期望長(zhǎng)度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支商定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進(jìn)制代碼，輸入二進(jìn)制代碼時(shí)可以編譯成字符串。其次章 設(shè)計(jì)要求對(duì)輸入的一串電文字符實(shí)現(xiàn)哈夫曼編碼，再對(duì)哈夫曼編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字

5、符串。但在信息傳遞時(shí)，總期望總長(zhǎng)度能盡可能短，即接受最短碼。假設(shè)每種字符在電文中消滅的次數(shù)為Wi，編碼長(zhǎng)度為L(zhǎng)i，電文中有n種字符，則電文編碼總長(zhǎng)度為WiLi。若將此對(duì)應(yīng)到二叉樹上，Wi為葉結(jié)點(diǎn)的權(quán)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度。那么，WiLi恰好為二叉樹上帶權(quán)路徑長(zhǎng)度。因此 ，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符消滅的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。設(shè)計(jì)實(shí)現(xiàn)的功能： (1) 哈夫曼樹的建立； (2) 哈夫曼編碼的生成； (3) 編碼文件的譯碼。第三章 概要設(shè)計(jì)哈夫曼編譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進(jìn)行譯碼 。在數(shù)據(jù)

6、通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對(duì)應(yīng)字符的編碼，稱之為哈夫曼編碼。最簡(jiǎn)潔的二進(jìn)制編碼方式是等長(zhǎng)編碼。若接受不等長(zhǎng)編碼，讓消滅頻率高的字符具有較短的編碼，讓消滅頻率低的字符具有較長(zhǎng)的編碼，這樣可能縮短傳送電文的總長(zhǎng)度。哈夫曼樹課用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。（1）其主要流程圖如圖1-1所示。開頭結(jié)束結(jié)點(diǎn)數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點(diǎn)和權(quán)值調(diào)用SELECT函數(shù)計(jì)算根結(jié)點(diǎn)函數(shù)雙親結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和輸

7、出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn)是否為根結(jié)點(diǎn)？左子是否為空？此時(shí)編碼為0I<2*N?I+編碼為1否否否右子是否為空是是否否是是是（2）設(shè)計(jì)包含的幾個(gè)方面： 哈夫曼樹的建立哈夫曼樹的建立由哈夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點(diǎn)的二叉樹。算法的其次步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就削減一棵樹，產(chǎn)生一個(gè)新結(jié)點(diǎn)。明顯要進(jìn)行n1次合并，所以共產(chǎn)生n1個(gè)新結(jié)點(diǎn)，它們都是具有兩個(gè)孩子的分支結(jié)點(diǎn)。由此可知，最終求得的哈夫曼樹中一共有2n1個(gè)結(jié)點(diǎn)，其中n個(gè)結(jié)點(diǎn)是初始森林的n個(gè)孤立結(jié)點(diǎn)。并且哈夫曼樹中沒有度數(shù)為1的分支結(jié)點(diǎn)。我們可以利用一個(gè)大小為

8、2n-1的一維數(shù)組來存儲(chǔ)哈夫曼樹中的結(jié)點(diǎn)。 哈夫曼編碼 要求電文的哈夫曼編碼，必需先定義哈夫曼編碼類型，依據(jù)設(shè)計(jì)要求和實(shí)際需要定義的類型如下： typedet struct char ch; / 存放編碼的字符 char bitsN1; / 存放編碼位串 int len; / 編碼的長(zhǎng)度 CodeNode; / 編碼結(jié)構(gòu)體類型 代碼文件的譯碼 譯碼的基本思想是：讀文件中編碼，并與原先生成的哈夫曼編碼表比較，遇到相等時(shí)，即取出其對(duì)應(yīng)的字符存入一個(gè)新串中。 第四章 具體設(shè)計(jì)（1）哈夫曼樹的存儲(chǔ)結(jié)構(gòu)描述為： #define N 50 / 葉子結(jié)點(diǎn)數(shù) #define M 2*N-1 / 哈夫曼樹中結(jié)點(diǎn)

9、總數(shù) typedef struct int weight; / 葉子結(jié)點(diǎn)的權(quán)值 int lchild, rchild, parent; / 左右孩子及雙親指針 HTNode; / 樹中結(jié)點(diǎn)類型 typedef HTNode HuffmanTreeM+1; 哈弗曼樹的算法void CreateHT(HTNode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點(diǎn)數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /全部結(jié)點(diǎn)的相關(guān)域置初值-1 for (

10、i=n;i<2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weight<min1) /若權(quán)值小于最小的左節(jié)點(diǎn)的權(quán)值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rn

11、ode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)（2）哈弗曼編碼void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /依據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.p

12、arent; while (f!=-1) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點(diǎn) hc.cdhc.start-='0' else /處理右孩子結(jié)點(diǎn) hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開頭字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i&l

13、t;n;i+) /輸出data中的全部數(shù)據(jù)，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出全部data中數(shù)據(jù)的編碼 printf("%c",hcdi.cdk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數(shù)char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進(jìn)行編碼的字符串存入string數(shù)組中printf

14、("n輸出編碼結(jié)果:n");for (i=0;stringi!='#'i+) /#為終止標(biāo)志for (j=0;j<n;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號(hào)，相同的就輸出這個(gè)字符的編碼for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)（3）哈弗曼譯碼void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m

15、,x;scanf("%s",code); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時(shí)m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)則輸出這個(gè)的data數(shù)據(jù)printf("%c",hti.data);for(x=0;codex-1!='#

16、'x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;（4）主函數(shù)void main() int n=26,i; char orz,back,flag=1; char str='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',

17、9;Q','R','S','T','U','V','W','X','Y','Z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結(jié)構(gòu)體 HCode hcdN; /建立結(jié)構(gòu)體 for (i=0;i<n;i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri

18、; hti.weight=fnumi; while (flag) /菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán) （5）顯示部分源程序： printf("n"); printf(" *"); printf("n * 1-顯示編碼 *"); printf("n * 2-進(jìn)行編碼 *"); printf("n * 3-進(jìn)行譯碼 *"); printf("n * 4-退出 *n"); printf(" * *"); printf("n"); print

19、f(" 請(qǐng)輸入選擇的編號(hào):"); scanf("%c",&orz); switch(orz) case 'a': case 'A': system("cls"); /清屏函數(shù) CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case 'b': case 'B&#

20、39;: system("cls"); printf("請(qǐng)輸入要進(jìn)行編碼的字符串(以#結(jié)束):n"); editHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case 'c': case 'C': system("cls"); DispHCode(ht,hcd,n); printf("請(qǐng)輸入編碼(以#結(jié)束):n"); deHCode(ht,hcd,n);

21、printf("n按任意鍵返回."); getch(); system("cls"); break; case 'd': case 'D': flag=0; break; default: system("cls"); 第五章 調(diào)試結(jié)果進(jìn)入主菜單選A時(shí)的顯示結(jié)果選擇B時(shí)的顯示結(jié)果選C時(shí)的顯示結(jié)果第六章 心得體會(huì)通過這次課程設(shè)計(jì)，讓我對(duì)一個(gè)程序的數(shù)據(jù)結(jié)構(gòu)有更全面更進(jìn)一步的生疏，依據(jù)不同的需求，接受不同的數(shù)據(jù)存儲(chǔ)方式，不肯定要用棧，二叉樹等高級(jí)類型，有時(shí)用基本的一維數(shù)組，只要運(yùn)用得當(dāng)，也能達(dá)到相同的效果，甚

22、至更佳，就如這次的課程設(shè)計(jì)，通過用for的多重循環(huán)，舍棄多余的循環(huán)，提高了程序的運(yùn)行效率。在編寫這個(gè)程序的過程中，我復(fù)習(xí)了之前學(xué)的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應(yīng)用范圍，程序結(jié)構(gòu)算法等一系列的問題它使我對(duì)數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)變了看法。在這次設(shè)計(jì)過程中，體現(xiàn)出自己?jiǎn)为?dú)設(shè)計(jì)模具的力量以及綜合運(yùn)用學(xué)問的力量，體會(huì)了學(xué)以致用、突出自己勞動(dòng)成果的喜悅心情，也從中發(fā)覺自己平常學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。第七章 參考文獻(xiàn)1 徐孝凱編著，數(shù)據(jù)結(jié)構(gòu)課程試驗(yàn)，清華高校出版 2002年第一版2 張乃笑編著，數(shù)據(jù)結(jié)構(gòu)與算法，電子工業(yè)出版社 2004年10月3 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)（C語言版） 清華高校

23、出版社附錄：源程序如下：#include <stdio.h>#include <stdlib.h> /要用system函數(shù)要調(diào)用的頭文件#include<conio.h> /用getch()要調(diào)用的頭文件#include <string.h>#define N 50 /義用N表示50葉節(jié)點(diǎn)數(shù)#define M 2*N-1 /用M表示節(jié)點(diǎn)總數(shù) 當(dāng)葉節(jié)點(diǎn)數(shù)位n時(shí)總節(jié)點(diǎn)數(shù)為2n-1#define MAXSIZE 100typedef struct char data; /結(jié)點(diǎn)值 int weight; /權(quán)值 int parent; /雙親結(jié)點(diǎn) int

24、 lchild; /左孩子結(jié)點(diǎn) int rchild; /右孩子結(jié)點(diǎn)HTNode; typedef struct char cdN; /存放哈夫曼碼 int start; /從start開頭讀cd中的哈夫曼碼HCode;void CreateHT(HTNode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點(diǎn)數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /全部結(jié)點(diǎn)的相關(guān)域置初值-1 for (i=n;i<2*n-1;i+) /構(gòu)造哈夫曼

25、樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weight<min1) /若權(quán)值小于最小的左節(jié)點(diǎn)的權(quán)值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;h

26、trnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /依據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點(diǎn)結(jié)束循

27、環(huán) if (htf.lchild=c) /處理左孩子結(jié)點(diǎn) hc.cdhc.start-='0' else /處理右孩子結(jié)點(diǎn) hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開頭字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<n;i+) /輸出data中的全部數(shù)據(jù)，即A-Z printf

28、(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出全部data中數(shù)據(jù)的編碼 printf("%c",hcdi.cdk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數(shù)char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進(jìn)行編碼的字符串存入string數(shù)組中printf("n輸出編碼結(jié)果:n");for (i=0;

29、stringi!='#'i+) /#為終止標(biāo)志for (j=0;j<n;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號(hào)，相同的就輸出這個(gè)字符的編碼for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進(jìn)行譯碼的字符

30、串存入code數(shù)組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時(shí)m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)則輸出這個(gè)的data數(shù)據(jù)printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex

31、+j;void main() int n=26,i; char orz,back,flag=1; char str='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結(jié)構(gòu)體 HCode hcdN; /建立結(jié)構(gòu)體 for (i=0;i<n;i+) /把初始化的數(shù)據(jù)存入ht結(jié)