c - 偏斜堆的C实现

我试图在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的隐式声明。
添加一个头文件，其中包含所有函数的原型，以及使用或定义这些函数的所有文件中的原型，以便编译器知道函数的类型。

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

应该是这样的

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

其中#include是一个*.c，但由于sk->root的隐式声明，假定返回一个struct node*。

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;

你应该返回的地方。int而不是。skewHeapMerge（起初我忽略了这一点）。
您在right中出错

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

在您使用left之后使用*right的位置。你必须在那个函数中交换最后两行。
在*left

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;

你在泄漏记忆。删除分配，因为如果使用了skewHeapRemoveFirst，则可以将n或free分配给它。