數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--電文編碼譯碼(哈夫曼編碼)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：15 大?。?41.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩14頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　計算機與信息學院　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　設(shè)計：電文的編碼譯碼　　姓名： 　　專業(yè)：2012級數(shù)學與應(yīng)用數(shù)學<

2、;p>　　學號： 　　目錄　　一、需求分析3　　二、設(shè)計要求3　　三、概要設(shè)計4</

3、b>　　① 哈夫曼樹的建立4　?、?哈夫曼編碼5　?、?代碼文件的譯碼5　　四、詳細設(shè)計5　?、僮址y(tǒng)計5</b&

4、gt;　?、诠蚵鼧涞乃惴?　?、芄蚵g碼7　?、葜骱瘮?shù)7　　五、調(diào)試8　　附錄10&

5、lt;/b>　　電文的曼編碼譯碼　　一、需求分析　　在當今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一

6、種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈夫曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫

7、曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是哈夫曼編碼。哈夫曼譯碼輸入字符串可以把它編譯成二進制代碼，輸入二進制代碼時可以編譯成字符串。　　二、設(shè)計要求　　對輸入的一串

8、電文字符實現(xiàn)哈夫曼編碼，再對哈夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為∑WiLi。若將此對應(yīng)到二叉樹上，Wi為葉結(jié)點的權(quán)，Li為根結(jié)點到葉結(jié)點的路徑長度。那么，∑WiLi恰好為二叉樹上帶權(quán)路徑

9、長度。因此，設(shè)計電文總長最短的二進制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。設(shè)計實現(xiàn)的功能： (1) 哈夫曼樹的建立； (2) 哈夫曼編碼的生成； (3) 編碼文件的譯碼。 　　三、概要設(shè)計　　哈夫曼編\譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈

10、夫曼編碼后進行譯碼。　　在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0、1組成的二進制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點到每個葉子節(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點對應(yīng)字符的編碼，稱之為哈夫曼編碼。　　最簡單的二進制編碼方式是等長編碼。若采用不等長編碼，讓出現(xiàn)頻率高的字符具有較

11、短的編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。哈夫曼樹課用于構(gòu)造使電文的編碼總長最短的編碼方案。　　設(shè)計包含的幾個方面：　　① 哈夫曼樹的建立　　赫夫曼樹的建立由赫夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點的二叉樹。算法的第二步是：將當前森

12、林中的兩棵根結(jié)點權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結(jié)點。顯然要進行n－1次合并，所以共產(chǎn)生n－1個新結(jié)點，它們都是具有兩個孩子的分支結(jié)點。由此可知，最終求得的哈夫曼樹中一共有2n－1個結(jié)點，其中n個結(jié)點是初始森林的n個孤立結(jié)點。并且哈夫曼樹中沒有度數(shù)為1的分支結(jié)點。我們可以利用一個大小為2n--1的一維數(shù)組來存儲赫夫曼樹中的結(jié)點。定義的結(jié)構(gòu)體類型如下：<p&g

13、t;　　typedef struct　　{　　char data; //結(jié)點字符　　int weight; //權(quán)值　　int parent;

14、 //雙親結(jié)點　　int lchild; //左孩子結(jié)點　　int rchild; //右孩子結(jié)點　　}HTNode;　　② 哈夫曼編碼 <

15、/b>　　要求電文的哈夫曼編碼，必須先定義哈夫曼編碼類型，根據(jù)設(shè)計要求和實際需要定義的類型如下： 　　typedet struct { 　　char cd[N]; // 存放編碼的數(shù)組　　int start; //從start 開始讀cd中的哈夫曼編碼</p

16、>　　}Hcode; // 編碼結(jié)構(gòu)體類型 　　③ 代碼文件的譯碼 　　譯碼的基本思想是：讀文件中編碼，并與原先生成的哈夫曼編碼表比較，遇到相等時，即取出其對應(yīng)的字符存入一個新串中。　　四、詳細設(shè)計<

17、b>　　①字符統(tǒng)計　　int jsq(char *s,int cnt[],char str[])　　{char *p;　　int i,j,k;　　for(i=1;i<=256;i++)

18、;　　cnt[i]=0;　　for(p=s;*p!='\0';p++)　　{　　k=*p;　　cnt[

19、k]++;　　}　　j=0;　　for(i=1,j=0;i<=256;i++)　　if(cnt[i]!=0)

20、　{　　j++;　　}　　return j;　　}<

21、b>　?、诠蚵鼧涞乃惴?lt;/b>　　void CreateHT(HTNode ht[],int n,char str[],int cn[]) //創(chuàng)建哈夫曼樹函數(shù)　　{for(int input=1;input<=256;input++)

22、{　　str[input]=input;　　}　　int l=0;　　for(int output=1;output<=256;output++)

23、　　{　　if(cn[output] !=0)　　{ht[l].data=str[output]; //按字母順序?qū)⒊霈F(xiàn)的字母依次存入數(shù)組ht[]　　ht[l].weight=cn[outpu

24、t];　　l++;　　}　　}　　int i,k,lnode,rnode;　　int min1,min2;</

25、p>　　for (i=0;i<2*n-1;i++) 　　ht[i].parent=ht[i].lchild=ht[i].rchild=0; //所有結(jié)點的相關(guān)域置初值0　　for (i=n;i<2*n-1;i++) //構(gòu)造哈夫曼樹<

26、;p>　　{　　min1=min2=MAX; //int的范圍是-32768-32767　　lnode=rnode=0; //lnode和rnode記錄最小權(quán)值的兩個結(jié)點位置　　for (k=0;k<

27、=i-1;k++) //選出每次外層循環(huán)最小權(quán)值的兩個結(jié)點　　{　　if (ht[k].parent==0) //只在尚未構(gòu)造二叉樹的結(jié)點中查找　　{<p&

28、gt;　　if (ht[k].weight<min1) //比min1小時　　{　　min2=min1;rnode=lnode;　　min1=ht[k].weight;lnode=k;　　}

29、　　else if (ht[k].weight<min2) //比min1大，比min2小　　{　　min2=ht[k].weight;rnode=k;　　}&l

30、t;/p>　　}　　}　　ht[lnode].parent=i;ht[rnode].parent=i; //兩個最小節(jié)點的父節(jié)點是i　　ht[i].weight=ht[lnode]

31、.weight+ht[rnode].weight; //兩個最小節(jié)點的父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和　　ht[i].lchild=lnode;ht[i].rchild=rnode; //父節(jié)點的左節(jié)點和右節(jié)點　　}

32、;　　}　?、酃蚵幋a　　void CreateHCode(HTNode ht[],HCode hcd[],int n)　　{　　int i,p,c;

33、　　HCode hc;　　for (i=0;i<n;i++) //根據(jù)哈夫曼樹求哈夫曼編碼　　{　　hc.start=n; //初始

34、位置　　c=i; //從葉子結(jié)點ht[i]開始上溯　　p=ht[i].parent;　　while (p!=0) //循序直到樹根結(jié)點結(jié)束循環(huán)　　{</

35、b>　　hc.cd[hc.start--]=(ht[p].lchild)==c?'0':'1'; //左孩子記為0，右孩子記為1　　c=p;　　p=ht[p].parent;

36、 //與上句c=i;p=ht[i].parent同義，促進循環(huán)　　}　　hc.start++; //start指向哈夫曼編碼hc.cd[]中最開始字符　　hcd[i]=hc;</p&

37、gt;　　}　　}　?、芄蚵g碼　　void deHCode(HTNode ht[],HCode hcd[],int n,char str[]) //譯碼函數(shù)<

38、/p>　　{　　printf("輸出譯碼結(jié)果為:\n");　　int i,j,k,x,m=0;　　char code[MAX];　　for (i=0;i<MAX;i++)

39、 　　for (j=0;j<n;j++)　　if(str[i]==ht[j].data) //循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼　　{　　for (k=hcd

40、[j].start;k<=n;k++)　　{　　code[m]=hcd[j].cd[k]; //將輸出的編碼賦值到數(shù)組中　　m++;　　}<

41、/p>　　break; //輸出完成后跳出當前for循環(huán)　　}　　code[m]='#';　　//把要進行譯碼的字符串存入code數(shù)組中　　while(c

42、ode[0]!='#')　　for (i=0;i<n;i++)　　{　　m=0; //m為想同編碼個數(shù)的計數(shù)器　　for (k=hcd[i].start

43、,j=0;k<=n;k++,j++) //j為記錄所存儲這個字符的編碼個數(shù)　　{　　if(code[j]==hcd[i].cd[k]) //當有相同編碼時m值加1　　m++;&l

44、t;p>　　}　　if(m==j) //當輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)　　{　　printf("%c",ht[i]

45、.data);　　for(x=0;code[x-j]!='#';x++) //把已經(jīng)使用過的code數(shù)組里的字符串刪除　　{　　code[x]=code[x+j]; //刪除j個數(shù)，往前移動j位</p&g

46、t;　　}　　}　　}　　printf("\n");　　}

47、　?、葜骱瘮?shù)　　void main()　　{　　char st[MAX],sst[MAX];　　int cn[257];<b&

48、gt;　　int n,i;　　printf("請輸入字符串(任意字符):\n");　　gets(st);　　n=jsq(st,cn,sst);　　////////////////////////

49、///99　　for(i=0;i<99;i++)　　sst[i]=st[i];　　//////////////////////////////////　　HTNode ht[M];　　HCode hcd[N];</p&

50、gt;　　CreateHT(ht,n,st,cn);　　CreateHCode(ht,hcd,n);　　outputHCode(ht,hcd,n);　　editHCode(ht,hcd,n,sst);　　deHCode(ht,hcd,n,sst);

51、　　}　　五、調(diào)試　　輸出哈夫曼編碼　　輸出編碼結(jié)果　　輸出

52、譯碼結(jié)果　　附錄　　源程序　　#include <stdio.h>　　#include <string.h> //gets()函數(shù)需

53、要　　#define N 256 //義用N表示50葉節(jié)點數(shù)　　#define M 2*N-1 //用M表示節(jié)點總數(shù) 當葉節(jié)點數(shù)位n時總節(jié)點數(shù)為2n-1　　#define MAX 32767　　typedef st

54、ruct　　{　　char data; //結(jié)點字符　　int weight; //權(quán)值　　int parent; //雙親結(jié)點<

55、/p>　　int lchild; //左孩子結(jié)點　　int rchild; //右孩子結(jié)點　　}HTNode;　　///////////////////////////

56、 　　typedef struct　　{　　char cd[N]; //存放哈夫曼碼　　int start; //從start開始讀cd中的哈夫曼碼<

57、/p>　　}HCode;　　///////////////////////////////////　　int jsq(char *s,int cnt[],char str[])　　{char *p;</p

58、>　　int i,j,k;　　for(i=1;i<=256;i++)　　cnt[i]=0;　　for(p=s;*p!='\0';p++)　　{&l

59、t;/p>　　k=*p;　　cnt[k]++;　　}　　j=0;　　for(i=1,j=0;

60、i<=256;i++)　　if(cnt[i]!=0)　　{　　j++;　　}　　return

61、 j;　　}　　///////////////////////////////////////////////////　　void CreateHT(HTNode ht[],int n,char str[],int cn[])

62、 //創(chuàng)建哈夫曼樹函數(shù)　　{for(int input=1;input<=256;input++)　　{　　str[input]=input;　　}

63、　　int l=0;　　for(int output=1;output<=256;output++)　　{　　if(cn[output] !=0)　　{ht[l].data=str[outp

64、ut]; //按字母順序?qū)⒊霈F(xiàn)的字母依次存入數(shù)組ht[]　　ht[l].weight=cn[output];　　l++;　　}&l

65、t;b>　　}　　int i,k,lnode,rnode;　　int min1,min2;　　for (i=0;i<2*n-1;i++) 　　ht[i].parent=ht[i].lchild=ht[i].rchild=0;

66、 //所有結(jié)點的相關(guān)域置初值0　　for (i=n;i<2*n-1;i++) //構(gòu)造哈夫曼樹　　{　　min1=min2=MAX; //int的范圍是-32768-32767&

67、lt;p>　　lnode=rnode=0; //lnode和rnode記錄最小權(quán)值的兩個結(jié)點位置　　for (k=0;k<=i-1;k++) //選出每次外層循環(huán)最小權(quán)值的兩個結(jié)點　　{　　if (ht[k

68、].parent==0) //只在尚未構(gòu)造二叉樹的結(jié)點中查找　　{　　if (ht[k].weight<min1) //比min1小時　　{

69、　min2=min1;rnode=lnode;　　min1=ht[k].weight;lnode=k;　　}　　else if (ht[k].weight<min2) //比min1大，比min2小

70、{　　min2=ht[k].weight;rnode=k;　　}　　}　　}　　ht[lnode

71、].parent=i;ht[rnode].parent=i; //兩個最小節(jié)點的父節(jié)點是i　　ht[i].weight=ht[lnode].weight+ht[rnode].weight; //兩個最小節(jié)點的父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和　　ht[i].lchild=lnode;ht[i].rchild=rno

72、de; //父節(jié)點的左節(jié)點和右節(jié)點　　}　　}　　//////////////////////////////////////////////////////　　v

73、oid CreateHCode(HTNode ht[],HCode hcd[],int n)　　{　　int i,p,c;　　HCode hc;　　for (i=0;i<n;i++)

74、 //根據(jù)哈夫曼樹求哈夫曼編碼　　{　　hc.start=n; //初始位置　　c=i; //從葉子結(jié)點ht[i]開始上溯

75、　　p=ht[i].parent;　　while (p!=0) //循序直到樹根結(jié)點結(jié)束循環(huán)　　{　　hc.cd[hc.start--]=(ht[p].lchild)==c?'0':'1'

76、;; //左孩子記為0，右孩子記為1　　c=p;　　p=ht[p].parent; //與上句c=i;p=ht[i].parent同義，促進循環(huán)　　}</b&g

77、t;　　hc.start++; //start指向哈夫曼編碼hc.cd[]中最開始字符　　hcd[i]=hc;　　}　　}</p&

78、gt;　　/////////////////////////////////////////////////　　void outputHCode(HTNode ht[],HCode hcd[],int n) //輸出哈夫曼編碼的列表　　{<

79、b>　　int i,k;　　printf(" 輸出哈夫曼編碼:\n"); 　　for (i=0;i<n;i++) //輸出data中的所有數(shù)據(jù)，　　{</p

80、>　　printf(" %c:\t",ht[i].data); 　　for (k=hcd[i].start;k<=n;k++) //輸出所有data中數(shù)據(jù)的編碼　　{

81、　　printf("%c",hcd[i].cd[k]); //從初最開始的字符起輸出　　}　　printf("\n");　　}</p

82、>　　}　　////////////////////////////////////////////　　void editHCode(HTNode ht[],HCode hcd[],int n,char str[]) //編碼函數(shù)　　{int

83、 i,j,k;　　printf("\n輸出編碼結(jié)果:\n");　　for (i=0;i<MAX;i++) 　　for (j=0;j<n;j++)　　if(str[i]==ht[j].data)

84、 //循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼　　{　　for (k=hcd[j].start;k<=n;k++)　　{　　printf("%c"

85、;,hcd[j].cd[k]);　　}　　break; //輸出完成后跳出當前for循環(huán)　　}　　printf("\n");</p&g

86、t;　　}　　/////////////////////////////////////////////　　void deHCode(HTNode ht[],HCode hcd[],int n,char str[]) //譯碼函數(shù)<b&g

87、t;　　{　　printf("輸出譯碼結(jié)果為:\n");　　int i,j,k,x,m=0;　　char code[MAX];　　for (i=0;i<MAX;i++)

88、　　for (j=0;j<n;j++)　　if(str[i]==ht[j].data) //循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼　　{　　for (k=hcd[j].start;k<=n;k++)&l

89、t;/p>　　{　　code[m]=hcd[j].cd[k]; //將輸出的編碼賦值到數(shù)組中　　m++;　　}　　break

90、; //輸出完成后跳出當前for循環(huán)　　}　　code[m]='#';　　//把要進行譯碼的字符串存入code數(shù)組中　　while(code[0]!='#')<

91、/p>　　for (i=0;i<n;i++)　　{　　m=0; //m為想同編碼個數(shù)的計數(shù)器　　for (k=hcd[i].start,j=0;k<=n;k++,j++)

92、 //j為記錄所存儲這個字符的編碼個數(shù)　　{　　if(code[j]==hcd[i].cd[k]) //當有相同編碼時m值加1　　m++;　　}</

93、b>　　if(m==j) //當輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)　　{　　printf("%c",ht[i].data);<p

94、>　　for(x=0;code[x-j]!='#';x++) //把已經(jīng)使用過的code數(shù)組里的字符串刪除　　{　　code[x]=code[x+j]; //刪除j個數(shù)，往前移動j位

95、}　　}　　}　　printf("\n");　　}　　///////////

96、/////////////////////////////　　void main()　　{　　char st[MAX],sst[MAX];　　int cn[257];　　in

97、t n,i;　　printf("請輸入字符串(任意字符):\n");　　gets(st);　　n=jsq(st,cn,sst);　　///////////////////////////99&l

98、t;/p>　　for(i=0;i<99;i++)　　sst[i]=st[i];　　//////////////////////////////////　　HTNode ht[M];　　HCode hcd[N];&l

99、t;p>　　CreateHT(ht,n,st,cn);　　CreateHCode(ht,hcd,n);　　outputHCode(ht,hcd,n);　　editHCode(ht,hcd,n,sst);　　deHCode(ht,hcd,n,sst);</p&

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--電文編碼譯碼(哈夫曼編碼)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--電文編碼譯碼(哈夫曼編碼)

文檔簡介

溫馨提示

最新文檔

評論

免費下載