4.cpp

霍夫曼编码程序

#include<stdio.h>
#include<math.h>
#include<malloc.h>
#include<string.h>
#include<process.h>
#define  n  8
typedef char * *huffcode;
typedef struct{
	int weight;
	int parent,lchild,rchild;
}htnode, * hufftree;

void main()
{void inweight(char a[n],int b[n]);
void huffcodeing(hufftree &ht,char * * &hc,int b[]);
void selecta(hufftree ht,int t,int d[2]);
void encoding(char * *hc, char a[]);
void decoding(hufftree ht,char a[]);
void print();
void treeprint(hufftree ht);
char a[n];int b[n];hufftree ht;char * *hc;char c[2];
printf("I :开始; Q:结束\n");
scanf("%c",&c[0]);
while(c[0]!='Q')
{
printf("I:初始化E:编码D:译码P:印代码T:打印哈夫曼树  请选择\n");
switch(c[0])
{case'I': {inweight(a,b);
           huffcodeing(ht,hc,b);
		   
//printf("%d,%d,%d\n",ht[1].weight,ht[1].rchild,ht[1].lchild);
          }
         break;
case'E':{encoding(hc,a);
		} break;
case'D':{
	//printf("%d,%d,%d\n",ht[15].weight,ht[15].rchild,ht[15].lchild);
	decoding(ht,a);
		}break;
case'P':{print();
		}break;
case 'T':{treeprint(ht);}break;
}
printf("请选择下一步\n");
scanf("%c",&c[0]);
}
}
void inweight(char c[],int d[])
{int i;
printf("请输入字母\n");
for(i=0;i<=n;i++)
scanf("%c",&c[i]);
printf("请输入权值\n");
for(i=0;i<=n-1;i++)
scanf("%d",&d[i]);
printf("字母，权输入完毕\n");

}

void selecta(hufftree ht,int t,int *l)
{int i,*g;int s=0;int m=200;
g=(int *)malloc((t+1)*sizeof(int));
for(i=1;i<=t;i++)
{if(ht[i].parent==0)
*(g+i)=ht[i].weight;
else *(g+i)=200;}
for(i=1;i<=t;i++)
{if(*(g+i)<m)
{m=*(g+i);s=i;}
}*(l+0)=s;*(g+s)=200;m=200;s=0;
for(i=1;i<=t;i++)
{if(*(g+i)<m)
{m=*(g+i);s=i;}
}*(l+1)=s;
free(g);
}


void huffcodeing(hufftree &ht,char * * &hc,int b[n])
{int m,i,start,c;int f;char *cd;int d[2];FILE *fp;
if((fp=fopen("hfmtree.doc","w+"))==NULL)
{ printf("can not open the file\n ");
 exit(0);
}
if(n<=1) printf("error");
m=2*n-1;
ht=(hufftree)malloc((m+1)*sizeof(htnode));
for(i=1;i<=n;++i)
{ht[i].weight=b[i-1];ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}
for(;i<=m;++i)
{ht[i].weight=0;ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}
for(i=n+1;i<=m;++i)
{selecta(ht,i-1,d);
ht[d[0]].parent=i;ht[d[1]].parent=i;
ht[i].lchild=d[0];ht[i].rchild=d[1];
ht[i].weight=ht[d[0]].weight+ht[d[1]].weight;
}

hc=(huffcode)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-1)*sizeof(char));
strcpy (hc[i],&cd[start]);
if( fwrite(hc[i],(n-start-1)*sizeof(char),1,fp)!=1)
printf("file write error");

}
fclose(fp);
free(cd);
printf("树建立完毕\n");


}



void encoding(char * * hc, char m[n])
{char ps[30];char * *ps1;int t, i=0;int j=0;FILE *fp;
printf ("please in put the passage\n");
ps1=(huffcode)malloc((30)*sizeof(char *));
scanf("%s",ps);
for (i=0;ps[i]!='\0';i++)
{while(ps[i]!=m[j])
j++;
ps1[i]=hc[j];j=0;}
if((fp=fopen("codefile.doc","w+"))==NULL)
{ printf("can not open the file\n ");
exit(0);
}
for(t=0;t<i;t++)
{
	fprintf(fp,"%s",*(ps1+t));
	printf("%s",*(ps1+t));
}
fclose(fp);
printf("编码完毕");

}

void decoding( hufftree ht,char g[])
{//printf("%d,%d,%d\n",ht[15].weight,ht[15].rchild,ht[15].lchild);
//printf("can not open the file\n ");
char c;int t;FILE *fp,*fp1;
if((fp=fopen("codefile.doc","r"))==NULL)
{ printf("can not open the file\n ");
 exit(0);
}

if((fp1=fopen("txetfile.doc","w+"))==NULL)
{ printf("can not open the file\n ");
 exit(0);
}
t=2*n-1;
while(!feof(fp))
{t=2*n-1;
//printf("%d\n ",t);
while((ht[t].lchild && ht[t].rchild)!=0)
{fscanf(fp,"%c",&c);
if(c=='0')
{t=ht[t].lchild;
}
else
{t=ht[t].rchild;
}
}

fprintf(fp1,"%c",g[t]);
printf("%c",g[t]);

}
fclose(fp);fclose(fp1);
printf("译码完毕\n");

}


void print()
{int i;char ch;FILE *fp;
if((fp=fopen("codefile.doc","r"))==NULL)
{printf("can not open the file\n");
exit(0);

}

while(!feof(fp))
{for(i=1;i<=50;i++)
{ch=fgetc(fp);
putchar(ch);}
printf("\n");
}
//fprintf("codeprint",   );
//printf("\n");
fclose(fp);
printf("印待码完毕");}
void treeprint(hufftree ht)
{int i;
printf("weight parent lchild rchild\n ");
 for (i=1;i<=2*n-1;i++)
printf("%d %d %d %d\n",ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);	 

}