精品资料(2021-2022年收藏)课程设计报告.doc
《精品资料(2021-2022年收藏)课程设计报告.doc》由会员分享,可在线阅读,更多相关《精品资料(2021-2022年收藏)课程设计报告.doc(6页珍藏版)》请在三一文库上搜索。
1、合肥学院计算机科学与技术系课程设计报告20132014学年第二学期课程数据结构与算法课程设计名称哈弗曼算法专业班级12级软件工程指导教师李红2014年9月题目:设计程序以实现构造哈夫曼树的哈夫曼算法。要求:求解所构造的哈夫曼树的带全路径长度。一、问题分析和任务定义根据要求需要:1、规划哈夫曼树的数据类型; 2、完成对哈夫曼树的输入; 3、构造出哈夫曼树; 4、求出哈夫曼树的带权路径长度; 5、输出哈夫曼树的结点信息。二、数据结构的选择和概要设计数据结构的选择:1. 由于一棵有n个叶子结点的哈夫曼树上共有2n-1个结点,可以采用为2n-1的数组顺序存储结点信息。每个结点包括四个域:一个float
2、类型的weight用来存储每个叶子结点的权值,三个int 类型的parent,rchild,lchild用来表示结点的父节点和左右孩子;结点的类型描述为:typedef struct float weight;int parent,lchild,rchild;hufm;若给定n个权值,则可定义数组tree来存储哈夫曼树上的结点:Hufm tree2n-1;为实现上述功能需要:1. 首先给定n个叶子结点的权值,构造n棵单结点二叉树;2. 在上面的二叉树中选择两个权值最小的结点,分别为左右孩子构造一棵新的二叉树且新的二叉树根结点的权值为其左右子树根结点的权值之和。3. 然后删除掉被选取的两棵二叉树
3、,并将新的二叉树加入。4. 重复2,3两步,直到只剩一颗二叉树为止。5. 由于哈夫曼树的带权路径长度就是等于所有非叶子结点值的和,因为树的带权路径长度是通过将所有叶子结点乘以对应的路径长度之和求出来的,而将所有的非叶子结点的累加过程就是包括了上述的计算,所以直接就可以计算出。三、详细设计和编码 1、程序先输入一个int的n表示共有n个叶子结点,然后输入n个叶子结点的权值;同时将数组内的所有值都初始化为-1; 2、根据概要设计的方法来构造哈夫曼树,将新的父节点放在数组下标为n到2n-2中,所以进行一个外层循环,为确保每次能够找到未含有父结点的权值最小的两个结点,需要定义两个整型的数,small1
4、,small2,在每次比较之前将一个最大值赋给它们,然后进行比较,在一个内层的循环进行,如果找到一个比small1小的结点,就先把small1赋给small2然后,在将这个结点的权值赋给small1,同时类似的用两个整型的数记录这个结点的下标;然后再每次内层循环结束后,将这两个叶子结点的parent值改为这个父节点的下标,将父节点的左右孩子域改为两个孩子结点的下标,将父节点的权值weight变成两个孩子的权值之和。 3、定义一个float类型的sum,初始化为0,然后在每次产生新结点的权值时,就将其累加,其为哈夫曼树的带权路径长度。 4、最后将构造好的哈夫曼树输出在屏幕上,并且输出带权路径长度
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精品 资料 2021 2022 收藏 课程设计 报告
链接地址:https://www.31doc.com/p-14903412.html