Ошибка сегментации (сбрасывание сердечника) при реализации двоичного дерева

Question

В моем коде есть ошибка сегментации (сбрасывается ядром). Я не уверен, какая строка вызывает его, так как я довольно новичок в C. . Я пытаюсь реализовать здесь двоичное дерево поиска для каждой строки в файле (только для вставки и поиска). Каждая строка не должна превышать 1000 слов.

Вот мой код:

BST *bst_ins(BST *bst, char *key, void *value) 
{ 
    BST* temp = NULL; 
    int cmp = strcmp(bst->kvp.key, key); 
    if(bst == NULL) 
    { /* This for null node */ 
    temp = (BST*)malloc(sizeof(BST)); /* allocate the memory of struct for new node */ 
    temp->left = NULL; 
    temp->right = NULL; 
    temp->kvp.key = key; 
    temp->kvp.value = value; 
    } 


    else if(cmp < 0) /* Current node less than input */ 
    { 
    bst->right = bst_ins(bst->right,key,value); 
    } 

    else if(cmp > 0) 
    { 
    bst->left = bst_ins(bst->left,key,value); 
    } 

    return bst; 
} 


KVP *bst_get(BST *bst, char *key) 
{ 
    KVP* return_this; 
    if(bst!=NULL) 
    { 
     if(bst->kvp.key==key) 
     { 
      return return_this; 
     } 
     else if(strcmp(bst->kvp.key, key) < 0) /* Current node less than input */ 
     { 
      return bst_get(bst->left, key); 
     } 
     else if(strcmp(bst->kvp.key,key) > 0) 
     { 
      return bst_get(bst->right,key); 
     } 
    } 
    return 0; 
} 

Ниже header.h

typedef struct { 
    char *key; 
    void *value; 
} KVP; 
typedef struct bst { 
    struct bst *left; 
    struct bst *right; 
    KVP kvp; 
} BST; 

Может кто-то пожалуйста, помогите мне понять, какая линия вызывает это? Спасибо.

EDIT:

SOLVED! НАКОНЕЦ: D

Вот основная функция.

int main() 
{ 
char* str1=strdup("alokama"); 
char* str2=strdup("kokokoko"); 
BST *bst = NULL; 
bst = bst_insert(bst,str1,NULL); 
bst = bst_insert(bst,str2,NULL); 
if(bst_get(bst,str1)){ printf ("yuhuu\n"); } 
return 0; 
} 

Answer 1

При вызове bst_ins, bst может быть NULL, так что вы не можете разыменования его. Кроме того, вы определяете временный узел, который равен NULL. Когда вы получите ваши сравнения строк,

if (strcmp(temp->kvp.key, key) < 0) ... 

вы, конечно, разыменовывать NULL указатель. Нехорошо. Приведенный ниже код исправляет проблему, а также вызывает strcmp только один раз за проход. Обратите внимание, как temp определяется только в области, где создается новый узел.

BST *bst_ins(BST * bst, char *key, void *value) 
{ 
    int cmp; 

    if (bst == NULL) { 
     BST *temp = (BST *) malloc(sizeof(*temp)); 

     temp->left = NULL; 
     temp->right = NULL; 
     temp->kvp.key = key; 
     temp->kvp.value = value; 

     return temp; 
    } 

    cmp = strcmp(bst->kvp.key, key); 

    if (cmp < 0) { 
     bst->right = bst_ins(bst->right, key, value); 
    } else if (cmp > 0) { 
     bst->left = bst_ins(bst->left, key, value); 
    } 

    return bst; 
} 

Теперь вы можете вставить новые узлы, как так:

bst = bst_ins(bst, "plum", "1"); 
bst = bst_ins(bst, "apple", "2"); 
bst = bst_ins(bst, "orange", "3"); 
bst = bst_ins(bst, "kumquat", "4"); 

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

Лучшим подходом может быть передача адреса корневого узла в функции, которые могут изменить дерево. Если вы не боитесь (*bst) нотации и адрес-poerator &, здесь идет:

BST *bst_ins(BST **bst, char *key, void *value) 
{ 
    int cmp; 

    if (*bst == NULL) { 
     *bst = (BST *) malloc(sizeof(**bst)); 

     (*bst)->left = NULL; 
     (*bst)->right = NULL; 
     (*bst)->kvp.key = key; 
     (*bst)->kvp.value = value; 

     return *bst; 
    } 

    cmp = strcmp((*bst)->kvp.key, key); 

    if (cmp < 0) return bst_ins(&(*bst)->right, key, value);  
    if (cmp > 0) return bst_ins(&(*bst)->left, key, value); 

    return *bst; 
} 

и назвать его так:

bst_ins(&bst, "plum", "1"); 
bst_ins(&bst, "apple", "2"); 
bst_ins(&bst, "orange", "3"); 
bst_ins(&bst, "kumquat", "4"); 

Функция возвращает узел, связанный с ключом, но вы можете легко игнорировать возвращаемое значение.

Наконец, убедитесь, что ваше дерево правильно удалено, когда вы закончите.