关于哈弗曼的解压
程序代码：#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;//返回叶子
}
