树的应用 哈夫曼编编码 和 译码

华%%%%%%%%%%%%%%%%%%学院数据结构实验报告2011～2012学年第二学期2011级计算机专业班级：学号：姓名：实验三树的应用一、实验题目：树的应用——哈夫曼编/译码二、实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。

根据哈夫曼编码的原理，编写一个程序，在用户输入字符及权值的基础上求哈夫曼编码。

要求：（1）从键盘输入字符集（字母a～z，空格）共27个字符，以及出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，并输出数组ht[]的初态和终态。

（2）对各个字符进行哈夫曼编码，打印输出字符及对应的哈夫曼编码。

（3）编码：从键盘输入字符串，利用已建好的哈夫曼编码，实现该字符串的编码。

（4）（选作）译码：从键盘输入二进制串，利用已建好的哈夫曼编码，将二进制串还原为字符串。

三、程序源代码：typedef struct{char data;int weight;int parent;int lchild;int rchild;}HTNode;typedef struct{char cd[100];int start;}HCode;//这里保存字母对应的编码，我本来想用指向字符数组的指针数组，可是后来想到利用结构体更简单。

struct Codes{char ch;char codes[27];};#include<iostream.h>#include<stdio.h>#include<string.h>const int maxsize=100;//特色，动态编码void tongji(char str[],int *pinlv);void createHT(HTNode *ht,int n,int pinlv[]);void showHT(HTNode ht[],int n);void createHcode(HTNode ht[],HCode* hcd,int n);void showHCode(HCode hcd[],int n,int pinlv[]);//使字符与编码对应void matchcodes(HCode hcd[],int pinlv[],int n,Codes* code);void charToCode(Codes codes[],char *str);void codeToChar(Codes codes[]);void main(){cout<<"本例实现动态编码：根据输入的字符串建立编码规则，然后按此规则对输入的字符串进行编码，对输入的编码进行译码操作"<<endl;//输入cout<<"input a string"<<endl;char str[maxsize];gets(str);//统计int pinlv[27];int len=0;for(int i=0;i<27;i++)pinlv[i]=0;tongji(str,pinlv);for(int k=0;k<27;k++)if(pinlv[k]!=0)len++;cout<<len<<endl;// cout<<pinlv[26]<<endl;//构造哈夫曼树HTNode ht[199];createHT(ht,len,pinlv);//哈夫曼编码HCode hcd[27];createHcode(ht,hcd,len);showHCode(hcd,len,pinlv);//字符与编码对应匹配Codes codes[27];matchcodes(hcd,pinlv,len,codes);//char to codecharToCode(codes,str);// code to charcodeToChar(codes);}//这个函数有错误，已经改正void codeToChar(Codes codes[]){cout<<"根据上面输出的编码规则，请输入要译码的01编码（相邻编码要以逗号分割，以“#”结束）"<<endl;char str[100];gets(str);cout<<str<<"的译码为："<<endl;char temp[27]; //保存每个字符的编码，每次要赋 0 啊int i,j;for(i=0,j=0;i<100;i++){if(str[i]!=','){temp[j]=str[i];j++;}else{temp[j]='\0';for(int k=0;k<27;k++){if(strcmp(codes[k].codes ,temp)==0){cout<<codes[k].ch <<" ";//cout.flush();break;}}j=0; //赋0 操作}if(str[i]=='#'){break;}}cout<<endl;}void charToCode(Codes codes[],char *str){char ch=*str;int k=0;cout<<str<<"的编码为："<<endl;while(ch!='\0'){for(int i=0;i<27;i++){if(codes[i].ch ==ch)cout<<codes[i].codes<<"，";}k++;ch=*(str+k);}cout<<endl;}//已经改进过的地方void matchcodes(HCode hcd[],int pinlv[],int n,Codes* codes) {int i,k,m;char ch='a';int p=0;char temp[27];for(int z=0;z<26;z++){temp[z]=' ';}temp[26]='\0';for(i=0;i<27;i++){if(pinlv[i]!=0){ch='a';ch=char(ch+i);if(ch>='a'&&ch<='z'){codes[p].ch =ch;//测试/* if(codes[p].ch==ch){cout<<"succss"<<endl;}*/}elsecodes[p].ch =' ';m=0;for(k=hcd[p].start;k<=n;k++){temp[m]=hcd[p].cd [k];m++;}//字符串必须给出结束符位置，否则会输出乱码啊temp[m]='\0';//codes[p]=temp;strcpy(codes[p].codes ,temp);// cout<<codes[p].ch;// cout<<codes[p].ch<<"-----"<<codes[p].codes<<endl;p++;}}}void showHCode(HCode hcd[],int n,int pinlv[]){int i,k;char ch='a';int p=0;cout<<"字符"<<" "<<"对应编码"<<endl;for(i=0;i<27;i++){//每次必须从字符'a'开始ch='a';////ch=char(ch+i);if(pinlv[i]!=0){if(ch>='a'&&ch<='z')cout<<ch<<" ";elsecout<<" "<<" ";for(k=hcd[p].start;k<=n;k++)cout<<hcd[p].cd [k];p++;cout<<endl;}}}void createHcode(HTNode ht[],HCode* hcd,int n) {int i,f,c;HCode hc;for(i=0;i<n;i++){//不是书上的hc.start =n;hc.start =n-1;c=i;f=ht[i].parent ;while(f!=-1){if(ht[f].lchild ==c)hc.cd [hc.start --]='0';elsehc.cd [hc.start --]='1';c=f;f=ht[f].parent ;}//最后一位必须赋值为结束符hc.cd[n]='\0';hc.start ++;hcd[i]=hc;}}void createHT(HTNode* ht,int n,int pinlv[]){for(int m=0;m<=2*n-1;m++)//初始化节点的所有与域值ht[m].parent =ht[m].lchild =ht[m].rchild =-1;char ch='a';int p=0;for(int z=0;z<27;z++)//循环27个字母（a-z和''），若频数大于0，就创建节点{if(pinlv[z]!=0){if(ch>='a'&&'z'>=ch){ht[p].data =ch;ht[p].weight =pinlv[ch-97];}else{ht[p].data =' ';ht[p].weight =pinlv[26];}p++;}ch=char (ch+1);}cout<<"ht[]初态输出 ";showHT(ht,n);int i,k,lnode,rnode;int min1,min2;for(i=n;i<2*n-1;i++){min1=min2=32767;lnode=rnode=-1;for(k=0;k<=i-1;k++){if(ht[k].parent ==-1){if(ht[k].weight <min1){min2=min1;rnode=lnode;min1=ht[k].weight ;lnode=k;}else if(ht[k].weight <min2){min2=ht[k].weight ;rnode=k;}}}ht[lnode].parent =i;ht[rnode].parent =i;ht[i].weight =ht[lnode].weight +ht[rnode].weight ;ht[i].lchild =lnode;ht[i].rchild =rnode;ht[i].data ='*';}cout<<"ht[]终态输出 ";showHT(ht,2*n-1);}void tongji(char str[],int *pinlv){char ch=*str;int k=1;while(ch!='\0'){ if(ch>='a'&&'z'>=ch)pinlv[ch-97]+=1;elsepinlv[26]+=1;ch=*(str+k);k++;}}void showHT(HTNode ht[],int n){ cout<<"节点信息如下："<<endl;cout<<"data"<<" "<<"weig"<<" "<<"pare"<<" "<<"lchd"<<" "<<"rchd"<<endl;for(int i=0;i<n;i++){cout<<ht[i].data <<" "<<ht[i].weight <<" "<<ht[i].parent <<" "<<ht[i].lchild <<" "<<ht[i].rchild <<endl;}}四、测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距通过本次实验，我感觉到自己的程序编程细节问题必须注意：如使用gets（）函数可接收带有空格的输入字符串；在进行编码译码时，必须注意，数组的上下界问题。