赞
踩
05-树7 堆中的路径 分数 25 作者 陈越 单位 浙江大学
将一系列给定数字插入一个初始为空的最小堆 h。随后对任意给定的下标 i,打印从第 i 个结点到根结点的路径。
输入格式:
每组测试第 1 行包含 2 个正整数 n 和 m (≤103),分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间 [−104,104] 内的 n 个要被插入一个初始为空的小顶堆的整数。最后一行给出 m 个下标。
输出格式:
对输入中给出的每个下标 i,在一行中输出从第 i 个结点到根结点的路径上的数据。数字间以 1 个空格分隔,行末不得有多余空格。
输入样例:
- 5 3
- 46 23 26 24 10
- 5 4 3
输出样例:
- 24 23 10
- 46 23 10
- 26 10
代码长度限制:16 KB 时间限制:400 ms 内存限制:64 MB
本题主要考察了对最小堆的插入操作,较易实现。
- # include<stdio.h>
- # include<stdlib.h>
- # define MINNUM -10001
-
- typedef struct MinHeap* PtrMinHeap;
- struct MinHeap{
- int* Array; // 存放最小堆的数组
- int Size; // 最小堆中已有的元素个数
- };
-
- PtrMinHeap CreateMinHeap(int N);
- void InsertMinHeap(PtrMinHeap Heap, int X);
- void PrintMinHeap(PtrMinHeap Heap, int index);
-
- int main(){
- int n,m;
- scanf("%d %d",&n,&m);
- // 创建含哨兵的最小堆
- PtrMinHeap Heap = CreateMinHeap(n+1);
- // 向最小堆中插入元素
- int i,data;
- for(i=0;i<n;i++){
- scanf("%d",&data);
- InsertMinHeap(Heap,data);
- }
- // 给定下标输出路径
- int index;
- for(i=0;i<m;i++){
- scanf("%d",&index);
- PrintMinHeap(Heap,index);
- }
- return 0;
- }
-
- // 创建容量为N的最小堆,并在数组下标为0的地方设置哨兵
- PtrMinHeap CreateMinHeap(int N){
- PtrMinHeap Heap = (PtrMinHeap)malloc(sizeof(struct MinHeap));
- Heap->Array = (int*)malloc(sizeof(int)*N);
- Heap->Array[0] = MINNUM;
- Heap->Size = 0;
- return Heap;
- }
-
- // 向一个最小堆中插入元素
- void InsertMinHeap(PtrMinHeap Heap, int X){
- int Child = ++Heap->Size;
- int Parent = Child/2;
- while(Heap->Array[Parent]>X){
- Heap->Array[Child] = Heap->Array[Parent];
- Child = Parent;
- Parent = Child/2;
- }
- Heap->Array[Child] = X;
- return;
- }
-
- // 给定一个下标,输出从这个下标到最小堆根结点的路径
- void PrintMinHeap(PtrMinHeap Heap, int index){
- int count = 0;
- while(index>=1){
- if(count==0){
- printf("%d",Heap->Array[index]);
- count++;
- }else{
- printf(" %d",Heap->Array[index]);
- }
- index/=2;
- }
- printf("\n");
- return;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。