c++数据结构哈夫曼编码问题
发布网友
发布时间：2022-04-25 16:58
共1个回答
热心网友
时间：2023-10-20 22:00
#include<iostream>
#include<cstring>
using namespace std;
const char ch[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',
'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
const double w[] = { 8.19, 1.47, 3.83, 3.91, 12.25, 2.26, 1.71, 4.57, 7.10,
0.14, 0.41, 3.77, 3.34, 7.06, 7.26, 2.89, 0.09, 6.85, 6.36, 9.41, 2.58,
1.09, 1.59, 0.21, 1.58, 0.08 }; //百分比%
const int n = sizeof(w) / sizeof(w[0]);
const double MAX = 10000;
struct element {
double weight; // 字符出现的概率为实数
int lchild, rchild, parent;
};
void HuffmanCode(element huffTree[], int n) {
for (int i = 0; i < n; i++) {
string strc="";
int j = i,t=0; //暂存i,不破坏循环变量
while (huffTree[j].parent != 0) {
if (huffTree[huffTree[j].parent].lchild == j)
strc = '1'+strc;
else
strc = '0'+strc;
j = huffTree[j].parent;
t++;
}
cout << ch[i] << ":"+strc;
for(t=12-t;t>0;t--)cout<<" ";
if(i%6==5)cout<<endl;
}
}
void Select(element huffTree[], int& i1, int& i2) {
double MIN1 = MAX, MIN2 = MAX;
for (int i = 0; i < 2 * n - 1; i++) {
if ((huffTree[i].parent == 0) && (huffTree[i].weight != 0)) {
if ((huffTree[i].weight < MIN1) || (huffTree[i].weight < MIN2)) {
if (MIN1 < MIN2) {
MIN2 = huffTree[i].weight;
i2 = i;
} else {
MIN1 = huffTree[i].weight;
i1 = i;
}
}
}
}
}
void HuffmanTree(element huffTree[], const double w[]) {
for (int i = 0; i < 2 * n - 1; i++) {
huffTree[i].parent = 0;
huffTree[i].lchild = 0;
huffTree[i].rchild = 0;
}
for (int i = 0; i < n; i++)
huffTree[i].weight = w[i];
for (int k = n; k < 2 * n - 1; k++) {
int i1 = -1, i2 = -1;
Select(huffTree, i1, i2);
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;
}
}
element huffTree[2 * n - 1];
int main() {
HuffmanTree(huffTree, w);
HuffmanCode(huffTree, n);
return 0;
}
