Cs50 Speller 未初始化值是由堆分配错误创建的

Question

我有一些代码应该获取字典文件，读取每个单词并将其添加到 trie 数据结构中，在单词的最后一个节点上将 bool 设置为 true。

它可以运行，但是当我稍后在 check() 函数中对照字典检查单词时，它总是说错误。

Valgrind 抛出此错误；

    ==20700== 
    ==20700== Conditional jump or move depends on uninitialised value(s)
    ==20700==    at 0x40116F: load (dictionary.c:114)
    ==20700==    by 0x400834: main (speller.c:40)
    ==20700==  Uninitialised value was created by a heap allocation
    ==20700==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==20700==    by 0x401180: load (dictionary.c:116)
    ==20700==    by 0x400834: main (speller.c:40)
    ==20700== 
    Killed

我环顾四周并添加了循环遍历 children[] 并在创建新节点后初始化为 NULL，但似乎仍然存在问题。

// Represents a node in a trie
typedef struct node
{
    bool is_word;
    struct node *children[N];
}
node;

// Represents a trie
node *root;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize trie
    root = malloc(sizeof(node));
    if (root == NULL)
    {
        return false;
    }
    root->is_word = false;
    for (int i = 0; i < N; i++)
    {
        root->children[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    //declare pointer to store adress of current node
    node *ptr = root;

    // Buffer for a word
    char word[LENGTH + 1];

    for (int i = 0; i < LENGTH + 1; i++)
        {
            word[i] = 0;
        }

    int size = 0;

    // Insert words into trie
    while (fscanf(file, "%s", word) != EOF)
    {

        // make pointer to current place in trie structure and intitialise to root
        ptr = root;

        // make variable to store chaacter as int representing position in alphabet
        int alphaindex;

        // iterate over letters in word
        for (int i =0; i < LENGTH; i++)
        {



            // if word i == to ' character check ptr children and make new node if necesary
            if ((int)&word[i] == '\'')
            {
                alphaindex = 26;
                if (ptr-> children[alphaindex] == NULL)
                {
                    node *n = malloc(sizeof(node));

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

                    root->is_word = false;

                    for (int j = 0; j < N; j++)
                    {
                        root->children[j] = NULL;
                    }


                    // set 27th element of children to new node
                    ptr -> children[alphaindex] = n;
                }

                // set ptr to ptr[26]

                ptr = ptr -> children[alphaindex];

            }

            else
            {

                // adjust alphainex
                alphaindex = islower((int) word[i]) ? (int) word[i] - 97 : (int) word[i] - 65;

                //check location for NULL and make new index if necessary
                if (ptr -> children[alphaindex] == NULL)
                {
                    node *n = malloc(sizeof(node));

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

                    root->is_word = false;

                    for (int k = 0; k < N; k++)
                    {
                        root->children[k] = NULL;
                    }

                    // set children[alphaindex] to new node
                    ptr -> children[alphaindex] = n;

                    //set ptr to new alphaindex element of array which its self points to the new node
                    ptr = ptr -> children[alphaindex];
                }

                else
                {

                //set ptr to new alphaindex element of array which its self points to the new node
                ptr = ptr -> children[alphaindex];

                }


            }



            // if the character is 0 word is over, set is_word and return to while loop
            if((char) word[i + 1] == 0)
            {
                ptr -> is_word = true;
                size ++;
                break;
            }



        }



    }

    printf("Size of dictionary = %i\n", size);

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

我相当确定，由于出现此错误的条件是我评估天气或不创建新节点的地方，因此当我稍后尝试针对它测试单词时，这将导致错误。

在此先感谢您的帮助

亚历克斯

Answer 1

几个紧迫的问题：

如果word包含撇号，root中的所有指针在这里都设置为NULL:

for (int j = 0; j < N; j++)
                    {
                        root->children[j] = NULL;
                    }

打字错误？这将使它们成为 "unfreeable"（更不用说，检查将永远找不到它们）。

else 分支中的相同问题：

for (int k = 0; k < N; k++)
                    {
                        root->children[k] = NULL;
                    }

撇号检查需要离散。看起来程序没有 "save" 足够的指针，但在纠正这些大的结构问题之前，您将无法完成它。

Cs50 Speller 未初始化值是由堆分配错误创建的

Cs50 Speller Uninitialised value was created by a heap allocation error

c

valgrind

cs50