DAVID MALAN: Va bene. Bentornati CS50. Questo è l'inizio della settimana 8. E ricordare che il problema insieme 5 conclusa con un po 'di una sfida. Quindi, supponendo che avete recuperato tutti i tuoi Fellows insegnamento e fotografie di CA nel file card.raw, si ha diritto per ora trovare tutte quelle persone, e un fortunato vincitore porterà a casa con uno di queste cose, il movimento salto dispositivo che è possibile utilizzare per la finale progetti, per esempio. 

Questo, ogni anno, porta a un po 'di creepiness. E così quello che ho pensato di fare è di condividere con voi alcune delle note che hanno andato avanti e indietro su l'elenco del personale di ritardo. Per esempio, proprio ieri sera, citazione unquote, da uno del personale membri, "Ho appena avuto una botta studente alla mia porta per fare una foto con me. Stalkers, vi dico. "Iniziato abbastanza descrittivo e poi ci siamo trasferiti a, circa un'ora dopo, "ho avuto un studente mi aspetta dopo la sezione e aveva tutti i nostri nomi e le foto su alcuni fogli di carta. «Va bene. Così organizzato, ma non tutto questo raccapricciante ancora. 

Poi, "Ero fuori città questo fine settimana, e quando sono tornato, non c'era uno in il mio camera da letto. "[risate] DAVID MALAN: Avanti citazione da uno staff membro ", uno studente è venuto a casa mia a Somerville alle 4:00 di questa mattina. "Avanti personale ", ho avuto al mio albergo a San Francisco e uno studente stava aspettando me alla hall con tre reflex digitali. " Tipo di fotocamera. "Non sono nemmeno sul personale in questo semestre, ma uno studente entrato in casa mia questa mattina e registrato il tutto con Google Glass. "E poi, infine, "Almeno 12 persone sono state avidamente attesa per me quando ho ottenuto dalla mia limo, e poi ho svegliò. «Va bene. Così tra le fotografie, come si può ricordare, è questo tizio qui, che si potrebbe sapere come Milo Banana, che vive con Lauren Carvalho, la nostra testa Teaching Fellow. Milo, Milo, vieni qui ragazzo. Milo. Milo. Intendiamoci, indossa Google Glass, così vi mostreremo tutto questo dopo. Quindi questo è Milo, se si desidera scattare una fotografia con lui dopo. Se vuoi guardare fuori presso il pubblico lì. OK. Questo è un bene metraggio. Beh, Milo Banana. Oh, non farlo. 

[Risata] 

OK. Così una parola poi su quello che ci aspetta, perché come si comincia a transizione, questa settimana specificamente, da C in un ambiente a riga di comando di PHP e Javascript e SQL e HTML e CSS in un ambiente web-based, saremo dotare voi con tutto l' più conoscenza per potenziali progetti finali. A questo scopo, il corso ha un tradizione di organizzazione di seminari che sono su temi tangenziali al corso. Molto legati alla programmazione e al lo sviluppo di applicazioni e così via, ma non necessariamente esplorato da proprio piano di studi del corso. 

Quindi, se si potrebbe essere interessati a una o più dei seminari di quest'anno, registrarsi al cs50.net/seminar. Ci sono seminari anziani a cs50.net/seminars. E nel roster finora per quest'anno sono sorprendenti applicazioni Web con Ruby on Rails, che è un'alternativa linguaggio di PHP. Linguistica Computazionale. Introduzione a iOS, che è la piattaforma che viene utilizzata per iPhone e sviluppo iPad. JavaScript per applicazioni web, vedremo che, ma in questo seminario, andrai in più particolare. 

Leap Movimento, quindi dovremo effettivamente avere qualche dei nostri amici di Leap Movimento, l'azienda stessa, unisciti a noi. Domani, infatti, per fornire un hands-on seminario, se di interesse per voi. Meteor.js, una tecnica alternativa per utilizzando JavaScript non in un browser, ma su un server. Node.js, che è molto in quella vena pure. Design elegante Android. Android essendo una alternativa molto popolare a iOS e Windows Phone e altre piattaforme mobili. E Web Defense Active Security. 

Quindi, in realtà, se si desidera di impegnarsi in questo, mi permetta prendere atto di questo. Siamo molto felici di dire che i nostri amici di Leap Movimento, che è una startup - questo dispositivo davvero appena arrivato un paio di mesi fa - ha gentilmente donato 30 tali dispositivi alla classe per altrettanti studenti, se vuoi prendere in prestito l'hardware verso la fine del semestre e utilizzarlo per un progetto finale vero e proprio. Essi sostengono un certo numero di lingue. Nessuno di loro C, nessuno di loro PHP, così realizzare uno o più di questi seminari potrebbe rivelarsi di interesse. E tutti loro sarà girato in caso in cui non si è in grado partecipare di persona. Il calendario sarà annunciato tramite mail come abbiamo solidificare camere. 

E, infine, se si va a projects.cs.50.net, questo è un sito sosteniamo ogni anno, che vi invitiamo gente della comunità, docenti, reparti, personale, ed entrambi in un fuori di CS50 per proporre idee progettuali. Le cose di interesse per gruppi di studenti. Motivi di interesse ai reparti. Quindi girare lì, se stai lottando con l'incertezza di ciò che si lei vorrebbe affrontare. 

Così l'ultima volta abbiamo introdotto un dubbio struttura dati più complessa di quanto ci saremmo visto nelle ultime settimane. Ci era stato l'utilizzo di matrici piuttosto felicemente come un utile se struttura dati semplicistico. Poi abbiamo introdotto questi, che naturalmente sono legati liste. E quale fu una delle motivazioni per l'introduzione di questa struttura dati? Sì? Che cos'è? 

AUDIENCE: Dimensione dinamica. 

DAVID MALAN: Dimensione dinamica. Quindi, mentre in array, si deve conoscerne la dimensione in anticipo quando si alloca esso. Nella lista collegata, non è necessario devono sapere che. Si può solo malloc, o più in generale, stanziare un ulteriore nodo, per così dire, ogni volta che si desidera inserire più dati. E il nodo non ha alcun significato predeterminato. E 'solo un termine generico che descrive una sorta di contenitore che siamo utilizzando nella nostra struttura dati per memorizzare qualche elemento di interesse, che in questo caso capita di essere numeri interi. 

Ma c'è sempre un compromesso. Così otteniamo dimensioni dinamiche dei dati struttura, ma che prezzo paghiamo? Qual è il lato negativo di liste collegate? Sì? 

AUDIENCE: richiede più memoria. 

DAVID MALAN: Si richiede di più memoria, come esattamente? 

AUDIENCE: [incomprensibile]. 

DAVID MALAN: Esattamente. Così ora abbiamo puntatori riprendendo memoria aggiuntiva che abbiamo precedentemente non aveva bisogno, perché il vantaggio di un array, naturalmente, è che tutto è contiguo, indietro to back to back, che ti dà accesso casuale. Perché semplicemente utilizzando parentesi quadra notazione, o più tecnicamente puntatore aritmetica, molto semplice addizione, si può accedere a qualsiasi elementi in tempo costante. E in effetti, questo è tipo di accennare a un altro prezzo che stiamo pagando con un lista collegata. 

Cosa succede al tempo di esecuzione di qualcosa di simile a Search, se voglio trovare qualche valore e dentro di una lista collegata? Che cosa fa il mio tempo di esecuzione diventi? Big O di n. Se si è ordinato al? Che cosa succede se la struttura dei dati è ordinato? Posso fare meglio di grande O di n per la ricerca? No, perché nel caso peggiore potrebbe benissimo essere ordinati, ma il numero stai cercando potrebbe essere grande. Potrebbe essere il numero 100, che potrebbe accadere di essere tutti il modo alla fine. E perché si può accedere solo un linked elenco in questa applicazione da parte via del suo primo nodo, sei ancora un po 'di fortuna. Devi attraversare il tutto dal primo all'ultimo, al fine di trovare che grande valore come 100. O per determinare se è nemmeno lì. 

Quindi non possiamo fare quello che l'algoritmo in un dato struttura che assomiglia a questo? Non possiamo fare ricerca binaria, perché ricerca binaria richieste che abbiamo avuto accesso casuale. Potremmo saltare da un luogo all'altro posizione senza dover seguire queste briciole di pane in forma di tutti questi puntatori. 

Ora, come abbiamo fatto a implementare questo? Beh, se andiamo alla schermata qui, se siamo in grado di implementare di nuovo rapidamente questi dati struttura - la mia scrittura non è tutto ciò che grande qui, ma ci proveremo. Così typedef struct, e cosa ho consiglia di chiamare questa cosa qui? Nodo. Così prendo iniziare. E ora, che cosa deve essere all'interno di la struttura dati per tale singolarmente lista collegata? Quanti campi? 

Quindi due. Uno è abbastanza facile. Quindi, int n. E potremmo chiamare n tutto ciò che vogliamo, ma dovrebbe essere un int se siamo l'attuazione di una lista collegata per int. E adesso cosa fa il secondo campo deve essere? Struct nodo *. Quindi se faccio struct nodo *, e poi ho può chiamare questo anche ciò che voglio, ma tanto per essere chiari chiamerò la prossima, come abbiamo fatto. E allora io chiudo parentesi graffe. 

E ora, come l'ultima volta, Ho messo nodo quaggiù. Ma se sto dichiarando questo è come un nodo, perché ho fastidio essere così verbose qui nel dichiarare struct nodo * prossimo, in contrapposizione al proprio nodo * prossimo? Sì? 

AUDIENCE: [incomprensibile]. 

DAVID MALAN: Esattamente. Esattamente. Poiché C si prende davvero letteralmente e vede solo la definizione del nodo fin qui, non è possibile fare riferimento ad esso qui. Quindi abbiamo questa sorta di prelazione dichiarazione qui, che è certamente più prolisso. Struct nodo, che significa ora possiamo accedervi all'interno della struttura dati. 

E per inciso, perché questo è diventando un po 'più soggettivo ora, la stella può tecnicamente andare qui, si può andare qui, si può anche andare nel mezzo. Abbiamo adottato, nel Manuale per il corso, la convenzione di mettere la stella a destra accanto ai dati tipo, che in questo caso, sarebbe nodo struct. Ma realizzare in un sacco di libri di testo e riferimenti on-line, si potrebbe infatti vedere sull'altro lato. Ma proprio conto che entrambi saranno effettivamente lavora e si dovrebbe semplicemente essere coerente. 

D'accordo. In modo che è stata la nostra dichiarazione del nodo struct. Ma poi abbiamo iniziato a fare di più cose sofisticate. Per esempio, abbiamo deciso di introdurre qualcosa di simile a una tabella hash. Così qui è una tabella hash di dimensione n, indicizzato da 0 in alto a sinistra per n meno 1 in basso a sinistra. Questo potrebbe essere un hash tavolo per qualsiasi cosa. Ma che tipo di cose abbiamo parlato su come utilizzare una tabella hash per? Memorizzazione di che cosa? 

Nomi. Potremmo fare nomi come abbiamo fatto l'ultima volta. E davvero, è possibile memorizzare qualsiasi cosa. E vedremo di nuovo in PHP e JavaScript. Una tabella hash è una bella specie di Svizzera Coltellino che consente di memorizzare praticamente tutto ciò che si desidera all'interno di esso da chiavi con valori associare. Tasti con i valori. 

Ora, in questo caso semplice, il nostro chiavi sono solo numeri. Stiamo implementando un hash tavolo come un array. E così le chiavi sono 0, 1, 2, e così via. E così noi, come esseri umani, abbiamo deciso all'ultimo settimana che si sa che cosa, se siamo andando a memorizzare nomi, diciamo solo arbitrariamente, ma piuttosto ragionevolmente, supporre che Alice, un Un nome, sarà solo essere indicizzati in 0. E Bob, un nome di B, sarà indicizzato in 1, e così via. Così abbiamo avuto un mapping tra gli ingressi, quali sono le stringhe, e l'hash luoghi, che sono i numeri. 

Modo che il processo è generalmente noto come una funzione di hash, e si può veramente recepirlo nel codice. Se avessi voluto implementare una funzione di hash che fa esattamente quello che abbiamo appena descritta dall'ultima volta, potrei dichiarare una funzione che prende, come Ingresso per esempio - e facciamolo su questo schermata qui. Se volessi realizzare un hash funzione, mi potrebbe dire qualcosa di simile a questo. 

E 'intenzione di restituire un int. E 'intenzione di essere chiamato hash, ed è intenzione di accettare come argomento un stringa, o possiamo essere più proprio ora, e di 'char *, che chiameremo s. E poi tutta questa funzione ha a che fare, in ultima analisi, è restituire un int. Ora, come lo fa, che potrebbe non essere così chiara. Ho intenzione di implementare questo senza alcun forma di controllo degli errori al momento. Sto solo andando a dire alla cieca, ritorno tutto ciò che è a s staffa 0, meno, diciamo, capitale Un punto e virgola. 

Totalmente rotto. Non è perfetto, perché uno, quello che se s è nullo? Brutte cose stanno per accadere. Due, quello che se la prima lettera in questo nome non è una lettera maiuscola? Che non sta andando a girare bene neanche. Potrebbe essere una lettera minuscola o no una lettera a tutti. Così totalmente margini di miglioramento qui, ma questa è l'idea di base. 

Ciò che abbiamo descritto la settimana scorsa verbalmente come solo un processo di mappatura di Alice 0 e Bob a 1 possono essere espressi certamente più formulaically come C funzionare qui. Chiamato di nuovo hash, prende una stringa come ingresso, e quindi in qualche modo fa qualcosa con tale ingresso per produrre un output. Non diversamente il nostro descrizione scatola nera che abbiamo fatto a lungo. Non so come questo potrebbe essere lavorando sotto la cappa. 

Per set problema 6, una delle sfide è per voi a decidere che cosa avrà la funzione di hash essere? Che cosa sta per essere all'interno di quello nero scatola, e presumibilmente, sarà un poco più interessante di questo, e decisamente più incline all'errore verifica di questo particolare attuazione. 

Ma possono sorgere problemi, giusto? Se abbiamo una struttura di dati come questo uno, quello che è uno dei problemi si può incorrere in corso del tempo, come si inserisce sempre più nomi nella tabella di hash? È possibile ottenere le collisioni, giusto? Che cosa succede se si dispone di Alice e Aronne, due persone i cui nomi successo iniziare con un? Che pone la domanda, in cui si mettere il secondo ad un nome? 

Beh, si potrebbe ingenuamente basta metterlo dove Bob appartiene, ma poi Bob è tipo di vite, se si tenta di inserire il suo nome accanto e non c'è spazio per lui. Così si potrebbe mettere Bob dove Charlie, e si può immaginare questo molto rapidamente devolvendo in un po 'di confusione. Qualcosa lineare, alla fine, in cui si basta cercare il tutto alla ricerca di Alice o Bob o Aaron o Charlie. 

Così invece abbiamo proposto, invece di linearmente sondaggio per spazi aperti e plopping i nomi, ci siamo proposto un approccio più elaborato. Una tabella hash implementato ancora con un serie di indici, ma il tipo di dati di tali indici ora sono puntatori. Puntatori a che cosa? Puntatori a liste collegate. 

Perché ricordo che una lista concatenata è in realtà solo un puntatore a un nodo, e il nodo ha un campo vicino, e tale nodo ha un campo successivo, e così via. Così ora è possibile pensare a questa matrice su il lato sinistro di una tabella hash come portando a una lista collegata. Il vantaggio di cui è se si ottiene un collisione tra Alice e Aronne, cosa fare con il secondo tale persona? È lui solo collegare o lei al end, o anche l'inizio di quella lista collegata. 

E in realtà, diciamo solo tagliatella attraverso che solo per un secondo. Dove renderebbe più senso? Se inserisco Alice e lei finisce a la prima posizione, poi cerco di inserire il nome di Aaron, e non c'è ovviamente una collisione, devo mettere lui all'inizio della lista collegata? Che è in primo luogo che, o alla fine? 

AUDIENCE: [incomprensibile]. 

DAVID MALAN: OK. Ho sentito all'inizio. Perché all'inizio? 

AUDIENCE: [incomprensibile]. 

DAVID MALAN: OK. E 'alfabetico, in modo che è bello. Questo è un buon albergo. Mi farà risparmiare un po 'di tempo potenzialmente. Non mi permette di fare la ricerca binaria, ma io potrebbe almeno essere in grado di uscire di un ciclo se mi rendo conto, beh, io sono via passato erano Aaron sarebbe in questo ordinati lista collegata. Io non devo sprecare il mio tempo alla ricerca fino alla fine. Ecco, questo è ragionevole. Perché altrimenti si potrebbe desiderare di inserire il nome collisione al inizio della lista? Che cos'è? 

AUDIENCE: [incomprensibile]. 

DAVID MALAN: Si potrebbe richiedere molto tempo per arrivare alla fine della lista. E infatti, più a lungo e più a lungo. Gli altri nomi che si inserisce Inizia con una, la più lunga che catena sta per arrivare. Quanto più a lungo che collegava lista sta per arrivare. Quindi sei davvero solo sprecare il vostro tempo. Forse è meglio mantenere tempo di inserzione costante, O grande di 1, da sempre mettendo il nome di collisione in l'inizio della lista collegata, e non preoccuparsi tanto sull'ordinamento. 

Qual è la migliore risposta? Non è chiaro. E 'sorta di dipende da ciò che il distribuzione è, ciò che il modello è dei nomi che si sta inserendo. Non è necessariamente una risposta ovvia. Ma qui per, ancora una volta, è un'opportunità disegno. 

Così abbiamo poi guardato questa cosa, che è davvero l'altra grande opportunità per p-set 6. E realizzare, se non l'hai già fatto, Immersioni Zamyla in entrambi questi, hash tavoli e cerca, più in dettaglio. E il video walkthrough è incorporato in p-set spec. Questo è stato un trie - T-R-I-E. E che cosa era interessante questo era un tempo di rotazione di ricerca di un nome, come Maxwell ultima volta, era grande O di che cosa? Che cos'è? 

PUBBLICO: Il numero di lettere. 

DAVID MALAN: numero di lettere. Ho sentito due cose. Numero di lettere e di tempo costante. Allora andiamo con quella prima. Il numero di lettere. Beh, questa struttura di dati, richiamo, è Come un albero, un albero genealogico, ciascuno dei i cui nodi sono costituiti da matrici. E questi array sono puntatori a altri tali nodi, o altri tali array nella struttura. 

Quindi se volessimo quindi determinare se Maxwell è qui, potrei andare alla prima matrice, al vertice di l'albero, la cosiddetta radice, cima trie, e quindi seguire il puntatore m, poi l'un puntatore, allora x, w, e, l, l. E poi quando vedo qualche simbolo speciale, indicata qui come un triangolo. Nel codice vedrete Vi proponiamo di implementato come un bool, basta dire sì o no, una parola si ferma qui. 

Bene, una volta che siamo andati a M-A-X-W-E-L-L, si sente come sette, forse otto se andiamo un passato, otto procedura per trovare Maxwell. O chiamiamolo K. non ricordare scorso tempo, ho sostenuto che se c'è realisticamente una lunghezza massima su un parola, come i personaggi 40-qualche-dispari, un massima lunghezza implica un valore costante. Quindi, in realtà, sì, è tecnicamente grande O di 8 o 7, o davvero grande O di K. Ma se c'è un limite finito su ciò K potrebbe essere, è una costante. E così è grande O di 1 a Alla fine della giornata. 

Non nel mondo reale. Non quando in realtà inizia a guardare il vostro orologio da corsa del vostro programma. E 'assolutamente intenzione di essere un po' lento di veramente costante tempo con un solo passaggio. Sta andando essere sette o otto gradini, ma questo è molto, molto meglio di un algoritmo simile grande O di n che dipende dalle dimensioni di ciò che è nel struttura dati. 

Notate la testa qui è che possiamo inserire un milione di nomi in questa struttura dei dati, ma quanti più passaggi sta andando a prendere noi per trovare Maxwell in quel caso? Nessuna. Lui è inalterato. E fino ad oggi, non credo che abbiamo visto un esempio di una struttura di dati o un algoritmo che è stato completamente influenzato da esterno comportamenti del genere. Ma questo non può essere sorprendente. Questo non può essere l'unica soluzione per il p-set 

E non è. Questo non è necessariamente i dati struttura che dovrebbe gravitare verso, perché come tabelle hash, compromesso. Qual è il prezzo che si paga qui? Memoria. Voglio dire, questo è un atroce quantità di memoria. E non riesco a vedere qui perché l'autore di questa immagine ovviamente troncata tutti gli array, e non stiamo vedendo un sacco di A e B e C e Q e Y del e le Z in questi array. Ma sono lì. 

Ciascuno di questi nodi è un'intera matrice di circa 26 o più byte, ciascuno dei che rappresenta una lettera. 27 nel nostro caso, in modo da poter sostenere apostrofi del problema proposto. Quindi, questa struttura dati è davvero, molto denso e largo. E che da solo potrebbe finire per rallentare le cose, o almeno costare un molto più spazio. Ma ancora una volta, possiamo trarre comparazioni qui. 

Ricordiamo un po 'indietro, abbiamo ottenuto molto più emozionante tempo di esecuzione in ordinamento quando usiamo merge sort, ma il prezzo abbiamo pagato per ottenere n log n per merge sorta richiesto che spendiamo più che cosa risorsa? Più spazio. Avevamo bisogno di una serie secondaria di copiare la gente in, proprio come abbiamo fatto qui sul palco. Quindi, di nuovo, senza chiari vincitori, ma proprio disegno soggettivo decisioni da prendere. 

D'accordo. Così come su questo? Chiunque riconosce che D-Hall? OK. Così tre di noi fanno. Mather House. Quindi questo è per il pranzo di Mather. Scommetto tutte le sale da pranzo hanno pile di vassoi come questo. E questo è in realtà rappresentativo di qualcosa che abbiamo ovviamente visto già. Lo abbiamo chiamato letteralmente una pila. E la pila, in termini di vostro memoria del computer, è dove i dati vanno mentre le funzioni sono chiamati. 

Per esempio, che tipo di cose vanno sulla pila rispetto alla layout di memoria che abbiamo discusso nelle ultime settimane? Che cos'è? 

AUDIENCE: chiamate a funzioni. 

DAVID MALAN: Mi dispiace. 

AUDIENCE: chiamate a funzioni. 

DAVID MALAN: Le chiamate a funzioni, ma In particolare, ciò che è dentro di ognuno di quei fotogrammi? Che tipo di cose? Già. Quindi, le variabili locali. Ogni volta che avevamo bisogno di un po 'di memoria locale, come un argomento, o INT o int temp, o qualunque sia il locale variabile è, siamo stati mettendo che in pila. E noi lo chiamiamo una pila perché di quell'idea stratificazione. Solo tipo di match up con la realtà, il concetto della stessa. 

Ma si scopre che una pila può anche essere visto come una struttura dati, un alternativa ad un array, in alternativa ad un elenco collegato. Qualcosa di concettualmente più interessante che può ancora essere implementato utilizzando uno di questi le cose, ma è un diverso tipo di struttura dati di supporto, in realtà, solo due operazioni. Ma si può aggiungere su amatore caratteristiche di questi. Ma queste sono le basi - inserire ed estrarre. 

E l'idea con uno stack è che se io sono qui, con o senza Annenberg sapendo, un vassoio della porta accanto con il numero 9 su esso. Quindi, solo un int. E voglio spingere questo sui dati struttura, che attualmente è vuoto. Considerate questo il fondo della pila. Vorrei spingere questo numero 9 sulla Catasta, e ora è proprio lì. 

Ma la cosa interessante di una pila è che se ora voglio spingere qualche altro valore, come il 17, e mi spingo presente nello stack, ho intenzione di fare l'unica cosa intuitiva, sto solo andando per dirla proprio dove noi umani sarebbe propenso a metterlo, in cima. Ma ciò che è interessante ora è, come faccio ad avere alle 9? Sai, io non senza qualche sforzo. 

Quindi cosa c'è di interessante uno stack è che dal disegno, si tratta di una struttura dati LIFO. Modo stupido di descrivere last in, first out. Così l'ultimo numero in in questo momento era 17. Quindi, se voglio qualcosa di pop off della pila, può essere solo 17. Quindi c'è un ordine obbligatorio di operazioni qui, dove l'ultimo elemento in deve essere il primo ad uscire. Da qui l'acronimo, LIFO. 

Allora, perché questo potrebbe essere utile? Sono i loro contesti in cui faresti vuole una struttura dati come questo? Beh, è ​​sicuramente stato utile all'interno di un computer. Sistemi operativi in ​​modo da utilizzare in modo chiaro questo tipo di struttura dati per le pile. Vedremo anche la stessa idea quando si tratta di pagine web. Così questa settimana e la prossima settimana e oltre, e come si inizia l'implementazione web pagine in un linguaggio chiamato HTML, è possibile effettivamente utilizzare una struttura dati simile questo per determinare se la pagina è formattato correttamente. Perché vedremo tutte le pagine web seguono una sorta di gerarchia, una rientranza che, al termine della giornata, essere un struttura ad albero sotto la cappa. Quindi, più che in appena un po '. 

Ma per ora, cerchiamo di proporre un momento, come potremmo fare per rappresentando ciò che una pila è? Lasciatemi propongo implementiamo una pila con codice come questo. Così una pila sta per avere all'interno di esso due cose, un array, chiamati vassoi, tanto per essere coerente con la demo. E ciascuna delle voci che la matrice sta per essere un tipo int. E la capacità è probabilmente quello che? Perché io non ho scritto la definizione completa qui. 

E 'probabilmente il massimo dimensione della matrice. E probabilmente è dichiarato come un forte definire all'inizio del file, alcuni sorta di costante implicita la mera capitalizzazione. Così da qualche capacità è definita come la dimensione massima possibile. Nel frattempo, all'interno della struttura dei dati noto come stack ci sarà essere un numero intero appena conosciuta semplicemente come dimensione. 

Quindi, se dovessi rappresentare questa società pittoricamente, supponiamo che questo tutta la scatola nera rappresenta il mio stack. All'interno di esso è due variabili. Quindi ho intenzione di disegnare il primo come dimensione. E il secondo vado a disegnare come un array. 

Ma solo per mantenere le cose ordinate, normalmente vorrei richiamare un array come questo, ma è una specie di bella se abbiniamo la realtà, o corrispondere al modello mentale. Così mi permetta invece disegnare la matrice verticalmente, che è proprio, di nuovo, interpretazione dell'artista. Non importa quello che è sotto il cofano. E diremo che, per impostazione predefinita, capacità sta per essere tre. Quindi questo sarà posizione 0, questo sarà location 1, questa sarà in posizione 2. 

Se io corrompere con una palla di stress, sarebbe qualcuno piace venire ed eseguire il bordo qui solo per un momento? OK, ha visto prima la tua mano. Andiamo su. D'accordo. Quindi credo che sia Steven. Andiamo su. D'accordo. 

Ma supponiamo ora ci Rewind a quella iniziale stato del mondo in cui mi hanno appena dichiarato una pila, ed è andando ad essere di capacità tre. Ma taglia non è ancora stata determinata. Vassoi non è ancora stata determinata. Così un paio di domande prima. E permettetemi di darvi microfono in modo da poter partecipare più attivamente a questo. 

Quindi, ciò che è dentro di dimensioni in questo momento nel tempo se tutto quello che ho fatto è dichiarato una pila con una riga di codice? 

STEVEN: Non molto. 

DAVID MALAN: OK, non molto. Sappiamo che cosa c'è dentro di dimensioni, facciamo a sapere cosa c'è dentro di questa matrice qui? 

STEVEN: codice Proprio casuale, giusto? Just - 

DAVID MALAN: Sì, ho intenzione di chiamarlo codice, ma casuale - 

STEVEN: Le cose. 

DAVID MALAN: Cose come casuale 

STEVEN: Bit. 

DAVID MALAN: Bit, giusto? Quindi i valori di immondizia, giusto? Così permutazioni di 0 e di 1. Resti di usi precedenti di questa memoria. E noi non sappiamo veramente quali sono i valori stiamo, quindi abbiamo in genere li disegniamo come punti interrogativi. 

Quindi la prima cosa che siamo presumibilmente intenzione di voler fare qui - e lasciatemi fare questo campo all'interno di là di un nome - vassoi. Cosa dovremmo presumibilmente inizializzare dimensioni per se vogliamo iniziare a utilizzare questo stack? 

STEVEN: Tray è sub 3. 

DAVID MALAN: Quindi, OK. Per essere chiari, la capacità viene dichiarato altrove come tre. Ed è quello che ho usato per allocare l'array. Dimensione sta per fare riferimento a quanti vassoi sono attualmente in pila. 

STEVEN: Zero. 

DAVID MALAN: Quindi dovrebbe essere pari a zero. Quindi, andare avanti, e con un dito, disegnare uno zero nel formato. D'accordo. Così ora, quello che c'è dentro di questa qui, non lo sappiamo. Questi sono in realtà solo i valori della spazzatura. Così potremmo disegnare punti interrogativi, ma cerchiamo di mantenere la tavola pulita per ora perché non importa cosa c'è. Non abbiamo bisogno di inizializzare l'array a nulla, perché se sappiamo che la dimensione dello stack è zero, bene, abbiamo non dovrebbe essere guardando qualcosa nel questa matrice in ogni caso a questo punto nel tempo. 

Così ora immagino che premo il numero 9 in cima alla pila. Come dovremmo aggiornare la struttura dei dati all'interno di questa scatola nera? Quali valori bisogno di cambiare? 

STEVEN: Within - le dimensioni? 

DAVID MALAN: OK. Dimensione dovrebbe diventare cosa? 

STEVEN: Dimensione sarebbe uno. 

DAVID MALAN: OK. Così dimensione dovrebbe diventarlo. Così si può fare questo in un paio di modi. Permettetemi di fare, ora il tuo dito è una gomma. D'accordo. Quindi ora il dito è un pennello. D'accordo. E ora che altro deve cambiare, ovviamente, nella struttura dati? 

STEVEN: Stiamo andando da basso fino a 9. 

DAVID MALAN: 9. OK, Good. Quindi ancora non importa ciò che è in posizione uno o due perché sono valori della spazzatura, ma non dovrebbero preoccuparsi guardando lì perché la dimensione è che ci dice che solo il primo elemento in realtà è legittima. Così ora mi spingo 17 sulla lista. Che cosa succede a questa immagine? 

STEVEN: Così dimensioni sta per andare in due. 

DAVID MALAN: OK. Sei gomma - oops. Sei una gomma. 

STEVEN: Eraser. 

DAVID MALAN: Sei un pennello. 

STEVEN: Brush. 

DAVID MALAN: OK. E che altro? 

STEVEN: E poi - 

DAVID MALAN: abbiamo spinto 17. 

STEVEN: Attacchiamo 17 sulla parte superiore, in modo - 

DAVID MALAN: OK, bene. 

STEVEN: - cadere giù. 

DAVID MALAN: Va bene. E 'sempre facile. Non ho intenzione di aiutarvi a questo momento. Spingere 22. 

STEVEN: Fatto. Diventare una gomma. Sto diventando un pennello. E poi sto mettendo 22. 

DAVID MALAN: 22. Eccellente. Quindi, ancora una volta. Ora sto andando a spingere sulla pila 26. 

STEVEN: Ooh. Oh Gosh. Davvero mi ha colto alla sprovvista. 

DAVID MALAN: Non l'hai fatto vedere il prossimo? 

STEVEN: Non ho visto questa venuta. Potremmo capacità di ri-iniziale? 

DAVID MALAN: Questa è una buona domanda. Così abbiamo sorta di dipinto noi stessi in un angolo qui. Non c'è davvero nulla di buono per Steven perché abbiamo assegnato questo array staticamente, per così dire, all'interno della struttura dati. E abbiamo essenzialmente rigido codificato rendere della dimensione tre. Quindi non possiamo davvero riallocare esso. 

Potremmo, se siamo tornati, abbiamo ridefiniti i vassoi di essere un puntatore che Abbiamo quindi utilizzare malloc alla memoria a mano a. Perché se abbiamo ottenuto la memoria da il mucchio tramite malloc, abbiamo potrebbe poi liberarlo. Ma prima di liberarla, abbiamo potuto riallocare un pezzo più grande di memoria, aggiornare il puntatore, e così via. Ma per ora, questo è davvero Il meglio che possiamo fare. Spingere e pop sono presumibilmente andando di avere a segnalare qualche errore. 

Così, per esempio, la nostra implementazione di spinta potrebbe restituire un bool che precedentemente restituito vero, vero, vero. Ma la quarta volta, sta andando ad avere per restituire false, per esempio. D'accordo. Molto ben fatto. Congratulazioni. Ti sei guadagnato la tua palla antistress oggi. 

[Applausi] 

STEVEN: Grazie. 

DAVID MALAN: Grazie. OK, quindi questo sembra essere non molto di un passo in avanti, giusto? Abbiamo descritto questa struttura dati. E 'stato interessante, no? Sistemi operativi piace. A quanto pare il web può fare uso di questa, e altre applicazioni ancora. Ma che stupida limitazione che siamo back to sorta di settimana due limiti dove abbiamo fissato array dimensioni. 

Quindi, ci sono infatti un paio di modi potremmo risolvere questo. Potremmo allocare dinamicamente la matrice, non da codificare come ho fatto qui, ma invece ri-dichiarando questo, tanto per essere chiari, come qualcosa di simile a questo. Int * vassoi, non decidere su ancora una capacità. Ma quando dichiaro la pila altrove nel mio codice, ho potuto quindi chiamare malloc, ottenere l'indirizzo di un pezzo di memoria, e potrei assegnare che l'indirizzo di vassoi. 

E poi, perché è solo un pezzo di memoria, ho potuto continuare a utilizzare piazza notazione parentesi nel solito modo. Perché ancora una volta, c'è una sorta di presente equivalente funzionale di array e blocchi di memoria che vengono di ritorno da malloc. Possiamo trattare uno come l'altra utilizzando l'aritmetica dei puntatori o piazza notazione staffa. Ecco, questo è un approccio. 

Ma altrimenti come potremmo realizzare questo stessa struttura dati, potenzialmente? Giusto? Mi sento come abbiamo appena risolto questo problema come una settimana fa. Qual è stata la soluzione a questo problema che Steven ha incontrato? Liste collegate Così, giusto. 

Se il problema è che stiamo dipingendo noi stessi in un angolo assegnando in anticipo troppo poca memoria che abbiamo poi avere a che fare in qualche modo con, bene, perché non solo evitare che rilasciare del tutto? Perché non dichiarano i vassoi per essere un puntatore a un nodo, ergo una lista concatenata, e poi semplicemente allocare nuovi nodi ogni volta Steven necessario misura un numero nella struttura dati. 

Quindi l'immagine dovrebbe cambiare. Non sta andando essere il più pulito e come semplice come un array di tre interi. Ora si sta andando ad essere un puntatore ad una struct, e che la struttura sta per avere un int e un indicatore accanto. E 'intenzione di portare via quel puntatore ad un altro tale struttura per un altro esempio struct. Quindi, l'immagine sarebbe in realtà ottenere un po 'incasinato. E avremmo frecce legando tutto insieme. 

Ma va bene, giusto, perché abbiamo visto come fare questo. E una volta che si ottiene confortevole attuare qualcosa di simile a una linked lista, che dovrete fare se scegliere di implementare una tabella hash con concatenazioni separate per p-set di 6, è possibile usarlo come un blocco di costruzione, o di un ingrediente, o in Scratch dire, un procedura, qualcosa che si mette, si creato il proprio pezzo di puzzle che si può riutilizzare. Compromessi così, ma le possibili soluzioni che abbiamo effettivamente visto prima. 

Quindi, molto spesso, si vede questo ogni anno o due, quando Apple rilascia qualcosa di nuovo, e tutti i matti line up al di fuori del Mela negozio per comprare il loro marginale aggiornare l'hardware. Dico questo, va bene, perché Io sono una di quelle persone. Quindi, che tipo di struttura dati potrebbe rappresentare questa realtà? 

Beh, chiamiamola una coda, una linea. So British chiamerebbe in genere una coda in ogni caso, quindi è un bel nome. E le due operazioni che una coda sostiene che chiameremo un enqueue funzionamento e una operazione dequeue, quali sono simili a spirito di spingere e pop. E 'solo una sorta di diversa convenzione, quello che stiamo chiamando questi. Ma per accodare qualcosa significa aggiungere o inserirlo alla struttura di dati. Per annullare l'accodamento significa per rimuoverlo. Ma mentre una pila era dati LIFO struttura, una coda è una prima in, first out struttura dati. 

Se è la prima persona in linea, sarai la prima persona a ottenere fuori linea e comprare il vostro nuovo dispositivo. Immaginate come sconvolto queste persone sarebbero se Apple invece utilizzato uno stack, per esempio, di attuare la raccolta up del vostro nuovo giocattolo. Quindi, le code hanno senso, certamente, e siamo in grado di pensare a tutti i tipi di applicazioni, presumibilmente, per le code, soprattutto quando si vuole equità. Così come potremmo implementare questi come struttura di dati? 

Ebbene, propongo che potremmo bisogno di farlo in questo modo. Quindi ho intenzione di ora hanno i numeri. Quindi dovremo fare cose semplici e non necessariamente parlare in termini di vassoi. Solo numeri che le persone di ottenuti. Capacità sta andando, ancora una volta, fissare il numero totale di persone che possono essere in questa linea, come tre o qualunque altro valore. 

Ma io propongo che ho bisogno di tenere traccia non solo delle dimensioni del coda, quante cose sono in esso. Quindi, la dimensione è la dimensione corrente, la capacità è la dimensione massima. Proprio di nuovo, nomenclatura per convenzione. Perché ho bisogno di un int aggiuntivo all'interno di una coda per tenere traccia di chi è dentro davanti alla linea? Perché ho bisogno di farlo in questo caso? 

Beh, come è questa immagine andando a cambiare? Probabilmente può riutilizzare più di questa immagine. Lasciami andare avanti e cancellare quello che c'è qui. Daremo questo un po ' Nome quassù diverso. Liberiamoci del 17 Liberiamoci del 9, liberiamoci del 3. E andiamo ad aggiungere un'altra cosa. Propongo che ho bisogno di tenere traccia di la parte anteriore della lista, che è solo andando essere un int pure. E abbiamo intenzione di mantenere le cose semplici. Nessun lista collegata per ora. 

Ci ammettere che stiamo andando a urtare contro questo limite. Ma quello che voglio vedere succederà questa volta? Quindi suppongo io vado avanti e il primo persona viene in su in linea, e è il numero 9. Noi abbiamo le palle stress. Posso rubare, diciamo, due o tre persone? Uno, due, tre? Andiamo su. Destra dalla parte anteriore, perché faremo questo rapido. 

Ognuno di voi è ora sta per essere un ragazzo fan in fila alla Apple. Non riceverete hardware Apple al termine di questo però. D'accordo. Quindi sei il numero 9, si è numero 17, numero 22. Questi sono numeri arbitrari, come studente gli ID o roba del genere. E in un attimo, cominciamo per iniziare ad aggiungere le cose. E io corro il consiglio qui questa volta. 

Quindi, in questo caso, ho inizializzato il fronte di essere - Io in realtà non mi interessa quello che la anteriore è, perché la dimensione è zero. Quindi questo potrebbe anche solo essere un punto di domanda. Questi sono tutti punti interrogativi. Così ora inizieremo a vedere in realtà un po 'di persone in fila al negozio. 

Quindi, se il numero 9, che sei il primo lì a 5:00, andare avanti e allineare, o la sera prima. OK. Così ora 9 è qui. 9 è così in testa alla lista. Quindi ho intenzione di andare avanti e di aggiornare la dimensione di questi dati correnti struttura per non essere più 0, ma per essere 1. Ho intenzione di mettere 9 al anteriore della lista. Lasciami andare avanti e di attivare o disattivare la schermata così possiamo vedere davanti a noi qui. 

E ora che cosa voglio di mettere a fronte? Ho intenzione di tenere traccia che l' anteriore della coda in questo momento è in posizione 0. Perché quello che sta accanto sta per accadere? Beh, immagino che ora mi Enqueue 17 pure. Così hop in linea lì. E ancora, il tipo di porta per la negozio sta per essere qui. Così ora ho aggiunto 17. E anche se questi ragazzi stanno bloccando lo schermo, che è OK, perché possiamo vederlo da qui. Mi dispiace. 

AUDIENCE: Siamo in grado di muoversi - 

DAVID MALAN: No, va bene così. È enorme lassù. Quindi 17 è ora all'interno della coda. Ho bisogno di aggiornare i quali campi ora però? OK, sicuramente dimensioni. E che dire di fronte? OK, no. Anteriore non dovrebbe cambiare, perché a differenza di una pila, abbiamo vogliono mantenere l'equità. Quindi se 9 è venuto in primo luogo, vogliamo 9 di essere il primo fuori dalla linea e in negozio. 

In effetti, vediamo che. Prima inseriamo 22, diamo andare avanti e dequeue 9. Qual è il tuo nome? 

AUDIENCE: Jake. 

DAVID MALAN: Jake sta andando essere rimosse dalla coda ora. Così si arriva a piedi in negozio. E far finta che il negozio è finita lì. Così ora che cosa ha bisogno - dit-dit-dit! Cosa deve accadere ora? Decisione di progettazione. Quindi non è un cattivo istinto, ma - qual è il tuo nome? 

AUDIENCE: David. 

DAVID MALAN: David. Così che cosa fece Davide? Stava cercando di ordinare di fissare i dati struttura e mossa dalla sua posizione in primo luogo di Jake. E va bene, se siamo disposti di accettare che come un dettaglio di implementazione. Ma in primo luogo, cerchiamo di aggiornare i dati struttura prima di farlo. Perché non mi piaceva l'idea di tutti le persone spostando in questa linea. 

Non è un grosso problema se Davide lo fa con un passo, ma ancora una volta, ripensare a quando abbiamo avuto otto volontari sul palco e abbiamo fatto come l'inserimento sorta, dove abbiamo dovuto cominciare spostare tutti intorno. Che ha ottenuto costoso, giusto? Questo mi fa rabbrividire di grande O di N, O grande di n al quadrato di nuovo. E 'non sentirsi come un risultato ideale. 

Così facciamo solo aggiornare questo. Quindi la dimensione della coda non è più 2. Ora è semplicemente 1. Ma ora posso aggiornare qualcosa Non è stato aggiornato in precedenza, la anteriore della lista. Potrei solo dire, è che posizione 1? Così ora abbiamo valore spazzatura qui, valore spazzatura qui, e David nel mezzo di questa spazzatura. Ma la struttura di dati è ancora intatta. 

E in effetti, non ho nemmeno bisogno di cambiare ex numero di Jake 9, perché chi se ne frega. Non ho abbastanza informazioni ora in dimensione che so c'è una persona in questa coda. E so che quella persona è in posizione 1, non 0. Non sto contando. Così pure 1. Quindi la struttura di dati è ancora OK. 

Ebbene, che cosa succede dopo? Enqueue Facciamo - come ti chiami? 

AUDIENCE: Callen. 

DAVID MALAN: Callen. Facciamo enqueue un Callen, e 22 è ora nella coda. Così ora che cosa deve cambiare qui? Anteriore non ha intenzione di cambiare, ovviamente. Dimensione sta per cambiare per essere di nuovo 2. E 22 finisce qui, 9 è ancora presente, ma è efficace un valore spazzatura adesso. E 'solo un residuo di Jake passato. 

Così ora che cosa succede se Ho Dequeue David? Un'ultima operazione, dequeue David. Potremmo spostare, ma propongo ti permette di fare il meno lavoro possibile. Ora la mia struttura dati va eseguire nel formato da 2 a 1. Ma la parte anteriore della coda ora diventa 2. Non ho bisogno di cambiare questi numeri appena ancora, perché sono solo i valori della spazzatura. 

Ma ora che cosa succede? Supponiamo che io enqueue me stesso, 26? Mi sento come se io appartengo qui. Quindi sono stati accodati. Così ho sorta di appartengo a questo posto. E anche se lo fai non abbastanza apprezzare questo visivamente sul palcoscenico, perché abbiamo un sacco di spazio, dovrei non essere in piedi qui, perché? 

PUBBLICO: Sei fuori dai limiti. 

DAVID MALAN: Giusto. Io sono fuori dai limiti. Ho indicizzati al di là del limiti di questo array. Mi dovrebbe essere in uno dei tre possibili posizioni. Ora, dove c'è di più naturale di andare? Propongo di leveraged una settimana un trucco. L'operatore mod, percentuale. Perché io sono tecnicamente in piedi al posizione 3, ma mi fanno 3 Capacità di mod, così 3, un segno di percentuale, 3 - capacità è 3. Che cos'è? Qual è il resto quando si divide 3 da 3? 0. 

In modo che mi mette fosse Jake era, che in realtà è buono. Così ora l'attuazione di questa cosa sta andando a essere un po 'di mal di testa. E 'davvero solo una riga della cefalea, del codice. Ma almeno adesso c'è immondizia valore qui, ma ci sono due int legittimi qui. E io sostengo che ora abbiamo fatto esattamente quello che dobbiamo fare, purché cambiamo quello che Jake valore doveva essere 26. 

Ora abbiamo abbastanza informazioni ancora per mantenere l'integrità di questa struttura dati. Siamo ancora un po 'di fortuna, quando abbiamo desidera inserire quattro o più totale elementi, ma posso almeno fare abbastanza uso efficiente di questa costante tempo, infatti. Io non devo preoccuparmi di spostamento tutti, come l'inclinazione di David era. 

Tutte le domande su pile, o questa coda? 

PUBBLICO: E 'la ragione per la quale avete bisogno del formato in modo da sapere dove per avere una persona? 

DAVID MALAN: Esattamente. Ho bisogno di sapere la dimensione della matrice perché ho bisogno di sapere esattamente come molti di questi valori sono legittimi, e in modo che possa trovare dove mettere la prossima persona. Esattamente. La dimensione è - in realtà, non abbiamo ancora aggiorniamo questo. Io ho aggiunto a 26. La dimensione è ora, non 1, ma 2. Così ora questo davvero mi aiuta a trovare il capo della lista, che non è 0, non 1, ma è 2. La parte anteriore della lista è infatti il ​​numero 22. Perché lui è venuto in primo luogo, così egli dovrebbe essere consentito in negozio prima di me, anche se visivamente sto in piedi più vicino al negozio. 

D'accordo? Un applauso a questi ragazzi e noi li lasciamo fuori di lì. 

[Applausi] 

DAVID MALAN: potrei lasciare si mantiene il cassetto. Abbiamo potuto vedere che cosa succede se si vuole, ma forse no. D'accordo. Così che ora a che punto siamo? Bene, lasciate che propongo che ci sia un alcune strutture di altri dati che potremmo iniziare ad aggiungere al nostro kit di strumenti che saranno effettivamente essere molto, molto rilevante come ci immergiamo in roba web. Che ancora una volta, ha un qualche tipo di collegamento per alberi sotto forma di qualcosa chiamato DOM, documento modello a oggetti. Ma vedremo più di che tra non molto. 

Lasciatemi Propongo definitionally che abbiamo chiamare albero ora quello che si potrebbe sapere come più di un albero genealogico, in cui si avere qualche antenato al radici dell'albero. Una matriarca patriarcale o presso la cima dell'albero. Senza il loro coniuge, in questo caso. Ma ora abbiamo quello che chiameremo bambini, che sono i nodi che pendono fuori il figlio sinistro o il bambino a destra, frecce, come raffigurato qui. 

In altre parole, in una struttura di dati ad albero in informatica, un albero è pari a zero o più nodi. Se ha almeno un nodo, che chiama la radice. Sono le cose visivamente che ci avviciniamo al top. E questo nodo, come qualsiasi altro nodo, può avere zero, uno, o due, o tre, o comunque molti bambini la struttura di dati supporta. In questo caso, la radice, la memorizzazione valore di uno, ha due figli, 2 e 3, così noi generalmente chiamiamo 2 sinistra bambino e 3 il bambino giusto. 

E poi, quando ci mettiamo a 5, 6, e 7, 6 potrebbe essere chiamato il figlio di mezzo. Se si dispone di quattro figli, esso si confonde. Quindi smettiamo di usare quel tipo di scelta rapida verbalmente. Ma è davvero solo un albero genealogico. E le foglie qui sono i nodi che si hanno figli. Sono appesi fuori la parte inferiore della struttura. 

Così come potremmo implementare un albero che ha solo due figli al massimo? Lo chiameremo un albero binario. Bi nuovo significato a due, in questo caso, come con binario. E così si può avere zero, uno, o al massimo due bambini. 

Io propongo di attuare il nodo per quella struttura con un int n, e poi due puntatori, uno chiamato a sinistra, uno chiamato destra. Ma questi sono solo belle convenzioni arbitrarie. E cosa c'è di bello oggi, soprattutto se si genere di lottato concettualmente con ricorsione, o pensato che non fosse davvero una soluzione a nulla, soprattutto se si potesse esaurito la memoria. Ora che stiamo parlando di dati strutture e algoritmi che consentono noi di attraversare e di manipolarle, Risulta che la ricorsione torna in una molto più convincente se non bellissimo modo. 

Quindi questo vi propongo è l'attuazione di una funzione di ricerca. Dati due ingressi - quindi pensare a questo come una scatola nera. Dati due ingressi, n, int, e un puntatore a un albero, un puntatore ad una nodo, o realmente la radice di un albero, mi affermazione che questa funzione può restituire vero o falso, che il valore di n è all'interno di questo albero. 

Che cosa è all'interno di questa scatola nera? Beh, quattro rami. Il primo solo assegni. Se albero è nullo, solo restituire false. Se non c'è nodo, non c'è n, non c'è nessun numero, solo restituiscono false. Se, però, n, il valore che stai cercando per, è inferiore albero freccia n, e tanto per essere chiari, che cosa significa quando Scrivo albero e poi la freccia notazione, n? Esattamente. Significa che dereferenziare puntatore chiamato albero. Vai lì, e poi entrare di che nodo e ottenere il suo campo chiamato n. E quindi confrontare il n effettivo che era passato nella ricerca contro di essa. 

Quindi se n è inferiore, il valore n nel nodo della struttura stessa, bene, che cosa vuol dire? Ciò significa nulla a prima vista. Giusto? Proprio come quando si dispone di una serie di valori, come si potrebbe applicare binario cercare come una forma di divisione e conquistare. Ma quello presupposto abbiamo bisogno di fare per la ricerca binaria funzioni tutto nella rubrica e esempi precedenti? 

Come da ordinare. Quindi cerchiamo di perfezionare la definizione di albero qui di non essere solo un albero, che può avere qualsiasi numero di bambini. Non solo un albero binario, che può avere 0, 1 o 2 al massimo. Ma come un albero binario di ricerca, o BST, che è solo un modo elegante per dire un albero binario tale che ogni nodo figlio sinistro, se presente, è meno del nodo. E figlio destro di ogni nodo, se presente, è maggiore rispetto al nodo stesso. 

Quindi, in altre parole, se si dovesse disegnare l'albero fuori, tutti i numeri sono accuratamente equilibrato come questo in modo che se avete 55 come la radice, il 33 può andare alla sua sinistra, perché è meno di 55. 77 può andare alla sua destra perché è maggiore di 55. Ma ora notare, la stessa definizione, si tratta di una definizione ricorsiva verbalmente, deve applicare per 33. 33 del bambino di sinistra deve essere minore di esso, e il figlio destro di 33, 44, deve essere grande di esso. 

Quindi questo è un albero binario di ricerca, e Propongo, usando un po 'di ricorsione, possiamo ora trovare n. Quindi se n è minore del valore n che è nodo corrente, ho intenzione di andare avanti e punt, per così dire, e proprio restituire qualunque sia la risposta è di alla ricerca di n sul figlio sinistro di albero. Si noti ancora una volta, questa funzione è sufficiente aspetta una stella nodo, un puntatore a un nodo. Quindi sicuramente posso solo fare albero Freccia a sinistra, che porterà me ad un altro nodo. Ma che cos'è quel nodo? 

Ebbene, secondo questa dichiarazione, sinistra è solo un puntatore, perché così, significa che sto passando alla funzione di ricerca un puntatore diverso, cioè quello che rappresenta albero di mio figlio sinistro. Quindi in questo caso, il puntatore a 33, se questo è il nostro ingresso campione Nel frattempo, se n è maggiore del valore n alla nodo corrente nella struttura, quindi io sono intenzione di andare avanti e di punt in altra direzione e dire, non mi sapere se questo valore n è nell'albero, ma so che se lo è, è la mia ramo di destra, per così dire. Quindi fammi chiamare ricorsivamente di ricerca, passando nuovamente un n, ma passando un puntatore a mio figlio destro. 

In altre parole, se io sono attualmente a 55 e sto cercando 99, lo so che il 99 è più grande di 55, così come ho strappato i telefoni settimane libro fa e abbiamo è andato a destra, allo stesso modo siamo intenzione di andare qui. E io non so se è alla mia destra bambino, e non, 77 è lì, ma Lo so che è in quella direzione. Così chiamo ricerca sul mio figlio destro, 77, e lasciare che la figura di ricerca fuori dal lì se 99 in questa arbitraria esempio è in realtà lì. 

Altrimenti, qual è il caso finale? Se albero è null è un caso. Se n è minore del nodo attuale valore è un altro caso. Se n è maggiore della corrente valore del nodo è un terzo caso. Qual è il quarto e ultimo caso? Penso che siamo fuori di casi, giusto? Deve essere che n è nella nodo corrente che sono in. 

Quindi, se io sto cercando 55 a questo punto nella storia, quel ramo della albero sarebbe restituire true. Quindi, ciò che è interessante è che abbiamo in realtà, a differenza di settimane passato, noi genere di avere due casi base. E loro non hanno a essere tutto in alto. La parte superiore è un caso base perché se il albero è nullo, non c'è niente da fare. Basta tornare un hard coded valore false. 

Il ramo inferiore è una sorta di di default, per cui se abbiamo controllato per nullo, abbiamo controllato se deve essere a sinistra, ma non dovrebbe essere, abbiamo verificato se dovesse essere giusta, ma non dovrebbe essere, evidentemente deve essere là dove siamo. Questo è un caso base. Quindi ci sono due casi ricorsivi ci intramezzato in mezzo. Ma ho potuto scrivere questo in qualsiasi ordine. Ho solo pensato che tipo di feltro naturale di controllare prima di un possibile errore, quindi controllare a sinistra, poi a destra controllare, quindi scontato che sei al nodo si sta effettivamente cercando. 

Allora, perché questo potrebbe essere utile? Così si scopre - e fammi saltare a un teaser qui che è nel web. Stiamo per iniziare a utilizzare non una linguaggio di programmazione in un primo momento, ma una linguaggio di markup. Un linguaggio di marcatura di essere uno che è simile nello spirito alla programmazione linguaggio, ma non dà la capacità di esprimere te stesso logicamente. Ti dà solo la possibilità di esprimere se stessi strutturalmente. 

Dove vuoi mettere qualcosa sulla pagina, la pagina web? Di che colore vuoi farlo? Che dimensione del carattere vuoi farlo? Quali parole che effettivamente vuole sulla pagina web? Ecco, questo è un linguaggio di markup. Ma poi si introducono molto rapidamente JavaScript, che è un vero e proprio linguaggio di programmazione. Molto simile sintatticamente in apparenza a C, ma si avrà un po 'di bella, più potente, più funzionalità user friendly. 

E una delle frustrazioni in questa punto nel semestre è che faremo presto implementare ortografico in molti meno righe di codice con altri linguaggi di C si concede, ma per la ragione di che presto capiamo. Questo sarà il primo di tali pagine web. Sarà completamente deludente, il primo che facciamo. Sarà semplicemente dire ciao mondo. Ma se l'avete mai visto prima, questo è HTML, HyperText Markup Language. 

Se vai a una determinata opzione di menu in più qualsiasi browser, su qualsiasi pagina web su Internet, è possibile vedere il codice HTML che alcune persone hanno scritto al creare quella pagina web. E probabilmente non sembra breve o come pulito come questo. Ma sarà seguire il modello di questi parentesi aperte e le barre e lettere e potenzialmente numeri. 

Io ho pensato di dare un occhiolino di quello che sarete in grado di fare dopo aver preso CS50. Lasciami andare a cs.harvard.edu / rob, homepage il nostro Rob Bowden. Ha fatto questo per noi. Così sarete presto in grado di farlo. E inoltre, cosa si sente questa mattina - quello che hai sentito questa mattina - 

[CRICETO DANCE MUSIC] 

- Avrete modo essere in grado di fare questo. Che ci attende il Mercoledì. Ci vediamo allora. 

[CRICETO DANCE MUSIC] DAVID MALAN: Al prossimo CS50 -