学步园

/* lefttist_heap.c -- 左式堆实现文件 */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include "lefttist_heap.h"</p> <p>/* 局部ADT定义 */</p> <p>typedef Node Item2 ;<br /> typedef struct node2<br /> {<br /> Item2 item2 ;<br /> struct node2 * next ;<br /> } Node2 ;<br /> typedef struct queue<br /> {<br /> Node2 * front ;<br /> Node2 * rear ;<br /> int items ;<br /> } * Queue ;</p> <p>typedef Heap Item3 ;<br /> typedef struct node3<br /> {<br /> Item3 item3 ;<br /> struct node3 * next ;<br /> } Node3 ;<br /> typedef struct queue3<br /> {<br /> Node3 * front ;<br /> Node3 * rear ;<br /> int items ;<br /> } * Queue3 ;</p> <p>/* 局部ADT声明 */</p> <p>static int Initialize_Queue (Queue * const pqueue) ;<br /> static int Queue_Is_Empty (const Queue * const pqueue) ;<br /> static int En_Queue (const Queue * const pqueue, const Item2 item2) ;<br /> static int De_Queue (Queue * pqueue, Item2 * pitem2) ;<br /> static void Release2 (const Queue * const pqueue) ;<br /> static Node2 * Make_Node2 (const Item2 item2) ;</p> <p>static int Initialize_Queue3 (Queue3 * const pqueue3) ;<br /> static int Queue_Is_Empty3 (const Queue3 * const pqueue3) ;<br /> static int En_Queue3 (const Queue3 * const pqueue3, const Item3 item3) ;<br /> static int De_Queue3 (Queue3 * pqueue3, Item3 * pitem3) ;<br /> static void Release3 (const Queue3 * const pqueue3) ;<br /> static Node3 * Make_Node3 (const Item3 item3) ;</p> <p>/* 局部函数声明 */</p> <p>static Heap Merge1 (const Heap h1, const Heap h2) ;<br /> static Heap Swap_Children (const Heap heap) ;</p> <p>/* 接口函数定义 */</p> <p>int CreateANullHeap (Heap * const pheap)<br /> {<br /> *pheap = (Node *) malloc (sizeof (Node)) ;<br /> if (NULL == *pheap)<br /> {<br /> puts ("Out of space.[1]") ;<br /> return 0 ;<br /> }<br /> else<br /> {<br /> *pheap = NULL ;<br /> return 1 ;<br /> }<br /> }</p> <p>int HeapIsEmpty (const Heap heap)<br /> {<br /> return NULL == heap ;<br /> }</p> <p>Heap Merge (const Heap h1, const Heap h2)<br /> {<br /> if (NULL == h1)<br /> return h2 ;<br /> if (NULL == h2)<br /> return h1 ;<br /> if (h1 -> item < h2 -> item)<br /> return Merge1 (h1, h2) ;<br /> else<br /> return Merge1 (h2, h1) ;<br /> }</p> <p>Heap Insert (Heap heap, const Item item)<br /> {<br /> Heap new_heap ;</p> <p> new_heap = (Node *) malloc (sizeof (Node)) ;<br /> if (!new_heap)<br /> return NULL ;<br /> else<br /> {<br /> new_heap -> item = item ;<br /> new_heap -> NPL = 0 ;<br /> new_heap -> left = new_heap -> right = NULL ;<br /> heap = Merge (heap, new_heap) ;<br /> }</p> <p> return heap ;<br /> }</p> <p>Heap DeleteMin (const Heap heap)<br /> {<br /> Heap left, right ;</p> <p> if (HeapIsEmpty (heap))<br /> {<br /> puts ("Heap is empty.") ;<br /> return heap ;<br /> }<br /> left = heap -> left ;<br /> right = heap -> right ;<br /> free (heap) ;</p> <p> return Merge (left, right) ;<br /> }</p> <p>Node * Find (const Heap heap, const Item item)<br /> {<br /> Node * temp ;</p> <p> if (NULL == heap)<br /> return NULL ;<br /> if (item == heap -> item)<br /> return heap ;<br /> if ((temp = Find (heap -> left, item)) != NULL)<br /> return temp ;<br /> if ((temp = Find (heap -> right, item)) != NULL)<br /> return temp ;<br /> else<br /> return NULL ;<br /> }</p> <p>Heap Bulid (Heap heap, const Item * array, const int size)<br /> {<br /> Heap h ;<br /> Queue3 q ;<br /> Node3 * arr ;<br /> int ct ;</p> <p> if (!HeapIsEmpty (heap))<br /> return NULL ;<br /> Initialize_Queue3 (&q) ;<br /> arr = (Node3 *) malloc (sizeof (Node3) * size) ;<br /> if (NULL == arr)<br /> return NULL ;<br /> for (ct = 0; ct < size; ct++)<br /> arr[ct].item3 = (Node *) malloc (sizeof (Node)) ;<br /> for (ct = 0; ct < size; ct++)<br /> {<br /> arr[ct].item3 -> item = array[ct] ;<br /> arr[ct].item3 -> NPL = 0 ;<br /> arr[ct].item3 -> left = arr[ct].item3 -> right = NULL ;<br /> En_Queue3 (&q, arr[ct].item3) ;<br /> }<br /> // 此处的内存空间情况很微妙.目前解释不了.我怀疑是借用了队列的空间,但没有什么语言依据<br /> h = (Node *) malloc (sizeof (Node)) ;<br /> while (q -> items != 1)<br /> {<br /> De_Queue3 (&q, &heap) ;<br /> De_Queue3 (&q, &h) ;<br /> heap = Merge (heap, h) ;<br /> En_Queue3 (&q, heap) ;<br /> }<br /> De_Queue3 (&q, &heap) ;<br /> Release3 (&q) ;<br /> // 此处的内存空间情况很微妙.目前解释不了.我怀疑是借用了队列的空间,但没有什么语言依据<br /> // free (h) ;</p> <p> return heap ;<br /> }</p> <p>void LevelOrderTraversal (const Heap heap)<br /> {<br /> Queue q ;<br /> Item2 item2 ;</p> <p> Initialize_Queue (&q) ;<br /> item2 = *heap ;<br /> En_Queue (&q, item2) ;<br /> while (!Queue_Is_Empty (&q))<br /> {<br /> De_Queue (&q, &item2) ;<br /> printf ("%d/n", item2.item) ;<br /> if (item2.left)<br /> En_Queue (&q, *item2.left) ;<br /> if (item2.right)<br /> En_Queue (&q, *item2.right) ;<br /> }<br /> Release2 (&q) ;<br /> }</p> <p>/* 局部函数定义 */</p> <p>static Heap Merge1 (const Heap h1, const Heap h2)<br /> {<br /> if (NULL == h1 -> left)<br /> h1 -> left = h2 ;<br /> else<br /> {<br /> h1 -> right = Merge (h1 -> right, h2) ;<br /> if (h1 -> left -> NPL < h1 -> right -> NPL)<br /> Swap_Children (h1) ;<br /> h1 -> NPL = h1 -> right -> NPL + 1 ;<br /> }</p> <p> return h1 ;<br /> }</p> <p>static Heap Swap_Children (const Heap heap)<br /> {<br /> Node * temp ;</p> <p> temp = heap -> left ;<br /> heap -> left = heap -> right ;<br /> heap -> right = temp ;</p> <p> return heap ;<br /> }</p> <p>/* 局部ADT定义 */</p> <p>static int Initialize_Queue (Queue * const pqueue)<br /> {<br /> *pqueue = (struct queue *) malloc (sizeof (struct queue)) ;<br /> if (!*pqueue)<br /> return 0 ;<br /> (*pqueue) -> front = (*pqueue) -> rear = NULL ;<br /> (*pqueue) -> items = 0 ;</p> <p> return 1 ;<br /> }</p> <p>static int Queue_Is_Empty (const Queue * const pqueue)<br /> {<br /> return 0 == (*pqueue) -> items ;<br /> }</p> <p>static int En_Queue (const Queue * const pqueue, const Item2 item2)<br /> {<br /> Node2 * new_node ;</p> <p> new_node = Make_Node2 (item2) ;<br /> if (!new_node)<br /> return 0 ;<br /> if (Queue_Is_Empty (pqueue))<br /> (*pqueue) -> front = (*pqueue) -> rear = new_node ;<br /> else<br /> {<br /> (*pqueue) -> rear -> next = new_node ;<br /> (*pqueue) -> rear = (*pqueue) -> rear -> next ;<br /> }<br /> (*pqueue) -> items++ ;</p> <p> return 1 ;<br /> }</p> <p>static int De_Queue (Queue * pqueue, Item2 * pitem2)<br /> {<br /> Node2 * temp ;</p> <p> if (Queue_Is_Empty (pqueue))<br /> return 0 ;<br /> *pitem2 = (*pqueue) -> front -> item2 ;<br /> temp = (*pqueue) -> front ;<br /> if (1 == (*pqueue) -> items)<br /> (*pqueue) -> front = (*pqueue) -> rear = NULL ;<br /> else<br /> (*pqueue) -> front = (*pqueue) -> front -> next ;<br /> (*pqueue) -> items-- ;<br /> free (temp) ;</p> <p> return 1 ;<br /> }</p> <p>static void Release2 (const Queue * const pqueue)<br /> {<br /> Node2 * scan, * temp ;</p> <p> scan = (*pqueue) -> front ;<br /> while (scan)<br /> {<br /> temp = scan ;<br /> scan = scan -> next ;<br /> free (temp) ;<br /> }<br /> free (*pqueue) ;<br /> }</p> <p>static Node2 * Make_Node2 (const Item2 item2)<br /> {<br /> Node2 * new_node ;</p> <p> new_node = (Node2 *) malloc (sizeof (Node2)) ;<br /> if (!new_node)<br /> return NULL ;<br /> new_node -> item2 = item2 ;<br /> new_node -> next = NULL ;</p> <p> return new_node ;<br /> }</p> <p>static int Initialize_Queue3 (Queue3 * const pqueue3)<br /> {<br /> *pqueue3 = (struct queue3 *) malloc (sizeof (struct queue3)) ;<br /> if (!*pqueue3)<br /> return 0 ;<br /> (*pqueue3) -> front = (*pqueue3) -> rear = NULL ;<br /> (*pqueue3) -> items = 0 ;</p> <p> return 1 ;<br /> }</p> <p>static int Queue_Is_Empty3 (const Queue3 * const pqueue3)<br /> {<br /> return 0 == (*pqueue3) -> items ;<br /> }</p> <p>static int En_Queue3 (const Queue3 * const pqueue3, const Item3 item3)<br /> {<br /> Node3 * new_node ;</p> <p> new_node = Make_Node3 (item3) ;<br /> if (!new_node)<br /> return 0 ;<br /> if (Queue_Is_Empty3 (pqueue3))<br /> (*pqueue3) -> front = (*pqueue3) -> rear = new_node ;<br /> else<br /> {<br /> (*pqueue3) -> rear -> next = new_node ;<br /> (*pqueue3) -> rear = (*pqueue3) -> rear -> next ;<br /> }<br /> (*pqueue3) -> items++ ;</p> <p> return 1 ;<br /> }</p> <p>static int De_Queue3 (Queue3 * pqueue3, Item3 * pitem3)<br /> {<br /> Node3 * temp ;</p> <p> if (Queue_Is_Empty3 (pqueue3))<br /> return 0 ;<br /> *pitem3 = (*pqueue3) -> front -> item3 ;<br /> temp = (*pqueue3) -> front ;<br /> if (1 == (*pqueue3) -> items)<br /> (*pqueue3) -> front = (*pqueue3) -> rear = NULL ;<br /> else<br /> (*pqueue3) -> front = (*pqueue3) -> front -> next ;<br /> (*pqueue3) -> items-- ;<br /> free (temp) ;</p> <p> return 1 ;<br /> }</p> <p>static void Release3 (const Queue3 * const pqueue3)<br /> {<br /> Node3 * scan, * temp ;</p> <p> scan = (*pqueue3) -> front ;<br /> while (scan)<br /> {<br /> temp = scan ;<br /> scan = scan -> next ;<br /> free (temp) ;<br /> }<br /> free (*pqueue3) ;<br /> }</p> <p>static Node3 * Make_Node3 (const Item3 item3)<br /> {<br /> Node3 * new_node ;</p> <p> new_node = (Node3 *) malloc (sizeof (Node3)) ;<br /> if (!new_node)<br /> return NULL ;<br /> new_node -> item3 = item3 ;<br /> new_node -> next = NULL ;</p> <p> return new_node ;<br /> }