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

Question

Я пытаюсь реализовать двоичное дерево поиска в C и получаю ошибку сегментации при попытке запустить мой код. По сути, в моем коде я читаю строку данных из файла, создаю для него узел и затем вставляю его в мое двоичное дерево поиска. Я даже не уверен, что моя реализация этого кода правильная, так как я получаю ошибку сегментации, когда пытаюсь его запустить. Я очень новичок в программировании на C и особенно выделяю память, поэтому я знаю, что в моем коде, вероятно, есть большое количество ошибок, даже в базовой структуре самого кода. Поэтому любая помощь в поиске причины ошибки сегментации или помощь в базовой структуре самого кода была бы признательна.

Answer 1

В вашем коде несколько проблем:

• root неинициализируется в функции main. Он должен быть инициализирован на NULL перед передачей на insertNode().

• Вы должны проанализировать только одну строку в readdata() и вернуть индикатор успеха.

• вы должны выполнять итерации в цикле main, пока readdata не сможет прочитать больше записей из файла. Ваш текущий тест while ((c = getchar()) != EOF) не подходит и портит этот поток ввода.

Здесь представлены модифицированные версии функций readdata и main:

bst_t *createNode(void) {
    bst_t *newNode;
    newNode = (struct bst_t *)malloc(sizeof(struct bst_t));
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int readData(bst_t *node) {
    return scanf("%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],"
                 "%[^,],%[^,],%[^,],%[^,],%[^,]",
                 node->data.ID, node->data.name, node->data.sex,
                 node->data.height, node->data.weight, node->data.team,
                 node->data.NOC, node->data.games, node->data.year,
                 node->data.season, node->data.city, node->data.sport,
                 node->data.event, node->data.medal) == 14;
}

int main(int argc, char *argv[]) {
    bst_t *root = NULL;
    bst_t *newNode;

    while ((newNode = createNode()) != NULL) {
        if (readData(newNode)) {
            /* record was read correctly: insert into the tree */
            root = insertNode(root, newNode);
        } else {
            /* end of file or input error: stop reading the file */
            free(newNode);
            break;
        }
    }
    freeTree(root);
    return 0;
}

Answer 2

Возможно, это скорее комментарий, чем ответ, но мне не хватает «репутации», чтобы комментировать, так что ...

Проблема связана с использованием, а не указателями, как ранее писал @Lundin.

В этой строке: *node->left = insertNode(node->left, newNode);

node-> left может быть NULL. Внутри вызова insertNode вы проверяете это и присваиваете newNode локальную копию node-> left, но это не влияет на node-> left, поэтому, когда возвращаемое значение insertNode записывается в расположение, на которое указывает node-left (NULL), вы гарантированно аварийно завершаете работу!

Answer 3

Я считаю, что проблема в функции readData. Когда вы используете scanf, вы должны использовать оператор адреса & для чтения переменных.

Следующий код:

void readData(bst_t *node) {
while (scanf("%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],"
             "%[^,],%[^,],%[^,],%[^,],%[^,]",
             node->data.ID, node->data.name, node->data.sex,
             node->data.height, node->data.weight, node->data.team,
             node->data.NOC, node->data.games, node->data.year,
             node->data.season, node->data.city, node->data.sport,
             node->data.event, node->data.medal) == 14) {
    continue;
}

следует изменить на:

void readData(bst_t *node) {
while (scanf("%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],%[^,],"
             "%[^,],%[^,],%[^,],%[^,],%[^,]",
             &node->data.ID, &node->data.name, &node->data.sex,
             &node->data.height, &node->data.weight, &node->data.team,
             &node->data.NOC, &node->data.games, &node->data.year,
             &node->data.season, &node->data.city, &node->data.sport,
             &node->data.event, &node->data.medal) == 14) {
    continue;
}

Также необходимо внести некоторые изменения:
1. Передайте аргументы и верните значения, используя указатели на структуры, а не на структуры.
2. Выделите память в куче, а не в стеке при работе со связанными списками (даже для корневого узла).
3. При распределении памяти в куче убедитесь, что выделенный размер соответствует размеру структуры, а не размеру указателя на структуру.
4. Убедитесь, что вы освобождаете всю память, выделенную в куче, и не ошибочно освобождайте память, выделенную в стеке, как вы, кажется, делаете здесь.

Answer 4

Вы освобождаете указатель на свой стек:

int main(int argc, char *argv[]) {

bst_t root;                                       <<< root is allocated on stack
bst_t newNode;
int c;

while ((c = getchar()) != EOF){
  newNode = createNode();
  root = insertNode(&root,&newNode);
  }
  freeTree(&root);                                <<< Your are passing a pointer to root ( pointer to a stack element )
  return 0;
}



void freeTree(bst_t *parent){                    <<< parent is a pointer to a stack element
  if(! parent){
    return;
  }
  freeTree(parent->left);
  freeTree(parent->right);
  free(parent);                                  <<< you free a stack element => segmentation fault
}

Вы должны либо выделить корневой узел, чтобы его можно было освободить, либо обработать корневой узел в вашем freeTree

---

РЕДАКТИРОВАТЬ : Вот синтаксис для malloc его:

bst_t *root = malloc(sizeof(bst_t));

malloc функция возвращает указатель на вновь выделенное пространство и принимает в качестве параметра размер выделения.

примечание: если вы хотите быть действительно чистым, malloc может вернуть null, если нет доступной памяти (очень редко), поэтому рекомендуется проверить возвращение.
подробнее