Ekleme
Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 5 / 14.
Trie yapısına bir kelime eklemek için, kökten başlayarak her seferinde bir karakter aşağı doğru ilerleyin. Kelimenin her bir karakteri için: eğer mevcut düğümün o karakter için bir alt düğümü yoksa, yeni bir TrieNode oluşturun ve onu ekleyin. Her iki durumda da, o alt düğüme geçin ve bir sonraki karakterle devam edin.
Kelimenin sonuna ulaştığınızda, vardığınız düğümü isEndOfWord = true olarak işaretleyin. Bu bayrak, daha sonra gerçek bir kayıtlı kelimeyi, sadece başka bir şeyin öneki olduğu için var olan bir yoldan ayıran şeydir.
Önce "cat" ve ardından "car" eklemek, c -> a yolunu paylaşır ve yalnızca üçüncü karakterde dallanır. Bu paylaşım, trie yapılarını sözlükler için alan açısından bu kadar verimli kılan şeydir.
Görev
KolayTrie sınıfına bir insert metodu ekleyin.
Bu metot bir word dizesi alır ve onu trie içinde saklar:
rootdüğümünden başlayın.wordiçindeki her birckarakteri için, mevcut düğümünciçin bir alt düğümü (child) yoksa, oraya yeni birTrieNodeekleyin.- O alt düğüme geçin ve devam edin.
- Son karakterden sonra, ulaşılan son düğümün
isEndOfWordözelliğinitrueolarak işaretleyin.
Kendin dene
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
}
return 0;
}