实验六哈夫曼编码和译码的算法设计与实现

12020年4月19日实验六哈夫曼编码和译码的算法设计与实现文档仅供参考22020年4月19日实验名称实验六哈夫曼编码和译码的算法设计与实现实验方案实验成绩实验日期-04-22实验室信息系统设计与仿真室I实验操作实验台号34号班级姓名信工11-1BF李煌峰实验结果一、实验目的1、根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编译码器；3、掌握贪心算法的一般设计方法。二、预习与参考1、认真阅读数据结构教材和算法设计教材内容,熟悉哈夫曼编码的原理;2、设计和编制哈夫曼编译码器。[参考数据类型或变量]typedefElemTypechar；typedefstructnode{intw;intflag;文档仅供参考32020年4月19日ElemTypec;structnode*plink,*llink,*rlink;charcode[m];}Node;Node*num[n],*root;[参考子程序接口与功能描述]voidSetTree(NODE*root)功能:从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树voidEnCode(Node*p)功能:利用已建好的哈夫曼树，对输入的正文进行编码voidDeCode(void)功能:利用已建好的哈夫曼树，将输入的代码进行译码三、实验要求上机实验时，一人一组，独立上机，熟练运用二叉树与贪心思想对数据进行压缩。四、实验步骤1、设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2、设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;文档仅供参考42020年4月19日3、设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4、将你的程序整理成功能模块存盘备用。5、将写的程序如下：#includestdio.h#includestring.h#includemath.h#includestring#definemaxn20//最大结点数目#defineinf0xfffffff//无穷大typedefstructnode{doublew;intflag;intc;structnode*plink,*llink,*rlink;charcode[maxn];intcodelen;node()//初始化节点{flag=0;llink=NULL;文档仅供参考52020年4月19日plink=NULL;rlink=NULL;codelen=0;}}node;node*num[2*maxn-1];//指针数组intn;voidSetTree(node*&root)//从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树{inti,m,j;scanf(%d,&n);//输入结点个数nfor(i=0;in;i++){num[i]=newnode();num[i]-c=i;scanf(%lf,&num[i]-w);//输入结点的权值}m=n;doublemin1,min2;intpos1=0,pos2=0;for(i=0;im-1;i++)文档仅供参考62020年4月19日{min1=inf;min2=inf;for(j=0;jn;j++)//寻找权值最小的两个结点，保存在pos1和pos2中{if(num[j]-flag==0){if(num[j]-wmin1){min1=num[j]-w;pos2=pos1;pos1=j;}elseif(num[j]-wmin2){min2=num[j]-w;pos2=j;}}}num[pos1]-flag=1;//将pos1和pos2合并在新结点中，作为新节点的子节点文档仅供参考72020年4月19日num[pos2]-flag=1;num[n]=newnode();//新节点编号从n开始num[n]-c=-1;////添加代码，建立新结点n//////建立新结点nnum[n]-w=num[pos1]-w+num[pos2]-w;num[n]-llink=num[pos1];num[n]-rlink=num[pos2];num[pos1]-plink=num[n];num[pos2]-plink=num[n];n++;}root=num[n-1];n=m;}voidEnCode(node*root,intdeep,charcode[])//利用已建好的哈夫曼树，对输入的文本进行编码{inti;if(root-c!=-1){for(i=0;ideep;i++){root-code[i]=code[i];文档仅供参考82020年4月19日}root-codelen=deep;return;}code[deep]='0';//左节点编码为0EnCode(root-llink,deep+1,code);code[deep]='1';//右节点编码为1EnCode(root-rlink,deep+1,code);}voidDeCode(node*root,charcode[])//利用已建好的哈夫曼树，对输入的代码进行译码{inti;node*temproot=root;intlen=strlen(code);intans[maxn],anslen=0;for(i=0;ilen;i++){////添加代码，根据code[i]的值确定temproot的指向//////根据code[i]的值确定temproot的指向if(code[i]=='0')temproot=temproot-llink;文档仅供参考92020年4月19日elsetemproot=temproot-rlink;if(temproot-c!=-1){ans[anslen++]=temproot-c;temproot=root;}if(temproot-llink==NULL&&temproot-rlink==NULL){printf(你输入的数据不存在于该哈弗曼树中!\n);return;}}printf(输入数据的译码为：\n);for(i=0;ianslen;i++){printf(%d,ans[i]);}printf(\n);}voidprint(){inti,j;文档仅供参考102020年4月19日for(i=0;in;i++){printf(%.2f:,num[i]-w);for(j=0;jnum[i]-codelen;j++)printf(%c,num[i]-code[j]);printf(\n);}}intmain(){freopen(in.txt,r,stdin);freopen(out.txt,w,stdout);node*root=NULL;root=newnode();SetTree(root);charcode[maxn*maxn];EnCode(root,0,code);print();printf(按上面的编码规则输入代码:\n);scanf(%s,code);DeCode(root,code);return0;文档仅供参考112020年4月19日}五、测试输入80.60.20.050.050.030.030.030.01输出0.6：00.2：100.05：11000.05：11110.03：110100.03：110110.03：111010.01：11100六、实验报告要求1、阐述实验目的和实验内容;2、提交实验程序的功能模块;3、记录最终测试数据和测试结果。七、心得在实验中我掌握哈夫曼编码的二叉树结构表示方法。