C实现斜堆的(C implementation of skew heap)

我试图实现在C斜堆，但我的代码不能编译。我不是在C经历和没有创建任何类型的C.堆，这就是为什么我不知道如何解决它，我希望有人能指出我朝着正确的方向。我一直在阅读文章对斜堆，这是我走到这一步，使用我在网上找到的算法。提前致谢。

typedef struct node
{
int value;
struct node * root;
struct node * leftchild;
struct node * rightchild;
} Node;

struct skewHeap
{
    struct node * root;
};

void skewHeapInit (struct skewHeap * sk)
{
    sk->root = 0;
}

void skewHeapAdd (struct skewHeap *sk)
{
    struct node *n = (struct node *) malloc(sizeof(struct node));
    assert(n != 0);
    n->value = 0;
    n->leftchild = 0;
    n->rightchild = 0;
    line 185. s->root = skewHeapMerge(s->root, n);
}

void skewHeapRemoveFirst (struct skewHeap *sk)
{
    struct node * n = sk->root;
    free(n);
    sk->root = skewHeapMerge(n->leftchild, n->rightchild);
}

line 196. struct node * skewHeapMerge(struct node *left, struct node *right)
{
    struct node *temp = (struct node *) malloc(sizeof(struct node));

    if (left == NULL) 
        return *right;

    if (right == NULL) 
        return *left;

    if (left->value < right-> value)
    {
        temp = left->leftchild;
        left->leftchild = skewHeapMerge(left->rightchild, right);
        left->rightchild = temp;
        return left;
    }
    else
    {
        temp = right->rightchild;
        right->rightchild = skewHeapMerge(right->leftchild, left);
        right->leftchild = temp;
        return right;
    }
}

这些都是汇编错误，我在那一刻得到：

program.c: In function ‘skewHeapAdd’:
program.c:185: warning: implicit declaration of function ‘skewHeapMerge’
program.c:185: warning: assignment makes pointer from integer without a cast
program.c: In function ‘skewHeapRemoveFirst’:
program.c:191: warning: assignment makes pointer from integer without a cast
program.c: At top level:
program.c:196: error: conflicting types for ‘skewHeapMerge’
program.c:185: note: previous implicit declaration of ‘skewHeapMerge’ was here
program.c: In function ‘skewHeapMerge’:
program.c:202: error: incompatible types when returning type ‘struct node’ but ‘struct   node *’ was expected
program.c:205: error: incompatible types when returning type ‘struct node’ but ‘struct node *’ was expected

关于编译器错误，

program.c: In function ‘skewHeapAdd’:
program.c:185: warning: implicit declaration of function ‘skewHeapMerge’
program.c:185: warning: assignment makes pointer from integer without a cast

告诉你，没有原型的skewHeapMerge是在范围skewHeapAdd定义，因此（编译器显然是工作在C89模式，但幸运的是警告一下吧），编译器假设与返回类型的隐式声明int为skewHeapMerge 。

添加与原型为您的所有功能的头文件，并#include在所有*.c这些函数使用或定义，这样编译器知道类型的功能文件。

program.c: In function ‘skewHeapRemoveFirst’:
program.c:191: warning: assignment makes pointer from integer without a cast

这应该是行

sk->root = skewHeapMerge(n->leftchild, n->rightchild);

其中sk->root是一个struct node* ，但是由于隐式声明skewHeapMerge ，即假定为返回一个int 。

program.c: At top level:
program.c:196: error: conflicting types for ‘skewHeapMerge’
program.c:185: note: previous implicit declaration of ‘skewHeapMerge’ was here

这里的编译器发现的定义skewHeapMerge给人一种矛盾的从隐式声明的一个。

program.c: In function ‘skewHeapMerge’:
program.c:202: error: incompatible types when returning type ‘struct node’ but ‘struct   node *’ was expected
program.c:205: error: incompatible types when returning type ‘struct node’ but ‘struct node *’ was expected

这是行

if (left == NULL) 
    return *right;

if (right == NULL) 
    return *left;

在这里你应该回到right RESP。 left的，而不是*right RESP。 *left （我忽视的是，在第一次）。

你有一个错误skewHeapRemoveFirst

void skewHeapRemoveFirst (struct skewHeap *sk)
{
    struct node * n = sk->root;
    free(n);
    sk->root = skewHeapMerge(n->leftchild, n->rightchild);
}

在您使用n后您free d它。你在功能交换的最后两行。

而在skewHeapMerge

struct node * skewHeapMerge(struct node *left, struct node *right)
{
    struct node *temp = (struct node *) malloc(sizeof(struct node));

    if (left == NULL)
        return *right;

    if (right == NULL)
        return *left;

您正在泄漏内存。取出分配，因为如果temp使用的一切，你要么分配left->leftchild或right->rightchild它。