用赫夫曼树进行字符串的编码

第1页共7页数据结构实验报告实验三树的应用一、实验题目：树的应用——哈夫曼编码二、实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：1．输出存放哈夫曼树的数组HT的初态和终态；2．输出每个字符的哈夫曼编码；3．输入由上述若干字符组成的字符串，对电文进行编码并输出；三、程序源代码：#includestdio.h#includestring.h#includestdlib.h#defineN8#defineM4typedefstruct{chardata;char*code;unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,char*data,int*w,intn,char*str){//存放n个字符的权值(均0)，构造赫夫曼树HT，并求出n各字符的赫夫曼编码HCif(n=1)return;intm=2*n-1;//总节点数HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用HuffmanTreep;第2页共7页inti,j;printf(\n);printf(------------------------------\n);printf(存放哈夫曼树的数组HT的初态:\n);printf(叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:\n);for(p=HT+1,i=1;i=n;++i,++p,++data,++w){p-data=*data;p-parent=p-lchild=p-rchild=0;p-weight=*w;p-code=(char*)malloc(n*sizeof(char));printf(%c%2d%2d%2d%2d\n,p-data,p-parent,p-weight,p-lchild,p-rchild);}for(;i=m;++p,++i){p-parent=p-lchild=p-rchild=p-weight=0;p-data=NULL;p-code=(char*)malloc(n*sizeof(char));printf(%2d%2d%2d%2d\n,p-parent,p-weight,p-lchild,p-rchild);}for(i=n+1;i=m;++i){//建赫夫曼树//在HT[1--i-1]选择parent为0且weight最小的两个节点，其序号分别为s1和s2unsignedintm1=32767;unsignedintm2=32767;//m1,m2为最小和次小权值ints1=0;ints2=0;//s1,s2为最小和次小节点的序号for(intk=1;k=i-1;k++){if((HT[k].parent==0)&&(HT[k].weightm1))第3页共7页{m2=m1;s2=s1;m1=HT[k].weight;s1=k;}elseif((HT[k].parent==0)&&(HT[k].weightm2)){m2=HT[k].weight;s2=k;}}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;}printf(\n);printf(------------------------------\n);printf(存放哈夫曼树的数组HT的终态:\n);printf(叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:\n);for(p=HT+1,i=1;i=n;++p,++i)printf(%c%2d%2d%2d%2d\n,p-data,p-parent,p-weight,p-lchild,p-rchild);for(;i=m;++p,++i)printf(%2d%2d%2d%2d\n,p-parent,p-weight,p-lchild,p-rchild);//----从叶子到根逆向求每个字符的赫夫曼编码----HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量char*cd;cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]='\0';//编码结束符intstart;第4页共7页unsignedintf,c;printf(\n);printf(------------------------------\n);printf(每个字符的哈夫曼编码:\n);for(p=HT+1,i=1;i=n;++i,++p)//逐个字符求赫夫曼编码{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';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间char*R=&cd[start];strcpy(HC[i],&cd[start]);strcpy(p-code,R);printf(%c,p-data);printf(%s,HC[i]);printf(\n);}printf(输出字符串的赫夫曼编码:\n);for(i=0;iM;i++){for(p=HT+1,j=0;jN;++j,++p)if(str[i]==p-data)printf(%s,p-code);}free(cd);//释放工作空间}intmain(){第5页共7页chardata[N],str[M];intp[N],i;for(i=0;iN;i++){printf(输入第%d个字符及频率：\n,i+1);scanf(%c,&data[i]);scanf(%d,&p[i]);getchar();}printf(输入字符串：\n);for(i=0;iM;i++)scanf(%c,&str[i]);HuffmanTreeHT;HuffmanCodeHC;HuffmanCoding(HT,HC,data,p,N,str);printf(\n);return0;}四、测试结果：第6页共7页五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距本次实验中第三个问题没做出来，我本来想出了一种方法，但是总是出错，我的方法是在结构体中加一个编码域，在形参中加一个字符指针，它的值由主函数中输入的字符串传递过来的。将得出的编码复制第7页共7页到编码域中，然后一遍一遍的访问HT数组，如果HT数组中data域中的字符与由主函数中传递过来的字符相等的话，输出对应的编码域中的编码，字符串中有几个字符，访问HT数组访问几次。但是总是出错，所以没做。后来通过仔细分析，将错误的地方改了过来，程序正确运行出来了。