问题遇到的现象和发生背景
题目
最优编码问题。给出n个字符的频率ci，给每个字符赋予一个01编码串，使得任意一个字符穿的编码不是另一个字符编码的前缀，而且编码后总长度（每个字符的频率与编码长度乘积的总和）尽量小。
如何构造一棵最优的编码树？
Huffman算法：把每个字符看作一个单结点子树放在一个树集合中，每棵子树的权值等于相应字符的频率。每次取权值最小的两棵子树合并成一棵新树，并重新放到集合中。新树的权值等于两颗子树权值之和。
编程要求
根据提示，在右侧编辑器 Begin-End 区间补充代码，完成Huffman编码树问题。
测试说明
平台会对你编写的代码进行测试：
输入数据: 第一行，一个输入(n)，n表示有n行。后面两行，第一个值是字符，第二个值是频率。输出一行，为多少位内存空间。 $内存空间=一个字符串的位编码长度*频率$ 输出数据： 最短编码长度
用代码块功能插入代码，请勿粘贴截图。 不用代码块回答率下降 50%
#include<iostream>
#include<map>
#include<vector>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
/********** Begin **********/
// 函数，结构体，全局变量定义区
struct Node{
int value;
string name;
Node *parent;
int code;
Node(int code=-1):code(code){
}
};
Node* newnode(){
return new Node();
}
struct node_compare{
bool operator()(const Node *a,const Node *b){//重载()
return a->value > b->value;
}
};
/********** End **********/
int main(void){
/********** Begin **********/
int n;
map<string,int> dt;
cin>>n;
Node f[n];
priority_queue<Node*,vector<Node*>,node_compare>ctree;
for(int i=0;i<n;i++){
cin>>f[i].name>>f[i].value;
tree.push(&f[i]);
dt[f[i].name]=0;
}
while(!tree.empty()){
Node *p1=tree.top();
tree.pop();
if(tree.empty()){
p1->parent=p1;
break;
}
Node * p2 =tree.top();
int a=p1->value;
tree.pop();
Node *node =newnode();
node->value=p1->value+p2->value;
p1->code=0;
p2->code=1;
p1->parent=node;
p2->parent=node;
tree.push(node);
}
int sum=0;
for(int i=0;i<n;i++){
int a[100],k=0;
Node *p1=&f[i];
Node *p2=f[i].parent;
while(p1!=p2){
a[k++]=p1->code;
p1=p2;
p2=p1->parent;
}
for (int j=k-1;j>=0;j--){
dt[f[i].name]++;
}
sum+=dt[f[i].name]*f[i].value;
}
cout<<sum<<endl;
/********** End **********/
return 0;
}
运行结果及详细报错内容
step3/student.cpp: In function ‘int main()’:
step3/student.cpp:39:9: error: ‘tree’ was not declared in this scope
tree.push(&f[i]);
^~~~
step3/student.cpp:39:9: note: suggested alternative: ‘ctree’
tree.push(&f[i]);
^~~~
ctree
step3/student.cpp:42:16: error: ‘tree’ was not declared in this scope
while(!tree.empty()){
^~~~
step3/student.cpp:42:16: note: suggested alternative: ‘ctree’
while(!tree.empty()){
^~~~
ctree
我的解答思路和尝试过的方法，不写自己思路的，回答率下降 60%
在程序实现上，可以先按照频率把所有字符排序成表P，然后创建一个新结点队列Q，在每次合并两个结点后把新结点放到队列Q中。由于后合并的频率和一定比先合并的频率和大，因此Q内的元素是有序的。类似有序表的合并过程，每次只需要检查P和Q的首元素即可找到频率最小的元素，时间复杂度为O(n)。算上排序，总时间复杂度为O(nlogn)。
我想要达到的结果，如果你需要快速回答，请尝试 “付费悬赏”
测试输入：
第1行 6
第2行 a 45
第3行b 13
第4行 c 12
第5行 d 16
第6行 e 9
第7行 f 5
预期输出： 224
