哈夫曼编码译码器c语言

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

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

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

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

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

10和11

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

可按二位一分进行译码

当然 在传送电文时

希望总长尽可能地短

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

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

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

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

这样的电文无法翻译

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

若要设计长短不等的编码

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

然而

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

二、概要设计

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

主要代码实现：

struct

课 程 设 计 说 明 书

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

学号： 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中选取两棵根结点权值

数据结构课设

哈夫曼编译码器

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

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

一、 实验名称

哈夫曼编/译码器的实现

二、 实验要求

【问题描述】

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

【基本要求】

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

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

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

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

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

中南大学

信息论编码实验报告

专业班级:电子信息1002 指导老师：赵颖 姓名:付永军 学号:0909100707

1

目录

一.实验目的 ..................................................................................... 3 二、实验内容 .................................................................................. 3 三、实验原理 .................................................................................. 4 1.1使用MATLAB 实现香农码编码。 ...................................... 4 1.2、使用MATLAB 实现HUFFMAN 编码. ............................... 7 2.1、使用C++实现香农码编码 ........................

哈夫曼编码的C语言实现

编码原理程序步骤的分析：

哈夫曼码是用概率匹配方法进行信源编码。编程时应该注意：1，概率大的符号对应于短码，概率小的对应于长码，充分利用短码；2缩减信源的最后二个码字，总是最后一位不同，保证了哈夫曼码是即时码。程序步骤：（见信息论课本p88页内容）

（l）将信号源的符号按照出现概率递减的顺序排列。

（2）将两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率

（3）重排后的两个概率最小符号重复步骤(2)过程。

（4）不断继续上述过程，直到最后两个符号配以0和1为止

（5）从最后一级开始向前返回各个信源符号所对应的码元序列，及相应的码字。

根据以上规则编码可知：哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，到树根结束，最后得到一个横放的码树，所以编出的码是即时码。哈夫曼编码概率大的符号对应于短码，概率小的符号对应于长码，使平均码长最小。每次对概率最小的两个符号求概率之和形成缩减信源时，构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字不惟一。

程序源代码如下;

#include <stdio.h>

#include #include

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

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

东北电力大学计算机科学与技术专业 综合设计报告

目 录

摘 要 ………………………………………………………………………..……………… II Abstract …………………………………………………………………………..………... II 第一章 课题描述………………………..………………………………………………….. 1 1.1 问题描述………………………………………………………………………………...1 1.2 需求分析…………………………………………………..…………………………… 1 1.3 程序设计目标…………………………………………………………………………… 第二章 设计简介及设计方案论述 ………………………………………………………… 2 2.1 设计简介.………………………………………………..………………………..….…2 2.2 设计方案论述……………………………………………..…………………….………2 2.3 概要设计…………………………………………………..………………………….…2 第三章 详细设计…………………………………………………………..……….….…….. 4 3.1 哈夫曼树………

东北电力大学计算机科学与技术专业 综合设计报告

目 录

摘 要 ………………………………………………………………………..……………… II Abstract …………………………………………………………………………..………... II 第一章 课题描述………………………..………………………………………………….. 1 1.1 问题描述………………………………………………………………………………...1 1.2 需求分析…………………………………………………..…………………………… 1 1.3 程序设计目标…………………………………………………………………………… 第二章 设计简介及设计方案论述 ………………………………………………………… 2 2.1 设计简介.………………………………………………..………………………..….…2 2.2 设计方案论述……………………………………………..…………………….………2 2.3 概要设计…………………………………………………..………………………….…2 第三章 详细设计…………………………………………………………..……….….…….. 4 3.1 哈夫曼树………