哈夫曼编码Word文档下载推荐.docx
《哈夫曼编码Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码Word文档下载推荐.docx（21页珍藏版）》请在冰点文库上搜索。
执行结果14
十一：
体会感想16
哈夫曼树
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffmantree）。
（1）路径和路径长度：
在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。
通路中分支的数目称为路径长度。
若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
（2）结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
结点的带权路径长度为：
从根结点到该结点之间的路径长度与该结点的权的乘积。
（3）树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
哈夫曼树的构造
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。
n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：
（1）将w1、w2、…，wn看成是有n棵树的森林（每棵树仅有一个结点）；
（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
（3）从森林中删除选取的两棵树，并将新树加入森林；
（4）重复
（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
哈夫曼编码（HuffmanCoding）是一种编码方式，哈夫曼编码是可变字长编码（VLC）的一种。
Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。
哈夫曼算法伪代码
1.数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；
2.数组huffTree的前n个元素的权值置给定权值w[n]；
3.进行n-1次合并
3.1在二叉树集合中选取两个权值最小的根结点，其下标分别为i1,i2；
3.2将二叉树i1、i2合并为一棵新的二叉树k；
哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。
哈夫曼压缩属于可变代码长度算法一族。
意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。
因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
程序功能及输入输出要求：
控制台输入需编码的字符个数,分别输入字符符号以及权值后，进行哈夫曼编码，将编码结果输出到txt文件中。
编码结束后，可在控制台输入0,1字符串进行解码，若解码成功，输出解码结果。
（1）：
编程软件MicrosoftVisualStudio2010
（2）：
使用C++语言，自定义HuffmanCode类，在头文件HuffmanCode.h中。
如下如：
自定义类使用的字段，方法以及嵌套类型
图1：
HuffmanCode类的定义
（3）：
HuffmanCode类的实现，在HuffmanCode.cpp文件中，如图
图2：
HuffmanCode类的实现
（4）：
HuffmanCode主程序，在HuffmanCodeMain.cpp文件中，如图
图3：
主程序
详细设计
如图HuffmanCode类中的公有成员：
HuffmanCode（）;
主要进行初始化，申请所需内存空间，对字符命名及赋予权值；
HuffTree（）;
由初始化后的信息构造哈夫曼树；
Huff_Encode（）;
对字符进行哈夫曼编码；
Huff_Decode（）;
对二进制信息进行哈夫曼解码；
HuffCode（string&
CharacterCode）;
哈夫曼解码算法，供成员Huff_Decode（）调用；
Ele_Path（intn,boolchild）;
供解码函数调用，返回下一个儿子结点所在下标；
~HuffmanCode（）;
析构函数，释放内存空间
HuffmanCode类中的私有成员：
structElement{
stringname;
intflag;
TEle_Weight;
intl_child,r_child,parent;
};
用于存放结点信息，即字符名称、标记、权值、左孩子、右孩子、双亲；
intNum;
字符个数；
Element*Elements;
一个指向Element结构体的指针；
string*Code;
所需解码的字符串指针；
调试与测试
n个字符进行哈夫曼编码，需2n-1个结点，在进行下标遍历时要注意，结点个数是2n-1但最后一个结点的下标是2n-2,否则地址出错，产生不可预测的结果；
执行解码时，由输入的0,1字符串判断下一个结点是左孩子还是右孩子，当浏览至叶子结点时，一定要把指针或者下表指向2n-1个结点（根节点）的位置，下表2n-2，否则会出错，导致解码失败；
执行n-1次合并时，参与过运算的结点一定要改变标记值，否则下次遍历会再次参与运算，导致结果错误。
程序源代码
（1）HuffmanCode.h
#include<
string>
usingstd:
:
string;
//HuffmanCode.h声明类HuffmanCode
#ifndefHuffmanCode_H
#defineHuffmanCode_H
template<
classT>
classHuffmanCode{
public:
HuffmanCode（）;
//构造函数，HuffTree初始化
voidHuffTree（）;
//构造哈夫曼树
voidHuff_Encode（）;
//哈夫曼编码函数
voidHuff_Decode（）;
//解码函数
voidHuffCode（string&
//解码算法
intEle_Path（intn,boolchild）;
//供解码函数嵌套调用，返回下一个儿子结点下标
//n代表当前结点下标，child代表下一结点所在下标
~HuffmanCode（）;
//析构函数
private:
structElement{
//编码的字符
//标记
//权值
//左孩子，右孩子，双亲
intNum;
Element*Elements;
string*Code;
//存放计算出字符哈夫曼编码
};
#endif
（2）HuffmanCode.cpp
#include"
stdafx.h"
#include"
HuffmanCode.h"
//无参构造函数，确定字符数目n，并初始化2*n-1个结点
HuffmanCode<
T>
HuffmanCode（）{
//输入一个大于2的整数
do{
cout<
<
"
Pleaseinputthenumber（above2）ofcharacters:
"
;
cin>
>
Num;
}while（Num<
2）;
//新建2*Num-1个结点
Elements=newElement[2*Num-1];
for（inti=0;
i<
2*Num-1;
i++）{
Elements[i].name="
Elements[i].Ele_Weight=0;
Elements[i].flag=0;
Elements[i].parent=-1;
Elements[i].l_child=-1;
Elements[i].r_child=-1;
}
Num;
PleaseinputthenameofNO."
i+1<
character'
sname:
Elements[i].name;
PleaseinputweightofNO."
character:
Elements[i].Ele_Weight;
//Textcout
cout<
Thedatastructurebeforcomputeis:
endl;
setw（4）<
Name"
setw（10）<
Weight"
<
setw（8）<
Flag"
Parent"
setw（15）<
Left_child"
Right_child"
Elements[i].flag;
Elements[i].parent;
Elements[i].l_child;
Elements[i].r_child;
}
template<
voidHuffmanCode<
HuffTree（）{
inti=0,
MIN_1,MIN_2,//最小与次小元素下标
MIN_W1,MIN_W2;
//最小元素与次小元素的权值
for（i;
i<
Num-1;
i++）{//n-1次合并
MIN_W1=MIN_W2=INT_MAX;
//climits中定义的常量值
MIN_1=MIN_2=0;
//下标0开始
//在森林中找两个权值最小的结点
for（intj=0;
j<
Num+i;
j++）{//注意：
是Num+i不是Num+1
if（Elements[j].flag==0）{//该点未加入HuffmanTree中
if（Elements[j].Ele_Weight<
MIN_W1）{
MIN_W2=MIN_W1;
MIN_2=MIN_1;
MIN_W1=Elements[j].Ele_Weight;
MIN_1=j;
}
elseif（Elements[j].Ele_Weight<
MIN_W2）{
MIN_W2=Elements[j].Ele_Weight;
MIN_2=j;
}
}
//确定两个最小结点的双亲
Elements[MIN_1].parent=Num+i;
Elements[MIN_2].parent=Num+i;
//标记已加入HuffTree中
Elements[MIN_1].flag=1;
Elements[MIN_2].flag=1;
Elements[Num+i].Ele_Weight=Elements[MIN_1].Ele_Weight+Elements[MIN_2].Ele_Weight;
Elements[Num+i].l_child=MIN_1;
Elements[Num+i].r_child=MIN_2;
Huff_Encode（）{
//申请编码所需空间并初始化
Code=newstring[Num];
i++）
Code[i]="
//计算第i个结点的HuffMan编码
TCode_Weight=0;
intchild=0;
intparent=0;
i++）{
Code_Weight=Elements[i].Ele_Weight;
child=i;
parent=Elements[i].parent;
//回溯
stringtemp;
while（parent!
=-1）{
temp=（Elements[parent].l_child==child）?
0"
1"
Code[i].insert（0,temp）;
child=parent;
parent=Elements[child].parent;
//输出结果
Thecharacter'
sCode"
Elements[i].name<
is"
Code[i]<
Huff_Decode（）{
//求字符编码最长的长度
string:
size_typeMAX_Length=0;
Element"
'
ssizeis"
Code[i].size（）<
if（Code[i].size（）>
MAX_Length）
MAX_Length=Code[i].size（）;
Themaximumlengthofcodeis"
MAX_Length<
//求字符编码最小的长度
size_typeMIN_Length=MAX_Length;
if（Code[i].size（）<
MIN_Length）
MIN_Length=Code[i].size（）;
Theminimumlengthofcodeis"
MIN_Length<
//
stringDecode="
do{//限制输入二进制代码长度
PleaseinputyourCode\n（ithavetolongerthancharacters'
maximumoflength）:
\n"
//进行译码
HuffCode（Decode）;
}while（cin>
Decode）;
CharacterCode）{
stringtemp="
intEle_Num=2*Num-2;
//注意：
元素个数是2*Num-1，但根结点下标是2*Num-2，否则参数传递时地址出错
for（string:
size_typeLength=0;
Length<
CharacterCode.size（）;
Length++）{
if（CharacterCode[Length]=='
0'
）{//该字符为‘0’
Ele_Num=Ele_Path（Ele_Num,false）;
if（Elements[Ele_Num].l_child==-1&
&
Elements[Ele_Num].r_child==-1）{
temp+=Elements[Ele_Num].name;
Ele_Num=2*Num-2;
//返回HuffmanTree的根结点
elseif（CharacterCode[Length]=='
1'
）{//该字符为‘1’
Ele_Num=Ele_Path（Ele_Num,true）;
Elements[Ele_Num].r_child==-1）{
else{//输入编码中带有0,1以外的字符
cerr<
Thecodehavebeenmadewrong."
Ele_Num=0;
//这里Ele_Nun可以是任意一个！
=2*Num-2的值
break;
//译码输出
if（Ele_Num==2*Num-2）
Code"
CharacterCode<
temp<
else
cerr<
hasbeenwrong."
intHuffmanCode<
Ele_Path（intn,boolchild）{
if（child==false）{
returnElements[n].l_child;
else{
returnElements[n].r_child;
~HuffmanCode（）{
delete[]Elements;
Elements=NULL;
delete[]Code;
Code=NULL;
（3）HuffmanCodeMain.cpp
//HuffmanCodeMain.cpp:
定义控制台应用程序的入口点。
//
#include<
iostream>
climits>
iomanip>
HuffmanCode.cpp"
cin;
cerr;
cout;
setw;
int_tmain（intargc,_TCHAR*argv[]）
{
HuffmanCode<
int>
a;
a.HuffTree（）;
a.Huff_Encode（）;
a.Huff_Decode（）;
a.~HuffmanCode（）;
return0;
执行结果
（1）如图4，运行主程序，输入字符个数及名称后，指向Element结构体的指针指向一段具有2n-1个结构体的连续内存空间；
图4：
输入字符个数及名称
（2）数据在内存中结构如图5
图5：
初始化字符个数及名称后的数据结构
（3）随后生成哈夫曼树，在内存中结构如图6：
图6:
生成后的哈夫曼树
由哈夫曼树对字符进行编码并输出编码长度等信息：
图7：
生成编码解决方案
输出编码结果到HuffmanCode.txt文件中，如图8；
图8：
输出编码结果到HuffmanCode.txt文件中
（5）：
解码，若输入无误，则输出解码结果（注：
Ctrl+Z结束解码）
图9：
哈夫曼解码
体会感想
经过这次数据结构课程设计，使我更加深刻体会了数据结构在实际应用中的作用，有效地组织好数据结构，可以有效地使系统高效率地执行。
而且通过开始的类的设计，程序的流程设计，以及后来类的具体实现，更使我深刻了解了更多C++语言的精妙之处，而且经历多次的调试，更加知道了程序的执行流程。
由于这次课程设计很早就得到了自己需要做的题目，因此有很长的时间准备，C++中最重要的指针部分也是我这次调试中问题最多的，但是最终都修改正确。
4、参考文献
1．王红梅．数据结构（C++版）．清华大学出版社
2．谭浩强．C++程序设计．清华大学出版社
3．王红梅．数据结构学习辅导与实验指导．清华大学出版社
4．StanleyB.LippmanJoseeLa
升级会员 