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

《实验六 哈夫曼编码和译码的算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、ElemTypec;structnode*plink,*llink,*rlink;     charcode[m];}Node;Node*num[n],*root;[参考子程序接口与功能描述]voidSetTree(NODE*root)功能:从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树voidEnCode(Node*p)功能:利用已建好的哈夫曼树，对输入的正文进行编码voidDeCode(void)功能:利用已建好的哈夫曼树，将输入的代码进行译码三、实验要求上机实验时，一人一组，独立上机，熟练运用二叉树与贪心思想对数据进行压缩。四、实验步骤1、设计Se

3、tTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2、设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3、设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4、将你的程序整理成功能模块存盘备用。5、将写的程序如下：#include#include#include#include#definemaxn20//最大结点数目#defineinf0xfffffff//无穷大typedefstructnode{doublew;in

4、tflag;intc;structnode*plink,*llink,*rlink;charcode[maxn];intcodelen;node()//初始化节点{flag=0;llink=NULL;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;i

5、de();num[i]->c=i;scanf("%lf",&num[i]->w);//输入结点的权值}m=n;doublemin1,min2;intpos1=0,pos2=0;for(i=0;iflag==0){if(num[j]->ww;pos2=pos1;pos1=j;}elseif(num[j]->ww;pos2=j;}

6、}}num[pos1]->flag=1;//将pos1和pos2合并在新结点中，作为新节点的子节点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

7、=m;}voidEnCode(node*root,intdeep,charcode[])//利用已建好的哈夫曼树，对输入的文本进行编码{inti;if(root->c!=-1){for(i=0;icode[i]=code[i];}root->codelen=deep;return;}code[deep]='0';//左节点编码为0EnCode(root->llink,deep+1,code);code[deep]='1';//右节点编码为1EnCode(root->rlink,deep+1,code);}voidDe