huffman解码.doc

#include "stdio.h"
#include "stdlib.h" //exit
#include "math.h" //pow,floor函数
#include "string.h" //strcmp函数
#define END_OF_STREAM 256 //最后结束符为257
#define Max_code_length 256 //共257个字符，可能的最长代码二进制位数为256个，假设第257个字符为结束符
#define Max_number 257 //加上结束符，共257个字
typedef struct tree_node
{
double weight; //权重,把权重写入输出文件时，
int flag; //标识是否为待构建结点，是的话用0表示，否则用1表示
int parent; //父结点
int lchild; //左结点
int rchild; //右结点
}NODE;

typedef struct codetype
{
int code[Max_code_length]; //共257个字符，可能的最长代码二进制位数为256个，假设第257个字符为结束符
int code_length;
}CODE;

FILE *read_file1(char *p)//读取文件
{
FILE *fp;

if(!(fp=fopen(p,"rb")))
{
printf("打开文件失败！\n");
exit(0);
}
return(fp);
}

FILE *write_file1(char *p)//写入文件
{
FILE *fp;
if(!(fp=fopen(p,"wb")))
{
printf("打开文件失败！\n");
exit(0);
}
return(fp);
}
void InitHuffman1(NODE nodes[],int n)//霍夫曼树的初始化
{
int i;
for(i=0;i<2*n-1;i++)
{
nodes[i].weight=0;
nodes[i].parent=0;
nodes[i].flag=0;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}
}
void count_bytes1(FILE *input,NODE nodes[])//统计待压缩文件中每个字符出现的次数，求权重
{
int n;
nodes[256].weight=1;//对于结束符“\n”，假设其定义的权重为1
n=fgetc(input); //利用fgetc函数从待压缩文件中读入一个字符
while(n!=EOF)//End Of File,带压缩文件也已经读取完毕
{
nodes[n].weight++;//当文件中有相同的字符时权重自动+1
n=fgetc(input);
}
fseek(input,0,0);//使用文件指针定位函数fseek()，使原始文件指针重新回到文件头
}
void scale_counts1(NODE nodes[])/*将权重进行同比例缩小，然后重新赋给nodes[i].weight*/
{
double MAX_weight,less_any_weight,a;
int i;
MAX_weight=nodes[0].weight;
for(i=1;i<=256;i++)//找到结点中权重最大的赋给MAX_weight
{
if(nodes[i].weight>MAX_weight)
{
MAX_weight=nodes[i].weight;
}
}
a=floor(MAX_weight/256)+1;//floor向下取整，例：floor（2.8）=2
for(i=0;i<=256;i++)
{
if(nodes[i].weight!=0)
{
less_any_weight=floor(nodes[i].weight/a);//缩小后的权重赋给less_any_weight
if(less_any_weight==0)//将为出现的字符的权重less_any_weight设为1
nodes[i].weight=less_any_weight+1;
else
nodes[i].weight=less_any_weight;
}
}
}
void output_counts1(FILE *output,NODE nodes[])//把权重写入以压缩文件，使编码和解码霍夫曼树一致
{
int a,i;
for(i=0;i<=256;i++)
{
a=(int)nodes[i].weight;
fputc(a,output);//利用fputc函数把权重写入以压缩文件
}
}
int build_tree1(NODE nodes[])//构建霍夫曼树
{
double q1,q2;
int i,j,m1,m2;

for(i=1;i<=257;i++)
{
for(j=0;j<513;j++)/*从0结点开始找出第一个权重不为0和标志不为1的结点对min1，m1赋值*/
if(nodes[j].weight!=0&&nodes[j].flag==0)
{
m1=j;
q1=nodes[j].weight;
break;
}
for(j=1;m1+j<513;j++)/*找出权重最小并且标记不为1的结点，然后赋值给m1,q1*/
if(nodes[m1+j].weight!=0&&nodes[m1+j].flag==0)
if(q1>nodes[m1+j].weight)
{
m1=m1+j;
j=0;
}
nodes[m1].flag=1;//找到最小权重结点之后，将其标记变为0，为寻找次小结点做准备
for(j=0;j<513;j++)/*从0结点开始找出第一个权重不为0和标志不为1的结点对m2,q2赋值*/
if(nodes[j].weight!=0&&nodes[j].flag==0)
{
m2=j;
q2=nodes[j].weight;
break;
}
if(j==513)break;//当达到第513个结点是直接跳出循环

for(j=1;m2+j<513;j++)/*从0结点开始找出第一个权重不为0和标志不为1的结点对m2,m2赋值*/
if(nodes[m2+j].weight!=0&&nodes[m2+j].flag==0)
if(q2>nodes[m2+j].weight)
{
q2=nodes[m2+j].weight;
m2=m2+j;
j=0;
}
nodes[m2].flag=1;//将已经选出的结点的标志设为1
nodes[256+i].lchild=m1;//将m1,m2对应结点的权值求和后赋值给256+i的左右子树
nodes[256+i].rchild=m2;
nodes[256+i].weight=q1+q2;//并将m1,m2对应结点权值求和后赋值给256+i结点的权重
nodes[m1].parent=256+i;//将256+i的值赋给已经选出的两个结点的双亲结点
nodes[m2].parent=256+i;
}
return(m1);
}
void convert_tree_to_code1(CODE codes[],NODE nodes[])//对codes数组赋值，完成霍夫曼编码
{
int cod[256],i,j,k;
int child,parent;
k=j=0;
for(i=0;i<=256;i++)//利用for循环将对应的编码数组赋值
{
if(nodes[i].weight!=0)
{
child=i;
parent=nodes[child].parent;
while(parent!=0)
{
if(nodes[parent].lchild==child)
cod[j]=0;//若child是parent的左子树，则生成代码'0'
else
cod[j]=1;//若child是parent的右子树，则生成代码'1'
j++;
child=parent;
parent=nodes[child].parent;
}
codes[i].code_length=j;//计算每个结点的编码长度
for(k=0;j>0;k++)//逆序求出每个结点的编码
{
j--;
codes[i].code[k]=cod[j];
}
}
}
}
void printf_model1(NODE nodes[],CODE codes[])//输出各结点的编码
{
int i,j;
for(i=0;i<=256;i++)
{
if(nodes[i].weight!=0)
{
printf("ASCII 码: %d,\t\t权重是 %3d,\t\t",i,(int)nodes[i].weight);
printf("编码是: ");
for(j=0;j<codes[i].code_length;j++)
{
printf("%d",codes[i].code[j]);
}
printf("\n");
}
}
}
void OutputBits1(FILE *output,CODE codes,int *pbyte_length,unsigned char *pascii_code) /*将codes表示的编码写入output所指向的输出文件中*/
{
int i;
for(i=0;i<codes.code_length;i++)
{
*pascii_code+=codes.code[i]*2^(*pbyte_length-1);/*将每8位二进制数对应的十进制数赋给*pascii_code */
(*pbyte_length)--;

if(*pbyte_length==0)/*当*pbyte_length变为0时，把*pascii_code中的值写入输出文件，
然后将*pascii_code=0,*pbyte_length=8 */
{
fputc(*pascii_code,output);
*pascii_code=0;
*pbyte_length=8;
}

}
}

void compress_data1(FILE *input,FILE *output,CODE codes[])/*按字节一次读入待压缩文件字符，并按照codes 数组中的编码值，把每个字符的编码写入输出文件*/
{
int c;
int byte_length=8;
unsigned char ascii_code=0;
c=fgetc(input);//读入压缩文件的一个字符
while(c!=EOF)//判断是否达到压缩文件的末尾
{
OutputBits1(output,codes[c],&byte_length,&ascii_code);/*调用OutoutBits1函数，将待压缩文件中
的每个字节符号的编码写入输出文件*/
c=fgetc(input);
}
OutputBits1(output,codes[256],&byte_length,&ascii_code);
if(byte_length!=8)//检查是否还有余留位流
fputc(ascii_code,output);
}

void print_ratios1(FILE *input,FILE *output)//求压缩比
{
double k,i,j;
i=ftell(input);//求带压缩文件的大小
printf("\n\nThe length of inputfile is %f\n",i);
j=ftell(output);//求输出文件的大小
printf("The length of outputfile is %f\n",j);
k=i/j;//计算压缩比
printf("The compression ratios is %f\n",k);
fclose(input);
fclose(output);
}
int main(int argc, char* argv[])
{
printf("\n****************************************************************\n");
printf("\t\t\t霍夫曼编码");
printf("\n****************************************************************\n");
printf("待压缩文件为3.doc\n");
printf("压缩后文件为3.out\n");
FILE *input,*output; //输入和输出文件的指针

CODE codes[Max_number];//共257个字符，假设存在一个结束符，其ascii码为257
NODE nodes[2*Max_number-1]; // 共257个字符，所以存在2*257-1=513个结点
printf("\n Compressing %s to %s\n\n",argv[1],argv[2]);
input=read_file1(argv[1]);//打开原始文件，读文件
output=write_file1(argv[2]); //创建一个新文件，准备写入
InitHuffman1(nodes,Max_number);//初始化 dLL和exe两者都行

count_bytes1(input,nodes);//计算每个ascii码出现的次数，即求权重
scale_counts1(nodes); // dLL和exe两者都行，对权重进行伸缩，使最大权重max'不超过255，当然也可不进行伸缩，若不伸缩，则存储空间加大，而output_counts中的字符也要换成fwrite
output_counts1(output,nodes); //把每个字符的权值输出到输出文件中
build_tree1(nodes); // dLL和exe两者都行，构建huffman树build_tree(nodes); 返回根结点的位置，但压缩时无需返回根结点，还原程序需要返回值
convert_tree_to_code1(codes,nodes); // dLL和exe两者都行，把huffman树转化成二进制代码,即编码，左孩子（最小）编码为0，右孩子(次小)编码为1

if (argc>3&&strcmp(argv[3],"-d")==0) //argc>3必须要有，否则出错，没有第3个参数，就不能进行strcmp操作
printf_model1(nodes,codes); // dLL和exe两者都行，可选函数，该函数不是必须的，若有第3个参数"-d"，则打印输出编码模型

compress_data1(input,output,codes);//准备压缩文件，里面调用OutputBits函数
print_ratios1(input,output);//可选函数打印压缩比，注意文件指针要定位到末尾，并关闭文件
printf("compression finish\n");
return 0;
}