>> KEVIN SCHMID: A volte, quando si costruisce una programma, si potrebbe desiderare di utilizzare un
struttura di dati nota come un dizionario.
A mappe Dizionario chiavi, che sono di solito stringhe, ai valori, int,
caratteri, un puntatore ad un oggetto, quello che vogliamo.
E 'proprio come dizionari ordinarie che sugli parole attraverso definizioni.
>> Dizionari ci forniscono l' capacità di immagazzinare informazioni
associato a qualcosa e guardare più tardi.
Quindi, come possiamo realmente attuare una dizionario, per esempio, il codice C che possiamo
utilizzare in uno dei nostri programmi?
Ebbene, ci sono molti modi in cui potremmo implementare un dizionario.
>> Per uno, potremmo utilizzare un array che dinamicamente ridimensionare o potremmo usare un
lista collegata, tabella hash o un albero binario.
Ma qualsiasi cosa scegliamo, dobbiamo essere consapevoli della efficienza e
prestazioni dell'implementazione.
Dovremmo pensare l'algoritmo usato di inserire e ricercare elementi in
la nostra struttura dati.
>> Per ora, supponiamo che ci voler usare le stringhe come chiavi.
Parliamo di una possibilità, una struttura di dati chiamata trie.
Quindi, ecco una rappresentazione visiva di un trie.
>> Come l'immagine suggerisce, un trie è una struttura di dati ad albero con
nodi collegati tra loro.
Vediamo che c'è chiaramente una radice nodo con alcuni link che estende alla
altri nodi.
Ma cosa significa ogni nodo consiste?
Se assumiamo che stiamo memorizzazione delle chiavi con soli caratteri alfabetici e
non ci preoccupiamo di capitalizzazione, ecco una definizione di un nodo che
sarà sufficiente.
>> Un oggetto il cui tipo è struct nodo ha due parti
chiamata dati e bambini.
Abbiamo lasciato la parte di dati come un commento per essere sostituito da un componente
dichiarazione quando il nodo è struct incorporata in un programma C.
La parte di dati di un nodo può essere un Valore booleano per indicare se
non il nodo rappresenta il completamento di una chiave di dizionario o potrebbe essere un
stringa che rappresenta la definizione di una parola nel dizionario.
>> Useremo una faccina sorridente per indicare quando è presente in un nodo di dati.
Ci sono 26 elementi nella nostra matrice bambini, un indice
per carattere alfabetico.
Vedremo il significato di questo presto.
>> Prendiamo uno sguardo più da vicino del nodo radice nel nostro schema, che non ha dati
ad esso associati, come indicato dal assenza della faccina sorridente nel
porzione di dati.
Le frecce che si estendono dalle parti di la matrice bambini rappresentano non-node
puntatori ad altri nodi.
Ad esempio, la freccia estende dal il secondo elemento di bambini
rappresenta la lettera B in una chiave di dizionario.
E nello schema più grande etichettiamo con una B.
>> Si noti che nello schema più grande, quando abbiamo disegnare un puntatore ad un altro nodo, esso
Non importa se la punta della freccia risponda a tale nodo.
Il nostro trie Dizionario campione contiene due parole, che e zoom.
Camminiamo attraverso un esempio di cerca i dati per una chiave.
>> Supponiamo di voler cercare l' valore corrispondente per il bagno chiave.
Inizieremo il nostro sguardo su al nodo radice.
Poi ci prenderemo la prima lettera del nostro chiave, B, e trovare il corrispondente
posto nella nostra matrice bambini.
Si noti che ci sono esattamente 26 punti nella matrice, una per ogni lettera
l'alfabeto.
E avremo i punti rappresentano il lettere dell'alfabeto in ordine.
>> Vedremo il secondo indice, allora, indice uno, per B. In generale, se
avere qualche alfabetico carattere C che potrebbe determinare il punto corrispondente
nella matrice dei minori che usano un calcolo come questo.
Abbiamo potuto utilizzare per bambini più grandi array se abbiamo voluto offrire sguardo di
tasti con una vasta gamma di personaggi, ad esempio l'intera
Set di caratteri ASCII.
>> In questo caso, il puntatore nei nostri bambini array
indice non è nullo.
Quindi noi continueremo cercando la vasca chiave.
Se mai incontrato un puntatore nullo nel punto corretto nei bambini
matrice mentre abbiamo attraversato i nodi, allora dovremo dire che abbiamo
non riusciva a trovare nulla per quella chiave.
>> Ora, prendiamo la seconda lettera di la nostra chiave, A, e continuare a seguire
puntatori in questo modo fino a noi raggiungere la fine della nostra chiave.
Se arriviamo alla fine della chiave senza colpire gli vicoli ciechi, puntatori nulli,
come è il caso qui, allora abbiamo solo deve controllare una cosa.
È questo tasto realtà nel dizionario?
>> Se è così, dovremmo trovare un valore, un bene smiley Icona volto nel nostro diagramma in cui
la parola finisce.
Se c'è qualcos'altro memorizzato con i dati, quindi siamo in grado di restituirlo.
Ad esempio, lo zoo chiave non è nella dizionario, anche se potremmo avere
raggiunto la fine di questa chiave senza mai colpire un puntatore nullo, mentre noi
scorrere l'trie.
>> Se abbiamo provato a cercare il bagno tasto, il secondo per indice di matrice di ultimo nodo,
corrispondente alla lettera H, sarebbe hanno tenuto un puntatore nullo.
Quindi il bagno non è presente nel dizionario.
E così un trie è unico in quanto le chiavi vengono mai esplicitamente memorizzati in
la struttura di dati.
Quindi, come possiamo inseriamo qualcosa in un trie?
>> Inseriamo la chiave zoo nel nostro trie.
Ricordate che una faccina sorridente in un nodo potrebbe corrispondere in codice per un semplice
Valore booleano per indicare che zoo è nel dizionario o potrebbe
corrispondono a maggiori informazioni che abbiamo desidera associare con lo zoo chiave,
come la definizione del parola o qualcos'altro.
In qualche modo, il processo per inserire qualcosa in un trie è simile a
guardando qualcosa in un trie.
>> Inizieremo con il nodo principale di nuovo, seguenti indicazioni corrispondenti a
le lettere della nostra chiave.
Per fortuna, siamo riusciti a seguire i puntatori tutta la strada fino a quando abbiamo raggiunto
la fine della chiave.
Poiché zoo è un prefisso della parola zoom, che è membro del
dizionario, non abbiamo bisogno di destinare eventuali nuovi nodi.
>> Possiamo modificare il nodo per indicare che il percorso di protagonisti a
rappresenta una chiave nel nostro dizionario.
Ora, proviamo inserendo il BAGNO chiave nel trie.
Inizieremo al nodo radice e seguire di nuovo i puntatori.
Ma in questa situazione, ci ha colpito un morto terminare prima che siamo in grado di ottenere il
fine della chiave.
Ora, abbiamo bisogno di allocare una nuova nodi dovranno allocare una nuova
nodo per ogni restante lettera della nostra chiave.
>> In questo caso, dobbiamo solo attribuire un nuovo nodo.
Poi abbiamo bisogno di rendere l'indice H riferimento a questo nuovo nodo.
Ancora una volta, possiamo modificare il nodo indicare che il percorso di caratteri
conduce ad esso rappresenta un chiave nel nostro dizionario.
Facciamo ragionare sulla asintotico complessità delle nostre procedure per tali
due operazioni.
>> Notiamo che in entrambi i casi il numero di passaggi nostro algoritmo ha preso è stato
proporzionale al numero di lettere della parola chiave.
Che è di destra.
Se si vuole cercare una parola in un trie basta scorrere
le lettere una ad una finché non si raggiungere la fine della parola o
colpito un vicolo cieco nel trie.
>> E quando si desidera inserire una chiave coppia di valori in un trie usando l'
procedura abbiamo discusso, il caso peggiore vi farà assegnazione di un nuovo nodo
per ogni lettera.
E noi assumiamo che l'assegnazione è un'operazione a tempo costante.
Quindi, se si assume che la lunghezza della chiave è delimitata da una costante fissa, sia
inserimento e guardare in alto sono costanti operazioni di tempo per un trie.
>> Se non facciamo questo presupposto che la lunghezza della chiave è delimitato da una fissa
costante, quindi dell'inserimento e guardare in alto, nel caso peggiore, sono lineari nella
lunghezza della chiave.
Si noti che il numero di elementi memorizzati nel trie non pregiudica il look up
o il tempo di inserimento.
È influenzato solo dal lunghezza della chiave.
>> Per contro, l'aggiunta di voci, per dire, una tabella hash tende a rendere
futuro sguardo lento.
Anche se questo può sembrare attraente in un primo momento, dovremmo tenere a mente che un
favorevole complessità asintotica non significa che in pratica i dati
struttura è necessariamente irreprensibile.
Dobbiamo anche considerare che per memorizzare un parola in un trie abbiamo bisogno, nella peggiore
caso, un numero di nodi proporzionale alla lunghezza della parola stessa.
>> Tenta tendono ad usare un sacco di spazio.
Questo è in contrasto con una tabella di hash, dove abbiamo solo bisogno di un nuovo nodo
memorizzare alcune coppia chiave-valore.
Ora, sempre in teoria, ampio spazio consumo non sembra un grande
affrontare, soprattutto considerando che la moderna computer hanno gigabyte e
gigabyte di memoria.
Ma si scopre che abbiamo ancora preoccuparsi di utilizzo della memoria e
organizzazione per il bene della prestazioni, dato che i computer moderni
disporre di meccanismi in atto sotto la Cappa per accelerare l'accesso alla memoria.
>> Ma questi meccanismi funzionano meglio quando accessi alla memoria sono realizzati in versione ridotta
regioni o zone.
E i nodi di un trie potrebbero risiedere ovunque in quel mucchio.
Ma questi sono compromessi che dobbiamo considerare.
>> Ricordate che, quando si sceglie un dato struttura per un certo compito, abbiamo
dovrebbe pensare a quali tipi di operazioni la struttura di dati deve
supporto e qual è il rendimento di ciascuno di tali
operazioni è importante per noi.
Queste operazioni possono anche estendersi oltre la semplice
aspetto di base e di inserimento.
Supponiamo di voler realizzare una sorta di funzionalità di completamento automatico, molto
come motore di ricerca di Google fa.
Cioè, restituire tutte le chiavi e potenzialmente valori che
avere un determinato prefisso.
>> Un trie è unicamente utile per questa operazione.
E 'semplice da scorrere trie per ogni carattere di
il prefisso.
Proprio come un guardare in alto funzionamento, abbiamo potuto seguire i puntatori
carattere per carattere.
Poi, quando si arriva alla fine del prefisso, potremmo scorrere l'
porzione rimanente della struttura dati poiché uno dei tasti di là
questo punto hanno il prefisso.
>> E 'anche facile da ottenere questo annuncio in ordine alfabetico poiché l'
elementi della matrice bambini sono elencate in ordine alfabetico.
Così si spera che prenderemo in considerazione dando prova una prova.
Sono Kevin Schmid, e questo è CS50.
>> Ah, questo è l'inizio del declino.
Mi dispiace.
Scusi.
>> Sciopero di quattro.
Sono fuori.
Scusi.
Ci scusiamo per fare la persona che deve modificare questa impazzire.
>> Scusi.
Scusi.
>> SPEAKER 1: Ben fatto.
Che è stato davvero ben fatto.