需求分析：

哈夫曼樹試驗(yàn)報(bào)告哈夫曼編碼，針對每個字母對其進(jìn)展譯碼，翻譯為原來的信息。二、概要設(shè)計(jì)程序分為以下幾個模塊：1、從終端讀入字符集大小，nnhfmTree2hfmTreehfm3ToTranhfmhfmCodefile中去4CodefileTextfileTreeprint抽象的數(shù)據(jù)定義如下：哈夫曼樹構(gòu)造typedefstruct //定義哈夫曼樹的構(gòu)造{intweight;//權(quán)值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) //取最小和次小權(quán)值{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{初始化參數(shù)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“);編碼字母和權(quán)值。\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--; 狀況下需要隔行輸入的設(shè)定}for(i=n+1;i<=2*n-1;i++) //補(bǔ)全剩余的{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); //關(guān)閉文件，這點(diǎn)很重要，否則文件不會寫入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是哈夫曼樹大小計(jì)數(shù)，count3是讀入的哈夫曼編碼計(jì)數(shù)crthuffmancode(ht1,hc1,count2-1); 重建立哈夫曼編碼表for(i=1;i<count3;i++){for(j=1;j<=count2/2;j++){len=strlen(hc1[j]); //對每個字符哈夫曼編碼長度統(tǒng)計(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”) //構(gòu)不好打印，這里就是通過本身構(gòu)造大致打印出來{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) //先查找根節(jié)點(diǎn)，打印出來{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; 記錄根節(jié)點(diǎn)左子樹low[t]=k;t++;for(c=0;c<2*count;c++) //打空格{printf(““);fprintf(fpw,““);}printf(“%d “,ht1[j].weight);//打印根節(jié)點(diǎn)的右子樹和左子樹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++) //下面就是一個循環(huán)過程{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++) //轉(zhuǎn)移{low[i]=d[i];}printf(“\n“);p++;count=count-1;}fclose(fpw); 記住關(guān)文件fclose(fpr);}}return0;}函數(shù)的調(diào)用關(guān)系MianCrthuffmancode crthuffmantreeselect設(shè)計(jì)和調(diào)試分析1、打印樹原來是考慮用嚴(yán)格格式輸出，但是需要空間太大，就用類似樹的形式輸出2、文件操作最終必需要關(guān)閉文件，否則會始終在緩沖區(qū)中用戶手冊用戶界面如下用戶需要預(yù)先預(yù)備好totran文件，然后依據(jù)提示輸入字符集大小和每個字母和對應(yīng)的權(quán)值，然后按測試結(jié)果測試數(shù)據(jù)為字符ABCDEFGHIJKLMNO權(quán)值64132232103211547571532205763字符PQRSTUVWXYZ權(quán)值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 //定義哈夫曼樹的構(gòu)造{intweight;intparent;intlchild;intrchild;}htnode,huffmantree[M+1];select(huffmantreeht,intpos,int*s1,int*s2) //取最小和次小權(quán)值{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++) //對字母建立哈夫曼樹的構(gòu)造{ht[i].weight=w[i];ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}m=2*n-1; //剩下的構(gòu)造初始化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，類似短除法求二進(jìn)制轉(zhuǎn)換//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) 假設(shè)雙親的左孩子等于該值在則該值0，1cd[start]=”0”;elsecd[start]=”1”;c=p; //向上走p=ht[p].parent;}hc[i]=(char*)malloc((n-start)*sizeof(char)); 數(shù)組指針strcpy(hc[i],&cd[start]); //字符串復(fù)制}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“);編碼字母和權(quán)值。\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--; 狀況下需要隔行輸入的設(shè)定}for(i=n+1;i<=2*n-1;i++) //補(bǔ)全剩余的{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); 關(guān)閉文件，這點(diǎn)很重要，否則文件不會寫入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是哈夫曼樹大小計(jì)數(shù)，count3是讀入的哈夫曼編碼計(jì)數(shù)crthuffmancode(ht1,hc1,count2-1); 重建立哈夫曼編碼表for(i=1;i<count3;i++){for(j=1;j<=count2/2;j++){len=strlen(hc1[j]); //對每個字符哈夫曼編碼長度統(tǒng)計(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”) //構(gòu)不好打印，這里就是通過本身構(gòu)造大致打印出來{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; 來掌握行數(shù)的for(i=1;i<=m;i++){t=0;if(ht1[i].parent==0) //先查找根節(jié)點(diǎn)，打印出來{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; //記錄根節(jié)點(diǎn)右子樹，用數(shù)組t++;k=ht1[i].rchi