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(打開文件失?。);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)計待壓縮文件中每個字符出現(xiàn)的次數，求權重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)/將為出現(xiàn)的字符的權重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;/找到最小權重結點之后，將其標記變?yōu)?，為尋找次小結點做準備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個結點是直接跳出循環(huán)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，則打