#include
#include
#include
#include
using namespace std;unsigned char saveChar = 0;
typedef struct
{int value;int p,l,r;
}HTNode,*HuffTree; struct fact
{ char ch;int weight;
};typedef char * * HuffCode;
typedef char * CHAR;void select(HuffTree &HT,int n,int &s1,int &s2);
void CREATEHUFFTREE(HuffTree &HT,fact *ww,int n,HuffCode &HC);
void BecomeCode(HuffCode &HC,int n,CHAR &Code,char *Text,int *match); void Code_ToBe_Artical(CHAR &Code,HuffTree &HT,fact *Fact,int n);
int main()
{HuffTree HT&#61;NULL;HuffCode HC; printf("请输入需要编码的文章\n");char Text[20000];CHAR Code &#61; NULL; gets(Text); int len&#61;strlen(Text);FILE *fp&#61;fopen("E:\\demo.txt", "w");if(fputs(Text, fp)!&#61;EOF){printf("写入E:\\demo.txt文件成功,大小为 %dk",len/1024&#43;1);}fclose(fp);int codeweight[54];int match[54];memset(codeweight,0,sizeof(codeweight));for(int i&#61;0;i<len;i&#43;&#43;) {if(Text[i]&#61;&#61;&#39; &#39;)codeweight[0]&#43;&#43;;else if(isupper(Text[i]))codeweight[Text[i]-&#39;A&#39;&#43;1]&#43;&#43;;elsecodeweight[Text[i]-&#39;a&#39;&#43;27]&#43;&#43;;}int n&#61;0;fact Fact[54]; for(int i&#61;0;i<&#61;52;i&#43;&#43;){if(codeweight[i]!&#61;0){if(i&#61;&#61;0)Fact[n].ch&#61;&#39; &#39;;else if(i<&#61;26) Fact[n].ch&#61;i&#43;&#39;A&#39;-1;elseFact[n].ch&#61;i&#43;&#39;a&#39;-27;match[i]&#61;n;Fact[n&#43;&#43;].weight&#61;codeweight[i];}}CREATEHUFFTREE(HT,Fact,n,HC); BecomeCode(HC,n,Code,Text,match); Code_ToBe_Artical(Code,HT,Fact,n); return 0;
}void select(HuffTree &HT,int n,int &s1,int &s2)
{s1&#61;s2&#61;0;HT[0].value&#61;0x7fffffff;for(int i&#61;1;i<&#61;n;i&#43;&#43;){if(HT[i].p!&#61;0)continue;if(HT[i].value<HT[s1].value){s2&#61;s1;s1&#61;i;}else if(HT[i].value<HT[s2].value)s2&#61;i;}
}void CREATEHUFFTREE(HuffTree &HT,fact *ww,int n,HuffCode &HC)
{int m&#61;n*2-1;HT &#61; (HuffTree)malloc((m&#43;1)*sizeof(HTNode)); int i,j,f;fact *w&#61;ww;HuffTree p;for(p &#61;HT,p&#43;&#43;,i&#61;1;i<&#61;n;i&#43;&#43;,p&#43;&#43;,w&#43;&#43;) {(*p).value&#61;(*w).weight,(*p).p&#61;0,(*p).l&#61;0,(*p).r&#61;0;}for(;i<&#61;m;i&#43;&#43;,p&#43;&#43;) {(*p).value&#61;0,(*p).p&#61;0,(*p).l&#61;0,(*p).r&#61;0;}int s1,s2;for(i&#61;n&#43;1;i<&#61;m;i&#43;&#43;){select(HT,i-1,s1,s2);HT[s1].p&#61;i,HT[s2].p&#61;i;HT[i].l&#61;s1,HT[i].r&#61;s2;HT[i].value&#61;HT[s1].value&#43;HT[s2].value;}HC &#61; (HuffCode)malloc((n&#43;1)*sizeof(char *)); char *temp&#61;(char *)malloc(n*sizeof(char));temp[n-1]&#61;&#39;\0&#39;;for(i&#61;1;i<&#61;n;i&#43;&#43;){int start&#61;n-2;for(j&#61;i,f&#61;HT[i].p;f!&#61;0;j&#61;f,f&#61;HT[f].p){if(HT[f].l&#61;&#61;j)temp[start--]&#61;&#39;0&#39;;elsetemp[start--]&#61;&#39;1&#39;;}HC[i]&#61;(char *)malloc((n-start)*sizeof(char));strcpy(HC[i],&temp[&#43;&#43;start]);}delete temp;printf("\n各个字符对应的编码\n");for(i&#61;1;i<&#61;n;i&#43;&#43;){if(ww[i-1].ch&#61;&#61;&#39; &#39;)printf("空格 --> ");elseprintf("%c --> ",ww[i-1].ch);puts(HC[i]);}
}void BecomeCode(HuffCode &HC,int n,CHAR &Code,char *Text,int *match)
{int len,i; len&#61;strlen(Text);Code &#61; (char *)malloc((len*n&#43;1)*sizeof(char));Code[0]&#61;&#39;\0&#39;; for(i&#61;0;i<len;i&#43;&#43;){if(Text[i]&#61;&#61;&#39; &#39;)strcat(Code,HC[1]);else if(Text[i]<&#61;&#39;Z&#39;&&Text[i]>&#61;&#39;A&#39;)strcat(Code,HC[ match[Text[i]-&#39;A&#39;&#43;1]&#43;1 ]);elsestrcat(Code,HC[ match[Text[i]-&#39;a&#39;&#43;27]&#43;1 ]);}printf("\n文章编码为\n");puts(Code);FILE *fp&#61;fopen("E:\\test.txt", "w");if(fputs(Code, fp)!&#61;EOF){printf("文章编码写入E:\\test.txt文件成功\n");}fclose(fp);FILE *fp2&#61;fopen("E:\\test.txt", "r");FILE *fpw &#61; fopen("E:\\Huffman","wb");char reder;int Hufflength&#61;0;int num&#61;0;{for(int i&#61;0;i<strlen(Code);i&#43;&#43;){saveChar &#61; ((Code[i]-&#39;0&#39;)|saveChar);num&#43;&#43;;if(num&#61;&#61;8){fwrite(&saveChar,sizeof(char),1,fpw);Hufflength&#43;&#43;;saveChar &#61; 0;num &#61; 0;}else{saveChar &#61; saveChar << 1; }}}if(num !&#61; 8){saveChar &#61; saveChar<<(7-num);fwrite(&saveChar,sizeof(char),1,fpw);Hufflength&#43;&#43;;}printf("加密文件写入E:\\Huffman 成功,大小为 %dk",Hufflength/1024&#43;1);fclose(fp2);fclose(fpw);}void Code_ToBe_Artical(CHAR &Code,HuffTree &HT,fact *Fact,int n)
{printf("\n将编码解码\n");for(int i&#61;0;Code[i]!&#61;&#39;\0&#39;;i&#43;&#43;){int m&#61;n*2-1,ok&#61;1;while(1){if(Code[i]&#61;&#61;&#39;0&#39;){m&#61;HT[m].l;if(HT[m].l&#61;&#61;0){printf("%c",Fact[m-1].ch);break;}}else if(Code[i]&#61;&#61;&#39;1&#39;){m&#61;HT[m].r;if(HT[m].r&#61;&#61;0){printf("%c",Fact[m-1].ch);ok&#61;0;}}if(!ok)break;i&#43;&#43;;}}printf("\n");return ;
}