哈夫曼树实验报告(付原C语言程序)

需求分析：

哈夫曼树试验报告哈夫曼编码，针对每个字母对其进展译码，翻译为原来的信息。二、概要设计程序分为以下几个模块：1、从终端读入字符集大小，nnhfmTree2hfmTreehfm3ToTranhfmhfmCodefile中去4CodefileTextfileTreeprint抽象的数据定义如下：哈夫曼树构造typedefstruct //定义哈夫曼树的构造{intweight;//权值intparent;//双亲intlchild;//左孩子intrchild;//右孩子}htnode,huffmantree[M+1];建立哈夫曼树voidcrthuffmantree(huffmantreeht,intw[],intn) //初始化哈夫曼树{inti,s1,s2,m;for(i=1;i<=n;i++){ht[i].weight=w[i];ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}m=2*n-1;for(i=n+1;i<=m;i++){ht[i].weight=0;ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}for(i=n+1;i<=m;i++){select(ht,i-1,&s1,&s2);ht[i].weight=ht[s1].weight+ht[s2].weight;ht[s1].parent=i;ht[s2].parent=i;ht[i].lchild=s1;ht[i].rchild=s2;}}typedefchar*huffmancode[N+1]; 建立哈夫曼树编码表voidcrthuffmancode(huffmantreeht,huffmancodehc,intn){char*cd; //建立一个指针intstart,i,c,p;安排求一个字符的哈夫曼编码的空间cd[n-1]=”\0”; //编码完毕符for(i=1;i<=n;i++){start=n-1;c=i;p=ht[i].parent;while(p!=0){--start;if(ht[p].lchild==c)cd[start]=”0”;elsecd[start]=”1”;c=p;p=ht[p].parent;}hc[i]=(char*)malloc((n-start)*sizeof(char));strcpy(hc[i],&cd[start]);}free(cd);}select(huffmantreeht,intpos,int*s1,int*s2) //取最小和次小权值{intj,m1,m2;m1=m2=maxint;for(j=1;j<=pos;j++){if(ht[j].weight<m1&&ht[j].parent==0) 定义为双亲为零时才开头求，这样就做到了防止筛选过的重参加比较列表里{m2=m1;*s2=*s1;*s1=j;m1=ht[j].weight;}elseif(ht[j].weight<m2&&ht[j].parent==0){m2=ht[j].weight;*s2=j;}}}主程序模块intmain{初始化参数printf(I;E;D;P;印哈弗曼树T\n“);Q\n“);while(1){ scanf(“%c“,&q);if(q==”Q”){break;}if(q==”I”){fpw=fopen(“hfmtree.txt“,“w“);ftest=fopen(“date.txt“,“r“);编码字母和权值。\n“);scanf(“%d“,&n); //字符集大小输入getchar; //吃空格用的for(i=1;i<=n;i++) 就写文件里，可以自己改回来{fscanf(ftest,“%c“,&a);if(a!=”\n”){str[i]=a;fscanf(ftest,“%d“,&weight[i]);}elsei--; 状况下需要隔行输入的设定}for(i=n+1;i<=2*n-1;i++) //补全剩余的{str[i]=”0”;}crthuffmantree(ht1,weight,n); //建立哈夫曼树crthuffmancode(ht1,hc1,n); 建立哈夫曼编码表for(i=1;i<=2*n-1;i++) //打印到文件中去{fprintf(fpw,“%c%d%d%d%d\n“,str[i],ht1[i].weight,ht1[i].parent,ht1[i].lchild,ht1[i].rchild);}fclose(ftest); //关闭文件，这点很重要，否则文件不会写入fclose(fpw);}if(q==”E”){j=1;i=1;fpr=fopen(“tobetran.txt“,“r“);fpr2=fopen(“hfmtree.txt“,“r“);fpw2=fopen(“codefile.txt“,“w“);while(fscanf(fpr2,“%c%d%d%d%d\n“,&str[j],&ht1[j].weight,&ht1[j].parent,&ht1[j].lchild,&ht1[j].rchild)!=EOF){值大小

j++; //}while(fscanf(fpr,“%c“,&dst[i])!=EOF){符大小

i++; //所输入文件字}count=j; //count是哈夫曼树大小，count1代表输入文件大小count1=i;crthuffmancode(ht1,hc1,count-1); 重从文件里建立哈夫曼编码表for(i=1;i<=count1-1;i++){

for(j=1;j<=count/2;j++) //count/2就是{if(dst[i]==str[j]) //比较{fprintf(fpw2,“%s“,hc1[j]); 找到后写入对codefile}}}fclose(fpr);fclose(fpr2);fclose(fpw2);}if(q==”D”){j=1;i=1;z=1;fpr2=fopen(“hfmtree.txt“,“r“);fpr3=fopen(“codefile.txt“,“r“);fpw3=fopen(“textfile.txt“,“w“);while(fscanf(fpr3,“%c“,&dst[i])!=EOF){i++;}count3=i;while(fscanf(fpr2,“%c%d%d%d%d\n“,&str[j],&ht1[j].weight,&ht1[j].parent,&ht1[j].lchild,&ht1[j].rchild)!=EOF){j++;}count2=j; //count2是哈夫曼树大小计数，count3是读入的哈夫曼编码计数crthuffmancode(ht1,hc1,count2-1); 重建立哈夫曼编码表for(i=1;i<count3;i++){for(j=1;j<=count2/2;j++){len=strlen(hc1[j]); //对每个字符哈夫曼编码长度统计for(t=0;t<len;t++){

if(hc1[j][t]==dst[t+i]) //这里就{flag=1;}if(hc1[j][t]!=dst[t+i]){flag=0;break;}}if(flag==1&&t==len) //推断{win[z]=str[j]; //写入字符z++;i=i+len-1;break;}}}count4=z;for(z=1;z<count4;z++) //写入文件中{fprintf(fpw3,“%c“,win[z]);}fclose(fpr2);fclose(fpr3);fclose(fpw3);}if(q==”P”) //打印codefile{j=1;fpr2=fopen(“codefile.txt“,“r“);fpw3=fopen(“codeprin.txt“,“w“);while(fscanf(fpr2,“%c“,&dst[j])!=EOF){j++;}count=j;j=0;for(i=1;i<count;i++){j++;if(j==50){printf(“\n“);j=0;}printf(“%c“,dst[i]);fprintf(fpw3,“%c“,dst[i]);}fclose(fpr2);fclose(fpw3);}if(q==”T”) //构不好打印，这里就是通过本身构造大致打印出来{fpw=fopen(“treeprin.txt“,“w“);fpr=fopen(“hfmtree.txt“,“r“);i=1;m=0;while(fscanf(fpr,“%c %d %d %d i].lchild,&ht1[i].rchild)!=EOF){m++;i++;}n=(m+1)/2; //字符集大小maxlen=0; //最大字符编码长度crthuffmancode(ht1,hc1,n); 重建立哈夫曼编码表for(i=1;i<=n;i++){len=strlen(hc1[i]);if(maxlen<len)maxlen=len;}count=maxlen; for(i=1;i<=m;i++){t=0;if(ht1[i].parent==0) //先查找根节点，打印出来{for(c=0;c<2*count;c++) //打印空格{printf(““);fprintf(fpw,““);}printf(“%d\n“,ht1[i].weight);fprintf(fpw,“%d\n“,ht1[i].weight);count=count-1; 跳入下一行j=ht1[i].lchild;low[t]=j; t++;k=ht1[i].rchild; 记录根节点左子树low[t]=k;t++;for(c=0;c<2*count;c++) //打空格{printf(““);fprintf(fpw,““);}printf(“%d “,ht1[j].weight);//打印根节点的右子树和左子树fprintf(fpw,“%d printf(““);fprintf(fpw,““);printf(“%d\n“,ht1[k].weight);fprintf(fpw,“%d\n“,ht1[k].weight);count=count-1;}}p=0;while(p<maxlen-2) //p{for(j=0;j<2*count;j++){printf(““);fprintf(fpw,““);}y=t; //yt=0;for(i=0;i<y;i++) //下面就是一个循环过程{if(ht1[low[i]].lchild!=0){printf(“%d “,ht1[ht1[low[i]].lchild].weight);fprintf(fpw,“%d “,ht1[ht1[low[i]].lchild].weight);}else{printf(“0“);fprintf(fpw,“ “);}if(ht1[low[i]].rchild!=0){printf(“%d “,ht1[ht1[low[i]].rchild].weight);fprintf(fpw,“%d “,ht1[ht1[low[i]].rchild].weight);}else{printf(“0“);fprintf(fpw,“ “);}if(ht1[low[i]].lchild!=0) //d[]{d[t]=ht1[low[i]].lchild;t++;}if(ht1[low[i]].rchild!=0){d[t]=ht1[low[i]].rchild;t++;}}for(i=0;i<t;i++) //转移{low[i]=d[i];}printf(“\n“);p++;count=count-1;}fclose(fpw); 记住关文件fclose(fpr);}}return0;}函数的调用关系MianCrthuffmancode crthuffmantreeselect设计和调试分析1、打印树原来是考虑用严格格式输出，但是需要空间太大，就用类似树的形式输出2、文件操作最终必需要关闭文件，否则会始终在缓冲区中用户手册用户界面如下用户需要预先预备好totran文件，然后依据提示输入字符集大小和每个字母和对应的权值，然后按测试结果测试数据为字符ABCDEFGHIJKLMNO权值64132232103211547571532205763字符PQRSTUVWXYZ权值151485180238181161测试语句为：THISPROGRAMEISMYFAVORITEhfmcode1101000101100011111100010001010011000010010101011001001011101100011111110010100011111110011101011000001001001001101101010111打印哈夫曼树814347 467156 191 217 25076 80 92 99 103 114 122 12835 41 45 47 48 51 57 57 59 63 64 6417 18 20 21 22 23 28 31 32 328 9 13 15 15 164 52 2附录程序源文件(#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#defineN100#defineM2*N+1#definemaxint32767typedefstruct //定义哈夫曼树的构造{intweight;intparent;intlchild;intrchild;}htnode,huffmantree[M+1];select(huffmantreeht,intpos,int*s1,int*s2) //取最小和次小权值{intj,m1,m2;m1=m2=maxint;for(j=1;j<=pos;j++){if(ht[j].weight<m1&&ht[j].parent==0) 定义为双亲为零时才开头求，这样就做到了防止筛选过的重参加比较列表里{m2=m1;*s2=*s1;*s1=j;m1=ht[j].weight;}elseif(ht[j].weight<m2&&ht[j].parent==0){m2=ht[j].weight;*s2=j;}}}voidcrthuffmantree(huffmantreeht,intw[],intn) //初始化哈夫曼树{inti,s1,s2,m;for(i=1;i<=n;i++) //对字母建立哈夫曼树的构造{ht[i].weight=w[i];ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}m=2*n-1; //剩下的构造初始化for(i=n+1;i<=m;i++){ht[i].weight=0;ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}for(i=n+1;i<=m;i++) //开头通过子树并入方式刷哈夫曼树{select(ht,i-1,&s1,&s2);ht[i].weight=ht[s1].weight+ht[s2].weight;ht[s1].parent=i;ht[s2].parent=i;ht[i].lchild=s1;ht[i].rchild=s2;}}typedefchar*huffmancode[N+1]; //建立哈夫曼树编码表，这里承受的是指针的形式voidcrthuffmancode(huffmantreeht,huffmancodehc,intn){ 1，类似短除法求二进制转换//cpchar*cd; //建立一个指针intstart,i,c,p;cd=(char*)malloc(n*sizeof(char)); 安排求一个字符的哈夫曼编码的空间cd[n-1]=”\0”; //编码完毕符for(i=1;i<=n;i++){start=n-1;c=i;p=ht[i].parent;while(p!=0) 逆向遍历到根{--start;if(ht[p].lchild==c) 假设双亲的左孩子等于该值在则该值0，1cd[start]=”0”;elsecd[start]=”1”;c=p; //向上走p=ht[p].parent;}hc[i]=(char*)malloc((n-start)*sizeof(char)); 数组指针strcpy(hc[i],&cd[start]); //字符串复制}free(cd);}intmain{FILE*fpw,*fpr,*fpw2,*fpr2,*fpr3,*fpw3,*ftest;intn=0,d[1000],m,low[1000],weight[10000]={0},i,j=0,count=0,count1=0,count3=0,z=1,count4=0,count2=0,len,t,flag=0,c,maxlen,k,p,y;charstr[10000]={0},q,dst[10000]={0},com[10000]={0},win[10000]={0},a;huffmantreeht1;huffmancodehc1;printf(I;E;D;P;印哈弗曼树T\n“);Q\n“);while(1){ scanf(“%c“,&q);if(q==”Q”){break;}if(q==”I”){fpw=fopen(“hfmtree.txt“,“w“);ftest=fopen(“date.txt“,“r“);编码字母和权值。\n“);scanf(“%d“,&n); //字符集大小输入getchar; //吃空格用的for(i=1;i<=n;i++) 就写文件里，可以自己改回来{fscanf(ftest,“%c“,&a);if(a!=”\n”){str[i]=a;fscanf(ftest,“%d“,&weight[i]);}elsei--; 状况下需要隔行输入的设定}for(i=n+1;i<=2*n-1;i++) //补全剩余的{str[i]=”0”;}crthuffmantree(ht1,weight,n); //建立哈夫曼树crthuffmancode(ht1,hc1,n); 建立哈夫曼编码表for(i=1;i<=2*n-1;i++) //打印到文件中去{fprintf(fpw,“%c%d%d%d%d\n“,str[i],ht1[i].weight,ht1[i].parent,ht1[i].lchild,ht1[i].rchild);}fclose(ftest); 关闭文件，这点很重要，否则文件不会写入fclose(fpw);}if(q==”E”){j=1;i=1;fpr=fopen(“tobetran.txt“,“r“);fpr2=fopen(“hfmtree.txt“,“r“);fpw2=fopen(“codefile.txt“,“w“);while(fscanf(fpr2,“%c%d%d%d%d\n“,&str[j],&ht1[j].weight,&ht1[j].parent,&ht1[j].lchild,&ht1[j].rchild)!=EOF)值大小

{j++; //}while(fscanf(fpr,“%c“,&dst[i])!=EOF){符大小

i++; //所输入文件字}count=j; //count是哈夫曼树大小，count1代表输入文件大小count1=i;crthuffmancode(ht1,hc1,count-1); 重从文件里建立哈夫曼编码表for(i=1;i<=count1-1;i++){

for(j=1;j<=count/2;j++) //count/2就是{if(dst[i]==str[j]) //比较{fprintf(fpw2,“%s“,hc1[j]); 找到后写入对codefile}}}fclose(fpr);fclose(fpr2);fclose(fpw2);}if(q==”D”){j=1;i=1;z=1;fpr2=fopen(“hfmtree.txt“,“r“);fpr3=fopen(“codefile.txt“,“r“);fpw3=fopen(“textfile.txt“,“w“);while(fscanf(fpr3,“%c“,&dst[i])!=EOF){i++;}count3=i;while(fscanf(fpr2,“%c%d%d%d%d\n“,&str[j],&ht1[j].weight,&ht1[j].parent,&ht1[j].lchild,&ht1[j].rchild)!=EOF){j++;}count2=j; //count2是哈夫曼树大小计数，count3是读入的哈夫曼编码计数crthuffmancode(ht1,hc1,count2-1); 重建立哈夫曼编码表for(i=1;i<count3;i++){for(j=1;j<=count2/2;j++){len=strlen(hc1[j]); //对每个字符哈夫曼编码长度统计for(t=0;t<len;t++){

if(hc1[j][t]==dst[t+i]) //这里就{flag=1;}if(hc1[j][t]!=dst[t+i]){flag=0;break;}}if(flag==1&&t==len) //推断{win[z]=str[j]; //写入字符z++;i=i+len-1;break;}}}count4=z;for(z=1;z<count4;z++) //写入文件中{fprintf(fpw3,“%c“,win[z]);}fclose(fpr2);fclose(fpr3);fclose(fpw3);}if(q==”P”) //打印codefile{j=1;fpr2=fopen(“codefile.txt“,“r“);fpw3=fopen(“codeprin.txt“,“w“);while(fscanf(fpr2,“%c“,&dst[j])!=EOF){j++;}count=j;j=0;for(i=1;i<count;i++){j++;if(j==50){printf(“\n“);j=0;}printf(“%c“,dst[i]);fprintf(fpw3,“%c“,dst[i]);}fclose(fpr2);fclose(fpw3);}if(q==”T”) //构不好打印，这里就是通过本身构造大致打印出来{fpw=fopen(“treeprin.txt“,“w“);fpr=fopen(“hfmtree.txt“,“r“);i=1;m=0;while(fscanf(fpr,“%c %d %d %d i].lchild,&ht1[i].rchild)!=EOF){m++;i++;}n=(m+1)/2; //字符集大小maxlen=0; //最大子符编码长度crthuffmancode(ht1,hc1,n); 重建立哈夫曼编码表for(i=1;i<=n;i++){len=strlen(hc1[i]);if(maxlen<len)maxlen=len;}count=maxlen; 来掌握行数的for(i=1;i<=m;i++){t=0;if(ht1[i].parent==0) //先查找根节点，打印出来{for(c=0;c<2*count;c++) //打印空格{printf(““);fprintf(fpw,““);}low[]

printf(“%d\n“,ht1[i].weight);fprintf(fpw,“%d\n“,ht1[i].weight);count=count-1; //跳入下一行j=ht1[i].lchild;low[t]=j; //记录根节点右子树，用数组t++;k=ht1[i].rchi