关于哈弗曼的解压
程序代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct { int weight; char ch; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; void welcome(); void HuffmanCoding(HuffmanTree &,char *,int *,int); void select(HuffmanTree HT,int j,int *s1,int *s2); void Init(); void Coding(); void Decoding(); void Print_code(); int Read_tree(HuffmanTree &); void find(HuffmanTree &HT,char *code,char *text,int i,int m); HuffmanTree HT; int n=0; int main() { char select; while(1) { welcome(); scanf("%c",&select); switch(select) { case '1':Init();break; case '2':Coding();break; case '3':Decoding();break; case '4':Print_code();break; case '5':exit(1); default :printf("Input error!\n"); } getchar(); } return 0; } void welcome() { printf("*_______________________________________________________*\n"); printf("| 菜单 |\n"); printf("|_______________________________________________________|\n"); printf("| |\n"); printf("| |\n"); printf("| 1 --------------------------建立哈夫曼树. |\n"); printf("| 2 --------------------------哈夫曼树编码压缩. |\n"); printf("| 3 --------------------------哈夫曼树译码. |\n"); printf("| 4 --------------------------输出压缩codefile文件. |\n"); printf("| 5 --------------------------退出. |\n"); printf("| |\n"); printf("|______________________________________________________|\n"); printf("|______________________________________________________|\n"); } void Init() { FILE *fp; int i,n,w[50]; char character[50]; printf("\n输入字符个数 n:"); scanf("%d",&n); printf("输入%d个字符:\n",n); for (i=0;i<n;i++) { char b=getchar(); scanf("%c",&character[i]); } printf("输入%d个对应的权值:\n",n); for(i=0;i<n;i++) { char b=getchar(); scanf("%d",&w[i]); } HuffmanCoding(HT,character,w,n); if((fp=fopen("hfmtree.txt","w"))==NULL) printf("打开文件 hfmtree.txt 错误!\n"); for (i=1;i<=2*n-1;i++) { if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) printf("文件写入错误!\n"); } printf("\n建立赫夫曼树成功,已将其存于文件hfmtree.txt中\n"); fclose(fp); } void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n) { int m,i,s1,s2; HuffmanTree p; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p,++character,++w) { p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0; } for(i=n+1;i<=m;++i,++p) { p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0; } for(i=n+1;i<=m;++i) { select(HT,i-1,&s1,&s2); 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; } } void select(HuffmanTree HT,int j,int *s1,int *s2) { int i; for (i=1;i<=j;i++) if (HT[i].parent==0) { *s1=i;break; } for (;i<=j;i++) if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight)) *s1=i; HT[*s1].parent=1; for (i=1;i<=j;i++) if (HT[i].parent==0) { *s2=i;break; } for (;i<=j;i++) if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight)) *s2=i; } void Coding() { FILE *fp,*fw; int i,f,c,start,t=1,J,l,k=1; char *cd; HuffmanCode HC; if(n==0) n=Read_tree(HT); { HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i) { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); } if((fp=fopen("tobetrans.txt","rb"))==NULL) printf("打开文件tobetrans.txt 错误!\n"); if((fw=fopen("codefile.txt","wb"))==NULL) printf("打开文件 codefile.txt 错误!\n"); // fscanf(fp,"%c",&temp); // while(!feof(fp)) // { // // for(i=1;i<=n;i++) // if(HT[i].ch==temp) break; //该部分为直接输出哈夫曼编码 // for(int r=0;HC[i][r]!='\0';r++) // { // fputc(HC[i][r],fw); // } // fscanf(fp,"%c",&temp); // } char temp; while(!feof(fp)) { temp=fgetc(fp); for(i=1;i<=n;i++) { if(HT[i].ch==temp) { l=strlen(HC[i]); if(l+k>=32) { fwrite(&c,4,1,fw); c=1; //该部分为输出压缩文件 k=1; } for(J=0;J<l;J++) { if(HC[i][J]=='0') c=c<<1; else {c=c<<1;c=c|1;} k++; } break; } } } fwrite(&c,4,1,fw); fclose(fw); fclose(fp); printf("\n对文件hfmtree.txt编码,压缩成功,结果存入codefile.txt中。\n\n"); } void Decoding() { FILE *fp,*fw; int m,i; char *code,*text,*p; if(n==0) n=Read_tree(HT); if((fp=fopen("codefile.txt","r"))==NULL) printf("打开文件 codefile.txt 错误!\n"); if((fw=fopen("textfile.txt","w"))==NULL) printf("打开文件 textfile.txt 错误!\n"); code=(char *)malloc(sizeof(char)); fscanf(fp,"%c",code); //////////////////////////////////////////////////////// for(i=1;!feof(fp);i++) { code=(char *)realloc(code,(i+1)*sizeof(char)); fscanf(fp,"%c",&code[i]); } code[i-1]='\0'; text=(char *)malloc(100*sizeof(char)); p=text; //中间这部分要改 m=2*n-1; if(*code=='0') find(HT,code,text,HT[m].lchild,m); else find(HT,code,text,HT[m].rchild,m); for(i=0;p[i]!='\0';i++) fputc(p[i],fw);//////////////////////////////////////////////////////////////// //fwrite(& ,4,1,fw); /* int t=1,J,l,k=1,c; char temp; HuffmanCode HC; while(!feof(fp)) { temp=fgetc(fp); for(i=1;i<=n;i++) { if(HT[i].ch==temp) { l=strlen(HC[i]); if(l+k>=32) { fwrite(&c,4,1,fw); c=1; //该部分为输出压缩文件 k=1; } for(J=0;J<l;J++) { if(HC[i][J]=='0') c=c>>1; else {c=c>>1;c=c|1;} k++; } break; } } } fwrite(&c,4,1,fw);*/////////////// fclose(fp); fclose(fw); printf("\n对codefile.txt文件译码成功,结果已存入textfile.txt文件。\n\n"); } void find(HuffmanTree &HT,char *code,char *text,int i,int m) { if(*code!='\0') //若译码未结束 { code++; if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点 { *text=HT[i].ch; text++; if((*code=='0')) find(HT,code,text,HT[m].lchild,m); else find(HT,code,text,HT[m].rchild,m); } else //如果不是叶子节点 if(*code=='0') find(HT,code,text,HT[i].lchild,m); else find(HT,code,text,HT[i].rchild,m); } else *text='\0'; //译码结束 } void Print_code() { FILE *fp,*fw; char temp; int i; if((fp=fopen("codefile.txt","r"))==NULL) printf("打开文件codefile.txt 错误!\n"); if((fw=fopen("codeprint.txt","w"))==NULL) printf("打开文件 codeprint.txt 错误!\n"); printf("\n文件codefi1e以压缩形式如下:\n"); fscanf(fp,"%c",&temp); //从文件读入一个字符 for (i=1;!feof(fp);i++) { printf("%c",temp); if(i%50==0) printf("\n"); fputc(temp,fw); //将该字符存入文件codeprint.txt中 fscanf(fp,"%c",&temp); //从文件读入一个字符 } printf("\n\n此字符形式的编码已写入文件codeprint.txt中.\n\n"); fclose(fp); fclose(fw); } int Read_tree(HuffmanTree &HT) { FILE *fp; int i,n; HT=(HuffmanTree)malloc(sizeof(HTNode)); if((fp=fopen("hfmtree.txt","r"))==NULL) printf("打开文件 hfmtree.txt 错误!\n"); for (i=1;!feof(fp);i++) { HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); fread(&HT[i],sizeof(HTNode),1,fp); } fclose(fp); n=(i-1)/2; return n;//返回叶子 }