实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本.docx

《实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本.docx》由会员分享，可在线阅读，更多相关《实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验6：哈夫曼树及哈夫曼编码的算法实现实验所需 学时数2学时实验目的1)掌握哈夫曼树的基本概念及其存储结构；2)掌握哈夫曼树的建立算法；3)掌握哈夫曼树的应用(哈夫曼编码和译码)。实验内容对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码， 输出电文字符串。实验所需 器材计算机及VC+ 6.0软件内容要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈 夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后

2、的字符串输出。4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。测试数据：输入字符串this*program*is*my*favourite完成这28个字符的编码和译码。实验结果1、演示程序运行结果。2、说明调试过程中出现的现象学生实验评价依据：优：实验认真、刻苦，有钻研精神，不无故缺席。良：能认真对待实验，不无故缺席。中：基本能认真对待实验，不无故缺席。差：对待实验不够认真，有少量迟到、早退或无故缺席现象。不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。#include #include #define maxvalue 10000 定义最大

3、权值常量#define maxnodenumber 100 定义节点最大数#define maxbit 10 定义哈弗曼编码最大长度typedef struct定义新数据类型即节点结构int weight; 权重域int parent,lchild,rchild; 指针域htnode;节点类型标识符typedef htnode * huffmanstree; 定义哈弗曼数类型htnode htmaxnodenumber; 定义三叉链表存储数组typedef struct 定义保存一个叶子节点哈弗曼编码的结构int bitmaxbit; 定义维数组为编码域int start; 定义位置域hcno

4、detype; 定义编码类型htnode * creatstree(int n) /huffmanstree creatstree(int n) 建立哈夫曼树算法实现函数 (int ijml,m2,kl,k2; 局部变量for(i=0;i2*n-l;i+) 初始化各节点(hti.weight=0; /权重初始化为0山1由3mM二-1；根节点和给左右孩子初始化为-1hti.lchild=-l;hti.rchild=-l;)for(i=0;in;i+) 权重赋初值，由用户输入(scanf(%d,&hti.weight);)for(i=0;in-l;i+) 生成新节点构造哈夫曼树(ml=maxval

5、ue; 预置最小权值变量为最大权值m2二maxvalue; 预置次小权值变量为最大权值kl=0; 预置最小权值节点位置为下标为0处k2=0; 预置次小权值节点位置为下标为0处for(j=0;jn+i;j+) 循环找出每趟最下权值和所在位置if(htj.parent=-l&htj.weightml)(m2=ml;k2=kl;ml=htj.weight;kl=j；)else 当小于当前次小m2那么更新m2及其位置if(htj.parent=-l&htj.weightm2)(m2=htj.weight;k2=j;)htkl.parent=n+i; 修改最小权值节点的双亲为刚生成的新节点htk2.pa

6、rent=n+i; 修改次小权值节点的双亲为刚生成的新节点htn+i.weight=htkl.weight+htk2.weight; 将新生成的权重值填入新的根节点htn+i.lchild二kl; 新生节点左孩子指向klhtn+i.rchild=k2; 新生节点右孩子指向k2return ht; 返回哈夫曼树指针void getstree(htnode * htjnt n) 哈夫曼编码算法及打印函数的实现 (int i,j,c,p; 局部变量的定义hcnodetype cdmaxnodenumbe门;定义存储哈夫曼编码的数组for(i=0;in;i+) 循环控制对每一个节点进行编码(c二i;

7、为编码各节点初始化c和jj=maxbit;do(指向bit中存放编码为的正确位置p=htc.parent; /p指向c的双亲节点if(htp.lchild=c) 如果 c 是 p 的左孩子cdi.bitj=O;编码为赋值Oelse 否贝U即c是p的右孩子cdi.bitj=l;编码赋值lc=p;更新当前指针，为下一节点编码做准备while(htp.parent!=-l); 判断是否编码结束即循环至最终根节点 cdi.start大编码完成，记下编码开始位置 )for(i=0;in;i+) 循环打印各节点哈夫曼编码for(j=cdi.start;jmaxbit;j+)循环逐一输出 printf(“%

8、d，cdi.bitj);printf(”n); 每输出一编码后换行)int main。主函数(int n;printf(请输入节点数用户输入节点数scanf(%d,&n);htnode * p; / huffmanstree p 定义哈夫曼树类型 pp=(htnode * )malloc(sizeof(htnode *);/p=(huffmanstree)malloc(sizeof(huffmanstree)分酉己内存 空间p二creatstree(n);调用建立哈夫曼树函数赋返回值给pgetstree(p,n); 调用编码函数读入建立的哈夫曼树p进行编码return 0;)$ m Md:DesktopMyProjectshafumanstreeDel)ugshiyanerhaffman.exeM- X r)晴输入节点数：65202?4?91100fill10111010100Press any key to continue