Двоичное дерево в Си - Проблемы - PullRequest
Новая
       7

Двоичное дерево в Си - Проблемы

1 голос
/ 06 октября 2010 
typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst* b, int i)
{
                b=malloc(sizeof(b));
                b->value=i;
                b->leftChild = NULL;
                b->rightChild = NULL;
                printf("[%i]",b->value);
                return;
}
main()
{
  bst* b;
  insert(b,5);
  printf("[%i]",b->value);
}

Второй printf вызывает сбой сегментации, комментируя его, он работает нормально. Что я здесь делаю неправильно (не обращайте внимания на значения имен функций, т. Е. То, что вставка является функцией вставки для bst)? Не должно ли bst сохраняться в настройках вне функции вставки?

Ответы [ 6 ]

4 голосов
/ 06 октября 2010

Вам нужно передать указатель по ссылке, чтобы изменить, куда он указывает. 

// just add this & here in the function definition.
// That's the only change in all your code (for c++)
void insert(bst * &b, int i)

Или в C указатель указателя 

void insert(bst ** b, int i)
{
                *b=malloc(sizeof(*b));
                (*b)->value=i;
                (*b)->leftChild = NULL;
                (*b)->rightChild = NULL;
                printf("[%i]",(*b)->value);
                return;
}

Обратите внимание на изменения для разыменования указателя указателя.

Когда вы вызываете эту функцию, вам нужно взять адрес вашего bst *: 

insert(&b,5);
2 голосов
/ 07 октября 2010

Вместо того, чтобы изменить значение, верните новое значение b 

bst* insert(bst* b, int i)
{
    if (b == NULL)
    {
        bst* result = (bst*)malloc(sizeof(bst));
        result->value=i;
        result->leftChild = NULL;
        result->rightChild = NULL;
        printf("[%i]",b->value);
        return result;
    }

    if (i < b->value)
        b->left  = insert(b->left, i);
    else
        b->right = insert(b->right, i);
    return b;
}

int main()
{
  bst* b  = NULL;   // Initialise it to empty.
  b       = insert(b,5);
  printf("[%i]",b->value);
}
2 голосов
/ 06 октября 2010

Поскольку C выполняет передачу аргументов по значению, указатель, на который ссылается внутри insert(), является копией оригинала b. Память выделяется для переменной b внутри функции, но не для переменной в функции main().

например. 

# In main
b<main> = 0xOrigLoc
b<insert> = undefined

# In insert (before malloc)
b<main> = 0xOrigLoc
b<insert> = 0xOrigLoc

# After Malloc
b<main> = 0xOrigLoc
b<insert> = 0xNewLoc

Обратите внимание, что b<main> остается нетронутым. Вы только настраиваете копию b внутри функции.

Решение состоит в том, чтобы использовать указатель на указатель, как описано в предыдущем решении.

2 голосов
/ 06 октября 2010

Проблема в том, что b в main указывает на недопустимую память.b не изменяется на insert, потому что insert использует копию указателя.Вы должны решить эту проблему:

  • Сделайте "вставку", возьмите указатель на указатель
  • Выделите память перед вводом "вставки"

Потому чтопервый труднее читать (и понимать), я бы предпочел второй.Но от вас зависит, какой вариант вы выберете.

Выделение памяти до insert: 

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst* b, int i)
{
                // No malloc here
                b->value=i;
                b->leftChild = NULL;
                b->rightChild = NULL;
                printf("[%i]",b->value);
                return;
}
main()
{
  bst* b = (bst *)malloc(sizeof(bst));  // This line has changed
  insert(b,5);
  printf("[%i]",b->value);
}

Вариант с двойным указателем: 

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst** b, int i)
{
                *b = (bst *)malloc(sizeof(bst));  // This line has changed
                (*b)->value=i;
                (*b)->leftChild = NULL;
                (*b)->rightChild = NULL;
                printf("[%i]", (*b)->value);
                return;
}
main()
{
  bst* b;
  insert(&b,5);  // Now b is changed
  printf("[%i]",b->value);
}

Примечание 1 : у вас также есть неправильный malloc () - вы должны использовать sizeof(bst) вместо sizeof(b) в качестве размера.Это потому, что sizeof(b) == sizeof(bst *) == size of an address, что почти наверняка не то, что вам нужно.

Примечание 2 : не забудьте в конце вызвать free(b), чтобы избежать утечек памяти.

Примечание 3 : убедитесь, что malloc() не возвращается NULL.Редкий случай, но хорошая программа должна этого ожидать.

1 голос
/ 06 октября 2010

Ну, одна проблема - вы не типизируете указатель.

Линия: 

b=malloc(sizeof(b));

Должно быть: 

b=(bst*)malloc(sizeof(b));

Ваш код выдает ошибку при компиляции в gcc.

Это способ выявления и исправления ошибок в будущем:

Тестирование в GDB :

Полный код: 

#include <malloc.h>
#include <stdio.h>

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst* b, int i)
{
  b=(bst*)malloc(sizeof(b));
                b->value=i;
                b->leftChild = NULL;
                b->rightChild = NULL;
                printf("[%i]",b->value);
                return;
}
main()
{
  bst* b;
  insert(b,5);
  printf("[%i]",b->value);
}

Скомпилировано с

% g ++ -g main.cc

Побежал с

% gdb a.out

Команды GDB: 

b main.cc:211
run
print b
(output is: 0x0)
step
step
print b
(output is: 0x4f60010)
step
step
step
step
step
print b
(output is: 0x0)
quit

Это ясно указывает на то, что ваша переменная освобождается, когда функция выходит из области видимости.

Изменение кода на: 

#include <malloc.h>
#include <stdio.h>

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst* b, int i)
{
                b->value=i;
                b->leftChild = NULL;
                b->rightChild = NULL;
                printf("[%i]",b->value);
                return;
}
main()
{
  bst* b;
  b=(bst*)malloc(sizeof(bst));
  insert(b,5);
  printf("[%i]",b->value);
  free(b);
}

и перезапуск GDB с помощью следующих команд: 

b main.cc:21
run
s
(short for step)
print b
(output: 0x1aab010)
s
s
s
s
s
s
print b
(output: 0x1aab010)

Ваша проблема явно в объеме распределения. Перемещение выделения в основные исправления.

Yay ваша программа теперь работает!

Это должно дать вам представление о том, как использовать отладчик для решения подобных простых ошибок в будущем.

Редактировать

Как отметил один из операторов, ваша основная проблема заключается в том, что указатели, передаваемые функциям в c, рассматриваются как локальные объекты, поэтому при выходе из функции любая выделенная память для отдельных указателей отбрасывается в битовую корзину.

Двойные указатели позволяют вам фактически размещать внутри функций, вы просто должны быть осторожны и разыменовывать их по мере необходимости. Таким образом, ваш рабочий код также может быть: 

#include <malloc.h>
#include <stdio.h>

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst** b, int i)
{
                (*b)=(bst*)malloc(sizeof(bst));
                (*b)->value=i;
                (*b)->leftChild = NULL;
                (*b)->rightChild = NULL;
                printf("[%i]",(*b)->value);
                return;
}
main()
{
  bst* b;
  insert(&b,5);
  printf("[%i]",b->value);
  free(b);
}
0 голосов
/ 06 октября 2010

BST * B; объявляет указатель ... но не выделяет фактическую структуру. выделите и инициализируйте b, и вы перейдете к следующему шагу.

Это немного стиль обсуждения, но ваш основной должен выглядеть так же. 

main()
{
  bst *b;
  b = (bst*)malloc(sizeof(bst));
  /* more initialization */
  insert(b, 5);

  free(b);
}

или как это 

main()
{
  bst *b;
  bst_new(&b);
  insert(b, 5);
  bst_free(&b);
}
...