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  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 。

添加包含所有函数原型的头文件，并在所有使用或定义这些函数的*.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; 

你应该在哪里返回 left而不是*right分别。 *left （我先忽略了）。

---

你在skewHeapRemoveFirst犯了一个错误

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

你free后使用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或left->leftchild 。