c - 添加到前缀树时出现段错误

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 是检测内存分配问题的一种非常粗糙的方法；有效但非常粗糙。)