hafuman2.txt

此霍夫曼编码可根据自己输入的字符集及频度构建霍夫曼树

#include <stdio.h> 
#include <conio.h> 
#include <string.h> 
#include <malloc.h> 

//#define NULL 0 
#define MAX_NUM 10000 
#define MAX 60 
int j=0; 

typedef int Status; 
typedef char **HuffmanCode; 

typedef struct{ 
unsigned int weight;//字符对应的权值 
unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree;//此处定义了哈夫曼树节点的数据类型。提供给Huffman使用 

typedef struct{ 
HuffmanTree HT; 
char *c;//存放将要建立哈夫曼树的字符 
int longth;//字符的大小，即开始第一步输入的一个整数 
HuffmanCode HC;//存放对应的哈夫编码即对应的01代码 
}Huffman; 

void Select(HuffmanTree HT,int end,int *s1,int *s2) 
//把输入的字符按权值从小到大排序，挑出最小权值供HuffmanCoding()调用 
//并且根节点的权值等于他的左右孩子的权值和 
//min2是在剩下的字符中挑出的最小的劝值的字符 

{ 
int i; 
int min1=MAX_NUM;//min1是根节点的权值 
int min2;//min2是在剩下的字符中挑出的最小的权值的字符 

for (i=1;i<=end;i++) 
{ 
if (HT[i].parent==0&&HT[i].weight<min1) 
{ 
*s1=i; 
min1=HT[i].weight; 
} 
} 
min2=MAX_NUM; 
for(i=1;i<=end;i++) 
{ 
if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight) 
{ 
*s2=i; 
min2=HT[i].weight; 
} 
} 
//test printf("qqqqq%d\nWWWWW%d\n",min1,min2); 
} 

Huffman HuffmanCoding(Huffman Hfm)//将输入的字符以及他的权值，按照哈夫曼规则建立2叉树 
{ 
/*---------------------------------*/ 
int i,n,m,s1,s2,start; 
int c,f; 
char *cd; 
n=Hfm.longth; 
if(n<=1) return Hfm; 
m=2*n-1; 

for(i=n+1;i<=m;++i) 
{ 
Select(Hfm.HT,i-1,&s1,&s2); 
Hfm.HT[s1].parent=i; 
Hfm.HT[s2].parent=i; 
Hfm.HT[i].lchild=s1; 
Hfm.HT[i].rchild=s2; 
Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight; 
//构造哈夫曼树时候，根节点的权值等于他的左右孩子权值和 

//test printf("ht%d\ns1--%d\ns2--%d", Hfm.HT[i].weight,s1,s2); 
} 
/*------------------------------------------*/ 
Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); 
cd=(char *)malloc(n*sizeof(char)); 
cd[n-1]='\0'; 
//中间变量用来存储字符对应的哈夫曼01编码 
for(i=1;i<=n;++i) 
{ 
start=n-1; 
for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent) 
{ 
if(c==Hfm.HT[f].lchild) cd[--start]='0'; 
else cd[--start]='1'; 
} 
Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char)); 
strcpy(Hfm.HC[i],&cd[start]); 
//将cd[]的值存储到变量Hfm.HC[i]中 
//该变量在Huffman数据类型中有定义 
} 
free(cd); 
return Hfm; 
} 

Huffman InputHuffman(Huffman Hfm)//接收原始数据： 从终端读入字符集大小n，n个字符和n个权值， 
//建立哈夫曼树，存于文件hfmtree.dat中。供InitHuffman（）函数调用 
{ 
int i,n; 
printf("\n\n\t\t********************构造哈夫曼树*********************\n"); 
printf("\t字符以及它的权值，数据将保存到同名目录下的'hfmTree.dat'\n"); 
printf("请输入字符的个数: "); 
scanf("%d",&n); 
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); 
Hfm.c=(char *)malloc((n+1)*sizeof(char)); 
for(i=1;i<=n;i++)//接收数据，并初始话，左右孩子节点赋0 
{ 
printf("请输入字符\n: "); 
scanf("%s",&Hfm.c[i]); 
printf("请输入他的权值\n: "); 
scanf("%d",&Hfm.HT[i].weight); 
Hfm.HT[i].parent=0; 
Hfm.HT[i].lchild=0; 
Hfm.HT[i].rchild=0; 
} 
for(;i<=2*n-1;++i) 
{ 
Hfm.HT[i].weight=0; 
Hfm.HT[i].parent=0; 
Hfm.HT[i].lchild=0; 
Hfm.HT[i].rchild=0; 
} 
Hfm.longth=n; 
return Hfm; 
} 

Huffman InitHuffman(Huffman Hfm)//初始化哈夫曼树，调用InputHuffman（），HuffmanCoding（）函数 
//将数据存入文件，如果文件以存在，那么直接读取数据，进行哈夫编码 
{ 
int n,i; 
FILE *fp; 
fp=fopen("hfmTree.dat","rt"); 
if(fp==NULL) 
{ 
Hfm=InputHuffman(Hfm); 
fp=fopen("hfmTree.dat","wt"); 
fprintf(fp,"%d\n",Hfm.longth); 
for(i=1;i<=Hfm.longth;i++) 
fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight); 
rewind(fp); 
} 
else 
{ 
fscanf(fp,"%d\n",&n); 
Hfm.c=(char *)malloc((n+1)*sizeof(char)); 
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); 
for(i=1;i<=n;i++) 
fscanf(fp,"%s %d",&Hfm.c[i],&Hfm.HT[i].weight); 
for(i=1;i<=n;i++) 
{ 
Hfm.HT[i].parent=0; 
Hfm.HT[i].lchild=0; 
Hfm.HT[i].rchild=0; 
} 
for(;i<=2*n-1;++i) 
{ 
Hfm.HT[i].weight=0; 
Hfm.HT[i].parent=0; 
Hfm.HT[i].lchild=0; 
Hfm.HT[i].rchild=0; 
} 
Hfm.longth=n; 
} 
fclose(fp); 
Hfm=HuffmanCoding(Hfm); 
return Hfm; 
} 


void Output(Huffman Hfm) 
//输出哈夫曼树，字符，权值，以及它对应的编码 
{ 
int i,n; 
n=Hfm.longth; 
printf("\n\n******************它的编码规则****************\n\n"); 
for(i=1;i<=n;i++) 
{ 
printf("\n"); 
printf("字符: %c\t",Hfm.c[i]); 
printf("权值: %d\t",Hfm.HT[i].weight); 
printf("对应的哈夫曼编码: "); 
puts(Hfm.HC[i]); 
} 
printf("\n\n******************打印哈夫曼树****************\n\n"); 
for(i=n;i>=1;i--) 
{ if(n==i) 
{ printf("\t\t*\n\n"); 
printf("\t%c\t\t*\n\n",Hfm.c[i]); 
} 
else if(i!=2&&i!=1) 
{ 
for(j=0;j<=n-i;j++) 
printf("\t"); 
printf("%c\t\t*\n\n",Hfm.c[i]); 
} 
else if(i==2) 
{ for(j=0;j<=n-i;j++) 
printf("\t"); 
printf("%c\t\t%c\n\n",Hfm.c[i],Hfm.c[1]); 
} 
else if(i==1) 
printf("\n\n"); 
} 

} 

void Encoding(Huffman Hfm) 
//编码： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入） 
//对文件中的正文进行编码，然后将结果存入文件codefile.dat中。 
//如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中 
//读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中 
{ 
int i=0,j=0,n; 
char ch[MAX]; 
FILE *fp,*ffp; 
n=Hfm.longth; 
printf("\n\n*******************编码**************************\n\n"); 
if((ffp=fopen("ToBeTran.dat","rt"))==NULL) 
{ 
printf("\n请输入要进行编码的句子: "); 
scanf("%s",&ch); 
printf("\n"); 
fp=fopen("CodeFile.dat","wt+"); 
} 
else 
{ 
fscanf(ffp,"%s",ch); 
fclose(ffp); 
} 
while(ch[j]) 
{ 
for(i=1;i<=n;i++) 
if(ch[j]==Hfm.c[i]) 
{ 
printf("%s",Hfm.HC[i]); 
fprintf(fp,"%s",Hfm.HC[i]); 
break; 
} 
j++; 
} 
rewind(fp); 
fclose(fp); 
} 

void Decoding(Huffman Hfm) 
//译码： 利用已建好的哈夫曼树将文件codefile.dat 
//中的代码进行译码，结果存入文件textfile.dat 中 
{ 
HuffmanTree p; 
int i,n; 
int j=0; 
char d[50]; 
FILE *fp; 
n=Hfm.longth; 
printf("\n\n******************译码************************\n\n"); 
if((fp=fopen("CodeFile.dat","rt"))==NULL) 
{ 
printf("输入哈夫曼码进行译码\n:"); 
scanf("%s",&d); 
} 
else 
{ 
fscanf(fp,"%s",d); 
fclose(fp); 
} 
printf("\nThe file is : "); 
fp=fopen("TextFile.dat","wt+"); 
while(d[j]) 
{ 
p=&Hfm.HT[2*n-1]; 
while(p->lchild||p->rchild) 
{ 
if(d[j]=='0') 
{ i=p->lchild; p=&Hfm.HT[i]; } 
else 
{ i=p->rchild; p=&Hfm.HT[i]; } 
j++; 
}; 
printf("%c",Hfm.c[i]); 
fprintf(fp,"%c",Hfm.c[i]); 
} 
fclose(fp); 

} 

int main() 
{ 
Huffman Hfm; 
char choice='a'; 
Hfm=InitHuffman(Hfm); 
while(choice!='q') 
{ 
printf("\n\n\n\t\t*************************************\n\n"); 
printf("\t\t\ta. 编码:\n\n"); 
printf("\t\t\tb. 译码:\n\n"); 
printf("\t\t\tc. 打印哈夫曼树以及它的编码规则:\n\n"); 
printf("\t\t\tq. 退出...\n\n"); 
printf("\n\t\t************************************\n\n"); 
printf("请输入你的选择\n: "); 
scanf("%s",&choice); 
switch(choice) 
{ 
case 'a': 
Encoding(Hfm); 
printf("\n\n*******Please enter anykey to continue*******\n"); 
getch(); break; 
case 'b': 
Decoding(Hfm); 
printf("\n\n*******Please enter anykey to continue********\n"); 
getch(); break; 
case 'c': 
Output(Hfm); 
printf("\n\n*******Please enter anykey to continue********\n"); 
getch(); break; 
case 'q': 
break; 
default: 
printf(" 选择错误!\n Please enter anykey to choice again!\n"); 
getch(); break; 
} 
} 
return 0; 
}