数据结构课程设计

合肥学院。计算机科学与技术系。

课程设计报告。

2013 ～2014 学年第 2 学期。

2014 年 9 月。

1、题目。设计程序以实现构造哈夫曼树的哈夫曼算法。要求：求解所构造的哈夫曼树的带全路径长度。

2、问题分析和任务定义。

这个程序需要我们解决两个问题，第一个是构造哈夫曼树，第二个是求带权路径的长度。

本问题的关键就是在于如何建立哈夫曼树。

3、概要设计和数据结构选择

假设给定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

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;

5、上机调试过程。

在这次程序编写的过程中我把weight定义为float.但是在后面的输出的时候我大意了用了%d导致最后输出的结果变成了0；还有一些括号的配对等这些问题。

6、测试结果及其分析。

图一。图二

图三。七、用户使用说明。

本程序运行时会有提示语句，根据提示操作。

八、参考文献。

[1] 王昆仑，李红。数据结构与算法。北京：中国铁道出版社，2024年5月。

[2] 其它。

9、附录。#include ""

#define maxval 100.0

typedef struct

printf("请输入%d个权值",n);

for(i=0;i scanf("%f",&f);

tree[i].weight=f;

for(i=n;i p1=p2=0;

small1=small2=maxval;

for(j=0;j<=i-1;j选出两个权值最小的根结点。

if(tree[j].parent==0)

if(tree[j].weightsmall2=small1;

small1=tree[j].weight;

p2=p1;

p1=j;else if(tree[j].weightsmall2=tree[j].weight;p2=j;

tree[p1].parent=tree[p2].parent=i;

tree[i].weight=tree[p1].weight+tree[p2].weight;

sum+=tree[i].weight求带权路径。

tree[i].lchild=p1;

tree[i].rchild=p2;

printf("哈夫曼树为： parent lchild rchild weight");

for(i=0;i<2*n-1;i++)

printf(" d %d %d %.2f",tree[i].parent,tree[i].lchild,tree[i].rchild,tree[i].weight);

printf("带权路径长度为：%.2f",sum);

int main()

hufmtree tree[100];

huffman(tree);

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了