将字典加载到 trie 树中的分段错误

Question

我正在制作一个程序，将给定的字典读入特里树，然后对用户输入的字符串执行自动完成。当我使用需要使用的词典文件（约 100,000 个单词）时，我遇到了分段错误。我似乎无法弄清楚是什么导致了分段错误。任何帮助将不胜感激。

typedef struct trieTree {
    int data;
    struct trieTree *array[26];
}trieTree;

插入函数：

    trieTree* insert_tree(trieTree *t, char *s, int val)
{
    int i;
    trieTree *p;
    if (strlen(s) == 0)
    return t;
    if (t == NULL)
    t = new_tree(t);
    p = t;
    for (i = 0; i < strlen(s); ++i) {
        if (p->array[s[i] - 'a'] == NULL) 
        p->array[s[i] - 'a'] = malloc(sizeof (trieTree));
        p = p->array[s[i] - 'a'];
    }
    p->data = val;
    return t;
}

填充树：

trieTree* load_tree(trieTree *t, char *file)
{
    char s[MAX];
    FILE *f = fopen(file, "r");
    if (f == NULL)
    printf("Error! File not found.");
    else 
    while (feof(f) == 0) {
        fscanf(f, "%s", s);
        t = insert_tree(t, s, 1);
    }
    return t;
}

主要功能

int main()
{
    trieTree t;
    new_tree(&t);
    load_tree(&t, "dict.txt");
    char word[100];
    printf("Enter word: ");
    scanf("%s", word);
    char dat[100] = "";
    search_tree(&t, word, dat);
    return 0;
}


trieTree* new_tree(trieTree *t)
{
    int i;
    t = malloc(sizeof (trieTree));
    for (i = 0; i < 24; ++i)
    t->array[i] = 0;
    return t;
}

Answer 1

您的函数 new_tree() return 是指向已分配内存的指针，但 returned 值被忽略。那是内存泄漏，您的代码继续使用未初始化的变量。这是个问题！

int main()
{
    trieTree t;
    new_tree(&t);
    load_tree(&t, "dict.txt");
    …

trieTree* new_tree(trieTree *t)
{
    int i;
    t = malloc(sizeof(trieTree));
    for (i = 0; i < 24; ++i)
        t->array[i] = 0;
    return t;
}

函数中的24当然应该是26。但是该函数分配内存并将其分配给本地指针（原始设置指向 main() 中的 t，但 malloc() 删除了该值）。该指针是 returned，但 return 被忽略。 main()中的变量t仍未初始化，但它被传递给load_tree()函数。

坦率地说，你需要：

int main()
{
    trieTree *tp = new_tree();
    load_tree(&t, "dict.txt");
    …

trieTree* new_tree(void)
{
    int i;
    trieTree *t = malloc(sizeof(trieTree));
    if (t == 0)
    {
        fprintf(stderr, "memory allocation failure\n");
        exit(EXIT_FAILURE);
    }
    for (i = 0; i < 26; ++i)
        t->array[i] = 0;
    return t;
}

注意应该在标准错误通道上报告错误；这就是它的用途。并且应该检查每个内存分配，因为如果你不检查，它将失败并且你的程序将崩溃。

可能还有很多其他问题；我没有调查所有这些。这应该能让你在崩溃之前走得更远。

这似乎对我有用，但不可否认我只在 'dictionary' 257 个单词上测试过它。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { MAX = 1024 };

typedef struct trieTree
{
    int data;
    struct trieTree *array[26];
} trieTree;

static trieTree *new_tree(void)
{
    int i;
    trieTree *t = malloc(sizeof(trieTree));
    if (t == 0)
    {
        fprintf(stderr, "malloc for %zu bytes failed\n", sizeof(trieTree));
        exit(EXIT_FAILURE);
    }
    t->data = 0;
    for (i = 0; i < 26; ++i)
        t->array[i] = 0;
    return t;
}

static trieTree *insert_tree(trieTree *t, char *s, int val)
{
    int i;
    trieTree *p;
    if (strlen(s) == 0)
        return t;
    if (t == NULL)
        t = new_tree();
    p = t;
    int len = strlen(s);
    for (i = 0; i < len; ++i)
    {
        if (p->array[s[i] - 'a'] == NULL)
            p->array[s[i] - 'a'] = new_tree();
        p = p->array[s[i] - 'a'];
    }
    p->data = val;
    return t;
}

static trieTree *load_tree(trieTree *t, char *file)
{
    char s[MAX];
    FILE *f = fopen(file, "r");
    if (f == NULL)
    {
        fprintf(stderr, "Error! File not found.");
        exit(EXIT_FAILURE);
    }
    else
    {
        while (fscanf(f, "%s", s) == 1)
            t = insert_tree(t, s, 1);
        fclose(f);
    }
    return t;
}

static void print_trie(trieTree *t, char *pad)
{
    int len = strlen(pad);
    char space[len + 3];
    memset(space, ' ', len + 2);
    space[len + 2] = '[=12=]';

    for (int i = 0; i < 26; i++)
    {
        if (t->array[i] != 0)
        {
            printf("%s%c\n", pad, i + 'a');
            print_trie(t->array[i], space);
        }
    }
}

static void free_trie(trieTree *t)
{
    if (t != 0)
    {
        for (int i = 0; i < 26; i++)
            free_trie(t->array[i]);
        free(t);
    }
}

int main(void)
{
    trieTree *tp = new_tree();
    if (tp != 0)
    {
        tp = load_tree(tp, "dict.txt");
        print_trie(tp, "");
        free_trie(tp);
    }
    return 0;
}

我相信它也没有泄漏。

请注意，如果任何输入的单词包含任何大写字母、数字或标点符号，此代码将崩溃并烧毁。它只处理小写和白色space；其他任何事情都是一场无法遏制的灾难，等待着摧毁你的程序。那是因为我没有对insert_tree()函数做任何实质性的工作。您需要担心该函数中的 'invalid' 个字符，可能是通过将大写字母转换为小写字母并忽略任何不是字母的字符。

将字典加载到 trie 树中的分段错误

Segmentation fault loading dictionary into trie tree

c

trie

segmentation-fault