C++ 哈弗曼编码的实现与反编码

Wesley13
• 阅读 566 
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;

typedef struct{
     int weight;
     int parent,lchild,rchild;
     int asc;
}HTNode,*HuffmanTree;    //定义赫夫曼存储结构

struct node{
      int ASCII;
      int n;
};
struct node a[127];
struct node w[127];    
//一些全局变量
int count;
HTNode H_T[250];
char ** HC;
char filename[20];

//函数声明
void menu1();     //菜单1
HuffmanTree HeapSort(HuffmanTree HT,int length);    //堆排序
void MinHeapify(HuffmanTree HT, int k,int len);     //调整成一个小顶堆
void buildMinHeap(HuffmanTree HT,int len);          //建一个小顶堆
void swap(HTNode &t1,HTNode &t2);                   //交换两结构体
void savefile();                            //把输入的英文文章保存到文件
void loadfile();                           //从文件中读取文章
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n);    //建立赫夫曼数并存入文件
void BianMa(HuffmanTree HT,int n );                                  //字符编码
void BianMa_all(HuffmanTree HT,char**HC,char *filename);             //整篇文章编码
int loadfile2();                                         //从文件读入文章
void JieMa();                                            //解码



//主函数
void main()
{    
    char s;
    while(s!='0')
    {
                system("cls");
                cout<<"/n/n/n";
                cout<<"/t/t/t/t赫夫曼编码/译码器"<<endl<<endl<<endl<<endl<<endl;
                cout<<"/t/t/t/t  1.编码"<<endl<<endl<<endl<<endl;
                cout<<"/t/t/t/t  2.译码"<<endl<<endl<<endl<<endl;
                cout<<"/t/t/t/t  0.退出"<<endl<<endl<<endl<<endl;
                cout<<"/t请输入0—2进行选择，按回车确认";
                cin>>s;
                switch(s)
                {
                 case '1':  menu1(); break;
                 case '2':
                  { 
                      system("cls"); 
                      JieMa();
                      system("pause");
                      break;
                  }
        
                }
        
    }
}
    
    
    
    

//菜单1    
void menu1(){
    char s;
    int i;
    int a;
    char c;
    char fpname[20]="article.txt";
    HuffmanTree HT;
while(s!='0'){
 
          system("cls");
          cout<<"/n/t/t/t/t编码界面";
          cout<<"/n/n/n/t/t/t/t1.输入英文文章"<<endl;
          cout<<"/n/n/t/t/t/t2.从文件中读入文章"<<endl;
          cout<<"/n/n/t/t/t/t0.返回上一层"<<endl;
          cout<<"/n/t请输入0—2进行选择，按回车确认";
          cin>>s;
  switch(s){
          case'1': 
             system("cls");
             savefile();
             loadfile();
             CreateHuffman(HT,w,count);
             BianMa(HT,count);
             BianMa_all(HT,HC,fpname);
             system("cls");
             cout<<"出现字符种类共计：";
             cout<<count<<endl;
             for(i=1;i<=count;i++)
             { a=HT[i].asc;
               c=(char)a;
               
               
               cout<<"________________________________________________________________________________"<<endl;
               cout<<"/t/t/t字符：";
               cout<<c<<endl;
               cout<<"/t/t/tASCII码：";
               cout<<a<<endl;
               cout<<"/t/t/t频数：";
               cout<<HT[i].weight<<endl;
               cout<<"/t/t/t赫夫曼编码：";
               cout<<HC[i]<<endl;
               
             
             
             }
             cout<<"________________________________________________________________________________";
             cout<<"/n/t/t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl;
             
             system("pause");
             break;
    
    case'2': 
             system("cls");
             if(loadfile2())
             { system("pause");
             return;}
             CreateHuffman(HT,w,count);
             BianMa(HT,count);
             BianMa_all(HT,HC,filename);
             system("cls");
             cout<<"出现字符种类共计：";
             cout<<count<<endl;
             for(i=1;i<=count;i++)
             { a=HT[i].asc;
               c=(char)a;
               
               
               cout<<"________________________________________________________________________________"<<endl;
               cout<<"/t/t/t字符：";
               cout<<c<<endl;
               cout<<"/t/t/tASCII码：";
               cout<<a<<endl;
               cout<<"/t/t/t频数：";
               cout<<HT[i].weight<<endl;
               cout<<"/t/t/t赫夫曼编码：";
               cout<<HC[i]<<endl;
               
             
             
             }
             cout<<"________________________________________________________________________________";
             cout<<"/n/t/t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl;
             system("pause");
             break;
         }

}
    
}
    




//交换结构体
void swap(HTNode &t1,HTNode &t2)
{
   HTNode m;
   
    m = t1;
    t1 = t2;
    t2 = m;
 }
    

//从键盘输入文章并保存
void savefile(){
    
    FILE *fp;
    char article;
    if((fp=fopen("article.txt","w"))==NULL){

        printf("打开文件不成功！");
        exit(0);
     }
    cout<<"请输入英文文章,以#结束:";
    getchar();
    article=getchar();
    while(article!='#'){
    
        fputc(article,fp);
                    
        article=getchar();
    }
   fclose(fp);
}



//从文件读取文章，并统计字符出现频数
void loadfile(){
     

    FILE *fp;
    char ch;
    int i,k,j=0;
    count=0;
    for(i=0;i<=127;i++)   //把所有字符的ascii码存在数组
    { a[i].ASCII=i;
      a[i].n=0;
      
    }
 if((fp=fopen("article.txt","r"))==NULL){
    
      printf("打开文件不成功！");
      exit(0);
    }
       ch=fgetc(fp);
       k=(int)ch;
       a[k].n++;
      while(!feof(fp)){
          ch=fgetc(fp);
          k=(int)ch;
          a[k].n++;
       }
      fclose(fp);
    
     for(i=0;i<=127;i++)      //统计字符种类总数
     {
        ch=(char)i;
        if(a[i].n){
         count++;
        }
     }
     for(i=0;i<=127;i++)
     {  
         for(;j<count;)
         {
             if(a[i].n)
             {
                w[j].n=a[i].n;
                w[j].ASCII=a[i].ASCII;
                j++;
                break;
             }
              else break;
         }
      }
     
}



//调整为小顶堆
void MinHeapify(HuffmanTree HT, int k,int len)   
{
    int left=k*2;
    int right=k*2+1;
    int large;
    int l=len;
    
    large = k;
    if (left<=l&&HT[left].weight<HT[large].weight)
        large = left;

    if (right<=l&& HT[right].weight<HT[large].weight)
        large=right;
    
    if (large!=k)
    {
        swap(HT[k],HT[large]);
        MinHeapify(HT,large,l);
    }
}


//建立小顶堆
void buildMinHeap(HuffmanTree HT,int len)  
{
    int i;
    for (i=len/2;i>=1;i--)
    {
        MinHeapify(HT,i,len);
    }
}


//堆排序
HuffmanTree HeapSort(HuffmanTree HT,int length)
{
    int i;
    int l=length;
    buildMinHeap(HT,length);
    for (i=length;i>= 2;i--)
    {
        swap(HT[1],HT[i]);
        length--;
        MinHeapify(HT,1,length);
    }
    
    
    return HT;
}


   
//建立赫夫曼数
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n)
{
    int i,m,s1,s2,k1,k2,j,x,a;
    FILE *fp,*fp2;
    
    
    if(n<=1) return HT;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用
  
    for(i=1,j=0;i<=n;i++,j++)
    {   HT[i].asc=w[j].ASCII;
        HT[i].weight=w[j].n;
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(;i<=m;i++)
    { a=250+i;
      HT[i].asc=a;//父亲节点的asc可以是大于127的任意值
      HT[i].weight=0;
      HT[i].parent=0;
      HT[i].lchild=0;
      HT[i].rchild=0;
    }
    for(i=1;i<=n;i++){
    
       H_T[i].asc=HT[i].asc;
       H_T[i].parent=HT[i].parent;
       H_T[i].lchild=HT[i].lchild;
       H_T[i].rchild=HT[i].rchild;
       H_T[i].weight=HT[i].weight;
    }
      
    for(i=n+1,x=n;i<=m;i++,x--)
    {  
     
        HeapSort(H_T,x);
        k1=H_T[x].asc;
        k2=H_T[x-1].asc;
       for(j=1;j<=127;j++)
       {
           if(HT[j].asc==k1)
           { s1=j;break;}
       
       }
        
       for(j=1;j<=127;j++)
       {  
          if(HT[j].asc==k2)
          {    s2=j;break;}
       
       
       }
        
       HT[s2].parent=i;
       HT[s1].parent=i;
       HT[i].lchild=s1;
       HT[i].rchild=s2;
       HT[i].weight=HT[s1].weight+HT[s2].weight;

       H_T[x-1].asc=HT[i].asc;
       H_T[x-1].lchild=HT[i].lchild;
       H_T[x-1].parent=HT[i].parent;
       H_T[x-1].rchild=HT[i].rchild;
       H_T[x-1].weight=HT[i].weight;
       
    }
   if((fp2=fopen("count.txt","w"))==NULL)        //保存赫夫曼树
   {   
       cout<<"文件打开不成功！"<<endl;
        exit(0);
   }
       fputc(count,fp2);
   if((fp=fopen("HuffmanTree.dat","wb"))==NULL)
   {  cout<<"文件打开不成功！"<<endl;
      exit(0);
   
   }
     
   for(i=1;i<=(2*count-1);i++){
     fwrite(&HT[i],sizeof(HTNode),1,fp);
   }
   fclose(fp);
   fclose(fp2);
  return HT;

}
       
      


//逆向编码
void BianMa(HuffmanTree HT,int n){
   char *cd,temp;
   
   int c,f,i,j,len,p,q;
     
   cd=(char *)malloc(n*sizeof(char));
   HC=(char * *)malloc(n*sizeof(char*));
   for(i=1;i<=n;i++){
     for(c=i,f=HT[i].parent,j=0;f!=0;c=f,f=HT[f].parent,j++)
     {     if(HT[f].lchild==c) cd[j]='0';
         else cd[j]='1';
         if(HT[f].parent==0)
            cd[j+1]='/0';
          
     }
     
     
     len=strlen(cd);
     for(p=0,q=len-1;p<=q;p++,q--)
     {
         temp=cd[q];
         cd[q]=cd[p];
         cd[p]=temp;
     }
     cd[len]='/0';
     HC[i]=(char*)malloc((len+10)*sizeof(char));
     strcpy(HC[i],cd);

   } 
   
   

}





//整篇文章编码，并存入文件
void BianMa_all(HuffmanTree HT,char**HC,char *filename){
      char ch;
      int k,i;
      FILE *fp,*fp2;
      
     char code[100];
  if((fp=fopen(filename,"r"))==NULL){

        printf("打开文件不成功！");
        exit(0);
     }
 if((fp2=fopen("赫夫曼编码.txt","w"))==NULL){

        printf("打开文件不成功！");
        exit(0);
     }
     ch=fgetc(fp);
     k=(int)ch;
     while(!feof(fp))
    {
         
      for(i=1;i<=count;i++)
      {
         if(k==HT[i].asc)
         strcpy(code,HC[i]);
         
      }  
        fputs(code,fp2);
        ch=fgetc(fp);
         k=(int)ch;
     
     }
    fclose(fp);
    fclose(fp2);

    

}

void JieMa(){
     int i,k,a,t,n=0;
     FILE *fp1,*fp2,*fp3;
     char ch,c;
     HuffmanTree ht;
     if((fp3=fopen("count.txt","r"))==NULL)     //从文件读出字符总数
     {    
        printf("打开文件不成功！");
        exit(0);
     }
       n=fgetc(fp3);
     ht=(HuffmanTree)malloc(2*n*sizeof(HTNode));
    if((fp1=fopen("赫夫曼编码.txt","r"))==NULL)
    {

        printf("打开文件不成功！");
        exit(0);
    }

  if((fp2=fopen("HuffmanTree.dat","rb"))==NULL)
   {  cout<<"文件打开不成功！"<<endl;
      exit(0);
   
   }
for(i=1;i<=2*n-1;i++)

  fread(&ht[i],sizeof(HTNode),1,fp2);
  

  for(i=1;i<=2*n-1;i++)
  {
    if(ht[i].parent==0){t=k=i;break;}
  }       
 
 ch=fgetc(fp1);
 while(!feof(fp1)){
     if(ch=='0')
     {
       k=ht[k].lchild;
       if(ht[k].lchild==0)
       {a=ht[k].asc;
        c=(char)a;
        printf("%c",c);;
        
        k=t;
       }
     }
    if(ch=='1')
    {
     k=ht[k].rchild;
     if(ht[k].lchild==0)
     {  a=ht[k].asc;
        c=(char)a;
        printf("%c",c);
        
        k=t;
     }
     
    }

 
   ch=fgetc(fp1);
 }
  fclose(fp1);
  fclose(fp2);

}




//读取文件中的文章，可自己选择文件
int loadfile2(){
     
    
    FILE *fp;
    char ch;
    int i,k,j=0;
    count=0;
    for(i=0;i<=127;i++)
    { a[i].ASCII=i;
      a[i].n=0;
      
    }
    cout<<"/n/n/n/t/t/t请输入你要打开的文件名：";
    cin>>filename;
   if((fp=fopen(filename,"r"))==NULL){
    
      printf("打开文件不成功！");
      return 1;
    }
       ch=fgetc(fp);
       k=(int)ch;
       a[k].n++;
      while(!feof(fp)){
          ch=fgetc(fp);
          k=(int)ch;
          a[k].n++;
       }
      fclose(fp);
    
     for(i=0;i<=127;i++){
        ch=(char)i;
        if(a[i].n){
         count++;
        }
    }
     for(i=0;i<=127;i++)
     {  
         for(;j<count;)
         {
             if(a[i].n)
             {
                w[j].n=a[i].n;
                w[j].ASCII=a[i].ASCII;
                j++;
                break;
             }
              else break;
         }
      }
     return 0;
}
C/C++
点赞
收藏
评论区
推荐文章
blmius blmius
•
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时，报错：原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等，这样可以更容易地在不同的环境中使用MySQL。全局s
3723
0
0
helloworld_34035044 helloworld_34035044
•
2年前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时，如何在新增行里自动增加id呢？能新增整数排序id吗？目前可以在新增行里自动增加id，但只能用uuid函数增加UUID编码，不能新增整数排序id。uuid函数说明：获取一个UUID，可以在填报表中用来创建数据ID语法：uuid()或uuid(sep)参数说明：sep布尔值，生成的uuid中是否包含分隔符''，缺省为
887
0
0
Wesley13 Wesley13
•
2年前
java 哈夫曼编码反编码的实现
//哈弗曼编码的实现类publicclassHffmanCoding{privateintcharsAndWeight;//0是字符，1存放的是字符的权值（次数）privateinthfmcoding;//存放哈弗曼树privateinti0;
577
0
0
Stella981 Stella981
•
2年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数：59593
1677
0
0
Stella981 Stella981
•
2年前
C# Aspose.Cells导出xlsx格式Excel，打开文件报“Excel 已完成文件级验证和修复。此工作簿的某些部分可能已被修复或丢弃”
报错信息：最近打开下载的Excel，会报如下错误。（xls格式不受影响）!(https://oscimg.oschina.net/oscnet/2b6f0c8d7f97368d095d9f0c96bcb36d410.png)!(https://oscimg.oschina.net/oscnet/fe1a8000d00cec3c
1233
0
0
Stella981 Stella981
•
2年前
Linux查看GPU信息和使用情况
1、Linux查看显卡信息：lspci|grepivga2、使用nvidiaGPU可以：lspci|grepinvidia!(https://oscimg.oschina.net/oscnet/36e7c7382fa9fe49068e7e5f8825bc67a17.png)前边的序号"00:0f.0"是显卡的代
1375
0
0
Stella981 Stella981
•
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签，将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
1147
0
0
Easter79 Easter79
•
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移
982
0
0
Stella981 Stella981
•
2年前
Nginx反向代理upstream模块介绍
!(https://oscimg.oschina.net/oscnet/1e67c46e359a4d6c8f36b590a372961f.gif)!(https://oscimg.oschina.net/oscnet/819eda5e7de54c23b54b04cfc00d3206.jpg)1.Nginx反
734
0
0
Stella981 Stella981
•
2年前
C语言实现的基于Huffman哈夫曼编码的数据压缩与解压缩
实验目的了解文件的概念掌握线性链表的插入、删除等算法掌握Huffman树的概念及构造方法掌握二叉树的存储结构及遍历算法利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理参考博文和源码下载地址：https://writebug.com/article/1281.html(https://www
474
0
0
Wesley13
Wesley13
Lv1
最大的安心是自律温柔和爱自己。
文章
1.2w
粉丝
19
获赞
1.7k
热门文章
JavPlayer：AI破坏马赛克，大量马赛克破坏版影片流出
8个在线接收手机短信验证码的免费网络服务整理
2020年最新可用的磁力搜索引擎&种子搜索网站，持续整理分享
IDM 激活破解工具
java.net.ConnectException：Connection timed out：connect 出现连接超时的问题？