学步园

/* d-heap.c -- d-堆实现文件 */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include "d-heap.h"</p> <p>/* 局部函数声明 */</p> <p>static int Percolate_Up (const Heap * const pheap, const Item item, const int position) ;<br /> static int Percolate_Down (const Heap * const pheap, const Item item, const int position) ;</p> <p>/* 接口函数定义 */</p> <p>int InitializeHeap (Heap * const pheap, const int capacity, const int d)<br /> {<br /> if (capacity < 0)<br /> return 0 ;<br /> *pheap = (struct heap *) malloc (sizeof (struct heap) * (capacity + 1)) ;<br /> if (NULL == *pheap)<br /> {<br /> puts ("Out of space.[1]") ;<br /> return 0 ;<br /> }<br /> (*pheap) -> array = (Item *) malloc (sizeof (Item) * capacity) ;<br /> if (NULL == (*pheap) -> array)<br /> {<br /> puts ("Out of space.[2]") ;<br /> free (*pheap) ;<br /> return 0 ;<br /> }<br /> (*pheap) -> capacity = capacity ;<br /> (*pheap) -> size = 0 ;<br /> (*pheap) -> d = d ;<br /> (*pheap) -> array[0] = MINDATA ;</p> <p> return 1 ;<br /> }</p> <p>int HeapIsEmpty (const Heap * const pheap)<br /> {<br /> return 0 == (*pheap) -> size ;<br /> }</p> <p>int HeapIsFull (const Heap * const pheap)<br /> {<br /> return (*pheap) -> capacity == (*pheap) -> size ;<br /> }</p> <p>int Insert (const Heap * const pheap, const Item item)<br /> {<br /> int i ;</p> <p> if (HeapIsFull (pheap))<br /> return 0 ;<br /> // 变量作为参数在函数间传递时后缀自增、自减不改变变量的值<br /> i = Percolate_Up (pheap, item, ++(*pheap) -> size) ;<br /> (*pheap) -> array[i] = item ;</p> <p> return 1 ;<br /> }</p> <p>Item DeleteMin (const Heap * const pheap)<br /> {<br /> Item min, item ;<br /> int i, position;</p> <p> if (HeapIsEmpty (pheap))<br /> return (*pheap) -> array[0] ;<br /> min = (*pheap) -> array[1] ;<br /> item = (*pheap) -> array[(*pheap) -> size] ;<br /> (*pheap) -> size-- ;<br /> position = 1 ;<br /> i = Percolate_Down (pheap, item, position) ;<br /> (*pheap) -> array[i] = item ;</p> <p> return min ;<br /> }</p> <p>int DecreaseKey (const Heap * const pheap, const int position, const int triangle)<br /> {<br /> Item item ;<br /> int i ;</p> <p> if (position > 0 && position <= (*pheap) -> size && triangle > 0)<br /> {<br /> item = (*pheap) -> array[position] -= triangle ;<br /> i = Percolate_Up (pheap, item, position) ;<br /> (*pheap) -> array[i] = item ;<br /> return 1 ;<br /> }<br /> else<br /> return 0 ;<br /> }</p> <p>int IncreaseKey (const Heap * const pheap, const int position, const int triangle)<br /> {<br /> Item item ;<br /> int i ;</p> <p> if (position > 0 && position <= (*pheap) -> size && triangle > 0)<br /> {<br /> item = (*pheap) -> array[position] += triangle ;<br /> i = Percolate_Down (pheap, item, position) ;<br /> (*pheap) -> array[i] = item ;<br /> return 1 ;<br /> }<br /> else<br /> return 0 ;<br /> }</p> <p>int BuildHeap (const Heap * const pheap, const Item * parray, const int size)<br /> {<br /> Item item ;<br /> int i, d, ct ;</p> <p> if (!HeapIsEmpty (pheap) || size <= 0)<br /> return 0 ;<br /> for (i = 0; i < size; i++)<br /> (*pheap) -> array[i + 1] = parray[i] ;<br /> (*pheap) -> size = size ;<br /> for (d = (*pheap) -> d, ct = (size + d - 2) / d; ct > 0; ct--)<br /> {<br /> item = (*pheap) -> array[ct] ;<br /> i = Percolate_Down (pheap, item, ct) ;<br /> (*pheap) -> array[i] = item ;<br /> }</p> <p> return 1 ;<br /> }</p> <p>int Delete (const Heap * const pheap, const int position)<br /> {<br /> int triangle ;</p> <p> if (position < 0 || position > (*pheap) -> size)<br /> return 0 ;<br /> triangle = (*pheap) -> array[position] - (*pheap) -> array[1] + 1 ;<br /> DecreaseKey (pheap, position, triangle) ;<br /> DeleteMin (pheap) ;</p> <p> return 1 ;<br /> }</p> <p>void Traversal (const Heap * const pheap, void (* pfun) (const Item item))<br /> {<br /> int i, size ;</p> <p> for (i = 1, size = (*pheap) -> size; i <= size; i++)<br /> (* pfun) ((*pheap) -> array[i]) ;<br /> }</p> <p>void Release (const Heap * const pheap)<br /> {<br /> free ((*pheap) -> array) ;<br /> free (*pheap) ;<br /> }</p> <p>/* 局部函数定义 */</p> <p>static int Percolate_Up (const Heap * const pheap, const Item item, const int position)<br /> {<br /> int i, d ;</p> <p> for (i = position, d = (*pheap) -> d; (*pheap) -> array[(i + d - 2) / d] > item; i = (i + d - 2) / d)<br /> (*pheap) -> array[i] = (*pheap) -> array [(i + d - 2) / d] ;</p> <p> return i ;<br /> }</p> <p>static int Percolate_Down (const Heap * const pheap, const Item item, const int position)<br /> {<br /> Item item_record ;<br /> int i, j, d, child, int_record;</p> <p> for (i = position, d = (*pheap) -> d; (i - 1) * d + 2 <= (*pheap) -> size; i = child)<br /> {<br /> child = (i - 1) * d + 2 ;<br /> for (j = 1, int_record = child, item_record = (*pheap) -> array[child]; int_record + j != (*pheap) -> size + 1 && j < d; j++)<br /> {<br /> if ((*pheap) -> array[int_record + j] < item_record)<br /> {<br /> item_record = (*pheap) -> array[int_record + j] ;<br /> child = j + int_record ;<br /> }<br /> }<br /> if (item > (*pheap) -> array[child])<br /> (*pheap) -> array[i] = (*pheap) -> array[child] ;<br /> else<br /> break ;<br /> }</p> <p> return i ;<br /> }