霍夫曼算法的实现
（通过对霍夫曼算法的实现，进一步了解霍夫曼算法进行数据压缩的原理及过程）
（用c++语言完成霍夫曼算法的实现）
1. 算法的描述
1初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
2把概率最小的两个符号组成一个节点，
3重复步骤2，得到节点P2，P3，P4，形成一棵树，其中p4称为根节点。
4从根节点开始到相应于每个符号的树叶。
5从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码
2. 算法中主要功能函数的设计思想
compress_math函数进行数据的压缩操作
Huffman_c函数用Huffman编码压缩指定的文件，并将结果存为新的文件
Huffman_d函数进行Huffman解码
decompress_math函数进行数据的解压缩操作
3. 算法的具体实现过程（代码）
**********************************************************************************************************/
int Huffman_c(char * infilename, char * outfilename) //用Huffman编码压缩指定的文件
{
if ((ifile = fopen (infilename, “rb”)) != NULL)
{
fseek (ifile, 0L, 2);
file_size = (unsigned long) ftell (ifile);
fseek (ifile, 0L, 0);
get_frequency_count ();
build_initial_heap ();
build_code_tree ();
if (!generate_code_table ()) {
printf (“ERROR! Code Value Out of Range. Cannot Compress./n”);
return 0;
}
else
{
if ((ofile = fopen (outfilename, “wb”)) != NULL)
{
fwrite (&file_size, sizeof (file_size), 1, ofile);
fwrite (code, 2, 256, ofile);
fwrite (code_length, 1, 256, ofile);
fseek (ifile, 0L, 0);
compress_math ();
fclose (ofile);
}
else
{
printf(“/nERROR: Couldn’t create output file %s/n”, outfilename);
return 0;
}
}
fclose (ifile);
}
else
{
printf (“/nERROR: %s — File not found!/n”, infilename);
return 0;
}
return 1;
}
void compress_math () // 进行数据的压缩操作
{
register unsigned int thebyte = 0;
register short loop1;
register unsigned short current_code;
register unsigned long loop;
unsigned short current_length, dvalue;
unsigned long curbyte = 0;
short curbit = 7;
for (loop = 0L; loop < file_size; loop++)
{
dvalue = (unsigned short) getc (ifile);
current_code = code[dvalue];
current_length = (unsigned short) code_length[dvalue];
for (loop1 = current_length-1; loop1 >= 0; –loop1)
{
if ((current_code >> loop1) & 1)
thebyte |= (char) (1 << curbit);
if (–curbit < 0)
{
putc (thebyte, ofile);
thebyte = 0;
curbyte++;
curbit = 7;
}
}
}
putc (thebyte, ofile);
compress_charcount = ++curbyte;
}
int Huffman_d(char * infilename, char * outfilename) // 本函数进行Huffman解码
{
if ((ifile = fopen (infilename, “rb”)) != NULL)
{
fread (&file_size, sizeof (file_size), 1, ifile);
fread (code, 2, 256, ifile);
fread (code_length, 1, 256, ifile);
build_decomp_tree ();
if ((ofile = fopen (outfilename, “wb”)) != NULL)
{
decompress_math();
fclose (ofile);
}
else
{
printf (“/nERROR: Couldn’t create output file %s/n”, outfilename);
return 0;
}
fclose (ifile);
}
else
{
printf (“/nERROR: %s — File not found!/n”, infilename);
return 0;
}
return 1;
}
void decompress_math () // 进行数据的解压缩操作
{
register unsigned short cindex = 1;
register char curchar;
register short bitshift;
unsigned long charcount = 0L;
while (charcount < file_size)
{
curchar = (char) getc (ifile);
for (bitshift = 7; bitshift >= 0; –bitshift)
{
cindex = (cindex << 1) + ((curchar >> bitshift) & 1);
if (decomp_tree[cindex] <= 0)
{
putc ((int) (-decomp_tree[cindex]), ofile);
if ((++charcount) == file_size)
bitshift = 0;
else
cindex = 1;
}
else
cindex = decomp_tree[cindex]; }
}
}