偏斜堆的C实现 [英] C implementation of skew heap

问题描述

我正在尝试在C中实现偏斜堆，但是我的代码无法编译.我不是C语言方面的经验丰富者，也从未在C语言中创建任何类型的堆.这就是为什么我不知道如何解决它的原因，我希望有人可以为我指出正确的方向.我一直在阅读有关偏斜堆的文章，这是我到目前为止使用在网上找到的算法得到的信息.提前致谢.

I'm trying to implement a skew heap in C, but my code doesn't compile. I'm not that experienced in C and never created any type of heap in C. That is why I don't know how to fix it, I'm hoping someone can point me the right direction. I have been reading articles about the skew heap and this is what I got so far using the algorithms I have found online. Thanks in Advance.

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;
    }
}

这些是我目前遇到的编译错误:

These are the compilations errors I'm getting at the moment:

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

告诉您在定义skewHeapAdd的范围内没有skewHeapMerge的原型，因此(编译器显然在C89模式下运行，但值得警告的是)，编译器假定隐式声明的返回类型为用于skewHeapMerge.

tells you that no prototype of skewHeapMerge is in scope where skewHeapAdd is defined, hence (the compiler apparently operates in C89 mode, but thankfully warns about it), the compiler supposes an implicit declaration with return type int for skewHeapMerge.

添加具有所有功能原型的头文件，并在使用或定义这些功能的所有*.c文件中添加#include头文件，以便编译器知道这些功能的类型.

Add a header file with prototypes for all your functions, and #include that in all *.c files where these functions are used or defined, so that the compiler knows the types of the functions.

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.

where sk->root is a struct node*, but due to the implicit declaration of skewHeapMerge, that is assumed to return an 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的定义给出的类型与隐式声明中的类型冲突.

here the compiler finds that the definition of skewHeapMerge gives a type conflicting with the one from the implicit declaration.

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的位置. left而不是*right *left(起初我忽略了它.)

where you ought to return right resp. left instead of *right resp. *left (I overlooked that at first).

您在skewHeapRemoveFirst

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

在free d之后在其中使用n的位置.您必须交换该函数的最后两行.

where you use n after you freed it. You have to exchange the last two lines in that function.

在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.

you are leaking memory. Remove the allocation, since if temp is used at all, you assign either left->leftchild or right->rightchild to it.

这篇关于偏斜堆的C实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！