代码之家 › 专栏 › 技术社区 › Gauraang Khurana

C语言中分段错误的不稳定行为

segmentation-fault memory-leaks memory-management memory c

Gauraang Khurana · 技术社区 · 7 年前

下面是我在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 quit\n");
    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;
}

1 回复 | 直到 7 年前

Pablo 7 年前

正如我在评论中所说的,这需要检查的代码太多了,特别是当您没有给我们足够的提示,从哪里开始看问题。

你能详细说明一下吗 为main中的根节点分配了内存,您没有初始化它 ,我不确定我是否遵循。我想我保留了记忆,那为什么它会导致如此不稳定的行为呢。我想它有时需要垃圾值,对吗?

我简单地查看了代码,发现了相同的模式。你只是分配内存,但在读取内容之前不初始化内存已分配内存的。这会产生未定义的行为和你是什么观察,有时工作,有时不工作,这是未定义的行为。由于未定义行为的性质,它非常很难预测会发生什么,有时几乎是不可能的。在大多数情况下您所需要做的就是找到未定义行为的来源。

对你来说,我做的第一件事就是 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或 -所以你的代码已经在做一些不可预测的事情了查看代码,您无法知道 rootNode->keys[0] = inputElement; 已执行,或 rootNode = insertInTree(rootNode,inputElement); .这就是问题所在未定义行为的性质。如果幸运的话 rootNode->n 为0,则功能可能正常工作。

你必须这样做

root = malloc(sizeof *root);

if(root == NULL)
{
    fprintf(stderr, "No memory left\n");
    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);
    ...
}

Don't cast malloc
检查总是 ,我的意思是总是的返回值 马洛克 / realloc
如果你错过了,检查一下总是 ,我的意思是总是的返回案例 马洛克 / realloc公司
避免使用 sizeof(struct node) 使用 sizeof *root 相反,生成代码更加健壮。
别忘了 free() 内存。
万一你错过了,别忘了 免费() 内存

我还建议您创建一个函数,返回一个新的已分配+已初始化节点,否则将一次又一次重复相同的代码。这适用于你所有的 马洛克 呼叫。

当然,在您的情况下,可以通过使用 calloc 而不是 马洛克 。 分配 工作原理如下 马洛克 但它也设置了分配的内存为0。这是一个很好的特性,因为如果你的记忆已初始化为0和 NULL 指针 ^1. ,这节省了大量时间你可以这样做

root = calloc(1, sizeof *root);

if(root == NULL)
{
    fprintf(stderr, "No memory left\n");
    return 1;
}

// initializing the memory with 0 is not needed
// anymore as calloc takes care of that

while(inputElement != 0) {
    root = addElement(root,inputElement);
    ...
}

在整个代码中进行此更改,这将消除许多未定义行为的来源。这并不意味着你所有的问题都是但已解决。

脚注

^1. 传说那里有很多建筑 无效的 是未解释为0,因此使用 分配 用于初始化 无效的 指针可能会失败。但我敢说任何人都能找到人们使用的商业上成功的建筑在这种情况下,这些天的工作效率很高。