C语言-哈夫曼编码实验报告

1、C语言 - 哈夫曼编码实验报告福建工程学院课程设计课程：数据结构题目：哈夫曼编码和译码专业：信息管理信息系统班级：1002 班座号：15 号姓名：林左权2011 年6 月27 日2实验题目：哈夫曼编码和译码一、要解决的问题利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码 （复原）。对于双工信道（即可以双向传输信息的信道） ，每端都需要一个完整的编/译码系统。二、算法基本思想描述：根据给定的字符和其中每个字符的频度 ,构造哈夫馒树,并输出字符集中每个字符的哈夫曼编码 .将给定的字

2、符串根据其哈夫曼编码进行编码 ,并进行相应的译码 .三、设计1. 数据结构的设计（1）哈夫曼树的表示设计哈夫曼树的结构体（ htnode ），其中包含权重、左右孩子、父母和要编码的字符。用这个结构体（ htnode ）定义个哈夫曼数组（ hfmt ）。迷宫定义如下：typedef structint weight;int lchild;int rchild;int parent;char key;htnode;typedef htnode hfmtMAXLEN;（ 2）对原始字符进行编码初始化哈夫曼树（ inithfmt ）。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼

3、树。并显示出每个字符的编码。31.void inithfmt(hfmt t)/对结构体进行初始化2.void inputweight(hfmt t)/输入函数3.void selectmin(hfmtt,int i,int*p1,int*p2)/ 选中两个权值最小的函数4.void creathfmt(hfmt t)/创建哈夫曼树的函数5.void phfmnode(hfmt t)/ 对字符进行初始编码（ 3）对用户输入的字符进行编码void encoding(hfmt t)/对用户输入的电文进行编码char r1000;/用来存储输入的字符串int i,j;printf(nn请输入需要编码的

4、字符:);gets(r);printf(编码结果为 :);for(j=0;rj!=0;j+)for(i=0;in;i+)if(rj=ti.key)hfmtpath(t,i,j);printf(n);（ 4）对用户输入的字符进行编码void decoding(hfmt t)/对用户输入的密文进行译码char r100;int i,j,len;j=2*n-2;/j初始从树的根节点开始printf(nn请输入需要译码的字符串:);gets(r);len=strlen(r);printf(译码的结果是 :);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)/对结构体进行初始化

6、int i;printf(n);printf(-n);printf(*输入区*n);printf(n请输入 n=);scanf(%d,&n);getchar();for(i=0;i2*n-1;i+)/对结构体进行初始化ti.weight=0;ti.lchild=-1;5ti.rchild=-1;ti.parent=-1;printf(n);void inputweight(hfmt t)/输入函数int w;/w表示权值int i;char k;/k表示获取的字符for(i=0;in;i+)printf(请输入第 %d个字符 :,i+1);scanf(%c,&k);getchar();ti.k

7、ey=k;printf(请输入第 %d个字符的权值 :,i+1);scanf(%d,&w);getchar();ti.weight=w;printf(n);void selectmin(hfmt t,int i,int *p1,int *p2)/选中两个权值最小的函数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、创建哈夫曼树的函数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(*哈夫曼编数结构 :*n);printf(tt 权重 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)/对字符进行初始编码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)/对用户输入的电文进行编码char r1000;/用来存储输入的字符串int i,j;printf(nn请输入需要编码的字符:);gets(r);printf(编码结果为 :);for(j=0;rj!=0;j+)for(i=0;in;i+)if(rj=ti.key)hfmtpath(t,i,j);printf(n);8void de

11、coding(hfmt t)/对用户输入的密文进行译码char r100;int i,j,len;j=2*n-2;/j初始从树的根节点开始printf(nn请输入需要译码的字符串:);gets(r);len=strlen(r);printf(译码的结果是 :);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;if(tj.rchild=-1)printf(%c,tj.key);j=2*n-2;printf(nn);int main()int

12、 i,j;hfmt ht;char flag;printf(|-|n);printf(|信管 1002- 林左权 -15号 |n);printf(|*|n);printf(|哈夫曼编码课程设计|n);printf(|*|n);printf(|设计完成时间 :2011/6/27|n);9printf(|-|n);creathfmt(ht);printhfmt(ht);phfmnode(ht);printf(n-n);printf(*编码&译码&退出*);printf(n【 1】编码 t 【 2】 t译码 t 【 0】退出 );printf(n您的选择： );flag=getchar();getchar();while(flag!=0)if(flag=1)encoding(ht);else if(flag=2)decoding(ht);elseprintf(您的输入有误，请重新输入。