haff

东华理工大学软件学院软件工程系

1

数据结构课程设计报告

题目：哈夫曼编码与解码

学生姓名：侯清源

学号：1021111118

班级：102111111

指导教师：张军

2012年6月1日

东华理工大学软件学院软件工程系

2

目录

需求分析说明

总体设计

详细设计

实现部分

程序测试部分

实验总结

附图：开发环境和工程文件介绍

东华理工大学软件学院软件工程系

3

1，需求分析说明

A，通信线路中实现信息的最大传送，利用变长编码的方式，

可以有效充分利用带宽，实现信息传送前的压缩。

B，在文件保存时，利用哈夫曼编码的方式，压缩文件。可以

实现硬盘存储最大的信息量。

C，实验目的：

1，.学会使用哈夫曼进行对文本文件的编码与译码。

2，通过对哈夫曼的编码与译码，能够理解通信领域中的数据传输

的压缩原理。

3，通过对哈夫曼的编码/译码器的研究与分析，能够彻底的理解软

件设计的一般步骤和方法，灵活地运用各种数据结构进行操作，

熟练地把所学地数据结构应用地软件开发当中，提高软件设计水

平，增强程序设计能力。

D，实现功能

压缩：实现对用户输入的字符串压缩，并在终端显示相应字符对应的

频率，编码，编码长度，平均编码长度，字符个数。

并显示字符串编码后的二进制文件。

解压：实现对压缩后的二进制文件解压，还原为原来的字符串。并显

示在终端。和用户输入的字符串比较。

2，总体设计

2,1开发环境介绍

编译器：gcc4.6.3

编辑器：vim7.0附插件：ctags、taglist、autocomplpop。

打开syntaxenable、syntaxon、tnumber。

操作系统：Ubuntu12.04LTS

硬件环境：Processor：Intel(R)Core™i5-2430CPU@2.40GHz

Vendor:AcerTravelMate4750GBusinessLaptop

Memory:4G

2.2系统框架

系统结构流程

东华理工大学软件学院软件工程系

4

算法思想描述（文字和图）

1，首先，根据用户输入的字符串得到字符频率。根据频率得到频率数据，对该频率数组由

栈顶到栈低由小到大排列，同时将从小到大顺序存入优先队列

2，构造哈弗曼树，过程如下：从栈中取出两个最小频率。按照左小右大的原则。构造哈弗

曼树。同时生成父节点，即频率和。同时父节点入栈，重新按照由小到大的顺序排列。

3，重复2过程，直到栈为空。

4，编码解码的过程

编码时，根据哈弗曼树，左0右1，建立map>容器，右边存储字符，

右边存储编码。编码时，从根节点递归遍历算法编码，左节点编码时添加0，右节点编

码添加1

解码时，也是根据哈弗曼编码树，从根节点开始，如果碰到编码的首部是1，往右遍历；

如果是0，往左遍历。直到叶子节点，遍历匹配字符成功，返回匹配的字符。同时回到

根节点，重复该步骤，翻译下一个编码。

3，详细设计

3.1，类模板设计

1，类模板设计资料：高永平老师给的资料：《数据结构（STL框架）》王晓东编

著，陈道蓄主审

2，主要是STL编程，并利用了vectormapqueue等容器，使用了容器的迭代器

iterator

东华理工大学软件学院软件工程系

5

哈夫曼树类结构模板Hafftree类模板原型

Template

Hufftree

+template

Hufftree(InputIteratorbegin,InputIteratorend);构造哈夫曼树

+~Hufftree()析构函数

+template

vectorencode(InputIteratorbegin,InputIteratorend);编码

+vectorencode(DataTypeconst&value);返回字符编码

+doubleencodelength(DataTypeconst&value);返回字符编码长度

+template

voiddecode(vectorconst&v,OutputIteratoriter);对字符串解码

-classNode;字符串节点类

-classNodeOrder;排序时用的类

-Node*tree;根节点

-typedefmap>encodemap;

encodemapencodetable;编码表

Node类成员：

template

Node

+Frequencyfreqeuency;权或频率

+Node*leftChild;左孩子指针

+union

Node*rightChild;右孩子指针

DataType*data;字符域指针

Template

NodeOrder初始化的时候对节点排序

3.2，类模板设计源代码（排版：QtCreator4.7）

Hufftree头文件

//----------------------------------------------------//

//哈夫编码与解码Haffmanencoding&decoding//

//作者：HoustarAuthorByHoustar//

//----------------------------------------------------//

#ifndefHuffman_H

#defineHuffman_H

#include

#include

#include

usingnamespacestd;

/*哈夫模板设计，需要参数：数据类型和频率*/

template

东华理工大学软件学院软件工程系

6

classHufftree

{

public:

/*输入迭代器，区间固定至begin到end,生成哈夫树*/

template

Hufftree(InputIteratorbegin,InputIteratorend);

/*析构函数，删除树*/

~Hufftree(){deletetree;}

/*哈夫编码，区间固定至begin到end*/

template

vectorencode(InputIteratorbegin,InputIteratorend);

/*返回单个字符的编码*/

vectorencode(DataTypeconst&value)

{

returnencodetable[value];

}

/*返回字符的编码长*/

doubleencodelength(DataTypeconst&value)

{

typenameencodemap::iteratoriter=(value);

returniter->();

}

/*哈夫解码,输入待解码的数组V，输出iter*/

template

voiddecode(vectorconst&v,OutputIteratoriter);

private:

classNode;//节点类

Node*tree;//指向树的指针

typedefmap>encodemap;

encodemapencodetable;//存储哈夫编码后的表

classNodeOrder;

};

template

structHufftree::Node

{

Frequencyfrequency;//字符出现的频率或权

Node*leftChild;//左边孩子指针

union

{

东华理工大学软件学院软件工程系

7

Node*rightChild;//ifleftChild!=NULL如果不是叶子节点

DataType*data;//ifleftChild==NULL如果是叶子节点

};

/*节点的构造函数,通过给基类传值构造*/

Node(Frequencyf,DataTyped):

frequency(f),

leftChild(0),

data(newDataType(d))

{

}

/*构造函数，该函数用来求父节点（最小两个节点出列，同时构造父节点）入列*/

Node(Node*left,Node*right):

frequency(left->frequency+right->frequency),

leftChild(left),

rightChild(right)

{

}

/*析构函数*/

~Node()

{

if(leftChild)

{

deleteleftChild;

deleterightChild;

}

el

{

deletedata;

}

}

/*该函数对哈夫树的各个节点进行0，1编码*/

voidfill(map>&encodetable,

vector&prefix)

{

if(leftChild)//递归到叶子节点停止，叶子节点：左孩子为空

{

_back(0);//尾部加0

leftChild->fill(encodetable,prefix);//递归调用该函数

()=1;//传回最后一个数据

rightChild->fill(encodetable,prefix);//递归调用该函数

_back();//删除最后一个数据

}

el

encodetable[*data]=prefix;//将字符对应的编码存入数组的一个元素中，下

东华理工大学软件学院软件工程系

8

标由

//data确定，即data为keyword,prefix为01010的编码

}

};

/*根据权值或频率生成哈夫树*/

template

template//InputIterator为频率或权值表，是二元组数组。存储字符及频率

Hufftree::Hufftree(InputIteratorbegin,

InputIteratorend):

tree(0)

{

priority_queue,NodeOrder>pqueue;//构造了一个优先队列，并非

FIFO

//优先队列参数说明：

//priority_queue

//其中Type为数据类型，Container为保存数据的容器，Functional为元素比较方式。

//数据类型节点类。存储容器为vector，排序方式为按权从小到大

while(begin!=end)//往优先队列添加权值二元组。

{

/*生成频率或权值的节点类，节点左边指向频率，右边指向字符*/

Node*dataNode=newNode(begin->cond,begin->first);//l.r

(dataNode);

++begin;

}

while(!())//队列不为空

{

Node*top=();//队首出列

();//清空队首

if(())//队列为空

{

tree=top;

}

el

{

Node*top2=();//队首出列

();

(newNode(top,top2));

}

}

vectorbitvec;//存储二进制编码的数组

tree->fill(encodetable,bitvec);//对树的各个节点进行0，1编码

}

/*该函数主要是节点进行排序，重载了（）运算符*/

东华理工大学软件学院软件工程系

9

template

structHufftree::NodeOrder

{

booloperator()(Node*l,Node*r)

{

if(r->frequencyfrequency)//如果右边频率小于左边

returntrue;

if(l->frequencyfrequency)//如果左边频率小于右边

returnfal;

if(!l->leftChild&&r->leftChild)//b节点存在左孩子

returntrue;

if(l->leftChild&&!r->leftChild)//a节点存在左孩子

returnfal;

if(l->leftChild&&r->leftChild)//均存在左孩子

{

if((*this)(l->leftChild,r->leftChild))

returntrue;

if((*this)(r->leftChild,l->leftChild))

returnfal;

return(*this)(l->rightChild,r->rightChild);

}

return*(l->data)<*(r->data);

}

};

template

template//InputIterator为待编码的字符串

vectorHufftree::encode(InputIteratorbegin,

InputIteratorend)

{

vectorresult;//存储编码后的文件即010100111

while(begin!=end)//从第一个字符扫描到最后一个字符

{

/*从字符编码表中寻找对应字符的编码，并转换为该字符编码*/

typenameencodemap::iteratori=(*begin);

/*将该字符编码插入已完成的文件00101后面.例如aabc.已经将aa编码为11碰到

b，

编码为00.添加到编码文件尾部*/

((),i->(),i->());

++begin;

}

东华理工大学软件学院软件工程系

10

returnresult;

}

template

template

voidHufftree::decode(vectorconst&v,//01001码

OutputIteratoriter/*源码*/)

{

Node*node=tree;//指向根节点

for(vector::const_iteratori=();i!=();++i)

{

/*对二进制码和节点对应的二进制码进行比较*/

node=*i?node->rightChild:node->leftChild;

if(!node->leftChild)//比较到叶子节点则返回叶子节点对应的字符

{

*iter++=*(node->data);//将对应字符加到文件中

node=tree;//重新回到根节点，翻译下一个二进制码

}

}

}

#endif//Huffman_H

主函数文件

#include"huffman.h"

#include

#include

#include

#include

#include

#include

#include

usingnamespacestd;

mapfrequencies;

doublesum=0;

ostream&operator<<(ostream&os,vectorvec)//重载运算符

{

copy((),(),ostream_iterator(os,""));

returnos;

}

mapfresTable(string&s)//生成字符频率表

{

for(string::const_iteratoriter=();iter!=();iter++)

{

frequencies[*iter]++;

++sum;

东华理工大学软件学院软件工程系

11

}

returnfrequencies;

}

intmain(intargc,char*argv[])

{

cout<<"----SourceFile----"<

stringsource;

doublefre;

doublelenAve;

cin>>source;

frequencies=fresTable(source);

cout<<"----Encode&decodeTable----"<

Hufftreehufftree((),());

typedeftypenamemap::iteratorit;

cout<

<

for(ititer=();iter!=();iter++)

{

fre=iter->cond/sum;

cout<first<<

tw(10)<cond<<

tw(10)<<(iter->first)<<

tw(10)<first)<<

tw(10)<

tw(10)<first))<

lenAve+=fre*length(iter->first);

}

cout<

cout<

cout<<"----EncodedFile----"<

vectorencoded=((),());

cout<

cout<<"----DecodedFile----"<

stringdestination;

(encoded,back_inrter(destination));

cout<

return0;

}

4，实现部分

东华理工大学软件学院软件工程系

12

在程序调试阶段，编译不出错，运行时经常出现gmentationerror，accessviolation！

后来才知道，是自己指针操作不当，访问内存错误！用GDB调试才找出了错误。总

结，总结，再总结，绝不再次犯错误！

5，程序测试部分

5.1对英文字符编码解码

a，由用户输入英文字符串，统计频率。打印字符出现次数F，频率f，字符对应编码encode，

平均编码长lenAve。整个字符串长度Sum，平均编码长lenAve。

5.2算法改进的地方，对中文，标点等进行编码解码。

东华理工大学软件学院软件工程系

13

6,实验总结

在本次实验中，学习并深入理解了数据结构的相关设计。在本例中，对问题的深入思

考，培养了自己的创造能力，使得程序可以对任意文件编码和译码。但是对于汉字，问题的

提出如下：汉字是两个字节存储的，可是我编码的时候却只对汉字的一个字节，那么解码的

时候，会不会出现a汉字和b汉字的前半部分编码相同，这样解码的时候会出现错误？出现

错误又该如何解决？有待以后深入思考！

7，附图：开发环境和工程文件

Vim+ctag+taglist+autocomplpop

编译器和操作系统信息

东华理工大学软件学院软件工程系

14

Unubu12.04LTS桌面

工程文件介绍

huffman.h头文件

主函数cpp文件

Makefilemake文件，编译直接敲make

huffman编译好的可执行文件i686-linux平台

注意：该工程不能在VC6.0下编译，原因是VC6.0编译器不支持类

模板嵌套编译！！只能在gcc里面编译·.·