《实验6：哈夫曼树及哈夫曼编码的算法实现》由会员分享，可在线阅读，更多相关《实验6：哈夫曼树及哈夫曼编码的算法实现（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 100
3、00 定义最大权值常量#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 s
4、tart; /定义位置域hcnodetype; /定义编码类型htnode * creatstree(int n) /huffmanstree creatstree(int n) /健立哈夫曼树算法实现函数 int i,j,m1,m2,k1,k2; /局部变量for(i=0;i2*n-1;i+) /初始化各节点hti.weight=0; 权重初始化为0hti.parent=-1; /根节点和给左右孩子初始化为-1hti.lchild=-1;hti.rchild=-1;for(i=0;in;i+)/权重赋初值，由用户输入scanf(%d,&hti.weight);for(i=0;in-1;i+)
5、 /生成新节点构造哈夫曼树m1=maxvalue; /预置最小权值变量为最大权值m2=maxvalue; /预置次小权值变量为最大权值k1=0; /预置最小权值节点位置为下标为0处k2=0; /预置次小权值节点位置为下标为0处for(j=0;jn+i;j+) /循环找出每趟最下权值和所在位置if(htj.parent=-1 &htj.weightm1)m2=m1;k2=k1;m1=htj.weight;k1=j；else /当小于当前次小m2则更新m2及其位置if(htj.parent=-1 &htj.weightm2)m2=htj.weight;k2=j;htk1.parent=n+i; /
6、修改最小权值节点的双亲为刚生成的新节点 htk2.parent=n+i; /修改次小权值节点的双亲为刚生成的新节点 htn+i.weight=htk1.weight+htk2.weight; /将新生成的权重值填入新的根节点 htn+i.lchild=k1; /新生节点左孩子指向k1 htn+i.rchild=k2; /新生节点右孩子指向k2return ht; /返回哈夫曼树指针void getstree(htnode * ht,int n) /哈夫曼编码算法及打印函数的实现int i,j,c,p; /局部变量的定义hcnodetype cdmaxnodenumber; /定义存储哈夫曼编码
7、的数组 for(i=0;in;i+) /循环控制对每一个节点进行编码c=i; /为编码各节点初始化c和jj=maxbit;doj-; /j指向bit中存放编码为的正确位置p=htc.parent; /p指向c的双亲节点if(htp.lchild=c) /如果 c 是 p 的左孩子cdi.bitj=O;/编码为赋值 0else /否则即c是p的右孩子cdi.bitj=1;/编码赋值 1c=p;/更新当前指针，为下一节点编码做准备while(htp.parent!=-1); /判断是否编码结束即循环至最终根节点 cdi.start=j; /编码完成，记下编码开始位置for(i=0;in;i+) /
8、循环打印各节点哈夫曼编码for(j=cdi.start;jmaxbit;j+)循环逐一输出printf(%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;2M12747. F- I 1 v s-11000+A111Press anu key ta cantinue
