2

目前我正在用 C 实现平衡 B-Tree。我决定使用双向链表，但遇到了一些问题。目前我收到第 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);
}
4

1 回答 1

5

啊哈！这个问题很棘手。它与node结构的定义有关。成员parent,和是类型left，但您直接将结构编辑为。我的猜测是 GCC 忽略了未定义并希望它在其他地方定义。middlerightstruct nodetypedefnodestruct node

换句话说：类型node存在，但struct node不存在。因此，当您尝试将 a 分配node给struct nodeGCC 时，您不知道该怎么做。所以改变

typedef struct {
    ...
} node;

至

typedef struct node {
    ...
} node;

尽管使用另一个名称可能struct node比 type更明智node。

一些挑剔：

  • GCC 抱怨main不返回int(just return 0;)
  • 在splitLeaf您重新声明与 .相同的参数int * middle时。node * middleroot
  • splitLeaf不返回时不返回任何内容currentPos->parent（NULL尽管您可能还没有完成该功能）
于 2013-06-08T14:13:44.010 回答