Вставляющий узел (Дерево двоичного поиска) C

Question

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

#include "stdafx.h" 
#include <string.h> 
#include <stdlib.h> 


typedef struct Node{ 
    char name[100]; 
    struct Node *pGauche; 
    struct Node *pDroit; 
}Node; 

void getName(char[]); 
void copy(Node **, Node *,char[]); 
void menu(Node **); 
void add(Node **); 
void search(char[],Node**, Node **,Node **); 
void print(Node **); 
void inOrder(Node *); 

void main(void) 
{ 
    Node *root = NULL; 
    menu(&root); 
    system("pause"); 
} 

void menu(Node **root) 
{ 
    for (int i=0;i<10;i++) 
    { 
     add(root); 
    } 
    print(root); 
} 

void add(Node **root) 
{ 
    char name[100]; 
    getName(name); 
    Node *p = NULL; 
    Node *savep = NULL; 
    search(name,root,&p,&savep); 
    copy(root,savep,name); 
} 

void search(char name[],Node **root, Node **p, Node **savep) 
{ 
    *p = *root; 

    while ((p == NULL) && (strcmp((*p)->name,name) != 0)) 
    { 
     *savep = *p; 

     if (strcmp(name,(*p)->name) < 0) 
      *p = (*p)->pGauche; 
     else 
      *p = (*p)->pDroit; 
    } 

} 

void getName(char name[]) 
{ 
    printf("What name do you want to add\n"); 
    scanf("%s",name); 
    fflush(stdin); 

} 

void copy(Node **root, Node *savep, char name[]) 
{ 
    Node *newp = (Node *) malloc(sizeof(Node*)); 
    newp->pDroit = NULL; 
    newp->pGauche = NULL; 

    strcpy(newp->name,name); 
    printf("%s",newp->name); 


    if (*root == NULL) 
     *root = newp; 
    else 
    { 
     if (strcmp(name,savep->name) < 0) 
      savep->pGauche = newp; 
     else 
      savep->pDroit = newp; 
    } 
    free(newp); 
} 

void print(Node ** root) 
{ 
    Node *p = *root; 
    inOrder(p); 
} 

void inOrder(Node *p) 
{ 
    if (p != NULL) 
    { 
     inOrder(p->pGauche); 
     printf("%s\n",p->name); 
     inOrder(p->pDroit); 
    } 
} 

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

В основном проблема заключается в том, что я получаю «место для чтения с нарушениями прав доступа» после ввода второго имени ... Я угадываю при выполнении strcmp, но я действительно не уверен:/

Я бы очень рад, если кто-то может помочь мне получить этот ход :)

Answer 1

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

В этом коде в search():

while ((p == NULL) && (strcmp((*p)->name,name) != 0)) 

Параметр p никогда не будет NULL. Таким образом, цикл while никогда не вводится. Это означает, что savep не будет установлено ни одного значения и будет NULL, когда вы вызываете copy() в свою функцию add(). Функция copy() затем разыгрывает неверную ссылку указателя, которая вызвала проблему, которую вы наблюдали.

Вы действительно хотите протестировать, если *p is NOT NULL. Это позволяет вам юридически разыгрывать его.

while ((*p != NULL) && (strcmp((*p)->name,name) != 0)) 

Во-вторых, в качестве hmjd идентифицирована, вы не выделить достаточно памяти для вашего узла внутри copy().

Node *newp = (Node *) malloc(sizeof(Node*)); 

Вы выделяете достаточно памяти только для одного указателя, а не для всего узла. Кроме того, при кодировании на C вы не должны указывать возвращаемое значение malloc() (это скроет ошибку, которая может привести к сбою в худшем случае).

Node *newp = malloc(sizeof(Node)); 

В-третьих, необходимо сохранить в памяти, выделенной для узлов, а не освобождая их сразу после введения его в конце copy():

// I need this memory for my tree! 
    //free(newp); 

Если вы звоните free(), как вы делали, то ваш tree будет указывать на освобожденную память, а доступ к ним приведет к неопределенному поведению.

Одна незначительная вещь: вы не должны делать fflush(stdin), так как fflush() предназначен только для выходных потоков.

Answer 2

Это неверно:

while ((p == NULL) && (strcmp((*p)->name,name) != 0)) 

и приведет к NULL указателя время разыменовано, что неопределенное поведение. Изменить на:

while (*p && strcmp((*p)->name,name) != 0) 

---

Это неверно:

Node *newp = (Node *) malloc(sizeof(Node*)); 

как он выделяет только достаточно для Node*, когда это необходимо выделение Node. Изменить на:

Node *newp = malloc(sizeof(*newp)); 

и не free() его в той же функции, что требуется позже. free()Node означает, что список имеет dangling pointers, а разыменование является неопределенным поведением и вероятной причиной нарушения доступа.

---

Примечание:

fflush(stdin); 

не определено поведение. На странице fflush():

Заставляет поток выходного файла синхронизироваться с фактическим содержимым файла. Если данный поток имеет тип ввода, то поведение функции не определено.