1、c語言 - 哈夫曼編碼實(shí)驗(yàn)報(bào)告福建工程學(xué)院課程設(shè)計(jì)課程：數(shù)據(jù)結(jié)構(gòu)題目：哈夫曼編碼和譯碼專業(yè)：信息管理信息系統(tǒng)班級(jí)：1002 班座號(hào)：15 號(hào)姓名：林左權(quán)2011 年6 月27 日2實(shí)驗(yàn)題目：哈夫曼編碼和譯碼一、要解決的問題利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼 （復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道） ，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。二、算法基本思想描述：根據(jù)給定的字符和其中每個(gè)字符的頻度 ,構(gòu)造哈夫饅樹,并輸出字符集中每個(gè)字符的哈夫曼編碼 .將給定的字

2、符串根據(jù)其哈夫曼編碼進(jìn)行編碼 ,并進(jìn)行相應(yīng)的譯碼 .三、設(shè)計(jì)1. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)（1）哈夫曼樹的表示設(shè)計(jì)哈夫曼樹的結(jié)構(gòu)體（ htnode ），其中包含權(quán)重、左右孩子、父母和要編碼的字符。用這個(gè)結(jié)構(gòu)體（ htnode ）定義個(gè)哈夫曼數(shù)組（ hfmt ）。迷宮定義如下：typedef structint weight;int lchild;int rchild;int parent;char key;htnode;typedef htnode hfmtmaxlen;（ 2）對(duì)原始字符進(jìn)行編碼初始化哈夫曼樹（ inithfmt ）。從終端讀入字符集大小 n，以及 n 個(gè)字符和 n 個(gè)權(quán)值，建立哈夫曼

3、樹。并顯示出每個(gè)字符的編碼。31.void inithfmt(hfmt t)/對(duì)結(jié)構(gòu)體進(jìn)行初始化2.void inputweight(hfmt t)/輸入函數(shù)3.void selectmin(hfmtt,int i,int*p1,int*p2)/ 選中兩個(gè)權(quán)值最小的函數(shù)4.void creathfmt(hfmt t)/創(chuàng)建哈夫曼樹的函數(shù)5.void phfmnode(hfmt t)/ 對(duì)字符進(jìn)行初始編碼（ 3）對(duì)用戶輸入的字符進(jìn)行編碼void encoding(hfmt t)/對(duì)用戶輸入的電文進(jìn)行編碼char r1000;/用來存儲(chǔ)輸入的字符串int i,j;printf(nn請(qǐng)輸入需要編碼的

4、字符:);gets(r);printf(編碼結(jié)果為 :);for(j=0;rj!=0;j+)for(i=0;in;i+)if(rj=ti.key)hfmtpath(t,i,j);printf(n);（ 4）對(duì)用戶輸入的字符進(jìn)行編碼void decoding(hfmt t)/對(duì)用戶輸入的密文進(jìn)行譯碼char r100;int i,j,len;j=2*n-2;/j初始從樹的根節(jié)點(diǎn)開始printf(nn請(qǐng)輸入需要譯碼的字符串:);gets(r);len=strlen(r);printf(譯碼的結(jié)果是 :);for(i=0;ilen;i+)if(ri=0)j=tj.lchild;if(tj.lchil

5、d=-1)printf(%c,tj.key);j=2*n-2;else if(ri=1)4j=tj.rchild;if(tj.rchild=-1)printf(%c,tj.key);j=2*n-2;printf(nn);四、源程序清單：#include #include #include #define maxlen 100typedef structint weight;int lchild;int rchild;int parent;char key;htnode;typedef htnode hfmtmaxlen;int n;void inithfmt(hfmt t)/對(duì)結(jié)構(gòu)體進(jìn)行初始化

6、int i;printf(n);printf(-n);printf(*輸入?yún)^(qū)*n);printf(n請(qǐng)輸入 n=);scanf(%d,&n);getchar();for(i=0;i2*n-1;i+)/對(duì)結(jié)構(gòu)體進(jìn)行初始化ti.weight=0;ti.lchild=-1;5ti.rchild=-1;ti.parent=-1;printf(n);void inputweight(hfmt t)/輸入函數(shù)int w;/w表示權(quán)值int i;char k;/k表示獲取的字符for(i=0;in;i+)printf(請(qǐng)輸入第 %d個(gè)字符 :,i+1);scanf(%c,&k);getchar();ti.k

7、ey=k;printf(請(qǐng)輸入第 %d個(gè)字符的權(quán)值 :,i+1);scanf(%d,&w);getchar();ti.weight=w;printf(n);void selectmin(hfmt t,int i,int *p1,int *p2)/選中兩個(gè)權(quán)值最小的函數(shù)long min1=999999;long min2=999999;int j;for(j=0;jtj.weight)min1=tj.weight;*p1=j;for(j=0;jtj.weight & j!=(*p1)/注意 j!=(*p1)min2=tj.weight;*p2=j;6void creathfmt(hfmt t)/

8、創(chuàng)建哈夫曼樹的函數(shù)int i,p1,p2;inithfmt(t);inputweight(t);for(i=n;i2*n-1;i+)selectmin(t,i-1,&p1,&p2);tp1.parent=i;tp2.parent=i;ti.lchild=p1;ti.rchild=p2;ti.weight=tp1.weight+tp2.weight;void printhfmt(hfmt t)/打印哈夫曼樹int i;printf(-n);printf(*哈夫曼編數(shù)結(jié)構(gòu) :*n);printf(tt 權(quán)重 t 父母 t 左孩子 t 右孩子 t 字符 t); for(i=0;i2*n-1;i+)p

9、rintf(n);printf(tt%dt%dt%dt%dt%c,ti.weight,ti.parent,ti.lchild,ti.rchild,ti.key);printf(n-n);printf(nn);void hfmtpath(hfmt t,int i,int j)/編碼的重要哈夫曼樹路徑遞歸算法int a,b;a=i;b=j=ti.parent;if(tj.parent!=-1)7i=j;hfmtpath(t,i,j);if(tb.lchild=a)printf(0);elseprintf(1);void phfmnode(hfmt t)/對(duì)字符進(jìn)行初始編碼int i,j,a;pri

10、ntf(n-n);printf(*哈夫曼編碼*);for(i=0;in;i+)j=0;printf(n);printf(tt%ct,ti.key,ti.weight);hfmtpath(t,i,j);printf(n-n);void encoding(hfmt t)/對(duì)用戶輸入的電文進(jìn)行編碼char r1000;/用來存儲(chǔ)輸入的字符串int i,j;printf(nn請(qǐng)輸入需要編碼的字符:);gets(r);printf(編碼結(jié)果為 :);for(j=0;rj!=0;j+)for(i=0;in;i+)if(rj=ti.key)hfmtpath(t,i,j);printf(n);8void decoding(hfmt t)/對(duì)用戶輸入的密文進(jìn)行譯碼char r100;int i,j,len;j=2*n-2;/j初始從樹的根節(jié)點(diǎn)開始printf(nn請(qǐng)輸入需要譯碼的字符串:);gets(r);len=strlen(r);printf(譯碼的結(jié)果是 :);for(i=0;ilen;i+)if(ri=0)j=tj.lchild;if(tj.lchild=-1)printf(%c,tj.key);j=2*n-2;else if(ri=1)j=tj.rchild;i