最优二叉树
本帖最后由 Etan76 于 2023-10-28 18:22 编辑为什么我的输出前面会有队列一个符号？下面是我使用过的头文件名
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXBIT 10
#define MAXVALUE 1000
typedef struct HNode {
int weight; // 权重
int lchild;
int rchild;
int parent;
} HNode, *HTree;
// 构建最优二叉树
HTree HuffmanTree(int* w, int n) {
int m, m1, m2, x1, x2, i, j;
HTree ht;
HNode* p;
if (n <= 1) {
return NULL;
}
m = 2 * n - 1;
ht = new HNode;
if (ht == NULL) return ht;
for (p = ht, i = 0; i < n; ++i, ++p, ++w) {
p->weight = *w;
p->rchild = -1;
p->lchild = -1;
p->parent = -1;
}
for (; i < m; ++i) {
p->weight = 0;
p->rchild = -1;
p->lchild = -1;
p->parent = -1;
}
for (i = n; i < m; ++i) {
m1 = m2 = MAXVALUE;
x1 = x2 = 0;
for (j = 0; j < i; ++j) {
if (ht.parent == -1 && ht.weight < m1) {
m2 = m1;
x2 = x1;
m1 = ht.weight;
x1 = j;
}
else if (ht.parent == -1 && ht.weight < m2) {
m2 = ht.weight;
x2 = j;
}
}
ht.parent = i;
ht.parent = i;
ht.lchild = x1;
ht.rchild = x2;
ht.weight = m1 + m2;
}
return ht;
}
// 获取哈夫曼编码
void getHuffmanCode(HTree ht, int n, vector<string>& huffmanCode) {
for (int i = 0; i < n; ++i) {
string code = "";
int child = i;
int parent = ht.parent;
while (parent != -1) {
if (ht.lchild == child) {
code += "0";
}
else {
code += "1";
}
child = parent;
parent = ht.parent;
}
reverse(code.begin(), code.end()); // 反转字符串，得到正确的哈夫曼编码
huffmanCode.push_back(code);
}
}
int main() {
int n;
cin >> n;
int* weights = new int;
for (int i = 0; i < n; ++i) {
cin >> weights;
}
HTree ht = HuffmanTree(weights, n); // 构建最优二叉树
vector<string> huffmanCode;
getHuffmanCode(ht, n, huffmanCode); // 获取哈夫曼编码
int wpl = 0; // 带权路径长度
for (int i = 0; i < n; ++i) {
wpl += weights * huffmanCode.length();
}
cout << wpl << endl; // 输出带权路径长度
sort(huffmanCode.begin(), huffmanCode.end()); // 按字典序排序哈夫曼编码
for (int i = 0; i < n; ++i) {
cout << huffmanCode << endl; // 输出哈夫曼编码
}
delete[] weights;
delete[] ht;
return 0;
} 这个你至少得把你的源码发出来啊 aonima 发表于 2023-10-28 17:40
这个你至少得把你的源码发出来啊
发了，麻烦大神帮忙看一下 本帖最后由 aonima 于 2023-10-30 00:01 编辑
大概看了一下，你这代码确定能跑起来 aonima 发表于 2023-10-29 23:20
大概看了一下，你这代码确定能跑起来
代码确实存在问题，我自己修改好了，谢谢你！{:1_918:}
页:
[1]