希望大佬能帮我解读以下这个C++代码的含义，图片编了序号
看不见呀{:10_269:} 大马强 发表于 2022-3-28 19:29看不见呀
我重新发一次{:5_100:}
大马强 发表于 2022-3-28 19:29
看不见呀
#include<bits/stdc++.h>
using namespace std;
struct Node{
int val;
char ch;
int lson, rson;
// val 记录出现的频率
// ch 记录叶子结点对应的字符
// lson 和 rson 分别对应左右子树
Node(){}
Node(int val, char ch): val(val), ch(ch){
lson = rson = 0;
}
}no;
int cnt;
class MyPriorityQueue{
int arr, cnt, siz;
public:
int top(){
int ret = -1;
for(int i = 1; i <= cnt; i++){
if(arr == -1) continue;
if(ret == -1 || no.val > no.val){
ret = i;
}
}
return ret;
}
// 返回一个val值最小的结点编号
int pop(){
int t = top();
for(int i = 1; i <= cnt; i++){
if(arr == t){
arr = -1;
siz--;
}
}
}
// 删除pop出的结点
void push(int x){
arr[++cnt] = x;
siz++;
}
// 加入一个结点
int size(){
return siz;
}
// 返回优先队列里面的结点个数
}pq;
int num;
// 记录每种字符出现的次数
map<char, string> bm;
// 存字符对应的编码
void dfs(int u, string ans){
if(!u) return;
if(no.lson == 0 && no.rson == 0){
bm.ch] = ans;
return;
}
dfs(no.lson, ans + "0");
dfs(no.rson, ans + "1");
}
// 在哈夫曼树上递归，算出叶子节点对应的编码
int main(){
string s, t = "";
cin >> s;
for(auto ch : s) num++;
// 统计每种字符出现次数
for(int i = 0; i < 256; i++){
if(num){
no[++cnt] = Node(num, i);
pq.push(cnt);
}
}
// 先将每个结点放进优先队列
if(pq.size() == 1){
no[++cnt].lson = pq.top(); pq.pop();
pq.push(cnt);
}
// 特殊处理只有一种字符的情况
while(pq.size() != 1){
cnt++;
no.lson = pq.top(); pq.pop();
no.rson = pq.top(); pq.pop();
no.val = no.lson].val + no.rson].val;
pq.push(cnt);
}
// 每次合并两个子树
dfs(pq.top(), "");
// 优先队列里面唯一的结点一定是哈夫曼树的根节点
for(auto P : bm){
cout << P.first << " : " << P.second << endl;
}
// 输出每种字符以及对应的编码
这个就是源代码{:5_96:} Lijingyang 发表于 2022-3-29 09:09
#include
using namespace std;
struct Node{
打扰了{:10_266:}
页:
[1]