-2

我有以下用于在 bst 中插入节点的程序

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


struct node {
    int key;
    struct node * left;
    struct node * right;
};

struct node * insert(struct node *,int);

int main( int argc, const char *argv[]){
    struct node *root= malloc(sizeof(struct node ));

    int x;

    if(root==NULL){
        printf("mem error"); 
        return;
    }
    root=NULL;


    while(1){
        fprintf(stdout, "Enter the value of data\n" );
        fscanf(stdin,"%d",&x);
        root=insert(root,x);

    }


}

struct node * insert(struct node * root, int data ){

    if(root==NULL){
       struct node *root= malloc(sizeof(struct node ));
       root->key = data;
       printf("hiii\n");
       root->left = NULL;
       root->right = NULL;
       return root;
    }else{
       if(root->key >= data){
          root->left = insert(root->left,data);
       }else if(root->key <= data){
          root->right = insert(root->right,data);
       }
       return root;
    }
}

它运行良好..但是如果我在插入函数中注释 malloc 行..它在获取第一个值后会给我一个分段错误。这里发生了什么？？

4

5 回答 5

1

如果您注释掉为 分配内存的行，则root剩下

if(root==NULL) {
    //struct node *root= malloc(sizeof(struct node ));
    root->key = data;

它取消引用一个NULL指针。这会导致未定义的行为。在这一点上，任何事情都可能发生。崩溃将是最有用的，并且很可能发生但不能保证。如果您的问题是说您设法写入root->key，这是可能的，但不要指望它在不同的版本或不同的主机上工作（甚至在同一台计算机上不同运行相同的程序）。

于 2013-07-26T16:20:26.410 回答
1

您不能在插入函数中评论 malloc-line。的用途 malloc()是为新节点动态分配新内存以插入到链表中。

读取：void* malloc (size_t size);

分配内存块
分配一块大小字节的内存，返回一个指向块开头的指针。

因此，假设您在insert()（阅读评论）中评论/删除 malloc 行：

//struct node *root= malloc(sizeof(struct node ));
root->key = data;  // here illegal operation

root->left = NULL;  //   here illegal operation
root->right = NULL;  //  here illegal operation

那么root值将是垃圾，您可以访问并对进程未分配的垃圾地址执行读/写操作 - 内存非法操作。

您的代码将编译，因为在语法方面代码是正确的，但在运行时操作系统会检测到非法内存访问并可以终止您的代码。（有趣的是：当操作系统检测到进程违反内存权限时——对有效内存的无效访问会给出：SIGSEGV 并且对无效地址的访问会给出：SIGBUS）。--实际上这会导致未定义的行为。在最坏的情况下，您的程序似乎执行时没有任何故障，产生垃圾结果。

取第一个值后，它给了我一个分段错误。这里发生了什么？

正如我在上面解释的那样，删除malloc()会使您的程序以未定义的方式运行（阅读：未定义的行为）。如果程序以未定义的行为运行，您可以猜测会发生什么，在最坏的情况下，您的程序可能会在没有任何故障的情况下执行，或者可能会部分运行（这就是您所观察到的）。事情是当操作系统检测到非法内存访问并发送信号终止进程时。（可能是前五个随机垃圾值，root指向与我们的程序关联的内存，并且根据操作系统访问该内存不是非法运算符 - 而第五次随机值root是不属于进程的内存和操作系统检测到的内存上的读/写操作，因此您的代码最终以分段错误终止）。

于 2013-07-26T16:21:03.663 回答
1

malloc获取一些内存并返回其地址。如果您不将该地址存储在变量中，则该变量中包含 NULL (0)。当您存储到该地址（使用指针）时，它不是合法的内存位置，处理器会抱怨该错误。

于 2013-07-26T16:21:28.880 回答
0

你似乎喜欢把记忆扔出窗外！主要：

struct node *root= malloc(sizeof(struct node ));  // reserve some memory
if(root==NULL)                                    // make sure that memory is reserved
{
    printf("mem error");
    return;
}
root=NULL;                                        // loose the address of the memory

这应该只是：

struct node *root = NULL;
于 2013-07-26T16:27:22.030 回答
0

当 root 为 NULL 时，寻址 root->key 会使您处于内存中非常有问题的部分。您的程序在崩溃之前成功地完成了一次迭代。

于 2013-07-26T16:29:25.400 回答