基于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++程序设计有所帮助。

来源：https://www.cnblogs.com/gyk666/p/6851821.html