此代码如何工作而不崩溃或段错误？

Question

所以这个问题有点不同，代码有效我只是不知道为什么或如何。 我正在参加 CS50 课程，我正在解决这个练习题，旨在训练我们搜索尝试数据库。目的是创建一个程序，该程序将从 txt 文件中获取狗名并将其排序为 trie 结构，并使用户能够输入名称并给出数据库中给定名称的找到或未找到的结果.

我只写了检查功能，它可以正常工作，但我不明白是怎么回事，也觉得哪里不对劲。它以正确的方式开始，我的 trav 指针设置为根节点，逐个字母地遍历给定的单词，并将值更改为下一个字母，当它到达末尾时，下一个字母显然是用户给出的字符串，这使得 trav->children[letter] 是 trav->children[-97]，这是 trav 结构数组范围之外的东西。然而，它以某种方式起作用并将获得正确的值。我觉得它应该给我一个超出数组范围的段错误。

此时我不知道该尝试什么，因为代码正在运行，我只是不明白为什么

请注意我不是在询问未定义的行为 我的函数必须找到一个 (is_word) 值才能每次返回正确的值，如果我超出数组限制，它如何找到它，即：未定义的行为？

这里是完整的代码

// Saves popular dog names in a trie
// https://www.dailypaws.com/dogs-puppies/dog-names/common-dog-names

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

#define SIZE_OF_ALPHABET 26
#define MAXCHAR 20

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

// Function prototypes
bool check(char *word);
bool unload(void);
void unloader(node *current);

// Root of trie
node *root;

// Buffer to read dog names into
char name[MAXCHAR];

int main(int argc, char *argv[])
{
    // Check for command line args
    if (argc != 2)
    {
        printf("Usage: ./trie infile\n");
        return 1;
    }

    // File with names
    FILE *infile = fopen(argv[1], "r");
    if (!infile)
    {
        printf("Error opening file!\n");
        return 1;
    }

    // Allocate root of trie
    root = malloc(sizeof(node));

    if (root == NULL)
    {
        return 1;
    }

    root->is_word = false;
    for (int i = 0; i < SIZE_OF_ALPHABET; i++)
    {
        root->children[i] = NULL;
    }

    // Add words to the trie
    while (fscanf(infile, "%s", name) == 1)
    {
        node *cursor = root;

        for (int i = 0, n = strlen(name); i < n; i++)
        {
            int index = tolower(name[i]) - 'a';
            if (cursor->children[index] == NULL)
            {

                // Make node
                node *new = malloc(sizeof(node));
                new->is_word = false;
                for (int j = 0; j < SIZE_OF_ALPHABET; j++)
                {
                    new->children[j] = NULL;
                }
                cursor->children[index] = new;
            }

            // Go to node which we may have just been made
            cursor = cursor->children[index];
        }

        // if we are at the end of the word, mark it as being a word
        cursor->is_word = true;
    }

    if (check(get_string("Check word: ")))
    {
        printf("Found!\n");
    }
    else
    {
        printf("Not Found.\n");
    }

    if (!unload())
    {
        printf("Problem freeing memory!\n");
        return 1;
    }

    fclose(infile);
}

// TODO: Complete the check function, return true if found, false if not found
bool check(char* word)
{
    // setting up a trav pointer to iterate through the trie
    node *trav = root;
    // iterating through the word given and descending through the pointers given by its letters
    for (int i = 0, n = strlen(word); i <= n; i++)
    {
        int letter = tolower(word[i]) - 'a';
        // if the next pointer is not null this means there are still letters in the word 
        if (trav->children[letter] != NULL)
        {
            trav = trav->children[letter];
        }
        else
        {
            if (trav->is_word)
            {
                return true;
            }
        }
    }
    return false;
}

// Unload trie from memory
bool unload(void)
{

    // The recursive function handles all of the freeing
    unloader(root);

    return true;
}

void unloader(node* current)
{

    // Iterate over all the children to see if they point to anything and go
    // there if they do point
    for (int i = 0; i < SIZE_OF_ALPHABET; i++)
    {
        if (current->children[i] != NULL)
        {
            unloader(current->children[i]);
        }
    }

    // After we check all the children point to null we can get rid of the node
    // and return to the previous iteration of this function.
    free(current);
}

Answer 1

未压缩的 trie 有很多内存为零。在现代架构中，几乎所有空指针都是 all-bits-zero，并且

is_word

也可能为零。一个指针和一个

bool

可能比一个字节大得多。内存中有很多零，因此遇到非零的可能性很小。这意味着，在这种情况下，该程序恰好可以在您的架构上运行。

您应该按照插入时转换它们的相同方式转换

letter

中的

check

。也就是说，测试''，如果是，则检查

is_word

，小写，减去'a'，拒绝所有落在0-25之外的内容。

例如，如果您有一个文本文件，

菲多 霸王龙

未压缩，即 1 + 4 + 3 = 8

node

。假设

sizeof node

是216字节。那是 1728 字节。假设它们是连续分配的。两个词表示两个 1 和

(4 + 3) 8 = 56 + 2 = 58 / 1728

。保守地说，仅从结构来看，就有 97% 为零。