鱼C论坛

 找回密码
 立即注册
查看: 1472|回复: 4

希望大佬能帮我解读以下这个C++代码的含义,图片编了序号

[复制链接]
发表于 2022-3-28 18:07:07 | 显示全部楼层 |阅读模式
50鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-3-28 19:29:01 | 显示全部楼层
看不见呀
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-3-28 21:48:28 | 显示全部楼层

我重新发一次

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-3-29 09:09:06 | 显示全部楼层

#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[1000];
int cnt;

class MyPriorityQueue{
int arr[1000], cnt, siz;
public:
int top(){
  int ret = -1;
  for(int i = 1; i <= cnt; i++){
   if(arr == -1) continue;
   if(ret == -1 || no[ret].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[256];
// 记录每种字符出现的次数

map<char, string> bm;
// 存字符对应的编码

void dfs(int u, string ans){
if(!u) return;
if(no.lson == 0 && no.rson == 0){
  bm[no.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[ch]++;
// 统计每种字符出现次数

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[cnt].lson = pq.top(); pq.pop();
  no[cnt].rson = pq.top(); pq.pop();
  no[cnt].val = no[no[cnt].lson].val + no[no[cnt].rson].val;
  pq.push(cnt);
}
// 每次合并两个子树

dfs(pq.top(), "");
// 优先队列里面唯一的结点一定是哈夫曼树的根节点

for(auto P : bm){
  cout << P.first << " : " << P.second << endl;
}
// 输出每种字符以及对应的编码

这个就是源代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-3-29 12:59:03 | 显示全部楼层
Lijingyang 发表于 2022-3-29 09:09
#include
using namespace std;
struct Node{

打扰了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-5-1 07:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表