实验八哈夫曼编码的方法和实现
一、实验目的
1.掌握哈夫曼编码的基本理论和算法流程；
2. 用VC++6.0编程实现图像的哈夫曼编码。
二、实验内容
1．画出哈夫曼编码的算法流程；
2．用VC++6.0编程实现哈夫曼编码。
三、实验步骤
（1）启动VC++6.0，打开Dip工程。
（2）在菜单栏→insert→resouce→dialog→new,在对话框模版的非控制区点击鼠标右键，在弹出的对话框中选properties,设置为ID：IDD_DLG_Huffman,C标题：哈夫曼编码表。
（3）在弹出的对话框中，添加如下的按钮等控件：
（4）在ResourceView栏中→Menu→选IDR_DIPTYPE ,如图
在图像编码菜单栏下空的一栏中，右键鼠标，
在弹出的对话框中选属性properties，在弹出的对话框中，进行如下的设置
（5）右击哈夫曼编码表菜单栏，在建立的类向导中进行如下设置
（6）在DipDoc.cpp中找到void CDipDoc::OnCodeHuffman()添加如下代码void CDipDoc::OnCodeHuffman()
{
int imgSize;
imgSize = m_pDibObject->GetWidth()*m_pDibObject->GetHeight();
//在点处理CPointPro类中创建用来绘制直方图的数据
CPointPro PointOperation(m_pDibObject );
int *pHistogram = PointOperation.GetHistogram();
//生成一个对话框CHistDlg类的实例
CDlgHuffman HuffmanDlg;
//将绘制直方图的数据传递给CHistDlg对话框类的公有成员变量m_pnHistogram
if( pHistogram != NULL )
{
//设置直方图数据指针
HuffmanDlg.m_fFreq = pHistogram;
HuffmanDlg.m_iSizeImage = imgSize;
if(m_pDibObject->GetNumBits() >= 8)
HuffmanDlg.m_iLeafNum=256;
else
HuffmanDlg.m_iLeafNum=m_pDibObject->GetNumBits();
}
//显示对话框
if ( HuffmanDlg.DoModal() != IDOK)
return;
delete [] pHistogram;
}
（7）在DipDoc.cpp中添加#include "DlgHuffman.h"
（8）将DlgHuffman.h、DlgHuffman.cpp文件拷贝到当前工程目录文件里面；并添加到当前工程。
四、实验结果
五、实验心得及体会
通过做这次实验掌握了哈夫曼编码的基本理论和算法流程；掌握了编程实现图像的哈夫曼编码算法。
昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图：
三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件
四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include
哈夫曼编码实验报告: 数据结构的某项实验 ①问题描述：给定n个字符的权值数组w，根据哈夫曼编码与译码规则，实现一个哈夫曼编/译码系统（利用实验指导书上的27个字符的数据进行实验）。 ②利用顺序表存储Huffman树，编码结果的存储方式采用书上的结构。 ③Huffman树的构造约定如下： 根的权值较小的子树作为左子树，当权值相等时，则先生成的子树是左子树； 按照结点的生成次序选择权值较小的两棵子树构造Huffman 树； 从叶子结点到根结点逆向求出每个字符的Huffman编码，不采用递归方法； 从根结点开始实现译码，要求被译码的字符数大于20个字符。 ④采用文件方式存储n个权值和待翻译的二进制代码，其余数据均不采用文件存储。 序号字符权值双亲结点左孩子右孩子 1□186 0 0 0 2 A 64 0 0 0 3 B 13 0 0 0 4 C 22 0 0 0
6 E 103 0 0 0 7 F 21 0 0 0 8 G 15 0 0 0 9 H 47 0 0 0 10 I 57 0 0 0 11 J 1 0 0 0 12 K 5 0 0 0 13 L 32 0 0 0 14 M 20 0 0 0 15 N 57 0 0 0 16 O 63 0 0 0 17 P 15 0 0 0 18 Q 1 0 0 0 19 R 48 0 0 0 20 S 51 0 0 0 21 T 80 0 0 0 22 U 23 0 0 0 23 V 8 0 0 0 24 W 18 0 0 0 25 X 1 0 0 0 26 Y 16 0 0 0
1.实验过程与结果 完整代码：（实验环境codeblock） #include
实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 #include
//选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++)
实验二二叉树的遍历及霍夫曼编码 班级：计科1101班 学号：0909101605 姓名：杜茂鹏 2013年5月22日
一、实验目的 掌握二叉树的建立及遍历操作，霍夫曼编码基本操作及存储结构表示 二、实验内容 1. 系统要求包含以下功能 1）初始化：从终端读入字符集大小n，以及n个字符和n个权值（或者读入字符集和频度数据文件），建立哈夫曼树，并将哈夫曼树存入到文件HfmTree 中。 2）编码：利用已建好的哈夫曼树（如果不在内存中，则从文件中读入），从文件ToBeTran中读入原文，对原文进行编码，将编码后的结果存入文件CodeFile 中。 3）译码：利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 4）打印：打印输出哈夫曼树，显示ToBeTran, TextFile和CodeFile文件的内容。 三、实验要求 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 四、概要设计 1）首先动态分配数组存储霍夫曼树及存储霍夫曼编码表，然后从终端或文件读入霍夫曼树的字符变量及其频度，初始化建立霍夫曼树并将其写入文件HfmTree.txt中。 2）从指定的文件succe.txt中读入原文，利用已经编好的霍夫曼树对其编码，将编码结果写入文件Coding.txt保存。 3）利用已建好的哈夫曼树将文件Coding.txt中的代码进行译码，结果存入文件decoding.txt中。
五、测试数据： 2．原文内容“THIS IS MY PROGRAM” 六、详细设计 实验内容(原理、操作步骤、程序代码) //建立霍夫曼树，对原文进行编码、译码 #include
实验报告 实验课名称：数据结构实验 实验名称：文件压缩问题 班级：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树来决定字符对应的编码，进行文件的压缩解码压缩即根据Huffman树进行译码 设计流程图如图1.1所示。
图1.1 设计流程图 (1)压缩文件 输入一个待压缩的文本文件名称(可带路径)如:D:\lu\lu.txt 统计文本文件中各字符的个数作为权值,生成哈夫曼树；将文本文件利用哈夫曼树进行编码,生成压缩文件。压缩文件名称=文本文件名.COD 如:D:\lu\lu.COD 压缩文件内容=哈夫曼树的核心内容+编码序列 for(int i=0;i<256;i++) { header[i].count=0; //初始化权重 header[i].b=(unsigned char)i; //初始化字符 } ifstream infile(infilename,ios::in|ios::binary); while(infile.peek()!=EOF) { infile.read((char *)&temp,sizeof(unsigned char)); //读入一个字符 header[temp].count++; //统计对应结点字符权重 flength++; //统计文件长度 } infile.close(); //关闭文件 for(i=0;i<256-1;i++) //对结点进行冒泡排序,权重大的放在上面，编码时效率高 for(int j=0;j<256-1-i;j++) if(header[j].count 实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include 哈夫曼编码步骤： 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。） 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，直到集合F中只有一棵二叉树为止。 /*------------------------------------------------------------------------- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在Win-TC 下测试通过 * 实现过程：着先通过HuffmanTree() 函数构造哈夫曼树，然后在主函数main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。*------------------------------------------------------------------------*/ #include 一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree #include if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) { (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/ { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }/*哈夫曼树建立完毕*/ void outputHuffman(HuffmanTree HT, int m) { if(m!=0) { 数据结构实验报告 ――实验五简单哈夫曼编/译码的设计与实现本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结 构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几 个功能来设计和实现。 一、【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。 2、编码。 利用已建好的哈夫曼树（如不在存，则从文件nodedata.dat中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中。 3、译码。利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 二、【数据结构设计】 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： typedef struct { int weight;//结点权值 int parent; int lchild; int rchild; char inf; }HNodeType; 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #define MAXBIT 10 typedef struct 0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。 译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定义为： 淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验3 贪心算法 哈夫曼编码 班级：软件102班 学号：11003215 姓名：鹿迅 实验3 贪心算法 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 struct huffman { double weight; //用来存放各个结点的权值 int lchild,rchild,parent; //指向双亲、孩子结点的指针 }; 核心源代码 #include int min=11000; int min1; for(int k=0;k 哈夫曼树实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 实验七哈夫曼编码 哈夫曼编码 1. 问题描述 设某编码系统共有n个字符，使用频率分别为{w1, w2,…, w n}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。 2. 基本要求 ⑴设计数据结构； ⑵设计编码算法； ⑶分析时间复杂度和空间复杂度。 3. 编码 #include if(c!='\0') { for(int j=0;T[j]!='\0';j++) { if(T[j]==c) { count++; T[j]='$'; } } } if(c!='\0') { w1[k]=count; w[k++]=count; } c='\0'; } return k; } void Select(element h[],int &i3,int &i4)//获得哈夫曼数组中权值最小的两个下标{ int c; i3=-1;i4=-1; for(int i=0;i3==-1;i++) if(h[i].parent==-1) i3=i; for(i;i4==-1;i++) if(h[i].parent==-1) i4=i; if(h[i3].weight>h[i4].weight) { c=i3; i3=i4; i4=c; } for(i;h[i].weight>0;i++) { if(h[i].parent==-1) 实验八哈夫曼编码的方法和实现 一、实验目的 1.掌握哈夫曼编码的基本理论和算法流程； 2. 用VC++6.0编程实现图像的哈夫曼编码。 二、实验内容 1．画出哈夫曼编码的算法流程； 2．用VC++6.0编程实现哈夫曼编码。 三、实验步骤 （1）启动VC++6.0，打开Dip工程。 （2）在菜单栏→insert→resouce→dialog→new,在对话框模版的非控制区点击鼠标右键，在弹出的对话框中选properties,设置为ID：IDD_DLG_Huffman,C标题：哈夫曼编码表。 （3）在弹出的对话框中，添加如下的按钮等控件： （4）在ResourceView栏中→Menu→选IDR_DIPTYPE ,如图 在图像编码菜单栏下空的一栏中，右键鼠标， 在弹出的对话框中选属性properties，在弹出的对话框中，进行如下的设置 （5）右击哈夫曼编码表菜单栏，在建立的类向导中进行如下设置 （6）在DipDoc.cpp中找到void CDipDoc::OnCodeHuffman()添加如下代码void CDipDoc::OnCodeHuffman() { int imgSize; imgSize = m_pDibObject->GetWidth()*m_pDibObject->GetHeight(); //在点处理CPointPro类中创建用来绘制直方图的数据 CPointPro PointOperation(m_pDibObject ); int *pHistogram = PointOperation.GetHistogram(); //生成一个对话框CHistDlg类的实例 CDlgHuffman HuffmanDlg; 电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名：陈**浩学号：*************指导教师：钱** 实验地点：科研教学楼A508实验时间：一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—树 三、实验学时：4 四、实验原理： 霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。 可以证明霍夫曼树的WPL是最小的。 中南大学数据结构课程 姓名：刘阳 班级：信息0703 学号：0903070312 实验时间： 08.11.14 指导老师：赵颖 一、实验内容 根据输入的n 个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕。 二、实验说明 哈夫曼数，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。 设二叉树具有n 个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL ，记作： WPL=k n k k L W *∑=1。在给定一组具有确定权值的叶结点，可以构造出不同的带权二 叉树。根据哈夫曼树的定义，一棵二叉树要使其WPL 值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。 在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA ，电文中只含有A ，B ，C ，D 四种字符，若这四种字符采用下表所示的编码，则电文的代码为000010000100100111 000，长度为21。 在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。并且在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，以避免反译成原文时，编码出现多义性。 在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。 采用哈夫曼树进行编码，也不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。 1．哈夫曼编码的方法 编码过程如下: (1) 将信源符号按概率递减顺序排列; (2) 把两个最小的概率加起来, 作为新符号的概率; (3) 重复步骤(1) 、(2), 直到概率和达到1 为止; (4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出"1"、"0"序列（从码数的根到终节点）。 2．哈夫曼编码的特点 ①哈夫曼方法构造出来的码不是唯一的。 原因 ·在给两个分支赋值时, 可以是左支( 或上支) 为0, 也可以是右支( 或下支) 为0, 造成编码的不唯一。 ·当两个消息的概率相等时, 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 ②哈夫曼编码码字字长参差不齐, 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。 ·当信源概率是2 的负幂时, 哈夫曼码的编码效率达到100%; ·当信源概率相等时, 其编码效率最低。 ·只有在概率分布很不均匀时, 哈夫曼编码才会收到显著的效果, 而在信源分布均匀的情况下, 一般不使用哈夫曼编码。 ④对信源进行哈夫曼编码后, 形成了一个哈夫曼编码表。解码时, 必须参照这一哈夫编码表才能正确译码。 ·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时, 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律 使用缺省的哈夫曼编码表有 解：为了进行哈夫曼编码, 先把这组数据由大到小排列, 再按上方法处理 （1）将信源符号按概率递减顺序排列。 （2）首先将概率最小的两个符号的概率相加，合成一个新的数值。 （3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。 5．4．2 Shannon-Famo编码 Shannon-Famo(S-F) 编码方法与Huffman 的编码方法略有区别, 但有时也能编 出最佳码。 1．S－F码主要准则 符合即时码条件; 在码字中,1 和0 是独立的, 而且是( 或差不多是)等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有 1位的信息量。 2．S－F码的编码过程 信源符号按概率递减顺序排列; 把符号集分成两个子集, 每个子集的概率和相等或近似相等;哈夫曼编码算法实现完整版
哈夫曼编码步骤
哈夫曼树的实验报告1
哈夫曼树建立、哈夫曼编码算法的实现
数据结构哈夫曼编码实验报告
0023算法笔记——【贪心算法】哈夫曼编码问题
哈夫曼编码_贪心算法
哈夫曼树实验报告
(完整word版)实验七 哈夫曼编码实验
数字图像实验 哈夫曼编码的方法和实现1234
哈夫曼树及其操作-数据结构实验报告(2)
哈夫曼编码实验报告
哈夫曼编码的方法
相关主题
文本预览