数据结构-怀化学院期末题(1321)

发布时间:2024年01月08日

构建哈夫曼树

题目描述:

根据给定的叶结点字符及其对应的权值创建哈夫曼树。
输入:
第一行为叶子结点的数目n(1<=n<=100)。第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼树。构造哈夫曼树的原则是先两个最小的,构造一个父结点,其中最小的结点为左孩子,次小的为右孩子,如果两个最小的叶结点相等,则取排在前一个位置的为左孩子。
输出:
哈夫曼树的权值,左孩子,右孩子及其对应的父亲,相邻数据之间用空格隔开;

输入样例:

5
abcde
15 25 15 20 25

输出样例:

15 0 0 6
25 0 0 7
15 0 0 6
20 0 0 7
25 0 0 8
30 1 3 8
45 4 2 9
55 5 6 9
100 7 8 0

代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<vector> 
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10;
int w[N],a[N],n;
int l[N],r[N],fu[N];
int cnt,idx = 1;
bool cmp(int x,int y){
	if(w[x] != w[y]) return w[x] > w[y];
	return x > y;
}
int main(){
	cin >> n;
	string q;
	cin >> q;
	for(int i = 1;i <= n;i ++){
		cin >> w[i];
		a[cnt ++] = i;
		idx ++;
	}
	while(cnt > 1){
		sort(a,a + cnt,cmp);
		int num1 = a[cnt - 1];
		int num2 = a[cnt - 2];
		a[cnt - 2] = idx ++;
		w[a[cnt - 2]] = w[num1] + w[num2];
		l[a[cnt - 2]] = num1;
		r[a[cnt - 2]] = num2;
		fu[num1] = a[cnt-2];
		fu[num2] = a[cnt-2];
		cnt --;
	}
	for(int i = 1;i < idx;i ++)
		cout << w[i] << ' ' << l[i] << ' ' << r[i] << ' ' << fu[i] << endl;
	return 0;
}

?

文章来源:https://blog.csdn.net/weixin_72982195/article/details/135451553
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。