学习日记7: 堆的路径
程序代码:
#include <stdio.h> #include <stdlib.h> int* BuildMaxHeap( int N ) { int i ; int t , size ; int item ; int *PtrElements ;//保存结点数据的指针 //建立一个N个元素的最小堆, PtrElements=(int*)malloc ( (N+1) * sizeof(int) ) ; *PtrElements = -10001 ; //将第0个元素设定为最小值-10001 size = 0 ; for(i=0 ; i<N ; i++) { scanf("%d" , &item ) ; size=size+1 ; for(t=size ; *(PtrElements+t/2)>item ; t=t/2 ) *(PtrElements+t)=*(PtrElements+t/2) ; *(PtrElements+t) = item ; } return PtrElements ; } int main( ) { int i,j ; int N,M ; //插入元素的个数、以及需要打印的路径条数 int index ;//需打印路径的起始元素的下标 int *p ; scanf("%d",&N) ;//输入插入元素的个数 scanf("%d",&M) ;//输入需打印的路径条数 p = BuildMaxHeap( N ) ;//建立一个N个元素的最小堆 for(i=1 ; i<=M ; i++) { scanf("%d" , &index) ;//输入需打印路径的起始元素的下标 for(j=index ; j>1 ; j=j/2 ) printf("%d ",*(p+j)) ; printf("%d",*(p+1)) ; printf("\n") ; } return 0; }