Доступ к неизвестному NULL-значению - PullRequest
Новая
       72

Доступ к неизвестному NULL-значению

0 голосов
/ 24 февраля 2020

это частичная программа дерева 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);
}

Теперь моя программа просто зависает, это не бесконечный вызов / l oop. Это, безусловно, значение доступа NULL. Но как это вообще возможно?

Ответы [ 2 ]

3 голосов
/ 24 февраля 2020

Отладка по форуму / 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);

, когда вставка не возвращает явно значение

2 голосов
/ 24 февраля 2020

Функция insert не возвращает указатель в случае r != NULL сбора возвращаемого значения, когда функция не возвращает ничего, это неопределенное поведение.

т.е. 

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

...