数据结构 基于哈夫曼树的知识进行编码和译码 课程设计 实验报告.doc

数 据 结 构 课 程 设 计 设计题目： 基于哈夫曼树的知识进行编码和译码 课题名称 基于哈夫曼树的知识进行编码和译码 院 系 年级专业 学 号 姓 名 成 绩 课题设计 目的与 设计意义 1、课题设计目的：在当今这个科技飞速发展的时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用和广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定，指向左子树的分支表示为‘0’码，指向右子树的分支表示为‘1’码。取每条路径上的‘0’或‘1’所排成的序列作为和各个对应字符的编码，称为哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码或译码。电报通信时传递文字的二进制码形式的字符串。但在传递信息时总希望总长度尽可能最短，即采用最短码。 2、课题设计意义：作为学计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，消化课堂所讲解的内容；通过积累调试程序的经验逐渐培养的编程能力、用计算机解决实际问题的能力。目 录 一：课程设计的目的及意义 - 1 - 二：需求分析 - 1 - 三：项目设计 - 2 - （1）设计思路及方案： - 2 - （2）模块的设计及介绍 - 3 - （3）模块图及流程图 - 6 - 四：系统实现 - 7 - （1）主调函数 - 7 - （2）建立哈夫曼树 - 7 - （3）对哈夫曼树进行编码 - 9 - (4) 对哈夫曼树进行译码 - 10 - 五：系统调试 - 11 - (1) 进入主界面 - 11 - （2）建立哈夫曼树 - 11 - （3）对哈夫曼树进行编码 - 12 - （4）对哈夫曼树进行译码 - 12 - 六：实验总结 - 13 - 附录 源程序 - 14 - 参考文献： - 18 - 一：课程设计的目的及意义 1、课题设计目的：在当今这个科技飞速发展的时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用和广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定，指向左子树的分支表示为‘0’码，指向右子树的分支表示为‘1’码。取每条路径上的‘0’或‘1’所排成的序列作为和各个对应字符的编码，称为哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码或译码。电报通信时传递文字的二进制码形式的字符串。但在传递信息时总希望总长度尽可能最短，即采用最短码。 2、课题设计意义：作为学计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，消化课堂所讲解的内容；通过积累调试程序的经验逐渐培养的编程能力、用计算机解决实际问题的能力。a：1010 b：00 c：10000 d：1001 e：11 f：10001 g：01 h：1011 对字符串进行译码： 输入二进制编码：11 您输入的编码对应的字符为：e 按‘0’退出 Press any key to continue 三：项目设计 （1）设计思路及方案： 本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码的功能。假设每种字符出现在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为（W1*L1）+（W2*W2）+…（Wi*Li）。若将此对应到二叉树上，Wi为叶子结点，Li为叶子结点到根结点的路径长度。那么，（W1*L1）+（W2*W2）+…（Wi*Li）恰好为二叉树上带权路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一颗哈夫曼树，此构造过程称为哈夫曼编码。 该项目设计将实现以下几项功能：1：构造哈夫曼树 2：对哈夫曼树进行编码 3：对哈夫曼树进行译码。 （2）模块的设计及介绍 #includestdio.h typedef struct { 结构体定义； }hufmtree; hufmtree tree[20]; typedef struct { 初始化； }codetype; codetype code[20]; void HUFM