斜堆的C实现

Question

我试图在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

Answer 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的原型不在定义skewHeapAdd的范围内，因此(编译器显然以C89模式运行，但谢天谢地对此发出警告)，编译器为skewHeapMerge假设一个返回类型为int的隐式声明。

添加一个头文件，其中包含所有函数的原型，以及使用或定义这些函数的所有*.c文件中的#include，以便编译器了解函数的类型。

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。CCD_ 13代替CCD_。*left(一开始我忽略了这一点)。

---

您在skewHeapRemoveFirst中有一个错误

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

在freed之后使用n。您必须交换该函数中的最后两行。

在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分配给它。