您好,欢迎访问三七文档
数学与计算机学院数据结构实验报告年级09数计学号2009432125姓名刘宝成绩专业数电实验地点主楼401指导教师苗秀芬实验项目哈夫曼树解决编码解码实验日期10年12月24日一、实验目的本实验的目的是通过对简单的哈夫曼编/译码系统的设计与实现来熟练掌握树形结构在实际问题中的应用。二、实验问题描述利用哈夫曼编码进行通信可以大大提高通信利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,此试验即设计这样的一个简单的编/译码系统。系统应该具备如下的几个功能。1、求出各个叶子节点的权重值输入一个字符串,统计其中各个字母的个数和总的字母个数。2、构造哈夫曼树统计出的字母种类为叶子结点个数,每个字母个数为相应的权值,建立哈夫曼树。3、打印哈弗曼树的功能模块按照一定形式打印出哈夫曼树。4、编码利用已经建立好的哈夫曼树进行编码。5、译码根据编码规则对输入的代码进行翻译并将译码。三、实验步骤1、实验问题分析一1一设计一个结构体数组保存字母的类型和个数。typedefstruct{charch;//字母的种类intnum;//字母的个数}inf;一2一在构造哈夫曼树时,设计一个结构体数组Hufftree保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个结点的哈夫曼树共有2n-1个结点,所以数组大小设置为2n-1,描述结点的数据类型为:typedefstruct{intweight;//权值intparent;//双亲intlchild;//左孩子intrchild;//右孩子}Hnodetype;typedefHnodetypeHufftree[maxnode];//定义此类型的数组、3、求哈夫曼编码,实质上是在已经建立的哈夫曼树中,从叶子结点开始,沿着结点的双亲链表域退回到根节点,每退回一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼值,由于一个字符的哈夫曼编码是从根结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码为所求编码的高位码,所以设计如下的数据类型:constintmaxbit=10;typedefstruct{intbit[maxbit];//每个结点的哈夫曼编码intstart;//开始位置}Hcodetype;一4一设置全局变量。strings;//s为输入的字符串intn=0;//记录输入的字符串中字母的种类,即叶子结点个数intv=0;//记录字符串中字母的总个数infinfo[maxleaf];//叶子结点类型2、功能(函数)设计一1一统计字母种类和个数模块此模块的功能为从键盘接受一个字符串,统计字符串中字母种类即结点个数,每种字母出现次数即各叶子结点的权值。全局变量s保存输入的字符串,将种类和个数保存到info[maxleaf]中。函数原型:voidfundchar()如输入的字符串是“sddfffgggg”则显示如下。一2一哈夫曼树的建立模块此模块的功能为从(1)中计算出的结点个数和各个叶子结点的权值构造一棵哈弗曼树。函数原型:Hnodetype*huffmantree()//函数返回结点类型的数组一3一打印哈弗曼树的功能模块此模块的功能是将由(2)建立的哈弗曼树按照一定规则weight,lchild,rchild,parent打印在屏幕上。函数原型:voidprint(Hnodetype*hufftree)如输入的字符串是”sddfffgggg”,则构造的哈夫曼树为一4一建立哈夫曼编码的功能模块此模块功能为将(2)中建立的哈夫曼树进行哈弗曼编码,然后将字符与对应的0、1代码串打印到屏幕上。函数原型:voidhuffmancode(Hnodetype*hufftree)如输入的字符串是“sddfffgggg”,则每个字母的代码和输入的字符串的哈夫曼编码是一5一译码的功能模块此模块的功能为接收需要译码的0和1代码串,按照(4)中建立的编码规则将其翻译成字符集中字符所组成的字符串形式,并将翻译的结果在屏幕上打印出来。函数原型:voidtranslation(Hnodetype*hufftree)如输入的代码串是“110111100”,则对应的字符串是“sdfg”四、实验结果(程序)及分析1、实验主要模块代码(一)函数功能:统计字母种类和个数模块voidfundchar(){intk,m;cout请输入字符串endl;cins;//s为输入的字符串while(s[v]){v++;}cout共有字符v个endl;//v是全局变量info[0].ch=s[0];info[0].num=1;for(k=1;k=v;k++)//统计s中字母种类和个数{for(m=0;m=n;m++){if(info[m].ch==s[k]){++info[m].num;break;}}if(mn){info[++n].ch=s[k];info[n].num=1;}}for(m=0;mn;m++)//输出种类和个数cout字符info[m].ch有info[m].num个endl;}(一)函数功能:哈弗曼树的建立模块Hnodetype*huffmantree(){Hnodetype*hufftree=newHufftree;inti,j,m1,m2,x1,x2;//m1记录最小的重权值,m2为次小for(i=0;i2*n-1;i++){//结点初始化hufftree[i].parent=-1;hufftree[i].weight=0;hufftree[i].lchild=-1;hufftree[i].rchild=-1;}for(i=0;in;i++)//将每个字母的个数当做叶子结点的权值hufftree[i].weight=info[i].num;for(i=0;in-1;i++){m1=m2=maxvalue;x1=x2=0;for(j=0;jn+i;j++){if(hufftree[j].parent==-1&&hufftree[j].weightm1){m2=m1;x2=x1;m1=hufftree[j].weight;x1=j;//x1记录最小重权值在数组中的下标}elseif(hufftree[j].parent==-1&&hufftree[j].weightm2){m2=hufftree[j].weight;x2=j;//x2记录次小重权值在数组中的下标}}hufftree[x1].parent=n+i;hufftree[x2].parent=n+i;hufftree[n+i].weight=m1+m2;hufftree[n+i].lchild=x1;hufftree[n+i].rchild=x2;}returnhufftree;//返回数组首地址}(一)函数功能:打印哈弗曼树的功能模块voidprint(Hnodetype*hufftree){coutendlendlendl;//界面优化cout哈弗曼树----endl;coutweightlchildrchildparentendl;//界面优化for(inti=0;i2*n-1;i++)couthufftree[i].weighthufftree[i].lchildhufftree[i].rchildhufftree[i].parentendl;}(一)函数功能:建立哈弗曼编码的功能模块voidhuffmancode(Hnodetype*hufftree){Hcodetypehuffcode[maxleaf],cd;inti,j,c,p;for(i=0;in;i++){//求每个结点的哈弗曼编码cd.start=n-1;c=i;p=hufftree[c].parent;while(p!=-1){//由叶子结点向上直到树根if(hufftree[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=hufftree[c].parent;}for(j=cd.start+1;jn;j++)//将结果保存huffcode[i].bit[j]=cd.bit[j];//保存每位号码huffcode[i].start=cd.start;//保存开始位置}coutendlendlendl;cout哈弗曼编码endl;for(i=0;in;i++)//打印各个字母对应的编码{cout-----------endl;coutinfo[i].ch的代码是;for(j=huffcode[i].start+1;jn;j++)couthuffcode[i].bit[j];coutendl;}cout-----------endl;coutendl输入的字符串的哈夫曼编码为:endl;for(i=0;iv;i++)//打印输入的字符串的编码结果for(inty=0;y=n;y++)if(s[i]==info[y].ch){for(j=huffcode[y].start+1;jn;j++)couthuffcode[y].bit[j];}coutendl;}(一)函数功能:译码的功能模块voidtranslation(Hnodetype*hufftree){stringcode;//code记录输入的0,1代码intt;coutendlendlendl;cout请输入代码串:;cincode;intnum=0;while(code[num])num++;//确定0,1代码长度Hnodetype*p=&hufftree[2*n-2];coutendlendlendl;cout译码结果----endl;for(inti=0;inum;i++){if(code[i]=='0')//从根向下p=&hufftree[p-lchild];elsep=&hufftree[p-rchild];if(p-lchild==-1&&p-rchild==-1){//如果到达叶子结点t=p-weight;//保存叶子结点的权值for(intj=0;jn;j++)if(hufftree[j].weight==t){coutinfo[j].ch;//输出权值的对应的字母break;}p=&hufftree[2*n-2];//重新从根节点开始}}coutendl;}2、测试数据sfddaaassss实验结果截图3、调试过程中出现的问题以及解决策略译码模块中,如果输入的代码串无对应的字母,则会出错。解决办法:提示用户输入时注意附最终代码:#includeiostream#includestring#definemaxvalue12#definemaxleaf12#definemaxnode23usingnamespacestd;intn=0;intv=0;strings;typedefstruct{charch;intnum;}inf;infinfo[12];typedefstruct{intweight;//权值intparent;intlchild;intrchild;}Hnodetype;typedefHnodetypeHufftree[maxnode];//-------------------------------------constintmaxbit=10;typedefstruct{intbit[maxbit];intstart;}Hcodetype;voidfundchar(){intk,m;cout请输入字符串endl;cins;while(s[v]){
本文标题:哈夫曼树实验报告
链接地址:https://www.777doc.com/doc-4211261 .html