怎么基于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++实现的哈夫曼编码解码操作”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。