數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼源代碼

#include<stdio.h>#include<stdlib.h>#inelude<math.h>#inelude<string.h>#defineN1000charkind[N]={'\0'};intnum[N]={0};intcount=0;ints1,s2;typedefstruct{intweight;/*字符權(quán)重*/intparent,lchild,rchild;}HTNode,*HuffmanTree;/*定義哈夫曼樹結(jié)點*/typedefchar**HuffmanCode;structcharcode{chardata;charcode[20];}Code[N],d[N],e[N];voidCreat_message()/*輸入字符并存入文件*/{FILE*fp;charc;if((fp=fopen(”文本文件.txt","wb"))==NULL){printf("cannotopenthisfile!\n");return;}printf("請輸入原代碼，以#表示結(jié)束\n”)；do{scanf("%c",&c);fputc(c,fp);}while(c!='#');fclose(fp);}voidCalculate() /*計算文件中字符的權(quán)值 */{charc;inti=1,k;FILE*fp;if((fp=fopen(”文本文件.txt","rb"))==NULL){printf("cannotopenthisfile\n");return;}c=fgetc(fp);while(c!='#'){for(k=O;k<i;k++)if(c==kind[k]){num[k]++;break;}if(k>=i&&kind[k-1]!=c){kind[i]=c;num[i]++;i++;}c=fgetc(fp);}count=i-1;}voidselect(HuffmanTreeHu,intj) /*尋找輸入的字符數(shù)據(jù)中權(quán)值最小的兩個結(jié)點 */{intk=1,t;while(Hu[k].parent!=O)k++;for(t=k;t<=j;t++)if(Hu[t].parent==O&&Hu[t].weight<Hu[k].weight)k=t;s仁k;k=1;while(Hu[k].parent!=O||k==s1)k++;for(t=k;t<=j;t++)if(Hu[t].weight<Hu[k].weight&&Hu[t].parent==O&&t!=s1)k=t;s2=k;}voidHuffmanCoding() /*構(gòu)建哈夫曼樹并編碼*/{voidselect(HuffmanTreeHu,intj);HuffmanTreeHT;HuffmanCodeHC;intm,i,start,f,c;char*cd;FILE*fp;if(count<=1)return;m=2*count-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=count;i++)HT[i].weight=num[i];for(i=1;i<=m;i++){HT[i].parent=O;HT[i].lchild=0;HT[i].rchild=O;}for(i=count+1;i<=m;i++){select(HT,i-1);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;}HC=(HuffmanCode)malloc((count+1)*sizeof(char*));cd=(char*)malloc(count*sizeof(char));cd[count-1]='\0：for(i=1;i<=count;i++){start=count-1;for(c=i,f=HT[i].parent;f!=O;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((count-start)*sizeof(char));strcpy(HC[i],&cd[start]);}if((fp=fopen(”字符代碼.txt","wb"))==NULL){printf("cannotopenthisfile\n");return;}for(i=1;i<=count;i++){Code[i].data=kind[i];strcpy(Code[i].code,HC[i]);fwrite(&Code[i],sizeof(structcharcode),1,fp);}fclose(fp);}voidTransform() /*將字符文件翻譯成代碼文件 */{FILE*fp1,*fp2,*fp3;inti;charc;if((fp仁fopen(”字符代碼.txt","rb"))==NULL){printf("cannotopenthisfile\n");return;}if((fp2=fopen(”文本文件.txt","rb"))==NULL){printf("cannotopenthisfile\n");return;}if((fp3=fopen(”碼本文件.txt","wb"))==NULL){printf("cannotopenthisfile\n");return;}for(i=0;i<count;i++)fread(&d[i],sizeof(structcharcode),1,fp1);while(!feof(fp2)){c=fgetc(fp2);for(i=0;i<count;i++)if(d[i].data==c){fputs(d[i].code,fp3);break;}}fputc(#,fp3);fclose(fp3);}voidTranslate() /*將代碼文件翻譯成字符文件 */{FILE*fp1,*fp2,*fp3;inti,j,k;charc[20]={'\0'};if((fp仁fopen(”碼本文件.txt","rb"))==NULL){printf("cannotopenthisfile\n");return;}if((fp2=fopen(”字符代碼.txt","rb"))==NULL){printf("cannotopenthisfile\n");return;}if((fp3=fopen(”破譯文件.txt","wb"))==NULL){printf("cannotopenthisfile\n");return;}for(i=1;i<=count;i++)fread(&d[i],sizeof(structcharcode),1,fp2);i=0;c[i]=fgetc(fp1);while(c[i]!='#'){for(k=1;k<=count;k++)if(!strcmp(c,d[k].code)){fputc(d[k].data,fp3);for(j=0;j<=i;j++)c[j]='\0';i=-1;break;}c[i]=fgetc(fp1);}fputc('#',fp3);fclose(fpl);fclose(fp2);fclose(fp3);}voidprint1(char*name) /*打印文件函數(shù)*/{FILE*fp;charc;if((fp=fopen(name,"rb"))==NULL){printf("cannotopenthisfile\n");return;}c=fgetc(fp);while(c!='#'){printf("%c",c);c=fgetc(fp);}}voidprint2(char*name) /*打印文件函數(shù)*/{FILE*fp;inti=1;if((fp=fopen(name,"rb"))==NULL){printf("cannotopenthisfile\n");return;}while(!feof(fp)){fread(&e[i],sizeof(structcharcode),1,fp);printf("%c--%s\n",e[i].data,e[i].code);i++;}}voidmain(){Creat_message();printf("您輸入的文本文件是：\n");print1("文本文件.txt");printf("\n");Calculate();HuffmanCoding();

printf(”每個字符相應(yīng)的哈夫曼編碼是：