哈夫曼编码译码器课程设计心得体会

课 程 设 计 说 明 书

课程名称：数据结构与算法 设计题目：哈夫曼编\\译码器 院系：计算机科学与信息工程学院 学生姓名：刘文杰

学号： 16031210229 专业班级：软件工程16-2 指导教师：孙高飞

2017年 12 月 11日

设计题目 哈夫曼编\\译码器 限定人数 3 采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于5000字节。 读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。 设字符集及频度如下表： 问题描述 字符 空格 A B C D E F G H I J 1 K L M 5 32 20 频度 186 64 13 22 32 103 21 15 47 57 字符 N O P Q R 1 S T U V W X Y Z 8 18 1 16 1 频度 57 63 15 48 51 80 23 1、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码 2

问题解析与解题方法

问题分析：

设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。 （1） 从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）；

（2） 统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）； （3） 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；

（4） 将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf） （5） 用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率； （6） 进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。

根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解码。

哈夫曼树的理论创建过程如下： 一、构成初始集合

对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合

F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 二、选取左右子树

在F中选取两棵根结点权值

人生充满着期待，梦想连接着未来。 一、需求分析 目前

进行快速远距离通信的主要手段是电报

即将需传送的文字转化成由二级制的字符组成的字符串 例如

假设需传送的电文为\它只有4种字符 只需两个字符的串 便可以分辨

假设A、B、C、D、的编码分别为00 01

10和11

则上述7个字符的电文便为\总长14位 对方接受时

可按二位一分进行译码

当然 在传送电文时

希望总长尽可能地短

如果对每个字符设计长度不等的编码

且让电文中出现次数较多的字符采用尽可能短的编码 则传送电文的总长便可减少

如果设计A、B、C、D的编码分别为0 00 1 01

则上述7个字符的电文可转换成总长为9的字符串\但是

这样的电文无法翻译

例如传送过去的字符串中前4个字符的字串\就可以有很多种译法 或是\或者\或者\等 因此

若要设计长短不等的编码

则必须是任一字符的编码都不是另一个字符的编码的前缀 这种编码称作前缀编码

然而

如何进行前缀编码就是利用哈夫曼树来做 也就有了现在的哈夫曼编码和译码

二、概要设计

利用哈夫曼树编/译码 （一）、建立哈夫曼树 （二）、对哈夫曼树进行编码 （三）、输出对应字符的编码 （四）、译码过程

主要代码实现：

struct

数据结构课设

哈夫曼编译码器

学 号： 姓 名： 提交日期： 成 绩：

东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术

一、 实验名称

哈夫曼编/译码器的实现

二、 实验要求

【问题描述】

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传来数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。

【基本要求】

一个完整的系统应具有以下功能：

(1)I：初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

(2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

(3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件TextFile中。

(4)P：打印代码文件(

数据结构 课程设计报告

课 题: 专业班级： 学 号： 姓 名： 指导教师:

1 课程设计的目的和意义

在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。

1

2．需求分析

课 题：哈夫曼编码译码器系统

问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们

作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。

问题补充：1. 从硬

四、综合设计（课程设计）摘要： 在这次课程设计中，所进行的实验是：哈夫曼编码和编译器。对哈夫曼树进行建立，由节点的权值建立最小二叉树，哈夫曼树haftree，并由所建立的哈夫曼树进行编码，求出各个节点的编码。在由所求的哈夫曼树，输入一段二进制电文，能够输出那所建立的哈夫曼树中的节点。建立的haftree用图形化表示出来。在整个代码实现中，窗体的实现，功能的完善，哈夫曼树的建立，哈夫曼树的编码，遇到了许多难题，haftree对象数组的分配空间，节点的属性等都比较困难。在整个过程中，用的是C#语言，包的应用，字符串数组的空间分配，在计算每个字符的权值时，用的是sizeOf()检索整个字符串，计算字符的权值，建立字符出现频度的表格，根据表格中每个字符频度建立起哈夫曼树。从根节点出发检索每个节点的左右孩子，如果是左孩子遍历左边，路径为0，然后左孩子为根节点；如果是右孩子，遍历右孩子，路径为1，然后右孩子为根节点。在重新上述方法，直到所有的节点都遍历完，每个节点的编码就确定后输出来。 在译码过程中，由所输入的二进制电文，根据所建立的哈夫曼树，如果是0走左边，如果是1，走右边，直到节点的左右孩子为空时，输出给节点的信息，在回到根节点重新遍历后面的二进制电

哈夫曼编码 综合设计报告

LD

1

武汉工程大学计算机科学与工程学院 综合设计报告

目 录

摘 要 ……………………………………………………………………………………… I Abstract …………………………………………………………………………………... II 第一章 课题背景…………………………………………………………………….…….. 1 1.1 课题背景 ……………………………………………………………………….……...1 1.2 课题内容 ………………………………………………..………………………….… 1 第二章 设计简介及设计方案论述 ………………………………………………….…….. 2 2.1 设计简介 ………………………………………………..……………………….….…2 2.2 问题分析 ………………………………………………..……………………….….…2 2.3 设计方案 ………………………………………………..……………………….….…3 第三章 详细设计…………………………………………………………..………….…….. 4 3.1 主要流程图 ……………………………………………..…………

华北水利水电大学 数据结构 实验报告

2013 ～2014 学年 第 一 学期 级 计算机科学与技术专业

班级： 学号： 姓名：

实验三：哈夫曼编/译码器

一． 实验目的

掌握哈夫曼树编码原理

二．实验内容

根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。 基本要求：

（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。

（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）。 （3）计算压缩比（选作） （4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）

测试数据：对字符串{casbcatbsatbat}进行编码；对电文“1101000”译码。字符集D={ ？},出现频率为w={？}

三． 程序源代码

#include #include #include

华北水利水电大学 数据结构 实验报告

2013 ～2014 学年 第 一 学期 级 计算机科学与技术专业

班级： 学号： 姓名：

实验三：哈夫曼编/译码器

一． 实验目的

掌握哈夫曼树编码原理

二．实验内容

根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。 基本要求：

（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。

（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）。 （3）计算压缩比（选作） （4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）

测试数据：对字符串{casbcatbsatbat}进行编码；对电文“1101000”译码。字符集D={ ？},出现频率为w={？}

三． 程序源代码

#include #include #include

实验五 哈夫曼编码与译码的设计与实现

一、问题描述

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。

基本要求：

（1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。

（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中。

（3）译码：利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件textfile.txt中。

（4）打印编码规则：即字符与编码的一一对应关系。 （5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。

二、数据结构设计 1、

构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。

在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可