哈夫曼树地课程设计报告材料

《哈夫曼树地课程设计报告材料》由会员分享，可在线阅读，更多相关《哈夫曼树地课程设计报告材料（11页珍藏版）》请在装配图网上搜索。

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

2、前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集与频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1二、设计正文1 系统分析1定义一个变量名为HTNode的结构体，用该结构体中的char data、int weight、in

3、t parent、int lchild、int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组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)函数来构造

4、一棵哈夫曼树，首先用一个for(i=0;2*n-1;+)循环将所有2n-1个结点的parent、lchild、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

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

6、亲结点的左孩子结点，如此在hcdi的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 功能详细描述与框图Int I,f,c;i+Hc.start+;multiplexi=0hc.start=n;c=i;inf!=-1Int i;scanf(“%d,&htt.wei+in完毕开始Int k,lnode,mode;Hti.parent=hti.childi+i=nHtlnode,parent=i;Min1=min2=3276

8、7Multiplexi=0;i2*2*n-1i2*n-1i+3、数据结构设计31抽象数据类型定义1树的抽象数据类型定义32模块划分本程序包括三个模块：1主程序模块void main()初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；2哈夫曼模块实现哈夫曼树的抽象数据类型3求哈夫曼编码模块实现求哈夫曼编码算法的数据类型4、主要功能逻辑过程和实现算法41数据类型的定义1哈夫曼树类型typedef struct/构造树 char data;/结点权值 int weight;/权重 int parent;/双亲结点 int lchild;/左孩子 int rchild;/右孩子 HTNode; H

9、TNode ht30;2求哈夫曼编码类型typedef struct char cd30;/存放当前结点的哈弗曼编码 int start;/cdstartcdn存放哈弗曼码 HCode; HCode hcd30;42主要模块的算法描述1主函数int main() int n; printf(请输入要输入的字符数量n:);/读入字符的个数 while(scanf(%d,&n),n!=-1)/初始化 printf(请输入n个字符和n个权值n); CodeInput(n,ht);/输入数据函数，将读入n个字符和权重 CreateHT(ht,n);/构造哈弗曼树 CreateHCode(ht,hcd,

10、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=hti.lchild=hti.rchild=-1; for (i=n;i2*n-1;i+)/构造哈弗曼树 min1=min2=32767;/lnode和rnode为最小权值的两个结点位置 lnode=rnode=-1

11、; for (k=0;k=i-1; k+)/在ht中查找权值的最小的两个结点 if (htk.parent=-1)/只在未构造的二叉树结点中查找 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=

12、rnode;/ht为双亲结点 3利用哈夫曼编码算法哈夫曼编码void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for(i=0; in; i+)/根据哈弗曼树求哈弗曼编码 hc.start=n; c=i; f=hti.parent; while (f!=-1)/循环知道树的根结点 if(htf.lchild=c) hc.cdhc.start-=0;/处理左孩子结点 else hc.cdhc.start-=1;/处理右孩子结点 c=f; f=htf.parent; hc.start+;/start指向哈弗曼编码最开始的

13、位置 hcdi=hc; 5、界面设计6、系统测试测试数据与结果如下：04F1 C6 H3E101010107 I2 D0110 B5 G01三、小组成员分工说明独立完成四、课程设计总结或结论1 课程设计过程中出现的技术难点和解决方法：1.1技术难点。（1） 输入的字符个数不确定，可跟据情况输入。（2） 哈夫曼树的类型。（3） 哈夫曼编码类型。（4） 构造哈夫曼树算法。（5） 计算哈夫曼编码算法。1.2解决方法。1通过向教师虚心学习请教.2和同学们细心交流，认真讨论。3上网参考，吸取别人的精华。2 课程设计期间的主要收获：通过这次课程设计使我充分的理解了用哈夫曼树再编码问题中根本原理的应用，知道

14、了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编码问题的程序。虽然此次的程序不是很完备，但是总体还是一个比拟能表现数据结构知识点的程序，当然只是相对于我这个学者来说。在刚开始编程的时候，我感到很茫然，无从下手。但是困难是可以解决的，只要通过努力，向教师虚心学习请教，再难的题目也可以自己动手完成。通过这次的数据结构课程设计，我也深刻了解到这门学问的博大精深，要积极进取，不断学习，不断积累知识。同时也认识到自己的不足和缺点，做什么事都需要细心和耐心，并坚持下去，这样才有一个比拟满意的成果。在此我非常感谢的是我的指导教师，感谢教师的细心认真的辅导，让我对数据结构这门课程有了更深刻的认识，同时我还要感谢帮助过我的同学，没有他们的帮助我不肯能完成这样顺利，谢谢！