哈夫曼树编码实验报告

1、. . 、数据结构课程设计报告题目：哈夫曼编码 / 译码学院数学与信息科学学院学科门类理科专业数学类学号 2013433033 姓名田娟 2014年 12 月 30 日. . 目录一、 需求分析1程序的功能 3 2输入输出的要求 33测试数据 3 二、概要设计1本程序所用的抽象数据类型的定义 3 2主程序模块 3 3主模块的流程及各子模块的主要功能 4 4模块之间的层次关系 4 三、详细设计1采用 c 语言定义相关的数据类型 4 2. 伪码算法 5 四、调试分析1调试中遇到的问题及对问题的解决方法 15 五、使用说明及测试结果1. 建立哈夫曼树，输入叶子结点个数，权值，字符集 15 2. 编码

2、 15 3. 译码 16 4. 显示码文 16 5. 显示哈夫曼树 16 六、源程序. . 一、需求分析1程序的功能；哈夫曼编码是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率， 加快信息传输速度， 降低传输成本。 数据压缩的过程称为编码， 解压缩的过程称为译码。 进行信息传递时， 发送端通过一个编码系统对待传数据（明文）预先编码，而接收端将传来的数据（密文）进行译码。2输入输出的要求；：2.1 构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n 个字符以及n 个对应的权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存。2.2 编码：利

3、用已构造的哈夫曼编码对“明文”文件中的正文进行编码，然后将结果存入“密文”文件中。2.3 译码：将“密文”文件中的0、1 代码序列进行译码。2.4 打印“密文”文件：将文件以紧凑格式显示在终端上，每行 30 个代码；同时，将此字符形式的编码文件保存。2.5 打印哈夫曼树及哈夫曼编码：将已在内存中的哈夫曼树以凹入表形式显示在终端上，同时将每个字符的哈夫曼编码显示出来；并保存到文件。3测试数据。3.1. 令叶子结点个数 n为 4， 权值集合为 1,3,5,7， 字符集合为 a,b,c,d ，且字符集与权值集合一一对应。3.2. 请自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫

4、曼树，构造哈夫曼编码，并实现其编码和译码。二、概要设计1本程序所用的抽象数据类型的定义；class huffmantree /哈夫曼树 private: huffmannode *node; /node存放哈夫曼树 int leafnum; /哈夫曼树的叶子个数，也是源码个数2. 主程序模块main() 2.2 建立哈夫曼树函数/ 函数功能：建立哈夫曼树void huffmantree:createhuffmantree() 2.3 函数功能：为哈夫曼树编码void huffmantree:encoder() 2.4 函数功能：对哈夫曼树进行译码void huffmantree:decoder

5、() 2.5 输出码文函数/ 函数功能：从文件中输出哈夫曼树的码文. . void huffmantree:printcodefile() 2.6 函数功能：用凹入法输出哈夫曼树void huffmantree:printhuffmantree_aoru(int t,int layer) 3主模块的流程及各子模块的主要功能；基本功能分析4模块之间的层次关系。 初始化：从键盘接收字符集大小n，以及 n 个字符和 n 个权值。 建立哈夫曼树：构造哈夫曼树，即将hnode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件htree.txt中。 构造哈夫曼编码：为从文件htree.tx

6、t中读入相关的字符信息进行哈夫曼编码，然后将结果存入hnode.txt 中，同时将字符与0、1 代码串的一一对应关系打印到屏幕上。 编码：利用已构造的哈夫曼编码（hnode.txt ）对文件sourcefile.txt（明文）中的正文进行编码，然后将结果存入文件codefile.txt（密文）中。 译码：将文件codefile.txt（密文）中的代码按照中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，进行译码，结果存入文件textfile.txt（明文）中。 （如果正确， textfile.txt的内容与 sourcefile.txt的内容一致） 显示哈夫曼树：从hnode数组中读入

7、相关的结点信息，以凹入表方式将各个结点以及叶子结点的权值和左分支上的0 和右分支上的三、详细设计1采用 c 语言定义相关的数据类型；结点的类型定义描述如下：struct huffmannode /哈夫曼树的一个结点 哈夫曼编码/译码系统建立哈夫曼树编码显示码文译码显示哈夫曼树显示哈夫曼树. . int weight; int parent; int lchild,rchild; char sourcecode; std:string code; ; class huffmantree /哈夫曼树 private: huffmannode *node; /node存放哈夫曼树 int leafn

8、um; 2. 伪码算法public: huffmantree(); huffmantree(); void createhuffmantree(); void createhuffmantreefromkeyboard(); void createhuffmantreefromfile(); void encoder(); void decoder(); void printcodefile(); void printhuffmantree(); void printhuffmantree_aoru(int t,int layer=1); ; / 构造函数/ 函数功能：初始化哈夫曼树huffm

9、antree:huffmantree() node=null; leafnum=0; / 函数功能：将哈夫曼的数组的空间释放/ 参数返回值：无huffmantree:huffmantree() delete node; / 建立哈夫曼树函数/ 函数功能：建立哈夫曼树void huffmantree:createhuffmantree() . . char choose; coutchoose; if(choose=2) createhuffmantreefromkeyboard(); /choose=2 else /从哈夫曼树文件 hfmtree.dat 中读入信息并建立哈夫曼树 create

10、huffmantreefromfile(); / 函数功能：从键盘建立哈夫曼树void huffmantree:createhuffmantreefromkeyboard() int num; coutnum; if (num=1) cout无法建立少于 2 个叶子结点的哈夫曼树。 nn; return; leafnum=num; node=new huffmannode2*num-1; for(int i=0;inum;i+) /读入哈夫曼树的叶子结点信息 cout请输入第 i+1 个字符值 ; getchar(); nodei.sourcecode=getchar(); /源文的字符存入字

11、符数组info getchar(); coutnodei.weight; /源文的字符权重存入node.weight nodei.parent=-1; nodei.lchild=-1; nodei.rchild=-1; nodei.code=0; for(int j=num;j2*num-1;j+) /循环建立哈夫曼树内部结点 int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits:max( ); /在所有子树的根结点中，选权重最小的两个根结点，pos1 最后应指向权重最小的根结点的下标for(int k=j-1;

12、k=0;k-) if (nodek.parent=-1)/如果是某棵子树的根结点. . if (nodek.weightmax1) /发现比当前最大值还大的权重 max2=max1; max1=nodek.weight; pos2=pos1; pos1=k; else if(nodek.weightmax2) /发现比当前次大值还大的次大权重 max2=nodek.weight; pos2=k; /if (nodej.parent=-1) /for / 在下标 i 处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2 所指向的结点 nodepos1.parent=j; nod

13、epos2.parent=j; nodej.lchild=pos1; nodej.rchild=pos2; nodej.parent=-1; nodej.weight=nodepos1.weight+nodepos2.weight; /for /产生所有叶子结点中字符的编码 for (int m=0;mnum;m+) /产生 nodei.sourcecode的编码，存入 nodei.code中 int j=m; int j1; while(nodej.parent!=-1) / 从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code j1=nodej.parent; if(nodej

14、1.lchild=j) nodem.code.insert(0,0); else nodem.code.insert(0,1); j=j1; cout 哈夫曼树已成功构造完成。n; char ch; coutch; . . if (ch!=y&ch!=y) return; ofstream fop; fop.open(hfmtree.dat,ios:out|ios:binary|ios:trunc); /打开文件 if(fop.fail() coutn哈夫曼树文件打开失败， 无法将哈夫曼树写入hfmtree.dat 文件。n; return; fop.write(char*)&

15、num,sizeof(num); /先写入哈夫曼树的叶子结点个数 for(int n=0;n2*num-1;n+) /最后写入哈夫曼树的各个结点（存储在node 中） fop.write(char*)&noden,sizeof(noden); flush(cout); fop.close(); /关闭文件 coutn哈夫曼树已成功写入hfmtree.dat 文件。 n; / 从文件建立哈夫曼树函数/ 函数功能：从文件建立哈夫曼树void huffmantree:createhuffmantreefromfile() ifstream fip; fip.open(hfmtree.dat,

16、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=new huffmannode2*leafnum-1; for(int i=0;i2*leafnum-1;i+) fip.read(char*)&nodei,sizeof(

17、nodei); fip.close(); cout哈夫曼树已从文件成功构造完成。n; / 编码函数/ 函数功能：为哈夫曼树编码. . void huffmantree:encoder() if(node=null) /内存没有哈夫曼树，则从哈夫曼树文件hfmtree.dat中读入信息并建立哈夫曼树 createhuffmantreefromfile(); if (leafnum=1) cout内存无哈夫曼树。操作撤销。nn; return; /if char *sourcetext; /让用户选择源文是从键盘输入， 还是从源文文件 tobetran.txt中读入 char choose; co

18、utchoose; if(choose=1) ifstream fip1(tobetran.txt); if(fip1.fail() cout源文文件打开失败 ! 无法继续执行。 n; return; char ch; int k=0; while(fip1.get(ch) k+; fip1.close(); sourcetext=new chark+1; ifstream fip2(tobetran.txt); k=0; while(fip2.get(ch) sourcetextk+=ch; fip2.close(); sourcetextk=0; else string sourcebuf

19、f; cin.ignore(); cout请输入需要编码的源文 ( 按回车键结束 ):n; getline(cin,sourcebuff,n); int k=0; while(sourcebuffk!=0) k+; sourcetext=new chark+1; . . k=0; while(sourcebuffk!=0) sourcetextk=sourcebuffk; k+; sourcetextk=0; cout 需编码的源文为： ; coutsourcetextendl; ofstream fop(codefile.dat,ios:trunc); /打开码文存放文件 int k=0;

20、while(sourcetextk!=0) /源文串中从第一个字符开始逐个编码 int i; for(i=0;ileafnum;i+) /找到当前要编码的源文的字符在哈夫曼树node 中的下标 if(nodei.sourcecode=sourcetextk) /将对应编码写入码文文件 fop=leafnum) cout源文中存在不可编码的字符。无法继续执行。nendl; fop.close(); return; k+; fop.close(); cout 已完成编码，码文已写入文件codefile.dat中。nn; / 函数功能：对哈夫曼树进行译码void huffmantree:decode

21、r() / 如果内存没有哈夫曼树， 则从哈夫曼树文件 hfmtree.dat中读入信息并建立哈夫曼树 if(node=null) . . createhuffmantreefromfile(); if (leafnum=1) cout内存无哈夫曼树。操作撤销。nn; return; 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 chark+

22、1; ifstream fip2(codefile.dat); k=0; while(fip2.get(ch) codestrk+=ch; fip2.close(); codestrk=0; cout 经译码得到的源文为： ; ofstream fop(textfile.dat); int j=leafnum*2-1-1; int i=0; while(codestri!=0) /下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符 if(codestri=0) j=nodej.lchild; else j=nodej.rchild; if(nodej.rchild=-1) /因为哈夫曼树

23、没有度为1 的结点，所以此条件等同于 nodej 为叶结点 coutnodej.sourcecode; fopnodej.sourcecode; . . j=leafnum*2-1-1; i+; fop.close(); coutn译码成功且已存到文件textfile.dat中。nn; / 输出码文函数/ 函数功能：从文件中输出哈夫曼树的码文void huffmantree:printcodefile() char ch; int i=1; ifstream fip(codefile.dat); ofstream fop(codeprin.dat); if(fip.fail() cout没有码

24、文文件，无法显示码文文件内容。n; return; while(fip.get(ch) coutch; fopch; if(i=50) coutendl; fopendl; i=0; i+; coutendl; fopendl; fip.close(); fop.close(); / 输出函数/ 函数功能：从内存或文件中直接输出哈夫曼树void huffmantree:printhuffmantree() if(node=null) . . createhuffmantreefromfile(); if (leafnum=1) cout内存无哈夫曼树。操作撤销。nn; return; ofst

25、ream fop(treeprint.dat,ios_base:trunc); fop.close(); printhuffmantree_aoru(2*leafnum-1-1); return; / 凹入法输出函数/ 函数功能：用凹入法输出哈夫曼树void huffmantree:printhuffmantree_aoru(int t,int layer) if (t!=-1) printhuffmantree_aoru(nodet.lchild,layer+1); ofstream fop(treeprint.dat,ios_base:app); coutendl; fopendl; for (int i=0;ilayer*5;i+) cou