c - C 语言 Trie 实现中的段错误

Question

我正在尝试实现一个 trie 数据结构来对给定的文本文件进行拼写检查。目前，它似乎适用于文件中的几个单词，然后出现段错误。我尝试调试来找到罪魁祸首，但我发现“letter”的值保留了看似随机的负值(它应该在 1 到 27 之间，包括 1 和 27)。通常，seg错误问题几乎在我启动程序后立即出现，所以我不确定为什么问题会在程序中间弹出。

    /**
     * Implements a dictionary's functionality.
     */

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

    #include "dictionary.h"


    //create global root node
    Trienode *root;
    //create word counter for size() function
    unsigned int wordcount = 0;

    //creates an empty node
    Trienode * newnode()
    {
        Trienode *nnode = NULL;
        nnode = (Trienode *)malloc(sizeof(Trienode));
        //initialize new node with null pointers and values
        nnode -> parent = NULL;
        for(int i = 0; i < 27; i++)
        {
            nnode -> children[i] = NULL;
        }
        return nnode;
    }

    void cleartrie(Trienode *head)
    {
        //if child node exists, free it, else continue with next iteration in for loop
        if(head)
        {
            for(int i = 0; i < 27; i++)
            {
                cleartrie(head -> children[i]);
            }
            free(head);
            head = NULL;
        }
    }

    /**
     * Returns true if word is in dictionary else false.
     */
    bool check(const char *word)
    {
        int i = 0;
        int letter;
        Trienode *head = root;

        while(word[i] != '\0')
        {
            if(isalpha(word[i]))
            {
                letter = word[i] - 'a';
            }
            else //it must be an apostrophe
            {
                letter = word[i] - 13;
            }
            if(!(head -> children[letter]))
            {
                return false;
            }
            else //a pointer must exist
            {
                head = head -> children[letter];
            }
            i++;
        }
        return true;
    }

    /**
     * Loads dictionary into memory. Returns true if successful else false.
     */
    bool load(const char *dictionary)
    {
        //open file
        FILE *infile = fopen(dictionary, "r");
        Trienode *parnode; //parent node
        root = newnode();
        Trienode *curnode = root; //current node

        int letter = 0;
        //while not end of file, read words
        while(fgetc(infile) != EOF)
        {
            //while not end of word, read letters
            for(;;)
            {
                int c;
                //read current letter in file
                c = fgetc(infile); 
                //convert input char to corresponding array location (a - z = 0-25, apostrophe = 26)
                if(isalpha(c))
                {
                    letter = c - 'a';
                }
                else if (c == '\'')
                {
                    letter = c - 13;
                }
                //if end of string, exit loop
                else if (c == '\0')
                {
                    //end of word, so endofstring = true
                    wordcount++;
                    break;
                }
                //move to next letter if not either apostrophe or alphabetical
                else
                {
                    break;
                }
                //if pointer to letter of word doesn't exist, create new node
                if(curnode -> children[letter] == NULL)
                {
                    curnode -> children[letter] = newnode();
                }
                //child node is the new current node
                parnode = curnode;
                curnode = curnode -> children[letter];
                curnode -> parent = parnode;

            }
            //return to root node
            curnode = root;
        } 

        fclose(infile);
        return true;
    }


    /**
     * Returns number of words in dictionary if loaded else 0 if not yet loaded.
     */
    unsigned int size(void)
    {
        return wordcount;
    }

    /**
     * Unloads dictionary from memory. Returns true if successful else false.
     */
    bool unload(void)
    {
        cleartrie(root);
        if (root == NULL)
        {
            return true;
        }
        return false;
    }

对文字墙感到抱歉，但其中大部分只是为了提供上下文(我希望)。检查辅助函数的 if(!(head -> Children[letter])) 行上发生了 seg 错误。

提前致谢!

Answer 1

我怀疑您的测试文件可能包含一些大写字母。如果是这种情况，则减去 'a'尝试重新映射您的字母将导致负数，因为 'A' < 'a' 。看看ASCII Table 。首先将字母转换为小写应该可以解决您的问题。