计算机科学与技术系
课程设计报告
2013 ～2014 学年第 2 学期
课学学专指
业导
班教生
姓
程 数据结构与算法
哈夫曼树 xxx xxxx 12软件工程
xx
名 号 级 师
课程设计名称
一、题目
设计程序以实现构造哈夫曼树的哈夫曼算法。要求：求解所构造的哈夫曼树的带全路径长度。
二、问题分析和任务定义
这个程序需要我们解决两个问题， 第一个是构造哈夫曼树， 第二个是求带权路径的长度。
本问题的关键就是在于如何建立哈夫曼树
三、概要设计和数据结构选择
假设给定n个实数w1,w2.....构造拥有n个叶子结点的哈夫曼树，且这n个叶子结点的权值分别为给定的实数，则哈夫曼树的构造方法如下：
1.根据给定的n个实数，根据n颗单结点二叉树，各二叉树的根权值分别为w1,w2.......，令这n颗二叉树构成一个二叉树的集合M。
在这n颗单结点的二叉树中，这些结点既是根结点又是叶子结点。
2.在集合M中筛选出两个根结点的权值最小的二叉树作为左右子树，构造一颗新二叉树，且新二叉树根结点的权值为其左右子树根结点权值之和。
3.从集合M中删除被选取的两颗二叉树，并将新二叉树加入该集合。
4.重复2,3步，直到集合M中只剩一颗二叉树为止，则该二叉树即为哈夫曼树。 带权路径长度的计算，我们可以用一个简便的方法，即WPL等于哈夫曼树上非叶子结
点权值之和。
一颗有n个叶子结点的哈夫曼树上共有2n-1个结点，可以采用长度为2n-1的数组顺序存储结点信息。每一个结点应该包括四个域：存放该结点权值weight域，分别存放其左右孩子结点在数组中下标的lchild域和rchild，和记录该结点的父亲结点信息的parent域。
所以我们定义的结点类型如下： typedef struct{ float weight;
int parent,lchild,rchild; }hufmtree;
四、详细设计和编码
基于上述存储结构的哈夫曼算法分析如下：
1.初始化数组tree[2n-1]；读入给定的n个权值，分别放入数组前n个分量的weight域中，并将数组中所有分量的lchild域，rchild域和parent域置0. for(i=0;i 2.从数组的前n个分量中选择权值最小和次小的两个结点（假设下标分别为p1和p2）合并，产生新结点。将新结点的信息存放在第n+1个分量中；新结点的权值weight为这两个结点的权值之和，左右孩子域中的值分别修改为p1和p2；同时，改变下标为p1和p2结点的parent域中的值，使其等于n+1； 3.重复2，每次均从parent域中的值为0的所有结点中选择权值最小和次小的两个结点合并，产生新结点顺次放在weight域值为0的分量中，同时修改该分量的左右孩子域值和被合并的两个结点的parent域值，直到数组的第2n-1个分量的weight域，lchild域和rchild域中的值被修改为止。 该哈夫曼树带权路径的长度：把每次新结点权值weight累加 sum+=tree[i].weight; 五、上机调试过程 在这次程序编写的过程中我把weight定义为float.但是在后面的输出的时候我大意了用了%d导致最后输出的结果变成了0；还有一些括号的配对等这些问题。 六、测试结果及其分析 图一 图二
相关推荐：
loading