1

我正在尝试在 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
4

1 回答 1

1

关于编译器错误，

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的范围内没有 of 的原型skewHeapAdd，因此（编译器显然在 C89 模式下运行，但谢天谢地对此发出警告），编译器假设有一个返回类型int为 for的隐式声明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是 a struct node*，但由于 的隐式声明skewHeapMerge，假定返回 a 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。left而不是*right相应的。*left（起初我忽略了这一点）。

你有一个错误skewHeapRemoveFirst

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

dn后在哪里使用。free您必须交换该函数中的最后两行。

而在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;

你正在泄漏内存。删除分配，因为 iftemp完全被使用，你分配left->leftchild或分配right->rightchild给它。

于 2012-11-12T23:34:56.203 回答