Как заполнить trie в C?

Question

Я пытаюсь написать программу, которая принимает слова и создает trie с каждым узлом trie, являющимся структурой, содержащей один единственный символ.

У меня есть функция, которая анализирует 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 и т. Д. ...

Первое, что мы попробовали, это «доктор», и моя тройка берет первую букву «d» 'и добавляет его к root.branches[0], затем берет' o 'и добавляет его к root.branches[0].branches[0], что является правильным. Но затем он добавляет «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» ... нет необходимости искать «свободное» место, которое действительно убьет выступление trie. Наконец, вам нужен терминатор, например, isWord, чтобы знать, что «врач» - это слово, а «доктри» - нет.