斜堆(一)之 C语言的实现

#ifndef _SKEW_HEAP_H_
#define _SKEW_HEAP_H_ typedef int Type; typedef struct _SkewNode{
Type key; // 关键字(键值)
struct _SkewNode *left; // 左孩子
struct _SkewNode *right; // 右孩子
}SkewNode, *SkewHeap; // 前序遍历"斜堆"
void preorder_skewheap(SkewHeap heap);
// 中序遍历"斜堆"
void inorder_skewheap(SkewHeap heap);
// 后序遍历"斜堆"
void postorder_skewheap(SkewHeap heap); // 获取最小值(保存到pval中)，成功返回0，失败返回-1。
int skewheap_minimum(SkewHeap heap, int *pval);
// 合并"斜堆x"和"斜堆y"，并返回合并后的新树
SkewNode* merge_skewheap(SkewHeap x, SkewHeap y);
// 将结点插入到斜堆中，并返回根节点
SkewNode* insert_skewheap(SkewHeap heap, Type key);
// 删除结点(key为节点的值)，并返回根节点
SkewNode* delete_skewheap(SkewHeap heap); // 销毁斜堆
void destroy_skewheap(SkewHeap heap); // 打印斜堆
void print_skewheap(SkewHeap heap); #endif

/**
* C语言实现的斜堆
*
* @author skywang
* @date 2014/03/31
*/ #include <stdio.h>
#include <stdlib.h>
#include "skewheap.h" /*
* 前序遍历"斜堆"
*/
void preorder_skewheap(SkewHeap heap)
{
if(heap != NULL)
{
printf("%d ", heap->key);
preorder_skewheap(heap->left);
preorder_skewheap(heap->right);
}
} /*
* 中序遍历"斜堆"
*/
void inorder_skewheap(SkewHeap heap)
{
if(heap != NULL)
{
inorder_skewheap(heap->left);
printf("%d ", heap->key);
inorder_skewheap(heap->right);
}
} /*
* 后序遍历"斜堆"
*/
void postorder_skewheap(SkewHeap heap)
{
if(heap != NULL)
{
postorder_skewheap(heap->left);
postorder_skewheap(heap->right);
printf("%d ", heap->key);
}
} /*
* 交换两个节点的内容
*/
static void swap_skewheap_node(SkewNode *x, SkewNode *y)
{
SkewNode tmp = *x;
*x = *y;
*y = tmp;
} /*
* 获取最小值
*
* 返回值：
* 成功返回0，失败返回-1
*/
int skewheap_minimum(SkewHeap heap, int *pval)
{
if (heap == NULL)
return -; *pval = heap->key; return ;
} /*
* 合并"斜堆x"和"斜堆y"
*
* 返回值：
* 合并得到的树的根节点
*/
SkewNode* merge_skewheap(SkewHeap x, SkewHeap y)
{
if(x == NULL)
return y;
if(y == NULL)
return x; // 合并x和y时，将x作为合并后的树的根；
// 这里的操作是保证: x的key < y的key
if(x->key > y->key)
swap_skewheap_node(x, y); // 将x的右孩子和y合并，
// 合并后直接交换x的左右孩子，而不需要像左倾堆一样考虑它们的npl。
SkewNode *tmp = merge_skewheap(x->right, y);
x->right = x->left;
x->left = tmp; return x;
} /*
* 新建结点(key)，并将其插入到斜堆中
*
* 参数说明：
* heap 斜堆的根结点
* key 插入结点的键值
* 返回值：
* 根节点
*/
SkewNode* insert_skewheap(SkewHeap heap, Type key)
{
SkewNode *node; // 新建结点 // 如果新建结点失败，则返回。
if ((node = (SkewNode *)malloc(sizeof(SkewNode))) == NULL)
return heap;
node->key = key;
node->left = node->right = NULL; return merge_skewheap(heap, node);
} /*
* 取出根节点
*
* 返回值：
* 取出根节点后的新树的根节点
*/
SkewNode* delete_skewheap(SkewHeap heap)
{
SkewNode *l = heap->left;
SkewNode *r = heap->right; // 删除根节点
free(heap); return merge_skewheap(l, r); // 返回左右子树合并后的新树
} /*
* 销毁斜堆
*/
void destroy_skewheap(SkewHeap heap)
{
if (heap==NULL)
return ; if (heap->left != NULL)
destroy_skewheap(heap->left);
if (heap->right != NULL)
destroy_skewheap(heap->right); free(heap);
} /*
* 打印"斜堆"
*
* heap -- 斜堆的节点
* key -- 节点的键值
* direction -- 0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。
*/
static void skewheap_print(SkewHeap heap, Type key, int direction)
{
if(heap != NULL)
{
if(direction==) // heap是根节点
printf("%2d is root\n", heap->key);
else // heap是分支节点
printf("%2d is %2d's %6s child\n", heap->key, key, direction==?"right" : "left"); skewheap_print(heap->left, heap->key, -);
skewheap_print(heap->right,heap->key, );
}
} void print_skewheap(SkewHeap heap)
{
if (heap != NULL)
skewheap_print(heap, heap->key, );
}

/**
* C语言实现的斜堆
*
* @author skywang
* @date 2014/03/31
*/ #include <stdio.h>
#include "skewheap.h" #define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) ) void main()
{
int i;
int a[]= {,,,,,,,};
int b[]= {,,,,,,};
int alen=LENGTH(a);
int blen=LENGTH(b);
SkewHeap ha,hb; ha=hb=NULL; printf("== 斜堆(ha)中依次添加: ");
for(i=; i<alen; i++)
{
printf("%d ", a[i]);
ha = insert_skewheap(ha, a[i]);
}
printf("\n== 斜堆(ha)的详细信息: \n");
print_skewheap(ha); printf("\n== 斜堆(hb)中依次添加: ");
for(i=; i<blen; i++)
{
printf("%d ", b[i]);
hb = insert_skewheap(hb, b[i]);
}
printf("\n== 斜堆(hb)的详细信息: \n");
print_skewheap(hb); // 将"斜堆hb"合并到"斜堆ha"中。
ha = merge_skewheap(ha, hb);
printf("\n== 合并ha和hb后的详细信息: \n");
print_skewheap(ha); // 销毁斜堆
destroy_skewheap(ha);
}