为什么有些词会出现分段错误？而其他人似乎工作正常

Question

在 C++ 中使用 trie 创建字典。在某些输入上给出分段错误。

调试帮我发现问题出在check函数上。具体在退出循环后，在检查isword条件下。

typedef struct node
{
    bool is_word;
    struct node *children[27];
} node;

node *createNode()
{
    // Void -> Node*
    // Create a pointer to a node(structure)
    // Allocate memory and store address in child pointer
    node *child = (node *)malloc(sizeof(node));
    // Initialize each node in child to NULL
    for (int i = 0; i < N; i++)
    {
        child->children[i] = NULL;
    }
    // Initialize the is_word variable
    child->is_word = false;
    // Return the pointer
    return child;
}

bool check(const char *word)
{
    int i = 0;

    // Create a pointer to the root of the trie
    node *ptr = root;

    // Iterate over each letter
    while (word[i] != '[=10=]')
    {
        char c = tolower(word[i]);

        // Get the key for each letter
        int key = hash(c);

        // If the node at the key is null then word is misspelled
        if (!ptr)
        {
            return false;
        }
        else
        {
            ptr = ptr->children[key];
            i++;
        }
    }

    // Check if isword at the last letter is true
    if (ptr->is_word)
    {
        return true;
    }
    else
    {
        return false;
    }
}

我希望输出是 FOUND 或 NOT FOUND，但实际输出是一个分段错误。

Answer 1

ptr 可能正在返回 null。

if ((ptr) && (ptr->is_word))
{
    return true;
}
else
{
    return false;
}

Answer 2

您需要检查 ptr 是否不为 null，因为如果您到达字符串的末尾并且它不是您的 trie 中的一个词，它就会为 null。
您还可以压缩代码。

bool check(const char *word)
{
    const node * ptr = root;
    for (int i = 0; ptr != nullptr && word[i] != '[=10=]'; i++)
    {
        ptr = ptr->children[hash(tolower(word[i]))];
    }
    return ptr != nullptr && ptr->is_word;
}

为什么有些词会出现分段错误？而其他人似乎工作正常

Why does some words give segmentation fault? While others seem to work fine

c++

dictionary

trie