数据结构实验哈夫曼编码算法的实现

实验四 哈夫曼树编码

一、实验目的

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) //

实验报告

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

实验名称 实验日期 实验六 哈夫曼编码和译码的算法设计与实现

实验方案 实验操作 实验成绩 2012-04-22 实 验 信息系统设计与仿室 真室I 实验台号 34号 班级姓信工11-1BF 李煌名 峰

实验结果

一、实验目的

1、根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法； 2、编程实现哈夫曼编译码器； 3、掌握贪心算法的一般设计方法。

二、预习与参考

1、认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理; 2、设计和编制哈夫曼编译码器。 [参考数据类型或变量] typedef ElemType char； typedef struct node{ int w; int flag; ElemType c;

struct node *plink,*llink,*rlink;

char code[m]; }Node;

Node *num[n], *root; [参考子程序接口与功能描述]

void SetTree( NODE *root )

功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树 void En

中南大学

信息论编码实验报告

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

1

目录

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

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

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

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

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

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

10和11

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

可按二位一分进行译码

当然 在传送电文时

希望总长尽可能地短

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

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

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

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

这样的电文无法翻译

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

若要设计长短不等的编码

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

然而

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

二、概要设计

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

主要代码实现：

struct

淮海工学院计算机工程学院

实验报告书

课程名： 《算法分析与设计》 题 目： 实验3 贪心算法

哈夫曼编码

班 级： 软件081班 学 号： 110831116 姓 名： 陈点点

评语： 成绩： 指导教师： 批阅时间： 年 月 日 《 算法分析与设计》实验报告 - 1 -

实验3 贪心算法

实验目的和要求

（1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数

#include #include #include

#define n 6 /* 叶子数目 */ #define m 2*n-1 /* 结点总数 */ #define Maxval 1 /* 最大权值 */ typedef char datatype;

typedef struct //定义为结构类型 { float weight; //权值 datatype data; int lchild, rchild, parent; } hufmtree; hufmtree tree[m]; typedef struct { char bits[n]; /* 编码数组位串，其中n为叶子结点数目*/ int start; /* 编码在位串的起始位置 */ datatype data; } codetype; codetype code[n];

HUFFMAN(hufmtree tree[ ]) { int i, j, p1,p2; char ch; float small

淮海工学院计算机工程学院

实验报告书

课程名： 《算法分析与设计》 题 目： 实验3 贪心算法

哈夫曼编码

班 级： 软件081班 学 号： 110831116 姓 名： 陈点点

评语： 成绩： 指导教师： 批阅时间： 年 月 日 《 算法分析与设计》实验报告 - 1 -

实验3 贪心算法

实验目的和要求

（1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数

北京邮电大学电信工程学院

2008级数据结构实验报告

实验名称： 实验三 树 学生姓名： 班 级： 班内序号： 学 号：

日 期： 20013年11月26日

1．实验要求

实验目的

通过选择下面两个题目之一进行实现，掌握如下内容： 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力 实验内容

利用二叉树结构实现赫夫曼编/解码器。 基本要求：

1. 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建

立赫夫曼树

2. 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输

出。

3. 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4. 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结

果。

5. 打印(Print)：以直观的方式打印赫夫曼树（选作）

6. 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

2. 程序分析

哈夫曼树结点的储存结构除了二叉树所有的双亲域parents，左子树域lchild，右子树域