双链表:不兼容的指针类型

Question

目前我正在研究C中平衡B树的实现.我决定使用双链表但我遇到了一些问题.目前我收到第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

啊哈!这个问题很棘手.它与node结构的定义有关.成员parent,left,middle和right有型的struct node,但你typedef编的结构是node直接.我的猜测是GCC忽略了undefined struct node并希望它在其他地方被定义.

换句话说:类型node存在,但struct node不存在.因此,当您尝试将一个GCC 分配node给struct nodeGCC时,不知道该怎么做.所以改变

typedef struct {
    ...
} node;

至

typedef struct node {
    ...
} node;

虽然使用其他名称struct node比使用类型更明智node.

一些挑剔:

• 海湾合作委员会抱怨main不回复int(只是return 0;)
• 在splitLeaf你重新声明的参数int * middle,以node * middle与相同root.
• splitLeaf当不返回任何东西currentPos->parent不是NULL(尽管也许你还没有完成的功能还)