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

1福建工程学院课程设计课程：数据结构题目：哈夫曼编码和译码专业：信息管理信息系统班级：1002班座号：15号姓名：林左权2011年6月27日2实验题目：哈夫曼编码和译码一、要解决的问题利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。二、算法基本思想描述：根据给定的字符和其中每个字符的频度,构造哈夫馒树,并输出字符集中每个字符的哈夫曼编码.将给定的字符串根据其哈夫曼编码进行编码,并进行相应的译码.三、设计1.数据结构的设计（1）哈夫曼树的表示设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。用这个结构体（htnode）定义个哈夫曼数组（hfmt[]）。迷宫定义如下：typedefstruct{intweight;intlchild;intrchild;intparent;charkey;}htnode;typedefhtnodehfmt[MAXLEN];（2）对原始字符进行编码初始化哈夫曼树（inithfmt）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。并显示出每个字符的编码。1.voidinithfmt(hfmtt)//对结构体进行初始化2.voidinputweight(hfmtt)//输入函数3.voidselectmin(hfmtt,inti,int*p1,int*p2)//选中两个权值最小的函数4.voidcreathfmt(hfmtt)//创建哈夫曼树的函数5.voidphfmnode(hfmtt)//对字符进行初始编码（3）对用户输入的字符进行编码voidencoding(hfmtt)//对用户输入的电文进行编码{charr[1000];//用来存储输入的字符串inti,j;printf(\n\n请输入需要编码的字符:);gets(r);printf(编码结果为:);for(j=0;r[j]!='\0';j++)for(i=0;in;i++)if(r[j]==t[i].key)3hfmtpath(t,i,j);printf(\n);}（4）对用户输入的字符进行编码voiddecoding(hfmtt)//对用户输入的密文进行译码{charr[100];inti,j,len;j=2*n-2;//j初始从树的根节点开始printf(\n\n请输入需要译码的字符串:);gets(r);len=strlen(r);printf(译码的结果是:);for(i=0;ilen;i++){if(r[i]=='0'){j=t[j].lchild;if(t[j].lchild==-1){printf(%c,t[j].key);j=2*n-2;}}elseif(r[i]=='1'){j=t[j].rchild;if(t[j].rchild==-1){printf(%c,t[j].key);j=2*n-2;}}}printf(\n\n);}四、源程序清单：#includestdio.h#includestdlib.h#includestring.h#defineMAXLEN100typedefstruct{intweight;4intlchild;intrchild;intparent;charkey;}htnode;typedefhtnodehfmt[MAXLEN];intn;voidinithfmt(hfmtt)//对结构体进行初始化{inti;printf(\n);printf(------------------------------------------------------------------\n);printf(******************************输入区******************************\n);printf(\n请输入n=);scanf(%d,&n);getchar();for(i=0;i2*n-1;i++)//对结构体进行初始化{t[i].weight=0;t[i].lchild=-1;t[i].rchild=-1;t[i].parent=-1;}printf(\n);}voidinputweight(hfmtt)//输入函数{intw;//w表示权值inti;chark;//k表示获取的字符for(i=0;in;i++){printf(请输入第%d个字符:,i+1);scanf(%c,&k);getchar();t[i].key=k;printf(请输入第%d个字符的权值:,i+1);scanf(%d,&w);getchar();t[i].weight=w;5printf(\n);}}voidselectmin(hfmtt,inti,int*p1,int*p2)//选中两个权值最小的函数{longmin1=999999;longmin2=999999;intj;for(j=0;j=i;j++)//选择最小权值字符的下标返回if(t[j].parent==-1)if(min1t[j].weight){min1=t[j].weight;*p1=j;}for(j=0;j=i;j++)//选择次小权值字符的下标还回if(t[j].parent==-1)if(min2t[j].weight&&j!=(*p1))//注意j!=(*p1)){min2=t[j].weight;*p2=j;}}voidcreathfmt(hfmtt)//创建哈夫曼树的函数{inti,p1,p2;inithfmt(t);inputweight(t);for(i=n;i2*n-1;i++){selectmin(t,i-1,&p1,&p2);t[p1].parent=i;t[p2].parent=i;t[i].lchild=p1;t[i].rchild=p2;t[i].weight=t[p1].weight+t[p2].weight;}}voidprinthfmt(hfmtt)//打印哈夫曼树{inti;6printf(------------------------------------------------------------------\n);printf(**********************哈夫曼编数结构:*****************************\n);printf(\t\t权重\t父母\t左孩子\t右孩子\t字符\t);for(i=0;i2*n-1;i++){printf(\n);printf(\t\t%d\t%d\t%d\t%d\t%c,t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,t[i].key);}printf(\n------------------------------------------------------------------\n);printf(\n\n);}voidhfmtpath(hfmtt,inti,intj)//编码的重要哈夫曼树路径递归算法{inta,b;a=i;b=j=t[i].parent;if(t[j].parent!=-1){i=j;hfmtpath(t,i,j);}if(t[b].lchild==a)printf(0);elseprintf(1);}voidphfmnode(hfmtt)//对字符进行初始编码{inti,j,a;printf(\n------------------------------------------------------------------\n);printf(**************************哈夫曼编码7******************************);for(i=0;in;i++){j=0;printf(\n);printf(\t\t%c\t,t[i].key,t[i].weight);hfmtpath(t,i,j);}printf(\n------------------------------------------------------------------\n);}voidencoding(hfmtt)//对用户输入的电文进行编码{charr[1000];//用来存储输入的字符串inti,j;printf(\n\n请输入需要编码的字符:);gets(r);printf(编码结果为:);for(j=0;r[j]!='\0';j++)for(i=0;in;i++)if(r[j]==t[i].key)hfmtpath(t,i,j);printf(\n);}voiddecoding(hfmtt)//对用户输入的密文进行译码{charr[100];inti,j,len;j=2*n-2;//j初始从树的根节点开始printf(\n\n请输入需要译码的字符串:);gets(r);len=strlen(r);printf(译码的结果是:);for(i=0;ilen;i++){if(r[i]=='0'){j=t[j].lchild;if(t[j].lchild==-1){printf(%c,t[j].key);j=2*n-2;}8}elseif(r[i]=='1'){j=t[j].rchild;if(t[j].rchild==-1){printf(%c,t[j].key);j=2*n-2;}}}printf(\n\n);}intmain(){inti,j;hfmtht;charflag;printf(|----------------------|\n);printf(|信管1002--林左权--15号|\n);printf(|**********************|\n);printf(|哈夫曼编码课程设计|\n);printf(|**********************|\n);printf(|设计完成时间:2011/6/27|\n);printf(|----------------------|\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);elseif(flag=='2')decoding(ht);elseprintf(您的输入有误，请重新输入。\n);9printf(\n***************************编码&&译码&&退出***********************);printf(\n【1】编码\t【2】\t译码\t【0】退出);printf(\n您的选择：);flag=getchar();getchar();}printf(\n\n-----------------------------------------------------------------\n);printf(***************欢迎使用林左权的哈夫曼编码系统********************\n);printf(------------------------------------------