huffman算法编写的压缩软件程序源代码

转自：http://blog.csdn.net/gubojun123/article/details/8286156  点击打开链接

1. /** 
2.  * author:gubojun 
3.  * time:2012-12-11 
4.  * name:~ 
5.  * version:0.1 
6.  */  
7. #include<stdio.h>  
8. #include<stdlib.h>  
9. #include<string.h>  
10. /** 
11.  * Huffman树的结构体 
12.  */  
13. typedef struct node{  
14.     char byte;//记录字符  
15.     int weight;//权值  
16.     char bit[10];//编码值  
17.     struct node *lchild,*rchild,*next;  
18. }hufnode,*huflink;  
19. huflink codetree;  
20. //--------------------编码对照表  
21. char codelist[256][10];int nn;  
22. //---------------------------------------------------------------------------------  
23. /** 
24.  * name:comp 
25.  * author:gubojun 
26.  * time:2012-12-11 
27.  * in:两个节点的地址 
28.  * out:int 大小 
29.  * function:qsort比较函数，降序排列结构体数组 
30.  */  
31. int comp(const void *a,const void *b){  
32.     return (*(huflink)b).weight-(*(huflink)a).weight;  
33. }  
34. //---------------------------------------------------------------------------------  
35. /** 
36.  * 函数功能：将新结点s插入到有序链表root中，并保持链表的有序性 
37.  * 函数参数：链表头结点指针root；结点指针s 
38.  */  
39. huflink insert(huflink root,huflink s){  
40.     huflink p1,p2;  
41.     if(root==NULL)root=s;  
42.     else{  
43.         p1=NULL;  
44.         p2=root;  
45.         while(p2 && p2->weight < s->weight){/*查找插入位置*/  
46.             p1=p2;  
47.             p2=p2->next;  
48.         }  
49.         s->next=p2;  
50.         if(p1==NULL) root=s;  
51.         else p1->next=s;  
52.     }  
53.     return root;  
54. }  
55. //---------------------------------------------------------------------------------  
56. /** 
57.  * 函数功能：根据有序链表root建立huffman树 
58.  * 函数参数：链表头结点二级指针变量root 
59.  */  
60. void creathuffman(huflink *root){//二阶指针(地址的指针)  
61.     huflink s,rl,rr;  
62.     while(*root && (*root)->next){//*root表示一个地址  
63.         rl=*root;  
64.         rr=(*root)->next;  
65.         *root=rr->next;  
66.         s=(huflink)malloc(sizeof(hufnode));/*生成新结点*/  
67.         s->next=NULL;  
68.         s->weight=rl->weight+rr->weight;  
69.         s->lchild=rl;  
70.         s->rchild=rr;  
71.         rl->next=rr->next=NULL;  
72.         s->bit[0]='\0';  
73.         *root=insert(*root,s);/*将新结点插入到有序表root中*/  
74.     }  
75. }  
76. void inorder(huflink t){    /*中序遍历二叉树*/  
77.     if(t){  
78.         inorder(t->lchild);  
79.         printf("%4d",t->weight);  
80.         inorder(t->rchild);  
81.     }  
82. }  
83. void preorder(huflink t){   /*前序遍历二叉树*/  
84.     if(t){  
85.         printf("%4d",t->weight);  
86.         preorder(t->lchild);  
87.         preorder(t->rchild);  
88.     }  
89. }  
90. void levelorder(huflink t){ //层次遍历二叉树  
91.     huflink queue[256];     //存放等待访问的节点队列  
92.     int f,r,i=0;            //f,r分别为对头、队尾指针  
93.     int length;  
94.     huflink p;  
95.     f=0;r=1;queue[0]=t;  
96.     while(f<r){             //队列不为空  
97.         p=queue[f];f++;  
98.         if(p->lchild==NULL && p->rchild==NULL){  
99.             printf("%c",p->byte);  
100.             strcpy(codelist[p->byte],p->bit);  
101.             printf("(%5s)  ",codelist[p->byte]);  
102.         }  
103.         if(p->lchild){  
104.             queue[r]=p->lchild;  
105.             strcpy((p->lchild)->bit,p->bit);  
106.             strcat((p->lchild)->bit,"0");  
107.             r++;  
108.         }  
109.         if(p->rchild){  
110.             queue[r]=p->rchild;  
111.             strcpy((p->rchild)->bit,p->bit);  
112.             strcat((p->rchild)->bit,"1");  
113.             r++;  
114.         }  
115.     }  
116. }  
117. //---------------------------------------------------------------------------------  
118. /** 
119.  * name:compress 
120.  * author:gubojun 
121.  * time:2012-12-11 
122.  * in:char[],char[],输入的文件名，输出的文件名 
123.  * out:none 
124.  */  
125. void compress(char infilename[],char outfilename[]){  
126.     long flength=0;         //记录压缩前文件长度  
127.     char ch,bin[10];        //存储读入的字符  
128.     huflink s,p;  
129.     hufnode list[256];  
130.     int i,j,word,count;  
131.     FILE *f_in,*f_out;  
132.     //----------------------判断文件是否打开成功  
133.     if((f_in=fopen(infilename,"r"))==NULL){  
134.         printf("Failure to open %s\n",infilename);  
135.         return;  
136.     }  
137.     //----------------------初始化数组  
138.     for(i=0;i<256;i++){  
139.         list[i].byte=i;     //初始化字符  
140.         list[i].weight=0;   //初始化权重  
141.     }  
142.     //----------------------统计权值大小  
143.     while((ch=fgetc(f_in))!=EOF){  
144.         list[ch].weight++;  //权值加1  
145.         putchar(ch);        //输出字符  
146.         flength++;          //长度加1  
147.     }  
148.     nn=flength;  
149.     //----------------------关闭文件  
150.     fclose(f_in);  
151.     //----------------------结构体数组快排  
152.     qsort(list,256,sizeof(hufnode),comp);  
153.   
154.     printf("\nlength:%d\n\n",flength);           //输入后换行  
155.   
156.     //----------------------建立Huffman编码树  
157.     codetree=(huflink)malloc(sizeof(hufnode));  
158.     codetree->byte=list[0].byte;//初始化字符  
159.     codetree->weight=list[0].weight;//初始化权重  
160.     codetree->lchild=codetree->rchild=codetree->next=NULL;  
161.     codetree->bit[0]='\0';  
162.     i=0;  
163.     while(list[++i].weight){//当权重不为0时  
164.         s=(huflink)malloc(sizeof(hufnode));  
165.         s->byte=list[i].byte;  
166.         s->weight=list[i].weight;  
167.         s->lchild=s->rchild=NULL;//左右孩子节点赋值为0  
168.         s->bit[0]='\0';  
169.         s->next=codetree;  
170.         codetree=s;  
171.     }  
172.     //----------------------打印权值和字符  
173.     p=codetree;  
174.     while(p){  
175.         printf("%d (%c)   ",p->weight,p->byte);  
176.         p=p->next;  
177.     }  
178.     printf("\n");  
179.     //----------------------建立编码树  
180.     creathuffman(&codetree);  
181.     //----------------------根据编码树编码  
182.     //----------------------层次遍历编码树填写编码对照表  
183.     levelorder(codetree);  
184.     //----------------------判断文件是否打开成功  
185.     if((f_in=fopen(infilename,"r"))==NULL){  
186.         printf("Failure to open %s\n",infilename);  
187.         return;  
188.     }  
189.   
190.     //----------------------判断文件是否打开成功  
191.     if((f_out=fopen(outfilename,"w"))==NULL){  
192.         printf("Failure to open %s\n",outfilename);  
193.         return;  
194.     }  
195.     /*//---------------------写入编码1 
196.     while((ch=fgetc(f_in))!=EOF){ 
197.         fprintf(f_out,"%s",codelist[ch]); 
198.     } 
199.     fclose(f_in);fclose(f_out);*/  
200.   
201.     printf("\n");  
202.     //----------------------写入编码  
203.     count=i=word=bin[0]=0;  
204.     while((ch=fgetc(f_in))!=EOF){  
205.         count+=strlen(codelist[ch]);  
206.         j=i;  
207.         while(i<count&&i<8){  
208.             word=word+((codelist[ch][i-j]-48)<<(7-i));  
209.             i++;  
210.         }  
211.         if(i==8){  
212.             if(count==8){  
213.                 count-=8;i=0;  
214.                 fprintf(f_out,"%c",word);  
215.                 printf("%d\n",word);  
216.                 word=0;  
217.             }  
218.             else{  
219.                 count-=8;i=0;  
220.                 fprintf(f_out,"%c",word);  
221.                 printf("%d\n",word);  
222.                 while(i<count&&i<8){  
223.                     word=(codelist[ch][i]-48)<<(7-i);  
224.                     i++;  
225.                 }  
226.             }  
227.         }  
228.         //fprintf(f_out,"%s",codelist[ch]);  
229.     }  
230.     if(i!=8){  
231.         fprintf(f_out,"%c",word);  
232.         printf("%d\n",word);  
233.     }  
234.     fclose(f_in);fclose(f_out);  
235. }  
236. //---------------------------------------------------------------------------------  
237. /** 
238.  * name:uncompress 
239.  * author:gubojun 
240.  * time:2012-12-11 
241.  * in:char[],char[],输入的文件名，输出的文件名 
242.  * out:none 
243.  */  
244. void uncompress(char infilename[],char outfilename[]){  
245.     FILE *f_in,*f_out;  
246.     char ch;//存储读入的字符  
247.     huflink s,p;  
248.     int i;  
249.     //-----------------------判断文件是否打开成功  
250.     if((f_in=fopen(infilename,"r"))==NULL){  
251.         printf("Failure to open %s\n",infilename);  
252.         return;  
253.     }  
254.     //-----------------------判断文件是否打开成功  
255.     if((f_out=fopen(outfilename,"w"))==NULL){  
256.         printf("Failure to open %s\n",outfilename);  
257.         return;  
258.     }  
259.     /*//------------------------读入编码1 
260.     p=codetree; 
261.     while((ch=fgetc(f_in))!=EOF){ 
262.         if(ch=='0'){ 
263.             p=p->lchild; 
264.         } 
265.         else{ 
266.             p=p->rchild; 
267.         } 
268.         if(p->lchild==NULL && p->rchild==NULL){ 
269.             fprintf(f_out,"%c",p->byte); 
270.             p=codetree; 
271.         } 
272.     }*/  
273.     //------------------------读入编码  
274.     printf("\n");  
275.     p=codetree;  
276.     while(fscanf(f_in,"%c",&ch)!=EOF){  
277.         for(i=7;i>=0&&nn;i--){  
278.             if(((ch>>i)&1)==0){  
279.                 p=p->lchild;  
280.             }  
281.             else{  
282.                 p=p->rchild;  
283.             }  
284.             if(p->lchild==NULL && p->rchild==NULL){  
285.                 printf("%c",p->byte);  
286.                 fprintf(f_out,"%c",p->byte);  
287.                 p=codetree;  
288.                 //nn--;  
289.             }  
290.         }  
291.     }  
292.     fclose(f_in);fclose(f_out);  
293. }  
294. /************************************************************************ 
295.  * name:main 
296.  * author:gubojun 
297.  * time:2012-12-11 
298.  * in:none 
299.  * out:none 
300.  * function:程序的主函数 
301.  ************************************************************************/  
302. int main(){  
303.     char infilename[256]="in.txt",outfilename[256]="out.txt";  
304.     int choice=1;  
305.     //printf("please input filename:");  
306.     //scanf("%d",infilename);  
307.     //printf("please input filename:");  
308.     //scanf("%d",outfilename);  
309.     printf("1.compress  2uncompress:\n");  
310.     //scanf("%d",&choice);  
311.     switch(choice){  
312.         case 1:compress(infilename,outfilename);  
313.         //break;  
314.         case 2:uncompress(outfilename,"解压后.txt");  
315.         break;  
316.     }  
317. } 
318. 
     

     源码下载地址：http://download.csdn.net/detail/gubojun123/4876722