当前位置: 首页 > >

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

发布时间:

计算机科学与技术系 课程设计报告 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<m;i++){ //初始化数组 tree[i].parent=0; tree[i].lchild=0; tree[i].rchild=0; tree[i].weight=0.0; } 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;还有一些括号的配对等这些问题。 六、测试结果及其分析 图一 图二 图三 七、用户使用说明 本程序运行时会有提示语句,根据提示操作。 八、参考文献 [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;i<m;i++){ //初始化数组 tree[i].parent=0; tree[i].lchild=0; tree[i].rchild=0; tree[i].weight=0.0; } printf(请输入%d 个权值\n,n); for(i=0;i<n;i++){ //读入前 n 个结点的权值 scanf(%f,&f); tree[i].weight=f; } for(i=n;i<m;i++){ //进行 n-1 次合并,产生 n-1 个新结点 p1=p2=0; small1=small2=maxval; for(j=0;j<=i-1;j++){ //选出两个权值最小的根结点 if(tree[j].parent==0) if(tree[j].weight<small1){ //查找最小权, 并用 p1 记录其下标 small2=small1; small1=tree[j].weight; p2=p1; p1=j; } else if(tree[j].weight<small2){ //查找次小权,并 用 p2 记录下标 small2=tree[j].weight; p2=j;



友情链接: