>> SPEAKER 1: Va bene, quindi siamo indietro.
Benvenuti a CS50.
Questa è la fine della settimana di sette.
Quindi ricorda che l'ultima volta, abbiamo iniziato guardando un po 'più sofisticato
strutture di dati.
Poiché fino ad ora, tutti abbiamo avuto davvero a nostra disposizione era questo, un array.
>> Ma prima di scartare l'array come non affatto interessante, che anzi
in realtà, quali sono alcuni dei vantaggi di questo semplice dei dati
struttura così lontano?
Che è bravo?
Per quanto abbiamo visto?
Che cos'hai?
Niente.
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Che cos'è?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Dimensione fissa.
OK, quindi perché è dimensione fissa bene però?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: OK, quindi è efficace in nel senso che è possibile allocare un
quantità fissa di spazio, che si spera è precisamente tanto
lo spazio che vuoi.
In modo che possa essere assolutamente un plus.
>> Qual è un altro lato di un array?
Sì?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Tutto il - scusate?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Tutte le caselle nella memoria o accanto all'altro.
Ed è utile - perché?
Questo è abbastanza vero.
Ma come possiamo sfruttare questa verità?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Esatto, siamo in grado di tenere traccia di dove tutto è solo conoscendo
un indirizzo, cioè l'indirizzo del primo byte di quel pezzo di memoria.
O, nel caso della stringa, l'indirizzo del primo
char in quella stringa.
E da lì, possiamo trovare la fine della stringa.
Possiamo trovare il secondo elemento, l' terzo elemento, e così via.
>> E così il modo elegante per descrivere che caratteristica è che gli array ci danno
accesso casuale.
Semplicemente utilizzando la parentesi quadra notazione e un numero, è possibile passare alla
uno specifico elemento dell'array in tempo costante, grande O
di una, per così dire.
>> Ma ci sono stati alcuni aspetti negativi.
Ciò che un array non fare molto facilmente?
Che non bravo?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Che cos'è?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: espansione in formato.
Così i lati negativi della matrice sono esattamente il contrario di ciò che il
sono aspetti positivi.
Così uno dei lati negativi è che si tratta di una dimensione fissa.
Così non si può davvero crescere.
È possibile riassegnare un pezzo più grande di memoria, e quindi spostare i vecchi elementi
nel nuovo array.
E poi libera la vecchia matrice, per esempio, usando malloc o un analogo
funzione chiamata realloc, che riallocazione di memoria.
>> Realloc, per inciso, cerca di dare memoria che è prossima alla matrice
che hai già.
Ma potrebbe spostare le cose intorno tutto.
Ma insomma, che è costoso, giusto?
Perché se si dispone di un pezzo di memoria di queste dimensioni, ma si vuole veramente uno
di queste dimensioni, e si desidera conservare gli elementi originali, avete
circa un processo di copia tempo lineare che deve avvenire da
vecchia matrice nuova.
E la realtà sta chiedendo il funzionamento ripetutamente sistema e
ancora per grandi blocchi di memoria possono iniziare a costare un po 'di tempo pure.
Quindi è sia una benedizione e una maledizione in mascherare, il fatto che questi array
sono di dimensione fissa.
Ma se introduciamo invece qualcosa come questo, che abbiamo chiamato un linked
lista, si ottiene un paio di aspetti positivi e pochi inconvenienti anche qui.
>> Quindi una lista collegata è semplicemente un dato Struttura composta da strutture del C in questa
caso, in cui una struct, richiamo, è solo di un contenitore per una o più specifiche
tipi di variabili.
In questo caso, ciò che fanno i tipi di dati sembrano essere all'interno della struttura che
ultima volta che abbiamo chiamato un nodo?
Ciascuno di questi rettangoli è un nodo.
E ciascuno dei rettangoli più piccoli all'interno di esso è un tipo di dati.
Quali tipi abbiamo detto erano il Lunedi?
Sì?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Una variabile e di un puntatore, o più specificamente, un int, per n,
e un puntatore in basso.
Sia di quelli capita di essere a 32 bit, a almeno su un computer come questo CS50
Appliance, e quindi sono disegnata in modo uguale in grandezza.
>> Così che cosa sta utilizzando il puntatore anche se a quanto pare per?
Perché aggiungere questo freccia ora, quando le matrici erano così bello e pulito e semplice?
Che cosa sta facendo per il puntatore noi in ciascuno di questi nodi?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Esattamente.
E 'che ti dice dove il prossimo è.
Così ho sorta di usare l'analogia della utilizzando un filo a sorta di
infilare questi nodi insieme.
E questo è esattamente quello che stiamo facendo con puntatori perché ciascuno di essi
blocchi di memoria possono essere o non essere contiguo, back to back to back
all'interno di RAM, perché ogni volta che si chiamare malloc dicendo, dammi abbastanza
byte per un nuovo nodo, potrebbe essere qui o potrebbe essere qui.
Potrebbe essere qui.
È solo che non sai.
>> Ma usando puntatori negli indirizzi di tali nodi, si può cucire loro
insieme in un modo che sembra visivamente come una lista, anche se queste cose sono
tutti sparsi per tutta la una o le due o le quattro gigabyte di RAM
all'interno del proprio computer.
>> Così il rovescio della medaglia, allora, di una lista collegata è che cosa?
Che cosa è un prezzo che siamo apparentemente pagare?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Più spazio, giusto?
Abbiamo, in questo caso, raddoppiato l'importo di spazio, perché siamo andati
da 32 bit per ogni nodo, per ogni int, così ora i 64 bit, perché dobbiamo
mantenere intorno un puntatore pure.
Si ottiene una maggiore efficienza se il struct è più grande di questa cosa semplice.
Se hai in realta 'uno studente all'interno di cui è una coppia di stringhe per
nome e la casa, forse un numero ID, forse alcuni altri campi del tutto.
>> Quindi, se si dispone di una grande struttura abbastanza, poi forse il costo del puntatore è
Non un grande affare.
Questo è un po 'un caso d'angolo in tale stiamo memorizzare una semplice primitiva tale
all'interno della lista collegata.
Ma il punto è lo stesso.
Stai sicuramente spendere di più memoria, ma che stai ricevendo
flessibilità.
Perché ora se voglio aggiungere un elemento all'inizio di questa lista,
Devo assegnare un nuovo nodo.
E devo aggiornare solo quelli frecce in qualche modo semplicemente spostando
alcune indicazioni circa.
>> Se voglio inserire qualcosa nella metà della lista, non c'è bisogno di
spingere tutti a parte come abbiamo fatto in passato settimane con i nostri volontari che
rappresentato un array.
Posso solo assegnare un nuovo nodo e poi basta puntare il mouse in
direzioni diverse, perché non devono restare in effettivo
ricordo una vera linea come ho disegnato qui sullo schermo.
>> E poi, infine, se si desidera inserire qualcosa alla fine della lista, è
ancora più facile.
Questa è una sorta di notazione arbitraria, ma pointer di 34, prendere una supposizione.
Qual è il valore del suo puntatore più probabilmente sorta disegnato come un vecchio
antenna scuola lì?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: E 'probabilmente nullo.
E in effetti questo è uno di autore rappresentazione del nulla.
Ed è nullo perché è assolutamente bisogno di sapere dove la fine di un Linked
elenco è, per non continuare a seguire e seguito e seguendo queste frecce
ad un certo valore immondizia.
Quindi nulla significherà che non c'è più nodi a destra del numero 34,
in questo caso.
>> Quindi proponiamo che possiamo implementare questo nodo in codice.
E abbiamo visto questo tipo di sintassi prima.
Typedef solo definisce un nuovo tipo di noi, ci dà un sinonimo come
stringa era per char *.
In questo caso, sta andando a darci notazione abbreviata in modo che il nodo struct
invece può solo essere scritta come nodo, che è molto più pulito.
E 'molto meno prolisso.
>> All'interno di un nodo è apparentemente un int chiamato n, e quindi un nodo struct *
che significa esattamente quello che volevamo l' frecce per dire, un puntatore ad un altro
nodo dello stesso tipo di dati esatto.
E propongo che potremmo implementare un funzione di ricerca come questo, che a
prima vista potrebbe sembrare un po 'complessa.
Ma vediamo nel contesto.
>> Lasciatemi passare all'apparecchio qui.
Permettetemi di aprire un file chiamato Lista zero virgola h.
E che contiene solo la definizione che appena visto un momento fa per questi dati
tipo denominato nodo.
Così abbiamo messo che in un file h dot.
>> E per inciso, anche se questo programma che state per vedere è
Non tutto quel complesso, è infatti convenzione quando si scrive un programma per
mettere le cose come i tipi di dati, per tirare costanti a volte, all'interno della vostra
file di intestazione e non necessariamente in il file C, certamente quando la tua
programmi diventano sempre più grandi, in modo che sapete dove cercare, sia per
documentazione in alcuni casi, o di base come questo, le
definizione di un certo tipo.
>> Se ora apro list zero virgola c, notare un paio di cose.
Include una serie di file di intestazione, la maggior parte delle di cui abbiamo visto prima.
Esso include un proprio file di intestazione.
>> E per inciso, perché questo è doppio citazioni qui, a differenza dell'angolo
parentesi sulla linea che Ho evidenziato lì?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Sì, quindi è un file locale.
Quindi, se è un file locale del proprio qui sulla linea 15, per esempio, si utilizza
le doppie virgolette invece delle parentesi angolari.
>> Ora questo è abbastanza interessante.
Notate che ho dichiarato un globale variabile in questo programma on line 18
chiamato per primo, l'idea è questa è sarà un puntatore al primo
nodo nella mia lista collegata, e ho inizializzato a NULL, perché ho
non assegnato alcun effettivo nodi ancora pochi.
>> Quindi questo rappresenta, pittoricamente, quello che abbiamo ha visto un momento fa nella foto come
che puntatore all'estrema a sinistra lato.
Quindi, in questo momento, che puntatore non ha una freccia.
E invece è proprio nulla.
Ma rappresenta quello che sarà l' indirizzo del primo effettivo
nodo in questa lista.
Così ho implementato è un globale perché, come avrete capito, tutto questo
programma non nella vita è implementare una lista collegata per me.
>> Ora ho un paio di prototipi qui.
Ho deciso di implementare caratteristiche come cancellazione, inserimento, ricerca, e
attraversamento -
l'ultimo solo di essere a piedi attraverso il elenco, stampando i suoi elementi.
Ed ora ecco la mia routine principale.
E noi non spendere troppo tempo su questi dal momento che questo è una sorta di, si spera
vecchio cappello da ora.
>> Ho intenzione di effettuare le seguenti operazioni, mentre l'utente collabora.
Quindi uno, ho intenzione di stampare questo menù.
Ed è stato formattato come pulito come ho potuto.
Se l'utente digita in uno, il che significa vogliono cancellare qualcosa.
Se l'utente digita in due, il che significa vogliono inserire qualcosa.
E così via.
Sto per poi spingere poi per un comando.
E poi ho intenzione di usare GetInt.
>> Quindi questo è davvero un semplice menuing interfaccia in cui è sufficiente digitare
una mappatura per un numero di quei comandi.
E ora ho un interruttore pulito bella dichiarazione che sta per accendere
qualunque sia l'utente ha digitato dentro
E se digitati uno, io chiamare cancellare e rompere.
Se hanno scritto due, io chiamare inserire e rompersi.
>> E ora notato che ho messo ogni di questi sulla stessa linea.
Questa è solo una decisione stilistica.
In genere abbiamo visto qualcosa come questo.
Ma ho deciso, francamente, il mio programma sembrava più leggibile perché
era solo quattro casi di basta elencare in questo modo.
Uso del tutto legittimo di stile.
E ho intenzione di fare questo a condizione che la utente non ha digitato zero, che io
deciso significherà che vogliono smettere di fumare.
>> Così ora accorgo che cosa sto intenzione di fare qui.
Ho intenzione di liberare l'elenco apparentemente.
Ma più su che in un attimo.
Si deve prima eseguire questo programma.
Quindi permettetemi di fare un terminale più grande finestra, dot barra elenco 0.
Ho intenzione di andare avanti e inserire da tipizzazione due, un numero come 50, e ora
vedrete la lista è ora 50.
E il mio testo solo scorrere un po '.
Così ora notare la lista contiene il numero 50.
>> Facciamo un altro inserto prendendo due.
Andiamo a digitare il numero come uno.
List è ora uno, seguito da 50.
Quindi questa è solo una rappresentazione testuale dell'elenco.
E cerchiamo di inserire un altro numero come il numero 42, che è auspicabilmente
andando a finire in mezzo, perché questo programma, in particolare le specie che
elementi come li inserisce.
Quindi non abbiamo.
Super semplice programma che potrebbe assolutamente ho usato un array, ma io
capita di usare una lista concatenata solo così posso dinamicamente
crescere e ridurla.
>> Quindi, diamo uno sguardo per la ricerca, se io comando eseguito tre, voglio cercare
per, ad esempio, il numero 43.
E nulla è stato a quanto pare ha trovato, perché sono tornato alcuna risposta.
Quindi cerchiamo di farlo di nuovo.
Cerca.
Facciamo ricerca di 50, o meglio la ricerca per 42, che ha una bella
poco significato sottile.
E ho trovato il senso della vita lì.
Numero 42, se non si conosce il riferimento, Google esso.
D'accordo.
Così che cosa è questo programma fatto per me?
E 'solo che mi ha permesso di inserire così lontano e la ricerca di elementi.
>> Andiamo avanti veloce, poi, a che funzione ci lanciò un'occhiata a
il Lunedi come un teaser.
Quindi questa funzione, io sostengo, ricerche di un elemento nell'elenco da prima
uno, chiedendo all'utente e quindi chiamando GetInt per ottenere un int reale
che si desidera cercare.
>> Poi notare questo.
Ho intenzione di creare una variabile temporanea in linea 188 chiamato puntatore -
PTR -
avrebbe chiamato nulla.
Ed è un puntatore a un nodo perché ho detto nodo * lì.
E sono in fase di inizializzazione che sia uguale a prima in modo che io effettivamente ho il mio
dito, per così dire, sul molto primo elemento della lista.
Quindi, se la mia mano destra qui è PTR sono indicando la stessa cosa che prima
sta indicando.
>> Così ora torna in codice, cosa succede dopo -
questo è un paradigma comune quando l'iterazione su una struttura come un
lista collegata.
Ho intenzione di effettuare le seguenti operazioni mentre puntatore non è uguale a null Così, mentre
il mio dito non è puntato a un certo nullo valore, se il puntatore a freccia n è uguale a n.
Ci accorgiamo prima che n è quello che il utente digitato per GetInts chiamano qui.
>> E puntatore a freccia n significa che cosa?
Beh, se torniamo alla foto qui, se ho un dito che indica
tale primo nodo contenente nove, l' freccia essenzialmente significa andare a quel
nodo e afferrare il valore in posizione n, in questo caso, il campo dati chiamato n.
>> Per inciso - e abbiamo visto una coppia di settimane fa, quando qualcuno ha chiesto -
questa sintassi è nuovo, ma non lo fa ci danno poteri che noi
non hanno già.
Qual è stata questa frase equivale a utilizzare dot notazione e la stella di un paio
di settimane fa, quando abbiamo staccata indietro questo strato un po 'prematuramente?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Esatto, era stella, e poi era stella dot n, con
tra parentesi qui, che guarda, Francamente, penso che un sacco
più criptico di leggere.
Ma la stella puntatore, come sempre, mezzo ci vanno.
E una volta che ci sei, quali dati campo si desidera accedere?
Ebbene si utilizza la notazione del punto di accesso un campo di dati struct, e io
specificamente vogliono n.
>> Francamente, direi questo è solo più difficile da leggere.
E 'più difficile di ricordare dove fanno le parentesi vanno, la
stella e tutto il resto.
Così il mondo ha adottato alcuni sintattica zucchero, per così dire.
Solo un modo sexy per dire, questo è equivalente, e
forse più intuitivo.
Se il puntatore è davvero un puntatore, il freccia significa notazione ci vanno e trovano
il campo in questo caso chiama n.
>> Quindi, se lo trovo, nota quello che faccio.
Ho semplicemente stampare fuori, ho trovato per cento i, collegare il valore per quella int.
Chiamo dormire per un secondo solo per tipo di pausa le cose sullo schermo per
dare all'utente una seconda di assorbire quello che è appena accaduto.
E poi mi rompo.
Altrimenti, che cosa devo fare?
Aggiorno puntatore alla pari puntatore a freccia accanto.
>> Quindi, tanto per essere chiari, questo significa andare lì, usando la mia notazione vecchia scuola.
Quindi questo significa solo andare a qualsiasi si sta indicando, che in molto
primo caso è che sto indicando la struttura con nove in esso.
Così sono andato lì.
E allora significa che la notazione del punto, ottenere il valore successivo.
>> Ma il valore, anche se è disegnato come stretto, è solo un numero.
E 'un indirizzo numerico.
Quindi questa riga di codice, sia scritto come questo, il più criptico
modo, o come questo, il leggermente più modo intuitivo, significa solo spostare la mia mano
dal primo nodo a quello successivo, e poi quella successiva, e poi l'
successivo, e così via.
>> Quindi non ci soffermeremo sull'altro implementazioni di inserire e cancellare
e di attraversamento, i primi due dei che sono abbastanza coinvolti.
E penso che sia abbastanza facile da ottenere perso quando farlo verbalmente.
Ma cosa possiamo fare qui è cercare di determinare in che modo
farlo al meglio visivamente.
Perché io proporrei che se noi desiderare di inserire elementi in questa
elenco esistente, che ha cinque elementi -
9, 17, 22, 26, e 33 -
se dovessi realizzare questo in codice, ho bisogno di prendere in considerazione come andare
a fare questo.
>> E vorrei proporre piccoli passi per cui, in questo caso, voglio dire, che cosa sono
i possibili scenari che abbiamo potrebbe incontrare in generale?
Quando si implementa inserto per un linked elenco, questo accade solo per essere un
esempio specifico di dimensioni cinque.
Beh, se si desidera inserire un numero, come dire il numero uno, e
mantenere l'ordine ordinato, dove ovviamente fa il numero uno necessità di
andare in questo esempio specifico?
Come agli inizi.
>> Ma ciò che è interessante è che Se si desidera inserire uno in questo
elenco, che cosa speciale puntatore bisogno essere aggiornati a quanto pare?
Primo.
Quindi direi, questo è il primo caso che potremmo prendere in considerazione, una
scenario che richiede l'inserimento di l'inizio della lista.
>> Andiamo coratella fuori forse un facile o addirittura semplice caso, relativamente parlando.
Supponiamo che io voglio inserire il numero 35 in modo ordinato.
E, ovviamente, spetta laggiù.
Quindi cosa puntatore ovviamente sta per devono essere aggiornati in questo scenario?
Puntatore 34 del divenire non nullo ma l'indirizzo della struct
contenente il numero 35.
Ecco, questo è caso, due.
Così già, io sono sorta di quantizzazione quanto lavoro che devo fare qui.
>> E, infine, il caso centrale evidente è anzi, in mezzo, se voglio
inserire qualcosa come dire 23, che va tra il 23 e il 26, ma
Ora le cose si fanno un po 'più coinvolto perché ciò che
puntatori devono essere cambiate?
Quindi 22 ha ovviamente bisogno di essere cambiato perché non può puntare a 26 più.
Ha bisogno di puntare al nuovo nodo che Dovrò allocare chiamando
malloc o qualche equivalente.
>> Ma poi ho anche bisogno che il nuovo nodo, 23 in questo caso, per avere il suo puntatore
indicando chi?
26.
E ci sara 'un ordine delle operazioni qui.
Perché se faccio questo stupidamente, e io per l'avvio esempio all'inizio di
la lista, e il mio obiettivo è quello di inserire 23.
E posso controllare, appartiene qui, vicino a nove?
No.
Ha appartengono qui, accanto a 17?
No.
Lo fa appartiene qui accanto a 22?
Sì.
>> Ora, se io sono stupido qui, e non pensare questo attraverso, potrei
allocare il mio nuovo nodo per il 23.
Potrei aggiornare il puntatore da il nodo chiamato 22, indicando
esso al nuovo nodo.
E allora che cosa devo aggiornare puntatore del nuovo nodo di essere?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Esattamente.
Indicando 26.
Ma dannazione se non avessi già aggiorno Puntatore del 22 per puntare a questo ragazzo, e
ora ho orfani, il resto della lista, per così dire.
Così ordine delle operazioni qui sta per essere importante.
>> Per fare questo potrei rubare, dire, sei volontari.
E vediamo se non siamo in grado di fare questo visivamente invece di codice-saggio.
E noi abbiamo qualche bella lo stress palle per voi oggi.
OK, come su di uno, due, nel indietro - alla fine lì.
tre, quattro, tutti e due ragazzi alla fine.
E cinque, sei.
Certo.
Cinque e sei.
Va bene e verremo a voi la prossima volta.
Va bene, andiamo su.
>> Bene, visto che sei qui in primo luogo, ti piacerebbe essere quello goffamente
in Google Glass qui?
Va bene, quindi, OK, vetro, registrare un video.
OK, tu sei a posto.
>> Va bene, quindi se voi ragazzi può venire qui, ho preparato in anticipo
alcuni numeri.
Va bene, vieni qui.
E perché non te ne vai un po ' inoltre in questo modo.
E vediamo, qual è il tuo nome, con il vetro di Google?
>> STUDENTE: Ben.
>> SPEAKER 1: Ben?
OK, Ben, è sarà il primo, letteralmente.
Quindi stiamo per inviarti alla fine della fase.
Va bene, e il tuo nome?
>> STUDENTE: Jason.
>> SPEAKER 1: Jason, OK viene essere il numero nove.
Quindi, se volete seguire Ben in quel modo.
>> STUDENTE: Jill.
>> SPEAKER 1: Jill, si sta andando ad essere 17, che se avessi fatto questo più
intelligente, avrei partire all'altra estremità.
Si va così.
22.
E tu sei?
>> STUDENTE: Maria.
>> SPEAKER 1: Maria, sarete 22.
E il tuo nome è?
>> STUDENTE: Chris.
>> SPEAKER 1: Chris, sarete 26.
E poi, infine.
>> STUDENTE: Diana.
>> SPEAKER 1: Diana, sarete 34.
Quindi vieni un po 'qui.
>> Va bene, così perfetto ordinati ordinare già.
E andiamo avanti e fare questo in modo che possiamo veramente -
Ben sei solo tipo di ricerca fuori nel nulla lì.
OK, quindi andiamo avanti e raffigurano questo usando le braccia, proprio come mi è stato, appunto,
quello che sta succedendo.
Quindi, andare avanti e dare voi stessi un piede o due tra di voi.
E andare avanti e puntare con una mano per chi si dovrebbe puntare a
sulla base di questo.
E se sei nullo basta puntare dritto verso il pavimento.
OK, tutto bene.
>> Così ora abbiamo una lista collegata, e mi ha lasciato Propongo che io interpreto il ruolo di
PTR, quindi non mi dilungherò portare questo giro.
E poi - qualcuno stupido convention - è possibile chiamare questo tutto quello che vuoi -
puntatore del predecessore, puntatore pred -
è solo il soprannome che abbiamo dato in il nostro codice di esempio per la mia mano sinistra.
L'altra mano che sta per essere tenuta tenere traccia di chi è chi nel
seguenti scenari.
>> Quindi immagino, prima, voglio cogliere off quel primo esempio di inserimento, diciamo
20, nella lista.
Quindi ho intenzione di bisogno di qualcuno che incarnare il numero 20 per noi.
Quindi ho bisogno di qualcuno malloc da parte del pubblico.
Andiamo su.
Qual è il tuo nome?
>> STUDENTE: Brian.
>> SPEAKER 1: Brian, tutto a posto, in modo da è il nodo contenente 20.
Va bene, vieni qui.
E ovviamente, dove Brian non appartiene?
Quindi, nel mezzo di - effettivamente, aspetta un attimo.
Stiamo facendo questo per ordine.
Stiamo facendo questo molto più difficile quanto dovrebbe essere a prima.
OK, stiamo andando a libera Brian e realloc Brian come cinque.
>> OK, ora vogliamo inserire Brian come cinque.
Quindi forza qui accanto Ben solo per un momento.
E si può probabilmente dire dove questa storia sta andando.
Ma cerchiamo di riflettere attentamente su l'ordine delle operazioni.
Ed è proprio questa visuale che sta per allineare
con quel codice di esempio.
Così qui ho PTR puntando inizialmente non a Ben, di per sé, ma a qualsiasi
valore che egli contiene, che in questo caso è - cosa c'è di nuovo il tuo nome?
>> STUDENTE: Jason.
>> SPEAKER 1: Jason, così sia Ben e io sono indicando Jason in questo momento.
Così ora ho di determinare, da dove viene Brian appartiene?
Quindi l'unica cosa che ho accesso a in questo momento è il suo elemento di dati n.
Quindi ho intenzione di controllo, viene Brian meno di Jason?
La risposta è vera.
>> Così che ora deve accadere, nel giusto ordine?
Ho bisogno di aggiornare il numero di puntatori in totale in questa storia?
Dove la mia mano è ancora puntato verso Jason, e la tua mano - se si desidera
mettere la mano come, sorta di, mi non so, un punto di domanda.
OK, bene.
>> Va bene, in modo da avere alcuni candidati.
Sia Ben o io o Brian o Jason o di chiunque altro, che
puntatori bisogno di cambiare?
Quanti in tutto?
>> OK, quindi due.
Il mio puntatore non importa più perché io sono solo temporanei.
Quindi è questi due ragazzi, presumibilmente, sia Ben e Brian.
Quindi lasciatemi propongo aggiorniamo Ben, visto che è in primo luogo.
Il primo elemento di questa lista ora sta per essere Brian.
Così Ben punto a Brian.
OK, ora che cosa?
>> Chi viene puntato contro chi?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: OK così Brian ha per puntare a Jason.
Ma ho perso le tracce di tale puntatore?
Posso sapere dove Jason è?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: che faccio, visto che sono il puntatore temporaneo.
E presumibilmente, non ho cambiato per puntare al nuovo nodo.
Così possiamo semplicemente avere Brian punto a chi sto indicando.
E abbiamo finito.
Così caso uno, inserimento alla inizio della lista.
Ci sono stati due passaggi chiave.
Uno, dobbiamo aggiornare Ben, e poi dobbiamo anche aggiornare Brian.
E poi io non devo preoccuparsi scarpinare attraverso il resto del
lista, perché abbiamo già trovato il suo posizione, perché apparteneva alla
sinistra del primo elemento.
>> Va bene, quindi abbastanza semplice.
In realtà, si sente come ci siamo quasi rendendo questo troppo complicato.
Quindi cerchiamo di oggi coratella largo della fine della lista, e vedere dove
la complessità inizia.
Quindi, se ora, io alloc da parte del pubblico.
Chiunque vuole giocare 55?
Va bene, ho visto la prima mano.
Andiamo su.
Già.
Qual è il tuo nome?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Habata.
OK, andiamo su.
Sarete il numero 55.
Quindi, ovviamente, appartiene alla fine della lista.
Quindi cerchiamo di replay della simulazione con me essendo il PTR solo per un momento.
Quindi sono prima di andare a puntare a qualunque Ben sta indicando.
Stiamo entrambi puntando ora a Brian.
Quindi 55 non è inferiore a cinque.
Quindi ho intenzione di aggiornare me stesso che punta al prossimo puntatore di Brian, che
ora è ovviamente Jason.
55 non è inferiore a nove, così Ho intenzione di aggiornare PTR.
Ho intenzione di aggiornare PTR Ho intenzione di aggiornare PTR.
E ho intenzione di - hmm, che cosa è il tuo nome?
>> STUDENTE: Diana.
>> SPEAKER 1: Diana è rivolto, ovviamente, a nulla con la mano sinistra.
Così dove Habata realtà appartengono chiaramente?
A sinistra, qui.
Allora, come faccio a sapere di metterla qui Penso di aver fatto un casino.
Perché ciò che è arte PTR questo momento nel tempo?
NULL.
Così, anche se, visivamente, possiamo ovviamente vedere tutti questi
ragazzi qui sul palco.
Io non ho tenuto traccia del precedente persona nell'elenco.
Non ho un dito puntato fuori, in questo caso, il numero di nodo 34.
>> Quindi cerchiamo di iniziare effettivamente questo sopra.
Così ora io in realtà ho bisogno una seconda variabile locale.
E questo è quello che vedrete nel codice C campione reale, dove, come vado,
quando aggiorno la mia mano destra per puntare Jason, lasciando dietro di Brian, ho
meglio iniziare a usare la mano sinistra per aggiornare dove mi trovavo, in modo che come vado
attraverso questa lista -
più goffamente di quanto volessi ora qui visivamente -
Ho intenzione di arrivare al fine dell'elenco.
>> Questa mano è ancora nullo, che è abbastanza inutile, non per indicare
Sono chiaramente alla fine della lista, ma ora almeno ho questa
puntatore predecessore puntamento qui, quindi ora quali mani e quello che hanno bisogno di puntatori
essere aggiornato?
Quale mano vuoi riconfigurare primo?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: OK, quindi di Diana.
Dove vuoi puntare Puntatore a sinistra di Diana a?
In 55, presumibilmente, in modo che abbiamo inserito lì.
E dove dovrebbe andare 55 puntatore?
Giù, in rappresentanza null.
E le mie mani, a questo punto, non importa, perché erano solo
variabili temporanee.
Così ora abbiamo finito.
>> Quindi la complessità aggiuntiva lì - e non è così difficile da attuare,
ma abbiamo bisogno di una variabile secondaria per rendere Assicurarsi che prima di passare il mio diritto
mano, aggiorno il valore della mia sinistra mano, puntatore pred in questo caso, così
che ho una freccia scorrevole per tenere traccia di dove mi trovavo.
Ora, come un a parte, se stai pensando questo attraverso, questo si sente come se fosse un
poco fastidioso dover tenere traccia di questa mano sinistra.
>> Cosa sarebbe un'altra soluzione a questo problema sono stati?
Se avete avuto modo di ridisegnare i dati struttura stiamo parlando
attraversando in questo momento?
Se questo solo tipo di sente un po ' fastidioso avere, tipo, due puntatori
passare attraverso la lista, chi altro potrebbe hanno, in un mondo ideale, mantenuto
informazioni di cui abbiamo bisogno?
Sì?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Esattamente.
Destra così non c'è in realtà un interessante germe di un'idea.
E questa idea di un puntatore precedente, indicando l'elemento precedente.
Che cosa succede se ho appena incarnata che all'interno della lista stessa?
E sta andando essere difficile da visualizzare questo senza tutta la carta
cadere a terra.
Ma supponiamo che questi ragazzi utilizzati sia delle loro mani per avere una precedente
puntatore, e un puntatore prossimo, così attuare quello che chiameremo un doppiamente
lista collegata.
Questo mi avrebbe permesso a sorta di rewind, molto più facilmente senza di me, la
programmatore, dover tenere traccia manualmente -
veramente manualmente -
di dove ero stato precedentemente nell'elenco.
Quindi non lo faremo.
Vi terremo le cose semplici perché è intenzione di venire ad un prezzo, il doppio
molto spazio per i puntatori, se si vuole un secondo.
Ma questa è davvero una comune struttura di dati nota come
doppiamente lista collegata.
>> Facciamo l'esempio finale qui e mettere questi ragazzi fuori dalla loro miseria.
Così malloc 20.
Vieni su dalla navata lì.
Va bene, come ti chiami?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Scusa?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Demeron?
OK andiamo su.
Tu sarai 20.
È, ovviamente, sta per appartengono tra il 17 e il 22.
Quindi, mi permetta di imparare la lezione.
Ho intenzione di iniziare puntatore indicando Brian.
E ho intenzione di avere la mia mano sinistra aggiornare solo a Brian come mi muovo a
Jason, il controllo fa 20 meno di nove anni?
No.
È di 20 meno di 17?
No.
È di 20 meno di 22?
Sì.
Quindi cosa puntatori o le mani hanno bisogno di cambiare dove stanno puntando ora?
>> Così siamo in grado di fare 17 che punta a 20.
Così va bene.
Dove vogliamo puntare il puntatore del momento?
Al 22.
E sappiamo dove 22 è, ancora una volta grazie al mio puntatore temporaneo.
Quindi siamo OK lì.
Quindi, a causa di tale memorizzazione temporanea Ho tenuto traccia di dove tutti sono.
E ora si può andare visivamente in cui si appartiene, e ora abbiamo bisogno di 1, 2, 3,
4, 5, 6, 7, 8, 9 stress balls, e un applauso per
questi ragazzi, se potessimo.
Ben fatto.
>> [Applausi]
>> SPEAKER 1: Va bene.
E si può tenere i pezzi di carta come ricordi.
>> Va bene, allora, mi creda è molto più facile da attraversare, che con
esseri umani di quanto lo sia con il codice vero e proprio.
Ma ciò che troverete in un attimo ora, è che la stessa - Oh, grazie.
Grazie -
è che troverete che gli stessi dati struttura, una lista collegata, può effettivamente
essere utilizzato come blocco di ancora più strutture dati sofisticate.
>> E realizzare anche il tema qui è che abbiamo assolutamente introdotto più
complessità in attuazione di questo algoritmo.
Di inserimento, e se siamo andati attraverso di essa, la cancellazione e la ricerca, è un po '
più complicato di quanto era con un array.
Ma ci guadagno un po 'di dinamismo.
Otteniamo una struttura dati adattivo.
>> Ma ancora una volta, paghiamo un prezzo di avere un po 'di ulteriori complessità, sia nella
attuazione.
E si sta per fornire l'accesso casuale.
E ad essere onesti, non c'è qualche bella pulire vetrino posso darti che
dice qui è perché una lista concatenata è meglio di un array.
E lasciare le cose come stanno.
Poiché il tema ricorrente ora, anche di più nelle prossime settimane, è
che non c'è necessariamente una risposta corretta.
>> Questo è il motivo per cui abbiamo l'asse separato di progettazione per set problema.
Sarà molto sensibili al contesto se si desidera utilizzare questi dati
struttura o quello, e sarà dipenderà da ciò che conta per voi in termini
delle risorse e la complessità.
>> Ma lasciate che propongo i dati ideali struttura, il Santo Graal, sarebbe
qualcosa che è tempo costante, indipendentemente dalla quantità di roba è
al suo interno, non sarebbe sorprendente se un struttura dati restituiti risposte in
tempo costante.
Sì.
Questa parola è nel vostro dizionario enorme.
Oppure no, questa parola non è.
O qualsiasi problema.
Bene vediamo se non possiamo almeno fare un passo in quella direzione.
>> Permettetemi di proporre una nuova struttura dati che può essere utilizzato per diverse cose,
in questo caso denominata tabella hash.
E così siamo tornati alla realtà guardando in una matrice, in questo caso, e
un po 'arbitrariamente, ho disegnato questo tabella hash come un array con una sorta di
array bidimensionale -
o meglio, è raffigurato qui come due matrice bidimensionale - ma questo è solo
un array di dimensione 26, tale che se ci richiamare la tabella matrice, staffa da tavolo
zero è il rettangolo in alto.
Tabella staffa 25 è il rettangolo in basso.
Ed è così che avrei potuto disegnare un dato struttura in cui voglio conservare
nomi delle persone.
>> Così, per esempio, e non voglio disegnare la cosa tutto qui sulla testa, se io
avuto questa matrice, che ora sto andando a chiamare una tabella hash, e questo è di nuovo
posizione zero.
Questa qui è la posizione uno, e così via.
Io affermo che voglio usare questi dati struttura, per amore di discussione,
per memorizzare i nomi delle persone, Alice e Bob e Charlie e altri nomi.
Quindi, pensare a questo ora come gli inizi di, diciamo, un dizionario
con un sacco di parole.
Capita di essere nomi nel nostro esempio qui.
E questo è tutto troppo germano, forse, per l'attuazione di un correttore ortografico, come abbiamo
potrebbe per il problema definito sei.
>> Quindi, se abbiamo un array di dimensioni totali 26 in modo che questa è la posizione 25
in fondo, e io sostengo che Alice è la prima parola nel dizionario di
nomi che voglio inserire nella RAM, in questa struttura dati, in cui sono
istinto che ti dice che di Alice nome dovrebbe andare in questa serie?
>> Abbiamo 26 opzioni.
Dove vogliamo metterla?
Vogliamo che lei in staffa a zero, giusto?
A per Alice, chiamiamolo che zero.
E B sarà uno, e C saranno due.
Quindi andremo a scrivere Nome qui di Alice.
Se poi inseriamo Bob, il suo nome andrà qui.
Charlie andrà qui.
E così via verso il basso attraverso questa struttura dati.
>> Questa è una struttura dati meraviglioso.
Perché?
Beh, che cosa è il tempo di esecuzione di inserendo il nome di un essere umano in questo
dati di struttura in questo momento?
Dato che questa tabella è implementato, veramente, come un array.
Beh, è ​​un tempo costante.
E 'ordine di uno.
Perché?
>> Beh come si fa a determinare dove Alice appartiene?
Si guarda a quale lettera del suo nome?
Il primo.
E si può arrivare, se si tratta di una stringa, solo guardando stringa
Staffa zero.
Quindi, il carattere zero della stringa.
Questo è facile.
Lo abbiamo fatto in crypto assegnazione settimane fa.
E poi una volta che si sa che Alice lettera è maiuscola, siamo in grado di sottrarre
off 65 o maiuscola se stessa, che ci dà zero.
Così ora sappiamo che Alice appartiene in posizione zero.
>> E dato un puntatore a questi dati struttura, di qualche tipo, per quanto tempo fa
mi ci vorrà per trovare posizione zero in un array?
Solo un passo, a destra E 'tempo costante causa dell'accesso casuale abbiamo
proposto era una caratteristica di una matrice.
Così, in breve, cercando di capire che cosa l'indice del nome di Alice è, che è, in
questo caso, è A, o facciamo solo risolvere che a zero, dove B è una e C è
due, pensando che fuori è tempo costante.
Non mi resta che guardarla prima lettera, cercare di capire dove zero è un
array è anche tempo costante.
Quindi tecnicamente questo è come due gradini ora.
Ma questo è ancora costante.
Quindi noi chiamiamo grande O di uno, quindi abbiamo Alice inserito in questa tabella in
tempo costante.
>> Ma, naturalmente, devo essere ingenuo qui, giusto?
E se ci fosse un Aaron nella classe?
O Alicia?
O altri nomi che iniziano con A. Dove stiamo andando a mettere
quella persona, giusto?
Voglio dire, in questo momento ci sono solo tre persone sul tavolo, quindi forse abbiamo
dovrebbe mettere Aaron a posizione zero uno due tre.
>> Giusto, potrei mettere una qui.
Ma allora, se proviamo a inserire Davide in questo elenco, da dove viene David andare?
Ora il nostro sistema inizia rottura verso il basso, giusto?
Perché ora David finisce qui se Aaron è in realtà qui.
E così ora tutta questa idea di avere un struttura dati pulita che ci dà
inserimenti di tempo costanti non è più costante di tempo, perché devo
controllare, oh, dannazione, qualcuno è già in posizione di Alice.
>> Permettetemi di sondare il resto di questi dati struttura, alla ricerca di un posto per mettere
chi, come il nome di Aaron.
E così anche questo sta iniziando di prendere tempo lineare.
Inoltre, se la società vuole trovare il Aaron in questa struttura dati, e si
controllo, e il nome di Aaron non è qui.
Idealmente, si dovrebbe solo dire Aaron non nella struttura dati.
Ma se si fa iniziare a fare spazio a Aaron dove non avrebbe dovuto essere un D
o una E, si, nel peggiore dei casi, è necessario controllare la struttura di dati interi, in
qual caso essa devolve in qualcosa lineare nella dimensione della tabella.
>> Quindi tutto bene, io sistemo questo.
Il problema qui è che ho avuto 26 elementi in questo array.
Permettetemi di cambiarlo.
Whoops.
Permettetemi di modificarlo in modo che, invece di essere di taglia 26 in totale, notare il fondo
indice sta per cambiare per n meno 1.
Se 26 è chiaramente troppo piccolo per gli esseri umani ' nomi, perché ci sono migliaia di
nomi del mondo, facciamo solo fare a 100 o 1000 o 10000.
Diciamo solo destinare molto più spazio.
>> Beh, questo non significa necessariamente diminuire la probabilità che non avremo due
persone con nomi che iniziano con A, e così, si andavano a cercare di mettere un
I nomi di luogo a zero ancora.
Stanno ancora andando a collidere, che significa che abbiamo bisogno di una soluzione per mettere
Alice e Aronne e Alicia e le altre nomi che iniziano con A altrove.
Ma quanto di un problema è questo?
Qual è la probabilità che si avere collisioni in un dato
struttura come questa?
>> Beh, mi permetta - ci torneremo a questa domanda qui.
E guarda come potremmo risolverlo prima.
Permettetemi di tirare su questa proposta qui.
Ciò che abbiamo appena descritto è un algoritmo, una euristica chiamato lineare
sondaggio in base al quale, se si è tentato di inserire qualcosa qui in questi dati
struttura, che si chiama una tabella hash, e non c'è spazio lì, si
veramente sondare la struttura dati controllo, è disponibile questo?
È questo Disponibile è disponibile questo?
È questo a disposizione?
E quando finalmente è, si inserisce il nome che si originariamente previsto
altrove in quella posizione.
Ma nel caso peggiore, l'unico punto potrebbe essere la molto inferiore dei dati di
struttura, alla fine della matrice.
>> Così scansione lineare, nel caso peggiore, devolve in un algoritmo lineare dove
Aaron, se gli capita di essere inserito all'ultimo in questa struttura dati, potrebbe
collidere con questa prima posizione, ma poi finiscono per sfortuna, alla fine molto.
Quindi questa non è una costante tempo santo graal per noi.
Questo metodo di inserimento di elementi in una struttura dati chiamata hash
tabella non sembra essere tempo costante almeno non nel caso generale.
Si può devolvere in qualcosa di lineare.
>> Che importa se risolviamo collisioni un po 'diverso?
Quindi, ecco un più sofisticato avvicinarsi a ciò che è ancora
denominata tabella hash.
E da hash, per inciso, che cosa Insomma è l'indice che
Mi riferivo prima.
Per hash qualcosa può essere pensato come un verbo.
>> Quindi, se si hash Alice è un nome, una funzione hash, per così dire,
dovrebbe restituire un numero.
In questo caso è pari a zero se lei appartiene a posizione zero, uno, se lei appartiene a
ubicazione uno, e così via.
Quindi la mia funzione di hash finora è stato super semplice, solo guardando il
prima lettera nel nome di qualcuno.
Ma una funzione hash prende come Ingresso qualche pezzo di dati, un
stringa, int, qualunque cosa.
E sputa fuori in genere un numero.
E questo numero è qui che i dati elemento appartiene in una struttura dati
conosciuto qui come una tabella hash.
>> Quindi, solo intuitivamente, questo è un contesto leggermente diverso.
Questo in realtà si riferisce ad un esempio compleanni a cui partecipano
ci potrebbero essere fino a 31 giorni del mese.
Ma che cosa ha fatto questa persona decide di fare in caso di collisione?
Contesto ora essere, non una collisione di nomi, ma uno scontro di compleanni,
se due persone hanno lo stesso compleanno il 2 ottobre, per esempio.
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Sì, così qui abbiamo la valorizzazione delle liste collegate.
Quindi sembra un po 'diverso che abbiamo disegnato in precedenza.
Ma sembra che abbiamo a un array sul lato sinistro.
Questo è un indice, per non motivo particolare.
Ma è ancora un array.
Si tratta di un array di puntatori.
E ciascuno di questi elementi, ciascuno dei questi cerchi o barre - lo slash
che rappresenta null - ciascuno di questi puntatori è apparentemente indicando
quale struttura dati?
Una lista concatenata.
>> Così ora abbiamo la possibilità di codificare nel nostro programma
la dimensione della tabella.
In questo caso, sappiamo che non c'è mai più di 31 giorni in un mese.
Così difficile codifica un valore come 31 è ragionevole in quel contesto.
Nel contesto di nomi, codifica duro 26 non è irragionevole che sia la gente
nomi iniziano solo con, per esempio, l'alfabeto coinvolgendo A alla Z.
>> Siamo in grado di stipare tutti in quei dati struttura finché, quando otteniamo una
collisione, non mettiamo i nomi qui, noi invece pensiamo di queste cellule
non come corde stesse, ma come puntatori a, per esempio, Alice.
E allora Alice può avere un altro puntatore ad un altro nome che inizia con
A. E Bob in realtà va qui.
>> E se c'è un altro nome che inizia con B, finisce qui.
E così ciascuno degli elementi di questa tavolo due, se abbiamo progettato questo un
po 'più intelligente -
andiamo -
se abbiamo progettato questo un po 'più abilmente, diventa ora un dato adattivi
struttura, dove non c'è limite rigido da quanti elementi è possibile inserire
in esso, perché se lo fai avere una collisione, che va bene.
Basta andare avanti e aggiungerla quello che abbiamo visto un po 'fa era
noto come un elenco collegato.
>> Bene cerchiamo di mettere in pausa per un momento.
Qual è la probabilità di una collisione in primo luogo?
Giusto, forse sto più pensando, forse Sono più di ingegnerizzare questo problema,
perché si sa che cosa?
Sì, posso venire con arbitraria Esempi di fuori della parte superiore della mia testa, come
Allison e Aaron, ma in realtà, data una distribuzione uniforme di
ingressi, cioè alcuni inserimenti casuali in una struttura di dati, ciò che è veramente
la probabilità di una collisione?
Ebbene si rivela, in realtà è altissima.
Permettetemi di generalizzare questo problema è come questo.
>> Quindi, in una stanza di n CS50 studenti, che cosa è la probabilità che almeno
due studenti in sala hanno la stessa data di nascita?
Quindi non c'è cosa. alcuni Hund -
200, 300 persone qui e diversi centinaia di persone a casa oggi.
Quindi, se si voleva chiederci che cosa è la probabilità di due persone
in questa stanza hanno lo stesso compleanno, siamo in grado di capirlo.
E io sostengo in realtà ci sono due persone con lo stesso compleanno.
>> Per esempio, qualcuno hanno compleanno oggi?
Ieri?
Domani?
Va bene, così ci si sente come sto andando di avere a che fare questo 363 o giù di lì più
volte per capire effettivamente fuori Se abbiamo una collisione.
Oppure potremmo fare questo matematicamente piuttosto che noiosamente
fare questo.
E proporre la seguente.
>> Quindi propongo che potremmo modellare la probabilità di due persone che hanno la
stessa data di nascita come la probabilità di 1 meno la probabilità di avere nessuno
lo stesso compleanno.
Quindi, per ottenere questo, e questo è solo il modo elegante per scrivere questo, per il
prima persona nella stanza, lui o lei può avere uno qualsiasi dei possibili
compleanni assumendo 365 giorni l'anno, con tante scuse a persone con
il 29 ° compleanno di febbraio.
>> Così la prima persona in questa stanza è libera per avere un qualsiasi numero di compleanni
fuori delle 365 possibilità in modo che lo faremo 365 diviso per 365,
che è uno.
La prossima persona nella stanza, se l'obiettivo è quello di evitare una collisione, può solo
avere il suo compleanno su come molte diverse possibili giorni?
364.
Quindi il secondo termine in questa espressione è sostanza, facendo che la matematica per noi
sottraendo fuori un giorno possibile.
E poi il giorno dopo, il giorno successivo, il giorno seguente difetto al numero totale
di persone nella stanza.
>> E se si considera poi, qual è allora la probabilità di non avere tutti
compleanni uniche, ma di nuovo 1 meno che, ciò che otteniamo è espressione
che può molto fantasiosamente simile a questa.
Ma è più interessante da guardare visivamente.
Questo è un grafico in cui sul asse x è il numero di persone nella stanza, il
numero di compleanni.
Sulla asse y è la probabilità di una collisione, due persone
avendo lo stesso compleanno.
>> E l'asporto da questa curva è che, non appena si arriva a come 40
studenti, siete in su in una probabilità del 90% combinatorically di due
o più persone che hanno lo stesso compleanno.
E una volta che si arriva a come 58 persone che è quasi il 100% di una possibilità due
persone in sala stanno per avere la stessa data di nascita, anche se non c'è
365 o 366 possibili secchi, e solo 58 persone nella stanza.
Proprio statisticamente è molto probabile che ottenere collisioni, che in breve
motiva questa discussione.
Che anche se otteniamo fantasioso qui, e iniziare con queste catene, siamo ancora
intenzione di avere collisioni.
>> In modo che pone la domanda, qual è la costo di fare inserimenti ed eliminazioni
in una struttura dati come questo?
Ebbene vorrei propongo -
e lasciatemi tornare alla schermata sopra qui - se abbiamo n elementi nel
elenco, quindi se stiamo cercando di inserire n elementi, e abbiamo
quanti secchi totali?
Diciamo che 31 secchi totali nel caso di compleanni.
Qual è la lunghezza massima di un di queste catene potenzialmente?
>> Se ancora non c'è 31 possibili compleanni in un dato mese.
E siamo solo grumi tutti -
in realtà questo è un esempio stupido.
Facciamo 26 invece.
Quindi, se in realtà sono persone i cui nomi iniziare con A a Z, dando così
noi 26 possibilità.
E stiamo usando una struttura dati come quello che abbiamo appena visto, per cui abbiamo
un array di puntatori, ciascuno dei quali indica una lista collegata dove l'
primo elenco è di tutti con il nome Alice.
Il secondo elenco è ogni con l' nome che inizia con A, a partire
con B, e così via.
>> Qual è la durata probabile di ciascuno di tali elenchi se si assume una bella pulita
distribuzione dei nomi da A a Z attraverso l'intera struttura dati?
Ci sono n persone nella struttura dati diviso per 26, se sono ben
sparsi su tutto il struttura dati.
Quindi la lunghezza di ciascuno di questi catene è n diviso per 26.
Ma nella grande notazione O, che cos'è?
Che cosa è che davvero?
Quindi è davvero solo n, giusto?
Perché abbiamo detto in passato, ugh che si divide per 26.
Sì, in realtà è più veloce.
Ma in teoria, non è fondamentalmente tutto questo veloce.
>> Quindi, non ci sembra di essere più di tanto più vicino a questo Santo Graal.
In realtà, questo è solo il tempo lineare.
Heck, a questo punto, perché non ci basta usare una lista collegata enorme?
Perché non basta usare un enorme matrice per memorizzare i nomi dei
tutti nella stanza?
Beh, c'è ancora qualcosa avvincente di una tabella di hash?
C'è ancora qualcosa di interessante una struttura dati
che assomiglia a questo?
Questo.
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Giusto, e di nuovo se è solo un algoritmo di tempo lineare, e un
struttura di dati in tempo lineare, perché non ho basta memorizzare il nome di tutti in una grande
array o in una grande lista collegata?
E smettere di fare CS così molto più difficile di quanto dovrebbe essere?
Ciò che è interessante su questo, anche anche se ho graffiato fuori?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Inserimenti non lo sono?
Più costoso.
Così inserimenti potenzialmente potrebbe ancora essere costante di tempo, anche se i dati
la struttura si presenta così, una serie di puntatori, ognuno dei quali sta puntando
potenzialmente una lista collegata.
Come si potrebbe ottenere costante inserimento tempo di nomi?
Stick it in fronte, giusto?
>> Se sacrifichiamo un obiettivo di progettazione da in precedenza, in cui abbiamo voluto mantenere
nome di tutti, per esempio, in ordine, o tutti i numeri sul palco ordinati,
supponiamo di avere un lista collegata indifferenziati.
E solo ci costa uno o due passi, come nel caso di Ben e Brian
precedenza, per inserire un elemento in l'inizio della lista.
Quindi, se non ci preoccupiamo di smistamento tutti dei nomi che iniziano con A o tutti
i nomi che iniziano con B, possiamo ancora conseguire costante inserimento tempo.
Ora guardando Alice o Bob o qualsiasi nome più in generale, è ancora quello?
È grande O di n diviso per 26, nella caso ideale in cui tutti sono uniformemente
distribuito, dove c'è il maggior numero di un come ci sono le Z, che è probabilmente
irrealistico.
Ma questo è ancora lineare.
>> Ma qui, torniamo al punto di di notazione asintotica essere
teoricamente vero.
Ma nel mondo reale, se io affermo che il mio programma può fare qualcosa di 26 volte
più veloce della tua, il cui programma hai intenzione di preferire usando?
Tua o la mia, che è 26 volte più veloce?
Realisticamente, la persona di cui è 26 volte più veloce, anche se teoricamente
i nostri algoritmi eseguiti nella stessa asintotica tempo di esecuzione.
>> Lasciatemi propongo un diverso soluzione del tutto.
E se questo non vi lascia sbalorditi, siamo fuori di strutture di dati.
Quindi questo è un trie -
genere di un nome stupido.
Viene da recuperi, e la parola è scritto trie, t-r-i-e, a causa di
recupero naturalmente suona come trie.
Ma questa è la storia della parola trie.
>> Quindi un trie è infatti una specie di albero, ed è anche un gioco di quella parola.
E anche se non riesco a vederlo con questa visualizzazione, un trie è un
albero strutturato, come un albero di famiglia con un antenato in alto e molto altro
di nipoti e pronipoti come le foglie sul fondo.
Ma ogni nodo in un trie è un array.
Ed è in un array - e sia di una semplificazione delle per un momento - è un
array, in questo caso, di dimensioni 26, dove ogni nodo nuovo è una matrice di dimensione
26, dove l'elemento zeroth in tale Una matrice rappresenta, e l'ultimo
elemento in ogni tale matrice rappresenta Z.
>> Quindi propongo, quindi, che questi dati struttura, noto come un trie, può essere
utilizzato anche per memorizzare le parole.
Abbiamo visto un momento fa, come abbiamo potuto conservare parole, o in questo caso i nomi, e noi
visto in precedenza come possiamo memorizzare i numeri, ma se ci concentriamo sui nomi o stringhe
qui, notare ciò che è interessante.
Io sostengo che il nome Maxwell è interno di questa struttura dati.
Dove vedi Maxwell?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: A sinistra.
Quindi, ciò che è interessante di questi dati la struttura è piuttosto che il negozio
stringa M-A-X-W-E-L-L backslash zero, l'intera contiguo, quello che invece fa
sta seguendo.
Se questo è un trie come la struttura di dati, ciascuno dei nodi di cui è ancora una volta un array,
e si desidera memorizzare Maxwell, è prima indice e quindi il nodo della radice, in modo
di parlare, il nodo più in alto, in posizione M, a destra, in modo da
approssimativamente in mezzo.
E poi da lì, si segue un puntatore ad una nodi figlio, per così dire.
Quindi, nella struttura di senso di famiglia, si segue verso il basso.
E che si portano a un altro nodo sulla sinistra, che è
solo un altro array.
>> E poi se si desidera memorizzare Maxwell, si trova il puntatore che rappresenta
A, che è questo qui.
Poi si passa al nodo successivo.
E di gara - questo è il motivo della foto un po 'ingannevole -
questo nodo look super minuscola.
Ma a destra di questa è Y e Z. E 'solo l'autore ha troncato la
immagine in modo che effettivamente vedere le cose.
Altrimenti questa immagine sarebbe estremamente ampia.
Così ora si indice nella posizione X, allora W, allora E, poi L, poi L. Allora qual è
questa curiosità?
>> Beh, se stiamo usando questa sorta di nuovo assumere come memorizzare una stringa in un
struttura dei dati, è comunque necessario controllare essenzialmente off nei dati
struttura che una parola finisce qui.
In altre parole, ciascuno di questi nodi ha in qualche modo ricordare che siamo
effettivamente seguito tutti i puntatori e stanno lasciando un po '
pangrattato al fondo di questa qui Struttura per indicare M-A-X-W-E-L-L è
infatti in questa struttura dati.
>> Così potremmo farlo in questo modo.
Ciascuno dei nodi del quadro che abbiamo appena sega ha uno, un array di dimensione 27.
Ed è ora 27, perché in p definito sei, avremo effettivamente dare un apostrofo,
così possiamo avere nomi come O'Reilly e altri con apostrofi.
Ma la stessa idea.
Ciascuno di tali elementi nella punti array ad una struct
nodo, quindi basta un nodo.
Quindi questo è molto ricorda della nostra lista collegata.
>> E poi ho un booleano, che verrà chiamare Parola, che è solo andare a essere
vero se una parola finisce nel nodo nell'albero.
Esso rappresenta efficacemente il piccolo triangolo abbiamo visto un momento fa.
Quindi se una parola termina in quel nodo nel albero, quel campo parola sarà vero,
che sta controllando concettualmente off, o stiamo disegnando questo triangolo, sì, ci
è una parola qui.
>> Quindi questo è un trie.
E ora la domanda è: che cosa è il suo tempo di esecuzione?
E 'grande O di n?
E 'qualcosa d'altro?
Beh, se hai n nomi di questi dati struttura, Maxwell essere solo uno di
loro, che cosa è il tempo di esecuzione di l'inserimento o la ricerca di Maxwell?
Qual è il tempo di esecuzione di inserimento di Maxwell?
Se ci sono n altri nomi già nella tabella?
Sì?
>> STUDENTE: [incomprensibile].
>> SPEAKER 1: Sì, è la lunghezza del nome, giusto?
Quindi M-a-x-w-e-l-l così ci si sente come questo algoritmo è O grande di sette.
Ora, naturalmente, il nome varieranno in lunghezza.
Forse è un nome breve.
Forse è un nome più lungo.
Ma ciò che è fondamentale è che si tratta di un numero costante.
E forse non è proprio costante, Ma Dio, se realisticamente, in un
dizionario, probabilmente c'è qualche limite il numero di lettere in un
il nome della persona in un determinato paese.
>> E così possiamo supporre che valore è una costante.
Io non so cosa sia.
E 'probabilmente più grande di pensiamo che sia.
Perché c'è sempre qualche angolo caso con un nome folle lungo.
Quindi chiamiamola k, ma è pur sempre un costante presumibilmente, perché ogni
nome nel mondo, almeno in una particolare paese, è che la lunghezza o
più breve, quindi è costante.
Ma quando abbiamo detto qualcosa è grande O di un valore costante, che cosa è che
davvero equivalente a?
Questa è davvero la stessa cosa come dire tempo costante.
>> Ora siamo un po 'barare, giusto?
Siamo un po 'sfruttando qualche teoria qui per dire che bene, l'ordine di k è
davvero solo ordinare di uno, ed è tempo costante.
Ma è davvero.
Perché l'intuizione chiave qui è che se abbiamo n nomi già in questa
struttura dati, e inseriamo Maxwell, è la quantità di tempo che ci vuole per
inserire Maxwell affatto interessata da quante altre persone
sono nella struttura dati?
Non sembra essere.
Se avessi un miliardo di altri elementi a questa trie, e quindi inserire Maxwell, è
ha affatto influenzato?
No.
E questo è diverso da tutti i dati al giorno strutture che abbiamo visto finora, dove
il tempo di esecuzione del vostro algoritmo è completamente indipendente quanta
roba è o non è già in tale struttura di dati.
>> E così con questo che consente di godere ora è un opportunità di p set di sei, che sarà
ancora una volta coinvolgere di implementare un correttore ortografico, la lettura a 150.000
parole, il modo migliore per conservare quella non è necessariamente evidente.
E se ho aspirato a trovare il Santo Graal, non mi
sostengono che un trie è.
Infatti, una tabella hash può benissimo rivelarsi molto più efficiente.
Ma questi sono solo -
questa è solo una delle decisioni di progettazione si dovrà fare.
>> Ma in chiusura prendiamo 50 o giù di lì secondi per dare uno sguardo a ciò che sta
avanti la prossima settimana e al di là di noi transizione da questa linea di comando
mondo, se programmi in C per cose web base e linguaggi come PHP e
Javascript e la stessa Internet, protocolli come HTTP, il quale hai
dato per scontato per anni ora, e digitato la maggior parte ogni
giorno, forse, o visto.
E inizieremo a staccare il strati di ciò che è internet.
E qual è il codice che alla base gli strumenti di oggi.
Quindi 50 secondi di questo teaser qui.
Vi do Guerrieri della rete.
>> [RIPRODUZIONE VIDEO]
>> -E 'venuto con un messaggio.
Con un protocollo tutto suo.
Egli è venuto per un mondo di crudeli firewall, router menefreghista, e pericoli lontano
peggiore della morte.
E 'veloce.
Lui è forte.
Lui è TCPIP.
E ha il vostro indirizzo.
Guerrieri della rete.
>> [FINE RIPRODUZIONE VIDEO]
>> SPEAKER 1: Questo è il modo in internet devono lavorare come della prossima settimana.