Я новичок в c, но для проекта я реализую двоичное дерево. вот мой код для функций:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BSTnode{
int key;
int subtree_size;
struct BSTnode* left;
struct BSTnode* right;
} TreeNode;
TreeNode* newNode(int value){
TreeNode *node = malloc(sizeof(TreeNode));
node->key = value;
node->left = NULL;
node->right = NULL;
node->subtree_size = 1;
return node;
}
TreeNode* insert(TreeNode* root, TreeNode* to_insert){
if (root == NULL){
root = newNode(to_insert->key);
}
else if (to_insert->key> root->key){
if (root->right == NULL){
root->right = to_insert;
return root;
}
else{
root->right = insert(root->right, to_insert);
}
}
else if (to_insert->key< root->key){
if (root->left == NULL){
root->left = to_insert;
return root;
}
root->left = insert(root->left, to_insert);
}
root->subtree_size = 1 + (root->left? root->left->subtree_size: 0) + (root->right? root->right->subtree_size: 0);
return root;
}
int find(TreeNode* root, int value){
if (root == NULL || root->key == value){
return root->key;
}
else if (value > root->key){
return find(root->right, value);
}
else{
return find(root->left, value);
}
}
В моей основной функции я читаю файл, содержащий число в каждой строке, которое мне нужно вставить в BST. Каждая строка начинается с буквы, за которой следует число, разделенное пробелом.
int main (int argc, char* argv[]){
FILE* input;
input = fopen(argv[1], "r");
char oper;
int num;
TreeNode* root = NULL;
while(fscanf(input, "%c", &oper) != EOF){
if (oper == 'i'){
fscanf(input, " %d\n", &num);
TreeNode* to_insert = newNode(num);
insert(root, to_insert);
//printf("operation: %c, num: %d\n", oper, num);
}
if (oper == 'r'){
//do some other thing
}
}
if (root == NULL){
printf("yes\n");
}
printf("size: %d\n", root->subtree_size);
printf("left size: %d\n", root->left->subtree_size);
printf("right size: %d\n", root->right->subtree_size);
fclose(input);
}
Запуск кода печатает «да», а затем выдает ошибку сегмента. Я видел еще одно сообщение о подобной проблеме, и решение состояло в том, чтобы изменить функцию вставки, чтобы она принимала двойной указатель для root. Здесь это работает? Да, как бы это выглядело? Я не очень хорошо разбираюсь в двойных указателях.
Редактировать 1: предположим, что fscanf() и входной файл правильно используются и открываются.
Edit2: входной файл будет выглядеть так:
i 10
i 20
i 30
i 40
i 50
i 60
i 70
i 80
i 90
i 99
i 15
i 14
i 12
i 25
i 28
i 95
i 35
i 38
i 11
i 23
i 22
@DevSolar fscanf() и входной файл открываются правильно. надо было упомянуть об этом в посте
@DevSolar Я добавил пример того, как будет выглядеть входной файл.
«При запуске кода выводится «да», а затем выдается ошибка сегмента». if (root == NULL){ printf("yes\n"); } printf("size: %d\n", root->subtree_size); Если root имеет значение NULL, вы не должны удалять его ссылку. Сегфолт является разумным потенциальным последствием этого.





Твоя проблема:
Ваша функция insert() возвращает root. Но вы никогда ничему не присваиваете возвращаемое значение, по крайней мере, в своем main():
TreeNode* root = NULL;
while(fscanf(input, "%c", &oper) != EOF){
// ...
insert(root, to_insert);
Ваш root всегда остаётся NULL.
Как я узнал:
gcc -Wall -Wextra -g testme.c -o testme
gdb -tui --args ./testme input.txt
break main
run
Затем «n» означает «следующий» (шаг вперед) и «s» означает «шаг» (вход). Либо научитесь использовать GDB, либо ознакомьтесь с другим отладчиком по вашему выбору. Заниматься разработкой программного обеспечения без отладчика сложно. Не пытайтесь это сделать.
Мое исправление:
Я ненавижу двойные указатели. К счастью, есть простое решение вашей проблемы. В insert() для первого полученного узла не делайте newNode(), просто возьмите тот узел, который вам дали:
if (root == NULL){
root = to_insert;
}
И в main() присвойте возвращаемое значение root:
TreeNode* to_insert = newNode(num);
root = insert(root, to_insert);
Еще предстоит сделать:
Обратите внимание, что ваша программа теряет всю выделенную ей память.
Вам необходимо проверить root на NULL перед доступом к root->left и root->right (в случае, если вы не читали какие-либо данные), и вам нужно еще раз проверить любой из них на NULL перед доступом к соответствующим ...->subtree_size (в случае, если вы, как в примере с данными, , вообще не имеют данных ни в одном поддереве).
выполнение root = insert(root, to_insert); позволяет мне напечатать «размер: 17», а затем ошибку сегмента. Знаете, что не так с root->left->subtree_size?
@The-coder-E Ваше начальное значение — 10. Все последующие значения больше 10 и, следовательно, идут справа от root. root->left остаётся NULL, а значит root->left->subtree_size — незаконный доступ. (Вы пробовали использовать отладчик?)
Большое спасибо за помощь. Проблемы с памятью я решу позже, а сейчас у меня есть дела поважнее.
Во-первых, поскольку вы не проверяете возвращаемое значение ваших вызовов
fscanf(), вы понятия не имеете, прочитали ли вы то, что, по вашему мнению, прочитали. На самом деле, вы даже не знаете, успешно ли вы открылиinput. И еслиrootравноNULL, следующиеprintf()следуют за указателемNULL, что является неопределенным поведением. Либо используйте отладчик, чтобы выяснить, что происходит (рекомендуется), либо добавьте больше сообщений о состоянии к операциям чтения/построения дерева, чтобы вы видели, что происходит, а не только конечный результат.