C89: чтение нарушения доступа 0x00 (сложность с malloc)

Question

Я занимаюсь разработкой C89 для Visual Studio 2010 Ultimate Beta (Win 7). Я не думаю, что я использую malloc() правильно. Я новичок в C, поэтому, пожалуйста, извините вопрос новичка.

Цель моей программы - подсчитать вхождение слов в **argv с помощью дерева.

hist.c

#include "tree.h"
#include <stdlib.h>

int main(int argc, char *argv[]) {
    unsigned int i;
    struct tree *tree;
    tree = new_tree();

    for (i = 1; i < argc; i++) {
        tree_add(tree, argv[i]);
    }

    tree_dump(tree);
    tree_free(tree);

    return 0;
}

tree_add.c:

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

struct tree *tree_add(struct tree *tree, char *value) {
    if (tree == NULL) {
        tree = new_tree();
        tree->value = value;
        tree->count = 0;
    }
    else if (tree->value == NULL) {
        tree->value = value;
    }
    else if (tree->value == value) {
        tree->count++;
    }
    else if (strcmp(value, tree->value) < 0) {
        tree_add(tree->left, value);
    }
    else if (strcmp(value, tree->value) > 0) {
        tree_add(tree->right, value);
    }
}

struct tree *new_tree() {
    struct tree * tree;
    tree = malloc(sizeof *tree);
    tree->left = NULL;
    tree->right = NULL;
    tree->value = NULL;
    tree->count = 0;
    return tree;
}

Я получаю ошибку:

0xC0000005: чтение о нарушении доступа местоположение 0x00000000.

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

ОБНОВЛЕНО код для отражения комментариев. Теперь у меня новая проблема. Это условие не работает должным образом, когда value == "x" и tree->value == "x"

else if (tree->value == value) {

В отладчике я вижу, что tree->value это 0x00553373 "x" char *, тогда как value это 0x00553375 "x" char *. Шестнадцатеричное значение отличается от последней цифры. Что здесь не так? Я неправильно проверяю равенство строк?

Answer 1

Как эта часть должна работать?

    if (tree == NULL) {
        tree->value = value;
        tree->count = 0;
    }

Я спрашиваю, потому что он всегда пытается разыменовать NULL, если это возможно. Код составляет:

    if (tree == NULL) {
        (NULL)->value = value;
        (NULL)->count = 0;
    }

Итак, он получит AV, когда попытается достичь элемента value структуры.

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

Вы, вероятно, имели в виду что-то вроде:

    if (tree->left == NULL) {
        tree->left = malloc(sizeof struct tree);
        tree = tree->left;
    }
    /* ... */

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

Answer 2

Некоторые проблемы:

tree = malloc(sizeof tree);

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

if (tree == NULL) {
    tree->value = value;
    tree->count = 0;
}

Если дерево NULL, то tree->value не в порядке.

Answer 3

if (tree == NULL) {
    tree->value = value;
    tree->count = 0;
}

здесь есть проблема: если дерево имеет значение NULL, вы не можете его использовать, вы должны сначала выделить его

Кроме того, вы должны сохранить возвращаемое значение strcmp вместо того, чтобы делать это дважды

Answer 4

У вас неправильная проверка в tree_add, здесь:

if (tree == NULL) { 
    tree->value = value; 
    tree->count = 0; 
} 

Поскольку дерево не равно NULL в исходном вызове, вы не будете записывать в tree-> value, и оно останется NULL. Когда вы затем вызываете strcmp, вы получаете нарушение прав доступа при попытке прочитать из дерева-> значение.

Вы никогда не выделяете tree-> left и tree-> right - вам нужно распределить их с помощью malloc перед использованием.

Answer 5

strcmp ожидает две строки и не может обработать ноль. Обратите внимание, что char *c="\0" - это не то же самое, что char *c = 0. Первый - указатель на массив символов с одним нулевым элементом, второй - нулевой указатель.

Answer 6

В дополнение к другим комментариям, tree_add должен возвращать дерево, а вызовы tree_add должны сохранять этот результат. (Хотя рекурсивные вызовы должны сохранять не как дерево, а как указатели влево / вправо).