您现在的位置:网站首页答辩论文计算机毕业设计计算机论文计算机软件

数据结构与算法课程设计——哈夫曼树

  • 简介:(毕业论文 字数:2402 页数:17 带程序)摘要:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称作路径长度。树的路径长度是从树跟到每一结点的路经长度之和。将此概念推广到一般情况,考虑带权结点。结点的带权路径长...
    • 请与管理员联系购买资料 QQ:5739126
  • 论文简介
  • 相关论文
  • 论文下载

(毕业论文 字数:2402 页数:17 带程序)摘要:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称作路径长度。树的路径长度是从树跟到每一结点的路经长度之和。将此概念推广到一般情况,考虑带权结点。结点的带权路径长度为从该点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子节点的带权路径长度之河,通常记作WPL。假设有n个权值,是构造一棵有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树乘坐最优二叉树或哈夫曼树。

目录
一、 问题描述和分析 …………………………………………………………1
二、 数据结构设计 ……………………………………………………………1
三、 算法设计 …………………………………………………………………2
四、 源代码说明 ………………………………………………………………3
五、 结果与分析 ………………………………………………………………13
六、 参考文献 …………………………………………………………………14

一、 问题描述和分析
问题描述:
目前,进行快速远距离通信的主要手段是电报,即将需传送的文字换换成由二进制的字符组成的字符串。在传送电文时,希望总长尽可能的短。如果每个字符设计长度不等的编码,且让电文中出现次数较多的字符尽可能短的编码,则传送电文的总长便可减少。若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符编码的前缀,这种编码称作前缀编码。
问题分析:
可以利用二叉树来设计二进制的前缀编码。假设有一颗如图所示的二叉树,其4个叶子结点分别表示A、B、C、D这四的字符,且约定左分支表示字符’0’,右分支表示字符’1’,则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。可以证明得到的必为二进制编码。如图所得A、B、C、D的二进制前缀编码分别为0、10、110和111。

二、 数据结构设计
因为哈夫曼树共有2n-1个节点,所以我们定义一个大小为2n-1的一维数组来存储哈夫曼树中的节点,其中前n各元素存储的是初始森林中的n个叶子节点,由初始森林中的两个最小的叶子节点构成的新节点存储在第n+1的单元中,以此类推,直到所有的节点都存储完毕为止。
typedef struct
{
int weight;
int flag;
int parent;
char ch;
int lchild;
int rchild;
}HafNode;
typedef struct
{
int bit[MAX];
int start;
int weight;
char ch;
}Code;

三、 算法设计
主要算法的基本思想:
 编码算法:
根据输入的数据,从中选取两棵根结点权值最小且没有被选过的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树上根结点的权值之和。
哈夫曼树已经建立后,从叶子到根逆向求每一个字符的哈夫曼编码。
 译码算法:
译码的过程是分解电文中的字符串,从根出发,如果为字符‘0’就找左孩子,如果为字符‘1’就找右孩子,直至叶子结点,得到该子串相应的字符并输出。

查看评论 已有0位网友发表了看法
  • 验证码: