[GIOCO MUSICA] 

ROB BOWDEN: Ciao. Sono Rob. E cerchiamo di questa soluzione fuori. Così qui stiamo andando a implementare una tabella generale. Si vede che il nodo struct del nostro tabella è andare a guardare come questo. Così sta andando ad avere un carattere normale array di dimensioni LUNGHEZZA + 1. Non dimenticare il + 1, dato che il massimo parola nel dizionario è di 45 caratteri. E poi stiamo andando ad avere bisogno uno in più caratteri per lo zero backslash. 

E allora la nostra hashtable in ogni benna sta per memorizzare un lista concatenata di nodi. Non stiamo facendo scansione lineare qui. E così, al fine di collegare al successivo elemento nel secchio, abbiamo bisogno di una struct node * prossimo. OK. Quindi questo è quello che un nodo assomiglia. 

Ora qui è la dichiarazione della nostra tabella hash. E 'intenzione di avere 16.834 secchi. Ma questo numero non importa. E, infine, stiamo andando ad avere la Dimensioni tabella hash variabile globale, che sta per iniziare a zero. E sta andando a tenere traccia di come molte parole sono nel nostro dizionario. 

Quindi diamo un'occhiata a carico. Si noti che il carico, esso restituisce un bool. Si ritorna true se fosse successo caricato, false in caso contrario. E ci vuole un dizionario * const char, che è il dizionario che vogliamo aprire. Ecco, questo è la prima cosa stiamo andando a fare. 

Stiamo andando a fopen l' Dizionario per la lettura. E stiamo andando ad avere per fare Assicurarsi che è riuscito. Quindi, se restituito NULL, allora non abbiamo aprire correttamente il dizionario. E dobbiamo restituire false. Ma supponendo che lo ha fatto con successo aperto, quindi vogliamo leggere l' dizionario. In modo da mantenere il ciclo finché non troviamo un po ' motivo per uscire da questo ciclo, che vedremo. Così mantenere looping. 

E ora stiamo andando a malloc un singolo nodo. E naturalmente abbiamo bisogno all'aria prova di nuovo. Quindi, se mallocing non è riuscito, quindi vogliamo scaricare qualsiasi nodo che è successo a malloc prima, chiudere il Dizionario e restituire false. Ma ignorare che, assumendo che riuscito, allora vogliamo usare fscanf leggere una sola parola dei Dizionario nel nostro nodo. Quindi ricorda che l'ingresso> parola è il carattere tampone parola di dimensioni lenghth + 1 che stiamo andando a memorizzare la parola dentro 

Così fscanf sta per restituire 1, purché come è stato in grado di successo leggere una parola dal file. Se succede sia un errore, o noi raggiungere la fine del file, non tornerà 1. Nel qual caso non ritorna 1, stiamo finalmente per uscire questo ciclo while. Così vediamo che quando abbiamo successo leggere una parola in iscrizione> parola, poi andremo a che parola utilizzando la nostra funzione di hash. 

Diamo uno sguardo a la funzione hash. Quindi non si ha realmente bisogno per capire questo. E in realtà abbiamo appena tirato questo hash funzionare da internet. L'unica cosa che dovete riconoscere è che questo richiede un const char * word. Così sta prendendo una stringa come input, e restituire un int unsigned come output. Ecco, questo è tutto una funzione di hash è, è prende in input e ti dà una indice nella tabella hash. 

Notate che stiamo moding da NUM_BUCKETS, in modo che il valore restituito in realtà è un indice nella tabella hash e non indicizza oltre il limiti della matrice. Quindi, dato che la funzione, stiamo andando hash la parola che leggiamo l' dizionario. E poi andremo a utilizzare che hash per inserire la entrata nella tabella hash. 

Hash Ora hashtable è la corrente elenco collegato nella tabella. Ed è molto probabile che è solo NULL. Vogliamo inserire il nostro ingresso alla all'inizio di questa lista collegata. E così stiamo per avere la nostra attuale punto di ingresso a quello che il hashtable Attualmente punti a. E poi andremo a memorizzare, nella tabella hash alla hash, la voce corrente. Così queste due righe inserire con successo la voce all'inizio del lista collegata a tale indice nella tabella hash. 

Una volta che abbiamo finito con quello, sappiamo che abbiamo trovato un'altra parola nella dizionario, e incrementiamo di nuovo. Così continuiamo a farlo fino fscanf finalmente tornato qualcosa di non-1 a questo punto ricordare che abbiamo bisogno di liberare voce. Quindi qui abbiamo malloced una voce. E abbiamo cercato di leggere qualcosa dal dizionario. E non abbiamo letto con successo qualcosa dal dizionario, in qual caso occorre liberare la voce che non abbiamo mai messo in Hashtable, e infine rompere. 

Una volta che usciamo abbiamo bisogno di vedere, bene, fatto usciamo perché non stava leggendo un errore dal file? Oppure abbiamo rompere fuori perché abbiamo raggiunto la fine del file? Se c'è stato un errore, quindi vogliamo tornare false. Dato che il carico non è riuscito. E nel processo vogliamo scaricare tutte le parole che leggiamo in, e chiudere il file dizionario. 

Supponendo che ci siamo riusciti, poi abbiamo appena ancora bisogno di chiudere il dizionario File e infine ritorno vero dal momento che caricata correttamente il dizionario. E questo è tutto per il carico. Così ora controllare, dato un hashtable caricata, sta andando a guardare come questo. Quindi controllare, restituisce un bool, che è andando per indicare se il passato in char * parola, se il passato nella stringa è nel nostro dizionario. Quindi, se è nel dizionario, se è nella nostra tabella hash, ci torneremo vero. E se non lo è, ci torneremo false. 

Dato questo passò in parola, siamo andando hash parola. Ora, una cosa importante da riconoscere è che in carico sapevamo che tutte le parole che andremo ad essere minuscolo. Ma qui non siamo così sicuri. Se diamo uno sguardo alla nostra funzione di hash, la nostra funzione di hash realtà è inferiore dell'involucro ogni carattere della parola. Quindi, indipendentemente dalla capitalizzazione di parola, la nostra funzione hash è il ritorno lo stesso indice per qualunque capitalizzazione è, come avrebbe restituito per completamente minuscolo versione della parola. Va bene. Questo è il nostro indice è verso la Hashtable per questa parola. 

Ora questo ciclo for sta per scorrere l'elenco collegato che era a tale indice. Così notiamo che stiamo inizializzazione di iscrizione per puntare a tale indice. Abbiamo intenzione di continuare mentre la voce! = NULL. E ricorda che l'aggiornamento del puntatore nella nostra lista iscrizione collegata = entry> prossimo. Così abbiamo il nostro punto di ingresso attuale l'elemento successivo nella lista collegata. 

Quindi, per ogni voce nella lista collegata, stiamo andando a utilizzare strcasecmp. Non è StrComp. Perché, ancora una volta, vogliamo fare caso le cose insensitively. Quindi usiamo strcasecmp confrontare la parola che è stato passato attraverso questo funzione contro la parola cioè in questa voce. Se si restituisce zero, significa che non vi era una partita, in questo caso vogliamo return true. Abbiamo trovato con successo la parola nella nostra tabella hash. 

Se non ci fosse una partita, quindi siamo andando in loop di nuovo e guardare il voce successiva. E noi continueremo looping mentre ci sono voci in questa lista collegata. Cosa succede se rompiamo fuori di questo ciclo for? Questo significa che non abbiamo trovato una voce che abbinato questa parola, nel qual caso torniamo false per indicare che il nostro hashtable non conteneva questa parola. E questo è un assegno. 

Quindi diamo un'occhiata a dimensioni. Ora dimensioni sta per essere piuttosto semplice. Da ricordare in carico, per ogni parola abbiamo trovato, abbiamo incrementato globale Dimensioni tabella hash variabile. Quindi la funzione di dimensione è solo andare per tornare variabile globale. E questo è tutto. 

Ora finalmente, abbiamo bisogno di scaricare la dizionario una volta che tutto è fatto. Quindi, come facciamo a fare questo? Proprio qui stiamo eseguendo un ciclo su tutti i secchi della nostra tavola. Quindi ci sono NUM_BUCKETS secchi. E per ogni lista collegata nel nostro hashtable, stiamo andando a ciclo su l'interezza della lista collegata, liberando ogni elemento. 

Ora dobbiamo stare attenti. Quindi qui abbiamo una variabile temporanea che è memorizzare il puntatore al successivo elemento della lista concatenata. E poi stiamo andando alla libera l'elemento corrente. Dobbiamo essere sicuri che facciamo da quando abbiamo non si può semplicemente liberare l'elemento corrente e quindi provare ad accedere il puntatore prossimo, dal momento che una volta che abbiamo liberato esso, la memoria non è più valido. 

Quindi abbiamo bisogno di mantenere attorno a un puntatore a l'elemento successivo, allora possiamo liberare il elemento corrente, e quindi possiamo aggiornare il nostro elemento corrente per puntare a l'elemento successivo. Ti ciclo while ci sono elementi in questa lista collegata. Lo faremo per tutte legate liste nella tabella hash. E una volta che avremo finito con quello, abbiamo completamente scaricato la tabella hash, e abbiamo finito. Quindi è impossibile per lo scaricamento per ritornare sempre false. E quando abbiamo finito, abbiamo solo return true. 

Diamo questa soluzione una prova. Quindi diamo un'occhiata a ciò che il nostro struct nodo sarà simile. Qui vediamo che stiamo andando ad avere un bool parola e un nodo struct * bambini Staffa ALFABETO. Quindi la prima cosa che si potrebbe essere chiedendo, perché è ALFABETO Ed definito come 27? Beh, ricordiamo che stiamo andando ad avere bisogno da gestire l'apostrofo. In modo che sara 'un po' un caso speciale nel corso di questo programma. 

Ora, ricordare come un trie effettivamente funziona. Diciamo che stiamo indicizzando la parola "gatti". Poi dalla radice del trie, stiamo andando a guardare i bambini array, e stiamo andando a guardare il indice che corrisponde alla lettera C. So che sarà indicizzato 2. Quindi, dato che, quella volontà ci danno un nuovo nodo. E poi ci lavoriamo da quel nodo. 

Quindi, dato che il nodo, siamo ancora una volta andando a guardare la matrice 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 di guardare alla fine si tratta di un corrisponde a T. E passare a quel nodo, Infine, abbiamo completamente guardato attraverso la nostra parola "cat". E ora bool parola dovrebbe indicare se Questa parola data è in realtà una parola. 

Allora, perché abbiamo bisogno che il caso speciale? Beh, cosa della parola "catastrofe" è nel nostro dizionario, ma l' la parola "cat" non è? Quindi, e cercando di vedere se la parola "cat" è nel nostro dizionario, siamo andando a guardare con successo attraverso gli indici C-A-T nel nodo regione. Ma è solo perché la catastrofe successo per creare nodi sulla strada da C-A-T, fino a la fine della parola. Così bool parola è usata per indicare se questa particolare posizione in realtà indica una parola. 

Bene. Quindi, ora che sappiamo che cosa è trie andando a guardare come, diamo un'occhiata al funzione di caricare. Quindi il carico sta per restituire un bool per se abbiamo successo o invano caricato il dizionario. E questo sta andando essere il dizionario che vogliamo caricare. 

Quindi prima cosa siamo a fare è aprire a quel dizionario per la lettura. E dobbiamo fare in modo noi non falliremo. Quindi, se il dizionario non era aperto con successo, verrà restituito null, nel qual caso siamo andando a restituire 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 un nodo *. E 'la parte superiore della nostra trie che siamo sta per essere scorrendo. Quindi la prima cosa che stiamo andando 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 assicurarsi che sono tutti nulli. Così calloc lo farà per noi. 

Ora, proprio come malloc, abbiamo bisogno di fare Assicurarsi che la ripartizione era in realtà successo. Se questo restituito un valore nullo, allora necessità di chiudere o dizionario file e restituire false. Quindi, supponendo che l'assegnazione è stata successo, stiamo andando a utilizzare un nodo * cursore per scorrere il nostro trie. Quindi, le nostre radici non cambierà mai, ma abbiamo intenzione di usare cursore effettivamente andare da nodo a nodo. 

Quindi, in questo ciclo for stiamo leggendo attraverso il file dizionario. E stiamo usando fgetc. Fgetc sta per afferrare un unico carattere dal file. Abbiamo intenzione di continuare a catturare personaggi mentre noi non raggiungiamo l' fine del file. 

Ci sono due casi che dobbiamo gestire. La prima, se il carattere non era una nuova linea. Così sappiamo se si trattasse di una nuova linea, quindi 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. 

Quindi, come ho detto prima, abbiamo bisogno di caso particolare l'apostrofo. Notate che stiamo usando il ternario operatore qui. Quindi stiamo andando a leggere questo come, se il personaggio si legge in è stato un apostrofo, poi andremo a impostare index = "ALFABETO" -1, che sarà essere l'indice 26. 

Altrimenti, se non fosse un apostrofo, ci stiamo andando a impostare l'indice uguale a c - a. Quindi ricordatevi di ritorno da precedentemente p-set, c - una sta per darci l' posizione alfabetica di C. Quindi, se C è la lettera A, questo sarà darci indice zero. Per la lettera B, darà noi l'indice 1, e così via. 

Quindi questo ci dà l'indice nella bambini matrice che vogliamo. Ora, se questo indice è attualmente nullo in i bambini, che significa che un nodo attualmente non esiste da tale percorso. Quindi abbiamo bisogno di allocare un nodo per quel percorso. Questo è quello che faremo qui. 

Così stiamo andando usare di nuovo la calloc funzione, in modo che non c'è bisogno di azzerare tutti i puntatori. E abbiamo ancora bisogno di controllare che calloc non ha fallito. 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 era nulla 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 allocare la parola "cat". E questo significa che quando andiamo a destinare "Catastrofe" non abbiamo bisogno di creare nodi per C-A-T di nuovo. Essi esistono già. 

Che cosa è questa cosa? 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 ci completato con successo una parola? Stiamo andando a utilizzare questo campo parola interno del nostro nodo struct. Vogliamo impostare tale true. In modo che indica che questo nodo indica un successo parola, 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, dal momento che abbiamo trovato un altro lavoro. Quindi stiamo andando a continuare a farlo, lettura carattere per carattere, la costruzione di nuovi nodi nel nostro trie e Per ogni parola del dizionario, fino finalmente raggiungiamo C! = EOF, in cui caso usciamo del file. 

Ora ci sono due casi in che avremmo potuto colpire EOF. La prima è se c'è stato un errore la lettura dal file. Quindi se ci fosse un errore, bisogno di fare tipico. Scaricare tutto, close il file, return 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 quando abbiamo Dizionario caricato correttamente nel nostro trie. 

Così ora diamo un'occhiata assegno. Guardando la funzione di controllo, vediamo tale verifica sta per restituire un bool. Restituisce true se questa parola che è essere passato è nella nostra trie. Esso restituisce false in caso contrario. Allora, come è possibile determinare 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 passati, stiamo andando a determinare il indice nella matrice bambini che corrisponde alla staffa parola I. Quindi questo sta andando a guardare esattamente come carico, dove se la parola [i] è un apostrofo, allora vogliamo utilizzare l'indice "alfabeto" - 1. Poiché abbiamo determinato che tale è dove stiamo andando a memorizzare apostrofi. 

Altrimenti andremo ad usare due parole più basso Staffa I. Quindi ricorda che la parola può hanno capitalizzazione arbitraria. E quindi vogliamo essere sicuri che siamo utilizzando una versione minuscola delle cose. E poi sottrarre da quella 'a' per volta ancora una volta ci danno la alfabetico posizione di quel personaggio. Quindi, che sta per essere il nostro indice nell'array bambini. 

E ora se questo 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. Poiché se così fosse, che sarebbe significa che ci sarebbe un percorso fino a quella parola. E si sarebbe mai incontrare null. Così incontrando null, torniamo false. La parola non è nel dizionario. Se non fosse nullo, quindi siamo intenzione di continuare l'iterazione. 

Così stiamo andando là fuori cursore per puntare a quel particolare nodo a tale indice. Noi continuiamo a fare che per tutto l'intera parola, assumendo non abbiamo mai colpito nulla. Questo significa che siamo stati in grado di ottenere attraverso l'intera parola e trovare un nodo nel nostro tentativo. Ma non siamo ancora del tutto finito. 

Noi non vogliamo tornare solo true. Vogliamo tornare il cursore> parola. Da ricordare ancora una volta, è "cat" non è nel nostro dizionario, e "catastrofe" è, allora avremo successo otteniamo attraverso la parola "cat". Ma cursore parola sarà falso e non vero. Quindi torniamo cursore parola per indicare se questo nodo è in realtà una parola. E questo è tutto per il controllo. 

Quindi diamo un'occhiata dimensioni. Così dimensioni sta per essere abbastanza facile poiché, ricordate in carico, siamo incrementando le dimensioni del dizionario per ogni parola che incontriamo. Così dimensione è solo andare a ritorno dimensione del dizionario. E questo è tutto. 

Così, infine, abbiamo scaricato. Così scarico, stiamo andando a utilizzare un funzione ricorsiva per fare realtà tutti del lavoro per noi. Quindi la nostra funzione sta per essere invitato 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 nodo figlio non è null, allora stiamo andando a scaricare il nodo figlio. 

Quindi questo è il modo ricorsivo scaricatela 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 scarico noi stessi. Questo funzionerà in modo ricorsivo scaricare l'intero trie. E poi, una volta fatto, possiamo semplicemente restituire true. Unload non può fallire. Stiamo 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 correttore ortografico. 

[GIOCO MUSICA]