哈夫曼树专题报告.docx

哈夫曼树专题报告.docx

《哈夫曼树专题报告.docx》由会员分享，可在线阅读，更多相关《哈夫曼树专题报告.docx（31页珍藏版）》请在冰点文库上搜索。

哈夫曼树专题报告

专题设计（二叉树）报告

题目：

文件压缩（哈夫曼树）

小组成员：

吴旭晨（1120121358）

周浩天（1120121365）

熊威博（1120121359）

郝鑫钢（1120122756）

魏鑫（1120121357）

王俊博（1120121355）

2014/5/7

1.问题描述

在信息通信过程中，我们需要传输大量文件。

在大的文件中有许多冗余，为了提高信道利用率、缩短信息传输时间、降低传输成本，我们设计一个编译系统，发送方利用哈夫曼编码对文件进行压缩后传输，接收方将接收到的数据进行译码。

2.基本要求

一个完整的系统应具有以下功能：

（1）I：

初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

（2）E：

编码（Encoding）。

利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（3）D：

译码（Decoding）。

利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。

（4）P：

印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

（5）T：

印哈夫曼树（Treeprinting）。

将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

3.数据结构

利用字符和权值建立哈夫曼树求得哈夫曼编码。

利用二叉树先序遍历输出哈夫曼树。

4.测试数据

用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：

“THISPROGRAMEISMYFAVORITE”。

字符

A

B

C

D

E

F

G

H

I

J

K

L

M

频度

186

64

13

22

32

103

21

15

47

57

1

5

32

20

字符

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

频度

57

63

15

1

48

51

80

23

8

18

1

16

1

5.实验设计与实现

a、数据结构设计

在程序中要用到两种结构类型，一种是哈夫曼树的节点类型，另一种是哈夫曼编码的结构类型。

在哈夫曼树的节点类型中应该存放权值、左子链、右子链，另外为了在生成哈夫曼树时，能方便地由儿子节点找到父节点，要设置父节点链。

在编码类型中需要设置一个设置bit[]保存由叶节点到根节点的路径所对应的哈夫曼编码，还要设置一个数据域start表示哈夫曼编码在数组中的起始位置。

这样每个叶节点的哈夫曼编码是从数组bit[]的起始位置start开始到数组结束位置中存放的0和1的序列。

定义这两个结构类型的代码如下：

#definemaxlen100//最长编码

structNode//哈夫曼树的节点类型

{

intweight;//权重

intparent;

intlchild;

intrchild;

};

structHaffCode//哈夫曼编码的结构类型

{

intbit[maxlen];//存储编码

intstart;//记录编码开始的位置

intweight;//权重

charch;//存储对应的字符

};

b、实验流程图

c、实验实现

软件平台：

VC++6.0

硬件平台：

32位机器

d、主要功能模块分析：

（1）、哈夫曼树类定义

classHaffmanCode

{

private:

intnum;//字符集个数

Node*ht;//哈夫曼树

HaffCode*hc;//哈夫曼码

public:

HaffmanCode（）:

num（0）,ht（NULL）,hc（NULL）{};

~HaffmanCode（）;

voidbuildHfmtree（charstr[],intw[],intn）;//构造哈夫曼树

voidHfmcode（charstr[]）;//由哈夫曼树生成哈夫曼编码

voidencoding（）;

voiddecoding（）;

voidprintcode（）;

voidprinttree（）;//打印树的实例函数

voidprinttree（fstream&outfile,intn,intlen）;//打印树的递归函数

intloct（charc）;//查找字符c所在的下标

};

（2）、建立哈夫曼树。

1、从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

1　初始化，利用得到的字符集和对应的权值生成初始哈夫曼树；

2　把概率最小的两个符号组成一棵树；

3　重复步骤

（2）（3），构造哈夫曼树的n-1个分支结点；

2、由哈夫曼树生成哈夫曼编码

对每个叶结点都进行如下的处理：

扫描由叶结点到根结点的各条分支，

若分支中的当前结点与双亲结点是左支关系，则生成编码0，

若分支中的当前结点与双亲结点是右支关系，则生成编码1，

由此生成的二进制码的序列即为该结点的哈夫曼编码。

源代码：

//构造哈夫曼树

voidHaffmanCode:

:

buildHfmtree（charstr[],intw[],intn）

{

num=n;

ht=newNode[2*n-1];

hc=newHaffCode[n];

inti,j,m1,m2;//m1、m2分别表示最小、次小的权值

intx1,x2;//x1、x2分别表示当前分支结点的左右儿子

for（i=0;i<2*n-1;i++）//哈夫曼树初始化

{

if（i

ht[i].weight=w[i];

else

ht[i].weight=0;

ht[i].parent=-1;

ht[i].lchild=-1;

ht[i].rchild=-1;

}

for（i=0;i

{

m1=m2=1000;

x1=x2=0;

for（j=0;j

{

//在没挂进哈夫曼树的节点中寻找权值最小的节点

if（ht[j].parent==-1&&ht[j].weight

{

m2=m1;//最小保存到次小

x2=x1;

m1=ht[j].weight;

x1=j;

}

elseif（ht[j].parent==-1&&ht[j].weight

{

m2=ht[j].weight;

x2=j;

}

}

ht[x1].parent=n+i;

ht[x2].parent=n+i;

ht[n+i].weight=ht[x1].weight+ht[x2].weight;

ht[n+i].lchild=x1;

ht[n+i].rchild=x2;

}

Hfmcode（str）;//由哈夫曼树生成哈夫曼编码

}

//由哈夫曼树生成哈夫曼编码

voidHaffmanCode:

:

Hfmcode（charstr[]）

{

HaffCodecd;

intchild,parent,i,j;

for（i=0;i

{

cd.start=num-1;

cd.weight=ht[i].weight;

child=i;

parent=ht[child].parent;

while（parent!

=-1）

{

if（ht[parent].lchild==child）

cd.bit[cd.start]=0;

else

cd.bit[cd.start]=1;

cd.start--;

child=parent;

parent=ht[child].parent;

}

for（j=cd.start+1;j

hc[i].bit[j]=cd.bit[j];

hc[i].start=cd.start;

hc[i].weight=cd.weight;

hc[i].ch=str[i];

}

//将生成的哈夫曼编码写入文件hfmTree.txt

fstreamoutput;

output.open（"hfmTree.txt",ios:

:

out）;

if（!

output）

{

cout<<"hfmTree.txtcan'topen!

"<

abort（）;

}

for（i=0;i

{

output<

for（j=hc[i].start+1;j

output<

output<

}

output.close（）;

}

（3）、对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile

处理过程：

逐行读取文件ToBeTran中的正文，存储于字符数组ch中，然后对数组ch[]中的字符编码，并将结果存入文件CodeFile中。

源代码：

voidHaffmanCode:

:

encoding（）

{

fstreaminfile,outfile;

infile.open（"ToBeTran.txt",ios:

:

in）;

outfile.open（"CodeFile.txt",ios:

:

out）;

if（!

infile）

{

cout<<"ToBeTran.txtcan'topen!

"<

abort（）;

}

if（!

outfile）

{

cout<<"CodeFile.txtcan'topen!

"<

abort（）;

}

inti,j,loc;

charch[255];

while（!

infile.eof（））

{

infile.getline（ch,255）;

i=0;

while（ch[i]!

='\0'）

{

loc=loct（ch[i]）;

if（loc!

=-1）

for（j=hc[loc].start+1;j

outfile<

i++;

}

}

infile.close（）;

outfile.close（）;

}

（4）、利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，将结果存入TextFile中。

处理过程：

逐行读取文件CodeFile中的正文，存储于字符数组ch中，然后利用哈夫曼树对数组ch[]中的字符译码。

源代码：

voidHaffmanCode:

:

decoding（）

{

fstreaminfile,outfile;

infile.open（"CodeFile.txt",ios:

:

in）;

outfile.open（"TextFile.txt",ios:

:

out）;

if（!

infile）

{

cout<<"CodeFile.txtcan'topen!

"<

abort（）;

}

if（!

outfile）

{

cout<<"TextFile.txtcan'topen!

"<

abort（）;

}

inti,j;

charch[255];

memset（ch,'5',255）;

while（!

infile.eof（））

{

infile.getline（ch,255）;

i=0;

while（ch[i]!

='\0'）

{

j=2*num-2;//j指向根节点

while（ht[j].lchild!

=-1）//直到叶子节点

{

if（ch[i]=='1'）

j=ht[j].rchild;

else

j=ht[j].lchild;

i++;

}

cout<

outfile<

}

}

cout<

infile.close（）;

outfile.close（）;

}

6.测试与结论

a、建哈夫曼树并建立哈夫曼树，并将它存于文件hfmTree.txt中。

b、利用已建好的哈夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（1）、文件ToBeTran中的正文为：

THISPROGRAMISMYFAVORITE

（2）、文件CodeFile中的结果为：

c、利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。

由上图可知，译码出来的结果和ToBeTran.txt中的内容一样。

文件Textfile.txt中的内容为：

d、将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

文件CodePrin：

e、将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

7、总结与思考

拿到题目的时候比较困惑，毕竟自己的C/C++学的不是很好，而且是使用在数据结构中间哈夫曼树中，后来看了很多有关的例子，仔细看了书上的哈夫曼树部分的知识，觉得就是书上的许许多多的内容和代码，其实总体来说，应该不会特别的难。

后来，参照书上的和网上的诸多例子，一个模块一个模块的编写，调试，一个功能一个功能去完善。

发现越做越顺利，又有以前用C/C++写的各个程序的代码，回头看了一下自己当年编写的程序，加上实验中对于改错的经验积累和几个学得不错的同学的帮助，我的程序中的错误也一个一个的顺利解决。

其实，这个对于文本文件的操作以前也有涉及到过，但是以前的时候总是以数组或者指针的形式进行调用，这一次直接才有的是I/O流，觉得效果还是很不错的。

再后来，我的程序终于就基本实现了。

其实，从这次实验中我认识到，我距离高手还很远，编程有很多的乐趣也有很多的技巧性和知识性。

我将在以后的日子里继续认真的学习知识，积累经验，让自己的编程能力提高。

附录：

程序代码

#define_HaffmanTree_h_

#include

#include

#include

#include

usingnamespacestd;

#definemaxlen100//最长编码

structHaffNode//哈夫曼树的节点类型

{

intweight;//权重

intparent;

intlchild;

intrchild;

};

structHaffCode//哈夫曼编码的结构类型

{

intbit[maxlen];//存储编码

intstart;//记录编码开始的位置

intweight;//权重

charch;//存储对应的字符

};

classHaffmanTree

{

private:

intnum;//字符集个数

HaffNode*ht;//哈夫曼树

HaffCode*hc;//哈夫曼码

public:

HaffmanTree（）:

num（0）,ht（NULL）,hc（NULL）{}

~HaffmanTree（）;

voidbuildHfmtree（charstr[],intw[],intn）;//构造哈夫曼树

voidHfmcode（charstr[]）;//由哈夫曼树生成哈夫曼编码

voidencoding（）;

voiddecoding（）;

voidprintcode（）;

voidprinttree（）;//打印树的实例函数

voidprinttree（fstream&outfile,intn,intlen）;//打印树的递归函数

intloct（charc）;//查找字符c所在的下标

};

HaffmanTree:

:

~HaffmanTree（）

{

delete[]ht;

delete[]hc;

}

//构造哈夫曼树

voidHaffmanTree:

:

buildHfmtree（charstr[],intw[],intn）

{

num=n;

ht=newHaffNode[2*n-1];

hc=newHaffCode[n];

inti,j,m1,m2;//m1、m2分别表示最小、次小的权值

intx1,x2;//x1、x2分别表示当前分支结点的左右儿子

for（i=0;i<2*n-1;i++）//哈夫曼树初始化

{

if（i

ht[i].weight=w[i];

else

ht[i].weight=0;

ht[i].parent=-1;//下标号>=0，所以初始化为负数，下同。

ht[i].lchild=-1;

ht[i].rchild=-1;

}

for（i=0;i

{

m1=m2=1000;

x1=x2=0;

for（j=0;j

{

if（ht[j].parent==-1&&ht[j].weight

{

m2=m1;//最小保存到次小

x2=x1;

m1=ht[j].weight;

x1=j;

}

elseif（ht[j].parent==-1&&ht[j].weight

{

m2=ht[j].weight;

x2=j;

}

}

ht[x1].parent=n+i;

ht[x2].parent=n+i;

ht[n+i].weight=ht[x1].weight+ht[x2].weight;

ht[n+i].lchild=x1;

ht[n+i].rchild=x2;

}

Hfmcode（str）;

}

//由哈夫曼树生成哈夫曼编码

voidHaffmanTree:

:

Hfmcode（charstr[]）

{

HaffCodecd;

intchild,parent,i,j;

for（i=0;i

{

cd.start=num-1;

cd.weight=ht[i].weight;

child=i;

parent=ht[child].parent;

while（parent!

=-1）

{

if（ht[parent].lchild==child）

cd.bit[cd.start]=0;

else

cd.bit[cd.start]=1;

cd.start--;

child=parent;

parent=ht[child].parent;

}

for（j=cd.start+1;j

hc[i].bit[j]=cd.bit[j];

hc[i].start=cd.start;

hc[i].weight=cd.weight;

hc[i].ch=str[i];

}

//将生成的哈夫曼编码写入文件hfmTree.txt

fstreamoutput;

output.open（"hfmTree.txt",ios:

:

out）;

if（!

output）

{

cout<<"hfmTree.txtcan'topen!

"<

abort（）;

}

for（i=0;i

{

output<

for（j=hc[i].start+1;j

output<

output<

}

output.close（）;

}

//功能：

对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile

voidHaffmanTree:

:

encoding（）

{

fstreaminfile,outfile;

infile.open（"ToBeTran.txt",ios:

:

in）;

outfile.open（"CodeFile.txt",ios:

:

out）;

if（!

infile）

{

cout<<"ToBeTran.txtcan'topen!

"<

abort（）;

}

if（!

outfile）

{

cout<<"CodeFile.txtcan'topen!

"<

abort（）;

}

inti,j,loc;

charch[255];

while（!

infile.eof（））

{

infile.getline（ch,255）;

i=0;

while（ch[i]!

='\0'）

{

loc=loct（ch[i]）;

if（loc!

=-1）

for（j=hc[loc].start+1;j

outfile<

i++;

}

}

infile.close（）;

outfile.close（）;

}

//功能：

利用已建好的哈夫曼树将文件CodeFile中的代码进行