#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct {
char letter;
int wt;
}hfm,*hfmlist;
//*************************全局变量************************************
unsigned int s1,s2,n;
char choose;
int DEPTH=0;
char a[20];
//***************Huffman树和Huffman编码的存储表示**********************
typedef struct{
unsigned int weight;
unsigned int code;
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree; //动态分配数组存储Huffman树
typedef char * *HuffmanCode; //动态分配数组存储Huffman编码表
//***************************初始化Huffman树***************************
void select(HuffmanTree HT,int l){
int a,b,c,j;
s1=s2=1;
a=b=1000;
for(j=1;j<=l;j++){
if(HT[j].code==0){
c=HT[j].weight;
if(c<a){b=a;a=c;s2=s1;s1=j;}
else if(c<b){b=c;s2=j;}
}//if
}//for
HT[s1].code=HT[s2].code=1;
}//select
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, hfmlist HL,unsigned int n){
//w存放n个权值（均>0），构造Huffman树HT,并求出n个字符的Huffman编码HC.
unsigned int i,f,start,c,m;
char*cd;
if (n<=1) return;
m =2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=m;++i){HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=HT[i].code=0;}
for(i=1;i<=n;++i)HT[i].weight=HL[i].wt;
for (i=n+1;i<=m;++i){
select(HT,i-1);
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;
}
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);
}
//*************************文件操作*****************************
void save (char *p){
FILE *fp;
int i;
printf("input the name:");
if((fp=fopen(gets(a),"w+"))==NULL){
printf("cannot open the file!\n");
exit(0);}//if
for(i=0;p[i]!='\0';i++){
if(fwrite(p+i,sizeof(char),1,fp)!=1){//fwrite函数写数据块
printf("File write error!\n");exit(0);}//if
}//for
fclose(fp);
}//save
//************************编码与译码操作**********************************
void Decoding(HuffmanTree HT,hfmlist HL,char*size,int n)//这个函数是用来译码的
{int i,j,k;
char p[30];
printf("请输入需要译码的代码:");gets(p);//接受需要译码的字符串
i=2*n-1;
k=0;
for(j=0;p[j]!='\0';j++){
if(p[j]=='0'){ if(HT[i].lchild!=0)i=HT[i].lchild;
else{ size[k++]=HL[i].letter;
i=2*n-1;
j--;}
}
else{ if(HT[i].rchild!=0)i=HT[i].rchild;
else{ size[k++]=HL[i].letter;
i=2*n-1;
j--;}
}
}//for
if( p[j-1]=='0')size[k++]=HL[i].letter;
else size[k++]=HL[i].letter;
size[k]='\0';
}//decoding
void Encoding(HuffmanCode HC,hfmlist HL,char *coding,int n){
int i,j,t,k=0;
char p[100];
printf("请再次输入需要编码的文本:");
gets(p);
for(i=0;p[i]!='\0';i++){
if((p[i]>='a'&&p[i]<='z')||p[i]==' ')
for(j=1;j<=n;j++)
if(p[i]==HL[j].letter)
for(t=0;HC[j][t]!='\0';t++)
coding[k++]=HC[j][t];
}//for
coding[k]='\0';
}//encoding
//************************打印操作****************************
void Print(FILE *fp1,FILE *fp2){
//将文件fp1中的代码以紧凑格式显示在终端上，每行50个代码
//同时将此字符形式的编码文件写入文件fp2中
char c[200];
int i;
fgets(c,200,fp1);
for(i=0;c[i]=='0'||c[i]=='1';i++){
printf("%c",c[i]);
fprintf(fp2,"%c",c[i]);
if((i+1)/50*50==(i+1)){
printf("\n");
fprintf(fp2,"\n");
}
}//for
printf("\n");
}//Print
void PreOrderTraverse(HuffmanTree HT,int k,FILE *fp){
//先序遍历并打印树，结果存放于fp中,k为根结点的下标
int i;
for(i=1;i<=DEPTH-1;i++)fprintf(fp," ");
for(;i<=DEPTH;i++)fprintf(fp,"|------");
fprintf(fp,"%d\n",HT[k].weight);
if(HT[k].lchild!=0){
DEPTH++;
PreOrderTraverse(HT,HT[k].lchild,fp);
DEPTH--;
}
if(HT[k].rchild!=0){
DEPTH++;
PreOrderTraverse(HT,HT[k].rchild,fp);
DEPTH--;
}
if(HT[k].lchild==0&&HT[k].rchild==0)return;
return;
} //PreOrderTraverse
void TreePrinting(HuffmanTree HT,int n,FILE *fp){
//打印树HT，结果存于文件fp中，n为树的叶子结点数
int i,k;
for(i=1;i<=2*n;i++)if(HT[i].parent==0){k=i;break;}//寻找根结点
PreOrderTraverse(HT,k,fp);
return;
}//TreePrinting
//**************************主函数*********************************
void main()
{
FILE *fp1,*fp2,*fp3,*fp4,*fp5;
HuffmanTree HT;
HuffmanCode HC;
hfmlist HL;
unsigned int i,n;
char *b,c[100],cha,ch;
b=(char *)malloc(100*sizeof(char));
printf("请选择操作：\n");
printf("i:初始化(Initialization)\ne:编码(Encoding)\nd:译码(Decoding)\n");
printf("p:印代码文件(Print)\nt:印哈夫曼树(Tree printing)\nq:退出(Quit)\n");b=(char *)malloc(100*sizeof(char));
HL=(hfmlist)malloc(30*sizeof(hfm));//存储字符与权值，线性表长30
printf("\n");
printf("选择操作(i,e,d,p,t,q):");
ch=getchar();
getchar();
printf("\n");
do{
switch(ch){
case 'i':printf("正在进行初始化……\n");
printf("输入字符长度：");
scanf("%d",&n);
getchar();
printf("\n");
HC=(HuffmanCode)malloc((n+1)*sizeof(char));
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
for(i=1;i<=n;i++){
printf("请输入第%d个字符及权值(格式:字符 权值):",i);
scanf("%c %d",&(HL+i)->letter,&(HL+i)->wt);
getchar();
}//for
if((fp5=fopen("hfmTree.txt","w"))==NULL){
printf("cannot open file!\n");
exit(0);
}//if
for(i=1;i<=n;i++){
fprintf(fp5,"第%d个字符及权值:\t\t\t",i);
fprintf(fp5,"%c %d\n",(HL+i)->letter,(HL+i)->wt);
}//for
fclose(fp5);
HuffmanCoding(HT,HC,HL,n);
printf("\n已经将Huffman树存入文件hfmTree.txt中\n\n");
printf("初始化完毕，请选择操作：\n");
printf("i:重新初始化(Initialization)\ne:编码(Encoding)\nd:译码(Decoding)\n");
printf("p:印代码文件(Print)\nt:印哈夫曼树(Tree printing)\nq:退出(Quit)\n\n");
break;
case 'e':
printf("请输入编码,以#结尾：");
if((fp2=fopen("ToBeTran.txt","w"))==NULL){
printf("cannot open file\n");exit(0);
}//if
cha=getchar();
while(cha!='#')
{
fputc(cha,fp2);
cha=getchar();
}//while
getchar();
fclose(fp2);
printf("已经把编码存入文件ToBeTran.txt中\n\n");
Encoding(HC,HL,b,n);
printf("文本的哈夫曼编码是:");
printf("%s\n",b);
printf("下面进行保存:");
save(b);
printf("编码完毕，请选择操作：\n");
printf("i:重新初始化(Initialization)\ne:编码(Encoding)\nd:译码(Decoding)\n");
printf("p:印代码文件(Print)\nt:印哈夫曼树(Tree printing)\nq:退出(Quit)\n");
break;
case 'd':
Decoding(HT,HL,c,n);
printf("输入要译码的编码：");
printf("正在进行译码……\n");
printf("%s\n",c);
save(c);
printf("已经将结果存入文件%s中\n",a);
printf("译码完毕，请选择操作：\n");
printf("i:重新初始化(Initialization)\ne:编码(Encoding)\nd:译码(Decoding)\n");
printf("p:印代码文件(Print)\nt:印哈夫曼树(Tree printing)\nq:退出(Quit)\n");
break;
case 'p':
for(i=1;i<=n;i++)
printf("字符:%c\t\t\t译码:%s\n",HL[i].letter,HC[i]);
if((fp1=fopen("CodePrin.txt","w"))==NULL){
printf("cannot open the file!\n");
exit(0);
}//if
if((fp4=fopen("CodeFile.txt","r"))==NULL){
printf("cannot open the file!\n");
exit(0);
}//if
Print(fp4,fp1);
printf("该代码文件已经存在并命名为CodePrin.
