数据结构课程设计-哈夫曼树(共14页)

1、精选优质文档-倾情为你奉上成绩评定教师签名嘉应学院 计算机学院实验报告课程名称：数据结构课程设计开课学期：2017-2018学年第2学期班 级：指导老师：实验题目：哈夫曼树学 号：姓 名：上机时间：一、实验目的本实验的目的是通过对简单的哈夫曼编/译码系统的设计与实现来熟练掌握树形结构在实际问题中的应用。二、实验问题描述利用哈夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此试验即设计这样的一个简单的编/译码系统。系统应该具备如下的几个功能。1、求出各个叶子节点的权重值输入一个字符串，统

2、计其中各个字母的个数和总的字母个数。2、构造哈夫曼树统计出的字母种类为叶子结点个数，每个字母个数为相应的权值，建立哈夫曼树。3、打印哈弗曼树的功能模块 按照一定形式打印出哈夫曼树。4、编码利用已经建立好的哈夫曼树进行编码。5、译码根据编码规则对输入的代码进行翻译并将译码。三、实验步骤1、实验问题分析（1） 设计一个结构体数组保存字母的类型和个数。typedef structchar ch; /字母的种类int num; /字母的个数inf;（2） 在构造哈夫曼树时，设计一个结构体数组Hufftree保存哈夫曼树中各结 点的信息，根据二叉树的性质可知，具有n个结点的哈夫曼树共有2n-1个结 点，

3、所以数组大小设置为2n-1,描述结点的数据类型为：typedef structint weight;/权值int parent; /双亲int lchild; /左孩子int rchild; /右孩子Hnodetype;typedef Hnodetype Hufftreemaxnode;/定义此类型的数组（3） 求哈夫曼编码，实质上是在已经建立的哈夫曼树中，从叶子结点开始， 沿着结点的双亲链表域退回到根节点，每退回一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼值，由于一个字符的哈夫曼编码是从根结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支

4、代码为所求编码的高位码，所以设计如下的数据类型：const int maxbit=10;typedef struct int bitmaxbit; /每个结点的哈夫曼编码 int start; /开始位置Hcodetype;（4） 设置全局变量。string s; /s为输入的字符串int n=0; /记录输入的字符串中字母的种类，即叶子结点个数int v=0; /记录字符串中字母的总个数inf infomaxleaf;/叶子结点类型2、 功能（函数）设计（1） 统计字母种类和个数模块此模块的功能为从键盘接受一个字符串，统计字符串中字母种类即结点个数，每种字母出现次数即各叶子结点的权值。全局变

5、量s保存输入的字符串，将种类和个数保存到infomaxleaf中。函数原型：void fundchar（）如输入的字符串是“sddfffgggg”则显示如下。（2） 哈夫曼树的建立模块此模块的功能为从（1）中计算出的结点个数和各个叶子结点的权值构造一棵哈弗曼树。函数原型：Hnodetype* huffmantree()/函数返回结点类型的数组（3） 打印哈弗曼树的功能模块此模块的功能是将由(2)建立的哈弗曼树按照一定规则<weight,lchild,rchild,parent>打印在屏幕上。函数原型：void print(Hnodetype *hufftree) 如输入的字符串是”

6、sddfffgggg”，则构造的哈夫曼树为（4） 建立哈夫曼编码的功能模块此模块功能为将（2）中建立的哈夫曼树进行哈弗曼编码，然后将字符与对应的0、1代码串打印到屏幕上。函数原型：void huffmancode(Hnodetype *hufftree)如输入的字符串是“sddfffgggg”，则每个字母的代码和输入的字符串的哈夫曼编码是（5） 译码的功能模块此模块的功能为接收需要译码的0和1代码串，按照（4）中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，并将翻译的结果在屏幕上打印出来。函数原型：void translation(Hnodetype *hufftree)如输入的代码

7、串是“”，则对应的字符串是“sdfg”四、实验结果（程序）及分析1、实验主要模块代码(一) 函数功能：统计字母种类和个数模块void fundchar()int k,m; cout<<"请输入字符串"<<endl;cin>>s; /s为输入的字符串while(sv)v+;cout<<"共有字符"<<v<<"个"<<endl; / v是全局变量 info0.ch=s0;info0.num=1; for(k=1;k<=v;k+) /统计s中字母种类和

8、个数for(m=0;m<=n;m+)if(infom.ch=sk)+infom.num;break;if(m>n)info+n.ch=sk;infon.num=1; for(m=0;m<n;m+) /输出种类和个数cout<<"字符"<<infom.ch<<"有"<<infom.num<<"个"<<endl;(二) 函数功能:哈弗曼树的建立模块Hnodetype* huffmantree() Hnodetype *hufftree=new Huf

9、ftree; int i,j,m1,m2,x1,x2;/m1记录最小的重权值，m2为次小 for(i=0;i<2*n-1;i+) /结点初始化 hufftreei.parent=-1; hufftreei.weight=0; hufftreei.lchild=-1; hufftreei.rchild=-1; for(i=0;i<n;i+) /将每个字母的个数当做叶子结点的权值 hufftreei.weight=infoi.num; for(i=0;i<n-1;i+) m1=m2=maxvalue; x1=x2=0; for(j=0;j<n+i;j+) if(hufftr

10、eej.parent=-1 && hufftreej.weight<m1) m2=m1; x2=x1; m1=hufftreej.weight; x1=j;/x1记录最小重权值在数组中的下标 else if(hufftreej.parent=-1 && hufftreej.weight<m2) m2=hufftreej.weight; x2=j;/x2记录次小重权值在数组中的下标 hufftreex1.parent=n+i; hufftreex2.parent=n+i; hufftreen+i.weight=m1+m2; hufftreen+i.lc

11、hild=x1; hufftreen+i.rchild=x2; return hufftree;/返回数组首地址(三) 函数功能：打印哈弗曼树的功能模块void print(Hnodetype *hufftree) cout<<endl<<endl<<endl; /界面优化 cout<<"哈弗曼树-"<<endl; cout<<" "<<"weight"<<" "<<"lchild"<

12、;<" "<<"rchild"<<" "<<"parent"<<endl;/界面优化 for(int i=0;i<2*n-1;i+)cout<<" "<<hufftreei.weight<<" "<<hufftreei.lchild<<" "<<hufftreei.rchild<<" "<

13、<hufftreei.parent<<endl;(四) 函数功能：建立哈弗曼编码的功能模块void huffmancode(Hnodetype *hufftree) Hcodetype huffcodemaxleaf,cd; int i,j,c,p; for(i=0;i<n;i+)/求每个结点的哈弗曼编码 cd.start=n-1; c=i; p=hufftreec.parent; while(p!=-1)/由叶子结点向上直到树根 if(hufftreep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.sta

14、rt-; c=p; p=hufftreec.parent; for(j=cd.start+1;j<n;j+) /将结果保存 huffcodei.bitj=cd.bitj;/保存每位号码 huffcodei.start=cd.start; /保存开始位置 cout<<endl<<endl<<endl; cout<<"哈弗曼编码"<<endl; for(i=0;i<n;i+) /打印各个字母对应的编码 cout<<"-"<<endl; cout<<in

15、foi.ch<<"的代码是" for(j=huffcodei.start+1;j<n;j+) cout<<huffcodei.bitj; cout<<endl; cout<<"-"<<endl; cout<<endl<<"输入的字符串的哈夫曼编码为："<<endl; for(i=0;i<v;i+)/打印输入的字符串的编码结果 for(int y=0;y<=n;y+) if(si=infoy.ch) for(j= huffc

16、odey.start+1;j<n;j+) cout<<huffcodey.bitj; cout<<endl;(五) 函数功能：译码的功能模块void translation(Hnodetype *hufftree) string code; /code记录输入的0，1代码 int t; cout<<endl<<endl<<endl; cout<<"请输入代码串:" cin>>code; int num=0; while(codenum) num+; /确定0，1代码长度 Hnodety

17、pe *p=&hufftree2*n-2; cout<<endl<<endl<<endl; cout<<"译码结果-"<<endl; for(int i=0;i<num;i+)if(codei='0') /从根向下 p=&hufftreep->lchild; else p=&hufftreep->rchild; if(p->lchild=-1 && p->rchild=-1) /如果到达叶子结点 t=p->weight; /

18、保存叶子结点的权值 for(int j=0;j<n;j+)if(hufftreej.weight=t) cout<<infoj.ch; /输出权值的对应的字母 break; p=&hufftree2*n-2; /重新从根节点开始 cout<<endl;2、测试数据 sfddaaassss实验结果截图3、 调试过程中出现的问题以及解决策略译码模块中，如果输入的代码串无对应的字母，则会出错。解决办法：提示用户输入时注意附最终代码：#include<iostream>#include<string>#define maxvalue 12#

19、define maxleaf 12#define maxnode 23using namespace std;int n=0;int v=0;string s;typedef structchar ch;int num;inf;inf info12;typedef struct int weight;/权值 int parent; int lchild; int rchild;Hnodetype;typedef Hnodetype Hufftreemaxnode;/-const int maxbit=10;typedef struct int bitmaxbit; int start;Hcod

20、etype;void fundchar()int k,m; cout<<"请输入字符串"<<endl;cin>>s;while(sv)v+;cout<<"共有字符"<<v<<"个"<<endl; info0.ch=s0;info0.num=1; for(k=1;k<=v;k+)for(m=0;m<=n;m+)if(infom.ch=sk)+infom.num;break;if(m>n)info+n.ch=sk;infon.num=1;

21、 for(m=0;m<n;m+)cout<<"字符"<<infom.ch<<"有"<<infom.num<<"个"<<endl;Hnodetype* huffmantree() Hnodetype *hufftree=new Hufftree; int i,j,m1,m2,x1,x2;/m1记录最小的重权值，m2为次小 for(i=0;i<2*n-1;i+) /结点初始化 hufftreei.parent=-1; hufftreei.weight=0;

22、 hufftreei.lchild=-1; hufftreei.rchild=-1; for(i=0;i<n;i+) /将每个字母的个数当做叶子结点的权值 hufftreei.weight=infoi.num; for(i=0;i<n-1;i+) m1=m2=maxvalue; x1=x2=0; for(j=0;j<n+i;j+) if(hufftreej.parent=-1 && hufftreej.weight<m1) m2=m1; x2=x1; m1=hufftreej.weight; x1=j;/x1记录最小重权值在数组中的下标 else if(

23、hufftreej.parent=-1 && hufftreej.weight<m2) m2=hufftreej.weight; x2=j;/x2记录次小重权值在数组中的下标 hufftreex1.parent=n+i; hufftreex2.parent=n+i; hufftreen+i.weight=m1+m2; hufftreen+i.lchild=x1; hufftreen+i.rchild=x2; return hufftree;/返回数组首地址void huffmancode(Hnodetype *hufftree) Hcodetype huffcodemax

24、leaf,cd; int i,j,c,p; for(i=0;i<n;i+)/求每个结点的哈弗曼编码 cd.start=n-1; c=i; p=hufftreec.parent; while(p!=-1)/由叶子结点向上直到树根 if(hufftreep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=hufftreec.parent; for(j=cd.start+1;j<n;j+) /将结果保存 huffcodei.bitj=cd.bitj;/保存每位号码 huffcodei.start=c

25、d.start; /保存开始位置 cout<<endl<<endl<<endl; cout<<"哈弗曼编码"<<endl; for(i=0;i<n;i+) /打印各个字母对应的编码 cout<<"-"<<endl; cout<<infoi.ch<<"的代码是" for(j=huffcodei.start+1;j<n;j+) cout<<huffcodei.bitj; cout<<endl; c

26、out<<"-"<<endl; cout<<endl<<"输入的字符串的哈夫曼编码为："<<endl; for(i=0;i<v;i+)/打印输入的字符串的编码结果 for(int y=0;y<=n;y+) if(si=infoy.ch) for(j= huffcodey.start+1;j<n;j+) cout<<huffcodey.bitj; cout<<endl;void print(Hnodetype *hufftree) cout<<

27、endl<<endl<<endl; cout<<"哈弗曼树-"<<endl; cout<<" "<<"weight"<<" "<<"lchild"<<" "<<"rchild"<<" "<<"parent"<<endl;/界面优化 for(int i=0;i<2*n-1;i+)cout<<" "<<hufftreei.weight<<" "<<huff