生活随笔
收集整理的這篇文章主要介紹了
堆中的路径 (25 分)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
7-17 堆中的路徑 (25 分)
將一系列給定數字插入一個初始為空的小頂堆H[]。隨后對任意給定的下標i，打印從H[i]到根結點的路徑。
輸入格式:
每組測試第1行包含2個正整數N和M(≤1000)，分別是插入元素的個數、以及需要打印的路徑條數。下一行給出區間[-10000,
10000]內的N個要被插入一個初始為空的小頂堆的整數。最后一行給出M個下標。
輸出格式:
對輸入中給出的每個下標i，在一行中輸出從H[i]到根結點的路徑上的數據。數字間以1個空格分隔，行末不得有多余空格。
輸入樣例:
5 3
46 23 26 24 10
5 4 3
輸出樣例:
24 23 10
46 23 10
26 10
#include<stdio.h>
#include<stdlib.h>
#define MinData -1;
typedef int ElementType
;typedef struct HeapStruct
*MaxHeap
;
struct HeapStruct
{ElementType
*data
; int count
; int Capacity
;
};
MaxHeap
creat(int n
)
{MaxHeap H
= (MaxHeap
)malloc(sizeof(struct HeapStruct
));H
->Capacity
= n
;H
->count
= 0;H
->data
= (ElementType
*)malloc((n
+1)*sizeof(ElementType
));H
->data
[0] = MinData
;return H
;
}
void swap(int *a
, int *b
)
{int temp
= *a
;*a
= *b
;*b
= temp
;}
void shiftUp(int k
,int *data
){while( k
> 1 && data
[k
/2] > data
[k
] ){swap( &data
[k
/2], &data
[k
] );k
/= 2;}
}
void shiftDown(int k
,int *data
,int count
){while( 2*k
<= count
){int j
= 2*k
;if( j
+1 <= count
&& data
[j
+1] < data
[j
] ) j
++;if( data
[k
] >= data
[j
] ) break;swap( &data
[k
] , &data
[j
] );k
= j
;}}
int main()
{int n
,m
;scanf("%d%d",&n
,&m
);MaxHeap H
= creat(n
);for(int i
=1;i
<=n
;i
++){scanf("%d",&H
->data
[i
]);H
->count
++;shiftUp(i
,H
->data
);shiftDown(i
,H
->data
,H
->count
);}int x
;for(int i
=1;i
<=m
;i
++){scanf("%d",&x
);int cnt
=0;while(x
>=1){if(cnt
)printf(" ");printf("%d",H
->data
[x
]);x
/=2;cnt
++;}printf("\n");}}
總結
以上是生活随笔為你收集整理的堆中的路径 (25 分)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
