在Trie結構中添加單詞C

Question

嗨我正在嘗試爲英語創建一個trie結構以西班牙單詞詞典。

這是我到目前爲止有：

struct s_trie_node 
{ 
    char * translation; /* NULL if node not a word */ 
    char * word; 

    /* pointer array to child nodes */ 
    struct s_trie_node * children[UCHAR_MAX+1]; 
}; 

int add_word(const char * word, char * translation) { 
    /* TODO: add word to trie structure 
    If word exists, append translation to existing string 
    Be sure to store a copy of translation, since 
    the string is reused by load_dictionary() 
    */ 
    struct s_trie_node * curr = proot; 
    char * currLetter = word; 
    while (currLetter != '\0') { 
     while ((curr -> children) != NULL) { 
      char * currChildLetter = ((curr -> children) -> word); 
      char * copyWord = word; 
      while (copyWord == currChildLetter) { 
       copyWord++; 
       currChildLetter++; 
      } 
      if (currChildLetter == '\0') { 
       curr = (curr -> children); 
       break; 
      } 
      (curr -> children)++; 
     } 
     currLetter++ 
    } 
} 

我不知道在哪裏可以從這裏走。任何幫助，將不勝感激。謝謝！

Answer 1

嗯，我認爲你的add_word函數太大了。先嚐試並將其分解成更小的問題。一旦你解決了小問題，更大的問題可能會變得更容易。

首先，我們必須實際創建Trie節點（試圖在add_word中執行此操作會很難看）。所以，讓我們現在做一個函數，它是：

/* Allocates, initializes, and returns a new Trie node. The node will contain 
* a copy of word and trans, rather than use them directly. The children array 
* will be initialized to all NULL's. 
*/ 
struct s_trie_node * trie_node_create(const char * prefix, const char * trans) 
{ 
    struct s_trie_node * n = malloc(sizeof(struct s_trie_node)); 
    int i; 

    n->word = prefix ? strdup(prefix) : strdup(""); 
    n->translation = trans ? strdup(trans) : NULL; 
    for (i = 0; i < UCHAR_MAX + 1; i++) 
     n->children[i] = NULL; 
    return n; 
} 

你應該注意到，我們正在創建的字符串的副本，而不是直接使用它們。這使得Trie圖書館的用戶可以更輕鬆地生活，也可以讓我們在不再需要時釋放它們，而無需擔心用戶是否在其他地方使用它們。然而，這是一個重要的決定，因爲它意味着我們有責任確保這些字符串在以後被釋放。此外，我們正在使用strdup，這意味着我們假設傳遞給我們的字符串是「乾淨的」（即以NULL字符結尾）。

不管怎樣，現在我們可以創建節點。讓我們繼續討論更多與Trie相關的問題。顯然，你將需要能夠找出2個字符串的公共前綴的長度。如果你不能做到這一點，你不能做任何事情。因此，我們可以使用以下功能：

/* Returns length of common prefix of v & w. */ 
int match(char * v, char * w) 
{ 
    char * start = v; 
    for (; *v && *v == *w; v++, w++); 
    return v - start; 
} 

這是非常基本的，但是是必要的。當我們比較一個字與一個前綴節點時，知道這個通用前綴的長度會告訴我們它是完全匹配還是部分匹配。完全匹配意味着我們只需要更新節點。部分匹配可能導致子節點不得不被「分裂」爲2，這很可能意味着我們必須沿着Trie進一步下去。這種分割節點的想法是至關重要的。如果列表中只有一個單詞，例如。 「hello」，那麼將只有2個節點：根節點（空字符串）和根節點的唯一子節點「hello」。如果我們現在想添加另一個與「hello」共享前綴的詞，例如。 「hey」，我們需要將「hello」分成兩個節點：「he」，根節點的孩子，以及「llo」的孩子「llo」。所以，讓我們創建一個函數，將處理拆分節點爲我們：

/* Creates a new node that is a child of n. The word stored at n will be 
* truncated after location (index into n->word), with the remaining suffix 
* of the word belonging to the new child of n. 
*/ 
struct s_trie_node * trie_node_split(struct s_trie_node * n, int location) 
{ 
    struct s_trie_node * child; 
    char * prefix; 
    char * suffix; 
    int len = strlen(n->word); 

    if (location <= 0) 
     return NULL; 
    if (location >= len) 
     return n; 

    prefix = strndup(n->word, location); 
    suffix = strndup(n->word + location, len - location); 

    child = trie_node_create(suffix, n->translation); 
    memcpy(child->children, n->children, 
     sizeof(struct s_trie_node *) * UCHAR_MAX); 
    free(n->word); 
    n->word = prefix; 
    n->translation = NULL; 
    n->children[0] = child; 
    n->children[1] = NULL; 
    return n; 
} 

由於能夠找到共同的前綴長度2串之間，創建節點和分裂節點，我們需要所有的基本操作操縱和穿越我們的Trie。

現在，遞歸通常非常適合Trie結構。所以，假設你有一個trie（根節點）和一個單詞來匹配Trie。這個詞或者與我們的一個孩子共享一個共同的前綴，或者它不會。如果沒有，那麼我們可以簡單地創建一個新的節點，其值是這個詞並將其添加到我們的孩子列表中。但是，如果是這樣，那麼我們會遇到幾種不同的情況，具體取決於常用前綴的長度。

案例1：單詞與我們的孩子完全匹配（也就是說，單詞是相同的）。在這種情況下，我們的孩子與這個詞完全匹配，我們可以簡單地更新翻譯並停止（不需要創建任何新節點）。案例2：這個詞的全部內容是我們孩子的前綴。在這種情況下，我們需要將孩子分成兩部分;第一個是我們的詞，第二個是先前存儲在我們孩子的單詞的其餘部分。第一部分成爲新生兒，我們將翻譯存儲在其中，第二部分成爲我們孩子的孩子。案例3：我們的孩子整體上是這個詞的前綴。在這種情況下，我們從單詞中刪除共同前綴（將單詞縮短爲僅後綴）。然後，我們將該詞的後綴添加到植根於我們孩子的子樹（即遞歸）中。

案例4：通用前綴比兩個單詞都短。在這種情況下，我們需要先分裂孩子。前綴成爲新的孩子，後綴爲孩子的孩子。然後，我們刪除單詞中的前綴，然後將該單詞的其餘部分添加到植根於我們孩子的子樹（即遞歸）中。

這就是全部4種情況。有了這個武裝，我們現在可以輕鬆編寫一個函數來處理這些情況，使用遞歸遍歷樹。

/* Add a translation to the Trie rooted at root. */ 
int trie_add_word(struct s_trie_node * root, char * word, char * trans) 
{ 
    struct s_trie_node ** n; 
    int loc; 

    for (n = root->children; *n; n++) { 
     /* Find length of longest common prefix. */ 
     loc = match(word, (*n)->word); 

     if (!loc) { 
      continue; 

     } else { 
      if (loc != strlen((*n)->word)) 
       trie_node_split(*n, loc); 

      word += loc; 
      if (!*word) { 
       if ((*n)->translation) 
        free((*n)->translation); 
       (*n)->translation = strdup(trans); 
       return 0; 
      } 

      return trie_add_word(*n, word, trans); 
     } 
    } 

    /* Failed to find any children that matched. */ 
    if (n - root->children >= UCHAR_MAX) { 
     fprintf(stderr, "Ran out of room to store children in."); 
     return -1; 
    } 
    *n = trie_node_create(word, trans); 
    return 0; 
} 

就是這樣！我想，答案很長，但很有趣。