電文編碼與譯碼

1、答 辯 人張紹歡、鄒孟雷、巫安電 文 的 編 碼 與 譯 碼電 文 的 編 碼 與 譯 碼目錄目錄1.設(shè)計(jì)要求2.概念設(shè)計(jì)3.詳細(xì)設(shè)計(jì)4.調(diào)試運(yùn)行摘要摘要摘要在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視，結(jié)合時(shí)間、空間復(fù)雜度綜合考慮，哈夫曼編碼哈夫曼編碼正是一種應(yīng)用廣泛且非常正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度（WPL）最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈夫曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。電文的編碼與譯

2、碼設(shè)計(jì)要求設(shè)計(jì)要求功能需求我們項(xiàng)目所需要實(shí)現(xiàn)的功能主要有：1.從鍵盤接受一串帶有權(quán)值的節(jié)點(diǎn)，輸出相應(yīng)的哈夫曼編。2.能夠翻譯由哈夫曼編碼生成的代碼串，輸出相對(duì)應(yīng)的電文字符。第一步：第一步：選最小兩個(gè)數(shù)合選最小兩個(gè)數(shù)合并出一個(gè)樹，得到這兩個(gè)并出一個(gè)樹，得到這兩個(gè)數(shù)的權(quán)值之和作為其父節(jié)數(shù)的權(quán)值之和作為其父節(jié)點(diǎn)。點(diǎn)。第二步：重復(fù)第一步，直第二步：重復(fù)第一步，直到構(gòu)造哈夫曼樹完成。到構(gòu)造哈夫曼樹完成。1.1.構(gòu)造哈夫曼樹構(gòu)造哈夫曼樹根據(jù)已經(jīng)構(gòu)造完成的哈夫曼樹，根據(jù)已經(jīng)構(gòu)造完成的哈夫曼樹，規(guī)定左分之代表規(guī)定左分之代表0 0，右分支代，右分支代表表1 1。所以可以分別得到節(jié)點(diǎn)。所以可以分別得到節(jié)點(diǎn)值的編碼

3、，且該編碼是唯一的。值的編碼，且該編碼是唯一的。2.2.生成編碼生成編碼根據(jù)已經(jīng)生成的編碼，一根據(jù)已經(jīng)生成的編碼，一一匹配編碼值，即可實(shí)現(xiàn)一匹配編碼值，即可實(shí)現(xiàn)譯碼。譯碼。3.3.電文譯碼電文譯碼實(shí)現(xiàn)原理5A2B4C7D8E1F9G3712152136編碼：編碼：A:110 B:0001 C:001 D:111 E:01 F:0000 G:10 節(jié)點(diǎn)值節(jié)點(diǎn)值權(quán)值權(quán)值電文編碼電文編碼編碼表：編碼表：A:110 B:0001 C:001 D:111 E:01 F:0000 G:10 電文譯碼110 111 01001 0001 01 01 001 10 111 01 0001所以可知電文所以可知電

4、文110111010010001010100110111010001所得到的譯碼為：所得到的譯碼為：ADECBEECGDEB詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)2 . 創(chuàng) 建 哈 弗 曼 樹3 . 編 碼4 . 譯 碼1 . 字 符 統(tǒng) 計(jì)5 . 主 函 數(shù)定義數(shù)據(jù)結(jié)構(gòu)#include#include #include typedef char DataType; /DataType可看做可看做char#define MAXNUM 50typedef struct/定義結(jié)構(gòu)體定義結(jié)構(gòu)體 DataType data;/字符表示數(shù)據(jù)字符表示數(shù)據(jù) int weight,parent,left,right;HuffNod

5、e;typedef struct/定義編碼的儲(chǔ)存結(jié)構(gòu)定義編碼的儲(chǔ)存結(jié)構(gòu) DataType cdMAXNUM;/存放編碼位串存放編碼位串 int start;HuffCode;dataweightparentleftright創(chuàng)建哈夫曼樹/創(chuàng)建哈夫曼樹 int HuffmanCreate(HuffNode *ht) /?int i,k,n,m1,m2,p1,p2;printf(請(qǐng)輸入元素個(gè)數(shù): );scanf(%d,&n);for( i=1;int 節(jié)點(diǎn)值：,i);scanf(%c,&hti.data);printf(t 權(quán) 重: );scanf(%d,&hti.weight);第一步：森林共有

6、n個(gè)樹，將兩棵根結(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è)大小為2n-1的一維數(shù)組來存儲(chǔ)赫夫曼樹中的結(jié)點(diǎn)。 for (i=n;i2*n-1;i+) /構(gòu)造哈夫曼樹構(gòu)造哈夫曼樹 min1=min2=MAX; / lnode=rnode=0; /lnode和和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k=i-1;k+) /

7、選出每次外層循環(huán)最小權(quán)值的兩個(gè)結(jié)點(diǎn)選出每次外層循環(huán)最小權(quán)值的兩個(gè)結(jié)點(diǎn) if (htk.parent=0) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weightmin1) /比比min1小時(shí)小時(shí) min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) /比比min1大，比大，比min2小小 min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.w

8、eight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之兩個(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)父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn) 編碼void Encoding(HuffNode ht,HuffCode hcd,int n) HuffCode d; int i,k,f,c; for (i=1;i=n;i+)/對(duì)構(gòu)造的哈夫曼樹的所有節(jié)點(diǎn)循環(huán)對(duì)構(gòu)造的哈夫曼樹的所有節(jié)點(diǎn)循環(huán) d.start=n+1; c=i; f=hti.parent; whi

9、le(f !=0) if(htf.left=c) d.cd-d.start=0; else d.cd-d.start=1; c=f; f=htf.parent; hcdi=d; printf(輸出哈弗曼編碼：輸出哈弗曼編碼：n); for(i=1;i=n;i+) printf(%c:,hti.data); for(k=hcdi.start;k=n;k+) printf(%c,hcdi.cdk);printf(n);譯碼void Decoding(HuffNode ht,HuffCode hcd,int n)int f,m,k;DataType c,ch200;/ch數(shù)組存儲(chǔ)接收到的電文數(shù)組存儲(chǔ)

10、接收到的電文 printf(請(qǐng)輸入電文請(qǐng)輸入電文(0或或1），以），以#結(jié)束：結(jié)束： n);c=getchar();/ k=1;while(c!=#)chk=c;c=getchar();k=k+1;m=k;f=2*n-1;k=1;printf(輸出哈弗曼譯碼：輸出哈弗曼譯碼： n);while(km)while (htf.left !=0)if(chk=0) f=htf.left;if(chk=1)f=htf.right;k+;printf(%c,htf.data);f = 2*n - 1;printf(n); 主函數(shù)int main(int argc,char *argv) int n,select,flag=0; HuffNode ht2*MAXNUM;/? HuffCode hcdMAXNUM;/? while(1) printf(t 請(qǐng)選擇功能（輸入請(qǐng)選擇功能（輸入1-4數(shù)字）數(shù)字）n); printf(t1 建立哈弗曼樹建立哈弗曼樹n); printf(t2 編碼編碼n); printf(t3 譯碼譯碼n); printf(t4 退出退出n);scanf(%d,&select);if(select!=1&select!=4&flag=0)printf(請(qǐng)先建立哈弗曼樹請(qǐng)先建立哈弗曼樹n);continue; f