トライで言葉を区別する

Question

トライに「すべて」という単語があり、「変更」という単語がありますが、「トート」の単語は「トライ」ではありません。しかし、 "alt"をチェックすると、 "all"が単語だったのでis_wordが真であるため、それでもtrueを返します。どのようにこのエラーを処理するはずです。

//Here's the code 
typedef struct node{ 
    bool is_word;  
    struct node *children[27]; 
} node; 

unsigned int wsize=0; 
node * root; 

bool check(const char* word) 
{ 
    // TODO 
    node *chrawler=root; 
    for(int i=0;i<strlen(word)-1;i++) 
    { 
     int t; 
     if(word[i]>=65&&word[i]<=90) 
     {   
      t=word[i]-'A'; 
     } 
     else if(isalpha(word[i])) 
      t=word[i]-'a'; 
     else 
      t=26; 

     if(chrawler->children[t]==NULL) 
      return false; 
     else 
      chrawler=chrawler->children[t]; 
    } 

    if(chrawler->is_word) 
     return true; 
    return false;  

} 

// Load function 
bool load(const char* dictionary) 
{ 
    // TODO 

    FILE *inptr=fopen(dictionary,"r"); 
    if(inptr==NULL) 
    { 
     return false; 
    } 

    node *new_node=malloc(sizeof(node)); 
    root=new_node; 

    char * word=malloc((LENGTH+1)*sizeof(char)); 
    int index=0; 
    for(int c=fgetc(inptr);c!=EOF;c=fgetc(inptr)) 
    { 
     char ch=c; 
     if(ch=='\n') 
     { 
      word[index]='\0'; 
      index=0; 
      node *chrawler=root; 
      for(int i=1;i<strlen(word);i++) 
      { 
        int t; 
        if(isalpha(word[i-1])) 
         t=word[i-1]-'a'; 
        else 
         t=26; 
        if(chrawler->children[t]==NULL) 
        { 
         node *new_node=malloc(sizeof(node)); 
         chrawler->children[t]=new_node; 

         chrawler=chrawler->children[t]; 
        } 
        else 
         chrawler=chrawler->children[t]; 
      } 
      chrawler->is_word=1; 
      wsize++; 

     } 
     else 
     { 
      word[index]=ch; 
      index++; 
     } 

    } 

    return true; 
} 

Answer 1

新しいノード内のすべてのポインタがNULLであるだけでなく、falseにis_word値を設定することを確認する必要があります。これはおそらく、calloc()を使用して領域を割り当てることで最も簡単に実行できます。ノードの割り当てを割り振り、エラーをチェックする機能を作成すると、それが簡単になります。同様に、索引を作成するための2つのコード・マッピング・ブロックがあります。小さなものでもより豊富な関数を使うべきです。

データ行の文字単位の入力は、実際には必要ありません。行を読むにはfgets()を使用する方が良いでしょう。

： -

これらおよび雑貨他の変化の追加（代わりに、動的に割り当てられた配列の例えば、ローカルアレイword解放されなかった;終了時にファイルを閉じるなど）は、このようなMCVE（Minimal, Complete, Verifiable Example）を与えます

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

enum { LENGTH = 256 }; 

// Here's the code 
typedef struct node 
{ 
    bool is_word; 
    struct node *children[27]; 
} node; 

unsigned int wsize = 0; 
node *root; 

static inline int map_char(unsigned char c) 
{ 
    int t; 
    if (isalpha(c)) 
     t = tolower(c) - 'a'; 
    else 
     t = 26; 
    return t; 
} 

static inline node *alloc_node(void) 
{ 
    node *new_node = calloc(1, sizeof(node)); 
    if (new_node == 0) 
    { 
     fprintf(stderr, "Memory allocation failed in %s\n", __func__); 
     exit(1); 
    } 
    return new_node; 
} 

static bool check(const char *word) 
{ 
    node *chrawler = root; 
    int len = strlen(word); 
    for (int i = 0; i < len; i++) 
    { 
     int t = map_char(word[i]); 
     if (chrawler->children[t] == NULL) 
      return false; 
     else 
      chrawler = chrawler->children[t]; 
    } 

    return chrawler->is_word; 
} 

// Load function 
static bool load(const char *dictionary) 
{ 
    FILE *inptr = fopen(dictionary, "r"); 
    if (inptr == NULL) 
    { 
     fprintf(stderr, "Failed to open file '%s' for reading\n", dictionary); 
     return false; 
    } 

    root = alloc_node(); 

    char word[LENGTH]; 
    while (fgets(word, sizeof(word), inptr) != 0) 
    { 
     word[strcspn(word, "\n")] = '\0'; 
     printf("[%s]\n", word); 
     node *chrawler = root; 
     int len = strlen(word); 
     for (int i = 0; i < len; i++) 
     { 
      int t = map_char(word[i]); 
      //printf("t = %d (%c)\n", t, word[i]); 
      if (chrawler->children[t] == NULL) 
       chrawler->children[t] = alloc_node(); 
      chrawler = chrawler->children[t]; 
     } 
     chrawler->is_word = 1; 
     wsize++; 
    } 
    printf("%d words read from %s\n", wsize, dictionary); 
    fclose(inptr); 

    return true; 
} 

int main(void) 
{ 
    const char *wordfile = "words.txt"; 
    if (load(wordfile)) 
    { 
     char line[4096]; 
     while (fgets(line, sizeof(line), stdin) != 0) 
     { 
      line[strcspn(line, "\n")] = '\0'; 
      if (check(line)) 
       printf("[%s] is a word\n", line); 
      else 
       printf("[%s] is unknown\n", line); 
     } 
    } 
    return 0; 
} 

その他の変更が必要です。たとえば、 の変数wsizeはグローバルではありません。それは実際にload()の機能の外で使用されていません。ルートノードもグローバルであってはならないことは容易に議論できる。 load()関数はルートノードを返し、check()関数はルートノードを渡す必要があります。一般的に、グローバル変数は可能な限り避けるべきであり、通常は可能です。

を含むファイル words.txtを考える：

abelone 
abyssinia 
archimedes 
brachiosaurus 
triceratops 
all 
alter 
asparagus 
watchamacallit 
a 
abracadabra 
abyss 
ant 

プログラムの実行からの出力を示します。

[abelone] 
[abyssinia] 
[archimedes] 
[brachiosaurus] 
[triceratops] 
[all] 
[alter] 
[asparagus] 
[watchamacallit] 
[a] 
[abracadabra] 
[abyss] 
[ant] 
13 words read from words.txt 
a 
[a] is a word 
ab 
[ab] is unknown 
al 
[al] is unknown 
all 
[all] is a word 
alt 
[alt] is unknown 
alte 
[alte] is unknown 
alter 
[alter] is a word 
triceratops 
[triceratops] is a word 
brachiosaurus 
[brachiosaurus] is a word 
abys 
[abys] is unknown 
abbey 
[abbey] is unknown 
abyss 
[abyss] is a word 
ant 
[ant] is a word 
a 
[a] is a word 
archimedes 
[archimedes] is a word