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

院系：计算机学院实验课程：数据结构预算法实验项目：哈弗曼树综合实验指导老师：开课时间：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#includeiostream#includefstream#includestringstructHuffmanNode//哈夫曼树的一个结点{intweight;intparent;intlchild,rchild;};classHuffmanTree//哈夫曼树{private:HuffmanNode*Node;//Node[]存放哈夫曼树char*Info;//Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放intLeafNum;//哈夫曼树的叶子个数，也是源码个数public:HuffmanTree();~HuffmanTree();voidCreateHuffmanTree();/*在内存中建立哈夫曼树，存放在Node[]中。让用户从两种建立哈夫曼树的方法中选择：1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/voidCreateHuffmanTreeFromKeyboard();voidCreateHuffmanTreeFromFile();voidEncoder();/*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。ToBeTran的内容可以用记事本等程序编辑产生。*/voidDecoder();/*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，得到的源文写入文件TextFile中，并同时输出到屏幕上。*/voidPrintCodeFile();/*将码文文件CodeFile显示在屏幕上*/voidPrintHuffmanTree();/*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上，同时写入文件TreePrintFile中*/voidPrintHuffmanTree_aoru(intT,intlayer=1);/*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/};///////////////////////////////////////////////////////////////////HuffmanTree.cpp#includestring#includelimits//为使用整型最大值#includeHuffmanTree.husingnamespacestd;//******************************************************HuffmanTree::HuffmanTree(){Node=NULL;}//******************************************************HuffmanTree::~HuffmanTree(){delete[]Node;}//******************************************************voidHuffmanTree::CreateHuffmanTree(){charChoose;cout你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？;cinChoose;if(Choose=='2'){//键盘输入建立哈夫曼树CreateHuffmanTreeFromKeyboard();}//choose=='2'else{//从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();}}//******************************************************voidHuffmanTree::CreateHuffmanTreeFromKeyboard(){intNum;cout\n请输入源码字符集个数：;cinNum;if(Num=1){cout无法建立少于2个叶子结点的哈夫曼树。\n\n;return;}LeafNum=Num;Node=newHuffmanNode[2*Num-1];Info=newchar[2*Num-1];for(inti=0;iNum;i++){//读入哈夫曼树的叶子结点信息cout请输入第i+1个字符值;getchar();Info[i]=getchar();//源文的字符存入字符数组Info[]getchar();cout请输入该字符的权值或频度;cinNode[i].weight;//源文的字符权重存入Node[].weightNode[i].parent=-1;Node[i].lchild=-1;Node[i].rchild=-1;}for(i=Num;i2*Num-1;i++){//循环建立哈夫曼树内部结点intpos1=-1,pos2=-1;intmax1=32767,max2=32767;for(intj=0;ji;j++)//在根节点中选出权值最小的两个if(Node[j].parent==-1)//是否为根结点if(Node[j].weightmax1){max2=max1;max1=Node[j].weight;pos2=pos1;pos1=j;}elseif(Node[j].weightmax2){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;}//forcout哈夫曼树已成功构造完成。\n;//把建立好的哈夫曼树写入文件hfmTree.datcharch;cout是否要替换原来的哈夫曼树文件(Y/N):;cinch;if(ch!='y'&&ch!='Y')return;else{ofstreamfop;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;iNum;i++){//再写入源文字符集的所有字符（存储在Info[]中）fop.write((char*)&Info[i],sizeof(Info[i]));flush(cout);}for(i=0;i2*Num-1;i++){//最后写入哈夫曼树的各个结点（存储在Node[]中）fop.write((char*)&Node[i],sizeof(Node[i]));flush(cout);}fop.close();//关闭文件cout\n哈夫曼树已成功写入hfmTree.dat文件。\n;}}//******************************************************voidHuffmanTree::CreateHuffmanTreeFromFile(){ifstreamfip;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=newchar[LeafNum];Node=newHuffmanNode[2*LeafNum-1];for(inti=0;iLeafNum;i++)fip.read((char*)&Info[i],sizeof(Info[i]));for(i=0;i2*LeafNum-1;i++)fip.read((char*)&Node[i],sizeof(Node[i]));fip.close();cout哈夫曼树已成功构造完成。\n;}//******************************************************voidHuffmanTree::Encoder(){if(Node==NULL){//内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();if(LeafNum=1){cout内存无哈夫曼树。操作撤销。\n\n;return;}}//ifchar*SourceText;//字符串数组，用于存放源文//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入charChoose;cout你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？;cinChoose;if(Choose=='1'){ifstreamfip1(ToBeTran.txt);if(fip1.fail()){cout源文文件打开失败!无法继续执行。\n;return;}charch;intk=0;while(fip1.get(ch))k++;//第一次读文件只统计文件中有多少个字符，将字符数存入kfip1.close();SourceText=newchar[k+1];//申请存放源文的字符数组空间ifstreamfip2(ToBeTra