学步园

  这个斜堆没有XX检测.也正因为我不明白书上说的是什么意思,才没有写出来.不过,那似乎是个理论上100%可以避免的检测.或者,至少来说,一些事实验证了代码的正确性.

 希望高手指正!

/* skew-heap.c -- 斜堆实现文件 */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include "skew-heap.h"</p> <p>/* 局部ADT声明 */</p> <p>/* Item1定义为指针类型在释放原空间后会造成非法的存储器引用 */<br /> /* 得到的经验教训是: 指针还是要慎用.没有理由的时候不要滥用 */<br /> typedef Node Item1 ;<br /> typedef struct node1<br /> {<br /> Item1 item1 ;<br /> struct node1 * next ;<br /> } Node1 ;<br /> typedef struct queue<br /> {<br /> Node1 * front ;<br /> Node1 * rear ;<br /> int size ;<br /> } * Queue ;</p> <p>int Initialize_Queue (Queue * const pqueue) ;<br /> int Queue_Is_Empty (const Queue * const pqueue) ;<br /> int En_Queue (const Queue * const pqueue, const Item1 item1) ;<br /> int De_Queue (const Queue * const pqueue, Item1 * const pitem1) ;<br /> void Release_ (const Queue * const pqueue) ;<br /> Node1 * Make_Node1 (const Item1 item1) ;</p> <p>/* 局部函数声明 */</p> <p>static Heap Merge1 (const Heap h1, const Heap h2) ;<br /> static Heap Swap_Children (const Heap h1) ;</p> <p>/* 接口函数定义 */</p> <p>int Create (Heap * const ph)<br /> {<br /> *ph = (Node *) malloc (sizeof (Node)) ;<br /> if (NULL == *ph)<br /> return 0 ;<br /> else<br /> {<br /> *ph = NULL ;<br /> return 1 ;<br /> }<br /> }</p> <p>int HeapIsEmpty (const Heap h)<br /> {<br /> return NULL == h ;<br /> }</p> <p>Heap Merge (const Heap h1, const Heap h2)<br /> {<br /> if (NULL == h1)<br /> return h2 ;<br /> else if (NULL == h2)<br /> return h1 ;<br /> else if (h1 -> item < h2 -> item)<br /> return Merge1 (h1, h2) ;<br /> else<br /> return Merge1 (h2, h1) ;<br /> }</p> <p>Heap Insert (Heap h, const Item item)<br /> {<br /> Heap new_heap ;</p> <p> new_heap = (Node *) malloc (sizeof (Node)) ;<br /> if (NULL == new_heap)<br /> return h ;<br /> new_heap -> item = item ;<br /> new_heap -> left = new_heap -> right = NULL ;<br /> h = Merge (h, new_heap) ;</p> <p> return h ;<br /> }</p> <p>Heap DeleteMin (Heap h, Node * const pnode)<br /> {<br /> Node * temp ;</p> <p> if (HeapIsEmpty (h))<br /> return h ;<br /> temp = h ;<br /> *pnode = *h ;<br /> h = Merge (h -> left, h -> right) ;<br /> free (temp) ;</p> <p> return h ;<br /> }</p> <p>Node * Find (const Heap h, const Item item)<br /> {<br /> Node * temp ;</p> <p> if (NULL == h)<br /> return NULL ;<br /> else if (item == h -> item)<br /> return h ;<br /> else if ((temp = Find (h -> left, item)))<br /> return temp ;<br /> else if ((temp = Find (h -> right, item)))<br /> return temp ;<br /> else<br /> return NULL ;<br /> }</p> <p>Heap Build (const Item array[], const int size)<br /> {<br /> Heap h1, h2 ;<br /> Queue q ;<br /> Node * arr ;<br /> int ct ;</p> <p> if (!Initialize_Queue (&q))<br /> return NULL ;<br /> arr = (Node *) malloc (sizeof (Node) * size) ;<br /> for (ct = 0; ct < size; ct++)<br /> {<br /> arr[ct].item = array[ct] ;<br /> arr[ct].left = arr[ct].right = NULL ;<br /> En_Queue (&q, arr[ct]) ;<br /> }<br /> // 养成内存不再使用之后立刻还回去的习惯<br /> free (arr) ;<br /> while (q -> size != 1)<br /> {<br /> // 此处的内存分配情况, 我只知道这么做内存够用.不清楚编译器是怎么分配的<br /> h1 = (Node *) malloc (sizeof (Node)) ;<br /> h2 = (Node *) malloc (sizeof (Node)) ;<br /> De_Queue (&q, h1) ;<br /> De_Queue (&q, h2) ;<br /> h1 = Merge (h1, h2) ;<br /> En_Queue (&q, *h1) ;<br /> }<br /> De_Queue (&q, h1) ;<br /> Release_ (&q) ;<br /> // h1 和 h2 共同承担了斜堆所用内存的需求</p> <p> return h1 ;<br /> }</p> <p>void Release (const Heap h)<br /> {<br /> if (h)<br /> {<br /> Release (h -> left) ;<br /> Release (h -> right) ;<br /> free (h) ;<br /> }<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 /> // 同左式堆相比, 斜堆的好处是节省了空间, 而且少了一步条件检测<br /> Swap_Children (h1) ;<br /> }</p> <p> return h1 ;<br /> }</p> <p>static Heap Swap_Children (const Heap h1)<br /> {<br /> Node * temp ;</p> <p> temp = h1 -> left ;<br /> h1 -> left = h1 -> right ;<br /> h1 -> right = temp ;</p> <p> return h1 ;<br /> }</p> <p>/* 局部ADT定义 */</p> <p>int Initialize_Queue (Queue * const pqueue)<br /> {<br /> *pqueue = (struct queue *) malloc (sizeof (struct queue)) ;<br /> if (NULL == *pqueue)<br /> return 0 ;<br /> (*pqueue) -> front = (*pqueue) -> rear = NULL ;<br /> (*pqueue) -> size = 0 ;</p> <p> return 1 ;<br /> }</p> <p>int Queue_Is_Empty (const Queue * const pqueue)<br /> {<br /> return 0 == (*pqueue) -> size ;<br /> }</p> <p>int En_Queue (const Queue * const pqueue, const Item1 item1)<br /> {<br /> Node1 * new_node ;</p> <p> new_node = Make_Node1 (item1) ;<br /> if (NULL == new_node)<br /> return 0 ;<br /> if (Queue_Is_Empty (pqueue))<br /> {<br /> // 实际上队列是通过 front 实现的, rear 起的只是辅助作用. 所以不为其分配空间<br /> (*pqueue) -> front = (*pqueue) -> rear = new_node ;<br /> }<br /> else<br /> {<br /> /* 也许到现在我才明白了这段代码的含义 */<br /> /* 在第二次调用的时候, (*pqueue) -> rear -> next = new_node 其实相当于 (*pqueue) -> front -> next = new_node */<br /> /* 在这步完成了队列的连接.太隐式了.我以前貌似真的是稀里糊涂的! */<br /> (*pqueue) -> rear -> next = new_node ;<br /> (*pqueue) -> rear = new_node ;<br /> }<br /> (*pqueue) -> size++ ;</p> <p> return 1 ;<br /> }</p> <p>int De_Queue (const Queue * const pqueue, Item1 * const pitem1)<br /> {<br /> Node1 * temp ;</p> <p> if (Queue_Is_Empty (pqueue))<br /> return 0 ;<br /> *pitem1 = (*pqueue) -> front -> item1 ;<br /> temp = (*pqueue) -> front ;<br /> if ((*pqueue) -> size != 1)<br /> (*pqueue) -> front = (*pqueue) -> front -> next ;<br /> else<br /> (*pqueue) -> front = (*pqueue) -> rear = NULL ;<br /> (*pqueue) -> size-- ;<br /> free (temp) ;</p> <p> return 1 ;<br /> }</p> <p>void Release_ (const Queue * const pqueue)<br /> {<br /> Node1 * 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>Node1 * Make_Node1 (const Item1 item1)<br /> {<br /> Node1 * new_node ;</p> <p> new_node = (Node1 *) malloc (sizeof (Node1)) ;<br /> if (NULL == new_node)<br /> return NULL ;<br /> new_node -> item1 = item1 ;<br /> new_node -> next = NULL ;</p> <p> return new_node ;<br /> }