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

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

2、据结构的设计哈夫曼树的表示设计哈夫曼树的结构体(htnode),其中包含权重、左右孩子、父母和要编码的字符。用这个结构体(htnode)定义个哈夫曼数组(hfmt)。迷宫定义如下：typedefstructintweight;intlchild;intrchild;intparent;charkey;htnode;typedefhtnodehfmtMAXLEN;对原始字符进行编码初始化哈夫曼树(inithfmt)。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树。并显示出每个字符的编码。voidinithfmt(hfmtt)对结构体进行初始化voidinputweight(hfmt

3、t)输入函数voidselectmin(hfmtt,inti,int*p1,int*p2)选中两个权值最小的函数voidcreathfmt(hfmtt)创建哈夫曼树的函数voidphfmnode(hfmtt)对字符进行初始编码对用户输入的字符进行编码voidencoding(hfmtt)/对用户输入的电文进行编码charr1000;/用来存储输入的字符串inti,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);

4、对用户输入的字符进行编码voiddecoding(hfmtt)/对用户输入的密文进行译码charr100;inti,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;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)/对结构体进行初始化inti;printf(n);printf(n);printf(*输入区*n);printf(n请输入n二)；scanf(%d,&n);getchar()；for(i=0;i2*n-l;i+)/对结构体进行初始化ti.weight=0;ti.lchil

6、d=-1;ti.rchild=-1;ti.parent=-1;printf(n);voidinputweight(hfmtt)/输入函数intw;/w表示权值inti;chark;/k表示获取的字符for(i=0;itj.weight)min1=tj.weight;*p1=j;for(j=0;j二i;j+)/选择次小权值字符的下标还回if(tj.parent=-1)if(min2tj.weight&j!=(*pl)/主意j!=(*pl)min2=tj.weight;*p2=j;voidcreathfmt(hfmtt)/创建哈夫曼树的函数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)/打印哈夫曼树inti;printf(n);printf(*哈夫曼编数结木勾：*n)printf(tt权重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)/编码的重要哈夫曼树路径递归算法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)/对字符进行初始编码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)/对用户输入的电文进行编码charr1000;/用来存储输入的字符串inti,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);voiddecoding(hfmtt)/对用户输入的密文进行译码charr100;inti,j,len;j=2*n-2;/j初始从树的根节点开始printf(nn请输入需要译码

10、的字符串:);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;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-林左权-15号|n);printf(|*|n);printf(|哈夫曼编码课程设计|n

11、);printf(|*|n);printf(“I设计完成时间：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(您的输入有误，请重新输入。n);printf（n*编码&译码&退出*）printf（n【1】编码t【2】t译码t【0】退出“）；printf（n您的选择：“）；flag=getchar（）;getchar（）;printf（nnn）;printf（“*欢迎使用林左权的哈夫曼编码系统*n）；printf（“system（pause）；五、测试数据及测试结果:例如：M言管1002林左15号:I耳MM耳MMMM耳MM耳MM耳MM耳MMKMI!哈夫曼编码课程设计!；设计完咸时间=2011/6/27!MM耳MM耳耳MM耳MM耳耳M车甬j/,區耳耳MM耳MXKMMKMMKXKM请