实验四--哈夫曼树与哈夫曼编码

实验四 哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容问题描述已知n个字符在原文中出现的频率，求它们的哈夫曼编码。基本要求1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。（具体算法可参见教材P147的算法6.12）2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。选作内容. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符0和1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。4. 打印Huffman树。测试数据利用教材P.148 例62中的数据调试程序。可设8种符号分别为A,B,C,D,E,F,G,H。编/译码序列为 “CFBABBFHGH”(也可自己设定数据进行测试)。3、 算法设计 1、主要思想：*赫夫曼树的构造*(1) 由给定的 n 个权值 w1, w2, , wn，构造具有 n 棵二叉树的森林 F =T1, T2, , Tn ，其中每棵二叉树 Ti 只有一 个带权为 wi 的根结点, 其左、右子树均为空。(2) 在 F 中选取两棵根结点的权值最小的二叉树, 作为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3)在 F 中删去这两棵二叉树, 把新的二叉树加入F。 (4)重复(2)和(3), 直到 F 中仅剩下一棵树为止。 *霍夫曼编码*主要用途是实现数据压缩。由于赫夫曼树中没有度为1的节点，则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既须知双亲的信息，又需知孩子结点的信息。2、 本程序包含三个模块1）主函数Int main() 先输入结点总数； 分别输入各个结点；调用建立哈夫曼树函数； 调用编码函数读入建立的哈夫曼树进行编码3、 元素类型、结点类型和指针类型typedef struct /定义新数据类型即结点结构int weight; /权重域 int parent,lchild,rchild; /指针域htnode; /结点类型标识符/typedef htnode * huffmanstree; /定义哈弗曼数类型htnode htmaxnodenumber;/定义三叉链表存储数组typedef struct /定义保存一个叶子节点哈弗曼编码的结构 int bitmaxbit; /定义一维数组为编码域 int start; /定义位置域hcnodetype; /定义编码类型4、 主函数和其他函数清单1）Int main() 先输入结点总数； 分别输入各个结点；调用建立哈夫曼树函数； 调用编码函数读入建立的哈夫曼树进行编码2）htnode * creatstree(int n) 建立哈夫曼树算法实现函数3）void getstree(htnode * ht,int n) 哈夫曼编码算法及打印函数的实现四、调试分析 输入结点总数 分别输入各个结点 赫夫曼的编码5、 总结本次实验电子报告中我原来打算加上各函数的简单流程图，但是由于我处理图形方面还比较不熟练，画了三四个小时也不太满意，所以索性将几个小时的努力通过del键结束了，所以这次报告不太令人满意，我将在以后的报告中加上示意图，多学习同学优秀的地方也会在以后的学习过程中要尽量考虑周全，使程序更有实用价值，提高编程能力。 我更加认识到自己动手的重要性，因为问题看起来很简单，但是等到亲自去实践时，你会发现出现很多问题。正是通过不断的发现问题、解决问题，我们才更加深刻的领悟到为核心，进而更好的掌握所学的知识；其次，我认识到了自己不明白的地方一定要向老师请教，老师的点拨，让人豁然开朗，有助于我们更好的理解和掌握。最后，我理解栈的顺序结构，实现了一些基本操作，掌握了栈的先进后出的特点，并且能运用这一点解决实际问题。六、源代码#include#include#include#define maxvalue 10000 /定义最大权值常量#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; /定义位置域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; /权重初始化为0 hti.parent=-1; /根节点和给左右孩子初始化为-1 hti.lchild=-1; hti.rchild=-1;for(i=0;in;i+)/权重赋初值，由用户输入 scanf(%d,&hti.weight); for(i=0;in-1;i+) /生成新节点构造哈夫曼树 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;/修改最小权值节点的双亲为刚生成的新节点htk2.parent=n+i;/修改次小权值节点的双亲为刚生成的新节点htn+i.weight=htk1.weight+htk2.weight; /将新生成的权重值填入新的根节点htn+i.lchild=k1; /新生节点左孩子指向k1htn+i.rchild=k2; /新生节点右孩子指向k2return ht; /返回哈夫曼树指针?void getstree(htnode * ht,int n) /哈夫曼编码算法及打印函数的实现? int i,j,c,p; /局部变量的定义 hcnodetype cdmaxnodenumber; /定义存储哈夫曼编码的数组for(i=0;in;i+) /循环控制对每一个节点进行编码 c=i; /为编码各节点初始化c和jj=maxbit;do j-;/j指向bit中存放编码为的正确位置p=htc.parent; /p指向c的双亲节点if(htp.lchild=c)/如果c是p的左孩子cdi.bitj=0;/编码为赋值0 else/否则即c是p的右孩子 cdi.bitj=1;/编码赋值1 c=p;/更新当前指针，为下一节点编码做准备while(htp.parent!=-1);/判断是否编码结束即循环至最终根节点cdi.start=j;/编码完成,记下编码开始位置for(i=0;in;i+) /循环打印各节点哈夫曼编码 for(j=cdi.start;jmaxbit;j+)/循环逐一输出 printf(%d,cdi.bitj); printf(n);/每输出一编码后换行 int main() /主函数 int n; printf(*欢迎欣赏哈夫曼树*:);coutendl; printf(请输入节点数:); /用户输入节点数 scanf(%d,&n); coutendl; cout分别输入哈夫曼树的各个节点:endl; htnode * p; /huffmanstree p /定义哈夫曼树类型p p=