当前位置:主页 > c/c++教程 > C++哈夫曼编码解码

基于C++实现的哈夫曼编码解码操作示例

发布:2022-10-09 08:51:39 59


我们帮大家精选了C++相关的编程文章,网友充宏大根据主题投稿了本篇教程内容,涉及到C++、哈夫曼、编码、解码、C++哈夫曼编码解码相关内容,已被245网友关注,如果对知识点想更进一步了解可以在下方电子资料中获取。

C++哈夫曼编码解码

本文实例讲述了基于C++实现的哈夫曼编码解码操作。分享给大家供大家参考,具体如下:

哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符:‘0'与‘1'表示。编码的实现过程很简单,只要实现哈夫曼树,通过遍历哈夫曼树,这里我们从每一个叶子结点开始向上遍历,如果该结点为父节点的左孩子,则在字符串后面追加“0”,如果为其右孩子,则在字符串后追加“1”。结束条件为没有父节点。然后将字符串倒过来存入结点中。

C++实现代码如下:

#include<iostream>
#include<string>
using namespace std;
struct Node
{
  double weight;
  string ch;
  string code;
  int lchild, rchild, parent;
};
void Select(Node huffTree[], int *a, int *b, int n)//找权值最小的两个a和b
{
  int i;
  double weight = 0; //找最小的数
  for (i = 0; i <n; i++)
  {
    if (huffTree[i].parent != -1)   //判断节点是否已经选过
      continue;
    else
    {
      if (weight == 0)
      {
        weight = huffTree[i].weight;
        *a = i;
      }
      else
      {
        if (huffTree[i].weight < weight)
        {
          weight = huffTree[i].weight;
          *a = i;
        }
      }
    }
  }
  weight = 0; //找第二小的数
  for (i = 0; i < n; i++)
  {
    if (huffTree[i].parent != -1 || (i == *a))//排除已选过的数
      continue;
    else
    {
      if (weight == 0)
      {
        weight = huffTree[i].weight;
        *b = i;
      }
      else
      {
        if (huffTree[i].weight < weight)
        {
          weight = huffTree[i].weight;
          *b = i;
        }
      }
    }
  }
  int temp;
  if (huffTree[*a].lchild < huffTree[*b].lchild) //小的数放左边
  {
    temp = *a;
    *a = *b;
    *b = temp;
  }
}
void Huff_Tree(Node huffTree[], int w[], string ch[], int n)
{
  for (int i = 0; i < 2 * n - 1; i++) //初始过程
  {
    huffTree[i].parent = -1;
    huffTree[i].lchild = -1;
    huffTree[i].rchild = -1;
    huffTree[i].code = "";
  }
  for (int i = 0; i < n; i++)
  {
    huffTree[i].weight = w[i];
    huffTree[i].ch = ch[i];
  }
  for (int k = n; k < 2 * n - 1; k++)
  {
    int i1 = 0;
    int i2 = 0;
    Select(huffTree, &i1, &i2, k); //将i1,i2节点合成节点k
    huffTree[i1].parent = k;
    huffTree[i2].parent = k;
    huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
    huffTree[k].lchild = i1;
    huffTree[k].rchild = i2;
  }
}
void Huff_Code(Node huffTree[], int n)
{
  int i, j, k;
  string s = "";
  for (i = 0; i < n; i++)
  {
    s = "";
    j = i;
    while (huffTree[j].parent != -1) //从叶子往上找到根节点
    {
      k = huffTree[j].parent;
      if (j == huffTree[k].lchild) //如果是根的左孩子,则记为0
      {
        s = s + "0";
      }
      else
      {
        s = s + "1";
      }
      j = huffTree[j].parent;
    }
    cout << "字符 " << huffTree[i].ch << " 的编码:";
    for (int l = s.size() - 1; l >= 0; l--)
    {
      cout << s[l];
      huffTree[i].code += s[l]; //保存编码
    }
    cout << endl;
  }
}
string Huff_Decode(Node huffTree[], int n,string s)
{
  cout << "解码后为:";
  string temp = "",str="";//保存解码后的字符串
  for (int i = 0; i < s.size(); i++)
  {
    temp = temp + s[i];
    for (int j = 0; j < n; j++)
    {
      if (temp == huffTree[j].code)
      {
        str=str+ huffTree[j].ch;
        temp = "";
        break;
      }
      else if (i == s.size()-1&&j==n-1&&temp!="")//全部遍历后没有
      {
        str= "解码错误!";
      }
    }
  }
  return str;
}
int main()
{
  //编码过程
  const int n=5;
  Node huffTree[2 * n];
  string str[] = { "A", "B", "C", "D", "E"};
  int w[] = { 30, 30, 5, 20, 15 };
  Huff_Tree(huffTree, w, str, n);
  Huff_Code(huffTree, n);
  //解码过程
  string s;
  cout << "输入编码:";
  cin >> s;
  cout << Huff_Decode(huffTree, n, s)<< endl;;
  system("pause");
  return 0;
}

运行结果如下:

希望本文所述对大家C++程序设计有所帮助。


参考资料

相关文章

  • 浅谈C++函数声明后面加throw()的作用(必看)

    发布:2022-04-14

    下面小编就为大家带来一篇浅谈C++函数声明后面加throw()的作用(必看)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧


  • C语言实现C++继承和多态的实例内容

    发布:2021-06-10

    本文主要给大家简单讲诉了C和C++的区别以及如何使用C语言模拟实现C++继承和多态,并附上示例代码,是篇相当不错的文章,推荐给喜欢C语言的小伙伴们


  • 用C/C++代码检测ip能否ping通(配合awk和system可以做到批量检测)

    发布:2022-04-21

    今天小编就为大家分享一篇关于用C/C++代码检测ip能否ping通(配合awk和system可以做到批量检测),小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧


  • C/C++指针和取地址的方法

    发布:2022-04-01

    C/C++指针和取地址的方法,需要的朋友可以参考一下


  • C++实现优酷土豆去视频广告的方法

    发布:2022-09-06

    给网友们整理关于C++的教程,这篇文章主要介绍了C++实现优酷土豆去视频广告的方法,实例分析了C++实现屏蔽功能的相关技巧,需要的朋友可以参考下


  • 深入解析C++中类的多重继承

    发布:2022-09-14

    给网友朋友们带来一篇关于C++的教程,这篇文章主要介绍了深入解析C++中类的多重继承,包括多重继承相关的二义性问题,需要的朋友可以参考下


  • VC++中进程与多进程管理的方法详解

    发布:2021-05-28

    这篇文章主要介绍了VC++中进程与多进程管理的方法,以实例形式详细分析了进程与多进程管理中所涉及的进程、子进程、进程的互斥运行与进程的结束等概念与具体实现方法,非常具有参考借鉴价值,需要的朋友可以参考下


  • C++实现会员管理程序的具体方案

    发布:2021-06-01

    这篇文章主要为大家详细介绍了C++实现会员管理程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下


网友讨论