Сопряженный список: Несовместимые типы указателей

Question

на данный момент я работаю над реализацией сбалансированного B-дерева в C. Я решил использовать двусвязные списки, но у меня возникли некоторые проблемы. На данный момент я получаю предупреждения для строк 94, 95 и 96, потому что, по-видимому, типы указателей несовместимы. Я действительно не понимаю, как и любая помощь будет принята с благодарностью.

#include <stdio.h> 
#include <stdlib.h> 

typedef struct { 
    int data1; 
    int data2; 
    int data2exists; // no: 0 , yes: 1 
    struct node * parent; 
    struct node * left; 
    struct node * middle; 
    struct node * right; 
} node; 

node * insert(int *, node *, node *); 
void getInput(int *); 
node * createNode(int *); 
void quickSwap(node *, int *, int *, int *, int *); 
node * splitLeaf(int *, int *, int *, node *, node *); 
void printTree(node *); 

void main() { 
    int input; 
    getInput(&input); 
    node * root = createNode(&input); 
    getInput(&input); 
    insert(&input, root, root); // returns current pos 
    getInput(&input); 
    insert(&input, root, root); // returns current pos 
    getInput(&input); 
    insert(&input, root, root); // returns current pos 
    printTree(root); 
} 

node * insert(int * input, node * root, node * currentPos) { 
    printf("data1: [%i], data2: [%i], d2exists: [%i], input: [%i]\n", currentPos->data1, currentPos->data2, currentPos->data2exists, *input); 
    if (currentPos->left == NULL && currentPos->middle == NULL && currentPos->right == NULL) { 
     // no children 
     if (*input > currentPos->data1 && currentPos->data2exists == 0) { 
      // data1 < input, no data2 

      currentPos->data2 = *input; 
      currentPos->data2exists = 1; 
      return(currentPos); 
      // printf("CASE1: data1 < input, no data2, no children\n"); 
     } 
     if (*input < currentPos->data1 && currentPos->data2exists == 0) { 
      // data1 > input, no data2 

      currentPos->data2 = currentPos->data1; 
      currentPos->data1 = *input; 
      currentPos->data2exists = 1; 
      return(currentPos); 
      // printf("CASE2: data1 > input, no data2, no children\n"); 
     } 
     if (currentPos->data2exists == 1) { 
      // data2 exists 
      int smallest; 
      int middle; 
      int largest; 
      quickSwap(currentPos, input, &smallest, &middle, &largest); 
      printf("s: [%i] m: [%i] l: [%i]\n", smallest, middle, largest); 
      root = splitLeaf(&smallest, &middle, &largest, currentPos, root); 
     } 
    } 
    return(currentPos); 
} 

void printTree(node * root) { 
    if (root->parent != NULL) { 
     printf("printTree() did not receive root!!!!\n"); 
     return; 
    } 
    else { 
     printf("%i || %i", root->data1, root->data2); 
     printf("\n"); 
     // printf("%i || %i", root->left->data1, root->left->data2); 
     // printf("\t\t"); 
     // printf("%i || %i", root->middle->data1, root->middle->data2); 
     // printf("\t\t"); 
     // printf("%i || %i", root->right->data1, root->right->data2); 
     // printf("\n"); 
    } 
} 

node * splitLeaf(int * smallest, int * middle, int * largest, node * currentPos, node * root) { 
// this function needs to return root! 
    if (currentPos->parent == NULL) { 
     // currentPos is root 
     // create a parent with median 
     node * root = createNode(middle); 
     node * left = createNode(smallest); 
     node * middle = createNode(largest); 
     // genau hier gehts weiter! hier müssen root, left und, middle verknüpft werden! 
     root->left = left; 
     root->middle = middle; 
     left->parent = middle->parent = root; 
     // printf("root-addr: %i, left->parent: %i\n", root, left->parent); 
     return(root); 
    } 
} 

void quickSwap(node * currentPos, int * input, int * smallest, int * middle, int * largest) { 
    // writes values to *smallest, *middle and *largest ordered by size 

    if (currentPos->data1 > currentPos->data2) { 
     *smallest = currentPos->data2; 
     *middle = currentPos->data1; 
    } 
    else { 
     *smallest = currentPos->data1; 
     *middle = currentPos->data2; 
    } 
    if (*input < *smallest) { 
     *largest = *middle; 
     *middle = *smallest; 
     *smallest = *input; 
    } 
    else if (*input < *middle) { 
     *largest = *middle; 
     *middle = *input; 
    } 
    else { 
     *largest = *input; 
    } 
} 

node * createNode(int * input) { 
    node * ptr = (node*) malloc(sizeof(node)); 
    ptr->data1 = * input; 
    ptr->data2 = 0; 
    ptr->data2exists = 0; 
    ptr->parent = NULL; 
    ptr->left = NULL; 
    ptr->middle = NULL; 
    ptr->right = NULL; 
    return(ptr); 
} 

void getInput(int * input) { 
    printf("Enter a number\n"); 
    scanf(" %i",input); 
} 

Answer 1

Aha! Проблема сложная. Это связано с определением вашей структуры node. Члены parent, left, middle и right имеют тип struct node, но вы typedef ed структура должна быть node напрямую. Я предполагаю, что GCC игнорирует неопределенный struct node и надеется, что он определен где-то в другом месте.

Иными словами: тип node существует, но struct node нет. Поэтому, когда вы пытаетесь присвоить nodestruct node, GCC не знает, что делать. Меняем

typedef struct { 
    ... 
} node; 

в

typedef struct node { 
    ... 
} node; 

Хотя это может быть разумнее использовать другое имя для struct node, чем тип node.

Некоторые nitpicks:

• GCC жалуется, что main не возвращать int (только return 0;)
• В splitLeaf вы повторного объявления аргументы int * middle в node * middle и то же с root.
• splitLeaf не возвращает ничего, если currentPos->parent не NULL (хотя, возможно, вы еще не закончили функцию еще)