1

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

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

  1. 一次读一个字符。
  2. 如果字符已经存在，则检查 trie 的子节点，如果它等于 NULL，我们为其分配一些空间。
  3. 光标设置为我们刚刚分配空间的子节点。
  4. 如果我们到达一个单词的结尾（“\n”），我们将布尔值设置为 true 并将光标完全重置为其初始值（我们之前存储在光标->根中）。

我尝试了几种实现，其中一些有一些我不满意的逻辑错误，当我有一本大字典时，有些给我带来了分段错误。

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

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 dictionary\n");
        return 1;
    }

    curser = (struct node*) malloc(sizeof(node));
    curser->root = curser;

    for (ch = fgetc(dict); ch != EOF; ch = fgetc(dict))
    {
        if (ch == '\0')
        {
            curser->end = true;
            curser = curser->root;
            totalwords++;
            printf("%i\n", 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 Terminator \0 但它可以检测到新行 \n？我需要能够检测空终止符才能获得正确数量的单词。关于什么是错的任何建议？

4

2 回答 2

3

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

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

当您为光标初始化内存时，不能保证它的成员会自动分配给NULLand false。

everywhere为您分配的节点执行此操作memory dynamically.

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

于 2014-06-30T12:06:26.233 回答
0

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

当您从内存中读取时，该单词会有一个'\0'NULL 终止符。但是，fgetc您正在使用 stdio 从文件中读取，并且该文件'\0'中不存在终止符。由于 CS50 字典中的单词每行存储一个单词，并且所有行都以'\n'（“新行”）结尾，因此可以这样找到。

于 2015-03-14T04:19:22.767 回答