本文实例讲述了基于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++实现哈夫曼树简单创建与遍历的方法
- 解析C++哈夫曼树编码和译码的实现
- C++数据结构之文件压缩（哈夫曼树）实例详解
- C++ 哈夫曼树对文件压缩、加密实现代码
- C++数据结构与算法之哈夫曼树的实现方法
- 哈夫曼的c语言实现代码
