访问了未知的 NULL 值

Question

这是一个 AVL 树的部分程序，但现在它更像是一个 BST

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
typedef struct node node;

struct node
{
    int data;
    int height;
    node *left;
    node *right;
} *root = NULL, *temp = NULL;

int max(int n1, int n2)
{
    return n1 > n2 ? n1 : n2;
}

node *new_node(int value)
{
    temp = (node *)malloc(sizeof(node));
    temp->data = value;
    temp->left = NULL;
    temp->right = NULL;
    temp->height = 0;
    return temp;
}
int get_height(node *x)
{
    if (x == NULL)
    {
        return -1;
    }

    return x->height;
}

node *insert(node *r, int value)
{
    if (r == NULL)
    {
        return new_node(value);
    }
    else
    {
        if (value < r->data)
            r->left = insert(r->left, value);
        else
            r->right = insert(r->right, value);

        int height = max(get_height(r->left), get_height(r->right)) + 1;
}

void inorder(node *r)
{
    if (r == NULL)
        return;
    inorder(r->left);
    printf("node = %d, height = %d\n", r->data, r->height);
    inorder(r->right);
}

void main()
{
    root = insert(root, 10);
    root = insert(root, 20);
    inorder(root);
}

此程序的输出如下，因为我没有访问任何 NULL 值 -

node = 10, height = 1
node = 20, height = 0

在添加一行之后，我正在访问一个 NULL 值

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
typedef struct node node;

struct node
{
    int data;
    int height;
    node *left;
    node *right;
} *root = NULL, *temp = NULL;

int max(int n1, int n2)
{
    return n1 > n2 ? n1 : n2;
}

node *new_node(int value)
{
    temp = (node *)malloc(sizeof(node));
    temp->data = value;
    temp->left = NULL;
    temp->right = NULL;
    temp->height = 0;
    return temp;
}
int get_height(node *x)
{
    if (x == NULL)
    {
        return -1;
    }

    return x->height;
}

node *insert(node *r, int value)
{
    if (r == NULL)
    {
        return new_node(value);
    }
    else
    {
        if (value < r->data)
            r->left = insert(r->left, value);
        else
            r->right = insert(r->right, value);

        int height = max(get_height(r->left), get_height(r->right)) + 1;
    int balance_factor = get_height(r->left)- get_height(r->right); // extra line added

  }
}

void inorder(node *r)
{
    if (r == NULL)
        return;
    inorder(r->left);
    printf("node = %d, height = %d\n", r->data, r->height);
    inorder(r->right);
}

void main()
{
    root = insert(root, 10);
    root = insert(root, 20);
    inorder(root);
}

现在我的程序只是挂起，它不是无限调用/循环。它肯定是 NULL 值访问。但这怎么可能呢？

Answer 1

函数 insert 不 return 在 r != NULL 收集一个 return 值的情况下函数 return 没有任何指针 return 未定义行为。

即

root = insert(root, 10);//it is returning valid pointer
root = insert(root, 20);//unknown value copied to root

请按如下方式更新您的代码，

node *insert(node *r, int value)
{
    if (r == NULL)
    {
        return new_node(value);
    }
    //rest of the logic     
    return r;//missing from both of your snippet
}

有关 UB

的更多详细信息，请参阅

Answer 2

forum/Q&A 的调试从来都没有效率。使用调试器：

例如 https://onlinegdb.com/S1ZansZNU

Reading symbols from a.out...done.                                                                                   
/usr/share/gdb/gdbinit: No such file or directory.                                                                   
(gdb) run                                                                                                            
Starting program: /home/a.out                                                                                        

Program received signal SIGSEGV, Segmentation fault.                                                                 
0x0000000000400703 in inorder (r=0xffffffff) at main.c:62                                                            
62          inorder(r->left);                                                                                        
(gdb)

r 不是 NULL，但也不是有效地址。

问题明显在：

root = insert(root, 10);

当插入未明确 return 值时

访问了未知的 NULL 值

Unknown NULL value accessed

c

null

binary-search-tree

nullreferenceexception