搜索
哈夫曼树实验报告需求分析：从终端读入一串字符，利用建立好的哈夫曼树对其进行编码，储存到文件当中去，然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。二、概要设计程序分为以下几个模块：1、从终端读入字符集大小，n个字符和n个权值，建立哈夫曼树，写入文件hfmTree中去。2、对hfmTree进行编码，建立hfm编码表。3、从文件ToTran读入信息，根据hfm编码表对其进行hfm编码，将编码后的信息写入文件Codefile中去4、对Codefile文件反向译码，结果储存在Textfile中去。5、将建立的hfmTree打印在终端上，并储存于相应的Treeprint文件中去。抽象的数据定义如下：哈夫曼树结构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=(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)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].weightm1&&ht[j].parent==0)//定义为双亲为零时才开始求，这样就做到了防止筛选过的重新加入比较列表里{m2=m1;*s2=*s1;*s1=j;m1=ht[j].weight;}elseif(ht[j].weightm2&&ht[j].parent==0){m2=ht[j].weight;*s2=j;}}}主程序模块intmain(){初始化参数printf(请输入：初始化I;编码E;译码D;印代码文件P;印哈弗曼树T\n);printf(结束请输入Q\n);while(1){//这就是用户输入scanf(%c,&q);if(q=='Q'){break;}if(q=='I'){fpw=fopen(hfmtree.txt,w);ftest=fopen(date.txt,r);printf(请输入密码表，第一位表示密码表大小，之后按空格键开始以紧凑的格式输入编码字母和权值。\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;icount3;i++){for(j=1;j=count2/2;j++){len=strlen(hc1[j]);//对每个字符哈夫曼编码长度统计for(t=0;tlen;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;zcount4;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;icount;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%d\n,&str[i],&ht1[i].weight,&ht1[i].parent,&ht1[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(maxlenlen)maxlen=len;}count=maxlen;//求得最大字符编码长度，用来控制行数的for(i=1;i=m;i++){t=0;if(ht1[i].parent==0)//先寻找根节点，打印出来{for(c=0;c2*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;/记录根节点右子树，用数组low[]t++;k=ht1[i].rchild;//记录根节点左子树low[t]=k;t++;for(c=0;c2*count;c++)//打空格{printf();fprintf(fpw,);}printf(%d,ht1[j].weight);//打印根节点的右子树和左子树fprintf(fpw,%d,ht1[j].weight);printf();fprintf(fpw,);printf(%d\n,ht1[k].weight);fprintf(fpw,%d\n,ht1[k].weight);count=count-1;}}p=0;while(pmaxlen-2)//p来控制打印的结束标志{for(j=0;j2*count;j++){printf();fprintf(fpw,);}y=t;//y作为每一行节点数的记录用t=0;for(i=0;iy;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(fp