数据结构哈夫曼编码课程设计

实验四 哈夫曼树编码

一、实验目的

1、掌握哈夫曼树的一般算法；

2、掌握用哈夫曼树对字符串进行编码；

3、掌握通过哈夫曼树对字符编码进行译码得过程。 二、实验基本要求 1、设计数据结构； 2、设计编码算法；

3、分析时间复杂度和空间复杂度 三、程序实现

此程序中包含六个函数：Select（）、HuffmanTree（）、BianMa（）、BianMa2（）、YiMa（）、 Sum（），其功能及实现过程如下： #include

struct element//哈夫曼树结点类型 { int weight; int lchild,rchild,parent; };

struct Char//字符编码表信息 { char node; int weight; char code[20]; };

void Select(element hT[],int &i1,int &i2,int k)//在hT[]中查找最小值及次小值 { int min1=9999,min2=9999; i1=i2=0; for(int i=0;i

void HuffmanTree(element huffTree[],Char zifuma[],int n) //

实验四 哈夫曼树编码

一、实验目的

1、掌握哈夫曼树的一般算法；

2、掌握用哈夫曼树对字符串进行编码；

3、掌握通过哈夫曼树对字符编码进行译码得过程。 二、实验基本要求 1、设计数据结构； 2、设计编码算法；

3、分析时间复杂度和空间复杂度 三、程序实现

此程序中包含六个函数：Select（）、HuffmanTree（）、BianMa（）、BianMa2（）、YiMa（）、 Sum（），其功能及实现过程如下： #include

struct element//哈夫曼树结点类型 { int weight; int lchild,rchild,parent; };

struct Char//字符编码表信息 { char node; int weight; char code[20]; };

void Select(element hT[],int &i1,int &i2,int k)//在hT[]中查找最小值及次小值 { int min1=9999,min2=9999; i1=i2=0; for(int i=0;i

void HuffmanTree(element huffTree[],Char zifuma[],int n) //

数据结构 课程设计报告

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

1 课程设计的目的和意义

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

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

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

1

2．需求分析

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

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

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

问题补充：1. 从硬

实验报告

实验课名称：数据结构实验 实验名称：文件压缩问题 班级：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树来决定字符对应的编

课 程 设 计 说 明 书

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

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

计算机学院信管专业

数据结构课程设计

题 目： 哈夫曼树的应用 班 级：

姓 名： 学 号： 同组人姓名：

起迄日期： 课程设计地点: 指导教师：

评阅意见： 成绩评定： 评阅人： 日期： 完成日期：2012年12月

目 录

一、 需求分析…………………………………………3 二、 概要设计…………………………………………4 三、 详细设计…………………………………………6 四、 调试分析和测试结果……………………………7 五、 心得体会和总结……………………………… 10 六、 参考文献……………………………………… 10 七、 附录…………………………………………… 11

2

一、 需求分析

（一）实验要求

要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。

要求实现的基本功能很简单，只

计算机学院信管专业

数据结构课程设计

题 目： 哈夫曼树的应用 班 级：

姓 名： 学 号： 同组人姓名：

起迄日期： 课程设计地点: 指导教师：

评阅意见： 成绩评定： 评阅人： 日期： 完成日期：2012年12月

目 录

一、 需求分析…………………………………………3 二、 概要设计…………………………………………4 三、 详细设计…………………………………………6 四、 调试分析和测试结果……………………………7 五、 心得体会和总结……………………………… 10 六、 参考文献……………………………………… 10 七、 附录…………………………………………… 11

2

一、 需求分析

（一）实验要求

要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。

要求实现的基本功能很简单，只

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

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

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

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

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

10和11

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

可按二位一分进行译码

当然 在传送电文时

希望总长尽可能地短

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

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

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

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

这样的电文无法翻译

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

若要设计长短不等的编码

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

然而

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

二、概要设计

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

主要代码实现：

struct

四、综合设计（课程设计）摘要： 在这次课程设计中，所进行的实验是：哈夫曼编码和编译器。对哈夫曼树进行建立，由节点的权值建立最小二叉树，哈夫曼树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 主要流程图 ……………………………………………..…………