Welcome 微信登录
编程资源 图片资源库 蚂蚁家优选 PDF转换器 软件资源

软件开发、小程序制作、系统集成与运维、空间租用、硬件开发、视频监控、技术咨询与支持——联系电话：0311-88999002/88999003

首页 / 操作系统 / Linux / 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. }  
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图