C語(yǔ)言哈夫曼編碼實(shí)驗(yàn)報(bào)告

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

2、據(jù)結(jié)構(gòu)的設(shè)計(jì)哈夫曼樹(shù)的表示設(shè)計(jì)哈夫曼樹(shù)的結(jié)構(gòu)體(htnode),其中包含權(quán)重、左右孩子、父母和要編碼的字符。用這個(gè)結(jié)構(gòu)體(htnode)定義個(gè)哈夫曼數(shù)組(hfmt)。迷宮定義如下：typedefstructintweight;intlchild;intrchild;intparent;charkey;htnode;typedefhtnodehfmtMAXLEN;對(duì)原始字符進(jìn)行編碼初始化哈夫曼樹(shù)(inithfmt)。從終端讀入字符集大小n,以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)。并顯示出每個(gè)字符的編碼。voidinithfmt(hfmtt)對(duì)結(jié)構(gòu)體進(jìn)行初始化voidinputweight(hfmt

3、t)輸入函數(shù)voidselectmin(hfmtt,inti,int*p1,int*p2)選中兩個(gè)權(quán)值最小的函數(shù)voidcreathfmt(hfmtt)創(chuàng)建哈夫曼樹(shù)的函數(shù)voidphfmnode(hfmtt)對(duì)字符進(jìn)行初始編碼對(duì)用戶(hù)輸入的字符進(jìn)行編碼voidencoding(hfmtt)/對(duì)用戶(hù)輸入的電文進(jìn)行編碼charr1000;/用來(lái)存儲(chǔ)輸入的字符串inti,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);

4、對(duì)用戶(hù)輸入的字符進(jìn)行編碼voiddecoding(hfmtt)/對(duì)用戶(hù)輸入的密文進(jìn)行譯碼charr100;inti,j,len;j=2*n-2;/j初始從樹(shù)的根節(jié)點(diǎn)開(kāi)始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;elseif(ri=1)j=tj.rchild;if(tj.rchild=-1)printf(%c,tj.key);j=2*n-2;printf(nn);

5、四、源程序清單：#include#include#include#defineMAXLEN100typedefstructintweight;intlchild;intrchild;intparent;charkey;htnode;typedefhtnodehfmtMAXLEN;intn;voidinithfmt(hfmtt)/對(duì)結(jié)構(gòu)體進(jìn)行初始化inti;printf(n);printf(n);printf(*輸入?yún)^(qū)*n);printf(n請(qǐng)輸入n二)；scanf(%d,&n);getchar()；for(i=0;i2*n-l;i+)/對(duì)結(jié)構(gòu)體進(jìn)行初始化ti.weight=0;ti.lchil

6、d=-1;ti.rchild=-1;ti.parent=-1;printf(n);voidinputweight(hfmtt)/輸入函數(shù)intw;/w表示權(quán)值inti;chark;/k表示獲取的字符for(i=0;itj.weight)min1=tj.weight;*p1=j;for(j=0;j二i;j+)/選擇次小權(quán)值字符的下標(biāo)還回if(tj.parent=-1)if(min2tj.weight&j!=(*pl)/主意j!=(*pl)min2=tj.weight;*p2=j;voidcreathfmt(hfmtt)/創(chuàng)建哈夫曼樹(shù)的函數(shù)inti,p1,p2;inithfmt(t);inputw

7、eight(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;voidprinthfmt(hfmtt)/打印哈夫曼樹(shù)inti;printf(n);printf(*哈夫曼編數(shù)結(jié)木勾：*n)printf(tt權(quán)重t父母t左孩子t右孩子t字符t);for(i=0;i2*n-1;i+)printf(n);printf(tt%dt%dt%dt%dt%c,ti.weight,ti.parent,ti

8、.lchild,ti.rchild,ti.key);printf(nn)7printf(nn);voidhfmtpath(hfmtt,inti,intj)/編碼的重要哈夫曼樹(shù)路徑遞歸算法inta,b;a=i;b=j=ti.parent;if(tj.parent!=-1)i=j;hfmtpath(t,i,j);if(tb.lchild=a)printf(0);elseprintf(1);voidphfmnode(hfmtt)/對(duì)字符進(jìn)行初始編碼inti,j,a;printf(nn)printf(* *);for(i=0;in;i+)j=0;printf(n);printf(tt%ct,ti.ke

9、y,ti.weight);hfmtpath(t,i,j);printf(nvoidencoding(hfmtt)/對(duì)用戶(hù)輸入的電文進(jìn)行編碼charr1000;/用來(lái)存儲(chǔ)輸入的字符串inti,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);voiddecoding(hfmtt)/對(duì)用戶(hù)輸入的密文進(jìn)行譯碼charr100;inti,j,len;j=2*n-2;/j初始從樹(shù)的根節(jié)點(diǎn)開(kāi)始printf(nn請(qǐng)輸入需要譯碼

10、的字符串:);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;elseif(ri=1)j=tj.rchild;if(tj.rchild=-1)printf(%c,tj.key);j=2*n-2;printf(nn);intmain()inti,j;hfmtht;charflag;printf(|n);printf(信管1002-林左權(quán)-15號(hào)|n);printf(|*|n);printf(|哈夫曼編碼課程設(shè)計(jì)|n

11、);printf(|*|n);printf(“I設(shè)計(jì)完成時(shí)間：2011/6/27|n);printf(|n);creathfmt(ht);printhfmt(ht);phfmnode(ht);printf(nprintf(*編碼&譯碼&退出*);printf(n【1】編碼t【2】t譯碼t【0】退出)；printf(n您的選擇：)；flag=getchar();getchar();while(flag!=0)if(flag=1)encoding(ht);elseif(flag=2)decoding(ht);elseprintf(您的輸入有誤，請(qǐng)重新輸入。n);printf（n*編碼&譯碼&退出*）printf（n【1】編碼t【2】t譯碼t【0】退出“）；printf（n您的選擇：“）；flag=getchar（）;getchar（）;printf（nnn）;printf（“*歡迎使用林左權(quán)的哈夫曼編碼系統(tǒng)*n）；printf（“system（pause）；五、測(cè)試數(shù)據(jù)及測(cè)試結(jié)果:例如：M言管1002林左15號(hào):I耳MM耳MMMM耳MM耳MM耳MM耳MMKMI!哈夫曼編碼課程設(shè)計(jì)!；設(shè)計(jì)完咸時(shí)間=2011/6/27!MM耳MM耳耳MM耳MM耳耳M車(chē)甬j/,區(qū)耳耳MM耳MXKMMKMMKXKM請(qǐng)