哈夫曼树编码解码器.docx
《哈夫曼树编码解码器.docx》由会员分享，可在线阅读，更多相关《哈夫曼树编码解码器.docx（21页珍藏版）》请在冰点文库上搜索。
哈夫曼树编码解码器
数据结构实验报告
实验名称：
哈夫曼树
学生姓名：
苗润泉
班级：
2009211103
班内序号：
14
学号：
09210074
日期：
2010年12月3日
1．实验要求
利用二叉树结构实现哈弗曼编/解码器
基本要求如下：
（1）.初始化（Init）：
能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈弗曼树。
（2）.建立编码表（CreateTable）：
利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
（3）.编码（Encoding）：
根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
（4）.译码（Decoding）：
利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
（5）.打印（Print）：
以直观的方式打印哈夫曼树（选作）。
（6）.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈弗曼编码的压缩效果。
测试数据如下：
Ilovedatastructure,Ilovecomputer.Iwilltrymybesttostudydatastructure.
提示：
（1）.用户界面可以设计为“菜单”方式，能够进行交互。
（2）.根据输入的字符串中的每个字符出现的次数统计频度。
2.程序分析
2.1存储结构
采用二叉树的静态三叉链表存储结构，示意图如下：
静态三叉链表的C++描述如下：
structHNode
{
unsignedintweight;
unsignedintparent;
unsignedintLChild;
unsignedintRChild;
};
2.2关键算法分析
1.关键算法：
a.创建哈夫曼树：
从1~i中选出权值最小的结点
由于要挑选的结点a[x],a[y]，是权值最小的两个结点，且要求a[x]b.生成编码表：
将编码字符逆置
由于在生成编码表时，采用自下而上的方式，所以每个字符的编码顺序是反序的，即还需要将编码逆置一下。
方法是采用循环算法，依次将编码中的前后对应的字符逆置。
c.编码：
此算法比较简单，每读出一个字符，只要在编码表中找出对应的编码即可。
2．代码详细分析：
示意图如下：
a=0
a=1
a=2a=3a=4
3.程序运行结果
1．输入及统计结果
2．编码表
3．编码结果
4．译码结果：
4.总结
程序一开始就碰到了一个难题，如何从屏幕上读取字符串并存储，后来在网上查找，发现cin.getline函数就是专门实现这个功能的，于是这个问题便迎刃而解了。
然后，由于本程序统计的东西较多，循环的嵌套也比较多，一开始时总是出现错误，后来慢慢的一个一个得都解决了，主要是细心的问题。
在理论课上感觉对树的概念理解的还算透彻，但是实验时，就发现，仅仅是理论课、教材上那么一点东西是远远不够的，我们需要的还是多实践，增强对C++编程的熟练程度。
还有一点就是，在编程时，很容易忽略机器的思维而代以人的思维，或者，很容易将一些不常见的情况忽略掉，有时候需要抛出异常，有时是需要做各种假设，这都需要在不断地熟悉中培养出来的良好的编程素质，我承认我在这方面做的还很差，以后会更加努力的。
//Huffman.h
#include
#include
usingnamespacestd;
structHNode//树º¡Â存ä?
储ä¡é结¨¢构1
{
unsignedintweight;
unsignedintparent;
unsignedintLChild;
unsignedintRChild;
};
structHCode//哈t夫¤¨°曼¨¹编À¨¤码?
的Ì?
存ä?
储ä¡é结¨¢构1
{
chardata;
charcode[100];
};
classHuffman
{
private:
HNode*HTree;
HCode*HCodeTable;
intCn;
public:
voidCreateHtree（inta[],intn）;//创ä¡ä建¡§哈t夫¤¨°曼¨¹树º¡Â
voidCreateCodeTable（charb[],intn）;//创ä¡ä建¡§哈t夫¤¨°曼¨¹编À¨¤码?
表À¨ª
voidEncode（char*s,char*d）;//对?
s进?
行D编À¨¤码?
，ê?
存ä?
储ä¡é到Ì?
d;
voidDecode（char*s,char*d,intn）;//对?
s进?
行D解a码?
，ê?
存ä?
储ä¡é到Ì?
d;
voidPrintTable（intn,charb[]）;//打䨰印®?
哈t夫¤¨°曼¨¹编À¨¤码?
表À¨ª
~Huffman（）;
intCodes;//用®?
于®¨²统ª3计?
转Áa换?
哈t夫¤¨°曼¨¹编À¨¤码?
后¨®所¨´用®?
空?
间?
};
voidHuffman:
:
CreateHtree（inta[],intn）
{
HTree=newHNode[2*n-1];
intCn=n;
for（inti=0;i{
HTree[i].weight=a[i];
HTree[i].LChild=-1;
HTree[i].RChild=-1;
HTree[i].parent=-1;
}
intx=0,y=1;
for（inti=n;i<2*n-1;i++）//找¨°到Ì?
权¨¡§值¦Ì最Á?
小?
的Ì?
两¢?
个?
字Á?
母?
，ê?
并¡é返¤¦Ì回?
他?
们?
的Ì?
位?
置?
x，ê?
y
{
for（intj=0;j{if（x==y）
y++;
if（a[x]<0）
x++;
if（a[y]<0）
y++;
if（（a[x]>a[j]）&&（a[j]>0））
x=j;
if（（a[y]>a[j]）&&（a[j]>0）&&y!
=x）
y=j;
}
a[i]=a[x]+a[y];
a[x]=-1;//将?
已°?
建¡§造¨¬哈t夫¤¨°曼¨¹的Ì?
权¨¡§值¦Ì置?
为a-1
a[y]=-1;
HTree[x].parent=HTree[y].parent=i;
HTree[i].weight=HTree[x].weight+HTree[y].weight;
HTree[i].LChild=x;
HTree[i].RChild=y;
HTree[i].parent=-1;
}
}
voidHuffman:
:
CreateCodeTable（charb[],intn）
{
chartemp;
Cn=0;
HCodeTable=newHCode[n];
if（CnCn=n;
for（inti=0;i{
HCodeTable[i].data=b[i];
intchild=i;
intparent=HTree[i].parent;
intk=0;
while（parent!
=-1）
{
if（child==HTree[parent].LChild）
HCodeTable[i].code[k]='0';
else
HCodeTable[i].code[k]='1';
k++;
child=parent;
parent=HTree[parent].parent;
}
HCodeTable[i].code[k]='\0';
k--;//'\0'不?
进?
行D反¤¡ä转Áa，ê?
所¨´以°?
k-1
for（intj=0;j编À¨¤码?
反¤¡ä转Áa
{
temp=HCodeTable[i].code[j];
HCodeTable[i].code[j]=HCodeTable[i].code[k];
HCodeTable[i].code[k]=temp;
}
}
}
voidHuffman:
:
PrintTable（intn,charb[]）
{
for（inti=0;i{
cout<编À¨¤码?
为a"<}
}
voidHuffman:
:
Encode（char*s,char*d）
{
intk=0,l=0,q=0,p=0;
Codes=0;//统ª3计?
哈t夫¤¨°编À¨¤码?
所¨´用®?
的Ì?
bit树º¡Â
while（s[p]!
='\0'）
{
k=0;q=0;
while（HCodeTable[k].data!
=s[p]）//找¨°到Ì?
编À¨¤码?
表À¨ª中D字Á?
母?
对?
应®|的Ì?
句?
子Á¨®的Ì?
之?
母?
{
k++;
}
while（HCodeTable[k].code[q]!
='\0'）//将?
编À¨¤码?
写¡ä入¨?
d
{
d[l]=HCodeTable[k].code[q];
l++;
q++;
Codes++;//写¡ä入¨?
1或¨°0，ê?
Codes+1，ê?
用®?
于®¨²统ª3计?
转Áa换?
后¨®的Ì?
bit
}
p++;
}
d[l]='\0';
}
voidHuffman:
:
Decode（char*s,char*d,intn）
{
intl=0,p=0;
while（s[p]!
='\0'）
{
intparent=2*n-2;
while（HTree[parent].LChild!
=-1&&HTree[parent].RChild!
=-1）
{
if（s[p]=='0'）
parent=HTree[parent].LChild;
else
parent=HTree[parent].RChild;
p++;
}
d[l]=HCodeTable[parent].data;
l++;
}
d[l]='\0';
}
Huffman:
:
~Huffman（）
{
inti=0;
HNode*p=NULL;
HCode*q=NULL;
while（HTree[i].parent=-1）//当Ì¡Àparent=-1时º¡À，ê?
就¨ª是º?
根¨´节¨²点Ì?
，ê?
此ä?
时º¡À是º?
HTree数ºy组Á¨¦的Ì?
结¨¢尾2
{
p=&HTree[i];
deletep;
i++;
}
i=0;
q=&HCodeTable[i];
while（i{
q=&HCodeTable[i];
deleteq;
i++;
}
}
//Huffman.cpp
#include
#include
#include"huffman.h"
#include
usingnamespacestd;
charStr[1024];//存ä?
储ä¡é输º?
入¨?
的Ì?
字Á?
符¤?
intcount=0;//统ª3计?
所¨´输º?
入¨?
的Ì?
字Á?
符¤?
串ä?
有®D多¨¤少¦¨´个?
字Á?
符¤?
intcount2=0;//统ª3计?
有®D多¨¤少¦¨´种?
字Á?
符¤?
charCount[1024];//存ä?
储ä¡é字Á?
符¤?
intCounti[1024];//存ä?
储ä¡é字Á?
符¤?
的Ì?
权¨¡§值¦Ì
voidGetchar（）;//统ª3计?
字Á?
符¤?
串ä?
中D的Ì?
各¡Â种?
字Á?
符¤?
的Ì?
权¨¡§值¦Ì
voidmain（）
{
inta=0;
charPstr1[1024];
charPstr2[1024];
boolflag=0;//标À¨º记?
是º?
否¤?
输º?
入¨?
了¢?
字Á?
符¤?
HuffmanHuff;
while（a!
=48）
{
cout<<"1:
输º?
入¨?
字Á?
符¤?
串ä?
2：
êo打䨰印®?
编À¨¤码?
表À¨ª3：
êo打䨰印®?
编À¨¤码?
结¨¢果?
4：
êo打䨰印®?
译°?
码?
结¨¢果?
0：
êo退ª?
出?
***************************************************************************"<a=_getche（）;inti=0;
switch（a）
{
case49:
cout<<"请?
输º?
入¨?
字Á?
符¤?
串ä?
（ꡧ小?
于®¨²1024个?
字Á?
符¤?
）ê?
"<//if（flag）
//{
//Huff.~Huffman（）;
//}
try
{
Getchar（）;
while（i{
if（Count[i]==''）
cout<<"空?
格?
"<<"的Ì?
个?
数ºy为a"<else
cout<个?
数ºy为a"<i++;
}
cout<cout<<"共2有®D"<字Á?
符¤?
";
cout<flag=1;
Huff.CreateHtree（Counti,count2）;
Huff.CreateCodeTable（Count,count2）;
}
catch（char*S）
{
cout<}
break;
case50:
if（flag）
{
Huff.PrintTable（count2,Count）;
}
else
cout<<"错䨪误¨®！
ê?
！
ê?
请?
先¨¨输º?
入¨?
字Á?
符¤?
"<break;
case51:
if（flag）
{
Huff.Encode（Str,Pstr1）;
cout<cout<<"编À¨¤码?
前¡ã字Á?
符¤?
串ä?
为a"<cout<<"共2"<符¤?
占?
8*"<cout<<"编À¨¤码?
后¨®所¨´占?
bit为a"<cout<<"压1缩?
比À¨¨为a"<<8*count/float（Huff.Codes）<}
else
cout<<"错䨪误¨®！
ê?
！
ê?
请?
先¨¨输º?
入¨?
字Á?
符¤?
"<
;
break;
case52:
if（flag）
{
Huff.Decode（Pstr1,Pstr2,count2）;
cout<}
else
cout<<"错䨪误¨®！
ê?
！
ê?
请?
先¨¨输º?
入¨?
字Á?
符¤?
"<break;
case48:
exit（0）;
}
}
}
voidGetchar（）
{
count=0;
cin.getline（Str,1024）;
for（;Str[count]!
='\0';count++）
if（count==1024）throw"溢°?
出?
";
if（count==0）throw"错䨪误¨®！
ê?
！
ê?
请?
重?
新?
输º?
入¨?
";
intj=0,k=0;
charkey=Str[0];//
intcount1=0;
while（key!
='\0'）
{
count1=0;
for（inti=j;Str[i]!
='\0';i++）
{
if（key==Str[i]）
++count1;
}
j++;//Str[]的Ì?
序¨°号?
Count[k]=key;
Counti[k]=count1;
k++;//Count[],Counti[]的Ì?
序¨°号?
for（inti=0;iCount[]中D是º?
否¤?
已°?
经-存ä?
有®DStr[j]
{
if（Str[j]==Count[i]）
{
j++;
i=0;
}
}
key=Str[j];//找¨°到Ì?
Count[]中D没?
有®DStr[j]这a个?
字Á?
母?
}
Count[k]='\0';
count2=k;//储ä¡é存ä?
有®D多¨¤少¦¨´种?
字Á?
母?
}
升级会员 