课程设计报告

合肥学院计算机科学与技术系课程设计报告20132014学年第二学期课程数据结构与算法课程设计名称哈弗曼算法专业班级12级软件工程指导教师李红2014年9月题目：设计程序以实现构造哈夫曼树的哈夫曼算法。要求：求解所构造的哈夫曼树的带全路径长度。一、问题分析和任务定义根据要求需要：1、规划哈夫曼树的数据类型； 2、完成对哈夫曼树的输入； 3、构造出哈夫曼树； 4、求出哈夫曼树的带权路径长度； 5、输出哈夫曼树的结点信息。二、数据结构的选择和概要设计数据结构的选择：1. 由于一棵有n个叶子结点的哈夫曼树上共有2n-1个结点，可以采用为2n-1的数组顺序存储结点信息。每个结点包括四个域：一个float类型的weight用来存储每个叶子结点的权值，三个int 类型的parent,rchild,lchild用来表示结点的父节点和左右孩子；结点的类型描述为：typedef struct float weight;int parent,lchild,rchild;hufm;若给定n个权值，则可定义数组tree来存储哈夫曼树上的结点：Hufm tree2n-1；为实现上述功能需要：1. 首先给定n个叶子结点的权值，构造n棵单结点二叉树；2. 在上面的二叉树中选择两个权值最小的结点，分别为左右孩子构造一棵新的二叉树且新的二叉树根结点的权值为其左右子树根结点的权值之和。3. 然后删除掉被选取的两棵二叉树，并将新的二叉树加入。4. 重复2,3两步，直到只剩一颗二叉树为止。5. 由于哈夫曼树的带权路径长度就是等于所有非叶子结点值的和，因为树的带权路径长度是通过将所有叶子结点乘以对应的路径长度之和求出来的，而将所有的非叶子结点的累加过程就是包括了上述的计算，所以直接就可以计算出。三、详细设计和编码 1、程序先输入一个int的n表示共有n个叶子结点，然后输入n个叶子结点的权值；同时将数组内的所有值都初始化为-1； 2、根据概要设计的方法来构造哈夫曼树，将新的父节点放在数组下标为n到2n-2中，所以进行一个外层循环，为确保每次能够找到未含有父结点的权值最小的两个结点，需要定义两个整型的数，small1,small2，在每次比较之前将一个最大值赋给它们，然后进行比较，在一个内层的循环进行，如果找到一个比small1小的结点，就先把small1赋给small2然后，在将这个结点的权值赋给small1，同时类似的用两个整型的数记录这个结点的下标；然后再每次内层循环结束后，将这两个叶子结点的parent值改为这个父节点的下标，将父节点的左右孩子域改为两个孩子结点的下标，将父节点的权值weight变成两个孩子的权值之和。 3、定义一个float类型的sum，初始化为0，然后在每次产生新结点的权值时，就将其累加，其为哈夫曼树的带权路径长度。 4、最后将构造好的哈夫曼树输出在屏幕上，并且输出带权路径长度。四、上机调试过程开始由于没有想到求带权路径长度可以通过上述方法进行，所有还需要在树建好以后进行每个叶子结点求其路径长度，这大大的增加了程序的时间复杂性，最后将其改进。五、测试结果及其分析程序的一开始是将结构体中的元素都初始化为0，但是由于为了更加清晰的表示出构造哈弗曼树的各个结点关系，防止与数组下标为0的进行混淆，将其初始化为-1。图中清晰的表示出了各个结点的信息，其中数组下标为0n的为叶子结点，其lchild与rchild都是-1；weight记录各个结点的权值，parent中的数字为每个结点的父节点所在的元素下标，lchild与rchild分别为其左右孩子的下标。六、用户使用说明 根据屏幕中的提示，先输入叶子结点的个数，然后输入n个叶子结点的权值，其可以为实数，然后回车就可以看到结果了。七、参考文献1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。2 其它。八、附录#include stdio.h#define max 100.0typedef struct float weight;int parent,lchild,rchild;hufm;int main()/p1,p2分别记录相加后节点的两个孩子的位置int n,i,j,p1,p2;float sum=0;hufm tree100;float small1,small2;/用于得到parent为0的两个最小的puts(请输入叶子节点的个数);scanf(%d,&n);for(i=0;i2*n-1;i+)treei.parent=-1;treei.lchild=-1;treei.rchild=-1;puts(请输入哈夫曼树的权值);for(i=0;in;i+)scanf(%f,&treei.weight);for(i=n;i2*n-1;i+)p1=p2=0;small1=small2=max;for(j=0;j=i-1;j+)if(treej.parent=-1) if(treej.weightsmall1) small2=small1; small1=treej.weight; p2=p1;p1=j; else if(treej.weightsmall2) small2=treej.weight; p2=j; treep1.parent=treep2.parent=i; treei.weight=treep1.weight+treep2.weight; sum+=treei.weight;/求树的带权路径长度 treei.lchild=p1; treei.rchild=p2;printf(输出该哈夫曼树的各个结点的值为：n);printf( weight parent lchild rchildn);for(i=0;i2*n-1;i+)pr