学步园

  虽然今天距昨天只有一天, 我还是成长了好多.对于昨天不懂的问题,今天搞清楚了大半.总体来说,总结起来,...都写到代码里了.还要去看数学,就不多写了.呵呵.总之,明天会更好./* skew-heap.h -- 斜堆头文件 */<br /> #define INSERT(heap, item) (heap = Insert (heap, item))<br /> #define DELETEMIN(heap, pnode) (heap = DeleteMin (heap, pnode))<br /> #define BUILD(heap, parray, size) (heap = Build (parray, size))</p> <p>/* 数据类型定义 */</p> <p>typedef int Item ;<br /> typedef struct node<br /> {<br /> Item item ;<br /> struct node * left ;<br /> struct node * right ;<br /> } Node ;<br /> typedef Node * Heap ;</p> <p>/* 接口函数声明 */</p> <p>/* 操作: 创建并将一个斜堆置为空 */<br /> /* 操作前: pheap 指向一个斜堆 */<br /> /* 操作后: 如果内存分配成功, 该斜堆被初始为空, 返回1; 否则返回0 */<br /> int Create (Heap * const ph) ;</p> <p>/* 操作: 确定一个斜堆是否为空 */<br /> /* 操作前: h 是一个已初始化的斜堆 */<br /> /* 操作后: 如果该堆为空, 返回1; 否则返回0 */<br /> int HeapIsEmpty (const Heap h) ;</p> <p>/* 操作: 合并两个斜堆并返回合并后的斜堆 */<br /> /* 操作前: h1, h2 是两个已初始化的斜堆 */<br /> /* 操作后: 合并二者, 返回新堆 */<br /> Heap Merge (const Heap h1, const Heap h2) ;</p> <p>/* 操作: 向斜堆中插入一个节点 */<br /> /* 操作前: h 是一个已初始化的斜堆, item 是新节点的数据 */<br /> /* 操作后: 将新节点插入到堆中, 返回新堆 */<br /> Heap Insert (Heap h, const Item item) ;</p> <p>/* 操作: 删除斜堆中最小关键字的节点 */<br /> /* 操作前: heap 是一个已初始化的斜堆, pnode 是承载最小关键字节点的指针变量 */<br /> /* 操作后: 如果堆不为空, 删除最小关键字的节点, 使 pnode 指向该节点, 返回新堆; 否则返回原堆 */<br /> Heap DeleteMin (Heap h, Node * const pnode) ;</p> <p>/* 操作: 查找并返回指向斜堆中具有指定关键字节点的指针 */<br /> /* 操作前: h 是一个已初始化的斜堆, item 指示被查找的关键字 */<br /> /* 操作后: 如果找到该节点, 返回指向该节点的指针; 否则返回NULL */<br /> Node * Find (const Heap h, const Item item) ;</p> <p>/* 操作: 根据一个数据数组构建并返回一个斜堆堆 */<br /> /* 操作前: array 是一个数据数组, size 指示数组的大小 */<br /> /* 操作后: 如果内存分配成功, 创建并返回该堆; 否则返回NULL */<br /> Heap Build (const Item array[], const int size) ;</p> <p>/* 操作: 清空一个斜堆所占内存空间 */<br /> /* 操作前: h 是一个已初始化的斜堆 */<br /> /* 操作后: 该堆所占内存空间被释放 */<br /> void Release (const Heap h) ;