trie의 단어 차별화

Question

내 트라이에 "all"이라는 단어가 있고 "alt"라는 단어가 있지만 "alt"는 트라이의 단어가 아닙니다. 그러나 "alt"를 검사 할 때 "all"이 단어이므로 is_word가 true이기 때문에 여전히 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()을 사용하여 공간을 할당함으로써 가장 쉽게 수행 할 수 있습니다. 노드 할당을 할당하고 오류를 검사하는 기능을 생성하면 더 쉽게 사용할 수 있습니다. 마찬가지로 색인을 작성하는 데 두 개의 코드 매핑 문자 블록이 있습니다. 작은 기능이라 할지라도 함수를 더 관대하게 사용해야합니다.

데이터 행에 대한 문자 단위 입력은 실제로 필요하지 않습니다. 줄을 읽으려면 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