Ошибка сегментации при добавлении в дерево префиксов

Question

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

int wordCount = 0;
typedef struct node
{
    bool isWord;
    struct node* children[26];
}node;
struct node* newNode(struct node* n)
{
    n = (struct node*)malloc(sizeof(struct node));
    n->isWord = false;
    for (int i = 0; i < 26; i++)
        n->children[i] = 0;    
    return n;
}
struct node* n = NULL;

void append(char* s)
{
    struct node* m = NULL;
    m = n;
    for (int i = 0, p = strlen(s); i < p; i++)
    {
        if (m->children[s[i] - 'a'] == NULL)
            m->children[s[i] - 'a'] = newNode(m->children[s[i] - 'a']);
        m = m->children[s[i] - 'a'];
        if (i == p - 1)
        {
            m->isWord = true;
            wordCount++;
        }            
    }              
}
bool load(const char* dictionary)
{
    FILE* f = fopen(dictionary, "r");
    n = newNode(n);
    if (f == NULL)
        return false;
    char s[100];
    while (f != NULL && !feof(f))
    {
        fgets(s, sizeof(s), f);       
        for (int i = 0, j = strlen(s); i < j; i++)
            s[i] = tolower(s[i]);  
        append(s);
    }
    return true;
}

После некоторого тестирования я почти уверен, что проблема в функции добавления.

Answer 1

Адаптация кода в вопросе (по состоянию на 2014-02-25 20:55 -08:00) в программу (добавьте заголовки <assert.h>, <ctype.h>, <stdbool.h>, <stdio.h>, <stdlib.h>, <string.h>; добавить утверждение после выделения памяти, исправить использование fgets()) и удалить новые строки из данных, распечатать строки (слова) по мере их чтения, и valgrind дает ему безаварийный (но очень негерметичный) прогон.

Код:

#include <assert.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int wordCount = 0;

typedef struct node
{
    bool isWord;
    struct node *children[26];
} node;

static struct node *newNode(struct node *n)
{
    n = (struct node *)malloc(sizeof(struct node));
    assert(n != 0);
    n->isWord = false;
    for (int i = 0; i < 26; i++)
        n->children[i] = 0;
    return n;
}

static struct node *n = NULL;

static
void append(char *s)
{
    struct node *m = NULL;
    m = n;
    for (int i = 0, p = strlen(s); i < p; i++)
    {
        if (m->children[s[i] - 'a'] == NULL)
            m->children[s[i] - 'a'] = newNode(m->children[s[i] - 'a']);
        m = m->children[s[i] - 'a'];
        if (i == p - 1)
        {
            m->isWord = true;
            wordCount++;
        }
    }
}

static
bool load(const char *dictionary)
{
    FILE *f = fopen(dictionary, "r");
    n = newNode(n);
    if (f == NULL)
        return false;
    char s[100];
    while (fgets(s, sizeof(s), f) != 0)
    {
        for (int i = 0, j = strlen(s); i < j; i++)
            s[i] = tolower(s[i]);
    s[strlen(s)-1] = '\0';
    printf("[%s]\n", s);
        append(s);
    }
    return true;
}

int main(void)
{
    if (load("file"))
    {
        printf("File loaded OK\n");
        return 0;
    }
    else
    {
        printf("Failed to load file\n");
        return 1;
    }
}

Данные:

an
anne
apple
aardvark
appalachian
antelope
antediluvian
alabama
antidisestablishmentarianism

Выход из valgrind:

$ valgrind ./prefix
==29970== Memcheck, a memory error detector
==29970== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==29970== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==29970== Command: ./prefix
==29970== 
[an]
[anne]
[apple]
[aardvark]
[appalachian]
[antelope]
[antediluvian]
[alabama]
[antidisestablishmentarianism]
File loaded OK
==29970== 
==29970== HEAP SUMMARY:
==29970==     in use at exit: 15,472 bytes in 70 blocks
==29970==   total heap usage: 70 allocs, 0 frees, 15,472 bytes allocated
==29970== 
==29970== LEAK SUMMARY:
==29970==    definitely lost: 0 bytes in 0 blocks
==29970==    indirectly lost: 0 bytes in 0 blocks
==29970==      possibly lost: 0 bytes in 0 blocks
==29970==    still reachable: 15,472 bytes in 70 blocks
==29970==         suppressed: 0 bytes in 0 blocks
==29970== Rerun with --leak-check=full to see details of leaked memory
==29970== 
==29970== For counts of detected and suppressed errors, rerun with: -v
==29970== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
$

Если вы не обрежете переводы строк, вы будете получать доступ к памяти за пределами границ; это было бы моим лучшим предположением относительно того, что идет не так, как надо. Это не ясно, что это проблема. Когда я закомментировал строку, которая закрывает новую строку, я получил жалобу на использование неинициализированных данных в строке:

        if (m->children[s[i] - 'a'] == NULL)

(Обратите внимание assert очень грубый способ выявления проблем с выделением памяти; эффективный, но очень грубый.)