Вставить в двоичное дерево поиска рекурсивно, используя функцию сравнения в C
Я использую вложенные структуры для создания BST, но у меня возникла проблема при вставке, потому что я использую для этого функцию сравнения! вот моя функция сравнения
int compare_doubles(const void* a, const void* b)
{
const double* a_ = (const double*)a;
const double* b_ = (const double*)b;
return (*a_ > *b_) - (*a_ < *b_);
}
int compare_int(const void* a, const void* b)
{
const int* a_ = (const int*)a;
const int* b_ = (const int*)b;
return (*a_ > *b_) - (*a_ < *b_);
}
а вот конструкции
typedef struct tree_t BinarySearchTree; //opaque structure declared on BinarySearchTree.h
struct tree_t{
int (*comparison)(const void *, const void *);
struct tree_t* lchild;
struct tree_t* rchild;
struct t_node* noeud;
};
struct t_node{
const void *key;
const void *data;
City *city;
};
и это моя функция для создания нового BST
BinarySearchTree* newBST(int comparison_fn_t(const void *, const void *))
{
BinarySearchTree *t = (struct tree_t *)malloc(sizeof(struct tree_t));
t->comparison = comparison_fn_t;
t->lchild = t->rchild = NULL;
t->noeud = NULL;
return t;
}
Это моя функция вставки
BinarySearchTree* insertInBST(BinarySearchTree* bst, const void* key, const void* value) {
BinarySearchTree *t = bst;
if (bst->noeud == NULL)
{
struct t_node* n = (struct t_node *)malloc(sizeof(struct t_node));
t->noeud = n;
t->noeud->data = value;
t->noeud->key = key;
return t;
}
if ((bst->comparison(&key,&(bst->noeud->key))) < 0){
bst->lchild = insertInBST(bst->lchild, key, value);
}
else if ((bst->comparison(&key,&(bst->noeud->key))) >= 0){ // handle duplicate keys
bst->rchild = insertInBST(bst->rchild, key, value);
}
return bst;
}
когда я пытаюсь запустить свой код с помощью этих тестов, я получаю segfault (сбрасывается ядро) это моя основная функция
int main()
{
int *t =15;
int *g = 13;
int *j =15;
int *k = 13;
BinarySearchTree *root = newBST(&compare_doubles);
insertInBST(root, k,j);
insertInBST(root, t, g);
}```
Я использовал его, но получил ошибку error :void value not ignored as it ought to be return (*b - *a);
Вы все еще указали значения, поэтому я бы написал это как (*(double *) b - *(double *) a).
Спасибо за ваше время, но я действительно не знаю, как с этим справиться, потому что я думаю, что проблема в моих структурах, я думаю, потому что я использовал другую структуру, где я помещал в нее все ключ, значение ... но не сравнение функция struct tree_t{ const void *data; const void *key; struct tree_t* lchild; struct tree_t* rchild; };
Да, я изменил функции сравнения и создал новое двоичное дерево, используя &comare_int, но я не знаю, как поступить с базовым случаем в рекурсии функции вставки, потому что это все еще дает мне segfault
` printf("%p\n", bst->сравнение); /*if ((bst->comparison(&key,&(bst->noeud->key))) < 0){ bst->lchild = insertInBST(bst->lchild, key, value); } else if ((bst->comparison(&key,&(bst->noeud->key))) >= 0){ bst->rchild = insertInBST(bst->rchild, key, value); }*/ ` Закомментированные строки вызывают segfault, когда я запускаю функцию во второй раз, не знаю почему?
В вашей вставке if (bst->noeud == NULL) должно быть if (bst == NULL)
Ответы 1
Ваша функция сравнения слишком сложна
(*a_ > *b_) - (*a_ < *b_), поскольку вы смешиваете операции сравнения (<, >) и арифметические (-). @WhozCraig предложил (a <b)? -1 : (б < а).Вам нужно определить структуру City.
Вам нужно
#include <stdlib.h>для malloc.В основном вы приводите целые числа к указателям. Предупреждение компилятора для первого случая:
предупреждение: инициализация «int *» из «int» делает указатель из целого числа без приведения [-Wint-conversion]
Как в
int t = 15; int g = 13и позжеinsertInBST(root, &t, &g)В основном вы используете неправильную функцию сравнения (удваивает вместо int).
Я пропустил ваш код через gdb, и он вылетел
if (bst->noeud == 0), потому чтоinsertInBST(root, t, g)вызываетbst->rchild = insertInBST(bst->rchild, key, value), но bst->rchild имеет значение NULL.В insertInBST вам нужно выполнить сравнение только один раз, чтобы выяснить, нужна ли вам левая или правая ветвь.
Не используйте (a-b) для сравнения порядка в функции компаратора C. Это рецепт недополнения и, следовательно, нарушения любого алгоритма упорядочения. Есть причина, по которой вы видите, что люди этого не делают, вот и все.
Спасибо @WhozCraig Что вы предлагаете вместо этого? Я буду рад обновить ответ. Проверять двойники на равенство тоже нельзя.
учитывая аргументы a и b, возвращая меньше нуля при a < b, больше нуля при b < a и ноль при эквивалентности, вы можете использовать return (a < b) ? -1 : (b < a); . Есть несколько способов сделать это; способ, которым выбрал ОП, является одним из них. Я предпочитаю использовать только один логический оператор (меньше чем), но это происходит из-за того, что я всю жизнь кодировал строгие слабые упорядочения.
Ваши функции сравнения излишне сложны. Просто верните *b - *a. Следующий шаг — скомпилировать код с символами отладки, а затем выполнить его в отладчике, чтобы увидеть, какая строка вызывает сбой. Вы выделяете новый узел в insertInBST, но копируете указатели на ключ и значение, что вызывает подозрение. Другая причина, вероятно, заключается в том, что в вашем примере используются compare_doubles, но данные, которые вы используете, представляют собой целые указатели (int *). Есть две проблемы: оба неправильного типа, но я также думаю, что вы хотите использовать значения, а не указатели. Также сверните свой пример, чтобы продемонстрировать проблему (например, int или double).