[RIPRODUZIONE DI BRANI MUSICALI] 

ANDI PENG: Benvenuti a settimana 6 della sezione. Abbiamo deviato dalla nostro standard ora sezione del Martedì pomeriggio per questa bella Domenica mattina. Grazie per tutti coloro che mi ha raggiunto oggi, ma sul serio, un applauso. 

Questo è un bel grande sforzo. Io quasi non ho nemmeno rendono in tempo, ma non era male. Quindi so che tutti voi hanno appena fatto per il quiz. Prima di tutto, non esitare a il rovescio della medaglia di questo. 

In secondo luogo, parleremo. Parleremo il quiz. Parleremo di come si sta facendo nella classe. Starai bene. Ho tuoi quiz per al termine di qui, quindi se voi volete prendere un guardare, tutto bene. 

Così in fretta prima di cominciare, la ordine del giorno per oggi è il seguente. Come potete vedere, siamo fondamentalmente cottura rapida attraverso tutta una serie di strutture di dati davvero, davvero, davvero in fretta. Quindi, come tale, non sarà oggi super-interattivo. Sarà solo me tipo di gridare cose che voi, e se ti confondo, se sto andando troppo veloce, fatemelo sapere. Sono solo i vari dati strutture, e come parte del vostro pset per questo prossima settimana, ti essere chiesto di attuare uno di loro, forse due di them-- due di essi nel pset. Ok, quindi sto solo andando a iniziare con alcuni annunci. Andremo su pile e code più in profondità di quello che abbiamo fatto prima il quiz. Andremo oltre legati elencare nuovamente, ancora una volta, più in profondità di quanto abbiamo avuto prima il quiz. E poi parleremo di hash tabelle, alberi e tentativi, che sono tutti abbastanza necessarie per la tua pset. E poi andremo su alcuni suggerimenti utili per pset5. 

OK, quiz 0. La media era un 58%. E 'stato molto basso, e così voi ragazzi tutti fatto molto, molto bene in conformità con quello. 

Praticamente, regola generale è che se siete all'interno di una deviazione standard della media soprattutto perché siamo in un meno sezione comodo, sei tutto bene. Siete sulla buona strada. La vita è bella. 

Lo so che è spaventoso pensare che Ho avuto come un 40% su questo quiz. Sto andando a fallire questa classe. Vi prometto che, non sei andando a fallire la classe. Sei totalmente bene. 

Per quelli di voi che ha ottenuto oltre la media, impressionante, impressionante, come, seriamente ben fatto. Li ho con me. Sentitevi liberi di venire prenderli alla fine della sezione. Fatemi sapere se avete qualsiasi problemi, domande con loro. Se sommiamo il tuo punteggio sbagliato, fateci sapere. 

OK, così pset5, questo è un davvero Settimana strano per Yale nel senso che il nostro pset è dovuto Mercoledì a mezzogiorno compreso la fine del giorno, quindi è in realtà teoricamente dovuto Martedì a mezzogiorno. Probabilmente nessuno finito a Martedì a mezzogiorno. Questo è totalmente bene. Stiamo per avere gli orari d'ufficio stasera così come Lunedi notte. E tutte le sezioni di questa settimana sarà effettivamente trasformate in officine, quindi sentitevi liberi di pop in ogni sezione che si desidera, e saranno di tipo mini-pset laboratori per aiuto su questo. Così come tale, questa è l'unica sezione dove stiamo materiale didattico. Tutte le altre sezioni si concentreranno esclusivamente sulla guida per la pset. Sì? 

PUBBLICO: Dove sono le ore di ufficio? 

ANDI PENG: Orario di ricevimento tonight-- oh, bella domanda. Penso che le ore di ufficio stasera sono in Teal oa Commons. Se si controlla in linea CS50 e si va in orario d'ufficio, ci dovrebbe essere un programma che dove tutti sono dice. 

So che sia stasera o domani è verde acqua, e penso che possiamo avere comuni per l'altra sera. Non sono sicuro. Bella domanda. Controllare il CS50. 

Cool, qualsiasi domanda relativa al pianificazione per il prossimo come tre giorni? Prometto voi ragazzi come David ha detto, questa è la cima della collina. Voi ragazzi siete quasi arrivati. Solo tre più giorni. Arriviamo, e allora saremo tutti scesi. Avremo una piacevole pausa CS-libero. Torneremo. Ci immergeremo in web programmazione e sviluppo, cose che sono molto divertenti a confronto per alcune delle altre pset. E sarà freddo, e avremo un sacco di divertimento. Avremo più caramelle. Ci scusiamo per caramelle. Ho dimenticato la caramella. Era una mattina di massima. Quindi voi siete quasi arrivati, e sono davvero orgoglioso di voi ragazzi. 

OK, così pile. Che amava la domanda su Jack e la sua veste sul quiz? Nessuno? Ok va bene. 

Quindi, in sostanza, come si può foto Jack, questo ragazzo qui, ama prendere l'abbigliamento fuori dalla sommità della pila, e la mette di nuovo sul pila dopo che ha fatto. Quindi, in questo modo, non ha mai sembra essere sempre al fondo del impilare nel suo abbigliamento. Quindi questo tipo di descrive la struttura di dati di base come uno stack è implementato. 

In sostanza, pensare ad una impilare come ogni pila di oggetti dove si mettono le cose sulla parte superiore, e poi si pop fuori dalla parte superiore. Così LIFO è l'acronimo che ci piace a use-- Last In, First Out. E così durare nel all'inizio della pila è il primo che esce. E così i due termini ci piace associare con che sono chiamati spinta e pop. Quando si preme qualcosa sul stack, e pop il backup. 

E quindi credo che questo è una specie di un concetto astratto per quelli di voi che vogliono vedere come un attuazione di questa nel mondo reale. Quanti di voi hanno scritto un saggio forse come un'ora prima che fosse dovuto, e accidentalmente cancellato una enorme pezzo di esso, come per caso? E allora cosa fare di controllo che utilizziamo per rimetterlo? Control-Z, sì? Control-Z, quindi la quantità di volte che Control-Z ha salvato la vita, ha salvato il culo, ogni volta che è implementato attraverso un camino. 

Sostanzialmente tutte le informazioni questo è il documento di Word, esso viene spinto e spuntato a volontà. E così in sostanza ogni volta che si eliminare qualsiasi cosa, pop il backup. E poi, se avete bisogno di nuovo su, è spingere, che è ciò che fa Control-C. E la funzione di mondo così reale di come semplice struttura dei dati può aiutare con la vostra vita di tutti i giorni. 

Quindi una struct è il modo in cui abbiamo effettivamente creare uno stack. Noi scriviamo definire struct, e poi la chiamiamo pila in fondo. E all'interno dello stack, abbiamo due parametri che possiamo in sostanza manipolare, così abbiamo char capacità stringhe stelle. 

Tutto ciò che sta facendo è la creazione di un array che possiamo memorizzare quello che volete che siamo in grado di determinarne la capacità. La capacità è solo l'importo massimo di articoli che possono mettere in questo array. int size è il contatore che tiene traccia di come molti elementi sono attualmente nella pila. Allora possiamo tenere traccia di, A, sia quanto grande lo stack effettivo è, e, B, quanto di quella pila abbiamo riempito perché non vogliamo traboccare su ciò che la nostra capacità è. 

Così, per esempio, questa bella domanda era sul quiz. Essenzialmente come facciamo a spingere sulla sommità di una pila. Abbastanza semplice. Se la si guarda, cammineremo attraverso questo. Se [incomprensibile] size-- ricordare, ogni volta che si vuole accedere a qualsiasi parametro all'interno di una struct, si fa il nome del struct.parameter. 

In questo caso, è s il nome del nostro stack. Vogliamo accedere alle dimensioni di esso, in modo da fare s.size. Quindi, fintanto che la dimensione non è uguale capacità o il tempo come è inferiore alla capacità, o avrebbe funzionato qui. 

Vuoi accedere all'interno del tuo stack, così s.strings, e si sta andando a mettere quel nuovo numero che si desidera inserire in là. Diciamo solo che vorremo inserire int n nello stack, potremmo fare s.strings, staffe, s.size uguale n. Perché la dimensione è dove siamo Attualmente sono in pila se stiamo andando a spingere su, abbiamo appena accediamo ove la dimensione è il corrente pienezza della pila, e spingiamo la int n su di esso. E poi vogliamo fare in modo che stiamo anche incrementando le dimensioni della n, in modo da poter tenere traccia di che abbiamo aggiunto una cosa supplementare alla pila. Ora abbiamo una dimensione maggiore. Questo qui ha senso tutti, come logicamente funziona? Era una specie di rapido. PUBBLICO: Si può andare oltre le s.stringss.strings [s.size] di nuovo? ANDI PENG: Certo, così che cosa fa s.size attualmente ci danno? PUBBLICO: E 'la dimensione corrente. ANDI PENG: Esattamente, in modo che il indice corrente che la nostra dimensione è a, e così vogliamo mettere il nuovo numero intero che vogliamo inserire nel s.size. Questo fa senso? Poiché s.strings, tutto ciò che è è il nome della matrice. Tutto ciò che è è l'accesso alla matrice all'interno della nostra struct, e quindi se vogliamo posizionare n in tale indice, possiamo semplicemente accedervi utilizzando le staffe s.size. Raffreddare. 

Va bene, pop, ho pseudocodice fuori per voi ragazzi, ma concetto simile. Questo fa senso? Se la dimensione è maggiore di zero, allora sai che si vuole prendere qualcosa out perché se la dimensione non è maggiore di zero, allora non hanno nulla in pila. 

Così si vuole solo eseguire questo codice, si può solo pop se c'è qualcosa di pop. Quindi, se la dimensione è maggiore di 0, abbiamo meno la dimensione. Abbiamo decrementa la dimensione e poi ritorniamo tutto ciò che è dentro di essa, perché da popping, vogliamo accesso tutto ciò che è memorizzato nell'indice della cima della pila. Tutto ha senso? Se ho fatto voi ragazzi scrivere questo fuori, VUOI ragazzi in grado di scrivere fuori? OK, voi potete giocare con esso. Non preoccuparti se non si capiscono. Non abbiamo il tempo di codice oggi fuori perché abbiamo avuto un sacco di queste strutture passare attraverso, ma essenzialmente pseudocodice, molto, molto simile a spingere. Basta seguire la logica. Assicurati di accedere a tutte le caratteristiche del tuo struct correttamente. Sì? 

PUBBLICO: Will queste slide e questa cosa sia oggi-ish? ANDI PENG: sempre, sì. Ho intenzione di provare a mettere questo in su come un'ora dopo. Io invieremo un'email David, David cercherà di metterlo come un'ora dopo. 

OK, così poi ci spostiamo in questo altro bella struttura di dati chiamata una coda. Come voi potete vedere qui, un coda, per gli inglesi in mezzo a noi, tutto ciò che è è una linea. Quindi, contrariamente a quanto si pensa che un stack è, una coda è esattamente quello logicamente si pensa che è. Si tiene dalle regole del FIFO, che è First In, First Out. Se sei il primo uno nella linea, sei il primo che esce dalla linea. 

Quindi quello che ci piace chiamare questo è dequeueing e enqueueing. Se vogliamo aggiungere qualcosa alla nostra coda, abbiamo enqueue. Se vogliamo dequeue, o prendere via qualcosa, noi dequeue. 

Così lo stesso senso che siamo tipo di la creazione di elementi di dimensione fissa che abbiamo in grado di memorizzare certa cose, ma possiamo anche cambiare dove stiamo mettendo parametri all'interno dei quali in base al tipo di funzionalità che vogliamo. Così pile, abbiamo voluto l'ultimo uno, N per essere il primo ad uscire. Coda è che vogliamo la prima cosa per la prima cosa fuori. 

Così il struct-tipo definire, come si può vedere, è un po 'diverso da ciò che la pila era perché non solo dobbiamo continuare traccia di dove la dimensione è attualmente, vogliamo anche tenere traccia della testa così come dove attualmente siamo. Quindi penso che sia più facile se ne traggo questo. Quindi cerchiamo di immaginare abbiamo una coda, quindi diciamo la testa è proprio qui. Il capo della linea, andiamo solo dire che è attualmente lì, e vogliamo inserire qualcosa nella coda. Io vado a chiamare formato essenzialmente è la stessa cosa di coda, alla fine della coda è ovunque il vostro. Diciamo solo che la dimensione è proprio qui. 

Quindi, come si fa a tenerne inserisci qualcosa in una coda? Cosa indice vogliamo porre dove vogliamo inserire in. Se questo è l'inizio della tua coda e questa è la fine di esso o le dimensioni di esso, dove fare noi vuole aggiungere l'oggetto successivo? 

PUBBLICO: [incomprensibile] ANDI PENG: Esattamente, si desidera aggiungere esso a seconda che hai scritto. O questo è vuoto o che è vuoto. Così si vuole aggiungere che probabilmente qui perché se la dimensione è-- se questi sono tutti pieni, si vuole per aggiungere proprio qui, giusto? 

E così che è, mentre molto, molto semplice, non proprio sempre corretto perché la differenza principale tra una coda e una pila è che la coda può effettivamente essere manipolato modo che le modifiche testa a seconda di dove si vuole l'inizio del vostro spunto per iniziare. E come risultato, la coda sta anche andando a cambiare. E così dare un'occhiata a questo codice al momento. Come voi ragazzi sono stati invitati a scrivere sul quiz, enqueue. Magari ne parliamo perché attraverso la risposta era quello che era. 

Io non riuscivo a montare questa linea su uno, ma essenzialmente questo pezzo di codice dovrebbe essere su una riga. Spendere come 30 secondi. Date un'occhiata, e capire perché questo è il modo in cui è. 

Molto, struct molto simili, molto, molto struttura simile alla precedente impilare tranne forse una riga di codice. E che una riga di codice determina la funzionalità. E si differenzia davvero una coda da una pila. 

Chiunque vuole prendere una pugnalata di spiegare il motivo per cui hai ottenuto questa cosa complicata qui dentro? Vediamo il ritorno del nostro amico meraviglioso modulo. Come voi ragazzi presto riconoscere in programmazione, quasi in qualsiasi momento avete bisogno di qualcosa per avvolgere qualsiasi cosa, modulo sarà il modo per farlo. Quindi, sapendo che, qualcuno vuole provare spiegando che riga di codice? Sì, tutte le risposte sono accettato e di benvenuto. PUBBLICO: Stai parlando con me? ANDI PENG: Sì. PUBBLICO: Oh, non mi dispiace. ANDI PENG: OK, quindi cerchiamo di camminare attraverso questo codice. Così, quando si sta cercando di aggiungere qualcosa su una coda, nella deliziosa caso che la testa succede di essere qui, è molto facile per noi andare solo alla fine inserire qualcosa, giusto? Ma il punto centrale di una coda è che la testa può effettivamente dinamicamente cambiare a seconda di dove ci vuole l'inizio del nostro q di essere, e come tale, la coda sta anche andando a cambiare. 

E quindi immaginare che questo non era il coda, ma questo è stato coda. Diciamo che la testa è proprio qui. Diciamo che la nostra coda si presentava così. Se volessimo spostare dove All'inizio della linea è, diciamo che abbiamo spostato testa in questo modo e misure delle taglie Qui. 

Ora vogliamo aggiungere qualcosa a questa coda, ma come voi potete vedere, non è così semplice da solo aggiungere tutto ciò che è dopo la dimensione perché allora siamo a corto di limiti della nostra gamma attuale. Dove vogliamo aggiungere davvero è qui. Questo è il bello di una coda è che per noi, visivamente si presenta come la linea va come questo, ma se conservato in una struttura di dati, danno come come un ciclo. E 'sorta di avvolge al fronte stesso modo che una linea può anche avvolgere intorno a seconda ovunque tu vogliono all'inizio della linea di essere. E quindi se prendiamo un guardare in basso qui, diamo diciamo abbiamo voluto creare un funzione chiamata enqueue. Abbiamo voluto aggiungere int n in quella q. Se q.size q-- chiameremo che i nostri dati structure-- se il nostro queue.size non lo fa uguale capacità o se è inferiore alla capacità, q.strings è la matrice all'interno della nostra q. Stiamo andando a impostare che la parità di q.heads, che è proprio qui, più q.size modulo dalla capacità che noi avvolgere di nuovo intorno qui. 

Quindi in questo esempio, l'indice di testa è 1, giusto? L'indice di dimensione è 0, 1, 2, 3, 4. Così possiamo fare 1 più 4 modulo dalla nostra capacità, che è 5. Che cosa ci danno? Che cosa è l'indice che esce di questo? 

PUBBLICO: 0. 

ANDI PENG: 0, che sembra essere proprio qui, e così noi vogliamo essere in grado da inserire nel proprio qui. E così questa equazione qui genere di opere solo con tutti i numeri a seconda di dove il tuo testa e il formato sono. Se sai cosa quelli le cose sono, sai esattamente dove si desidera inserire tutto ciò che è dopo la vostra coda. Questo fa senso a tutti? 

So che tipo di un cervello rompicapo soprattutto perché questo è venuto a seguito del quiz. Ma si spera tutti ora può capire perché questa soluzione o questa funzione è il modo in cui è. Chiunque un po 'poco chiaro su questo? OK. 

E così ora, se si voluto dequeue, questo è dove la nostra testa sarebbe spostamento perché se dovessimo dequeue, non prendiamo fuori alla fine del q. Vogliamo prendere la testa, giusto? Così come risultato, testa sta per cambiare, ed è per questo che quando si enqueue, hai avuto modo di tenere traccia di dove la testa e la tua taglia devono essere in grado di inserire nella posizione corretta. 

E così quando si dequeue, Ho anche pseudocodice fuori. Sentitevi liberi di se volete per tentare di codifica questo fuori. Si desidera spostare la testa, giusto? Se volessi dequeue, io sarebbe spostare la testa sopra. Questa sarebbe la testa. 

E il nostro dimensioni attuali sarebbe sottrarre perché non siamo più avere quattro elementi dell'array. Abbiamo solo tre, e poi vogliamo per tornare ciò che è stato memorizzato all'interno della testa perché vogliamo prendere questo valore in modo molto simile alla pila. Appena si sta prendendo da un posto diverso, e si deve riassegnare il puntatore al posto differente come risultato. Logicamente, tutti seguire? Grande. 

Ok, quindi stiamo andando a parlare un po ' più in profondità su liste collegate perché sarà molto, molto prezioso per voi nel corso di questa settimana di pset. Liste collegate, come voi ragazzi può ricordare, tutto quello che sono sono nodi che sono i nodi di alcuni valori sia un valore e un puntatore che sono collegati tra loro da quei puntatori. E così la struct su come creiamo un nodo qui è noi avere int n, che è tutto ciò che il valore in un negozio o una stringa n o quello che volete chiamarlo, il carattere stella n. Struct stella nodo, che è il puntatore che si desidera avere in ogni nodo, si sta andando ad avere quel punto puntatore verso il prossimo. Avrete la testa di una lista collegata che è andando a puntare al resto i valori così via e così via fino a quando alla fine si raggiunge la fine. E questo ultimo nodo è solo andando a non avere un puntatore. Sta andando a puntare a nullo, e che quando sai che hai colpito il fine della vostra lista collegata è quando il tuo ultimo puntatore non punta a nulla. 

Quindi stiamo per andare un po 'più a profondità per quanto riguarda come si farebbe forse cercare una lista collegata. Ricordate che cosa sono alcuni dei inconvenienti delle liste collegate versetti una matrice per quanto riguarda le ricerche. Un array è possibile ricerca binaria, ma perché non si può fare che in una lista concatenata? 

PUBBLICO: Perché sono tutti collegati, ma non si sa bene dove [Incomprensibile]. 

ANDI PENG: Sì, esattamente in modo da ricordare che la brillantezza di un array era il fatto che abbiamo avuto memoria ad accesso casuale in cui se volevo il valore dall'indice sei, potrei solo dire indice di sei, dammi quel valore. E questo perché gli array sono ordinati in uno spazio contiguo di memoria in un unico luogo, mentre tipo di liste concatenate sono intervallati in modo casuale in tutto, e l'unico modo è possibile trovare uno è attraverso un puntatore che ti dice l'indirizzo di dove tale nodo successivo è. 

E così, come risultato, l'unico modo per la ricerca in una lista concatenata è ricerca lineare. Perché io non so esattamente dove il valore 12 nella lista collegata è, Devo attraversare la totalità di quella lista collegata uno da uno dalla testa al primo nodo, al secondo nodo, al terzo nodo, tutta la strada fino a quando ho finalmente dove quel nodo che sto cercando è. E così, in questo senso, la ricerca su una lista concatenata è sempre n. E 'sempre n. E 'sempre in tempo lineare. 

E così il codice in cui attuiamo questo, e questo è un po 'nuova per voi ragazzi da voi ragazzi non hanno davvero parlato o mai visto puntatori in come la ricerca in puntatori, così noi cammineremo attraverso questo molto, molto lentamente. Quindi ricerca bool, a destra, immaginiamo che vogliamo per creare una funzione denominata di ricerca che restituisce true se hai trovato un valore all'interno del collegato elencare, e restituisce false altrimenti. Elenco dei nodi stella è attualmente appena il puntatore al primo elemento nella lista collegata. int n è il valore che si sta cercando in tale elenco. 

Così puntatore nodo stella uguale lista. Questo significa che stiamo impostando e creando un puntatore a tale primo nodo all'interno della lista. Tutti con me? Quindi, se dovessimo andare di nuovo qui, avrei inizializzato un puntatore che punta a il capo di tutto ciò che tale elenco. 

E poi una volta arrivati ​​qui, mentre il puntatore non è uguale nullo, così che è il ciclo in cui siamo sta per essere successivamente attraversare il resto della nostra lista perché ciò che succede quando il puntatore è uguale a zero? Sappiamo che have-- 

PUBBLICO: [incomprensibile] 

ANDI PENG: Esattamente, quindi sappiamo che abbiamo raggiunto la fine della lista, giusto? Se si va indietro qui, ogni nodo dovrebbe essere che punta a un altro nodo E così via e così via fino a colpire alla fine la coda della lista collegata, che ha un puntatore che solo non punta ovunque a parte no. E in modo da sapere in sostanza che la vostra lista vi è ancora in piedi fino a quando il puntatore non è uguale nullo perché una volta che è uguale a zero, si sa che non c'è più roba. 

In modo che sia il ciclo in cui siamo andando ad avere la ricerca vera e propria. E se i pointer-- Vedete che tipo di funzione freccia lì? Quindi, se i punti di puntatore a n, se il puntatore n è uguale uguale a n, in modo che significa che se il puntatore che sei cercare sull'estremità di ciascun nodo è effettivamente uguale al valore che stai cercando, quindi si vuole restituire true. Quindi, fondamentalmente, se siete a un nodo che ha il valore che si sta cercando, lo sai che sei stato in grado di cercare con successo. 

In caso contrario, si desidera impostare il puntatore al nodo successivo. Questo è ciò che la linea qui sta facendo. Puntatore uguale indicatore accanto. Vedere a tutti come che sta lavorando? 

E in sostanza, si sta andando a solo attraversare la totalità della lista, reimpostare il puntatore ogni volta fino a alla fine si colpisce la fine della lista. E si sa che non ci sono più nodi per la ricerca attraverso, e poi si può tornare falso perché si sa che, oh, beh, se sono stato in grado di cercare attraverso la totalità della lista. Se in questo esempio, se volevo per cercare il valore di 10, e mi metto in testa, e Cerco fino in fondo, e alla fine ho avuto modo tale che un puntatore che punta a null, So che, merda, credo che 10 non è in questa lista perché non riuscivo a trovarlo. E io sono alla fine della lista. E in questo caso si sa Ho intenzione di restituire false. 

Vediamo che in ammollo per un po '. Questo sarà piuttosto importante per il vostro pset. La logica è molto semplice, forse sintatticamente appena attuazione. Voi ragazzi vogliono fare Assicurarsi di aver compreso. Raffreddare. 

OK, così come ci sarebbe l'inserimento di nodi, a destra, in un elenco, perché ricordare quali sono le quali i vantaggi di avere una lista collegata contro una matrice in termini di stoccaggio? 

PUBBLICO: E 'dinamica, quindi è più facile a-- 

ANDI PENG: Esattamente, quindi è dinamico, che significa che può espandersi e contrarsi a seconda delle esigenze dell'utente. E così, in questo senso, non abbiamo bisogno di sprecare memoria inutile perché se non so quanti valori che voglio a negozio, non ha senso per me per creare una matrice, poiché se voglio memorizzare 10 valori e creo una serie di 1000, che è un sacco di memoria sprecata, assegnato. Ecco perché vogliamo usare un collegato lista per poter dinamicamente modificare o ridurre la nostra dimensione. 

E in modo che rende l'inserimento un po 'più complicato. Dal momento che non possiamo accedere in modo casuale elementi il modo in cui avremmo di un array. Se voglio inserire un elemento nel settimo index, Ho appena può inserirla nel settimo indice. Su una lista collegata, non è così abbastanza lavorare con la stessa facilità, e quindi se volevamo inserire quella qui nella lista collegata, visivamente, è molto facile da vedere. Vogliamo solo inserire proprio lì, proprio all'inizio della lista, subito dopo la testa. 

Ma il modo in cui dobbiamo riassegnare i puntatori è un po 'contorto o, logicamente, ha senso, ma si vuole fare in modo che avete fino in fondo perché l'ultima cosa che vuoi è quello di riassegnare un puntatore modo in cui stiamo facendo qui. Se si dereference il puntatore da capo a 1, poi tutto ad un tratto la resto della vostra lista collegata è perso perché non avete realmente ha creato un qualcosa di temporaneo. Questo è rilevato al 2. Se si riassegna il puntatore, allora la resto della vostra lista è completamente persa. Così si vuole essere molto, molto attenti qui per assegnare la prima puntatore da tutto ciò che vogliono inserire nel ovunque si vuole, e poi si possono dereference il resto della vostra lista. 

Quindi, questo vale per ovunque si sta cercando di inserire nel. Se si desidera inserire al testa, se si desidera rispondere qui, se si desidera inserire in Alla fine, beh, alla fine ho Immagino che sarebbe solo non hanno puntatore, ma voi vuole fare in modo che non si perdere il resto della vostra lista. Si vuole sempre fare in modo il vostro nuovo nodo punta verso tutto ciò che vogliono inserire, e quindi è possibile aggiungere il concatenamento su. Tutti chiaro? 

Questo sta per essere uno dei problemi reali. Una delle questioni più importanti si sta andando ad avere sul vostro pset è che si sta andando a cercare di creare una lista collegata e cose inserto ma poi solo perdere il resto della vostra lista collegata. E si sta andando ad essere come, io non so perché questo sta accadendo? Ed è un dolore di passare attraverso e cercare tutti i puntatori. 

E vi garantisco su questo pset, scrivere e disegnare questi nodi fuori sarà molto, molto utile. Così si può tenere completamente traccia di dove tutti i vostri puntatori sono, cosa sta andando male, in cui tutti i nodi sono, che cosa dovete fare per accedere o inserire o eliminare o uno di essi. Tutti bene con quello? Raffreddare. 

Quindi, se volessimo guardare il codice? Oh, non so se siamo può vedere the-- OK, così in alto tutto ciò che è è una funzione chiamato inserto dove vogliamo inserire int n alla lista linkata. Stiamo andando a camminare attraverso questo. E 'un sacco di codice, un sacco di nuova sintassi. Saremo OK. 

Così nella parte superiore, ogniqualvolta vogliamo creare qualcosa di che cosa dobbiamo fare, soprattutto se si vogliamo che non da memorizzare nello stack ma nel mucchio? Andiamo in un malloc, giusto? Quindi stiamo andando a creare un puntatore. Nodo, puntatore, nuove eguali malloc la dimensione di un nodo perché vogliamo che il nodo da creare. Vogliamo la quantità di memoria che un nodo riprende da assegnare per il creazione del nuovo nodo. 

E poi andremo a controllare vedere se le nuove uguali equivale a nulla. Ricordate ciò che abbiamo detto? Qualunque cosa tu malloc, cosa deve sempre fare? Si deve sempre verificare se questo è nullo. 

Per esempio, se il vostro operativo sistema era completamente pieno, se non aveste più memoria a tutto e si tenta di malloc, sarebbe restituire null per voi. E così, se si tenta di utilizzarlo quando stava puntando a null, tu non hai intenzione di poter per accedere a tali informazioni. E così, come tale, abbiamo voluto fare Assicurarsi che ogni volta che si sta mallocing, sei sempre il controllo per vedere se che la memoria dato a voi è nullo. E se non lo è, allora possiamo passare con il resto del nostro codice. 

Quindi stiamo andando a inizializzare il nuovo nodo. Stiamo andando a fare nuova n è uguale a n. E poi andremo a fare set nuovo il puntatore sulla nuova a nulla perché in questo momento non lo facciamo voglio niente per poter puntare a. Non abbiamo idea di dove sta andando a mettere voi, e poi se vogliamo inserirla in testa, allora possiamo riassegnare il puntatore alla testa. Non tutti seguono la logica di dove che sta succedendo? 

Tutto quello che stiamo facendo è la creazione di un nuovo nodo, l'impostazione del puntatore a null, e poi riassegnare alla testa se sappiamo che vogliamo inserirla in testa. E poi la testa sta per puntare verso quel nuovo nodo. Tutti d'accordo con questo? 

Quindi è un processo in due fasi. Hai avuto modo di prima assegnazione qualunque cosa si sta creando. Impostare che puntatore riferimento, e poi si può tipo di dereference il primo puntatore e puntarlo verso il nuovo nodo. Ovunque si vuole inserire, che la logica sta per tenere vero. 

E 'un po' come l'assegnazione di variabili temporanee. Ricordate, hai per fare in modo che si non perdere le tracce di se si sta scambiando. Si vuole fare in modo di avere una variabile temporanea quel tipo di conserva traccia di dove quella cosa è memorizzato in modo che si non perdono alcun valore nel corso di come fare in giro con esso. 

OK, il codice sarà qui. Voi ragazzi Date un'occhiata dopo la sezione. Sarà lì. 

Quindi credo che come fa questo diverso se volevamo inserire nella metà o alla fine? Qualcuno ha un'idea di ciò che è la pseudocodice come riferimento logico che noi prenderemmo se volevamo per inserirlo nel mezzo? Quindi, se volessimo per inserirlo al testa, tutto ciò che facciamo è creare un nuovo nodo. Abbiamo impostato il puntatore di quel nuovo nodo per qualunque sia la testa, e poi abbiamo impostato la testa per il nuovo nodo, giusto? Volendo inserire nel mezzo della lista, che cosa dobbiamo fare? 

PUBBLICO: Sarebbe ancora essere un processo simile di come l'assegnazione di puntatore e assegnando tale puntatore, ma avremmo dovuto trovare lì. 

ANDI PENG: Esattamente, così esattamente lo stesso processo tranne voi devono individuare dove esattamente si vuole che il nuovo puntatore per andare in, quindi se voglio inserire nel al centro della collegata list-- OK, diciamo che è la nostra lista collegata. Se vogliamo inserire proprio qui, stiamo andando a creare un nuovo nodo. Stiamo andando a malloc. Stiamo per creare un nuovo nodo. Stiamo per assegnare il indicatore di questo nodo qui. 

Ma il problema che differisce da cui la testa è è che noi sapevamo esattamente dove la testa è. E 'stato proprio in occasione della prima, giusto? Ma qui dobbiamo tenere traccia di dove stiamo inserendo in. Se stiamo inserendo la nostra nodo qui, abbiamo per assicurarsi che il precedente per questo nodo è quella che riassegna il puntatore. Allora dovete tipo di tenere traccia delle due cose. Se si tiene traccia di dove questo nodo attualmente sta inserendo in. Dovete anche tenere traccia di dove il nodo precedente che si sta guardando è stato anche lì. Tutti bene con quello? OK. 

Che ne dite di inserire nella parte finale? Se volessi aggiungere che qui-- se volevo aggiungere un nuovo nodo alla fine di un elenco, come potrei fare per fare che? PUBBLICO: Così attualmente, il di ultimo indicava nulla. ANDI PENG: Sì. Esattamente, quindi questo uno attualmente è puntato a conoscere, e quindi credo che, in questo senso, è molto facile da aggiungere alla fine di un elenco. Tutto quello che dovete fare è impostare la uguale a null e poi espandersi. Proprio lì, molto facile. Molto semplice. 

Molto simile al testa, ma logicamente si vuole fare in modo che i passi si prende in direzione di fare nulla di tutto questo, si sta seguendo. E 'molto facile, in mezzo del codice, preso su su, oh, ho tanti puntatori. Io non so dove niente sta indicando. Io non so nemmeno quale nodo sto. Cosa sta succedendo? 

Relax, calmati, prendere un respiro profondo. Disegna la tua lista collegata. Se dici, io so dove esattamente Ho bisogno di inserire questo in e so esattamente come riassegnare la mia puntatori, molto, molto più facile da immagine fuori-- molto, molto più facile da non perdersi nei bug del codice. Tutti d'accordo con questo? OK. 

Quindi credo che un concetto che non abbiamo davvero parlato prima d'ora, e credo che probabilmente non si incontrano molto yet-- è una specie di un concept-- avanzata è che in realtà abbiamo un dato struttura chiamata una lista doppiamente concatenata. Così come voi potete vedere, tutto quello che stiamo facendo è la creazione di un valore effettivo, un extra puntatore su ciascuno dei nostri nodi che punti anche al nodo precedente. Quindi non solo abbiamo il nostro nodi indicano quello successivo. Essi indicano anche alla precedente. Ho intenzione di ignorare questi due al momento. 

Allora avete una catena che può muoversi in entrambe le direzioni, e quindi è un po 'più facile a seguire logicamente lungo. Come qui, anziché tenere traccia di, oh, devono sapere che questo nodo è quello che ho da riassegnare, Posso solo andare qui e basta tirare la precedente. Poi so esattamente dove che è, e poi si non c'è bisogno di attraversare la elementi della lista collegata. E 'un po' più facile. 

Ma, come tale, si dispone doppiamente la quantità di puntatori, che è il doppio della quantità di memoria. E 'un sacco di puntatori per tenere traccia di. E 'un po' più complesso, ma è un po 'più facile da usare a seconda su ciò che si sta cercando di realizzare. 

Quindi questo tipo di dati struttura totalmente esiste, e la struttura per è molto, molto semplice salvo tutto quello che stai avendo è, invece di un puntatore successivo, anche voi avete un puntatore al precedente. Questa è la differenza era. Tutti bene con quello? Raffreddare. 

Va bene, ora sto di spendere davvero probabilmente come 15 a 20 minuti o il bulk il resto del tempo in sezione parlare di tabelle hash. Quanti di voi ragazzi hanno letto pset5 specifiche? Va bene, bene. Questo è superiore al 50% del normale. Va bene. 

Così come voi ragazzi vedere, siete sfida in pset5 sarà quello di implementare un dizionario dove si caricano oltre 140.000 parole che vi diamo e controllo ortografico contro tutto il testo. Ti daremo casuale pezzi di letteratura. Ti daremo l'Odissea. Ti daremo l'Iliade. Ti daremo Austin Powers. 

E la tua sfida sarà per il controllo ortografico ogni singola parola in tutta la di tali dizionari essenzialmente con il nostro correttore ortografico. E così ci sono alcune parti della creazione di questo pset, prima si vuole essere in grado di caricare effettivamente tutte le parole nel vostro dizionario, e poi si vogliono poter controllo ortografico tutti loro. E così, come tale, si sta andando a richiedere una struttura di dati che può fare questo veloce ed efficiente e dinamicamente. 

Quindi suppongo che il più facile modo per fare questo, è probabilmente creare un array, giusto? Il modo più semplice di archiviazione è voi in grado di creare una serie di 140.000 parole e appena li posto lì e poi attraversare dalla ricerca binaria o dalle selezioni o not-- mi dispiace che è l'ordinamento. È possibile ordinare loro e poi li attraversare per ricerca binaria o la ricerca semplicemente lineare e appena finali le parole, ma che prende un enorme quantità di memoria, e non è molto efficiente. 

E così stiamo per iniziare parlando di modi di fare il nostro tempo di esecuzione più efficiente. E il nostro obiettivo è quello di ottenere costante di tempo in cui è quasi come gli array, dove si ha accesso istantaneo. Se volessi cercare qualsiasi cosa, Voglio essere in grado di solo, asta, trovo esattamente, ed estrarlo. E così una struttura in cui saremo diventando molto vicino per poter accedere costanti tempo, questo Santo Graal in programmazione costante tempo è chiamato una tabella hash. E così Davide accennato in precedenza il [Incomprensibile] un po 'a lezione, ma stiamo andando a davvero tuffo nel profondo di questa settimana su un pezzo che è per quanto riguarda come una tabella hash funziona. 

Quindi il modo che un hash opere tavola, per esempio, se volessi memorizzare un mucchio di parole, un mucchio di parole in lingua inglese, Potrei teoricamente mettere banana, mela, kiwi, mango, coppia, e melone tutto solo su un array. Tutti potevano adattarsi ed essere trovare. Sarebbe una specie di dolore per la ricerca in e di accesso, ma il modo più semplice per farlo è che possiamo creare effettivamente una struttura chiamato una tabella hash dove hash. Noi usiamo tutti i nostri chiavi attraverso una funzione hash, un'equazione, che li trasforma in una sorta di un valore che allora possiamo memorizzare su essenzialmente un array di lista collegata. 

Ed ecco, se abbiamo voluto per memorizzare le parole inglesi, potremmo potenzialmente semplicemente, non lo faccio conoscere, girare tutte le prime lettere in una sorta di un numero. E così, per esempio, se volevo Una di essere sinonimo di apple-- o con l'indice di 0, e B per essere sinonimo di 1, possiamo avere 26 iscrizioni che può solo memorizzare tutte le lettere del alfabeto che inizieremo con. E allora possiamo avere mela l'indice di 0. Possiamo avere banana l'indice 1, melone all'indice di 2, E così via e così via. E così se volevo cercare il mio hash tavolo e accesso mela, So mela inizia con una A, e so esattamente che deve essere e l'hash tavolo indice 0 perché della funzione precedentemente assegnato. 

Quindi io non lo so, siamo un programma utente in cui ti verrà addebitato con arbitrarily-- non arbitrariamente, con il tentativo di pensieroso pensare di buone equazioni essere in grado di diffondersi tutti i tuoi valori in modo che possano facilmente accedere in un secondo momento con come un'equazione che voi, voi stessi, so. Così, nel senso se volevo andare a mango, lo so, oh, si inizia con m. Deve essere in corrispondenza dell'indice di 12. Non ho per la ricerca in qualsiasi cosa. So exactly-- ho potuto solo andare a l'indice di 12 e tirare che fuori. 

Tutti chiare su come una La funzione di tabella di hash funziona? E 'una specie di solo una matrice più complessa. Questo è tutto ciò che è. OK. 

Quindi credo che ci imbattiamo in la questione di ciò che succede se si dispone di più le cose che ti danno lo stesso indice? Quindi dire la nostra funzione, tutto ciò che fatto è stato prendere quella prima lettera e trasformarla in un rispettivi 0 a 25 indice. Che è totalmente bene se hai solo uno di ciascuno. Ma la seconda si avvia avendo più, sei andando ad avere quella che viene chiamata una collisione. 

Quindi, se provo ad inserire seppellire in un hash tabella che ha già banane su di esso, cosa succederà quando si tenta di inserire questo? Cose cattive perché banane esiste già all'interno dell'indice che si desidera memorizzare in. Berry tipo di è come, ah, cosa devo fare? Io non so dove andare. Come posso risolvere questo? 

E così voi ragazzi sarà di tipo vediamo facciamo questa cosa difficile dove possiamo tipo di realtà creare lista collegata nel nostro array. E così il modo più semplice a pensare a questo, tutto tabella hash è un array di liste concatenate. E così, in questo senso, è necessario questa bella serie di puntatori, e poi ogni puntatore in tale valore, in tale indice, può effettivamente puntare ad altre cose. E in modo da avere tutte queste separata catene venuta fuori di una grande matrice. 

Ed ecco, se io ha voluto inserire bacca, Lo so, va bene, ho intenzione di ingresso attraverso la mia funzione di hash. Io vado a finire con l'indice 1, e poi ho intenzione di essere in grado di avere solo un sottoinsieme più piccolo di questo gigante dizionario 140.000 parola. E poi posso solo guardare attraverso 1/26 di quello. 

E così poi posso basta inserire bacca, prima o dopo la banana in questo caso? Dopo, giusto? E così si sta andando a voler inserire questo nodo dopo la banana, e così si sta andando ad inserire in coda che lista collegata. Ho intenzione di tornare indietro a questa diapositiva precedente, così voi potete vedere come funzione hash funziona. 

Quindi funzione hash è questa equazione che si sta eseguendo tipo di vostro input attraverso per ottenere qualunque indice si vuole assegnare verso. E così, in questo esempio, tutti volevamo fare era prendere la prima lettera, trasformarla in un indice, poi siamo in grado di memorizzare che nella nostra funzione di hash. Tutto quello che stiamo facendo qui è che siamo convertire la prima lettera. Così KeyKey [0] è solo la prima lettera di qualsiasi stringa che stiamo avendo, stiamo passando. Stiamo convertendo che a superiore, e stiamo sottraendo dalla A maiuscola, perciò tutto quello che sta facendo ci sta dando un numero in cui possiamo hash nostri valori su. 

E poi andremo a tornare hash modulo SIZE. Essere molto, molto attenti perché, in teoria, qui il vostro valore di hash potrebbe essere infinita. Si potrebbe semplicemente andare avanti e avanti e avanti. Potrebbe essere qualche davvero, davvero grande valore, ma perché la vostra tabella di hash che hai creato ha solo 26 indici, si vuole assicurarsi che il proprio modulusing modo che si non run-- è la stessa cosa come il vostro queue-- in modo che non si esegue fuori fondo della vostra funzione di hash. 

Si vuole avvolgere indietro intorno allo stesso modo in [incomprensibile] quando hai avuto come un molto, molto grande lettera, non ha voluto che a appena scappare alla fine. Stessa cosa qui, si vuole fare in modo non scappare alla fine avvolgendo intorno alla parte superiore della tabella. Quindi questo è solo un molto semplice funzione di hash. Tutto ciò che ha fatto è stato prendere la prima lettera di qualunque sia il nostro ingresso era e trasformarla in un indice che potremmo mettere nella nostra tabella di hash. 

Gia ', e così come ho detto prima, il modo in cui risolvere le collisioni nel nostro hash tabelle stanno avendo, ciò che chiamiamo, concatenamento. Quindi, se si tenta di inserire più parole che iniziano con la stessa cosa, si sta andando ad avere un valore di hash. Avocado e mele, se hai eseguirlo tramite il nostro funzione di hash, stanno per dare il stesso numero, il numero di 0. E così il nostro modo di risolvere cioè che possiamo effettivamente tipo di collegarli insieme attraverso liste collegate. 

E così in questo senso, voi potete vedere tipo di come le strutture di dati che abbiamo impostazione precedentemente come un passito collegato lista genere di può venire insieme in un unico. E allora si può creare lontano strutture dati più efficienti in grado di gestire grandi quantità di i dati, che ridimensionare in modo dinamico a seconda alle vostre esigenze. Tutti chiaro? Tutti i tipi di chiara su quello che succede qui? 

Se volevo insert-- ciò che è un frutto che inizia con, non lo so, B, diversi da bacca, banana. 

PUBBLICO: Blackberry. 

ANDI PENG: Mora, mora. Da dove viene mora va qui? Beh, in realtà non abbiamo ordinato questo ancora, ma in teoria se volevamo avere questo in ordine alfabetico, dove dovrebbe andare mora? 

PUBBLICO: [incomprensibile] 

ANDI PENG: Esattamente, dopo qui, giusto? Ma dal momento che è molto difficile reorder-- Credo che tocca a voi ragazzi. Voi ragazzi può totalmente implementa quello che vuoi. Il modo più efficiente di fare questo forse sarebbe quella di ordinare la vostra collegato elencare in ordine alfabetico, e così quando sei l'inserimento di cose, si vuole per essere sicuri di inserirli in ordine alfabetico in modo che poi quando sei cercando di loro la ricerca, non c'è bisogno di attraversare tutto. Si sa esattamente dove è, ed è più facile. 

Ma se avete tipo di cose intervallati in modo casuale, si sta ancora andando ad avere per attraversare comunque. E così se volevo solo inserisci mora qui e volevo cercare si, lo so, oh, mora deve iniziare con l'indice di 1, in modo da conoscere istantaneamente basta cercare a 1. E poi posso tipo di attraversare la lista collegata fino a ottenere alla mora, e then-- sì? 

PUBBLICO: Se stai cercando di create-- Credo che in questo modo è molto semplice hash funzione. E se volessimo fare più livelli di che, come, OK, vogliamo separare in come tutte le lettere alfabetiche e poi di nuovo a come un altro set di lettere alfabetiche all'interno di quella, stiamo mettendo come un hash tabella all'interno di una tabella hash, o come una funzione all'interno di una funzione? O è che-- 

ANDI PENG: Così il vostro hash function-- la tua tabella di hash può essere grande come si desidera. Quindi, in questo senso, ho pensato era molto facile, molto semplice per me basano appena sorta sulle lettere della prima parola. E così ci sono solo 26 opzioni. Posso solo 26 opzioni da 0-25, perché solo è possibile iniziare dalla A alla Z. Ma se si voleva aggiungere, forse, più complessità o più veloce il tempo di esecuzione per la vostra tabella di hash, è assolutamente può fare un sacco di cose. È possibile rendere il proprio equazione che ti dà più la distribuzione nella vostra parole, poi quando si cerca, che sta per essere più veloce. 

E 'totalmente a voi ragazzi come si desidera attuare tale. Pensate a come appena secchi. Se volevo avere 26 secchi, sto andando per sistemare le cose in quelli secchi. Ma ho intenzione di avere un gruppo di roba di ciascun segmento, quindi se si vuole fare più veloce ed efficiente, mi permetta di avere un centinaio di secchi. 

Ma poi si deve capire un modo per ordinare le cose in modo che siano nel secchio corretta dovrebbero essere in. Ma allora quando realmente vuole guardare quel secchio, è molto più veloce perché non c'è meno roba in ciascun segmento. E così, sì, questo è in realtà il trucco per voi ragazzi a pset5 è che sarete sfidati a creare solo Qualunque sia la più efficiente funzione che si può pensare di essere in grado di memorizzare e controllare questi valori. 

Totalmente a voi ragazzi comunque lo si voglia fare, ma questo è davvero un buon punto. Che il tipo di logica che si voglia di iniziare a pensare è, beh, perché non faccio più secchi. E poi devo cercare meno cose, e poi forse hanno una funzione hash differente. 

Sì, ci sono un sacco di modi per fare questo pset, alcuni sono più veloci di altri. Sono totalmente andando a vedere quanto veloce è stato il più veloce voi ragazzi essere in grado di ottenere le funzioni per lavorare. OK, tutti bene su concatenamento e hash tabelle? In realtà è come una molto semplice concetto se ci pensate. Tutto ciò che è è ciò che separa gli ingressi sono in secchi, loro ordinamento, e quindi la ricerca del elenca che vi è associato. 

Raffreddare. Va bene, ora abbiamo una specie diversa di struttura dati che è chiamato un albero. Andiamo avanti e parlare di tentativi quali sono nettamente diverso, ma nella stessa categoria. Essenzialmente, tutto un albero è invece di organizzare i dati in modo lineare che una tabella hash si does-- Sai, che ha un alto e un basso e quindi è sorta di collegare al largo di un it-- albero ha una parte superiore, che si chiama la radice, e quindi ha foglie tutto intorno. 

E così tutto quello che avete qui è solo il nodo superiore che punta ad altri nodi, che i punti a più nodi, e così via e così via. E quindi basta avere i rami di divisione. E 'solo un modo diverso di organizzare dati, e perché si parla di un albero, voi ragazzi solo-- è solo modellato a guardare come un albero. Ecco perché lo chiamiamo alberi. 

Tabella hash si presenta come un tavolo. Un albero appare come un albero. Tutto ciò che è è un separato modo di organizzare i nodi a seconda di cosa i vostri bisogni sono. 

In modo da avere una radice e allora avete foglie. Il modo in cui possiamo particolarmente pensarci è un albero binario, un albero binario è solo un tipo specifico di un albero dove solo ogni nodo punti a, al massimo, due altri nodi. Ed ecco avete distinti simmetria nel tuo albero che rende più facile per tipo di look a quali valori si sono perché poi si avere sempre a sinistra o destra. Non c'è mai come un terzo da sinistra sinistra o un quarto da sinistra. E 'solo avete una sinistra e una destra e si può cercare uno di quei due. E allora perché è utile? Il modo in cui questo è utile è se stai cercando per la ricerca in valori, giusto? Invece di attuazione binario cerca in un array di errore, se si voleva essere in grado di inserire i nodi e portare via i nodi a volontà e anche preservare la ricerca capacità di ricerca binaria. Quindi, in questo modo, siamo sorta di tricking-- ricordo quando abbiamo detto liste concatenate non può ricerca binaria? Stiamo tipo di creazione di una struttura di dati che trucchi che a lavorare. 

E le liste perché collegate sono lineari, si collegano solo uno dopo l'altro. Possiamo sorta di avere diverso tipo di puntatori quel punto a differenti nodi che ci può aiutare con la ricerca. Ed ecco, se volevo avere un albero binario di ricerca, So che il mio mezzo, se 55. Sto solo andando a creare quella come il mio mezzo, come la mia radice, e poi ho intenzione di avere I valori di spin fuori di esso. 

Così qui, se io vado a cercare il valore di 66, posso iniziare a 55. È 66 maggiore di 55? Sì, è, quindi so che MUS cerco i n il puntatore a destra di questo albero. Vado a 77. OK, è inferiore a 66 o superiore a 77? E 'meno, in modo da sapere, oh, che deve essere il nodo di sinistra. 

Ed ecco che stiamo tipo di preservare tutte le grandi cose su array, così come il ridimensionamento dinamico di oggetti, essendo in grado di inserire e cancellare a piacimento, senza doversi preoccupare del fisso quantità di spazio. Abbiamo ancora conserviamo tutti quelle cose meravigliose pur essendo in grado di preservare la log e cercare il tempo di ricerca binaria che eravamo solo in precedenza in grado di ottenere una frase. 

Struttura dati fresco, tipo di complesso da attuare, il nodo. Come potete vedere, tutto ciò che è la struct del nodo è che si dispone di un sinistro e un puntatore a destra. Questo è tutto ciò che è. Quindi, piuttosto che solo avere un x o di un precedente. Si dispone di un sinistro o un diritto, e quindi è possibile tipo di collegarli insieme tuttavia lo desidera. 

OK, stiamo effettivamente andando basta prendere un paio di minuti. Quindi stiamo per tornare qui. Come ho detto in precedenza, I tipi di spiegai la logica dietro il modo in cui sarebbe la ricerca in questo. Stiamo andando a provare pseudocoding questo fuori per vedere se siamo in grado di applicare il tipo stessa logica di ricerca binaria ad un diverso tipo di struttura dati. Se voi ragazzi volete prendere come una coppia minuti per pensare solo di questo. OK. Va bene, vado a in realtà solo darvi the-- no, parleremo il pseudocodice prima. Così qualcuno vuole per dare una pugnalata a ciò che la prima cosa che voglio fare quando si sta partendo la ricerca è? Se stiamo cercando il valore di 66, ciò che è la prima cosa che vogliamo fare se vogliamo in binario cercare questo albero? 

PUBBLICO: Si vuole guardare a destra e guardare a sinistra e vedere [incomprensibile] numero maggiore. 

ANDI PENG: Sì, esattamente. Così si sta andando a guardare root. Ci sono molti modi è possibile chiamare esso, il tuo popolo nodo genitore dire. Mi piace dire radice perché che è come la radice dell'albero. Si sta andando a guardare il nodo principale, e sei andando a vedere è maggiore 66 o minore di 55. E se è maggiore di, beh, è superiore, dove vogliamo guardare? Dove vogliamo per cercare ora, giusto? Noi vogliamo cercare la metà destra di questo albero. 

Così abbiamo, comodamente, un puntatore che punta a destra. E così poi possiamo impostare la nostra nuova radice per essere 77. Possiamo solo andare ovunque il puntatore punta. Beh, oh, qui stiamo iniziando a 77, e possiamo solo fare questo in modo ricorsivo ancora e ancora. In questo modo, è sorta di avere una funzione. Avete un modo di cercare che si può solo ripetere più e più e più volte, a seconda di dove si vuole guardare fino ad arrivare alla fine del valore che si sta cercando. Ha senso? 

Sto per mostrarvi la reale codice, ed è un sacco di codice. Non c'è bisogno di fuori di testa. Parleremo attraverso di essa. 

In realtà, no. Quello era solo pseudocodice. OK, questo era solo l'pseudocodice, che è un po 'complessa, ma è assolutamente soddisfacente. Ognuno seguendo lungo qui? Se la radice è nullo, il ritorno falso perché questo significa voi non hanno nemmeno bisogno nulla. 

Se radice n è il valore, quindi se sembra essere quello che si sta guardando, allora si sta andando a restituire true perché sai hai trovato. Ma se il valore è inferiore di radice di n, sei andando a cercare la sinistra bambino o la foglia di sinistra, qualunque cosa si voglia chiamare. E se il valore è maggiore di radice, si sta andando a cercare l'albero giusto, poi basta eseguire la funzione attraverso la ricerca di nuovo. 

E se radice è nullo, che tale significa che hai raggiunto la fine? Ciò significa che non avete più più foglie per la ricerca, poi si sa, oh, Immagino che non è qui perché dopo che ho guardato attraverso il tutto e non è qui, semplicemente non potrebbe essere qui. 

Questo fa senso a tutti? Così è come la ricerca binaria preservare le capacità di liste collegate. Fresco, e così il secondo tipo di strutture dati voi ragazzi può provare l'attuazione sul pset, devi solo scegliere un metodo. Ma forse un metodo alternativo per la tabella hash è ciò che chiamiamo un trie. 

Tutto un trie è un specifico tipo di albero che ha valori che vanno ad altri valori. Così, invece di avere un binario albero nel senso che un solo cosa può puntare a due, si può avere punto una cosa da molte, molte cose. Hai essenzialmente matrici all'interno del quale si memorizza puntatori che puntano ad altri array. 

Quindi il nodo di come definirebbe un trie è che vogliamo avere un Booleano, c parola, giusto? Quindi il nodo è booleano come vero o falso, prima di tutto alla testa tale matrice, si tratta di una parola? In secondo luogo, si vuole avere puntatori a qualunque il resto di loro sono. Un po 'complesso, un po' astratto, ma Spiegherò cosa che tutti i mezzi. 

Così qui, in alto, se si hanno una matrice dichiarato già, un nodo in cui si dispone di un booleano valore memorizzato nella parte anteriore che ti dice è questa una parola? Non è questa una parola? E poi ci sono la resto del vostro array in realtà memorizza tutte le possibilità di ciò che potrebbe essere. Così, per esempio, come in alto si ha la prima cosa che dice vero o falso, sì o no, questa è una parola. 

E poi ci sono da 0 a 26 di le lettere che è possibile memorizzare. Se volessi cercare per pipistrello, vado al top e cerco B. trovo nel mio B array, e quindi so, OK, è B una parola? B non è una parola, così così Devo continuare a cercare. Vado da B, e guardo al puntatore che punta verso B e vedo un altro array di informazioni, la stessa struttura che avevamo prima. 

E qui-- oh, il prossimo lettera [incomprensibile] è A. Quindi guardiamo in tale matrice. Troviamo l'ottavo del valore, e poi guardiamo a vedere, oh, ehi, che è una parola, è B-A una parola? Non è una parola. Dobbiamo continuare a cercare. 

E così poi guardiamo a dove l'indicatore di punti A, e indica un altro modo in che abbiamo più valore memorizzato. E alla fine, si arriva a B-A-T, che è una parola. E così la prossima volta si guarda, si sta andando per avere quel controllo di, sì, questa funzione booleana è vero. E così, nel senso che siamo tipo di avere un albero con array. 

Così allora si può tipo di ricerca in giù. Invece di una funzione hash e assegnando valori da lista collegata, si può solo attuare un trie che cerca downwords. Davvero, davvero complicato roba. Non è facile pensare, perché sono come sputando tante strutture di dati fuori a voi, ma lo fa tutti i tipi di capire come funziona la logica di questo? 

Ok bello. Quindi B-A-T, e quindi si sta andando a cercare. La prossima volta che si sta andando per vedere, oh, ehi, è vero, quindi so che questo deve essere una parola. 

Stessa cosa per lo zoo. Quindi, ecco la cosa in questo momento, se si voluto per cercare zoo, in questo momento, attualmente zoo non è un parola nel nostro dizionario perché, come voi potete vedere, il primo posto che abbiamo un valore booleano ritorno vero è a fine zoom. Abbiamo Z-O-O-M. 

Ed ecco, noi non abbiamo in realtà la parola, zoo, nel nostro dizionario perché questa casella non è selezionata. Quindi il computer non si sa che lo zoo è una parola perché il modo che abbiamo memorizzata esso, solo uno zoom qui in realtà ha un valore booleano ciò che è stato trasformato vero. Quindi, se vogliamo inserire la parola, zoo, nel nostro dizionario, come potremmo fare per fare che? Cosa dobbiamo fare per assicurarsi che il nostro computer sa che Z-O-O è una parola e non la prima parola è Z-O-O-M? 

PUBBLICO: [incomprensibile] 

ANDI PENG: Esattamente, abbiamo vuole fare in modo che questo qui, che è valore booleano spuntata che è vero. Z-O-O, allora stiamo andando a verificare che, così sappiamo esattamente, ehi, lo zoo è una parola. Io vado a dire la computer che è una parola così che quando il computer controlla, sa che lo zoo è una parola. 

Perché ricordare tutti questi dati strutture, è molto facile per noi per dire, oh, pipistrello è una parola. Zoo è una parola. Zoom è una parola. Ma quando si sta costruendo essa, il computer non ha idea. 

Quindi devi dire esattamente a che punto è questa una parola? A che punto non è forse una parola? E a che punto devo bisogno di cercare le cose, ea che punto devo andare dopo? Ognuno chiaro di che? Raffreddare. 

E così poi arriva il problema di come sarebbe noi andare sull'inserimento qualcosa questo non è davvero lì? Quindi diciamo solo che vogliamo inserire la parola, il bagno, nel nostro trie. Come voi ragazzi possono vedere come attualmente tutto quello che abbiamo ora è B-A-T, e questa nuova struttura di dati vi era una pinta che indicò nullo perché si suppone che, oh, non ci sono parole dopo B-A-T, perché abbiamo bisogno di mantenere avere cose dopo che T. 

Ma il problema si pone se non facciamo voi vogliono avere una parola che viene dopo il T. Se si dispone di vasca da bagno, sei intenzione di voler un diritto H. E così il modo in cui stiamo andando per farlo è stiamo andando a creare un nodo separato. Non stiamo assegniamo qualsiasi importo di memoria per questo nuovo array, e abbiamo intenzione di riassegnare i puntatori. 

Stiamo per assegnare il H, Prima di tutto, questo nullo, stiamo andando a sbarazzarsi. Stiamo per avere le basso punto H. Se vediamo un H, lo vogliamo per andare da qualche altra parte. 

Qui, possiamo allora spuntare sì. Se abbiamo raggiunto una H dopo la T, oh, allora sappiamo che si tratta di una parola. Il booleana sta per restituire true. Ognuno chiaro su come quello che è successo? OK. 

Quindi, in sostanza, tutti queste strutture dati che siamo andati oltre oggi, ho passati su di loro molto, molto in fretta e non per molto dettaglio, e questo è OK. Una volta che si inizia a fare scherzi con essa, sarete tenere traccia di dove tutti i puntatori sono, cosa sta succedendo nella vostra strutture di dati, eccetera. Saranno molto utili, e tocca a voi ragazzi per capire completamente come si desidera implementare le cose. 

E così pset4, di 5-- oh, questo è sbagliato. Pset5 è errori di ortografia. Come ho detto prima, si sta andando a, una volta ancora una volta, scaricare il codice sorgente da noi. Ci sara 'tre principali cose sarete scaricando. Potrai scaricare dizionari, kers, e testi. 

Tutte queste cose sono sono sia dizionari di parole che vogliamo di controllare o il test di informazioni che vogliamo farvi Controllo ortografico. E così il dizionari diamo si sta andando per darvi parole reali che vogliamo di memorizzare in qualche modo in un modo che è più efficiente di una matrice. E poi i testi sono sta per essere ciò che siamo si chiede di controllo ortografico per assicurarsi tutte le parole ci sono parole reali. 

E così i tre blocchi di programmi che vi daremo sono chiamati dictionary.c, dictionary.h, e speller.c. E così tutto si fa dictionary.c quello che ti viene chiesto di implementare. Carica parole. E 'incantesimo controlli loro, e si assicura che tutto sia inserito correttamente. 

diction.h è solo un file di libreria dichiara che tutte quelle funzioni. E speller.c, stiamo per darvi. Non è necessario modificare qualsiasi di esso. Tutti speller.c non è prendere che, lo carica, controlla la velocità di esso, prove il punto di riferimento di come come rapidamente siete in grado di fare le cose. 

E 'un correttore ortografico. Basta che non si scherza con esso, ma fare sicuri di capire quello che sta facendo. Noi usiamo una funzione chiamata getrusage che test le prestazioni del vostro incantesimo checker. Tutto ciò che fa è fondamentalmente testare il tempo di tutto nel vostro dizionario, quindi assicuratevi di capire. Fare attenzione a non pasticciare con essa o altra cosa non verranno eseguiti correttamente. 

E la maggior parte di questa sfida è per voi ragazzi a modificare realmente dictionary.c. Stiamo per darvi 140.000 parole in un dizionario. Stiamo per darvi un testo file con quelle parole, e noi vogliamo che tu sia in grado di organizzare li in una tabella hash o un trie perché quando ti chiediamo di precisare check-- immaginare se siete magia controllo come l'Odissea di Omero. E 'come questo enorme, enorme prova. 

Immaginate se ogni singolo parola si doveva guardare attraverso una serie di 140.000 valori. Che avrebbe preso per sempre per la vostra macchina per l'esecuzione. Per questo motivo vogliamo organizzare la nostra i dati in strutture dati più efficienti ad esempio una tabella hash o un trie. E poi voi ragazzi può tipo di quando si cerca l'accesso le cose più facilmente e più velocemente. 

E quindi state attenti a risolvere le collisioni. Stai andando a ottenere un mucchio di parole di che iniziano con A. Stai andando a ottenere un mazzo parole che iniziano con B. Fino a voi ragazzi come si desidera risolvere esso. Forse non c'è più funzione hash efficiente che solo la prima lettera del qualcosa, e in modo che tocca a voi ragazzi al tipo di fare quello che vuoi. 

Forse si vuole aggiungere tutte le lettere insieme. Forse si vuole piace fare cose strane per spiegare il numero di lettere, che cosa mai. Fino a voi ragazzi come si desidera fare. Se si vuole fare una tabella di hash, se vuole provare un trie, totalmente a voi. Io vi avvertirà in anticipo che il trie è in genere un po 'più difficile solo perché c'è un sacco ulteriori riferimenti a tenere traccia di. Ma totalmente a voi ragazzi. E 'molto più efficiente nella maggior parte dei casi. Si vuole essere veramente in grado di mantenere traccia di tutti i tuoi puntatori. Come fare la stessa cosa che stavo facendo qui. Quando si sta cercando di inserire valori in una tabella hash o cancellare, fare in modo che tu sia davvero tenere traccia di dove tutto è perché è davvero facile per se sono cercando di inserire come la parola, andy. Diciamo solo che è un vera parola, la parola, andy, in una lista gigante di un parole. 

Se mi capita di riassegnare un puntatore sbagliato, oops, ci va l'interezza della il resto della mia lista collegata. Ora l'unica parola che mi avere è Andy, e ora tutte le altre parole del dizionario sono andati perduti. E così si vuole fare in modo che si tenere traccia di tutti i tuoi puntatori oppure si sta andando ad ottenere enormi problemi nel codice. Disegna le cose con cura passo dopo passo. Lo rende molto più facile pensare. 

E, infine, si vuole essere in grado di testare le prestazioni del vostro programma sul grande tabellone. Se voi ragazzi prendere una guardare CS50 in questo momento, noi abbiamo quello che si chiama il grande tavola. E 'la scheda di valutazione dei più veloci ortografico tempi di controllo in tutti CS50 in questo momento, penso che il top come 10 volte penso che otto di loro sono personale. Vogliamo davvero che voi ragazzi a battere noi. 

Tutti noi stavano cercando di attuare il codice più veloce possibile. Vogliamo che voi ragazzi per cercare di sfidare i noi e implementare più velocemente di tutti noi lattina. E così questo è davvero la prima volta che siamo chiedendo ragazzi di fare un pset che si può davvero fare a qualsiasi metodo tu vuoi. 

Io dico sempre, questo è più simile ad una soluzione di vita reale, giusto? Dico, ehi, ho bisogno che tu faccia questo. Costruire un programma che fa questo per me. Farlo nel modo desiderato. So solo che voglio digiunare. Questa è la tua sfida per questa settimana. Ragazzi, ci sta andando per darvi un compito. Stiamo per darvi una sfida. E poi tocca a voi ragazzi completamente solo capire qual è il più veloce e più modo efficace per implementare questo. Sì? 

PUBBLICO: Stiamo permesso di se wanted alla ricerca metodi più veloci a fare tabelle hash in linea, possiamo fare che e citare il codice di qualcun altro? ANDI PENG: Sì, tutto bene. Quindi, se voi ragazzi leggere il spec, c'è una linea nelle specifiche che dice voi ragazzi sono totalmente gratuito per la ricerca di hash funzioni quali sono alcune delle funzioni hash rapidi a correre le cose attraverso come Finché si cita quel codice. Così alcune persone hanno già capito modi veloci di fare correttori ortografici, di veloce modalità di archiviazione delle informazioni. Totalmente a voi ragazzi, se si vuole prendere proprio questo, giusto? Assicurarsi che si sta citando. La sfida qui davvero che stiamo cercando di testare è fare in modo che si sa il modo per aggirare puntatori. Per quanto si attuazione la reale funzione di hash e venire con come la matematica per farlo, voi potete ricercare qualunque metodi in linea voi ragazzi vogliono. Sì? 

PUBBLICO: Possiamo citare solo utilizzando il [incomprensibile]? 

ANDI PENG: Sì. Si può solo, nel tuo commento, si può citare come, oh, tratto da bla, bla, bla, funzione hash. Qualcuno ha delle domande? Abbiamo effettivamente bellicose attraverso la sezione oggi. Sarò qui a rispondere alle domande pure. 

Inoltre, come ho già detto, ufficio ore stasera e domani. Le specifiche di questa settimana è in realtà super facile e super breve da leggere. Vorrei suggerire di dare un'occhiata, basta leggere attraverso la totalità di esso. 

E Zamyla realtà ti guida attraverso ciascuna delle funzioni è necessario implementare, e quindi è molto, molto chiaro come fare tutto. Giusto per assicurarsi che si sta tenere traccia dei puntatori. Si tratta di un pset molto impegnativo. 

Non è difficile perché, come, oh, i concetti sono molto di più difficile, o si deve imparare tanto nuova sintassi il modo che avete fatto per l'ultimo pset. Questo pset è difficile perché ci sono così tanti punti, e quindi è molto, molto facile una volta si dispone di un bug nel codice non essere in grado per trovare dove tale bug è. 

E così completa e la fede assoluta in te ragazzi di essere in grado di battere il nostro [incomprensibile] ortografia. Io in realtà non ho alcuna mio scritto ancora, ma sto per scrivere la mia. Così, mentre si sta scrivendo tuo, io scriverò la mia. Ho intenzione di provare a fare il mio più veloce della tua. Vedremo chi ha quello più veloce. 

E sì, vedrò tutti voi ragazzi qui il Martedì. Corro un genere come un laboratorio pset. Tutte le sezioni questo settimana sono laboratori pset, così voi ragazzi hanno un sacco di opportunità per chiedere aiuto, le ore d'ufficio come sempre, e non vedo l'ora di la lettura di tutti i codici vostri ragazzi '. Ho quiz qui se ragazzi vogliono venire ottenere quelle. Questo è tutto.