1

私は現在、ハーバードから CS50 を行っています。目標は、可能な限り最速の方法で辞書を任意のデータ構造にロードすることです。この問題セットでは、Trie を使用しています。

私のコードの背後にあるロジックは次のとおりです。

  1. 一度に 1 文字ずつ読み取ります。
  2. 文字がすでに存在する場合はトライの子ノードをチェックインし、NULL に等しい場合はそれにスペースを割り当てます。
  3. カーソルは、領域を割り当てたばかりの子ノードに設定されます。
  4. 単語の終わり ("\n") に到達すると、ブール値を true に設定し、カーソルを完全に初期値 (curser->root に以前に保存した値) にリセットします。

私はいくつかの実装を試しましたが、いくつかの論理エラーがあり満足できませんでした。また、大きな辞書を持っていたときにセグメンテーション違反が発生したものもありました。

以下は私の最新の実装のコードです。基本的に、最初の単語をトライ構造にロードすることは問題ありませんが、2 番目の単語では失敗します。問題は、新しいノード値を childenode (空き領域を割り当てた場所) に設定することにあります。この背後にあるロジックは、明らかにツリーを接続して次のノードに移動することです。これは私が間違っていると思うコードです：

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;
}

編集：

もう 1 つの質問は、現在のコードで Null ターミネータ \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;

curser のメモリを初期化する場合、そのメンバーが and に自動的に割り当てられるとは限りませNULLんfalse。

everywhere割り当てているノードに対してこれを行いますmemory dynamically.

child->root=curser->rootまた、メモリを動的に割り当てるすべての子に対して設定する必要があります

于 2014-06-30T12:06:26.233 に答える
0

これは CS50 の Pset5 に関連しているようで、辞書のロードを実装しようとしています。たまたま、fgetc関数を使用して、メモリからではなく、テキスト ファイルから単一の文字を読み取っています。

メモリから読み取る場合'\0'、単語の NULL ターミネータがあります。ただし、fgetcstdio を使用してファイルから読み取ると、'\0'ターミネータがそのファイルに存在しません。CS50 辞書の単語は 1 行に 1 単語格納され、すべての行が'\n'(「改行」) で終わるため、そのように見つけることができます。

于 2015-03-14T04:19:22.767 に答える