《哈夫曼树_数据结构课程设计》由会员分享，可在线阅读，更多相关《哈夫曼树_数据结构课程设计（22页珍藏版）》请在金锄头文库上搜索。
1、 数据结构 课程设计赫夫曼编码/译码器设计指导教师：孙树森、周维达班级：09 数媒（2）班学号：E09700203姓名：林真超1数据结构课程设计实验报告一、题目：赫夫曼编码/译码器设计二、目的：1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。2、熟悉掌握一门计算机语言，可以进行数据算法的设计。三、要求3.1 总体要求1、要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准备工作。尤其是对编程软件的使用有基本的认识。2、既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创新。3、独立按时完成规定的工作任务，不得弄虚作假，不准抄
2、袭他人内容，否则成绩以不及格计。4、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。3.2 实施要求1、理解赫夫曼编码/译码的确切意义。2、独立进行方案的制定，系统结构设计要合理。3、在程序开发时，则必须清楚主要实现函数的目的和作用，需要在程序书写时说明做适当的注释。在写课设报告时，必须要将主要函数的功能和参数做详细的说明。4、通过多组数据来检测该系统的稳定性和正确性。3.3 课程设计报告的内容及要求 在完成课题验收后，学生应在规定的时间内完成课程设计报告一份（不少于 2000 字） 。1一、实验目的1 进一步掌握最优二叉树的含义。2 掌握最优二
3、叉树的结构特征，以及各种存储结构的特点及使用范围。3 熟练掌握哈夫曼树的建立和哈夫曼编码方法。4 掌握用指针类型描述、访问和处理运算。二、实验原理哈夫曼（Huffman）编码属于码词长度可变的编码类，是哈夫曼在 1952 年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“ 编码树”（coding tree ）的技术。算法步骤如下：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。（3）重复
4、第 2 步，直到形成一个符号为止（树），其概率最后等于 1。（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为 1，上分枝赋值为 0。译码的过程是分解电文中字符串，从根出发，按字符“ 0”或“1” 确定找做孩子或右孩子，直至叶子节点，便求得该子串相应的字符。三、实验内容（一）需求分析一个完整的系统应具有以下功能：(1) I：初始化。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。(2) E：编码。利用已建好的哈夫曼树，对文件 ToBeTran 中的正文进行编码，然后2将结果存入文件 CodeFile 中。(3) D：译码。利
5、用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 Textfile 中。(4) P：印代码 文件（Print）.将文件 CodeFile 以紧凑格式显示在终端上，每行 50个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。(5) T：印哈夫曼 树（Treeprinting）.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。（二）实验步骤1.定义结点结构，定义哈夫曼树结构；2.初始化哈夫曼树，存储哈夫曼树信息；3.定义求哈夫曼编码的函数；4.定义译哈夫曼编码的函数；5.写出主函数。6.
6、测试系统。（三）概要设计1 设计思想赫夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。2 函数间的关系函数间的关系如图所示：3主函数显示表头初始化树输入字符编码 译码 打印编码打印赫夫曼树选最小两个权值Select() 图 3.1 函数间的关系3 数据结构与算法设计赫夫曼编译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符 0、1 组成的二进制串，称之为编码。构造一棵赫夫曼树，规定赫夫曼 树中的左分之代表 0，右分支代表 1，则从根节点到每个叶子节点所经过的路径分支组成的 0 和 1 的序列便为该节点对
7、应字符的编码，称之为赫夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出 现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课 用于构造使电文的编码总长最短的编码方案。其主要流程图如图 3.2 所示。4开始结点数是否大于 1将 data 和权值赋给 ht输出根结点和权值调用 SELECT 函数 计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为 0I#include #include #include #include const int UINT_MAX=1000;typede
8、f struct /哈夫曼树的存储表示 int weight; /权值int parent,lchild,rchild; /父节点，左孩子结点，右孩子结点HTNode,* HuffmanTree; /动态分配数组存储哈夫曼树typedef char *HuffmanCode;/动态分配数组存储哈夫曼编码表/-全局变量-HuffmanTree HT; /代表赫夫曼 树HuffmanCode HC; /代表赫夫曼编码int *w,i,j,n; char *z;int flag=0; int numb=0;/ -求赫夫曼编码 -14void line()/画分割线的函数couts2)/ s1 为最小
9、的两个值中序号较小的那个j=s1;s1=s2;s2=j;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)int m,i,s1,s2,start;int c,f;HuffmanTree p;char *cd;if(nweight=*w;/赋权值p-parent=0;p-lchild=0;p-rchild=0;for(;iparent=0; for(i=n+1;inum;/输入结点个数n=num;w=(int*)malloc(n*sizeof(int);/权值z=(char*)malloc(n*sizeof(char)
10、;/字符coutnum2;17*(w+i)=num2;HuffmanCoding(HT,HC,w,n);/调用哈夫曼编码/-打印编码-coutn)coutrchild,HT);if(start-lchild!=NULLcoutweightweight);coprint(HT+start-lchild,HT);numb-;fclose(TreePrint);void printree(HuffmanTree HT,int w) /打印赫夫曼树22HuffmanTree p;p=HT+w;coutchoice;switch(choice)case i: /按下 i 则进行初始化赫夫曼链表,调用 i
11、nit 函数 init(); break;case w: /按下 w 编码字符，调用 inputcode 函数inputcode();break;case e: /按下 e 编码，调用 encode 函数23encode();break;case d: /按下 d 译码，调用 decode 函数decode();break;case p: /按下 p 打印编码，调用 printcode 函数printcode();break;case t: /按下 t 打印赫夫曼树，调用 printree 函数printree(HT,2*n-1);break;case q: /按下 q 退出break;default:cout输入错误， 请重新选择endl;free(z); /释放 z 结点free(w); /释放 w 结点free(HT); /释放 HT 结点24成绩评定表平时成绩答辩成绩最终成绩
