在C中的Trie实现:分段错误

我目前正在哈佛大学做CS50，目标是尽可能以最快的方式将字典加载到任何数据结构中。对于这个习题集，我使用的是一个Trie。

我的代码背后的逻辑如下:

每次读取一个字符
检查树的子节点，如果字符已经存在，如果它等于NULL，我们分配一些空间给它。
光标被设置为我们刚刚分配空间的子节点。
如果我们到达一个单词的末尾("n")，我们将布尔值设置为true，并将光标完全重置为其初始值(我们之前存储在光标->root中)。

我已经尝试了几种实现，其中一些有一些逻辑错误，我不满意，有些给了我分割错误，当我有一个大字典。

下面是我最新实现的代码，基本上发生的事情是，它可以很好地将第一个单词加载到tree结构中，但它在第二个中失败了。接下来的问题是将新节点值设置为子节点(我们为其分配了一些空闲空间)。这背后的逻辑显然是连接树并移动到下一个节点。这是我认为是错误的代码:

curser = curser->children[tolower(ch) - 'a'];

但问题是，它在我的一些其他实现中工作，只有这个它突然停止工作，并在第一个单词后给了我一个分割错误。正如我所说，我是编码的初学者，所以请给我启发和批评我的实现!非常感谢。

#include <stdbool.h>
#include <stdio.h>
#include "dictionary.h"
#include <ctype.h>
#include <stdlib.h>
typedef struct node
{
    bool end;
    struct node* children[27];
    struct node* root;
    struct node* next;
} node;
//global variable used to check the number of words in the trie
int totalwords = 0;
//root node
node* curser;
int ch;
int main(void)
{
    FILE* dict = fopen("text.txt", "r");
    if (dict == NULL)
    {
        printf("Could not open dictionaryn");
        return 1;
    }
    curser = (struct node*) malloc(sizeof(node));
    curser->root = curser;
    for (ch = fgetc(dict); ch != EOF; ch = fgetc(dict))
    {
        if (ch == '')
        {
            curser->end = true;
            curser = curser->root;
            totalwords++;
            printf("%in", totalwords);
        }
        else
        {
            if (isalpha(ch))
            {
                if (curser->children[tolower(ch) - 'a'] == NULL)
                {
                    curser->children[tolower(ch) - 'a'] = (struct node*)malloc(sizeof(node));
                }
                curser = curser->children[tolower(ch) - 'a'];
            }
            else if (ch == ''')
            {
                if (curser->children[26] == NULL)
                {
                    curser->children[26] = (struct node*)malloc(sizeof(node));
                }
                curser = curser->children[26];
            }
        }
    }
    fclose(dict);
    return false;
}

编辑:

我的另一个问题是为什么在我当前的代码中，它无法检测到Null终止符，但它可以检测到新行n?我需要能够检测空终止符，以获得正确的字数。有什么问题吗?

在curser->root=curser;之后，您应该执行以下操作:

curser->end=false;
curser->next=NULL;
for(i=0;i<27;i++)
    curser->children[i]=NULL;

初始化curser内存时，不能保证它的成员会自动分配给NULL和false。

为正在分配memory dynamically.的节点执行此everywhere

您还需要为动态分配内存的每个子节点设置child->root=curser->root

看起来好像这与CS50的Pset5有关，并且您正在尝试实现字典的加载。碰巧，您正在使用fgetc函数从文本文件中读取单个字母，而不是从内存中读取。

当你从内存中读取时，会有一个'' NULL结束符。但是，对于fgetc，您使用stdio从文件中读取，并且该文件中不存在''终止符。由于CS50字典中的单词每行存储一个单词，并且所有行都以'n'("new line")结尾，因此可以这样查找。

相关内容

最新更新

热门标签：