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

2、的字符串根據其哈夫曼編碼進行編碼,并進行相應的譯碼.三、設計1.數據結構的設計（1）哈夫曼樹的表示設計哈夫曼樹的結構體（htnode），其中包含權重、左右孩子、父母和要編碼的字符。用這 個結構體（htnode）定義個哈夫曼數組（hfmt）。迷宮定義如下：typedef structint weight;int lchild;int rchild;int pare nt;char key;ht no de;typedef htnode hfmtMAXLEN;（2）對原始字符進行編碼初始化哈夫曼樹（inithfmt ）。從終端讀入字符集大小n，以及n個字符和n個權值， 建立哈夫曼樹。并顯示出每個字

3、符的編碼。1. void in ithfmt(hfmt t)對結構體進行初始化2. void inputweight(hfmt t)/ 輸入函數3. void selectmin(hfmt t,int i,int *p1,int *p2) 選中兩個 權值最小的函數4. void creathfmt(hfmt t)/創建哈夫曼樹的函數5. void phfmnode(hfmt t)/對字符進行初始編碼(3) 對用戶輸入的字符進行編碼void en codi ng(hfmt t)/對用戶輸入的電文進行編碼char r1000;用來存儲輸入的字符串int i,j;printf(nn請輸入需要編碼的字

4、符：)；gets(r);printf(編碼結果為:);for(j=0;rj!=0;j+)for(i=0;i n;i+)if(rj=ti.key)hfmtpath(t,i,j);prin tf(n);(4) 對用戶輸入的字符進行編碼void decodi ng(hfmt t)/ 對用戶輸入的密文進行譯碼char r100;int i,j,le n;j=2* n-2;/j初始從樹的根節點開始printf(nn請輸入需要譯碼的字符串:);gets(r);len=strle n(r);printf( 譯碼的結果是:);for(i=0;ile n;i+)if(ri=0)j=tj.lchild;if(tj

5、.lchild=-1)prin tf(%c,tj.key);j=2* n-2;else if(ri=1)j=tj.rchild;if(tj.rchild=-1)prin tf(%c,tj.key); j=2* n-2;prin tf(nn);四、源程序清單：#i nclude #i nclude #include #defi ne MAXLEN 100 typedef struct int weight; int lchild; int rchild;int pare nt; char key;ht no de;typedef htnode hfmtMAXLEN;int n;void in i

6、thfmt(hfmt t) int i;prin tf(n);對結構體進行初始化prin tf(- printf(*n); printf(n請輸入 n=);scan f(%d,&n); getchar();for(i=0;i2* n-1;i+) *對結構體進行初始化n);輸ti.weight=O; ti.lchild=-1;ti.rchild=-1;ti.pare nt=-1;prin tf(n);void in putweight(hfmt t)/輸入函數int w;/w表示權值int i;char k;/k表示獲取的字符for(i=0;i tj.weight)min 1=tj.weight

7、;*p1=j;for(j=0;jtj.weight & j!=(*p1)/注意 j!=(*p1)min 2=tj.weight;*p2=j;void creathfmt(hfmt t)創建哈夫曼樹的函數int i,p1,p2;in ithfmt(t);in putweight(t);for(i=n;i2* n-1;i+)selectmi n(t,i-1,&p1,&p2);tp1.pare nt=i;tp2.pare nt=i;ti.lchild=p1;ti.rchild=p2;ti.weight=tp1.weight+tp2.weight;打印哈夫曼樹n); void prin thfmt(h

8、fmt t)/ int i;printf(printf( *n);printf（tt權重t父母t左孩子t右孩子t字符t）;for(i=0;i2* n-1;i+)prin tf(n);prin tf(tt%dt%dt%dt%dt%c,ti.weight,ti.pare nt,ti.lchild,ti.rchild ,ti.key);printf(n);prin tf(nn);void hfmtpath(hfmt t,i nt i,i nt j) int a,b; a=i;b=j=ti.pare nt;if(tj.pare nt!=-1)n編碼的重要哈夫曼樹路徑遞歸算法i=j； hfmtpath(

9、t,i,j);if(tb.lchild=a)prin tf(0);elseprin tf(1);void phfm no de(hfmt t)/對字符進行初始編碼int i,j,a;printf(n);printf( * *);nfor(i=0;i n ;i+)j=0;prin tf(n);prin tf(tt%ct,ti.key,ti.weight); hfmtpath(t,i,j);prin tf(n)；nvoid en codi ng(hfmt t)/對用戶輸入的電文進行編碼char r1000;int i,j;prin tf(nngets(r);用來存儲輸入的字符串請輸入需要編碼的字符

10、：);printf(編碼結果為:);for(j=0;rj!=0;j+)for(i=0;i n;i+)if(rj=ti.key)hfmtpath(t,i,j);prin tf(n);void decodi ng(hfmt t)/ 對用戶輸入的密文進行譯碼 char r100;初始從樹的根節點開始請輸入需要譯碼的字符串：);int i,j,le n;j=2* n-2;/j譯碼的結果是:);i=0;ile n;i+)prin tf(nn gets(r); len=strle n(r); printf( for if(ri=0) j=tj.lchild; if(tj.lchild=-1) prin t

11、f(%c,tj.key); j=2* n-2;else if(ri=1)j=tj.rchild;if(tj.rchild=-1)prin tf(%c,tj.key); j=2* n-2;ntf(nn); priI13int maiintn()i,j; hfmt ht; char flag; printf( printf( printf( printf( printf( prin tf(|I *|I *|n);信管1002-林左權-15號|n);|n);哈夫曼編碼課程設計|n);|n);設計完成時間:2011/6/27|n);|n);printf( creathfmt(ht); prin thf

12、mt(ht); phfm no de(ht);18prin tf(nn);printf( *&譯 碼 & 退*);printf(n【1】編碼t【2】t譯碼t【0】退出);prin tf(n您的選擇：);flag=getchar(); getchar();while(flag!=0) if(flag=1)en cod in g(ht); else if(flag=2) decod in g(ht); elseprintf(您的輸入有誤，請重新輸入prin tf(n*n);編碼&譯碼 &退*)prin tf(n prin tf(n flag=getchar(); getchar();1】編碼t【2

13、】t譯碼t【0】退出); 您的選擇：);prin tf(nn);printf(*n歡迎使用林左權的哈夫曼編碼系*n);printf(n);system(pause);五、測試數據及測試結果：例如：! f言菅丄盹2林左權一巧號!:M*畀-住咒|!哈夫曼編碼課程設計! | :MiMKXNWKXiMKXaOtKHatKiMKWaOE ；設計完成時間吆陌血？ !MKMXXmtXKMKMXKmCMiMMBillOiM： MXM屛XX 刖 - 審K 耳凰 J4 何且耳 *MM 良 K 耳 K請輸人“=4耿書抹睪輛權值汐I星那i冃胸請賴H -值 &勺 - ! J3J- 3 3 spm 入入 嚴1 42 土冃青A14 44測主冃青諾權值 C; U serslzqDe s ktopXBp 夫曼詢豈 ex 已權？ S 2 4H子S一一右HFS莖T ; T裁母夫父 5 4-4哈乂符字abedie118111 IWlifiiiHWiilrfaii :MKKaeilCKtMIMElrfjMK； 哈夫員編碼0 C