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)姓名：林左權(quán)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ì)1.

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

4、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;i<len;i+)(if(ri='0')(j=tj.lchild;if(tj.lchild=-1)(printf("

5、;%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");四、源程序活單：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXLEN100typedefstruct(intweight;intIchild;intrchild;intparent;charkey;htno

6、de;typedefhtnodehfmtMAXLEN;intn;voidinithfmt(hfmtt)/對(duì)結(jié)構(gòu)體進(jìn)行初始化inti;printf("n");printf("n");printf("*5)printf("n請(qǐng)輸入n=");scanf("%d",&n);getchar();for(i=0;i<2*n-1;i+)/對(duì)結(jié)構(gòu)體進(jìn)行初始化ti.weight=0;ti.lchild=-1;ti.rchild=-1;ti.parent=-1;printf("n");voi

7、dinputweight(hfmtt)/輸入函數(shù)intw;/w表示權(quán)值inti;chark;/k表示獲取的字符for(i=0;i<n;i+)printf("請(qǐng)輸入第樸字符:",i+1);scanf("%c",&k);getchar();ti.key=k;printf("請(qǐng)輸入第樸字符的權(quán)值:",i+1);scanf("%d",&w);getchar();ti.weight=w;voidselectmin(hfmtt,inti,int*p1,int*p2)/選中兩個(gè)權(quán)值最小的函數(shù)(longmin

8、1=999999;longmin2=999999;intj;for(j=0;j<=i;j+)/選擇最小權(quán)值字符的下標(biāo)返回if(tj.parent=-1)if(min1>tj.weight)(min1=tj.weight;*p1=j;for(j=0;j<=i;j+)/選擇次小權(quán)值字符的下標(biāo)還回if(tj.parent=-1)if(min2>tj.weight&&j!=(*p1)/注意j!=(*p1)(min2=tj.weight;*p2=j;voidcreathfmt(hfmtt)/創(chuàng)建哈夫曼樹(shù)的函數(shù)(inti,p1,p2;inithfmt(t);inpu

9、tweight(t);for(i=n;i<2*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("printf(''*n");哈夫*printf("tt權(quán)重t父母t左孩子t右孩子t字符t");for(i=0;i<2*n-1;i+)(printf(&qu

10、ot;n");printf("tt%dt%dt%dt%dt%c",ti.weight,ti.parent,ti.lchild,ti.rchild,ti.key);printf("nn");printf("nn");編碼的重要哈夫曼樹(shù)路徑遞歸算法voidhfmtpath(hfmtt,inti,intj)/(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(&

11、quot;1H);voidphfmnode(hfmtt)/對(duì)字符進(jìn)行初始編碼(inti,j,a;n")printf("nprintf(''*哈夫曼編碼*");for(i=0;i<n;i+)(j=0；printf("n");printf("tt%ct",ti.key,ti.weight);hfmtpath(t,i,j);printf("nn");voidencoding(hfmtt)/對(duì)用戶(hù)輸入的電文進(jìn)行編碼(charr1000;/用來(lái)存儲(chǔ)輸入的字符申inti,j;printf(&qu

12、ot;nn請(qǐng)輸入需要編碼的字符:");gets(r);printf("編碼結(jié)果為：")；for(j=0;rj!='0'j+)for(i=0;i<n;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)輸入需要譯碼的字符申:");gets(r);len=strlen(r);printf("譯碼的

13、結(jié)果是:");for(i=0;i<len;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("printf("printf(&q

14、uot;printf("printf("printf("printf("creathfmt(ht);printhfmt(ht);phfmnode(ht);|n");|信管1002-林左權(quán)-15號(hào)|n");|*|村)；|哈夫曼編碼課程設(shè)計(jì)|n");|*|村)；|設(shè)計(jì)完成時(shí)間：2011/6/27|n");|n");n")printf(''*編碼&&譯碼&&退出printf("n*");printf("n【1】編碼t【2】t

15、譯碼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("nn);printf("*n"歡送使用林左權(quán)的哈夫曼編碼系統(tǒng)*5);printf("n");system("paus