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 codeMax_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;i2*n-1;i+) nodesi.weight=0; nodesi.parent=0; nodesi.flag=0; nodesi.lchild=-1; nodesi.rchild=-1;void count_bytes1(FILE *input,NODE nodes)/统计待压缩文件中每个字符出现的次数，求权重int n;nodes256.weight=1;/对于结束符“n”，假设其定义的权重为1n=fgetc(input); /利用fgetc函数从待压缩文件中读入一个字符while(n!=EOF)/End Of File,带压缩文件也已经读取完毕 nodesn.weight+;/当文件中有相同的字符时权重自动+1n=fgetc(input);fseek(input,0,0);/使用文件指针定位函数fseek()，使原始文件指针重新回到文件头void scale_counts1(NODE nodes)/*将权重进行同比例缩小，然后重新赋给nodesi.weight*/double MAX_weight,less_any_weight,a;int i;MAX_weight=nodes0.weight;for(i=1;iMAX_weight)MAX_weight=nodesi.weight;a=floor(MAX_weight/256)+1;/floor向下取整，例：floor（2.8）=2for(i=0;i=256;i+)if(nodesi.weight!=0)less_any_weight=floor(nodesi.weight/a);/缩小后的权重赋给less_any_weightif(less_any_weight=0)/将为出现的字符的权重less_any_weight设为1nodesi.weight=less_any_weight+1;elsenodesi.weight=less_any_weight;void output_counts1(FILE *output,NODE nodes)/把权重写入以压缩文件，使编码和解码霍夫曼树一致int a,i;for(i=0;i=256;i+)a=(int)nodesi.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;j513;j+)/*从0结点开始找出第一个权重不为0和标志不为1的结点对min1，m1赋值*/if(nodesj.weight!=0&nodesj.flag=0)m1=j;q1=nodesj.weight;break;for(j=1;m1+jnodesm1+j.weight)m1=m1+j;j=0;nodesm1.flag=1;/找到最小权重结点之后，将其标记变为0，为寻找次小结点做准备for(j=0;j513;j+)/*从0结点开始找出第一个权重不为0和标志不为1的结点对m2,q2赋值*/if(nodesj.weight!=0&nodesj.flag=0)m2=j;q2=nodesj.weight;break;if(j=513)break;/当达到第513个结点是直接跳出循环for(j=1;m2+jnodesm2+j.weight)q2=nodesm2+j.weight;m2=m2+j;j=0;nodesm2.flag=1;/将已经选出的结点的标志设为1nodes256+i.lchild=m1;/将m1,m2对应结点的权值求和后赋值给256+i的左右子树nodes256+i.rchild=m2;nodes256+i.weight=q1+q2;/并将m1,m2对应结点权值求和后赋值给256+i结点的权重nodesm1.parent=256+i;/将256+i的值赋给已经选出的两个结点的双亲结点nodesm2.parent=256+i;return(m1);void convert_tree_to_code1(CODE codes,NODE nodes)/对codes数组赋值，完成霍夫曼编码int cod256,i,j,k;int child,parent;k=j=0;for(i=0;i0;k+)/逆序求出每个结点的编码j-;codesi.codek=codj;void printf_model1(NODE nodes,CODE codes)/输出各结点的编码int i,j;for(i=0;i=256;i+)if(nodesi.weight!=0)printf(ASCII 码: %d,tt权重是 %3d,tt,i,(int)nodesi.weight);printf(编码是: );for(j=0;jcodesi.code_length;j+)printf(%d,codesi.codej);printf(n); void OutputBits1(FILE *output,CODE codes,int *pbyte_length,unsigned char *pascii_code) /*将codes表示的编码写入output所指向的输出文件中*/int i;for(i=0;i3&strcmp(argv3,-d)=0) /argc3必须要有，否则出错，没有第3个参数，就不能进行strcmp操作printf_model1(nodes,codes); / dLL和exe两者都行，可选函数，该函数不是必须的，若有第3个参数-d，则打