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. 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 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.