Блог

Главная - Вопросы по программированию - Удаление элементов из двоичного дерева поиска на основе условия

Удаление элементов из двоичного дерева поиска на основе условия

#c #recursion #data-structures #binary-search-tree #recursive-datastructures

Вопрос:

У меня есть структура, в которой хранится имя файла и день последнего доступа к нему.

 typedef struct sFile {
   int lastAccess;
   char name[50];
} File;

typedef struct sNode {
   File info;
   struct sNode* left;
   struct sNode* right;
} Node;

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

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

Я считаю, что мои функции вставки и удаления верны, но на всякий случай я оставляю их ниже.

Функции вставки и удаления:

 void insert(Node **root, File value) {
   if(*root == NULL) {
      Node *celula = getNode();
      
      if(celula == NULL) {
         printf("nERRO: Falha na alocacao de memoria. Encerrando programa.n");
         exit(1);
      }

      celula->left = NULL;
      celula->right = NULL;
      celula->info = value;
      *root = celula ;
   } else {
      if(strcmp(value.name, (*root)->info.name) < 0) {
         insert(amp;(*root)->left, value);
      } else {
         insert(amp;(*root)->right, value);
      }
   }
};

Node* deleteNode(Node *root, char name[50]) {
    if (root == NULL)
        return root;
 
    if (strcmp(name, root->info.name) < 0)
        root->left = deleteNode(root->left, name);
 
    else if (strcmp(name, root->info.name) > 0)
        root->right = deleteNode(root->right, name);
 
    else {
        if (root->left == NULL) {
            Node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            Node *temp = root->left;
            free(root);
            return temp;
        }
 
        Node *temp = minValueNode(root->right);
 
        root->info = temp->info;
 
        root->right = deleteNode(root->right, temp->info.name);
    }
    return root;
}

Функция очистки деревьев:

 Node* clear(Node *root, int date) {
   if(root == NULL) {
      return NULL;
   }

   if(root->info.lastAccess <= date) {
      root = deleteNode(root, (root)->info.name);
   }

   root = clear(root->left, date);
   root = clear(root->right, date);

   return root;
}

сообщение об ошибке:

 [1]    39970 segmentation fault (core dumped)  ./7.out

У кого-нибудь есть какие-либо идеи о том, что может быть причиной этой ошибки и как я могу ее исправить?

Комментарии:

1. Я не понимаю, как эти две root = clear(... строки имеют смысл. Одна вещь, которую нужно сделать наверняка, — это научиться загружать дамп ядра в gdb, чтобы вы могли видеть строку, вызвавшую ошибку. Какой-то указатель в этой строке был мусором. Еще один совет-сделать доступной самую маленькую полную программу, которая может выявить проблему. Это лучший способ получить помощь.

Ответ №1:

Я бы рекомендовал запустить valgrind, gdb и т. Д., Чтобы попытаться выяснить, где именно находится ошибка, но без этой информации здесь я вижу возможное разыменование NULL.

Если root->left и root->right оба равны НУЛЮ, то deleteNode будет возвращен NULL , который затем разыменован вызовами clear(root->left, date) .

Посмотрите, не приведет ли вставка проверки на значение NULL к тому, что он больше не будет использоваться по умолчанию.

Опять же, здесь невозможно определить, является ли это причиной, пожалуйста, также предоставьте остальную часть кода, чтобы сделать его работоспособным, или отладьте его, чтобы выяснить, какая строка вызывает segfault.

Ответ №2:

Мне удалось найти ошибку. Спасибо всем, кто помогал.

Я возвращал значение NULL в корень дерева, поэтому я потерял все ссылки на дерево и, следовательно, выполнил неправильный доступ к памяти. Я обновил функцию очистки до следующего:

 Node* clear(Node *root, int date) {
   if(root == NULL) {
      return NULL;
   }

   if(root->info.lastAccess <= date) {
      root = deleteNode(root, (root)->info.name);
   }

   root->left = clear(root->left, date);
   root->right = clear(root->right, date);

   return root;
}
Метки: