分割故障的不稳定行为

以下是我在C实现b-tree中的代码。该代码有时会非常奇怪，因为它给出'分割故障'有时，如果我再次运行并提供相同的输入值，则可以正常工作。

也碰巧，我输入了1个值(例如500(现在应该是根值，但是代码还打印两个空的(nil(子值。

所有这些行为都是不稳定的，并非每次都会发生。这几乎从来没有第二次发生。我敢肯定，这与内存有关。有人可以建议我治愈吗？

预先感谢!!

#include <stdio.h>
#include <stdlib.h>
#define ORDER 4
struct node{
    int n;
    int keys[ORDER-1];
    struct node *children[ORDER];
};
struct toReturn{
    int result;
    struct node* nodeReturn;
};
struct node* splitNodeAndAdd(struct node* , int );
struct  node* insertInTree(struct node* , int );
struct toReturn* insertRecursive(struct node *, int );
struct node* splitNodeAndAddNode(struct node* , struct node* );

struct node* addElement(struct node *, int);
void printTree(struct node*, int);
void addAndSort(int *, int, int);
int checkLeaf(struct node* node);


int main(){
    int inputElement = 0;
    printf("Enter the element you want to add. Press 0 to quitn");
    scanf("%d",&inputElement);

    struct node * root;
    root = (struct node*) malloc(sizeof(struct node));
    while(inputElement != 0){
        root = addElement(root,inputElement);
        printTree(root,0);
        scanf("%d",&inputElement);
    }
    return 0;
}
struct node* addElement(struct node * rootNode, int inputElement){
    if(rootNode->n == 0){
        rootNode->keys[0] = inputElement;
        rootNode->n += 1;
        return rootNode;
    }
    else{
        rootNode = insertInTree(rootNode,inputElement);
        return rootNode;
    }
}

struct  node* insertInTree(struct node* node, int inputElement){
    if(checkLeaf(node) == 0){           //It is leaf node.
        if(node->n == ORDER - 1){
            struct node * temp = node;
            struct node *newRoot = (struct node*) malloc(sizeof(struct node));
            node = newRoot;
            newRoot->children[0] = temp;
            newRoot = splitNodeAndAdd(newRoot,inputElement);
            return newRoot;
        } else{
            addAndSort(node->keys,node->n,inputElement);
            node->n += 1;
        }
    } else{
        //recursive add . DO IT.
        struct toReturn * returnedValue = insertRecursive(node,inputElement);
        node = returnedValue->nodeReturn;
    }
    return node;
}

//Change split node and add before running. Won't work otherwise.
struct toReturn* insertRecursive(struct node *node, int inputElement){
    if(checkLeaf(node) == 0){
        if(node->n == ORDER - 1){
            struct node * temp = node;
            struct node *newRoot = (struct node*) malloc(sizeof(struct node));
            node = newRoot;
            newRoot->children[0] = temp;
            newRoot = splitNodeAndAdd(newRoot,inputElement);
            struct toReturn *value = (struct toReturn*) malloc(sizeof(struct toReturn));
            value->result = 0;
            value->nodeReturn = newRoot;
            return value; // Also send parameter to show its done.

        } else{
            addAndSort(node->keys,node->n,inputElement);
            node->n += 1;
            struct toReturn *value = (struct toReturn*) malloc(sizeof(struct toReturn));
            value->result = 1;
            value->nodeReturn = node;
            return value; // Also send parameter to show its done.
        }
    }
    else{
        int i = node->n;
        i -= 1;
        while( i >= 0 && inputElement < node->keys[i]){
            i -= 1;
        }
        i += 1;
        //Go to child node of this using 'i'
        struct toReturn* returnedValue = insertRecursive(node->children[i],inputElement);
        if(returnedValue->result == 0){
            //Now we have a node in returnedValue to be added to current node.
            //Check if current root is also going to be full.
            if(node->n == ORDER - 1){
                struct node* currentNode = node;
                struct node* nodeToAdd = returnedValue->nodeReturn;
                struct node* newRoot = (struct node*) malloc(sizeof(struct node));
                newRoot->children[0] = currentNode;
                newRoot = splitNodeAndAddNode(newRoot,nodeToAdd);

                struct toReturn* temp = (struct toReturn*) malloc(sizeof(struct toReturn));
                temp->result = 0;
                temp->nodeReturn = newRoot;// whatever is returned from splitNodeAndAddNode.
                return temp;
            } else{
                int k = i;
                for(k = node->n; k>i; k--){
                    node->keys[k] = node->keys[k-1];
                }
                for(k = node->n + 1; k > i; k--){
                    node->children[k] = node->children[k-1];
                }
                node->keys[i] = returnedValue->nodeReturn->keys[0];
                node->n += 1;
                node->children[i] = returnedValue->nodeReturn->children[0];
                node->children[i+1] = returnedValue->nodeReturn->children[1];
                returnedValue->result = 1;
                returnedValue->nodeReturn = node;
            }
        }else{
            node->children[i] = returnedValue->nodeReturn;
            returnedValue->nodeReturn = node;
        }
        return returnedValue;
    }
}
struct node* splitNodeAndAddNode(struct node* node, struct node* toAdd){
    struct node* leftChild = node->children[0];
    struct node* allChildren[ORDER+1];
    int i = 0;
    for(i = 0; i<ORDER; i++){
        allChildren[i] = leftChild->children[i];
    }
    int childrenCount = 0;
    int j = 0;
    struct node* rightChild = (struct node*) malloc(sizeof(struct node));
    int array[ORDER];
    for(i=0; i<ORDER - 1; i++){
        array[i] = leftChild->keys[i];
    }
    addAndSort(array,ORDER-1,toAdd->keys[0]);
    int addedPosition = 0;
    for(i=0; i<ORDER; i++){
        if(array[i] == toAdd->keys[0]){
            addedPosition = i;
        }
    }
    for(j=ORDER-1; j>= addedPosition; j--){
        allChildren[j+1] = allChildren[j];
    }
    allChildren[addedPosition] = toAdd->children[0];
    allChildren[addedPosition+1] = toAdd->children[1];

    int median = ORDER / 2;
    node->keys[0] = array[median];
    node->n += 1;
    //add left and right child of node.
    for(i = 0; i<median; i++){
        leftChild->keys[i] = array[i];
        leftChild->children[i] = allChildren[childrenCount];
        childrenCount++;
    }
    leftChild->children[i] = allChildren[childrenCount];
    childrenCount++;
    leftChild->n = median;
    for(i = median; i<ORDER-1; i++){
        leftChild->keys[i] = 0;
    }
    int k = 0;
    for(i = median+1; i<ORDER; i++){
        rightChild->keys[k] = array[i];
        rightChild->n += 1;
        rightChild->children[k] = allChildren[childrenCount];
        childrenCount++;
        k++;
    }
    rightChild->children[k] = allChildren[childrenCount];
    childrenCount++;
    node->children[0] = leftChild;
    node->children[1] = rightChild;
    return node;
}

struct node* splitNodeAndAdd(struct node* rootNode, int inputElement){
    struct node* leftChild = rootNode->children[0];
    struct node* rightChild = (struct node*) malloc(sizeof(struct node));
    int i = 0;
    int j = 0;
    int array[ORDER];
    for(i =0; i<ORDER-1;i++){
        array[i] = leftChild->keys[i];
    }
    addAndSort(array,ORDER-1,inputElement);
    int medianIndex = 0;
    for(i = 0; i<ORDER; i++){
        if(inputElement == array[i]){
            medianIndex = i;
            break;
        }
    }
    int median = ORDER / 2;
    for(j=0; j<median; j++){
        leftChild->keys[j] = array[j];
    }
    for(j=median; j<ORDER-1;j++){
        leftChild->keys[j] = 0;
    }
    leftChild->n = median;
    rootNode->keys[0] = array[median];
    rootNode->n += 1;
    int k = 0;
    for(j= median+1; j<ORDER; j++){
        rightChild->keys[k] = array[j];
        rightChild->n += 1;
        k++;
    }
    rootNode->children[0] = leftChild;
    rootNode->children[1] = rightChild;
    //Have to add all children if this is not leaf node.
    //Have to change rootNode[0] to long term picture.
    return rootNode;
}


void printTree(struct node *a, int level){
    printf("%d : ",level);
    for(int i=0; i<a->n; i++){
        printf("%d ",a->keys[i]);
    }
    printf("n");
    if(checkLeaf(a) == 1){
        for(int i=0; i <= a->n ; i++){
            printTree(a->children[i],level+1);
        }
    }else {
        return;
    }
}

int checkLeaf(struct node* node){
    int i = 0;
    if(node->children[i] != NULL){
        return 1;
    }
    return 0;
}

void addAndSort(int *array, int elementCount, int inputElement){
    int i = 0;
    for(i = elementCount-1; i >=0 && array[i] > inputElement; i--){       //else find the best
        array[i+1] = array[i];
    }
    array[i+1] = inputElement;
}

正如我在评论中所说的那样，这是对要查看的很多代码，特别是当您没有给我们足够的提示开始查看问题。

您可以在上为root节点分配的内存中详细介绍一下，您没有初始化它，我不确定是否关注。我认为我保留了内存，那为什么会导致这种不稳定的行为。我认为有时需要垃圾价值，我对吗？

我简要介绍了代码，我注意到了相同的模式。你刚才分配内存，但是在阅读内容之前，您不会初始化内存分配的内存。这产生了不确定的行为和您是什么观察，有时甚至有时不起作用，这是一个经典的迹象不确定的行为。由于行为不确定的本质，这是非常艰难，有时几乎不可能预测会发生什么。在多数情况下您需要做的就是找到不确定行为的来源。

在您的情况下，我要做的第一件事是查看您的malloc电话，看看哪里您启动内存。您没有这样做，所以我不再寻找更多错误，因为这很可能是您所有问题的来源。

当您使用malloc分配内存时，您只会从操作系统，不能保证在任何中初始化内存方式，这意味着内存具有Randon值。您在main

中做

root = (struct node*) malloc(sizeof(struct node));
while(inputElement != 0) {
    root = addElement(root,inputElement);
    ...
}

，然后addElement确实：

struct node* addElement(struct node * rootNode, int inputElement){
    if(rootNode->n == 0){
        rootNode->keys[0] = inputElement;
        ...
    } else {
        rootNode = insertInTree(rootNode,inputElement);
        ...
    }
}

如您所见，您已经为root节点分配了内存，但是root->n不是初始化，它的值是随机的，可能是0，但也可能是24或-12389。因此，您的代码已经在做不可预测的事情，因为查看代码，您不知道rootNode->keys[0] = inputElement;是否被执行，或rootNode = insertInTree(rootNode,inputElement);。就是这样不确定行为的性质。在幸运的情况下，rootNode->n是0，功能可能正常工作。

您必须做

root = malloc(sizeof *root);
if(root == NULL)
{
    fprintf(stderr, "No memory leftn");
    return 1;
}
// initializing the memory
root->n = 0;
memset(root->keys, 0, sizeof root->keys / sizeof root->keys[0]);
for(size_t i = 0; i < sizeof root->children / sizeof root->children[0]; ++i)
    root->children[i] = NULL;
while(inputElement != 0) {
    root = addElement(root,inputElement);
    ...
}

不要铸造malloc
检查始终，我的意思是始终 malloc/realloc
如果您错过了，请检查始终，我的意思是始终 malloc/realloc
避免使用sizeof(struct node)，改用sizeof *root，制作代码更健壮。
不要忘记free()内存。
如果您错过了，请不要忘记free()内存

我还建议您创建一个函数，使您返回一个新的分配初始化节点，否则您将一次又一次地重复相同的代码。这适用于您所有的malloc呼叫。

当然，在您的情况下，可以使用calloc避免初始化而不是malloc。calloc工作类似于malloc，但也设置了分配的内存到0。这是一个很棒的功能，因为如果您的内存必须是用0和NULL指针初始化¹，这节省了很多时间和你可以做

root = calloc(1, sizeof *root);
if(root == NULL)
{
    fprintf(stderr, "No memory leftn");
    return 1;
}
// initializing the memory with 0 is not needed
// anymore as calloc takes care of that
while(inputElement != 0) {
    root = addElement(root,inputElement);
    ...
}

在整个代码中进行此更改，这将消除许多不确定行为的来源。这并不意味着您的所有问题是

已解决。

脚注

¹传奇人物说有 NULL所在的建筑未解释为0，因此使用calloc初始化NULL指针可能会失败。但是我敢于找到人们使用的任何商业上成功的体系结构这些天有有效的情况。

相关内容

最新更新

热门标签：