《实验六-哈夫曼编码和译码的算法设计与实现.doc》由会员分享，可在线阅读，更多相关《实验六-哈夫曼编码和译码的算法设计与实现.doc（9页珍藏版）》请在三一文库上搜索。
1、实验六-哈夫曼编码和译码的算 法设计与实现实验名称 哈旳 六逅 验算 实的实验日期实验室统仿 系与I ,k计室实验台号号班信工级信丄姓 11-1BF 姓李煌峰、实验目的1、根据算法设计需要,掌握哈夫曼编码的二叉 树结构表示方法；2、编程实现哈夫曼编译码器；3、掌握贪心算法的一般设计方法。实验方案实验成绩实验操作实验结果、预习与参考1、认真阅读数据结构教材和算法设计教材内 容，熟悉哈夫曼编码的原理；2、设计和编制哈夫曼编译码器。参考数据类型或变量typedef ElemType char ；typedef struct no deint w;int flag;ElemType c;struct
2、node *pli nk,*lli nk,*rl ink;char codem;Node;Node *n um n, *roo t; 参考子程序接口与功能描述 void SetTree( NODE *root )功能:从终端读入字符集大小n,以及n个字 符和 n 个权值，建立哈夫曼树void EnCode( Node *p )功能: 利用已建好的哈夫曼树， 对输入的正文 进行编码void DeCode( void )功能: 利用已建好的哈夫曼树， 将输入的代码 进行译码三、实验要求上机实验时，一人一组，独立上机，熟练运 用二叉树与贪心思想对数据进行压缩。四、实验步骤1、设计 SetTree 的
3、测试方案和程序 , 输入测 试数据, 修改并调试程序 , 直至正确为止 ;2、设计EnCode的测试方案和程序,输入测 试数据 , 修改并调试程序 , 直至正确为止 ;3、设计DeCode的测试方案和程序,输入测试数据 , 修改并调试程序 , 直至正确为止 ;4、将你的程序整理成功能模块存盘备用。5、将写的程序如下：#include #include #include #include #define maxn 20 / 最大结点数目#define inf 0xfffffff /无穷大typedef struct node double w;int flag;int c;struct node
4、 *plink,*llink,*rlink;char codemaxn;int codelen;node() / 初始化节点 flag=0; llink=NULL; plink=NULL; rlink=NULL; codelen=0; node;node *num2*maxn-1;/ 指针数组int n;void SetTree(node *&root)/ 从终端读入字 符集大小n,以及n个字符和n个权值，建立 哈夫曼树int i,m,j;scanf(%d,&n);/ 输入结点个数 n for(i=0;ic=i;scanf(%lf,&numi-w);/输 入结点的权值 m=n;double m
5、in1,min2;int pos1=0,pos2=0;for(i=0;im-1;i+)min1=inf;min2=inf;for(j=0;jflag=0)if(numj-ww; pos2=pos1; pos1=j;else if(numj-ww; pos2=j;numpos1-flag=1; / 将 pos1和 pos2 合并在新结点中，作为新节点的子节点八、numpos2-flag=1;numn=new node(); /新节点编号从 n 开始numn-c=-1;/ 添加代码，建立新结点 n/ 建立新结点 nnumn-w=numpos1-w+numpos2-w; numn-llink=num
6、pos1; numn-rlink=numpos2; numpos1-plink=numn; numpos2-plink=numn; n+;root=numn-1;n=m;void EnCode(node *root,int deep,char code) / 利用已建好的哈夫曼树， 对输入的 文本进行编码int i;if(root-c!=-1)for(i=0;icodei=codei;root-codelen=deep;return;codedeep=0; /左节点编码为 0EnCode(root-llink,deep+1,code);codedeep=1; /右节点编码为 1EnCode(r
7、oot-rlink,deep+1,code);void DeCode(node *root,char code) / 利用已建好的哈夫曼树， 对输入的代码进行译 码int i;node *temproot=root;int len=strlen(code);int ansmaxn,anslen=0;for(i=0;illink;elsetemproot=temproot-rlink;if(temproot-c!=-1)ansanslen+=temproot-c; temproot=root;if(temproot-llink=NULL & temproot-rlink=NULL)printf(
8、 你输入的数据不存在 于该哈弗曼树中 !n);return;printf( 输入数据的译码为： n);for(i=0;ianslen;i+)printf(%d,ansi);printf(n);void print()int i,j;for(i=0;iw);for(j=0;jcodelen;j+) printf(%c,numi-codej);printf(n);int main()freopen(in.txt,r,stdin);freopen(out.txt,w,stdout);node *root=NULL;root=new node();SetTree(root);char codemaxn
9、*maxn;EnCode(root,0,code);print();printf( 按 上 面 的 编 码 规 则 输 入 代 码:n);scanf(%s,code);DeCode(root,code);return 0;五、测试输入80.030.6 0.2 0.05 0.05 0.03 0.030.01输出0.6： 00.2： 100.05： 11000.05： 11110.03： 110100.03： 110110.03： 111010.01： 11100六、实验报告要求1、阐述实验目的和实验内容 ;2、提交实验程序的功能模块 ;3、记录最终测试数据和测试结果。七、心得 在实验中我掌握哈夫曼编码的二叉树结构表 示方法。