c - 将字典加载到 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()返回一个指向已分配内存的指针，但返回的值将被忽略。这是内存泄漏，并且您的代码继续使用未初始化的变量。这是一个问题!

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()消除该值)。该指针被返回，但返回被忽略。 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;
}

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

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

这似乎对我有用，尽管我承认我只在 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] = '\0';

    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;
}

我相信它也是无泄漏的。

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