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

《试验四--哈夫曼树与哈夫曼编码》由会员分享，可在线阅读，更多相关《试验四--哈夫曼树与哈夫曼编码（13页珍藏版）》请在装配图网上搜索。

1、实验四 哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容 问题描述已知 n 个字符在原文中出现的频率，求它们的哈夫曼编码。 基本要求1. 初始化：从键盘读入 n 个字符，以及它们的权值，建立 Huffman 树。（具体算法可参见教材 P147 的算法 6.12 ）2. 编码：根据建立的 Huffman 树，求每个字符的 Huffman 编码。对给定的待编码字符序列进行编码。 选作内容1 .译码：利用已经建立好的 Hufman 树，对上面的编码 结果译码。 译码的过程是分解电文中的字符串，从根结点出发，按字符0和 1 确定找左孩子或

2、右孩子， 直至叶结点， 便求得该子串相应的 字符。4. 打印 Huffman 树。 测试数据利用教材 P.148 例 62 中的数据调试程序。 可设 8 种符号 分别为A,B,C,D,E,F,G,H。编/译码序列为 “CFBABBFHGH ”（也 可自己设定数据进行测试 ）。三、算法设计1 、 主 要 思 想 ： * 赫 夫 曼 树 的 构造*(1) 由给定的n个权值w1, w2,wn,构造具有n棵二 叉树的森林F =T1, T2,Tn ，其中每棵二叉树 Ti只有 一 个带权为 wi 的根结点 , 其左、右子树均为空。(2) 在 F 中选取两棵根结点的权值最小的二叉树 , 作为左、 右子树构造

3、一棵新的二叉树。 置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和(3)在 F 中删去这两棵二叉树 , 把新的二叉树加入 F。(4)重复(2)和(3) , 直到 F 中仅剩下一棵树为止*编码*主要用途是实现数据压缩。由于赫夫曼树中没有度为 1 的节点，则一棵有 n 个叶子结点的赫夫曼树共有 2n-1 个结点，可以 存储在一个大小为 2n-1 的一维数 组中。由于在构成赫夫曼树之后，为求编码需从叶子结点出发走 一条从叶子到根的路径； 而为译码需从根出发走一条从根到叶子 的路径。则对每个结点而言，既须知双亲的信息，又需知孩子结点的信息。2 、 本程序包含三个模块1)主函数Int main

4、() 先输入结点总数；分别输入各个结点；调用建立哈夫曼树函数；调用编码函数读入建立的哈夫曼树进行编码3、元素类型、结点类型和指针类型typedef struct / 定义新数据类型即结点结构int weight; / 权重域int parent,lchild,rchild; / 指针域 htnode; / 结点类型标识符/typedef htnode * huffmanstree; / 定义哈弗曼数类型 htnode htmaxnodenumber;/ 定义三叉链表存储数组 typedef struct / 定义保存一个叶子节点哈弗曼编码的结构 int bitmaxbit; / 定义一维数组为

5、编码域int start; / 定义位置域hcnodetype; / 定义编码类型4、主函数和其他函数清单1 )Int main() 先输入结点总数；分别输入各个结点；调用建立哈夫曼树函数； 调用编码函数读入建立的哈夫曼树进行编码2)htnode * creatstree(int n)建立哈夫曼树算法实现函-可编辑修改 -哈夫曼编码算法及打3) void getstree(htnode * ht,int n)印函数的实现四、调试分析输入结点总数分别输入各个结点I“I欢迎欣赏哈夫晏树 XJtXXMJCMIJCKMXXJCMIJC 二 请输入节点数池分别输入哈夫曼树的&个节馬13E792赫夫曼的编

6、码-可编辑修改-S勞ktop谓鴻结构作业实豔四皓夫晏癒与皓夫曼鵜码書命旳储丟曼诃写觸码七.g苗迎朮赏哈夫曼谢 BOf 请脇入节点数酩分别输入哈夫曼树的各个节点：1357哈夫曼树的编码为=311Q3109810110111Press any kev to continue五、总结本次实验电子报告中我原来打算加上各函数的简单流程图，但是由于我处理图形方面还比较不熟练， 画了三四个小时也不太满 意，所以索 性将几个小时的努力通过del键结束了，所以这次 报告不太令人满意，我将在以后的报告中加上示意图，多学习同学优秀的地方也会在以后的学习过程中要尽量考虑周全，使 程序更有实用价值，提高 编程能力。我更

7、加认识到自己动手的重要性，因为问题看起来很简 单，但是等到亲自去实践时，你会发现出现很多问题。正是通过 不断的发现问题、解决问题，我们才更加深刻的领悟到为核心， 进而更好的掌握所学的知识；其次，我认识到了自己不明白的地 方一定要向老师请教，老师的点拨，让人豁然开朗，有助于我们 更好的理解和掌握。最后，我理解栈的顺序结构，实现了一些基本操作，掌握了栈的先进后出的特点，并且能运用这一点解决实 际问题。六、源代码#include#include#include#define maxvalue 10000 / 定义最大权值常量#define maxnodenumber 100 / 定义节点最大数#de

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

9、类型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+) / 生成新节点构造哈夫曼树 m1=

10、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;

11、/ 修改最小权值节点的双亲为刚生成的 新节点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

12、; / 定义存储哈夫曼 编码的数组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;/ 编码为赋值 0else/ 否则即 c 是 p 的右孩子cdi.bitj=1;/ 编码赋值 1c=p;/ 更新当前指针，为下一节点编码做准备while(htp.parent!=-1);/ 判断是否编码结束即循环至最终根节点cdi.start

13、=j;/ 编码完成 ,记下编码开始位置for(i=0;in;i+) / 循环打印各节点哈夫曼编码 for(j=cdi.start;jmaxbit;j+)/循环逐一输出printf(%d,cdi.bitj);printf(n);/ 每输出一编码后换行int main() / 主函数 int n;printf(f*欢迎欣赏哈夫曼树*:);coutendl;printf( 请输入节点数 :); / 用户输入节点数scanf(%d,&n);coutendl;cout 分别输入哈夫曼树的各个节点 :endl;htnode * p; /huffmanstree p / 定义哈夫曼树类型 p p=(htnode * )malloc(sizeof(htnode *);/p=(huffmanstree)malloc(sizeof(huffmanstree)/ 分 配 内存空间p=creatstree(n);/ 调用建立哈夫曼树函数赋返回值给 p cout 哈夫曼树的编码为 :endl;getstree(p,n); / 调用编码函数读入建立的哈夫曼树 p 进 行编码return 0;-可编辑修改 -THANKS !致力为企业和个人提供合同协议，策划案计划书,学习课件等等打造全网一站式需求欢迎您的下载，资料仅供参考-可编辑修改-