数据结构实验四 -哈夫曼数与哈弗曼编码

第2页共7页实验四哈夫曼树及其的应用一、实验目的1、在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。2、掌握构造哈夫曼树以及哈夫曼编码的方法。3、熟练掌握哈夫曼树特征及其应用二、实验内容题目哈夫曼树和哈夫曼编码：从终端输入若干个字符，统计（或指定）字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。三、实验步骤（一）、数据结构与核心算法的设计描述本实验在二叉树基本操作的基础上着重对其应用，哈弗曼树及哈弗曼编码均采用动态数组存储，关键在于哈弗曼树的构造和哈弗曼编码，此外对终端字符的统计也比较重要。以下是头文件中数据结构的设计和相关函数的声明：#defineDataTypechar#include<iostream.h>#include<malloc.h>#include<string.h>#include<iomanip.h>typedefstruct{DataTypech;intweight;//权值及频率intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;int*TongjiChar(int*text);/*统计字符出现的频率*/voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn);//该函数包含哈弗曼数的构造及哈弗曼编码voidSelect(HuffmanTreeHT,inti,int&s1,int&s2);voidTranslate(HuffmanTree&HT,HuffmanCode&HC,int&n);（二）、函数调用及主函数设计externintn;//n为节点的个数voidmain(){ HuffmanTreeHT; HuffmanCodeHC;int*text,*count;count=TongjiChar(text);HuffmanCoding(HT,HC,count,n); Translate(HT,HC,n);}（三）、程序运行结果分析：（四）、实验总结由于有二叉树的基本操作的经验，在本实验中哈弗曼树的构造及哈弗曼编码相对就较容易实现，但是本实验的关键仍在于哈弗曼树的构造和哈弗曼编码，本实验的一个特点是在实验基本要求的基础上增加了翻译功能。尽管实验过程中不同模块遇到了不同程度的困难，但是经过详细的设计和反复的测试、调试，实验最终结果达到了实验的预期结果。四、主要算法流程图及程序清单1、主要算法流程图：终端输入字符终端输入字符统计字符的频率构造哈弗曼和哈弗曼编码翻译结束2、程序清单统计字符的频率模块：intn=0;int*TongjiChar(int*text){ charch; inti; charstr[100]; intcount[100]; for(i=0;i<100;i++) count[i]=1; inttotal=0; intlength=0; cout<<"请输入一串字符(以#结尾)："; do {loop:cin>>ch;length++; total++; if(ch!='#') { str[length-1]=ch; for(i=0;i<length;i++) { if(length!=1) { for(intj=0;j<length-1;j++) { if(str[j]==ch) {count[j]++;length--; gotoloop; } } } } } }while(ch!='#'); length--;//去掉最后一个#号 total--; cout<<"所有字符的个数为(不含#):"<<total<<endl; cout<<"不同字符的个数为:"<<length<<endl; text=count;for(i=0;i<length;i++) cout<<str[i]<<""<<"频率："<<count[i]<<""<<endl;n=length; returntext;}构造哈弗曼数和哈弗曼编码模块：voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,i,s1,s2,start,c,f;intdata[30];charstr;HuffmanTreep;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));cout<<"请依次输入各个结点的数值(可以是字符)：\例如：afhkr8680ds\n"; for(i=1;i<=n;i++){cin>>str; data[i]=str; } data[i+1]='\0';for(p=HT+1,i=1;i<=n;++i) { p->weight=*w; str=data[i]; p->ch=str; cout<<"第"<<i<<"个接点的数值为："<<p->ch<<'\n'; p->parent=0; p->lchild=0; p->rchild=0; p++; w++;}for(;i<=m;++i,++p) { p->weight=0;p->parent=0; p->lchild=0; p->rchild=0;}cout<<endl<<"建立哈夫曼树:";for(i=n+1;i<=m;++i){ Select(HT,i-1,s1,s2); //选择各元素中权值最小的两个HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;cout<<endl<<setw(6)<<"HT["<<s1<<"]和HT["<<s2<<"]"<<setw(5)<<"生成";cout<<setw(5)<<"HT["<<i<<"],且权值="<<HT[i].weight<<"的接点。";}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//哈夫曼编码char*cd;cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';cout<<endl<<"哈夫曼编码如下:"<<endl;for(i=1;i<=n;++i){ start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0';//--后的值作为表达式的值。如果是左支,记为0;右支,记为1; else cd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]); cout<<"HT["<<i<<"]"<<"的哈夫曼编码为："<<HC[i]<<endl;}free(cd);}//HuffmanCoding()end选泽模块：voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){ intj,k=1;//j为循环变量while(HT[k].parent!=0)k++;s1=k;for(j=1;j<=i;j++)if(HT[j].parent==0&&HT[j].weight<HT[s1].weight) s1=j;//s1为权值最小的元素k=1;while((HT[k].parent!=0||k==s1))k++;s2=k;for(j=1;j<=i;++j)if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1) s2=j;}//Select()end翻译模块：voidTranslate(HuffmanTree&HT,HuffmanCode&HC,int&n){inti,k,j=0;HuffmanTreep;char*data;data=newchar[n+1];for(p=HT+1,i=1;i<=n;i++,p++)data[i]=p->ch;cout<<"各结点数值依次是：";for(i=1;i<=n;i++) cout<<data[i]<<"";cout<<endl;char*str;str=newchar[n];cout<<"(提示：请您输入需要译码的0和1的个数以及序列!例如：6010111)"<<endl;cin>>k;char*ch;ch=newchar[k+1];for(intm=0;m<k;m++) cin>>ch[m];ch[k]='\0';cout<<"翻译后的字符序列是"; while(ch[j]!='\0') { for(i=1;i<=n;i++) { str[i-1]=ch[j];