哈夫曼树的课程设计报告

上传人:公**** 文档编号:431961170 上传时间:2024-01-16 格式:DOC 页数:9 大小:204.50KB
返回 下载 相关 举报
哈夫曼树的课程设计报告_第1页
第1页 / 共9页
哈夫曼树的课程设计报告_第2页
第2页 / 共9页
哈夫曼树的课程设计报告_第3页
第3页 / 共9页
哈夫曼树的课程设计报告_第4页
第4页 / 共9页
哈夫曼树的课程设计报告_第5页
第5页 / 共9页
点击查看更多>>
资源描述

《哈夫曼树的课程设计报告》由会员分享,可在线阅读,更多相关《哈夫曼树的课程设计报告(9页珍藏版)》请在金锄头文库上搜索。

1、数据结构与算法课程设计报告书题目:哈夫曼编码 / 译码器班级:学号:姓名:田欢指导教师:龚丹周期: 2011-12-19至 2011-12-23成绩:年月日一、课程设计的目的与要求(一)课程设计目的与任务(参考已发文档自行编辑,但不少于100 字)设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,到选择退出为止。利用哈夫曼树编码问题基本原理的应用,撑握对树的不同存储结构的定义和算法描述。学会构造哈夫曼树和哈夫曼编码等主要算法。(二)题目要求1)? 将权值数据存放在数据文件( 文件名为data.txt,位于执行程序的当前目直录中 )2)? 分别采用动态和静态存储结构3)? 初始化

2、:键盘输入字符集大小n、 n 个字符和n 个权值,建立哈夫曼树;4)? 编码:利用建好的哈夫曼树生成哈夫曼编码;5)? 输出编码;6)? 设字符集及频度如下表:字符空格 ABCDEFGHIJKLM频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 NOPQRSTUVWXYZ频度二、设计正文1 系统分析( 1)定义一个变量名为HTNode的结构体,用该结构体中的char data 、 intweight 、 int parent 、 int lchild、 int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子,再定义一个H

3、TNode类型的数组 ht30存放哈夫曼树;另外定义一个变量名为HCode 的结构体,采用HCode 类型变量的cdstartcdn存放当前结点的哈夫曼编码、最后定义一个HCode 类型的数组hcd30 的数组用于存放当前叶子结点hti 的哈夫曼编码。( 2)编写 CodeInput(n,ht)函数并在函数中设置一个for(i=0;n;+)循环,首先输入 n 个字符,再利用函数中的for(i=0;n;+)循环实现对这n 个字符的权值的输入。( 3)编写 CreateHT(ht,n)函数来构造一棵哈夫曼树,首先用一个for(i=0;2*n-1;+)循环将所有2n-1 个结点的 parent 、l

4、child、rchild域均置初值为 -1 ;再用一个 for(i=n;2*n-1;+)循环来构造哈夫曼树,在该循环中首先令lnode 和 rnode 为最小权值的两个结点位置且其域值均为-1 ,再用一个for(k=0;=i-1;k+)循环在数组 ht30中寻找权值最小的两个结点并且只能在尚未构造二叉树的结点中查找,由于只能在尚未构造二叉树的结点中查找,因此在for(k=0;k=i-1;k+)循环中加入一个if(htk.parent=-1)语句来判断结点lnode 和 rnode 是否已经在二叉树中,如果结点lnode 和 rnode 在二叉树中,则结点 lnode 和 rnode的 pare

5、nt 的值为其双亲结点在数组 ht30中的序号就不会为 -1了,在查找到htlnode和 htrnode后将他们作为hti的左右子树, htlnode和 htrnode 的双亲结点置为 hti ,且 hti.weight=htlnode.weight+htrnode.weight。如此处理下去,直到所2n-1 个结点处理完毕。( 4)编写 CreateHCode(ht,hcd,n) 函数来求哈夫曼编码,由于求哈夫曼编码只需求叶子结点的哈夫曼编码。对于当前叶子结点hti,首先将对应的哈夫曼编码 hcdi 的 start域值置初值 n,找其双亲结点htf ,若当前结点是双亲结点的左孩子结点,则在h

6、cdi的 cd 数组中添加0,若当前结点是双亲的右孩子结点,则在 hcdi 的 cd 数组中添加 1,将 start域减 1。再对双亲结点进行同样的操作,直到无双亲结点为止, 最后让 start 指向哈夫曼编码最开始字符。因此在函数中设置一个 for(i=0;in;i+)循环,在循环中设置一个while(f!=-1)循环语句来判断循环是否到了根结点, 再在 while(f!=-1)中设置一个 if(htf.lchild=c)语句来判断该处理左孩子结点还是该处理右孩子结点。最后用这个for(i=0;in;i+)循环来根据哈夫曼树求出哈夫曼编码。( 5)最后编写 CodeOutput(n,hcd)

7、函数,首先利用for(i=0;in;i+)循环和for(j=hcdi.start;j=n;j+)循环来实现所有字符的哈夫曼编码的输出;再利用for(i=0;in;i+)循环和 for(j=hcdi.start;j=n;j+)循环来实现每个字符的序号和哈夫曼编码的输出。2 功能详细描述及框图( 1)主函数流程图如图2.1开始Int i;inscanf( “%d”,&htti+结束图 2.1 主函数流程图( 2)哈夫曼编码算法流程图,如图2.2( 3)构造树函数流程图,如图2.3Int I,f,c;i=0inhc.start=n;c=i;f!=-1multiplexHc.start+;i+图 2.

8、2 哈夫曼编码算法流程图Int k,lnode,mode;i=0;i2*n-1Hti.parent=htii+i=ni2*2*n-1Min1=min2=32767MultiplexHtlnode,parent=ii+图 2.3 构造树函数流程图3、数据结构设计3 1 抽象数据类型定义( 1)树的抽象数据类型定义3 2 模块划分本程序包括三个模块:( 1)主程序模块void main()初始化;构造哈夫曼树;求哈夫曼编码;哈夫曼编码输出;( 2)哈夫曼模块实现哈夫曼树的抽象数据类型( 3)求哈夫曼编码模块实现求哈夫曼编码算法的数据类型4、主要功能逻辑过程和实现算法4 1 数据类型的定义( 1)哈

9、夫曼树类型typedef struct/char data;/int weight;/int parent;/int lchild;/int rchild;/HTNode;HTNode ht30;构造树结点权值权重双亲结点左孩子右孩子( 2)求哈夫曼编码类型typedef structchar cd30;/存放当前结点的哈弗曼编码int start;/cdstartcdn存放哈弗曼码HCode;HCode hcd30;4 2 主要模块的算法描述( 1)主函数int main()int n;printf(请输入要输入的字符数量n:);/读入字符的个数while(scanf(%d,&n),n!=-

10、1)/初始化printf(请输入 n 个字符和n 个权值 n);CodeInput(n,ht);/输入数据函数,将读入CreateHT(ht,n);/构造哈弗曼树CreateHCode(ht,hcd,n);/哈弗曼编码算法n 个字符和权重CodeOutput(n,hcd);/打印哈弗曼编码将打印出编码,和每一个字符的编码return 0;( 2)构造哈夫曼树void CreateHT(HTNode ht,int n)/ 构造一棵哈夫曼树int i,k,lnode,rnode;int min1,min2;for (i=0;i2*n-1;i+)/ 所有结点的相关域置初值 -1 hti.parent

11、=hti.lchild=hti.rchild=-1;for (i=n;i2*n-1;i+)/构造哈弗曼树min1=min2=32767;/lnode和rnode为最小权值的两个结点位置lnode=rnode=-1;for (k=0;k=i-1; k+)/if (htk.parent=-1)/在ht中查找权值的最小的两个结点只在未构造的二叉树结点中查找if (htk.weightmin1)min2=min1;rnode=lnode;min1=htk.weight; lnode=k;else if (htk.weightmin2)min2=htk.weight; rnode=k;htlnode.parent=i; htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode; hti.rchild=rnode;/ht为双亲结点( 3)利用哈夫曼编码算法哈夫曼编码voi

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 幼儿/小学教育 > 幼儿教育

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号