DOUG LLOYD: Quindi, in CS50, abbiamo coperto un sacco di strutture di dati diversi, destra? Abbiamo visto gli array, e legati elenchi e tabelle hash, e cerca, pile e code. Impareremo anche un po ' su alberi e mucchi, ma in realtà tutti questi solo fine per essere variazioni sul tema. Ci sono davvero questi tipo di quattro idee di base che tutto il resto può ridursi a. Array, liste concatenate, tabelle hash, e cerca. E come ho detto, ci sono variazioni su di loro, ma questo è abbastanza tanto andare a riassumere tutto quello che stiamo andando a parlare circa in questa classe, in termini di C. Ma come fanno questi ogni misura, giusto? Abbiamo parlato i pro ei contro di ciascuno in video separati su di loro, ma c'è un sacco di numeri ottenere gettato intorno. C'è un sacco di generale pensieri sempre gettati in giro. Cerchiamo di consolidare in un solo posto. Facciamo pesare i pro contro i contro, e prendere in considerazione quale struttura dati potrebbe essere il giusto dati Struttura per la vostra situazione particolare, qualunque tipo di dati si sta memorizzazione. Non è necessariamente sempre bisogno di utilizzare l'inserimento super veloce, la cancellazione, e ricerca di un trie se davvero non si preoccupano di inserimento e cancellazione troppo. Se avete bisogno di appena rapidamente casuale accesso, forse un array è meglio. Quindi cerchiamo di distillare tale. Parliamo di ciascuno dei quattro principali tipi di strutture di dati che abbiamo parlato, e basta vedere quando potrebbe essere buono, e quando potrebbero non essere così buono. Quindi partiamo con gli array. Così l'inserimento, che una specie di male. 

Inserimento alla fine di un array è OK, se stiamo costruendo una matrice come andiamo. Ma se abbiamo bisogno di inserire elementi nel mezzo, ripensare a inserimento tipo, c'è un sacco di spostare a montare un elemento in là. E così, se abbiamo intenzione di inserire ovunque ma la fine di una matrice, che probabilmente non è così grande. 

Allo stesso modo, la cancellazione, a meno che non siamo eliminazione dalla fine di una matrice, è probabilmente non è così grande, se non vogliamo lasciare fessure vuote, che di solito non lo facciamo. Vogliamo rimuovere un elemento, e poi sorta di renderlo aderente di nuovo. E così l'eliminazione di elementi da un array, anche non così grande. 

Consultazione, tuttavia, è grande. Abbiamo accesso casuale, ricerca costante di tempo. Diciamo solo sette, e andiamo a matrice di delocalizzazione sette. Diciamo 20, all'appuntamento per array di trasferimento 20. Non abbiamo per scorrere attraverso. Questo è abbastanza buono. 

Gli array sono anche relativamente facile da ordinare. Ogni volta che abbiamo parlato di un ordinamento algoritmo, come la selezione tipo, insertion sort, bubble sort, merge specie, abbiamo sempre usato le matrici di farlo, perché gli array sono abbastanza facili da tipo, rispetto alle strutture di dati che abbiamo visto finora. 

Sono anche relativamente piccolo. Non c'è un sacco di spazio in più. Devi solo mettere da parte esattamente quanto come è necessario per tenere i vostri dati, e che è praticamente. Quindi sono piuttosto piccole ed efficiente in questo modo. Ma un altro aspetto negativo, però, è che essi hanno una dimensione fissa. Dobbiamo dichiarare esattamente come grande vogliamo la nostra gamma di essere, e abbiamo solo un colpo a questo. Non possiamo crescere e ridurla. 

Se abbiamo bisogno di crescere o restringersi, noi hanno bisogno di dichiarare un nuovo array, copiare tutti gli elementi del primo array nella seconda matrice. E se noi calcolato male che tempo, abbiamo bisogno di farlo di nuovo. Non così grande. Quindi gli array non ci danno la flessibilità di avere un numero variabile di elementi. 

Con una lista collegata, inserimento è abbastanza facile. Siamo appiccicare semplicemente le anteriore. La cancellazione è anche abbastanza facile. Dobbiamo trovare gli elementi. Che coinvolgono qualche ricerca. 

Ma una volta che hai trovato l'elemento che stai cercando, tutto quello che dovete fare è cambiare un puntatore, forse due se avete un legato list-- un doppiamente lista collegata, rather-- e allora si può solo liberare il nodo. Non è necessario spostare tutto intorno. Basta cambiare due puntatori, così che è piuttosto veloce. 

Ricerca è male però, no? Al fine per noi trovare un elemento in una lista collegata, se singolarmente o doppiamente collegata, dobbiamo lineare cercarlo. Dobbiamo cominciare all'inizio e spostare l'estremità, o iniziare alla fine mossa all'inizio. Noi non abbiamo più accesso casuale. Quindi, se stiamo facendo un sacco di ricerca, forse una lista collegata non è abbastanza così buono per noi. 

Sono anche molto difficile da risolvere, giusto? L'unico modo è possibile davvero ordinare una lista concatenata è quello di ordinare come si costruisce esso. Ma se si ordina come si costruirlo, non sei più rendendo più inserimenti rapidi. Tu non sei solo virata le cose sulla parte anteriore. Devi trovare il posto giusto per metterlo, e poi la vostra inserzione diventa quasi come cattivo come l'inserimento in una matrice. Quindi liste concatenate non sono così grande per ordinare i dati. 

Sono anche piuttosto piccolo, formato-saggio. Doppiamente concatenata po 'elenco più grande di liste concatenate semplici, che sono leggermente più grandi di array, ma non è una grande quantità di spazio sprecato. Quindi, se lo spazio è ad un premio, ma Non un premio davvero intenso, questa potrebbe essere la strada giusta da percorrere. 

Tabelle hash. Inserimento in una tabella hash è abbastanza semplice. Si tratta di un processo in due fasi. In primo luogo abbiamo bisogno di eseguire i nostri dati attraverso una funzione di hash per ottenere un codice hash, e poi inseriamo l'elemento nella tabella hash in quella posizione codice hash. 

La cancellazione, simile alla lista collegata, è facile una volta trovato l'elemento. Devi trovare per primo, ma poi quando lo si elimina, basta scambiare una coppia di puntatori, se si sta utilizzando concatenazioni separate. Se stai usando sondare, o se non siete utilizzando concatenamento a tutti nella tabella di hash, l'eliminazione è in realtà molto semplice. Tutto quello che dovete fare è il hash i dati, e poi andare a quella posizione. E a patto che non lo fai avere collisioni, sarete in grado di eliminare rapidamente. 

Ora, di ricerca è dove le cose ottenere un po 'più complicato. E 'in media meglio di liste concatenate. Se stai usando concatenazioni, avete ancora una lista collegata, il che significa che avete ancora la Ricerca detrimento una lista collegata. Ma perché si sta prendendo la tua collegati lista e dividendolo oltre 100 o 1000 o n elementi nella vostra tabella di hash, sei liste collegate sono tutte ennesimo le dimensioni. Sono tutti sostanzialmente più piccolo. Hai n collegato liste invece di una lista collegata di dimensione n. 

E così questo mondo reale costante fattore, che generalmente non si parla di complessità tempo, realtà non fare la differenza qui. Quindi ricerca è ancora lineare cercare se si sta usando concatenazioni, ma la lunghezza della lista si sta cercando attraverso è molto, molto breve in confronto. Anche in questo caso, se l'ordinamento è il vostro obiettivo qui, hash tabella di probabilmente non è il modo giusto per andare. Basta usare un array se l'ordinamento è veramente importante per voi. 

E possono eseguire la gamma di dimensioni. E 'difficile dire se un tabella hash è piccolo o grande, perché in realtà dipende quanto è grande la vostra tabella di hash è. Se avete intenzione solo di essere l'archiviazione cinque elementi nella vostra tabella hash, e si dispone di una tabella di hash con 10.000 elementi in esso, probabilmente stai sprecando un sacco di spazio. Contrasto si possono anche essere avere tabelle hash molto compatte, ma il più piccolo la tua tabella hash ottiene, il più lungo ciascuna di tali liste collegate prende. E così non c'è davvero nessun modo per definire esattamente la dimensione di una tabella hash, ma è probabilmente sicuro dire che è generalmente sta per essere più grande di un collegato Lista memorizzare gli stessi dati, ma più piccolo di un trie. 

E tentativi sono la quarta di queste strutture che stiamo parlando. Inserimento in un trie è complessa. C'è un sacco di dinamica allocazione della memoria, soprattutto all'inizio, come si sta iniziando a costruire. Ma è tempo costante. E 'solo l'elemento umano qui che lo rende difficile. Dover incontrare puntatore nullo, malloc spazio, andare lì, lo spazio forse malloc da lì di nuovo. Il tipo di fattore di intimidazione di puntatori in allocazione dinamica della memoria è l'ostacolo per cancellare. Ma una volta che hai eliminato esso, l'inserimento in realtà arriva abbastanza semplice, e certamente è un tempo costante. 

La cancellazione è facile. Tutto quello che dovete fare è navigare lungo una paio di puntatori e la connessione al nodo, così che è abbastanza buono. Lookup è anche abbastanza veloce. Si basa unicamente sulla lunghezza dei vostri dati. Quindi, se tutti i dati sono cinque stringhe di caratteri, per esempio, si sta memorizzare cinque stringhe di caratteri nel trie, ci vogliono solo cinque passi per trovare quello che stai cercando. Cinque è solo un fattore costante, così ancora una volta, l'inserimento, la cancellazione, e ricerca qui ci sono tutti i tempi costanti, in modo efficace. 

Un'altra cosa è che il vostro è trie in realtà tipo di già ordinato, giusto? In virtù di quanto siamo inserire elementi, andando lettera per lettera del chiave, o cifra per cifra della chiave, In genere, il trie finisce per essere tipo di ordinati come si costruisce. Non fa davvero senso di pensare di smistamento nello stesso modo in cui pensiamo con gli array, o liste collegate, o tabelle hash. Ma in un certo senso, il vostro trie è ordinato, come si va. 

Il rovescio della medaglia, naturalmente, è che un trie diventa rapidamente enorme. Da ogni punto di congiunzione, si potrebbe have-- se la tua chiave è costituito da cifre, avete altri 10 luoghi che si può andare, che significa che ogni nodo contiene informazioni sui dati che si desidera memorizzare a quel nodo, più 10 puntatori. Il che, in CS50 IDE, è di 80 byte. Quindi è di almeno 80 byte per ogni nodo che si crea, e che non è nemmeno contare i dati. E se i nodi sono lettere invece di cifre, ora avete 26 puntatori da ogni posizione. E 26 volte 8 è probabilmente 200 byte, o qualcosa del genere. E tu hai capitale e si può lowercase-- vedere dove sto andando con questo, giusto? I nodi possono ottenere davvero grande, e così il trie stesso, nel complesso, può ottenere veramente grande, troppo. Quindi, se lo spazio è molto elevata premio sul proprio sistema, un trie potrebbe non essere il modo giusto per andare, anche se i suoi altri benefici entrare in gioco. Sono Doug Lloyd. Questo è CS50.