利用trie數據結構

Question

因此，我正在實現一個用於從文件中讀取唯一字的trie。我是如何實現它的在線尋找和整個做的這種方式來： //插入在特里樹樹 「

void insert(struct node *head, string str) 
{ 
    int i, j; 
    for(i = 0;i < str.size(); ++i){ 
     //if the child node is pointing to NULL 
     if(head -> next_char[str[i] - 'a'] == NULL){ 
      struct node *n; 
      //initialise the new node 
      n = new struct node; 
      for(j = 0;j < 26; ++j){ 
       n -> next_char[j] = NULL; 
      } 
      n -> end_string = 0; 
      head -> next_char[str[i] - 'a'] = n; 
      head = n; 
     } 
     //if the child node is not pointing to q 
     else head = head -> next_char[str[i] - 'a']; 
    } 
    //to mark the end_string flag for this string 
    head -> end_string = 1; 
} 

從行我的困惑arrise： 」線頭 - > next_char [str [i] - 'a'] == NULL 在這段代碼實現它的所有方式中使用'a'的減法的目的是什麼？

Answer 1

當你的輸入字符串由一些相對較小的固定字母表中的字符組成時，Trie是有意義的。

在這個具體實現中，假設這些字符的範圍是從a .. z,26個總數。

在許多語言中Char類型實際上是Int或Byte，您可以使用它執行算術運算。當你這樣做時，字符的代碼被用作操作數。

考慮到上述情況，很明顯，將字符從一些已知的基於非零範圍映射到基於零的範圍的最簡單方法是從特定字符的代碼中減去範圍的開始元素。

對於'a'..'z'範圍：

when you do ('a' - 'a') you get 0 
'b' - 'a' = 1 
... 
'z' - 'a' = 25