>> SPEAKER 1: Diamo questa soluzione una prova.
Quindi diamo un'occhiata a ciò che il nostro Struct node sarà simile.
Qui, vediamo che stiamo andando ad avere un Bool Word e un nodo stella Struct
Bambini staffa alfabeto.
Quindi, prima cosa che si potrebbe chiedere, perché è l'alfabeto hash definito come 27?
Beh, ricordiamo che stiamo andando ad avere bisogno essere la manipolazione l'apostrofo, così
che sta per essere un po 'speciale caso nel corso di questo programma.
>> OK, ora, ricordare come una Trie funziona realmente.
Diciamo che stiamo indicizzando la parola gatti, poi dalla radice della nostra Trie,
stiamo andando a guardare i bambini array, e stiamo andando a guardare il
indice che corrisponde alla lettera C. So che sarebbe indice due.
Quindi dato che, che ci darà un nuovo nodo, e poi faremo
lavorare da quel nodo.
>> Quindi, dato che il nodo, siamo ancora una volta andando a guardare la matrice dei bambini,
e stiamo andando a guardare indice zero corrispondere alla A in cat.
Allora stiamo per andare a quel nodo, e dato che il nodo, stiamo andando
a guardare l'indice che corrisponde a T. E passare a quel nodo,
Infine, abbiamo completamente guardato attraverso la nostra parola Gatto, e ora Bool
Word dovrebbe indicare se Questa parola data è in realtà una parola.
>> Allora, perché abbiamo bisogno che il caso speciale?
Ebbene, che cosa se la parola catastrofe è nel nostro dizionario, ma
la parola gatto non è?
Quindi, in cercando di vedere se la parola gatto è nel nostro dizionario, stiamo andando a
guardare con successo attraverso gli indici C-A-T e raggiungere un nodo, ma questo è
solo perché la catastrofe è successo a creare nodi sulla strada da C-A-T tutti
fino alla fine della parola.
Così Bool Word viene usato indicare se questa posizione particolare realtà
indica una parola.
>> Va bene, ora che sappiamo cosa sia una Trie è andare a guardare come, diamo un'occhiata
alla funzione Load.
Così Load sta per restituire un Bool per se abbiamo successo o
dizionario e senza successo caricati questo sta andando essere il dizionario
che vogliamo caricare.
Quindi prima cosa che andremo a fare è aprire a quel dizionario per la lettura.
Dobbiamo fare in modo noi non falliamo, quindi se il dizionario non era
aperto con successo, verrà restituito No, in questo caso andremo a
ritorno False.
Ma supponendo che successo aperto, allora possiamo davvero leggere
attraverso il dizionario.
>> Quindi prima cosa che andremo a vogliamo fare è che abbiamo questa
radice variabile globale.
Ora, radice sta per essere una stella nodo.
E 'la parte superiore della nostra Trie che siamo sta per essere scorrendo.
Quindi prima cosa che andremo a voler fare è allocare memoria per la nostra radice.
>> Si noti che stiamo usando il calloc funzione, che è sostanzialmente la stessa
come funzione Malloc, tranne che è garantito per restituire qualcosa che è
completamente azzerato.
Quindi, se abbiamo usato Malloc, avremmo bisogno di passare attraverso tutti i puntatori nella nostra
nodo e fare in modo che sono tutti nulli.
Così calloc lo farà per noi.
>> Ora, proprio come Malloc, abbiamo bisogno di fare Assicurarsi che la ripartizione realtà
successo.
Se questo restituito un valore nullo, allora necessario chiudere nostro dizionario
file e restituire False.
Quindi, supponendo che l'assegnazione è stata successo, stiamo andando a utilizzare un nodo
stella cursore per scorrere attraverso il nostro Trie.
Così la nostra radice è mai cambierà, ma abbiamo intenzione di utilizzare il cursore per
effettivamente andare da nodo a nodo.
>> Va bene, quindi in questo ciclo For, siamo lettura attraverso il file dizionario,
e stiamo usando a fgetc.
Così fgetc sta per afferrare un unico carattere dal file.
Abbiamo intenzione di continuare a catturare personaggi mentre noi non raggiungiamo l'
fine del file, quindi non ci sono due casi dobbiamo gestire.
La prima, se il carattere non era nuova linea, in modo da sapere se si trattava di un nuovo
linea, allora stiamo per passare ad una nuova parola.
Ma ammesso che non era una nuova linea, quindi qui, vogliamo capire il
Indice stiamo per indicizzare nella matrice bambini che
abbiamo guardato prima.
>> Così come ho detto prima, abbiamo bisogno di caso particolare l'apostrofo.
Notate che stiamo usando l'operatore ternario qui, così stiamo andando a leggere
questo come se il personaggio si legge in è stato un apostrofo, allora stiamo andando a
impostare indice pari alfabeto meno 1, che sarà l'indice 26.
Altrimenti, se non fosse un apostrofo, allora stiamo andando a impostare l'indice
pari a C meno.
Quindi ricordatevi di ritorno da set p precedenti, c meno una sta per darci l'
posizione alfabetica di c, quindi se c è la lettera A, questa volontà
darci indice zero.
Per la lettera B, darebbe noi l'indice 1, e così via.
>> Quindi questo ci dà l'indice nella I bambini matrice che vogliamo.
Ora, se questo indice è attualmente nullo in la matrice bambini, che significa che
un nodo attualmente non esiste da tale percorso, quindi abbiamo bisogno di destinare una
nodo per quel percorso.
Questo è quello che facciamo qui.
Quindi stiamo andando, ancora una volta, utilizzare il calloc funzione in modo che non abbiamo
per azzerare tutti i puntatori, e noi, ancora una volta, è necessario verificare che calloc
non ha mancato.
Se calloc ha mancato, allora abbiamo bisogno per scaricare tutto, chiudere il nostro
dizionario, e restituire False.
>> Quindi, supponendo che non ha mancato, poi questo creerà un nuovo figlio per noi,
e poi andremo a quel bambino.
Il nostro cursore scorrere fino a quel bambino.
Ora, se questo non fosse nullo per cominciare, poi il cursore può solo scorrere
fino a quel bambino senza realmente dover allocare nulla.
Questo è il caso in cui abbiamo prima accademmo di destinare la parola gatto, e
questo significa che quando andiamo a destinare catastrofe, non abbiamo bisogno di creare
nodi per C-A-T di nuovo.
Essi esistono già.
>> OK, allora che cosa è questo altro?
Questa è la condizione in cui c era backslash n, dove c era una nuova linea.
Questo significa che abbiamo successo completato una parola.
Ora, che cosa vogliamo fare quando si completato con successo una parola?
Stiamo andando a utilizzare questo campo parola interno del nostro nodo Struct.
>> Vogliamo impostare che a True, in modo che indica che questo nodo indica un
parola successo una parola vera.
Ora, impostare tale true.
Vogliamo ripristinare il nostro cursore sul punto all'inizio del trie nuovamente.
E, infine, incrementare nostro dizionario dimensioni dato che abbiamo trovato un'altra parola.
>> Va bene, quindi abbiamo intenzione di continuare a fare che, leggendo nel carattere da
carattere, la costruzione di nuovi nodi in la nostra Trie e per ogni parola nel
dizionario, fino a quando raggiungiamo finalmente c uguale EOF, in questo caso, noi spezziamo
dal file.
Ora, ci sono due casi sotto che avremmo potuto colpire EOF.
La prima è se c'è stato un errore leggendo il file, quindi se ci fosse
un errore, dobbiamo fare il tipico scarico tutto, chiudere il file,
ritorno False.
Supponendo che non c'è stato un errore, che semplicemente significa che in realtà ha colpito la fine del
il file, nel qual caso, si chiude l' file e restituire True dato che
caricato correttamente il dizionario nel nostro Trie.
>> Va bene, così ora cerchiamo di Estrai.
Guardando la funzione di controllo, vediamo Controlla che sta per restituire un Bool.
Restituisce True se questa parola che è essere passato è nella nostra Trie.
Esso restituisce False altrimenti.
>> Quindi, come facciamo a stabilire se questa parola è nel nostro Trie?
Vediamo qui che, proprio come prima, stiamo andando a utilizzare il cursore per scorrere
attraverso il nostro Trie.
Ora, qui, stiamo andando a scorrere su tutta la nostra parola.
Così l'iterazione sulla parola siamo passato, stiamo andando a determinare il
indice nella matrice bambini che corrisponde alla staffa parola i.
Quindi questo sta a guardare esattamente come Load, dove se la staffa parola i è un
apostrofo, poi vogliamo usare l'indice alfabeto meno 1 perchè abbiamo determinato
che è dove stiamo andando memorizzare apostrofi.
>> Altrimenti andremo a utilizzare tolower Staffa parola i.
Quindi ricorda che la parola può avere arbitrario capitalizzazione, e quindi abbiamo
vuole fare in modo che stiamo usando una versione minuscola delle cose.
E quindi sottrarre da questo minuscolo una, ancora una volta, ci dia la
posizione alfabetica di quel personaggio.
Quindi, che sta per essere il nostro indice nella matrice dei bambini.
>> E ora, se tale indice nei bambini array è null, questo significa che
non può più continuare l'iterazione giù la nostra Trie.
Se questo è il caso, questa parola non può forse nella nostra Trie, perché se
stati, ciò significherebbe ci sarebbe un discesa a quella parola, e si sarebbe
mai incontrare null.
Così incontrando nullo, torniamo False.
La parola non è nel dizionario.
Se non fosse nullo, allora stiamo andando a continua iterazione, quindi stiamo andando
per aggiornare il nostro cursore per puntare a quella particolare nodo a tale indice.
>> Quindi noi continuiamo a fare che per tutto l'intera parola.
Supponendo che non abbiamo mai colpito nulla, il che significa siamo stati in grado di ottenere attraverso l'intera
mondo e trovare un nodo nella nostra Trie, ma non siamo ancora del tutto finito.
Noi non vogliamo tornare solo true.
Vogliamo tornare il cursore parola errore dal momento che, ricordiamo ancora una volta, se il gatto non è
nel nostro dizionario e la catastrofe è, allora avremo successo ottenere attraverso
la parola del gatto, ma la parola del cursore sarà falso e non vero.
Quindi torniamo cursore parola per indicare se questo nodo è in realtà una parola,
e questo è tutto per il check.
>> Quindi diamo un'occhiata Size.
Così Dimensioni sta per essere abbastanza facile poiché, ricordate in carico, siamo
incrementando le dimensioni del dizionario per ogni parola che incontriamo.
Così Size è solo andare a ritorno dimensione del dizionario, e questo è tutto.
>> Va bene, quindi, infine, abbiamo Unload.
Così Unload, stiamo andando a utilizzare un funzione ricorsiva per fare realtà tutti
del lavoro per noi, così la nostra funzione sta per essere chiamato Scaricatore.
Che cosa sta Scaricatore intenzione di fare?
Vediamo qui che Scaricatore sta per iterare su tutti i bambini al
questo particolare nodo, e se il bambino nodo non è nullo, allora stiamo andando a
scaricare il nodo figlio.
>> Quindi questo sta andando in modo ricorsivo scaricare tutti i nostri figli.
Una volta che siamo sicuri che tutti i nostri figli sono stati scaricati, poi abbiamo
può liberare noi stessi, in modo da scaricare noi stessi.
Quindi questo ricorsivamente scaricare la intero Trie, e poi una volta che è
fatto, possiamo solo tornare Vero.
Unload non può fallire, siamo solo liberando le cose.
Quindi, una volta che abbiamo finito liberando tutto, di ritorno Vero.
E questo è tutto.
Il mio nome è Rob, e questo era [incomprensibile].