哈夫曼树编码实验报告.docx
《哈夫曼树编码实验报告.docx》由会员分享，可在线阅读，更多相关《哈夫曼树编码实验报告.docx（23页珍藏版）》请在冰点文库上搜索。
哈夫曼树编码实验报告
、
数据结构课程设计
报告
题目：
哈夫曼编码/译码
学院数学与信息科学学院
学科门类理科
专业数学类
学号2013433033
姓名田娟
2014年12月30日
一、需求分析
1．程序的功能··················································3
2．输入输出的要求··············································3
3．测试数据····················································3
二、概要设计
1．本程序所用的抽象数据类型的定义·······························3
2．主程序模块···················································3
3．主模块的流程及各子模块的主要功能·····························4
4．模块之间的层次关系···········································4
三、详细设计
1．采用c语言定义相关的数据类型·································4
2.伪码算法·····················································5
四、调试分析
1．调试中遇到的问题及对问题的解决方法···························15
五、使用说明及测试结果
1.建立哈夫曼树，输入叶子结点个数，权值，字符集··················15
2.编码··························································15
3.译码··························································16
4.显示码文······················································16
5.显示哈夫曼树··················································16
六、源程序
一、需求分析
1．程序的功能；
哈夫曼编码是一种应用广泛而有效的数据压缩技术。
利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。
数据压缩的过程称为编码，解压缩的过程称为译码。
进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码，而接收端将传来的数据（密文）进行译码。
2．输入输出的要求；：
2.1．构造哈夫曼树及哈夫曼编码：
从终端读入字符集大小n、n个字符以及n个对应的权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存。
2.2编码：
利用已构造的哈夫曼编码对“明文”文件中的正文进行编码，然后将结果存入“密文”文件中。
2.3．译码：
将“密文”文件中的0、1代码序列进行译码。
2.4．打印“密文”文件：
将文件以紧凑格式显示在终端上，每行30个代码；同时，将此字符形式的编码文件保存。
2.5．打印哈夫曼树及哈夫曼编码：
将已在内存中的哈夫曼树以凹入表形式显示在终端上，同时将每个字符的哈夫曼编码显示出来；并保存到文件。
3．测试数据。
3.1.令叶子结点个数N为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。
3.2.请自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码。
二、概要设计
1．本程序所用的抽象数据类型的定义；
classHuffmanTree//哈夫曼树
{
private:
HuffmanNode*Node;//Node[]存放哈夫曼树
intLeafNum;//哈夫曼树的叶子个数，也是源码个数
2.主程序模块
main（）
2.2建立哈夫曼树函数
//函数功能：
建立哈夫曼树
voidHuffmanTree:
:
CreateHuffmanTree（）
2.3函数功能：
为哈夫曼树编码
voidHuffmanTree:
:
Encoder（）
2.4函数功能：
对哈夫曼树进行译码
voidHuffmanTree:
:
Decoder（）
2.5输出码文函数
//函数功能：
从文件中输出哈夫曼树的码文
voidHuffmanTree:
:
PrintCodeFile（）
2.6函数功能：
用凹入法输出哈夫曼树
voidHuffmanTree:
:
PrintHuffmanTree_aoru（intT,intlayer）
3．主模块的流程及各子模块的主要功能；
哈夫曼编码/译码系统
建立哈夫曼树
编码
显示码文
译码
显示哈夫曼树
显示哈夫曼树
基本功能分析
4．模块之间的层次关系。
①初始化：
从键盘接收字符集大小n，以及n个字符和n个权值。
②建立哈夫曼树：
构造哈夫曼树，即将HNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件HTree.txt中。
③构造哈夫曼编码：
为从文件HTree.txt中读入相关的字符信息进行哈夫曼编码，然后将结果存入HNode.txt中，同时将字符与0、1代码串的一一对应关系打印到屏幕上。
④编码：
利用已构造的哈夫曼编码（HNode.txt）对文件SourceFile.txt（明文）中的正文进行编码，然后将结果存入文件CodeFile.txt（密文）中。
⑤译码：
将文件CodeFile.txt（密文）中的代码按照③中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，进行译码，结果存入文件TextFile.txt（明文）中。
（如果正确，TextFile.txt的内容与SourceFile.txt的内容一致）
⑥显示哈夫曼树：
从HNode数组中读入相关的结点信息，以凹入表方式将各个结点以及叶子结点的权值和左分支上的0和右分支上的
三、详细设计
1．采用c语言定义相关的数据类型；
结点的类型定义描述如下：
structHuffmanNode//哈夫曼树的一个结点
{
intweight;
intparent;
intlchild,rchild;
charsourcecode;
std:
:
stringcode;
};
classHuffmanTree//哈夫曼树
{
private:
HuffmanNode*Node;//Node[]存放哈夫曼树
intLeafNum;
2.伪码算法
public:
HuffmanTree（）;
~HuffmanTree（）;
voidCreateHuffmanTree（）;
voidCreateHuffmanTreeFromKeyboard（）;
voidCreateHuffmanTreeFromFile（）;
voidEncoder（）;
voidDecoder（）;
voidPrintCodeFile（）;
voidPrintHuffmanTree（）;
voidPrintHuffmanTree_aoru（intT,intlayer=1）;
};
//构造函数
//函数功能：
初始化哈夫曼树
HuffmanTree:
:
HuffmanTree（）
{
Node=NULL;
LeafNum=0;
}
//函数功能：
将哈夫曼的数组的空间释放
//参数返回值：
无
HuffmanTree:
:
~HuffmanTree（）
{
delete[]Node;
}
//建立哈夫曼树函数
//函数功能：
建立哈夫曼树
voidHuffmanTree:
:
CreateHuffmanTree（）
{
charChoose;
cout<<"从键盘输入哈夫曼树（按2）？
";
cin>>Choose;
if（Choose=='2'）{
CreateHuffmanTreeFromKeyboard（）;
}//choose=='2'
else{//从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile（）;
}
}
//函数功能：
从键盘建立哈夫曼树
voidHuffmanTree:
:
CreateHuffmanTreeFromKeyboard（）{
intNum;
cout<<"\n请输入源码字符集个数：
";
cin>>Num;
if（Num<=1）{
cout<<"无法建立少于2个叶子结点的哈夫曼树。
\n\n";
return;
}
LeafNum=Num;
Node=newHuffmanNode[2*Num-1];
for（inti=0;icout<<"请输入第"<getchar（）;
Node[i].sourcecode=getchar（）;//源文的字符存入字符数组Info[]
getchar（）;
cout<<"请输入该字符的权值";
cin>>Node[i].weight;//源文的字符权重存入Node[].weight
Node[i].parent=-1;
Node[i].lchild=-1;
Node[i].rchild=-1;
Node[i].code="\0";
}
for（intj=Num;j<2*Num-1;j++）{//循环建立哈夫曼树内部结点
intpos1,pos2;
intmax1,max2;
pos2=pos1=j;
max2=max1=numeric_limits:
:
max（）;
//在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标
for（intk=j-1;k>=0;k--）{
if（Node[k].parent==-1）{//如果是某棵子树的根结点
if（Node[k].weightmax2=max1;
max1=Node[k].weight;
pos2=pos1;
pos1=k;
}
else
if（Node[k].weightmax2=Node[k].weight;
pos2=k;
}
}//if（Node[j].parent==-1）
}//for
//在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2所指向的结点
Node[pos1].parent=j;
Node[pos2].parent=j;
Node[j].lchild=pos1;
Node[j].rchild=pos2;
Node[j].parent=-1;
Node[j].weight=Node[pos1].weight+Node[pos2].weight;
}//for
//产生所有叶子结点中字符的编码
for（intm=0;m//产生Node[i].sourcecode的编码，存入Node[i].code中
intj=m;
intj1;
while（Node[j].parent!
=-1）{//从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code[]
j1=Node[j].parent;
if（Node[j1].lchild==j）
Node[m].code.insert（0,"0"）;
else
Node[m].code.insert（0,"1"）;
j=j1;
}
}
cout<<"哈夫曼树已成功构造完成。
\n";
charch;
cout<<"是否要替换原来的哈夫曼树文件（Y/N）:
";
cin>>ch;
if（ch!
='y'&&ch!
='Y'）return;
ofstreamfop;
fop.open（"hfmTree.dat",ios:
:
out|ios:
:
binary|ios:
:
trunc）;//打开文件
if（fop.fail（））{
cout<<"\n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。
\n";
return;
}
fop.write（（char*）&Num,sizeof（Num））;//先写入哈夫曼树的叶子结点个数
for（intn=0;n<2*Num-1;n++）{//最后写入哈夫曼树的各个结点（存储在Node[]中）
fop.write（（char*）&Node[n],sizeof（Node[n]））;
flush（cout）;
}
fop.close（）;//关闭文件
cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。
\n";
}
//从文件建立哈夫曼树函数
//函数功能：
从文件建立哈夫曼树
voidHuffmanTree:
:
CreateHuffmanTreeFromFile（）{
ifstreamfip;
fip.open（"hfmTree.dat",ios:
:
binary|ios:
:
in）;
if（fip.fail（））{
cout<<"哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。
\n";
return;
}
fip.read（（char*）&LeafNum,sizeof（LeafNum））;
if（LeafNum<=1）{
cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。
\n";
fip.close（）;
return;
}
Node=newHuffmanNode[2*LeafNum-1];
for（inti=0;i<2*LeafNum-1;i++）
fip.read（（char*）&Node[i],sizeof（Node[i]））;
fip.close（）;
cout<<"哈夫曼树已从文件成功构造完成。
\n";
}
//编码函数
//函数功能：
为哈夫曼树编码
voidHuffmanTree:
:
Encoder（）
{
if（Node==NULL）{//内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile（）;
if（LeafNum<=1）{
cout<<"内存无哈夫曼树。
操作撤销。
\n\n";
return;
}
}//if
char*SourceText;
//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入
charChoose;
cout<<"从键盘输入源文（按2）？
";
cin>>Choose;
if（Choose=='1'）{
ifstreamfip1（"ToBeTran.txt"）;
if（fip1.fail（））{
cout<<"源文文件打开失败!
无法继续执行。
\n";
return;
}
charch;
intk=0;
while（fip1.get（ch））k++;
fip1.close（）;
SourceText=newchar[k+1];
ifstreamfip2（"ToBeTran.txt"）;
k=0;
while（fip2.get（ch））SourceText[k++]=ch;
fip2.close（）;
SourceText[k]='\0';
}
else{
stringSourceBuff;
cin.ignore（）;
cout<<"请输入需要编码的源文（按回车键结束）:
\n";
getline（cin,SourceBuff,'\n'）;
intk=0;
while（SourceBuff[k]!
='\0'）
k++;
SourceText=newchar[k+1];
k=0;
while（SourceBuff[k]!
='\0'）{
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}
cout<<"需编码的源文为：
";
cout<ofstreamfop（"CodeFile.dat",ios:
:
trunc）;//打开码文存放文件
intk=0;
while（SourceText[k]!
='\0'）//源文串中从第一个字符开始逐个编码
{
inti;
for（i=0;iif（Node[i].sourcecode==SourceText[k]）{//将对应编码写入码文文件
fop<break;
};
}
if（i>=LeafNum）{
cout<<"源文中存在不可编码的字符。
无法继续执行。
\n"<fop.close（）;
return;
}
k++;
}
fop.close（）;
cout<<"已完成编码，码文已写入文件CodeFile.dat中。
\n\n";
}
//函数功能：
对哈夫曼树进行译码
voidHuffmanTree:
:
Decoder（）
{
//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if（Node==NULL）
{
CreateHuffmanTreeFromFile（）;
if（LeafNum<=1）{
cout<<"内存无哈夫曼树。
操作撤销。
\n\n";
return;
}
}
ifstreamfip1（"CodeFile.dat"）;
if（fip1.fail（））{
cout<<"没有码文，无法译码。
\n";
return;
}
char*CodeStr;
intk=0;
charch;
while（fip1.get（ch））{
k++;
}
fip1.close（）;
CodeStr=newchar[k+1];
ifstreamfip2（"CodeFile.dat"）;
k=0;
while（fip2.get（ch））
CodeStr[k++]=ch;
fip2.close（）;
CodeStr[k]='\0';
cout<<"经译码得到的源文为：
";
ofstreamfop（"TextFile.dat"）;
intj=LeafNum*2-1-1;
inti=0;
while（CodeStr[i]!
='\0'）{//下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符
if（CodeStr[i]=='0'）
j=Node[j].lchild;
else
j=Node[j].rchild;
if（Node[j].rchild==-1）{//因为哈夫曼树没有度为1的结点，所以此条件等同于Node[j]为叶结点
cout<fop<j=LeafNum*2-1-1;
}
i++;
}
fop.close（）;
cout<<"\n译码成功且已存到文件TextFile.dat中。
\n\n";
}
//输出码文函数
//函数功能：
从文件中输出哈夫曼树的码文
voidHuffmanTree:
:
PrintCodeFile（）
{
charch;
inti=1;
ifstreamfip（"CodeFile.dat"）;
ofstreamfop（"CodePrin.dat"）;
if（fip.fail（））
{
cout<<"没有码文文件，无法显示码文文件内容。
\n";
return;
}
while（fip.get（ch））
{
cout<fop<if（i==50）
{
cout<fop<i=0;
}
i++;
}
cout<fop<fip.close（）;
fop.close（）;
}
//输出函数
//函数功能：
从内存或文件中直接输出哈夫曼树
voidHuffmanTree:
:
PrintHuffmanTree（）
{
if（Node==NULL）
{
CreateHuffmanTreeFromFile（）;
if（LeafNum<=1）{
cout<<"内存无哈夫曼树。
操作撤销。
\n\n";
return;
}
}
ofstreamfop（"TreePrint.dat",ios_base:
:
trunc）;
fop.close（）;
PrintHuffmanTree_aoru（2*LeafNum-1-1）;
return;
}
//凹入法输出函数
//函数功能：
用凹入法输出哈夫曼树
voidHuffmanTree:
:
PrintHuffmanTree_aoru（intT,intlayer）{
if（T!
=-1）{
PrintHuffmanTree_aoru（Node[T].lchild,layer+1）;
ofstreamfop（"TreePrint.dat",ios_base:
:
app）;
cout<fop<for（inti=0;icout<<"";
fop<<"";
}
if（Node[T].lchild==-1）{
cout<fop<}
升级会员 