C++ 哈弗曼編碼的實現與反編碼

C++ 哈弗曼編碼的實現與反編碼

1. #include<iostream>   
2. #include<stdlib.h>   
3. #include<string.h>   
4. using namespace std;  
5.   
6. typedef struct{  
7.      int weight;  
8.      int parent,lchild,rchild;  
9.      int asc;  
10. }HTNode,*HuffmanTree;    //定義赫夫曼存儲結構   
11.   
12. struct node{  
13.       int ASCII;  
14.       int n;  
15. };  
16. struct node a[127];  
17. struct node w[127];      
18. //一些全局變量   
19. int count;  
20. HTNode H_T[250];  
21. char ** HC;  
22. char filename[20];  
23.   
24. //函數聲明   
25. void menu1();     //菜單1   
26. HuffmanTree HeapSort(HuffmanTree HT,int length);    //堆排序   
27. void MinHeapify(HuffmanTree HT, int k,int len);     //調整成一個小頂堆   
28. void buildMinHeap(HuffmanTree HT,int len);          //建一個小頂堆   
29. void swap(HTNode &t1,HTNode &t2);                   //交換兩結構體   
30. void savefile();                            //把輸入的英文文章保存到文件   
31. void loadfile();                           //從文件中讀取文章   
32. HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n);    //建立赫夫曼數並存入文件   
33. void BianMa(HuffmanTree HT,int n );                                  //字符編碼   
34. void BianMa_all(HuffmanTree HT,char**HC,char *filename);             //整篇文章編碼   
35. int loadfile2();                                         //從文件讀入文章   
36. void JieMa();                                            //解碼   
37.   
38.   
39.   
40. //主函數   
41. void main()  
42. {      
43.     char s;  
44.     while(s!='0')  
45.     {  
46.                 system("cls");  
47.                 cout<<"/n/n/n";  
48.                 cout<<"/t/t/t/t赫夫曼編碼/譯碼器"<<endl<<endl<<endl<<endl<<endl;  
49.                 cout<<"/t/t/t/t  1.編碼"<<endl<<endl<<endl<<endl;  
50.                 cout<<"/t/t/t/t  2.譯碼"<<endl<<endl<<endl<<endl;  
51.                 cout<<"/t/t/t/t  0.退出"<<endl<<endl<<endl<<endl;  
52.                 cout<<"/t請輸入0—2進行選擇，按回車確認";  
53.                 cin>>s;  
54.                 switch(s)  
55.                 {  
56.                  case '1':  menu1(); break;  
57.                  case '2':  
58.                   {   
59.                       system("cls");   
60.                       JieMa();  
61.                       system("pause");  
62.                       break;  
63.                   }  
64.           
65.                 }  
66.           
67.     }  
68. }  
69.       
70.       
71.       
72.       
73.   
74. //菜單1      
75. void menu1(){  
76.     char s;  
77.     int i;  
78.     int a;  
79.     char c;  
80.     char fpname[20]="article.txt";  
81.     HuffmanTree HT;  
82. while(s!='0'){  
83.    
84.           system("cls");  
85.           cout<<"/n/t/t/t/t編碼界面";  
86.           cout<<"/n/n/n/t/t/t/t1.輸入英文文章"<<endl;  
87.           cout<<"/n/n/t/t/t/t2.從文件中讀入文章"<<endl;  
88.           cout<<"/n/n/t/t/t/t0.返回上一層"<<endl;  
89.           cout<<"/n/t請輸入0—2進行選擇，按回車確認";  
90.           cin>>s;  
91.   switch(s){  
92.           case'1':   
93.              system("cls");  
94.              savefile();  
95.              loadfile();  
96.              CreateHuffman(HT,w,count);  
97.              BianMa(HT,count);  
98.              BianMa_all(HT,HC,fpname);  
99.              system("cls");  
100.              cout<<"出現字符種類共計：";  
101.              cout<<count<<endl;  
102.              for(i=1;i<=count;i++)  
103.              { a=HT[i].asc;  
104.                c=(char)a;  
105.                  
106.                  
107.                cout<<"________________________________________________________________________________"<<endl;  
108.                cout<<"/t/t/t字符：";  
109.                cout<<c<<endl;  
110.                cout<<"/t/t/tASCII碼：";  
111.                cout<<a<<endl;  
112.                cout<<"/t/t/t頻數：";  
113.                cout<<HT[i].weight<<endl;  
114.                cout<<"/t/t/t赫夫曼編碼：";  
115.                cout<<HC[i]<<endl;  
116.                  
117.                
118.                
119.              }  
120.              cout<<"________________________________________________________________________________";  
121.              cout<<"/n/t/t整篇文章的編碼已存入文件“赫夫曼編碼.txt”"<<endl;  
122.                
123.              system("pause");  
124.              break;  
125.       
126.     case'2':   
127.              system("cls");  
128.              if(loadfile2())  
129.              { system("pause");  
130.              return;}  
131.              CreateHuffman(HT,w,count);  
132.              BianMa(HT,count);  
133.              BianMa_all(HT,HC,filename);  
134.              system("cls");  
135.              cout<<"出現字符種類共計：";  
136.              cout<<count<<endl;  
137.              for(i=1;i<=count;i++)  
138.              { a=HT[i].asc;  
139.                c=(char)a;  
140.                  
141.                  
142.                cout<<"________________________________________________________________________________"<<endl;  
143.                cout<<"/t/t/t字符：";  
144.                cout<<c<<endl;  
145.                cout<<"/t/t/tASCII碼：";  
146.                cout<<a<<endl;  
147.                cout<<"/t/t/t頻數：";  
148.                cout<<HT[i].weight<<endl;  
149.                cout<<"/t/t/t赫夫曼編碼：";  
150.                cout<<HC[i]<<endl;  
151.                  
152.                
153.                
154.              }  
155.              cout<<"________________________________________________________________________________";  
156.              cout<<"/n/t/t整篇文章的編碼已存入文件“赫夫曼編碼.txt”"<<endl;  
157.              system("pause");  
158.              break;  
159.          }  
160.   
161. }  
162.       
163. }  
164.       
165.   
166.   
167.   
168.   
169. //交換結構體   
170. void swap(HTNode &t1,HTNode &t2)  
171. {  
172.    HTNode m;  
173.      
174.     m = t1;  
175.     t1 = t2;  
176.     t2 = m;  
177.  }  
178.       
179.   
180. //從鍵盤輸入文章並保存   
181. void savefile(){  
182.       
183.     FILE *fp;  
184.     char article;  
185.     if((fp=fopen("article.txt","w"))==NULL){  
186.   
187.         printf("打開文件不成功！");  
188.         exit(0);  
189.      }  
190.     cout<<"請輸入英文文章,以#結束:";  
191.     getchar();  
192.     article=getchar();  
193.     while(article!='#'){  
194.       
195.         fputc(article,fp);  
196.                       
197.         article=getchar();  
198.     }  
199.    fclose(fp);  
200. }  
201.   
202.   
203.   
204. //從文件讀取文章，並統計字符出現頻數   
205. void loadfile(){  
206.        
207.   
208.     FILE *fp;  
209.     char ch;  
210.     int i,k,j=0;  
211.     count=0;  
212.     for(i=0;i<=127;i++)   //把所有字符的ascii碼存在數組   
213.     { a[i].ASCII=i;  
214.       a[i].n=0;  
215.         
216.     }  
217.  if((fp=fopen("article.txt","r"))==NULL){  
218.       
219.       printf("打開文件不成功！");  
220.       exit(0);  
221.     }  
222.        ch=fgetc(fp);  
223.        k=(int)ch;  
224.        a[k].n++;  
225.       while(!feof(fp)){  
226.           ch=fgetc(fp);  
227.           k=(int)ch;  
228.           a[k].n++;  
229.        }  
230.       fclose(fp);  
231.       
232.      for(i=0;i<=127;i++)      //統計字符種類總數   
233.      {  
234.         ch=(char)i;  
235.         if(a[i].n){  
236.          count++;  
237.         }  
238.      }  
239.      for(i=0;i<=127;i++)  
240.      {    
241.          for(;j<count;)  
242.          {  
243.              if(a[i].n)  
244.              {  
245.                 w[j].n=a[i].n;  
246.                 w[j].ASCII=a[i].ASCII;  
247.                 j++;  
248.                 break;  
249.              }  
250.               else break;  
251.          }  
252.       }  
253.        
254. }  
255.   
256.   
257.   
258. //調整為小頂堆   
259. void MinHeapify(HuffmanTree HT, int k,int len)     
260. {  
261.     int left=k*2;  
262.     int right=k*2+1;  
263.     int large;  
264.     int l=len;  
265.       
266.     large = k;  
267.     if (left<=l&&HT[left].weight<HT[large].weight)  
268.         large = left;  
269.   
270.     if (right<=l&& HT[right].weight<HT[large].weight)  
271.         large=right;  
272.       
273.     if (large!=k)  
274.     {  
275.         swap(HT[k],HT[large]);  
276.         MinHeapify(HT,large,l);  
277.     }  
278. }  
279.   
280.   
281. //建立小頂堆   
282. void buildMinHeap(HuffmanTree HT,int len)    
283. {  
284.     int i;  
285.     for (i=len/2;i>=1;i--)  
286.     {  
287.         MinHeapify(HT,i,len);  
288.     }  
289. }  
290.   
291.   
292. //堆排序   
293. HuffmanTree HeapSort(HuffmanTree HT,int length)  
294. {  
295.     int i;  
296.     int l=length;  
297.     buildMinHeap(HT,length);  
298.     for (i=length;i>= 2;i--)  
299.     {  
300.         swap(HT[1],HT[i]);  
301.         length--;  
302.         MinHeapify(HT,1,length);  
303.     }  
304.       
305.       
306.     return HT;  
307. }  
308.   
309.   
310.      
311. //建立赫夫曼數   
312. HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n)  
313. {  
314.     int i,m,s1,s2,k1,k2,j,x,a;  
315.     FILE *fp,*fp2;  
316.       
317.       
318.     if(n<=1) return HT;  
319.     m=2*n-1;  
320.     HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用   
321.     
322.     for(i=1,j=0;i<=n;i++,j++)  
323.     {   HT[i].asc=w[j].ASCII;  
324.         HT[i].weight=w[j].n;  
325.         HT[i].parent=0;  
326.         HT[i].lchild=0;  
327.         HT[i].rchild=0;  
328.     }  
329.     for(;i<=m;i++)  
330.     { a=250+i;  
331.       HT[i].asc=a;//父親節點的asc可以是大於127的任意值   
332.       HT[i].weight=0;  
333.       HT[i].parent=0;  
334.       HT[i].lchild=0;  
335.       HT[i].rchild=0;  
336.     }  
337.     for(i=1;i<=n;i++){  
338.       
339.        H_T[i].asc=HT[i].asc;  
340.        H_T[i].parent=HT[i].parent;  
341.        H_T[i].lchild=HT[i].lchild;  
342.        H_T[i].rchild=HT[i].rchild;  
343.        H_T[i].weight=HT[i].weight;  
344.     }  
345.         
346.     for(i=n+1,x=n;i<=m;i++,x--)  
347.     {    
348.        
349.         HeapSort(H_T,x);  
350.         k1=H_T[x].asc;  
351.         k2=H_T[x-1].asc;  
352.        for(j=1;j<=127;j++)  
353.        {  
354.            if(HT[j].asc==k1)  
355.            { s1=j;break;}  
356.          
357.        }  
358.           
359.        for(j=1;j<=127;j++)  
360.        {    
361.           if(HT[j].asc==k2)  
362.           { s2=j;break;}  
363.          
364.          
365.        }  
366.           
367.        HT[s2].parent=i;  
368.        HT[s1].parent=i;  
369.        HT[i].lchild=s1;  
370.        HT[i].rchild=s2;  
371.        HT[i].weight=HT[s1].weight+HT[s2].weight;  
372.   
373.        H_T[x-1].asc=HT[i].asc;  
374.        H_T[x-1].lchild=HT[i].lchild;  
375.        H_T[x-1].parent=HT[i].parent;  
376.        H_T[x-1].rchild=HT[i].rchild;  
377.        H_T[x-1].weight=HT[i].weight;  
378.          
379.     }  
380.    if((fp2=fopen("count.txt","w"))==NULL)        //保存赫夫曼樹   
381.    {     
382.        cout<<"文件打開不成功！"<<endl;  
383.         exit(0);  
384.    }  
385.        fputc(count,fp2);  
386.    if((fp=fopen("HuffmanTree.dat","wb"))==NULL)  
387.    {  cout<<"文件打開不成功！"<<endl;  
388.       exit(0);  
389.      
390.    }  
391.        
392.    for(i=1;i<=(2*count-1);i++){  
393.      fwrite(&HT[i],sizeof(HTNode),1,fp);  
394.    }  
395.    fclose(fp);  
396.    fclose(fp2);  
397.   return HT;  
398.   
399. }  
400.          
401.         
402.   
403.   
404. //逆向編碼   
405. void BianMa(HuffmanTree HT,int n){  
406.    char *cd,temp;  
407.      
408.    int c,f,i,j,len,p,q;  
409.        
410.    cd=(char *)malloc(n*sizeof(char));  
411.    HC=(char * *)malloc(n*sizeof(char*));  
412.    for(i=1;i<=n;i++){  
413.      for(c=i,f=HT[i].parent,j=0;f!=0;c=f,f=HT[f].parent,j++)  
414.      {   if(HT[f].lchild==c) cd[j]='0';  
415.          else cd[j]='1';  
416.          if(HT[f].parent==0)  
417.             cd[j+1]='/0';  
418.             
419.      }  
420.        
421.        
422.      len=strlen(cd);  
423.      for(p=0,q=len-1;p<=q;p++,q--)  
424.      {  
425.          temp=cd[q];  
426.          cd[q]=cd[p];  
427.          cd[p]=temp;  
428.      }  
429.      cd[len]='/0';  
430.      HC[i]=(char*)malloc((len+10)*sizeof(char));  
431.      strcpy(HC[i],cd);  
432.   
433.    }   
434.      
435.      
436.   
437. }  
438.   
439.   
440.   
441.   
442.   
443. //整篇文章編碼，並存入文件   
444. void BianMa_all(HuffmanTree HT,char**HC,char *filename){  
445.       char ch;  
446.       int k,i;  
447.       FILE *fp,*fp2;  
448.         
449.      char code[100];  
450.   if((fp=fopen(filename,"r"))==NULL){  
451.   
452.         printf("打開文件不成功！");  
453.         exit(0);  
454.      }  
455.  if((fp2=fopen("赫夫曼編碼.txt","w"))==NULL){  
456.   
457.         printf("打開文件不成功！");  
458.         exit(0);  
459.      }  
460.      ch=fgetc(fp);  
461.      k=(int)ch;  
462.      while(!feof(fp))  
463.     {  
464.            
465.       for(i=1;i<=count;i++)  
466.       {  
467.          if(k==HT[i].asc)  
468.          strcpy(code,HC[i]);  
469.            
470.       }    
471.         fputs(code,fp2);  
472.         ch=fgetc(fp);  
473.          k=(int)ch;  
474.        
475.      }  
476.     fclose(fp);  
477.     fclose(fp2);  
478.   
479.       
480.   
481. }  
482.   
483. void JieMa(){  
484.      int i,k,a,t,n=0;  
485.      FILE *fp1,*fp2,*fp3;  
486.      char ch,c;  
487.      HuffmanTree ht;  
488.      if((fp3=fopen("count.txt","r"))==NULL)     //從文件讀出字符總數   
489.      {      
490.         printf("打開文件不成功！");  
491.         exit(0);  
492.      }  
493.        n=fgetc(fp3);  
494.      ht=(HuffmanTree)malloc(2*n*sizeof(HTNode));  
495.     if((fp1=fopen("赫夫曼編碼.txt","r"))==NULL)  
496.     {  
497.   
498.         printf("打開文件不成功！");  
499.         exit(0);  
500.     }  
501.   
502.   if((fp2=fopen("HuffmanTree.dat","rb"))==NULL)  
503.    {  cout<<"文件打開不成功！"<<endl;  
504.       exit(0);  
505.      
506.    }  
507. for(i=1;i<=2*n-1;i++)  
508.   
509.   fread(&ht[i],sizeof(HTNode),1,fp2);  
510.     
511.   
512.   for(i=1;i<=2*n-1;i++)  
513.   {  
514.     if(ht[i].parent==0){t=k=i;break;}  
515.   }         
516.    
517.  ch=fgetc(fp1);  
518.  while(!feof(fp1)){  
519.      if(ch=='0')  
520.      {  
521.        k=ht[k].lchild;  
522.        if(ht[k].lchild==0)  
523.        {a=ht[k].asc;  
524.         c=(char)a;  
525.         printf("%c",c);;  
526.           
527.         k=t;  
528.        }  
529.      }  
530.     if(ch=='1')  
531.     {  
532.      k=ht[k].rchild;  
533.      if(ht[k].lchild==0)  
534.      {  a=ht[k].asc;  
535.         c=(char)a;  
536.         printf("%c",c);  
537.           
538.         k=t;  
539.      }  
540.        
541.     }  
542.   
543.    
544.    ch=fgetc(fp1);  
545.  }  
546.   fclose(fp1);  
547.   fclose(fp2);  
548.   
549. }  
550.   
551.   
552.   
553.   
554. //讀取文件中的文章，可自己選擇文件   
555. int loadfile2(){  
556.        
557.       
558.     FILE *fp;  
559.     char ch;  
560.     int i,k,j=0;  
561.     count=0;  
562.     for(i=0;i<=127;i++)  
563.     { a[i].ASCII=i;  
564.       a[i].n=0;  
565.         
566.     }  
567.     cout<<"/n/n/n/t/t/t請輸入你要打開的文件名：";  
568.     cin>>filename;  
569.    if((fp=fopen(filename,"r"))==NULL){  
570.       
571.       printf("打開文件不成功！");  
572.       return 1;  
573.     }  
574.        ch=fgetc(fp);  
575.        k=(int)ch;  
576.        a[k].n++;  
577.       while(!feof(fp)){  
578.           ch=fgetc(fp);  
579.           k=(int)ch;  
580.           a[k].n++;  
581.        }  
582.       fclose(fp);  
583.       
584.      for(i=0;i<=127;i++){  
585.         ch=(char)i;  
586.         if(a[i].n){  
587.          count++;  
588.         }  
589.     }  
590.      for(i=0;i<=127;i++)  
591.      {    
592.          for(;j<count;)  
593.          {  
594.              if(a[i].n)  
595.              {  
596.                 w[j].n=a[i].n;  
597.                 w[j].ASCII=a[i].ASCII;  
598.                 j++;  
599.                 break;  
600.              }  
601.               else break;  
602.          }  
603.       }  
604.      return 0;  
605. }