堆中的路径

堆中的路径

0x00 问题描述

QQ截图20200206110058

0x01 解题思路

​ 这个题目不难,只需要先根据节点构造堆,然后再输出指定位置的节点到根的路径,位置不断除2即可实现

0x02 show me the code

#include <stdio.h>
#include <stdlib.h>
#define maxsize 1000
#define minnum -1000
typedef struct heap* minheap;
struct heap{
	int* data;
	int capacity;
	int size;
};
void traversal(minheap h){
	int i;
	for(i=1;i<h->size+1;i++){
		printf("(%d) ",h->data[i]);
	}
	printf("\n");
}
void adjust(minheap h,int parent){
	int child=2*parent;
	for(;child<=h->size;){   
		int minpos=child;   //假设左儿子最小
		if(child+1<=h->size&&h->data[child+1]<h->data[child]){
			minpos=child+1;
		}
		if(h->data[parent]>h->data[minpos]){
			int temp=h->data[parent];
			h->data[parent]=h->data[minpos];
			h->data[minpos]=temp;
			parent=minpos;
			child=2*parent;
		}
		else{
			break;
		}
	}
}
minheap create_by_list(int* data,int size){
	int i;
	if(size>maxsize){
		printf("超过最大容量!"); 
		return NULL; 
	}
	minheap h=(minheap)malloc(sizeof(struct heap));
	h->capacity=maxsize;
	h->data=(int*)malloc(sizeof(int)*(h->capacity+1));
	h->size=0;
	h->data[0]=-1000;
	for(i=1;i<size+1;i++){
		h->data[++h->size]=data[i-1];
	}
	int parent=h->size/2;
	for(i=parent;i>0;i--){
		adjust(h,i);
	}
	return h;
}
void getline(minheap h,int pos){
	if(pos<=h->size&&pos>0){
		printf("(%d)",h->data[pos]);
		while(pos/=2){
			printf("(%d)",h->data[pos]);
		}
		printf("\n");
	}else{
		printf("没有这个节点!"); 
	}
}
int main(void){
	int m,n;
	int i;
	scanf("%d %d",&m,&n);
	int* a=(int*)malloc(sizeof(int)*m);
	for(i=0;i<m;i++){
		scanf("%d",a+i);
	}
	minheap h=create_by_list(a,m);
	for(i=0;i<n;i++){
		int pos=0;
		scanf("%d",&pos);
		getline(h,pos);
	}
	return 0;	
}