构造哈夫曼树，计算WPL。 函数接口定义： void CreateHTree(); void CreateHCode(); 裁判测试程序样例： #include <iostream> #include <queue> #include <vector> #include <string> #include <map> using namespace std; #define MAX 101 int n; struct HTreeNode //哈夫曼树结点类型 { char data; //字符 int weight; //权值 int parent; //双亲的位置 int lchild; //左孩子的位置 int rchild; //右孩子的位置 }; HTreeNode ht[MAX]; //哈夫曼树 map<char,string> htcode; //哈夫曼编码 struct NodeType //优先队列结点类型 { int no; //对应哈夫曼树ht中的位置 char data; //字符 int weight; //权值 bool operator<(const NodeType &s) const { //用于创建小根堆 return s.weight<weight; } }; void CreateHTree(); void CreateHCode(); int WPL() //求WPL { int wps=0; for (int i=0;i<n;i++) wps+=ht[i].weight*htcode[ht[i].data].size(); return wps; } int main() { cin >> n; for(int i=0;i<n;i++) { cin >> ht[i].data >> ht[i].weight; } CreateHTree(); //建立哈夫曼树 CreateHCode(); //求哈夫曼编码 printf("WPL=%d",WPL()); return 0; } /* 请在这里填写答案 */ 输入样例： 第一行输入一个数n(1<n<100)，表示叶子节点的个数，接下去输入n行，每行输入一个字符和一个整数，表示每个节点表示的字符和权值。 5 A 8 B 10 C 2 D 11 E 1 输出样例： 输出WPL。 WPL=67 给我 void CreateHTree(); void CreateHCode(); 完整代码

题目描述

构造哈夫曼树，计算WPL。

函数接口定义：

void CreateHTree();
void CreateHCode();

裁判测试程序样例：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;

#define MAX 101

int n;

struct HTreeNode //哈夫曼树结点类型
{
char data; //字符
int weight; //权值
int parent; //双亲的位置
int lchild; //左孩子的位置
int rchild; //右孩子的位置
};

HTreeNode ht[MAX]; //哈夫曼树
map<char,string> htcode; //哈夫曼编码

struct NodeType //优先队列结点类型
{
int no; //对应哈夫曼树ht中的位置
char data; //字符
int weight; //权值
bool operator<(const NodeType &s) const
{ //用于创建小根堆
return s.weight<weight;
}
};

void CreateHTree();
void CreateHCode();

int WPL() //求WPL
{
int wps=0;
for (int i=0;i<n;i++)
wps+=ht[i].weight*htcode[ht[i].data].size();
return wps;
}

int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
cin >> ht[i].data >> ht[i].weight;
}

CreateHTree(); //建立哈夫曼树
CreateHCode(); //求哈夫曼编码
printf("WPL=%d",WPL());

return 0;
}

样例

输入样例：
第一行输入一个数n(1<n<100)，表示叶子节点的个数，接下去输入n行，每行输入一个字符和一个整数，表示每个节点表示的字符和权值。

5
A 8
B 10
C 2
D 11
E 1

输出样例：
输出WPL。

WPL=67

算法1

(哈夫曼树) $O(n \log n)$

C++ 代码

void CreateHTree()
{
priority_queue<NodeType> que; //优先队列
for(int i=0;i<n;i++) //初始化哈夫曼树
{
ht[i].parent=-1;
ht[i].lchild=-1;
ht[i].rchild=-1;
que.push((NodeType){i,ht[i].data,ht[i].weight});
}
for(int i=n;i<2*n-1;i++) //构造哈夫曼树
{
NodeType x1=que.top();que.pop();
NodeType x2=que.top();que.pop();
ht[x1.no].parent=i;
ht[x2.no].parent=i;
ht[i].lchild=x1.no;
ht[i].rchild=x2.no;
ht[i].weight=x1.weight+x2.weight;
que.push((NodeType){i,ht[i].data,ht[i].weight});
}
}

void CreateHCode()
{
for(int i=0;i<n;i++)
{
int f,r;
string hcode="";
for(r=i,f=ht[i].parent;f!=-1;r=f,f=ht[f].parent) //从叶子结点到根结点求编码
{
if(ht[f].lchild==r)
hcode='0'+hcode;
else
hcode='1'+hcode;
}
htcode[ht[i].data]=hcode;
}
}

时间复杂度

参考文献

C++ 代码