课程的设计哈夫曼编码与译码.doc

哈夫曼编码译码 数据结构是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据的逻辑结构(logical structure)是指数据元素之间逻辑关系的整体。所谓逻辑关系是指数据元素之间的关联方式或邻接关系。根据数据元素之间逻辑关系的不同，数据结构分为四类：集合、线性结构、树结构、图结构。数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式。为了区别于数据的存储结构，常常将数据的逻辑结构称为数据结构。数据的存储结构(storage structure)又称为物理结构，是数据及其逻辑结构在计算机中的表示，换言之，存储结构除了数据元素之外，必须隐式或显示地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和链接存储结构。 树是一种在实际应用中被广泛使用的数据结构。它是由同一类型的记录构成的集合。哈夫曼树是树的一种子类型，又称最优树，是一类带权路径最短的树，利用哈夫曼树可以得到合适的字符编码，这样我们既可以对数据加密，也可以实现高效的存储信息。因此哈夫曼编码是一种常用的编码方式。 1.2 课程设计目的 哈夫曼编码与译码系统是为了实现信息的高效存储与管理、加密、解密而设计的。通过建立一个有效，低存储量，易于管理的编码译码系统，使得企业对信息管理更加高效、准确，更加科学化和正规化，降低企业对信息管理的难度。 本课程设计主要是用数据结构和文件实现的，通过程序的编写、调试和运行可以进一步掌握数据结构及算法的程序实现的基本方法。理解对数据结构的基本知识及应用，同时加深对哈夫曼树的运用及理解。本课程设计是利用哈夫曼编码实现对字符串的加密、解密和低存储量存储，程序实现哈夫曼树的建立和哈夫曼编码的生成，实现字符串的快速编码、解密和保存。掌握哈夫曼编码的工作原理，熟悉建立哈夫曼树、利用哈夫曼编码进行实际编码、解码等功能的实现，同时加深对文件的操作原理。 1.3课程设计内容 本课程设计主要是采用哈夫曼编码对字符串的编码、解码，同时实现地存储量要求。在设计的过程中，共用到两种数据元素，第一种是哈夫曼树建立是用到树的结构，树节点信息包括父节点、左子树节点、右子树节点以及该节点的权值其信息如图1-1所示，第二种是在存储个字符对应编码时用到的结构，其中包括字符、字符密文以及其长度，如图1-2所示：  图1-1 树节点数据元素 图1-2 每个字符密文数据元素 程序功能是实现对用户输入信息的编码与解码，并存入文件中，具体如图1-3所示： 图1-3 功能模块图2 设计思路与方案 2.1 设计思路 C语言是结构化和模块化的语言，它是面向过程的。在处理较小规模的程序时，程序员用C语言还比较得心应手。 C++是由C语言发展而来的，与C语言兼容。用C语言编写的程序基本上可以不加修改地用于C++。从C++的名字可以看出它是C的超集。C++既可以用于面向过程的结构化程序设计，又可用于面向对象的程序设计，是一种功能强大的混合型的程序设计语言。 C++对C的“增强”，表现在两个方面： （1）在原来面向过程的机制基础上，对C语言的功能做了不少扩充。 （2）增加了面向对象的机制。 作为一种编程约定，C++程序员倾向于只有当所有的成员均为公共时才使用结构。结构（struct）是一种特殊的类，它的特殊之处在于其成员都是公共的（除非另作声明）。C++程序员只有在所有成员都是公共的时候才会使用结构。 在计算机中进行编码的方法有很多种，此文选择哈弗曼编码。哈弗曼编码由哈弗曼树得到，所以我们要选择存储树的数据结构，为了高效的产生哈弗曼编码，树的存储采用三叉链表的方式，同时增加一个选项以存储各个树结点的权值。同时将得到的密文存储到文件中，以便我们进行查看。 2.2 设计方案 通过分析可知，本课程设计主要功能是通过哈弗曼树得到哈弗曼编码，利用得到的哈弗曼编码对字符串进行编码与译码，并存入文件便于查看。由于构造哈弗曼树和根据哈弗曼树得到编码时要经常对节点的父结点，左右子树结点进行访问，所以采用三叉链表的方式存储树结点，同时在该结点信息中还需要增加一个选项存储结点的权值。其次，为了解决得到的哈弗曼编码的存储问题，再建立一个结构体，用于存储每个字符所对应编码及编码长度，编码的存储简化了编码与译码的操作。同时，将得到的密文存储到文件中，便于我们查看。 定义一个结构体HTNode将树结点，父结点，左右子树结点及该结点的权值联系在一起，便于操作。具体定义如下： typedef struct //建立树结点 { int weight; int parent,lchild,rchild; }HTNode; 定义一个结构体CodeNode