10-2.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
#define  MAX_SIZE 100    /*  堆最大个数－1 */
#define FALSE 0
#define TRUE  1
#define SWAP(x, y, t)  ((t) = (x) , (x) = (y), (y) = (t))
typedef struct  info{
		int key;
		/* 其他数据 */
} element;
int min_child_grandchild(element heap[],int parent)
{	
	if(heap[2*parent].key>heap[parent/2].key)
		return parent/2;
	else
		return 2*parent;
}
element min_delete(element heap[ ], int *n)
{   /* 从堆中删除最小元素 */ 
	int i, last, k, parent;
	element temp, x;
	if ( !(*n) ) {
		printf("堆是空的\n");
    heap[0].key =-1;    
    return heap[0];
	}
	heap[0] = heap[1];      /* 保存元素 */
	x = heap[(*n)--];
	/*找到位置插入x */
	for ( i = 1, last = (*n)/2; i <= last;) {
		k = min_child_grandchild(heap,i);
		if (x.key <= heap[k].key) 
			break;
		heap[i] = heap[k];
		if (k <= 2*i+1) { /* 2(b) */
			i = k;
			break;
		}
		parent = k/2;
		if (x.key > heap[parent].key)
			SWAP(heap[parent],x,temp);
		i = k;
	} /* for */
	heap[i] = x;
	return heap[0];
}
 

void main()
{
	element heap[MAX_SIZE];
	int n=10;
	min_delete(heap,10);
}