哈弗曼树编码译码综合实验报告

院系：计算机学院

实验课程：数据结构预算法

实验项目：哈弗曼树综合实验

指导老师：

开课时间：2009 ～ 2010年度第1学期专业：计算机类

班级：08本6班

学生：

学号：

华南师范大学教务处

华南师范大学实验报告

学生姓名禤欢子学号20082100173

专业计算机类年级、班级08本6 班

课程名称数据结构与算法分析实验项目哈弗曼树综合实验

实验时间2009年12月25日指导老师黄定

实验评分

----------------------------------------------------------------------------------------------------------------------

【需求分析】

本实验需要设计程序，输入叶子结点和权值，建立一颗哈弗曼树，并根据哈弗曼树进行编码和译码操作。键盘中输入或者从文件中读入哈弗曼树；键盘中输入或者从源文件中读入需要编码的源文，然后将源文根据哈弗曼树的权值，译码为二进制代码。最后实现凹入显示法显示哈弗曼树。

【概念设计】

本程序由HaffmanTree.h、HaffmanTree.cpp、main.cpp三个文件构成。HaffmanTree.h中定义了哈弗曼树的储存结构体HaffmanNode，里面定义了weight、parent、lchild、rchild四个变量来描述哈弗曼树的储存结构。在HaffmanTree.h中还定义了一个名为HaffmanTree的类，里面定义的是建树、编码、译码和凹入显示哈弗曼树等函数，而相关的实现代码则在HaffmanTree.cpp中给出。main.cpp中主要是实现内部函数与用户界面的对接。

【详细设计】

具体代码实现如下：

//HaffmanTree.h

#include

#include

#include

struct HuffmanNode //哈夫曼树的一个结点

{

int weight;

int parent;

int lchild,rchild;

};

class HuffmanTree //哈夫曼树

{

private:

HuffmanNode *Node; //Node[]存放哈夫曼树

char *Info; //Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放

int LeafNum; //哈夫曼树的叶子个数，也是源码个数

public:

HuffmanTree();

~HuffmanTree();

void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node[]中。让用户从两种建立哈夫曼树的方法中选择：

1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，

并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/

void CreateHuffmanTreeFromKeyboard();

void CreateHuffmanTreeFromFile();

void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），

对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。

ToBeTran的内容可以用记事本等程序编辑产生。*/

void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，

则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，

得到的源文写入文件TextFile中，并同时输出到屏幕上。*/ void PrintCodeFile(); /*将码文文件CodeFile显示在屏幕上*/

void PrintHuffmanTree(); /*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上，

同时写入文件TreePrintFile中*/

void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/

};

///////////////////////////////////////////////////////////////////HuffmanTree.

cpp

#include

#include //为使用整型最大值

#include"HuffmanTree.h"

using namespace std;

//******************************************************

HuffmanTree::HuffmanTree()

{

Node=NULL;

}

//******************************************************

HuffmanTree::~HuffmanTree()

{

delete[]Node;

}

//******************************************************

void HuffmanTree::CreateHuffmanTree()

{

char Choose;

cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？";

cin>>Choose;

if(Choose=='2') {//键盘输入建立哈夫曼树

CreateHuffmanTreeFromKeyboard();

}//choose=='2'

else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树

CreateHuffmanTreeFromFile();

}

}

//******************************************************

void HuffmanTree::CreateHuffmanTreeFromKeyboard()

{

int Num;

cout<<"\n请输入源码字符集个数：";

cin>>Num;

if (Num<=1)

{

cout<<"无法建立少于2个叶子结点的哈夫曼树。\n\n";

return;

}

LeafNum=Num;

Node=new HuffmanNode[2*Num-1];

Info=new char[2*Num-1];

for(int i=0;i

cout<<"请输入第"<

getchar();

Info[i]=getchar(); //源文的字符存入字符数组Info[]

getchar();

cout<<"请输入该字符的权值或频度";

cin>>Node[i].weight; //源文的字符权重存入Node[].weight

Node[i].parent=-1;

Node[i].lchild=-1;

Node[i].rchild=-1;

}

for(i=Num;i<2*Num-1;i++)

{//循环建立哈夫曼树内部结点

int pos1=-1,pos2=-1;

int max1=32767,max2=32767;

for(int j=0;j

if(Node[j].parent==-1)//是否为根结点

if(Node[j].weight

{

max2=max1;

max1=Node[j].weight;

pos2=pos1;

pos1=j;

}

else

if(Node[j].weight

{

max2=Node[j].weight;

pos2=j;

}

Node[pos1].parent=i;

Node[pos2].parent=i;

Node[i].lchild=pos1;

Node[i].rchild=pos2;

Node[i].parent=-1;

Node[i].weight=Node[pos1].weight+Node[pos2].weight;

} //for

cout<<"哈夫曼树已成功构造完成。\n";

//把建立好的哈夫曼树写入文件hfmTree.dat

char ch;

cout<<"是否要替换原来的哈夫曼树文件(Y/N):";

cin>>ch;

if (ch!='y'&&ch!='Y') return;

else

{

ofstream fop;

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(i=0;i

{ //再写入源文字符集的所有字符（存储在Info[]中）

fop.write((char*)&Info[i],sizeof(Info[i]));

flush(cout);

}

for(i=0;i<2*Num-1;i++)

{ //最后写入哈夫曼树的各个结点（存储在Node[]中）

fop.write((char*)&Node[i],sizeof(Node[i]));

flush(cout);

}

fop.close(); //关闭文件

cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。\n";

}

}

//******************************************************

void HuffmanTree::CreateHuffmanTreeFromFile()

{

ifstream fip;

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;

}

Info=new char[LeafNum];

Node=new HuffmanNode[2*LeafNum-1];

for(int i=0;i

fip.read((char*)&Info[i],sizeof(Info[i]));

for(i=0;i<2*LeafNum-1;i++)

fip.read((char*)&Node[i],sizeof(Node[i]));

fip.close();

cout<<"哈夫曼树已成功构造完成。\n";

}

//******************************************************

void HuffmanTree::Encoder()

{

if(Node==NULL)

{//内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();

if (LeafNum<=1)

{

cout<<"内存无哈夫曼树。操作撤销。\n\n";

return;

}

}//if

char *SourceText; //字符串数组，用于存放源文

//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入

char Choose;

cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？";

cin>>Choose;

if(Choose=='1')

{

ifstream fip1("ToBeTran.txt");

if(fip1.fail())

{

cout<<"源文文件打开失败!无法继续执行。\n";

return;

}

char ch;

int k=0;

while(fip1.get(ch)) k++; //第一次读文件只统计文件中有多少个字符，将字符数存入k

fip1.close();

SourceText=new char[k+1]; //申请存放源文的字符数组空间

ifstream fip2("ToBeTran.txt");//第二次读源文文件，把内容写入SourceText[] k=0;

while(fip2.get(ch)) SourceText[k++]=ch;

fip2.close();

SourceText[k]='\0';

cout<<"需编码的源文为：";

cout<

}

else

{ //从键盘输入源文

string SourceBuff;

cin.ignore();

cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):\n";

getline(cin,SourceBuff,'\n');

int k=0;

while(SourceBuff[k]!='\0')

k++;

SourceText=new char[k+1];

k=0;

while(SourceBuff[k]!='\0')

{

SourceText[k]=SourceBuff[k];

k++;

}

SourceText[k]='\0';

cout<<"覆盖已有的编码原文件?（Y/N）";

char ch;

cin>>ch;

if(ch=='y'||ch=='Y')

{

ofstream fip2;

fip2.open("ToBeTran.txt");

if(!fip2)

{

cerr<<"文件打开失败！"<

abort();

}

fip2<

fip2.close();

cout<<"需编码的源文已写入ToBeTran.txt中"<

}

}

//开始编码

ofstream fop("CodeFile.dat",ios::trunc); //打开码文存放文件

char *code;

code=new char[LeafNum]; //存放一个源文字符的编码

int k=0;

while(SourceText[k]!='\0') //源文串中从第一个字符开始逐个编码{

int star=0;

char ch=SourceText[k];

for(int i=0;i

if(Info[i]==ch)//求出该文字所在的单元编号

break;

int j=i;

while(Node[j].parent!=-1)

{

j=Node[j].parent;

if(Info[Node[j].lchild]==Info[i]) code[star++]='0';

else code[star++]='1';

i=j;

}

code[star]='\0';

for(i=0;i

{

int j=code[i];

code[i]=code[star-i-1];

code[star-i-1]=j;

}

i=0; //将源文的当前字符的对应编码写入码文文件

while(code[i]!='\0')

{

fop<

i++;

}

k++; //源文串中的字符后移一个

}

fop.close();

cout<<"已完成编码，码文已写入文件CodeFile.dat中。\n\n";

}

//******************************************************

void HuffmanTree::Decoder()

{

//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树if(Node==NULL)

{

CreateHuffmanTreeFromFile();

if (LeafNum<=1)

{

cout<<"内存无哈夫曼树。操作撤销。\n\n";

return;

}

}

//将码文从文件CodeFile.dat中读入 CodeStr[]

ifstream fip1("CodeFile.dat");

if(fip1.fail())

{

cout<<"没有码文，无法译码。\n";

return;

}

char* CodeStr;

int k=0;

char ch;

while(fip1.get(ch))

{

k++;

}

fip1.close();

CodeStr=new char[k+1];

ifstream fip2("CodeFile.dat");

k=0;

while(fip2.get(ch)) CodeStr[k++]=ch;

fip2.close();

CodeStr[k]='\0';

cout<<"经译码得到的源文为：";

ofstream fop("TextFile.dat");

int j=LeafNum*2-1-1; //j指向哈夫曼树的根

int i=0; //码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子

while(CodeStr[i]!='\0')

{ //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符

if(CodeStr[i]=='0') j=Node[j].lchild;

else j=Node[j].rchild;

if(Node[j].rchild==-1)

{

cout<

fop<

j=LeafNum*2-1-1;

}

i++;

}

fop.close();

cout<<"\n译码成功且已存到文件TextFile.dat中。\n\n";

}

//****************************************************** void HuffmanTree::PrintCodeFile()

{

char ch;

int i=1;

ifstream fip("CodeFile.dat");

ofstream fop("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();

}

//******************************************************

void HuffmanTree::PrintHuffmanTree()

{

//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树if(Node==NULL)

{

CreateHuffmanTreeFromFile();

if (LeafNum<=1)

{

cout<<"内存无哈夫曼树。操作撤销。\n\n";

return;

}

}

ofstream fop("TreePrint.dat",ios_base::trunc);

fop.close();

PrintHuffmanTree_aoru(2*LeafNum-1-1,0);

return;

}

//******************************************************

void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer)

{

for(int i=0;i

cout<

if(Node[T].lchild!=-1) PrintHuffmanTree_aoru(Node[T].lchild,++layer);

if(Node[T].rchild!=-1) PrintHuffmanTree_aoru(Node[T].rchild,layer--);

}

///////////////////////////////////////////////////////////////////main.cpp

#include"HuffmanTree.h"

#include

#include

using namespace std;

int main()

{

HuffmanTree huftree;

char Choose;

while(1)

{

cout<<"\n\n**********************欢迎使用哈夫曼编码/译码系统***********************"<

cout<<"您可以进行以下操作:"<

cout<<"1 建立哈夫曼树 3 译码(码文已在文件CodeFile中) 5 显示哈夫曼树"<

cout<<"2 编码(源文已在文件ToBeTran中，或键盘输入) 4 显示码文 6 退出 "<

cout<<"请选择一个操作:";

cin>>Choose;

switch(Choose)

{

case '1':

huftree.CreateHuffmanTree();

break;

case '2':

huftree.Encoder();

break;

case '3':

huftree.Decoder();

break;

case '4':

huftree.PrintCodeFile();

break;

case '5':

huftree.PrintHuffmanTree();

break;

case '6':

cout<<"\n*************************感谢使用本系统!***********************\n\n";

system("pause");

return 0;

}//switch

}//while

}//main

【用户手册】

进入哈弗曼树系统，出现以下界面：

1建立弗曼树 2、编码（源文中读入，键盘输入） 3、译码 4、显示码文 5、显示哈弗曼树 6、退出

用户根据该提示，选择前面数字，就能进入各个功能函数，实现函数功能。

【运行结果】

截图一：

截图二：

截图三：

【心得体会】

本实验是有老师提供模板，然后自己增加功能函数的代码实现的。因此，在完成未完成的功能函数之前还必须要细心阅读所给出代码，

整体观察各个部分之前的联系，搞清楚已给出和未完成的代码功能之后，才根据算法，设计出该功能的函数代码。

在完成实验时，有发现老师所给出代码也有纰漏的地方，如在源文件读入的时候，多出了一个值，得要增加下表减这个代码来去掉。还有就是在译码的时候，由于变量定义的混淆，在编译的时候通过，但执行时却出现意料不到的结果，在自己细心观察、思考之前也还没找出错误之处。后来通过请教老师，在和老师讨论检查之后才知道了错误之所在，最后改正错误。实验成功完成。

【参考文献】

数据结构与算法（课本）

C++语言基础

本文来源：https://www.bwwdw.com/article/7g8l.html