huffman解碼.doc

#include stdio.h#include stdlib.h /exit#include math.h /pow,floor函數(shù)#include string.h /strcmp函數(shù)#define END_OF_STREAM 256 /最后結(jié)束符為257#define Max_code_length 256 /共257個(gè)字符，可能的最長(zhǎng)代碼二進(jìn)制位數(shù)為256個(gè)，假設(shè)第257個(gè)字符為結(jié)束符#define Max_number 257 /加上結(jié)束符，共257個(gè)字typedef struct tree_node double weight; /權(quán)重,把權(quán)重寫入輸出文件時(shí)，int flag; /標(biāo)識(shí)是否為待構(gòu)建結(jié)點(diǎn)，是的話用0表示，否則用1表示int parent; /父結(jié)點(diǎn)int lchild; /左結(jié)點(diǎn)int rchild; /右結(jié)點(diǎn)NODE;typedef struct codetype int codeMax_code_length; /共257個(gè)字符，可能的最長(zhǎng)代碼二進(jìn)制位數(shù)為256個(gè)，假設(shè)第257個(gè)字符為結(jié)束符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(打開文件失?。);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)/統(tǒng)計(jì)待壓縮文件中每個(gè)字符出現(xiàn)的次數(shù)，求權(quán)重int n;nodes256.weight=1;/對(duì)于結(jié)束符“n”，假設(shè)其定義的權(quán)重為1n=fgetc(input); /利用fgetc函數(shù)從待壓縮文件中讀入一個(gè)字符while(n!=EOF)/End Of File,帶壓縮文件也已經(jīng)讀取完畢 nodesn.weight+;/當(dāng)文件中有相同的字符時(shí)權(quán)重自動(dòng)+1n=fgetc(input);fseek(input,0,0);/使用文件指針定位函數(shù)fseek()，使原始文件指針重新回到文件頭void scale_counts1(NODE nodes)/*將權(quán)重進(jìn)行同比例縮小，然后重新賦給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);/縮小后的權(quán)重賦給less_any_weightif(less_any_weight=0)/將為出現(xiàn)的字符的權(quán)重less_any_weight設(shè)為1nodesi.weight=less_any_weight+1;elsenodesi.weight=less_any_weight;void output_counts1(FILE *output,NODE nodes)/把權(quán)重寫入以壓縮文件，使編碼和解碼霍夫曼樹一致int a,i;for(i=0;i=256;i+)a=(int)nodesi.weight;fputc(a,output);/利用fputc函數(shù)把權(quán)重寫入以壓縮文件int build_tree1(NODE nodes)/構(gòu)建霍夫曼樹double q1,q2;int i,j,m1,m2;for(i=1;i=257;i+)for(j=0;j513;j+)/*從0結(jié)點(diǎn)開始找出第一個(gè)權(quán)重不為0和標(biāo)志不為1的結(jié)點(diǎn)對(duì)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;/找到最小權(quán)重結(jié)點(diǎn)之后，將其標(biāo)記變?yōu)?，為尋找次小結(jié)點(diǎn)做準(zhǔn)備for(j=0;j513;j+)/*從0結(jié)點(diǎn)開始找出第一個(gè)權(quán)重不為0和標(biāo)志不為1的結(jié)點(diǎn)對(duì)m2,q2賦值*/if(nodesj.weight!=0&nodesj.flag=0)m2=j;q2=nodesj.weight;break;if(j=513)break;/當(dāng)達(dá)到第513個(gè)結(jié)點(diǎn)是直接跳出循環(huán)for(j=1;m2+jnodesm2+j.weight)q2=nodesm2+j.weight;m2=m2+j;j=0;nodesm2.flag=1;/將已經(jīng)選出的結(jié)點(diǎn)的標(biāo)志設(shè)為1nodes256+i.lchild=m1;/將m1,m2對(duì)應(yīng)結(jié)點(diǎn)的權(quán)值求和后賦值給256+i的左右子樹nodes256+i.rchild=m2;nodes256+i.weight=q1+q2;/并將m1,m2對(duì)應(yīng)結(jié)點(diǎn)權(quán)值求和后賦值給256+i結(jié)點(diǎn)的權(quán)重nodesm1.parent=256+i;/將256+i的值賦給已經(jīng)選出的兩個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)nodesm2.parent=256+i;return(m1);void convert_tree_to_code1(CODE codes,NODE nodes)/對(duì)codes數(shù)組賦值，完成霍夫曼編碼int cod256,i,j,k;int child,parent;k=j=0;for(i=0;i0;k+)/逆序求出每個(gè)結(jié)點(diǎn)的編碼j-;codesi.codek=codj;void printf_model1(NODE nodes,CODE codes)/輸出各結(jié)點(diǎn)的編碼int i,j;for(i=0;i=256;i+)if(nodesi.weight!=0)printf(ASCII 碼: %d,tt權(quán)重是 %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必須要有，否則出錯(cuò)，沒有第3個(gè)參數(shù)，就不能進(jìn)行strcmp操作printf_model1(nodes,codes); / dLL和exe兩者都行，可選函數(shù)，該函數(shù)不是必須的，若有第3個(gè)參數(shù)-d，則打