哈夫曼编码译码器实验报告

问题解析与解题方法

问题分析：

设计一个哈夫曼编码、译码系统。对一个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中选取两棵根结点权值

课 程 设 计 说 明 书

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

学号： 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

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

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

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

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

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

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

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

10和11

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

可按二位一分进行译码

当然 在传送电文时

希望总长尽可能地短

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

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

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

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

这样的电文无法翻译

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

若要设计长短不等的编码

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

然而

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

二、概要设计

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

主要代码实现：

struct

哈弗曼编码实验报告

一．实验内容描述

1.实验名称：

哈夫曼编码译码器

2.实验内容：

利用哈夫曼树实现电文和比特流互相转换的功能。

二．存储结构分析

1.存储需编码字符的字符型数组 chars[N]

2.哈夫曼树的结点元素存储结构

typedef struct {

int weight,parent,left,right;

}HTNode;

3.哈夫曼树存储结构

typedef struct {

HTNode *Htree;

int root；

}HuffmanTree；

4.存储每个字符对应的编码的二维数组

HC[N][N];

三．数据结构分析

1.宏定义 OK为1,Error为0 ，定义Status为int型，N为100，方便调节。

2.自定义结点结构：包括整型变量weight，parent，left，right；字符型变量等。

3.定义数组HC[N][N]，二维数组，可实现编码的存储。

四．程序功能

======Huffman编码解码器======

1----------输入字符创建编码

2----------输出统计结果

3----------打印哈夫曼树

4----------打印哈夫曼编码

5----------电文->比特流

6----------比特流->电文

五．各函数

数据结构课设

哈夫曼编译码器

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

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

一、 实验名称

哈夫曼编/译码器的实现

二、 实验要求

【问题描述】

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

【基本要求】

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

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

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

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

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

第四次上机实验报告

姓名：康辉 学号：15180210013 班级：1518021 一、题目要求

对输入的一串电文字符(A B C D E F G H 8 个字符，其概率分别为 0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11)实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。实现功能如下： ? Huffman树的建立 ? Huffman编码的生成 ? 编码文件的译码 二、程序思路

设置一个数组v存放待编码元素，一个数组w存放权值，n为元素个数，ht为创建的哈夫曼树，hc为指针数组存储哈夫曼编码，这些作为函数参数传递到函数haffcoding中，创建编码树，然后按权值进行编码，这些都在一个函数中实现。 哈夫曼树节点： typedef struct { char data;

Int weight;

Int parent,lchild,rchild;

}htnode,huffmantree; 三、程序设计中遇到的问题

1、 选择一个数组来存储来存放编码，但是指针数组运用的不够熟练，造成值传递时

出错。最后查看c语言书籍得以解决.

2、 在选择所有权值中最小，次小的时候

院系：计算机学院

实验课程：数据结构预算法

实验项目：哈弗曼树综合实验

指导老师：

开课时间：2009 ～ 2010年度第1学期专业：计算机类

班级：08本6班

学生：

学号：

华南师范大学教务处

华南师范大学实验报告

学生姓名禤欢子学号20082100173

专业计算机类年级、班级08本6 班

课程名称数据结构与算法分析实验项目哈弗曼树综合实验

实验时间2009年12月25日指导老师黄定

实验评分

----------------------------------------------------------------------------------------------------------------------

【需求分析】

本实验需要设计程序，输入叶子结点和权值，建立一颗哈弗曼树，并根据哈弗曼树进行编码和译码操作。键盘中输入或者从文件中读入哈弗曼树；键盘中输入或者从源文件中读入需要编码的源文，然后将源文根据哈弗曼树的权值，译码为二进制代码。最后实现凹入显示法显示哈弗曼树。

【概念设计】

本程序由HaffmanTree.h、HaffmanTree.cpp、main.cpp三个文件构成。HaffmanTree.h中定义了哈弗曼树的储存结构体HaffmanNod

实验报告

实验课名称：数据结构实验 实验名称：文件压缩问题 班级：20132012 学号： 姓名： 时间：2015-6-9 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 二、数据结构设计 首先定义一个结构体： struct head { unsigned char b; //记录字符 long count; //权重 int parent,lch,rch; //定义双亲，左孩子，右孩子 char bits[256]; //存放哈夫曼编码的数组 } header[512],tmp; //头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511 三、算法设计 输入要压缩的文件读文件并计算字符频率根据字符的频率，利用Huffman编码思想创建Huffman树由创建的Huffman树来决定字符对应的编