数据结构课程设计——赫夫曼编码

《数据结构课程设计——赫夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计报告课程设计名称：数据结构课程设计课程设计题目：哈夫曼编码问题院（系）：专业：班级：学号：姓名：指导教师：目录目录1课程设计介绍11.1课程设计内容与要求11.2课程设计分析与描述12系统功能模块结构图及功能介绍22.1系统功能模块结构图22.2模块功能介绍32.2.1统计频数32.2.2建树32.2.3生成编码33使用的数据结构的描述43.1栈43.2二叉树54主要函数的描述及流程图64.1creatHuffamnTree()（创建哈夫曼树）64.2huffmanCode()（生成哈夫曼编码）75程序的测试与运行8参考文献10附录（关键部分程序清单）1113第

2、1章课程设计介绍1课程设计介绍1.1课程设计内容与要求利用哈夫曼编码来解决由A、B、C、D四个字符组成的字符串子啊压缩时产生的译码二义性问题，对字符串进行编码时，其中任一字符的编码都不能是其他字符的前缀。即要求编码为前缀编码。实现：1：创建哈夫曼树的结构；2：生成哈夫曼编码；要求：1：使用C语言或其他面向对象语言实现；2：按要求写出课程设计报告；1.2课程设计分析与描述根据问题的要求，我们需要做以下的工作：1．录入一字符串，统计A、B、C、D四个字符在字符串中出现的频数，把它当作字符的权值；2．根据四个字符各自的权值建立哈夫曼树；3．根据已建立的哈夫曼树生成每个字符的哈

3、夫曼编码；13第2章系统功能模块结构图及功能介绍2系统功能模块结构图及功能介绍2.1系统功能模块结构图本系统含有统计频数、建树、生成编码四个模块，各模块之间的关系如下图1所示：统计频数建树生成编码图1：模块图13第2章系统功能模块结构图及功能介绍2.2模块功能介绍2.2.1统计频数在给定的字符串中统计A、B、C、D四个字符在其中出现的频数，并且把它作为该字符的权值；2.2.2建树根据各个字符的权值根据哈夫曼算法建立哈夫曼树；2.2.3生成编码根据建立的哈夫曼树，生成哈夫曼编码；13第3章使用的数据结构的描述3使用的数据结构的描述3.1栈栈的顺序存储表示：typedefs

4、truct{SElemType*base;//栈底SElemType*top;//栈顶intstacksize;//栈的容量}SqStack;栈的用法说明：栈又称为后进先出的线性表（LIFO结构），特点如下图2所示：出栈进栈栈顶栈底图2：栈的示意图13第3章使用的数据结构的描述3.2二叉树二叉树的二叉链表存储表示：typedefstructBiTNode{intdata;//数据域structBiTNode*lchild,*rchild;//左、右孩子}BiTNode,*BiTree;二叉树的用法说明：二叉树是一种树型结构，特点是每个结点至多只有两棵子树（即二叉树中不存

5、在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能颠倒。如下图3：BACDE图3：二叉树的示意图13第4章主要函数的描述与流程图4主要函数的描述及流程图4.1creatHuffamnTree()（创建哈夫曼树）集合F：根据给定的n个权值{w1,w2,.....wn}构成n棵二叉树的集合F={T1,T2,…..Tn}，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子开始F中只含一棵树结束T在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树的根节点的权值之和F在F中删除这两棵树，同时将新得到的二叉树加

6、入F中图4:创建哈夫曼树的流程图树均空。创建哈夫曼树的流程如下图4所示：13第4章主要函数的描述与流程图4.2huffmanCode()（生成哈夫曼编码）创建一空栈S，让T指向哈夫曼树的根节点。生成哈夫曼编码的流程如下图5所示：开始T==NULL结束T->lchild==NULL&&T->rchild==NULL从栈底到栈顶依次输出栈中的元素，得到该结点所对应字符的前缀编码将0入栈huffmanCode（T->lchild）将1入栈huffmanCode（T->lchild）TFFT出栈图5：生成哈夫曼编码的流程图13第5章程序测试与运行5程序的测试与运行1.程序开始界

7、面（如下图6所示）：图6：开始界面2.程序的输入（如图7所示）：输入一个只含A、B、C、D四个字符的字符串，回车结束。图7：输入界面3.程序的运行（如下图8、9所示）：13第5章程序测试与运行图8：运行界面1图9：运行界面213参考文献参考文献[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007[2]戴艳等.零基础学算法（第二版）北京：机械工业出版社，2012.2[3]谭浩强.C语言程序设计（第三版）北京：清华大学出版社，2005[4]张清国.C语言程序设计教程（第二版）.北京：清华大学出版社，2009[5]张长海.C语言