c - 如何在C中填充一个trie树？

Question

我正在尝试编写一个程序，它接受单词并创建一个特里树，其中特里树的每个节点都是包含一个字符的结构。

我有一个将 char* 解析为单词的函数(假设 char* 仅包含小写字母)。由于每个单词均取自 char*，因此它被传递给函数 addWordOccurrence(const char* word, const int wordLength, struct tNode root) 。 addWordOccurrence()应该检查该单词的第一个字母是否在 root.branches[i] 中当我在循环中递增时，检查 root.branches 的每个可能的索引(对于字母表中的所有小写字母来说，范围是 0-25)。如果第一个字母不在 root.branches 中一个新的结构tNode创建包含新字母。然后继续查看该单词的第二个字母，将其与新创建的结构 tNode 的分支进行比较等等...

我们尝试的第一个单词是“doctor”，我的字典树采用第一个字母“d”并将其添加到 root.branches[0] 中。然后将“o”添加到 root.branches[0].branches[0] ， 哪个是对的。但随后它将 doctor 中的 'd' 添加到其分支的接下来 17 个索引中(因此 root.branches[0].branches[1] through [18] )，但事实并非如此。请帮忙!

struct tNode{
  char c;
  int occurrences;
  struct tNode *branches;
};

int addWordOccurrence(const char* word, const int wordLength, struct tNode root){
//declare fields
int counter, i,k,firstNull;
counter = 0;
while(1){
  if(counter >= wordLength){
    break;
  }
  //traverse through the word letter by letter
  for(i=0; i<wordLength; i++){
    //compare each letter to the branches of root until the letter is found or first null space
    for(k=0; k<26; k++){
    //if the letter is a branch already set root to the struct of that letter in branches
       if(root.branches[k].c == word[i]){
          root = root.branches[k];
          break;
       }
    }
    //the current letter of the word is not in branches
    //go through branches to find position to add the new tNode
    for(firstNull=0; firstNull<26; firstNull++){
       //set firstNull equal to the index of the first null value in branches
       if(root.branches[firstNull].c  <  'a' || root.branches[firstNull].c > 'z' ){
          break;
       }
    }
    //add a new node to branches
    root.branches[firstNull].c = word[i];
    root.branches[firstNull].occurrences = 0;
    root.branches[firstNull].branches = malloc(sizeof(struct tNode) * 26);
    if(counter != wordLength){
       root = root.branches[firstNull];
    }
    counter++;
    if(counter == wordLength-2){
       root.occurrences++;
    }
 }
}
 return 0;
}

Answer 1

您的实现存在一系列问题:

1. 这是一个奇怪的特里树设计，字母表是随机排列的。必须在每个级别上对您想要的字母进行线性搜索就违背了进行特里树的目的。
2. 当你这样做时root = root.branches[k];您正在创建该变量的副本。现在，在这种情况下，由于通过指针访问事物，它可能恰好适合您，但这实际上只是自找麻烦。
3. 当您在循环中分配节点时，您不会初始化它，这意味着它充满了垃圾/未知数据并导致问题。
4. 您的实现不必要地复杂，就像您的外部 while (1)循环。

对于一个非常简单的特里树，我会做类似的事情:

struct tNode {
  bool isWord;
  struct tNode *branches[26];
};

void addWordOccurrence (const char* word, const int wordLength, struct tNode* pRoot) {
   int i;
   int nodeIndex;
   tNode* pCurrentNode = pRoot;

   for (i = 0; i < wordLength; ++i)
   {
       nodeIndex = tolower(word[i]) - 'a'; 

       if (nodeIndex >= 0 && nodeIndex <= 25)
       {
            if (pCurrentNode->branches[nodeIndex] == NULL)
            {
                pCurrentNode->branches[nodeIndex] = calloc(1, sizeof(tNode));
            }

            pCurrentNode = pCurrentNode->branches[nodeIndex];
       }
   }

   pCurrentNode->isWord = true;
}

您可以使用struct tNode *branches;但它实际上只是添加了您并不真正需要的另一个分配步骤。您使用字符的 ASCII 值来分配 branches[0]到“a”和branches[25]到“z”...无需搜索“空闲”位置，这会真正影响特里的性能。最后，你需要一个像 isWord 这样的终结符为了知道“doctor”是一个单词而“docto”不是一个单词。