基于C++实现的哈夫曼编码解码操作示例
作者:雨中枫玲 时间:2023-10-13 13:02:43
本文实例讲述了基于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
标签:C++,哈夫曼
0
投稿
猜你喜欢
Maven项目读取resources文件路径问题解决方案
2023-04-21 15:05:11
关于idea引入spring boot <parent></parent>父依赖标红问题
2021-11-23 09:42:12
java处理图片背景颜色的方法
2023-11-27 04:38:20
一文搞懂JMeter engine中HashTree的配置问题
2022-05-11 01:21:08
Java文本文件操作方法实例详解
2021-12-14 10:03:21
深入浅析hbase的优点
2021-08-06 19:27:58
Spring Boot 2结合Spring security + JWT实现微信小程序登录
2022-07-14 08:25:54
Java AQS信号量Semaphore的使用
2021-06-11 17:10:44
Android开发中Button组件的使用
2021-07-08 07:18:13
C#中Dictionary泛型集合7种常见的用法
2021-08-07 04:47:17
详解Android开发中Fragment的使用
2023-05-02 20:32:25
C# 操作XML文档 使用XmlDocument类方法
2023-06-11 04:21:14
Java8时间接口LocalDateTime详细用法
2023-11-25 09:56:49
java数据类型与二进制详细介绍
2021-07-28 19:04:38
c#实现metro文件压缩解压示例
2022-07-07 22:36:33
Java C++题解leetcode904水果成篮
2023-12-08 21:06:09
Android性能优化之plt hook与native线程监控详解
2021-09-10 22:06:01
C++版本基于ros将文件夹中的图像转换为bag包
2021-11-13 07:15:59
Android 8.0升级不跳转应用安装页面的解决方法
2022-03-20 03:30:13
Java判断字符串是否是整数或者浮点数的方法
2022-04-30 10:06:20