#include "stdlib.h" //exit
#include "math.h" //pow,floor函数
#include "string.h" //strcmp函数
#include "stdio.h"
#include "malloc.h"
#define max_char 10000 //最后结束符为257
#define Max_code_length 256 //共257个字符,可能的最长代码二进制位数为256个,假设第257个字符为结束符
#define Max_number 257 //加上结束符,共257个字符
typedef struct tree_node
{
int data; //结点值
float weight; //权重,把权重写入输出文件时,
struct tree_node* Lchild; //左结点
struct tree_node* Rchild; //右结点
}NODE;
typedef struct codetype
{
int code[Max_code_length]; //共257个字符,可能的最长代码二进制位数为256个,假设第257个字符为结束符
int code_length;
}CODE;
CODE codes[Max_number];
FILE * read_file();//打开原始文件,读文件
void InitHuffman(NODE nodes[],int max);
void count_bytes(char save[], NODE nodes[]);//计算每个ascii码出现的次数,即求权重
void order_nodes(NODE nodes[]);
NODE* build_tree(NODE nodes[]);
void tree_view(int m,NODE nodes[],NODE *p);
void HuffmanDode_creat(NODE *p, NODE nodes[]);
void code_view(NODE nodes[]);
void transform(char save[]);
FILE * write_file(int i,int j);//创建一个新文件,准备写入
int sum=0;
char save[max_char];
int main(int argc, char* argv[])
{
int a;
FILE *input;//,*output; //输入和输出文件的指针
read_file();//打开原始文件,读文件
printf("%s",save);
NODE nodes[Max_number+1]; // 共257个字符,所以存在2*257-1=513个结点
InitHuffman(nodes,Max_number);//初始化 dLL和exe两者都行
count_bytes(save,nodes);//计算每个ascii码出现的次数,即求权重
order_nodes( nodes);
build_tree(nodes); // dLL和exe两者都行,构建huffman树build_tree(nodes); 返回根结点的位置,但压缩时无需返回根结点,还原程序需要返回值
HuffmanDode_creat(build_tree(nodes),nodes);
code_view(nodes);
transform(save);
printf("\n");
return 0;
}
FILE * read_file()//打开原始文件,读文件
{
FILE *fp;
fp=fopen("f.txt","rb");
fread(save,sizeof(char),1000,fp);
fclose(fp);
return fp;
};
FILE * write_file(int i,int j )//打开原始文件,写文件
{
FILE *fp;
fp=fopen("t.txt","a+");
fwrite(&(codes[save[i]].code[j]),sizeof(char),1,fp);
fclose(fp);
return fp;
};
void InitHuffman(NODE nodes[],int max)//初始化 dLL和exe两者都行
{
int i;
for(i=0;i<=max;i++)
{
nodes[i].data=i;
nodes[i].weight=0;
nodes[i].Lchild=NULL;
nodes[i].Rchild=NULL;
}
};
void count_bytes(char save[], NODE nodes[])//计算每个ascii码出现的次数,相当于在求权重(其实不是权重。。。)
{
int i=0,j=0;
while(save[i]!='\0')
{
for(j=0;j<= Max_number;j++)
{
if(save[i]==nodes[j].data )
{
nodes[j].weight +=1;
break;
}
}
i++;
}
};
void order_nodes(NODE nodes[])//通过出现次数对节点重新排序
{
int i=0,j=0;
NODE *p;
p=(NODE*)malloc(sizeof(NODE));
for(i=Max_number;i>=0;i--)
{
for(j=0;j<i;j++)
{
if( nodes[j].weight>nodes[j+1].weight )
{
p->data = nodes[j].data;
p->weight =nodes[j].weight;
nodes[j].data=nodes[j+1].data;
nodes[j].weight=nodes[j+1].weight;
nodes[j+1].data=p->data;
nodes[j+1].weight=p->weight;
}
}
}
};
NODE* build_tree(NODE nodes[])//建立霍夫曼树
{
NODE* p,*q;
int i=0;
for(i=0;i<=257;i++)
{
if(nodes[i].weight!=0)
{
p=&nodes[i];
if(i==257)
{
return p;
}
else
{
for(;i<Max_number;i++)
{
q=(NODE*)malloc(sizeof(NODE));
q->data =-1;
q->weight =-1;
q->Lchild =&nodes[i+1] ;
q->Rchild =p;
p=q;
}
break;
}
}
else
{
q=NULL;
}
}
return q;
};
void tree_view( int m,NODE nodes[], NODE *p)//通过后续遍历访问霍夫曼树达到编码的目的
{
if (p->data==m)
{
codes[m].code[sum]=1;
sum+=1;
codes[m].code_length +=1;
}
else
{
if(p->Lchild ->data !=m)
{
codes[m].code[sum]=1;
p=p->Rchild;
sum+=1;
codes[m].code_length +=1;
tree_view(m ,nodes, p);
}
else
{
if(p->Lchild ->data ==m)
{
codes[m].code[sum]=0;
codes[m].code_length +=1;
}
}
}
};
void HuffmanDode_creat(NODE *p, NODE nodes[])//生成霍夫曼代编码
{
int i=0;
for(i=0;i<=Max_number;i++)
{ sum=0;
codes[i].code_length =0;
if(nodes[i].weight !=0)
{
tree_view(nodes[i].data ,nodes, p);
}
}
};
void code_view(NODE nodes[])//把出现过的
{
int i=0,j=0;
for(i=0;i<=Max_number;i++)
{ j=0;
if(nodes[i].weight !=0)
{
printf("\n%c的霍夫曼编码为:\n",nodes[i].data);
for(j=0;j<codes[nodes[i].data].code_length;j++)
{
printf("%d",codes[nodes[i].data].code[j]);
}
}
}
};
void transform(char save[])//将本件全部转化成霍夫曼编码
{
printf("\n此文件中字母的霍夫曼编码为:\n");
int i=0,j=0;
for(i=0;i<=max_char;i++)
{
if (save[i]!='\0')
{
for(j=0;j<codes[save[i]].code_length;j++)
{
write_file(i,j);
printf("%d",codes[save[i]].code[j]);
}
}
else
{
break;
}
}
};