哈夫曼树数据结构课程的设计.doc

合肥学院 计算机科学与技术系 课程设计报告 2013 ～2014 学年第 2 学期 课程 数据结构与算法 课程设计名称 哈夫曼树 学生姓名 宋俊 学号 1204091008 专业班级 12软件工程 指导教师 李红 2014 年 9 月 题目 设计程序以实现构造哈夫曼树的哈夫曼算法。要求：求解所构造的哈夫曼树的带全路径长度。 问题分析和任务定义 这个程序需要我们解决两个问题， 第一个是构造哈夫曼树， 第二个是求带权路径的长度。 本问题的关键就是在于如何建立哈夫曼树 概要设计和数据结构选择 假设给定n个实数w1,w2.....构造拥有n个叶子结点的哈夫曼树，且这n个叶子结点的权值分别为给定的实数，则哈夫曼树的构造方法如下： 根据给定的n个实数，根据n颗单结点二叉树，各二叉树的根权值分别为w1,w2.......，令这n颗二叉树构成一个二叉树的集合M。 在这n颗单结点的二叉树中，这些结点既是根结点又是叶子结点。 在集合M中筛选出两个根结点的权值最小的二叉树作为左右子树，构造一颗新二叉树，且新二叉树根结点的权值为其左右子树根结点权值之和。 从集合M中删除被选取的两颗二叉树，并将新二叉树加入该集合。 重复2,3步，直到集合M中只剩一颗二叉树为止，则该二叉树即为哈夫曼树。 带权路径长度的计算，我们可以用一个简便的方法，即WPL等于哈夫曼树上非叶子结点权值之和。 一颗有n个叶子结点的哈夫曼树上共有2n-1个结点，可以采用长度为2n-1的数组顺序存储结点信息。每一个结点应该包括四个域：存放该结点权值weight域，分别存放其左右孩子结点在数组中下标的lchild域和rchild，和记录该结点的父亲结点信息的parent域。 所以我们定义的结点类型如下： typedef struct{ float weight; int parent,lchild,rchild; }hufmtree; 详细设计和编码 基于上述存储结构的哈夫曼算法分析如下： 初始化数组tree[2n-1]；读入给定的n个权值，分别放入数组前n个分量的weight域中，并将数组中所有分量的lchild域，rchild域和parent域置0. for(i=0;im;i++){ //初始化数组 tree[i].parent=0; tree[i].lchild=0; tree[i].rchild=0; tree[i].weight=0.0; } 从数组的前n个分量中选择权值最小和次小的两个结点（假设下标分别为p1和p2）合并，产生新结点。将新结点的信息存放在第n+1个分量中；新结点的权值weight为这两个结点的权值之和，左右孩子域中的值分别修改为p1和p2；同时，改变下标为p1和p2结点的parent域中的值，使其等于n+1； 重复2，每次均从parent域中的值为0的所有结点中选择权值最小和次小的两个结点合并，产生新结点顺次放在weight域值为0的分量中，同时修改该分量的左右孩子域值和被合并的两个结点的parent域值，直到数组的第2n-1个分量的weight域，lchild域和rchild域中的值被修改为止。 该哈夫曼树带权路径的长度：把每次新结点权值weight累加 sum+=tree[i].weight; 上机调试过程 在这次程序编写的过程中我把weight定义为float.但是在后面的输出的时候我大意了用了%d导致最后输出的结果变成了0；还有一些括号的配对等这些问题。 测试结果及其分析 图一 图二 图三 七、用户使用说明 本程序运行时会有提示语句，根据提示操作。 八、参考文献 [1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。 [2] 其它。 附录 #include stdio.h #define maxval 100.0 typedef struct{ float weight; int parent,lchild,rchild; }hufmtree; void Huffman(hufmtree tree[]){ int i,j,p1,p2; int n,m; float sum=0; //带权路径的长度 float small1,small2,f; puts(请输入叶子结点的数目); scanf(%d,n); m=2*n-1; //n个叶子结点的哈夫曼树上共有2n-1个结点 for(i=0;im;i++){ //初始化数组 tree[i].parent=0; tree[i].lc