Печать двоичного дерева поиска, ошибка ошибки сегментации 11 - PullRequest
Новая
       11

Печать двоичного дерева поиска, ошибка ошибки сегментации 11

0 голосов
/ 23 сентября 2018

не могли бы вы мне помочь?

Программа читает слова из файла и помещает их в двоичное дерево поиска, но я получаю «Ошибка сегментации: 11» при запуске моей функции печати. ​​

struct node {
    char * item;
    struct node * left;
    struct node * right;
};

struct node * new(char * a) {
    struct node * new;
    new = (struct node *)malloc(sizeof(struct node *));
    new->item = a;
    new->left = new->right = NULL;
    return new;
}

struct node * insert(struct node * a, char * b) {
    if(a == NULL) {
        a = new(b);
    }
    else if (b <= a->item) {
        a->left = insert(a->left, b);
    }
    else {
        a->right = insert(a->right, b);
    }
    return a;
}

void print(struct node * a) {
    if (a->left == NULL && a->right == NULL)
        printf("%s", a->item);
    else if (a->left != NULL)
        print(a->left);
    else
        print(a->right);
}

из main.c: 

   struct node * root = NULL;
   struct node * start;

   start = root;

   while (fscanf(fp, "%s", temp) != EOF) {
   root = insert(root, temp); // insert function works ok
   }

   print(start);

ОБНОВЛЕНИЕ: я сделал изменение в main.c: 

int i = 0;

while (fscanf(fp, "%s", temp) != EOF) {
        root = insert(root, temp);
        if (!i) {
            start = root;
            i = 1;
        }
    }

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

ОБНОВЛЕНИЕ № 2: Спасибо за вашу помощь.Следуя вашим предложениям, я внес изменения в эту функцию: 

struct node * new(char * a) {
    struct node * new;
    char * stringcopy;
    stringcopy = malloc(strlen(a) + 1);
    strcpy(stringcopy, a);
    new = malloc(sizeof(* new));
    new->item = stringcopy;
    new->left = new->right = NULL;
    return new;
}

Теперь все работает нормально.

1 Ответ

0 голосов
/ 23 сентября 2018

Первоначальной проблемой было почти наверняка то, что start было NULL, поскольку вы не обновляли его при обновлении root.(Между тем, кажется, что все start не нужно; просто используйте root напрямую.)

Новая проблема (печать только последнего слова) состоит в том, что вы неправильно обходите дерево: ваш print Функция печатает, только если left и right равны NULL, поэтому печатается только листовой узел, и, кроме того, он не спускается в ветвь right, если есть ветвь left.

Вместо этого вы можете попробовать что-то вроде этого (непроверенный код): 

void print(struct node * a) {
    if (a == NULL) { return; }
    print(a->left);
    (void) puts(a->item);
    print(a->right);
}

В частности, обратите внимание, что если вы находитесь не на узле NULL, вам необходимо напечатать его itemбезусловно, или весь вывод будет отсутствовать в этом узле.

Другая проблема , по-видимому, в том, что вы не копируете item при создании узла.Поэтому, если ваш temp в insert(root, temp) действительно является временным объектом, который будет перезаписан или освобожден, все ваши item с (за исключением, возможно, последнего) будут недействительными к тому времени, когда вы попытаетесь их напечатать.Вместо присвоения new->item = a, сделайте эквивалент new->item = strdup(a) и затем запомните free при освобождении узла.

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

Кроме того, сравнение b <= a->item почти наверняка не дает ожидаемого результата;см strcmp.

...