实现哈夫曼的编码和译码功能，采用C++编写

实现功能

• 以字符出现次数作为权值，构建哈夫曼树
• 哈夫曼编码以及译码处理
• 哈夫曼编码后统计压缩效率
• 从硬盘文件中读取一篇英文文章

功能部分

• 硬盘读取中读取文件

  string str;
  ifstream inFile("test.txt");    // fileName内容读取到file中 （按照实际情况修改)
  getline(inFile, str);
  

• 构建哈夫曼树

  //构建哈夫曼树
  void HuffmanTree(HNodeType HuffNode[MAXNODE], int arr[], int n){
  int i,j,z,p1,p2;          //p1,p2哈夫曼树过程中最小的两个权值数组的下标
  double min1,min2;       //哈夫曼树过程中最小的两个权值
  
  //初始化
  for(i=0; i<n; i++){
      HuffNode[i].weight = 0;
      HuffNode[i].parent = -1;
      HuffNode[i].lchild = -1;
      HuffNode[i].rchild = -1;
  }
  
  //输入n个叶子的权值
  z=0;
  for(i=0; i<256; i++){
      if(arr[i]!=0){
          HuffNode[z].value = (char)i;
          HuffNode[z].weight = arr[i];
          z++;
      }
  }
  
  //构建哈夫曼树
  for(i=0; i<n-1; i++){
      min1=min2=MAXVALUE;
      p1=p2=0;
      for (j=0; j<n+i; j++) {
          if (HuffNode[j].weight<min1 && HuffNode[j].parent==-1)
          {
              min2 = min1;
              p2 = p1;
              min1 = HuffNode[j].weight;
              p1 = j;
          }
          else if (HuffNode[j].weight < min2 && HuffNode[j].parent==-1)
          {
              min2=HuffNode[j].weight;
              p2=j;
          }
      }
      
      HuffNode[p1].parent  = n+i;
      HuffNode[p2].parent  = n+i;
      HuffNode[n+i].parent = -1;          //构建一个新根
      HuffNode[n+i].weight = min1+min2;
      HuffNode[n+i].lchild = p1;
      HuffNode[n+i].rchild = p2;
      cout << HuffNode[n+i].weight <<"\t" << HuffNode[p1].weight << "\t" << HuffNode[p2].weight <<endl;
  }
  }
  
  

• 哈夫曼编码

  //哈夫曼编码
  void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n){
  HCodeType temp;         //定义临时变量
  int i,j,c,p;
  for(i=0;i<n;i++)
  {
      temp.start=n-1;
      c=i;
      p=HuffNode[c].parent;
      while(p!=-1)
      {
          if(HuffNode[p].lchild==c)
              temp.bit[temp.start]=0;
          else
              temp.bit[temp.start]=1;
          temp.start--;
          c=p;
          p=HuffNode[c].parent;    // 循环
      }
      for (j=temp.start+1; j<n; j++)                      // 把叶子结点的编码信息从临时变量中复制出来，放入编码结构体数组
          HuffCode[i].bit[j]=temp.bit[j];
      HuffCode[i].start=temp.start;
  }
  
  //输出结果
  for(i=0;i<n;i++)
  {
      cout<<HuffNode[i].value<<": Huffman code is: ";
      for(j=HuffCode[i].start+1;j<n;j++)
          cout<<HuffCode[i].bit[j];
      cout<<endl;
  }
  }
  

• 哈夫曼译码

  //哈夫曼译码操作
  void HuffmandeCode(int count){
  string arr;
  cout << "请输入一串字符串" <<endl;
  int j = count*2 -2;
  getline(cin, arr);
  cout << "下面为译码的结果" <<endl;
  for (int i=0; i<arr.length(); i++) {
      if (arr[i] == '0') {
          j = HuffNode[j].lchild;
      }else if (arr[i] == '1'){
          j = HuffNode[j].rchild;
      }
      if (HuffNode[j].lchild == -1 && HuffNode[j].rchild == -1) {
          cout << HuffNode[j].value;
          j = count*2 -2;;
      }
  }
  cout <<endl;
  }
  

• 统计压缩效率

  //哈夫曼编码压缩(所有字符的)
  void HuffmanCodeAll(string arr,int n){
  cout << "下列输出所有文字的Huffman code: " << endl;
  int arrcount = arr.length();                        //原文章的字符总数
  int codecount = 0 ;                                     //编码后的所有总数
  for(int i=0; i<arr.length(); i++){
      for (int j=0; j<n; j++) {
          if ( tolower(arr[i]) == HuffNode[j].value) {
              for(int z=HuffCode[j].start+1;z < n; z++){
                  cout<<HuffCode[j].bit[z];
                  codecount++;
              }
          }
      }
  }
  cout << endl;
  cout << "压缩的效率为：" <<endl;
  codecount = codecount / 8;                                              //计算编码后的字符串总数
  if( codecount%8 != 0 ){                                                 //除不完情况下，加一处理
      codecount++;
  }
  printf("%.2lf%%\n",(double)(arrcount-codecount)/arrcount*100);          //输出压缩百分比
  }
  

完整代码哈夫曼，欢迎star