哈夫曼编码压缩文件

#include
#include
#include
#include
using namespace std;unsigned char saveChar &＃61; 0; //用来保存二进制文件&＃xff0c;因为char类型是1个字节&＃xff0c;所以每8位储存一次 ,而且用unsigned无符号型&＃xff0c;避免符号位干扰
typedef struct
{int value;int p,l,r;
}HTNode,*HuffTree; //哈夫曼树struct fact //因为不是每一篇文章中所有字符都会出现
{ //所以结构体数组存储数组下标真正对应的字符ch以及权值weightchar ch;//字符int weight;//权重
};typedef char * * HuffCode; // 字符指针数组用于存储各个字符对应的编码
typedef char * CHAR;void select(HuffTree &HT,int n,int &s1,int &s2); //查找HT中未被使用的权值最小的两个点的下标
void CREATEHUFFTREE(HuffTree &HT,fact *ww,int n,HuffCode &HC); //建树函数&＃xff0c;附带完成每一个字符对应的编码
void BecomeCode(HuffCode &HC,int n,CHAR &Code,char *Text,int *match); //由已知的各个字符的编码完成全文的编码void Code_ToBe_Artical(CHAR &Code,HuffTree &HT,fact *Fact,int n); //由全文的编码&＃xff0c;用已经建立的哈弗曼树完成解码
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");//printf("15555555");if(fputs(Text, fp)!&＃61;EOF){printf("写入E:\\demo.txt文件成功,大小为 %dk",len/1024&＃43;1);//printf("%d",len);}fclose(fp);int codeweight[54];//频率数组int match[54];memset(codeweight,0,sizeof(codeweight));//置0for(int i&＃61;0;i<len;i&＃43;&＃43;) // 统计频率 空格下标为0 &＃xff0c;&＃xff08;A~Z&＃xff09;下标分别为&＃xff08;1~26&＃xff09; &＃xff08;a~z&＃xff09;下标分别为&＃xff08;27~52&＃xff09;{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]; // 由于不是每一个字符都出现在文章中&＃xff0c;将codeweight数组录入Fact结构体数组中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); //建树函数&＃xff0c;附带完成每一个字符对应的编码BecomeCode(HC,n,Code,Text,match); //由已知的各个字符的编码完成全文的编码Code_ToBe_Artical(Code,HT,Fact,n); //由全文的编码&＃xff0c;用已经建立的哈弗曼树完成解码return 0;
}void select(HuffTree &HT,int n,int &s1,int &s2) //查找HT中未被使用的权值最小的两个点的下标
{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)); //分配m&＃43;1个内存&＃xff0c;是因为要存储m个数据&＃xff0c;但是要从HT数组下标1开始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;) //对HT &＃xff08;1~n&＃xff09;赋值语句{(*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;) //对HT &＃xff08;n&＃43;1~m&＃xff09;赋值语句{(*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; //纯粹是用已知的文本Text和HC将文本转化为编码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");//2进制写入文件char reder;int Hufflength&＃61;0;//压缩长度int num&＃61;0;//计数//int t&＃61;0;//printf("len&＃61;%d\n",strlen(Code));// while ((reder&＃61;fgetc(fp2))!&＃61;EOF)//一个一个读入字符{//t&＃43;&＃43;;for(int i&＃61;0;i<strlen(Code);i&＃43;&＃43;){//saveChar || &＃61; (code[i]-&＃39;0&＃39;);//printf("%c",Code[i]);saveChar &＃61; ((Code[i]-&＃39;0&＃39;)|saveChar);//让saveChar和编码中的每一位进行或操作num&＃43;&＃43;;if(num&＃61;&＃61;8){fwrite(&saveChar,sizeof(char),1,fpw);//每8位写入一次文件Hufflength&＃43;&＃43;;saveChar &＃61; 0;//重新置0num &＃61; 0;}else{saveChar &＃61; saveChar << 1; //每做完一步&＃xff0c;左移一位}}}//printf("t&＃61;%d",t);//最后不到8位&＃xff0c;移到最左端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);//printf("%d",Hufflength);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 ;
}