Программа вставки двоичного дерева поиска показывает ошибку сегментации

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

Ниже приведена реализация программы вставки для двоичного дерева поиска. Эта программа использует рекурсию для вставки заданного узла.

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

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

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

void
main ()
{
  struct node *root;
  root = NULL;

  insert (root, 2);
  insert (root, 3);
  insert (root, 4);
  insert (root, 5);
  insert (root, 6);
  insert (root, 7);
  printf ("%d", root->data);
}

struct node *
make (int x)
{
  struct node *temp;
  temp = (struct node *) malloc (sizeof (struct node *));
  temp->data = x;
  temp->left = NULL;
  temp->right = NULL;
  return temp;
}

struct node *
insert (struct node *root, int x)
{
  if (root == NULL)
  {
    root = make (x);
  }
  else
  {
    if (x <= root->data)
    {
      root->left = insert (root->left, x);
    }
    else if (x > root->data)
    {
      root->right = insert (root->right, x);
    }
  }
  return root;
}

c malloc dynamic-memory-allocation binary-search-tree
person Shashank Kumar Pandey    schedule 02.10.2019    source источник
comment
Что показывает ваша трассировка стека?   -  person Baldrickk    schedule 02.10.2019
comment
Тогда вам повезло! Ошибка сегментации направит ваш отладчик точно к той строке и инструкции, где произошла ошибка, и покажет вам значение каждой переменной и ячейки памяти в этой точке.   -  person Useless    schedule 02.10.2019
comment
root == NULL - root является локальным указателем, он не изменяет корень снаружи. Таким образом, root->data внутри printf есть NULL->data.   -  person KamilCuk    schedule 02.10.2019
comment
Только подумайте, вы выделяете память для root в insert с помощью make: как main увидит это?   -  person Paul Ogilvie    schedule 02.10.2019
comment
Спасибо - Камил Чук. Я должен был объявить root = insert(root,2).   -  person Shashank Kumar Pandey    schedule 02.10.2019

Ответы (2)


arrow_upward
2
arrow_downward

Проблема в том, что вы не присваиваете возвращаемое значение функции вставки корневому узлу.

Напишите

корень = вставить (корень, 2);

//...

Еще проблема в том, что вы неправильно выделяете память

temp = (struct node *) malloc (sizeof (struct node *));
                                       ^^^^^^^^^^^^^

Должно быть

temp = (struct node *) malloc (sizeof (struct node ));
                                       ^^^^^^^^^^^^^

Также внутри функции вставьте внутренний оператор if, который должен выглядеть так:

if (x < root->data)
{
    root->left = insert (root->left, x);
}
else
{
    root->right = insert (root->right, x);
}

Обратите внимание, что по стандарту C функция main без параметров должна быть объявлена ​​как

int main( void )
person Vlad from Moscow    schedule 02.10.2019
comment
Является ли приведение типа возврата malloc() бесполезным, как указано в: stackoverflow.com/questions/605845/ - person EsmaeelE; 02.10.2019
comment
@EsmaeelE Иногда это бесполезно, иногда делает код самодокументированным и позволяет избежать ошибки. - person Vlad from Moscow; 02.10.2019
comment
не могли бы вы объяснить истинный способ использования malloc(), особенно ситуацию, когда мы не должны приводить возвращаемые значения, и когда приведение является хорошим. - person EsmaeelE; 02.10.2019
comment
@EsmaeelE Например, можете ли вы сказать, действителен ли этот код p = malloc(sizeof(int[M][N] ));? Или что вы можете сказать о типе выделенной памяти в этом выражении p = malloc(sizeof(*p))? Между этим оператором и объявлением p могут быть десятки экранов. Собираетесь ли вы прокручивать исходный код вперед и назад, чтобы узнать, что такое объявление p? - person Vlad from Moscow; 02.10.2019
comment
Я обнаружил в двух случаях явное преобразование типов для возвращаемого типа malloc, то есть: p =(cast to type of p) malloc( sizeof( *p ) ) помогает сделать код ясным, и с этого момента мы знаем, что p указывает на какой тип памяти вместо поиска объявления p в других местах. - person EsmaeelE; 02.10.2019
comment
@EsmaeelE Более того, в C++ не разрешается присваивать указатель типа void * указателю другого типа. Используя кастинг, вы помогаете компилятору найти ошибку во время компиляции. - person Vlad from Moscow; 02.10.2019

arrow_upward
0
arrow_downward

Не игнорируйте возвращаемое значение insert:

void main(){
  struct node* root;
  root = NULL;

  root = insert(root,2);
  insert(root,3);
  insert(root,4);
  insert(root,5);
  insert(root,6);
  insert(root,7);

  printf("%d",root->data);
}

Другие моменты, которые вы, возможно, захотите рассмотреть:

  • Я не могу рекомендовать использовать void main(): в основном потому, что это нестандартно. Используйте int main(void) и верните 0.
  • Используйте printf("%p", root); для проверки: если значение равно 0x0, ваш указатель равен NULL.
  • Выполняя выделение памяти в подфункции, вы всегда должны проверять, удалось ли выделение.
struct node *
make (int x)
{
  struct node *temp;
  if ((temp = (struct node *) malloc (sizeof (struct node))) == NULL)
      return (NULL);
  temp->data = x;
  temp->left = NULL;
  temp->right = NULL;
  return temp;
}
person AugustinLopez    schedule 02.10.2019
comment
На любом другом пути insert просто возвращает исходный корень без изменений. Таким образом, всегда можно переназначить переменную root вызывающей стороны возвращаемому значению. - person Useless; 02.10.2019
comment
Если insert вернет NULL в случае неудачи, как, вероятно, и должно быть, вы потеряете указатель root. - person AugustinLopez; 02.10.2019
comment
Истинный! Но то, как это написано сейчас, предполагает, что вызывающая сторона должна сохранить возвращаемое значение, а вызывающая сторона этого не делает. И текущий код в любом случае отправляется в SEGV при сбое выделения - для этого требуется переработка. - person Useless; 02.10.2019
comment
Тоже верно! Мое решение определенно не идеально: хотя я хотел ответить на вопрос ОП и конкретную проблему с наименьшим количеством изменений кода, я не решил все проблемы с обработкой памяти. - person AugustinLopez; 02.10.2019
comment
Выполняя выделение памяти в подфункции, вы всегда должны проверять, было ли выделение выполнено успешно. и если вы работаете в ОС *nix, вы также должны попытаться выделить и ей, поскольку фактическое выделение памяти откладывается, а malloc() всегда возвращает True (такое удовольствие) быть полезным - person Baldrickk; 02.10.2019