利用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