【算法】蓝桥杯 试题 基础练习 Huffuman树
2024-10-08 08:16:39
资源限制
时间限制:1.0s 内存限制:512.0MB
问题描述
Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。
给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下:
1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
2. 重复步骤1,直到{pi}中只剩下一个数。
在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。
本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。
给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下:
1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
2. 重复步骤1,直到{pi}中只剩下一个数。
在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。
本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。
例如,对于数列{pi}={5, 3, 8, 2, 9},Huffman树的构造过程如下:
1. 找到{5, 3, 8, 2, 9}中最小的两个数,分别是2和3,从{pi}中删除它们并将和5加入,得到{5, 8, 9, 5},费用为5。
2. 找到{5, 8, 9, 5}中最小的两个数,分别是5和5,从{pi}中删除它们并将和10加入,得到{8, 9, 10},费用为10。
3. 找到{8, 9, 10}中最小的两个数,分别是8和9,从{pi}中删除它们并将和17加入,得到{10, 17},费用为17。
4. 找到{10, 17}中最小的两个数,分别是10和17,从{pi}中删除它们并将和27加入,得到{27},费用为27。
5. 现在,数列中只剩下一个数27,构造过程结束,总费用为5+10+17+27=59。
输入格式
输入的第一行包含一个正整数n(n<=100)。
接下来是n个正整数,表示p0, p1, …, pn-1,每个数不超过1000。
接下来是n个正整数,表示p0, p1, …, pn-1,每个数不超过1000。
输出格式
输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
5 3 8 2 9
样例输出
59
#include<stdio.h>
#include<string.h>
void countSort(int n,int *p);
int Huffuman(int n,int *p); int main()
{
int n,i;
int p[];
int all;
scanf("%d",&n);
for(i=; i<n; i++)
{
scanf("%d",&p[i]);
}
all=Huffuman(n,p);
printf("%d",all);
return ;
} int Huffuman(int n,int *p)
{
int i,j;
int sum=;//记录总费用
int q=;//记录最小数的指向,当当前最小的置为0之后就移动位置
//可以控制循环次数为数组个数-1,因为每循环一次就少一个数
for (i=; i<n-; i++)
{
//1.如何找到数组中的两个最小的数?——先排序(采用计数排序)
countSort(n,p);
//2.将数组前两个相加并将最小位置为0,将第二小上面保存两个最小数的和
sum=sum+p[q]+p[q+];//记录费用
p[q+]=p[q]+p[q+];//第二小的位置上保存两个最小的相加之后的结果
p[q]=;//将最小的位置上置为0;
q++;//q指向下一位
}
return sum;
}
void countSort(int n,int *p)
{
int i;
//先找到数组中的最大元素,以便给辅助数组定空间
int max=p[];
int k=;
for(i=; i<n; i++)
{
if(p[i]>=max)
{
max=p[i];
}
}
int help[max+];//根据最大的元素来定义辅助数组的大小
//并且初始化将help数组中都为0
memset(help,,sizeof(help));
for(i=; i<n; i++)
{
//循环遍历原数组,将对应的元素传给辅助数组的下标
help[p[i]]++;
}
//扫描辅助数组,将元素不为0的下标按顺序返回给原数组
for(i=; i<max+; i++)
{
while(help[i]!=)
{
p[k]=i;
help[i]--;
k++;
}
}
}
最新文章
- zabbix利用自带的模板监控mysql数据库
- Implement a TextView with an animation in its left side
- 【JAVA】LOG4J使用心得
- JavaScript读写脚txt文件
- iOS 进入后台的处理
- USACO3.25Magic Squares(bfs)
- web端及时通讯原理
- 连接SQLite 创建ADO.net实体类
- centos主机建立ssh互信
- C语言实现的猜数字小游戏(主要是对于自定义函数的运用)
- 2、jenkins+svn自动发布和回滚
- python利用xlrd读取excel文件始终报错原因
- Latex文件分别用Texwork和Winedt打开时,产生中文乱码的解决方法
- noteforjs
- scrapy知识积累
- 乘风破浪:LeetCode真题_027_Remove Element
- BZOJ 2226 [Spoj 5971] LCMSum 最大公约数之和 | 数论
- 升级cocoapods1.1.1版本
- Nginx启动SSL功能
- R6
热门文章
- Centos7安装 Anaconda + jupyter notebook
- ①CM+CDH6.2.0安装(全网最全)
- SpringBoot + Mybatis 和ssm 使用数据库的区别
- logback 发送邮件和自定义发送邮件;java类发送邮件
- webpack--运行npm run dev自动打开浏览器运行首页的两种方式以及热加载
- Win32实现迷宫
- 青石巷-小L的爸爸
- 【基础】CodeBlocks调试器基本使用方法
- 低功耗蓝牙ATT/GATT/Profile/Service/Characteristic规格解读
- ls-remote -h -t git://github.com/adobe-webplatform/eve.git