Дифференцируя слова в trie

Question

У меня есть слово «все» в моей тройке и слово «alter», но «alt» - это не слово в trie. Но когда я проверяю «alt», он все равно возвращает true, потому что is_word истинно, поскольку «все» - это слово. Как должна работать эта ошибка.

//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

Вы должны убедиться, что все указатели в новом узле равны нулю, а также установка значения is_word в false. Это, пожалуй, проще всего сделать, используя calloc() для выделения пространства. Создание функции для выделения и проверки ошибок позволяет определить распределение узла. Аналогичным образом, у вас есть два блока символов кода для индексов. Вы должны использовать функции - даже маленькие - более щедро.

Символьный символ для строки данных также не нужен; было бы лучше использовать 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