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在範圍上哪裏因此（定義編譯器明顯在C89模式下運行，但幸運地警告它），編譯器假設返回t的隱式聲明ype int for skewHeapMerge。

爲所有函數添加一個包含原型的頭文件，並在所有使用或定義這些函數的文件中使用#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 RESP。 left而不是*right resp。 *left（我首先忽略了）。

---

，你以後你free d它使用n你有skewHeapRemoveFirst

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

一個錯誤。你必須交換該函數中的最後兩行。

而且在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。