Implémentation en C du tas de désalignement

Question

J'essaye d'implémenter un tas de décalage en C, mais mon code ne compile pas. Je ne suis pas très expérimenté en C et je n'ai jamais créé de tas en C. C'est pourquoi je ne sais pas comment le réparer, j'espère que quelqu'un pourra me diriger dans la bonne direction. J'ai lu des articles sur le tas de biais et c'est ce que j'ai obtenu jusqu'à présent en utilisant les algorithmes que j'ai trouvés en ligne. Merci d'avance.

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

Ce sont les erreurs de compilations que je reçois en ce 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 

Answer 1

En ce qui concerne les erreurs du compilateur,

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 

vous dit qu'aucun prototype de skewHeapMerge est portée où skewHeapAdd est défini, par conséquent (le compilateur fonctionne apparemment en mode C89, mais avertit heureusement à ce sujet), le compilateur suppose une déclaration implicite avec retour t ype int pour skewHeapMerge.

Ajoutez un fichier d'en-tête avec des prototypes pour toutes vos fonctions, et #include dans tous les fichiers *.c où ces fonctions sont utilisées ou définies, afin que le compilateur connaisse les types de fonctions.

program.c: In function ‘skewHeapRemoveFirst’: 
program.c:191: warning: assignment makes pointer from integer without a cast 

qui devrait être la ligne

sk->root = skewHeapMerge(n->leftchild, n->rightchild); 

où sk->root est un struct node*, mais en raison de la déclaration implicite de skewHeapMerge, qui est supposée retourner un 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 

ici le compilateur trouve que la définition de skewHeapMerge donne un type en conflit avec celui de la déclaration implicite.

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 

qui est pour les lignes

if (left == NULL) 
    return *right; 

if (right == NULL) 
    return *left; 

où vous devez retourner right resp. left au lieu de *right resp. *left (j'ai négligé cela au début).

---

Vous avez une erreur dans skewHeapRemoveFirst

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

où vous utilisez n après que vous free d it. Vous devez échanger les deux dernières lignes dans cette fonction.

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

vous fuite de mémoire. Supprimez l'allocation, puisque si temp est utilisé, vous lui attribuez left->leftchild ou right->rightchild.