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

1、实验名称实验六哈夫曼编码和译码的算法设计与实现实验日期2012-04-22实验室信息系统设计与仿真室I实验台号34号信工11-1BF李煌班级峰实验方案实验成绩实验操作实验结果、实验目的1、根据算法设计需要，掌握哈夫曼编码的二叉树结构表示方法;2、编程实现哈夫曼编译码器；3、掌握贪心算法的一般设计方法。1、认真阅读数据结构教材和算法设计教材内容，熟悉哈夫曼编码的原理2、设计和编制哈夫曼编译码器。参考数据类型或变量typedefElemTypechar;typedefstructnode(intw;intflag;ElemTypec;structnode*plink,*llink,*rlink;c

2、harcodem;Node;Node*numn,*root;参考子程序接口与功能描述voidSetTree(NODE*root)功能：从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树voidEnCode(Node*p)功能：利用已建好的哈夫曼树，对输入的正文进行编码voidDeCode(void)功能：利用已建好的哈夫曼树，将输入的代码进行译码三、实验要求上机实验时，一人一组，独立上机，熟练运用二叉树与贪心思想对数据进行压缩。四、实验步骤1、设计SetTree的测试方案和程序，输入测试数据，修改并调试程序，直至正确为止2、设计EnCode的测试方案和程序，输入测试数据，修改并调试程

3、序，直至正确为止3、设计DeCode的测试方案和程序，输入测试数据，修改并调试程序，直至正确为止4、将你的程序整理成功能模块存盘备用。5、将写的程序如下：#include<stdio.h>#include<string.h>#include<math.h>#include<string>#definemaxn20/最大结点数目#defineinfOxfffffff/无穷大typedefstructnode(doublew;intflag;intc;structnode*plink，*llink，*rlink;charcodemaxn;intcod

4、elen;node()/初始化节点(flag=O;llink=NULL;plink=NULL;rlink=NULL;codelen=0;node;node*num2*maxn-1;/指针数组intn;voidSetTree(node*&root)/从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树inti,m,j;scanf("%d”,&n);/输入结点个数nfor(i=0;i<n;i+)numi=newnode();numi->c=i;scanf("%lf",&numi->w);/输入结点的权值m=n;doub

5、lemin1,min2;intpos1=0,pos2=0;for(i=0;i<m-1;i+)min1=inf;min2=inf;for(j=0;j<n;j+)/寻找权值最小的两个结点，保存在pos1和pos2中if(numj->flag=0)if(numj->w<min1)min1=numj->w;pos2=pos1;pos1=j;min2=numj->w;pos2=j；numpos1->flag=1;/将posl和pos2合并在新结点中，作为新节点的子节点numpos2->flag=1;numn=newnode();/新节点编号从n开始n

6、umn->c=-1;/添加代码，建立新结点n/建立新结点nnumn->w=numpos1->w+numpos2->w;numn->llink=numpos1;numn->rlink=numpos2;numpos1->plink=numn;numpos2->plink=numn;n+;root=numn-1;n=m;voidEnCode(node*root,intdeep,charcode)/利用已建好的哈夫曼树，对输入的文本进行编码(inti;if(root->c!=-1)(for(i=0;i<deep;i+)(root->co

7、dei=codei;root->codelen=deep;return;codedeep='0'/左节点编码为0EnCode(root->llink,deep+1,code);codedeep='1'/右节点编码为1EnCode(root->rlink,deep+1,code);voidDeCode(node*root,charcode)/利用已建好的哈夫曼树，对输入的代码进行译码(inti;node*temproot=root;intlen=strlen(code);intansmaxn,anslen=0;for(i=0;i<len;i

8、+)(/添加代码，根据codei的值确定temproot的指向/根据codei的值确定temproot的指向if(codei='0')temproot=temproot->llink;elsetemproot=temproot->rlink;if(temproot->c!=-1)(ansanslen+=temproot->c;temproot=root;if(temproot->llink=NULL&&temproot->rlink=NULL)(printf("你输入的数据不存在于该哈弗曼树中!n");re

9、turn;printf("输入数据的译码为：n");for(i=0;i<anslen;i+)(printf("%d”,ansi);printf("n");voidprint()(inti,j;for(i=0;i<n;i+)(printf("%.2f:",numi->w);for(j=0;j<numi->codelen;j+)printf("%c”,numi->codej);printf("n");intmain()(freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);node*root=NULL;root=newnode();SetTree(root);charcodemaxn*maxn;EnCode(root,0,code);print();printf("按上面的编码规则输入代码:n");scanf("%s",code);DeCode(root,code);return0;五、测试输入80.60.20.050.050.030.