不要使用其他的队列和堆操作,朴实一点
时间: 2024-09-24 16:24:30 浏览: 18
在不使用额外的队列和堆操作的情况下,我们可以手动模拟霍夫曼树的构建过程。以下是通过递归和两个辅助变量来完成这一任务的一种简单方法:
首先,在 `create_ht` 函数中,我们可以从输入数据开始,对每个字符节点进行如下操作:
1. 对于每个字符,将其添加到一个名为 `remaining_chars` 的列表中,并设置其初始权重为其在输入中的频率。
2. 初始化一个辅助变量 `current_node`,表示当前正在构建的节点。
3. 当 `remaining_chars` 中仍有节点时,执行循环:
a. 取出 `remaining_chars` 中权重最小的两个节点(可以通过遍历找到),记为 `node1` 和 `node2`。
b. 创建一个新的节点,将 `node1` 和 `node2` 结合成一个新节点,新节点的权重为 `node1` 和 `node2` 的权重之和。
c. 将新节点插入到 `remaining_chars` 的合适位置,保持按权重升序排列。
d. 将 `current_node` 更新为新节点。
最后,`remaining_chars` 中剩下的最后一个节点就是霍夫曼树的根节点。
`doWPL` 函数可以按照递归的方式进行,对于每一个非叶节点,我们都需要计算左子树和右子树的 WPL(即它们各自路径的总权重),然后加上节点本身的权重,作为整个节点的 WPL。
```c
void create_ht() {
list<char> remaining_chars;
for (int i = 1; i <= n; i++) {
remaining_chars.push_back(ht[i].w);
}
current_node = 0;
while (!remaining_chars.empty()) {
int node1 = find_min_weight(remaining_chars);
int node2 = find_min_weight(remaining_chars); // 注意这里是第二个最小的,因为上一次已经被选了
int newNode = ++n;
ht[newNode].lch = node1;
ht[node1].parent = newNode;
ht[newNode].rch = node2;
ht[node2].parent = newNode;
remaining_chars.erase(remove(remaining_chars.begin(), remaining_chars.end(), node1), remaining_chars.end());
remaining_chars.erase(remove(remaining_chars.begin(), remaining_chars.end(), node2), remaining_chars.end());
remaining_chars.push_back(ht[newNode].w);
current_node = newNode;
}
root = current_node;
}
void doWPL(int node, int depth) {
if (ht[node].parent == -1) return;
// 递归计算左右子树的WPL
doWPL(ht[node].lch, depth + 1);
doWPL(ht[node].rch, depth + 1);
// 更新当前节点的WPL
WPL += ht[node].w * depth;
}
int find_min_weight(list<char>& chars) {
// 找到剩余节点中的最小权重,这里假设list已经排序过
int min_weight = chars.front();
int min_index = 0;
for (size_t i = 1; i < chars.size(); i++) {
if (chars[i] < min_weight) {
min_weight = chars[i];
min_index = i;
}
}
return min_index;
}
阅读全文