Inserimento
Lezione 5 di 14 del corso Trie - Serie sulle strutture dati n. 8 di Coddy.
Per inserire una parola nel trie, scendi dalla radice un carattere alla volta. Per ogni carattere della parola: se il nodo corrente non ha un figlio per quel carattere, crea un nuovo TrieNode e collegalo. In entrambi i casi, passa a quel figlio e continua con il carattere successivo.
Quando raggiungi la fine della parola, contrassegna il nodo raggiunto con isEndOfWord = true. È questo flag che in seguito distingue una parola effettivamente memorizzata da un percorso che esiste solo perché è il prefisso di qualcos'altro.
Inserire "cat" e poi "car" condivide il percorso c -> a e si dirama solo al terzo carattere. Questa condivisione è ciò che rende i trie così efficienti in termini di spazio per i dizionari.
Sfida
FacileAggiungi un metodo insert alla classe Trie.
Riceve una stringa word e la memorizza nel trie:
- Parti da
root. Per ogni caratterecinword, se il nodo corrente non ha un figlio perc, aggiungi lì un nuovoTrieNode. - Spostati in quel figlio e continua.
- Dopo l'ultimo carattere, imposta
isEndOfWorddel nodo finale sutrue.
Provalo tu
#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;
}
Tutte le lezioni di Trie - Serie sulle strutture dati n. 8
Esercitati da solo: Compilatore C online