哈夫曼树编码实验报告

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

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

3、文进行编码，然 后将结果存入“密文”文件中。23 译码：将“密文”文件中的 0、1代码序列进行译码。2.4 .打印“密文”文件：将文件以紧凑格式显示在终端上，每行30个代码; 同时，将此字符形式的编码文件保存。25打印哈夫曼树及哈夫曼编码：将已在内存中的哈夫曼树以凹入表形式 显示在终端上，同时将每个字符的哈夫曼编码显示出来；并保存到文件。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。2.5 输出码文函数/函数功能：从文件中输出哈夫曼树的码文vo

5、id HuffmanTree二PrintCodeFile（）2.6 函数功能：用凹入法输出哈夫曼树void HuffmanTree二PrintHuffmanTree_aoru(int T,int layer)3 .主模块的流程及各子模块的主要功能;哈夫曼编码/译码 系统建立哈夫曼树显示码文显示哈夫曼树显示哈夫曼树基本功能分析4 .模块之间的层次关系。 初始化：从键盘接收字符集大小n,以及n个字符和n个权值。 建立哈夫曼树：构造哈夫曼树，即将 HNode数组中的各个位置的各个域 都添上相关的值，并将这个结构体数组存于文件HTree.txt中。构造哈夫曼编码：为从文件HTree.txt中读入相关的

6、字符信息进行哈夫曼 编码，然后将结果存入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 LeafNum;2 .伪码算法public:HuffmanTree();HuffmanTree();void

8、 CreateHuffmanTree();void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();void Encoder。；void Decoder。；void PrintCodeFile();void PrintHuffmanTree();void PrintHuffmanTree_aoru(int T,int layer=1);一/构造函数/函数功能：初始化哈夫曼树HuffmanTree:HuffmanTree()Node=NULL;LeafNum=0;/函数功能：将哈夫曼的数组的空间释放/参数返回值：无

9、HuffmanTree:HuffmanTree() delete口 Node;/建立哈夫曼树函数/函数功能：建立哈夫曼树void HuffmanTree二CreateHuffmanTree()char Choose;coutChoose;if(Choose=2) CreateHuffmanTreeFromKeyboard();choose=2else /从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();/函数功能：从键盘建立哈夫曼树void HuffmanTree二CreateHuffmanTreeFromKeyboard()

10、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(); /源文的字符存入字符数组 Info口 getchar();coutNodei.weight; / 源文的字符权重存入 Node.weightNodei.parent=-1;Nodei.lchild=-1;Nodei.rch

11、ild=-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();/在所有子树的根结点中，选权重最小的两个根结点，posl最后应指向权重最小的根结点的下标for(int k=j-1;k=0;k-) if (Nodek.parent=-1)/如果是某棵子树的根结点if (Nodek.weightmax1) 发现比当前最大值还大的权重max2=max1;max1=Nodek.weight;pos2=pos

12、1;pos1=k;elseif(Nodek.weightmax2) /发现比当前次大值还大的次大权重max2=Nodek.weight;pos2=k;/if (Nodej.parent=-1) /for/在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上posh pos2所指向的结点Nodepos1.parent=j;Nodepos2.parent=j;Nodej.lchild=pos1;Nodej.rchild=pos2;Nodej.parent=-1;Nodej.weight=Nodepos1.weight+Nodepos2.weight; /for/产生所有叶子结点中字符的编码

13、for (int m=0;mNum;m+) /产生 Nodei.sourcecode 的编码，存入 Nodei.code 中int j=m;intj1;while(Nodej.parent!=-1) 从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code口j1=Nodej.parent;if(Nodej1.lchild=j)Nodem.code.insert(0,0);elseNodem.code.insert(0,1);j=j1;cout哈夫曼树已成功构造完成。n;char ch;coutch;if (ch!=y&ch!=Y) return;ofstream fop;fop.ope

14、n(hfmTree.dat,ios二out|ios二binary|ios:trunc);附丁 开文件if(fop.fail() coutn哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。n; return;fop.write(char*)&Num,sizeof(Num); /先写入哈夫曼树的叶子结点个数for(int n=0;n2*Num-1;n+) /最后写入哈夫曼树的各个结点(存储在Node口1fop.write(char*)&Noden,sizeof(Noden);flush(cout);fop.close(); /关闭文件coutn哈夫曼树已成功写入hfmTree.

15、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();retu

16、rn;Node=new HuffmanNode2*LeafNum-1;for(int i=0;i2*LeafNum-1;i+)fip.read(char*)&Nodei,sizeof(Nodei);fip.close();cout哈夫曼树已从文件成功构造完成。n;/编码函数/函数功能：为哈夫曼树编码void HuffmanTree二Encoder。if(Node=NULL) 内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();if (LeafNum=1) cout内存无哈夫曼树。操作撤销。nn;return;

17、/ifchar *SourceText;/让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入char Choose;coutChoose;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) SourceTex

18、tk+=ch;fip2.close();SourceText止0;else string SourceBuff;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+;SourceText止0;cout需编码的源文为：;coutSourceTextendl;ofstream fop(CodeFile.

19、dat,ios:trunc);打开码文存放文件int k=0;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;/函数功能：对哈夫曼树进行译码

20、void HuffmanTree二Decoder。/如果内存没有哈夫曼树，则从哈夫曼树文件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+

21、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;elsej=Nodej.rchild;if(Nodej.rchild=-1) /因为哈夫曼树没有度为1的结点，所以此条件等同于N

22、odej为叶结点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没有码文文件，无法显示码文文件内容。n”;return;while(fip.get(c

23、h)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;ofstream fop(TreePrint.dat,ios_base:trunc);fop.close();PrintHuffmanT

24、ree_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+) cout”;fop;if (NodeT.lchild=-1)coutNodeT.sourcecodeNodeT.weight(NodeT.code)endl;fopNodeT.sourcecodeNodeT.weight(NodeT.code)endl;else coutNodeT.weightendl;fopNodeT.weightendl;fop.close();PrintHuffmanTree_aoru(NodeT.rchild,layer+1);.int main()HuffmanTree huftree; char Choose;while(1)coutn*哈夫曼编码/ 译码*肝；cout*1.建立哈夫曼树*n;cout*2.编码*n;co