1、 哈夫曼编码哈夫曼编码与与译码译码 学生姓名：学生姓名： 指导老师：指导老师： 摘 要 本课程设计主要解决的是利用哈夫曼树生成的哈夫曼编码进行字符串的加密 和解密，并将加密的编码写入文件。在此课程设计中，系统开发平台为 Windows XP， 程序设计语言采用面向过程的高级语言 C 和面向对象的高级语言 C+， 程序运行平台为 Visual C+ 6.0。在程序设计中，采用了结构化与面向过程两种解决问题的方法。程序通 过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实 际问题。 关键词 哈夫曼树，编码，译码，文件操作，C，C+； 1 1 引引 言言 1.1 1.1 课
2、题背景课题背景 随着信息时代的到来，各种信息日益丰富，信息迅速膨胀，对信息管理的工作量也 日益增大。在信息化未到来之前，信息的存储编码也变得尤为重要，公司之间的信息需 要编码，用户个人数据需要编码，都需要占用很大的空间，所以一个好的、高效的编码 译码算法是十分重要的。好的加密算法不仅可以降低管理方的工作量和存储量，还可以 对用户的信息进行高效的管理，同时使在用中可以避免不必要的麻烦。 数据结构是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结 构分为逻辑结构和存储结构。 数据的逻辑结构(logical structure)是指数据元素之间逻辑关 系的整体。所谓逻辑关系是指数据元素
3、之间的关联方式或邻接关系。根据数据元素之间 逻辑关系的不同，数据结构分为四类：集合、线性结构、树结构、图结构。数据的逻辑 结构属于用户视图，是面向问题的，反映了数据内部的构成方式。为了区别于数据的存 储结构，常常将数据的逻辑结构称为数据结构。数据的存储结构(storage structure)又称 为物理结构，是数据及其逻辑结构在计算机中的表示，换言之，存储结构除了数据元素 之外，必须隐式或显示地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存 储结构和链接存储结构。 树是一种在实际应用中被广泛使用的数据结构。它是由同一类型的记录构成的集 合。哈夫曼树是树的一种子类型，又称最优树，是一类
4、带权路径最短的树，利用哈夫曼 树可以得到合适的字符编码， 这样我们既可以对数据加密， 也可以实现高效的存储信息。 因此哈夫曼编码是一种常用的编码方式。 1.2 1.2 课程设计目的课程设计目的 哈夫曼编码与译码系统是为了实现信息的高效存储与管理、加密、解密而设计的。 通过建立一个有效，低存储量，易于管理的编码译码系统，使得企业对信息管理更加高 效、准确，更加科学化和正规化，降低企业对信息管理的难度。 本课程设计主要是用数据结构和文件实现的，通过程序的编写、调试和运行可以进 一步掌握数据结构及算法的程序实现的基本方法。理解对数据结构的基本知识及应用， 同时加深对哈夫曼树的运用及理解。本课程设计是
5、利用哈夫曼编码实现对字符串的加 密、解密和低存储量存储，程序实现哈夫曼树的建立和哈夫曼编码的生成，实现字符串 的快速编码、解密和保存。掌握哈夫曼编码的工作原理，熟悉建立哈夫曼树、利用哈夫 曼编码进行实际编码、解码等功能的实现，同时加深对文件的操作原理。 1.3 课程设计内容课程设计内容 本课程设计主要是采用哈夫曼编码对字符串的编码、 解码， 同时实现地存储量要求。 在设计的过程中，共用到两种数据元素，第一种是哈夫曼树建立是用到树的结构，树节 点信息包括父节点、左子树节点、右子树节点以及该节点的权值其信息如图 1-1 所示， 第二种是在存储个字符对应编码时用到的结构，其中包括字符、字符密文以及其
6、长度， 如图 1-2 所示： 图图 1 1- -1 1 树节点数据元素树节点数据元素 图图 1 1- -2 2 每个字符密文数据元素每个字符密文数据元素 程序功能是实现对用户输入信息的编码与解码， 并存入文件中， 具体如图 1-3 所示： 树节点信息 父节点 左子树节点 右子树节点 权值 编码信息 字符 编码 编码长度 图图 1 1- -3 3 功能模块图功能模块图 哈夫曼编码与译码 对 用 户 输 入 字 符 串 编 码 解 码 利 用 字 符 和 权 值 建 立 哈 夫 曼 树 得 到 哈 夫 曼 编 码 将 编 码 存 入 文 件 保 存 输 入 字 符 串 或 字 符 及 权 值 信 息 2 2 设计思路与方案设计思路与方案 2.1 2.1 设计思路设计思路 C 语言是结构化和模块化的语言，它是面向过程的。在处理较小规模的程序时，程 序员用 C 语言还比较得心应手。 C+是由 C 语言发展而来的，与 C 语言兼容。用 C 语言编写的程序基本上可以不 加修改地用于 C+。从 C+的名字可以看出它是 C 的超集。C+
