哈夫曼树编码以及译码

求一个哈夫曼树编码以及译码的小程序，26个字母以及权值已经给出，希望以此建立哈夫曼树。在由键盘输入字符串或者二进制数时可以根据此树进行编码或译码

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7517842
• 这篇博客你也可以参考下：哈夫曼编码实验报告
• 这篇博客也不错, 你可以看下哈夫曼编码实验报告

#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <bitset>

using namespace std;

struct Node
{
  char ch;
  int freq;
  Node *left, *right;

  Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}

  bool isLeaf()
  {
    return left == nullptr && right == nullptr;
  }
};

struct Compare
{
  bool operator()(Node *l, Node *r)
  {
    return l->freq > r->freq;
  }
};

void getFrequency(string inputFile, unordered_map<char, int> &freq)
{
  ifstream in(inputFile);
  char ch;
  while (in >> noskipws >> ch)
  {
    freq[ch]++;
  }
  in.close();
}

Node *buildHuffmanTree(unordered_map<char, int> &freq)
{
  priority_queue<Node *, vector<Node *>, Compare> heap;
  for (auto pair : freq)
  {
    heap.push(new Node(pair.first, pair.second));
  }
  while (heap.size() > 1)
  {
    Node *left = heap.top();
    heap.pop();
    Node *right = heap.top();
    heap.pop();
    Node *parent = new Node('\0', left->freq + right->freq);
    parent->left = left;
    parent->right = right;
    heap.push(parent);
  }
  return heap.top();
}

void generateCodes(Node *root, string str, unordered_map<char, string> &codes)
{
  if (root == nullptr)
  {
    return;
  }
  if (root->isLeaf())
  {
    codes[root->ch] = str;
  }
  generateCodes(root->left, str + "0", codes);
  generateCodes(root->right, str + "1", codes);
}

void compress(string inputFile, string outputFile, unordered_map<char, string> &codes)
{
  ifstream in(inputFile);
  ofstream out(outputFile, ios::binary);
  char ch;
  while (in >> noskipws >> ch)
  {
    string code = codes[ch];
    for (char bit : code)
    {
      out << bit;
    }
  }
  in.close();
  out.close();
}

void decompress(string inputFile, string outputFile, Node *root)
{
  ifstream in(inputFile, ios::binary);
  ofstream out(outputFile);
  Node *current = root;
  char ch;
  while (in >> ch)
  {
    if (ch == '0')
    {
      current = current->left;
    }
    else
    {
      current = current->right;
    }
    if (current->isLeaf())
    {
      out << current->ch;
      current = root;
    }
  }
  in.close();
  out.close();
}

int main()
{
  unordered_map<char, int> freq;
  getFrequency("input.txt", freq);
  Node *root = buildHuffmanTree(freq);
  unordered_map<char, string> codes;
  generateCodes(root, "", codes);
  compress("input.txt", "output.bin", codes);
  decompress("output.bin", "decompressed.txt", root);
  return 0;
}

首先使用 getFrequency 函数读取文件并统计每个字符的出现频率。然后使用 buildHuffmanTree 函数构建哈夫曼树。接下来，使用 generateCodes 函数生成哈夫曼编码。最后，使用 compress 和 decompress 函数进行压缩和解压缩。

你可以根据你的需要来修改这份代码，例如添加菜单选项。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define n 5 
#define m 2*n-1
#define MIN 100 
typedef struct 
{
   float weight;
   int lchild,rchild,parent;
}hfmtree;
hfmtree tree[m];
typedef struct
{
   char bits[n];
   int start;
   char ch;
}codetype;
codetype code[n];

void hfm(void)
{
   //int n = 5; 
   int i,j,p1,p2;
   float s1,s2,f;
   //m个节点初始化
   for(i = 0;i<m;i++){
       tree[i].parent = -1;
       tree[i].lchild = -1;
       tree[i].rchild = -1;
       tree[i].weight = 0;
   }
   //输入n个节点的权值
   printf("请输入n个权值，空格隔开回车结束\n");
   for(i = 0;i<n;i++){
       scanf("%f",&f);
       getchar();
       tree[i].weight = f;
   }
   //合并成m个节点
   for(i = n;i<m;i++){
       p1 = -1;    //小的下标
       p2 = -1;    //第二小的下标
       s1 = MIN;    //小的权值
       s2 = MIN+1;    //第二小的权值
       //找出前面的最小权值和第二小权值
       for(j =0;j<i;j++){
           if(tree[j].parent == -1){
               if(tree[j].weight<=s1){
               s2 = s1;
               s1 = tree[j].weight;
               p2 = p1;
               p1 = j;
               }
               else if(tree[j].weight<=s2){
               s2 = tree[j].weight;
               p2 = j;
               }
           }
       }
       tree[p1].parent = i;
       tree[p2].parent = i;
       tree[i].lchild = p1;
       tree[i].rchild = p2;
       tree[i].weight = tree[p1].weight+tree[p2].weight;
       tree[i].parent = -1;
   }
   for(i=0;i<n;i++)
       printf("第%d个的权值是%f\n",i,tree[i].weight);
}
void hfm_code(void)
{
   int i,j,p1,p2,k;
   char c;
   codetype ct;
   //输入对应的字符 
   printf("请输入对应的字符,空格隔开回车结束\n");
   for(i=0;i<n;i++){
       scanf("%c",&c);
       getchar();
       code[i].ch = c;
   } 
   //编码0或者1 
   for(i=0;i<n;i++){
       ct.start = n;
       p1 = tree[i].parent;
       p2 = i;
       //从叶子开始编码
       while(p1 != -1){
           //n个节点最多有n-1个编码 
           ct.start--;
           if(tree[p1].lchild==p2)
               ct.bits[ct.start] = '0';
           else if(tree[p1].rchild==p2)
               ct.bits[ct.start] = '1';
           p2 = p1;
           p1 = tree[p2].parent;    
       }
       //保存编码
       k = 0;
       for(j=ct.start;j<n;j++){
           code[i].bits[k] = ct.bits[j];
           k++;
       }
       code[i].start = ct.start;
   }
   //打印编码
   printf("编码表为\n");
   for (i=0; i<n; i++){
       printf ("%c 's HFM code is: ", code[i].ch);
       for (j=0;j<(n-code[i].start);j++){
           printf ("%c", code[i].bits[j]);
       }
       printf ("\n");
   }
   
   
} 
//解码 
void hfm_decode(char arr[]) 
{
   int i,j,k;
   char temp[n];
   k = 0;
   i = 0;
   //遍历输入的编码，从编码表查找。 
   while(arr[i]!='\0'){
       if(arr[i]=='\0')
           break;
       temp[k] = arr[i];
       k++;
       temp[k] = '\0';
       //从编码表中找出相应的字符 
       for(j=0;j<n;j++){
           if(!(strcmp(temp,code[j].bits))){
               k = 0;
               printf("%c",code[j].ch);
               break;
           }
       }
       if(k>n)
           printf("这串编码有问题，请重新检查！！\n"); 
       i++;
   }
   printf("\n"); 
}

int main()
{
   int i = 0;
   char c,arr[1024];
   hfm();
   hfm_code();
   //输入需要解码的一串码 
   printf("请输入一段编码序列,Ctrl+Z结束\n");
   while(scanf("%c",&c)!=EOF){
       arr[i] = c;
       i++;
   }
   arr[i-1] = '\0';
   hfm_decode(arr);
   
   return 0;
}