SPEAKER 1: Va bene, quindi questo è CS50 Questa è la fine della settimana di cinque. E ricordare che l'ultima volta che abbiamo iniziato a guardare i dati più elaborato strutture che hanno cominciato a risolvere problemi, che hanno cominciato a introdurre nuovi problemi, ma la chiave di questo era il tipo di filettatura che iniziato a fare da nodo a nodo. Quindi questo, naturalmente, è una lista concatenata. E per concatenata, Voglio dire, c'è solo un filo tra tali nodi. Si scopre che si può fare amatore cose come le liste doppiamente collegate per cui si dispone di una freccia in entrambe le direzioni, che può aiutare con alcune efficienze. Ma questo risolto il problema? Che cosa ha fatto questo problema risolto? Perché abbiamo a cuore il Lunedi? Perché, in teoria, abbiamo a cuore il Lunedi? Che cosa fa? 

PUBBLICO: Possiamo ridimensionare dinamicamente. 

SPEAKER 1: OK, in modo che possiamo ridimensionare dinamicamente. Complimenti entrambi. Così si può ridimensionare in modo dinamico questo struttura di dati, mentre una matrice, richiamo, è necessario conoscere un priori come si desidera molto spazio e se avete bisogno di un po 'più spazio, sei un po 'fuori di fortuna. È necessario creare un array completamente nuovo. Dovete spostare tutti i vostri dati da uno all'altro, infine liberare il vecchio matrice se è possibile, e quindi procedere. Quali appena si sente molto costoso e molto inefficiente, e anzi può essere. Ma questo non è tutto buono. Paghiamo un prezzo, quello che era uno dei prezzi più evidenti noi pagare usando una lista concatenata? 

PUBBLICO: Dobbiamo usare doppio spazio per ognuno. SPEAKER 1: Sì, quindi abbiamo bisogno almeno il doppio dello spazio. In realtà, mi sono reso conto di questa immagine anche un po 'fuorviante, perché il CS50 IDE in un sacco di moderno computer, un puntatore o un indirizzo Non è infatti quattro byte. E 'molto spesso questi giorni otto byte, che mezzi fondo più rettangoli lì in realtà sono un po 'il doppio grande come quello che ho disegnato, il che significa che si sta utilizzando tre volte tanto spazio quanto potremmo avere altrimenti. Ora, allo stesso tempo, siamo ancora parlando byte, giusto? Non stiamo parlando necessariamente megabyte o gigabyte, a meno che questi dati strutture diventano grandi. 

E così oggi cominciamo a considerare come potremmo esplorare i dati in modo più efficiente se in Infatti i dati diventa più grande. Ma proviamo a canonicalizzare le operazioni primi che si può fare su questi tipi di strutture di dati. Quindi qualcosa come un collegato Lista supporta generalmente operazioni come eliminare, inserire, e la ricerca. E che cosa voglio dire con questo? Questo significa solo che di solito, se la gente sta usando lista collegata, essi o qualcun altro ha messo in atto funzioni come cancellare, inserire, e di ricerca, in modo da poter effettivamente fare qualcosa utile con la struttura di dati. Quindi, diamo un rapido sguardo a come potremmo implementare del codice per una lista collegata come segue. 

Quindi questo è solo un po 'di codice C, nemmeno un programma completo che ho davvero frustato rapidamente. Non è in linea nella distribuzione codice, perché non effettivamente eseguito. Ma accorgo ho appena con un commento, ha detto, dot dot dot, c'è qualcosa là, puntini puntini, qualcosa lì. E facciamo solo guardare ciò che le parti sono succose. Così sulla linea tre, ricordare che questo è ora Abbiamo proposto che dichiara un nodo scorso tempo, uno di quegli oggetti rettangolari. Ha un int che chiameremo N, ma potremmo chiamarla nulla, e poi una stella nodo struct chiamata successiva. E tanto per essere chiari, che secondo Linea, sulla linea sei, che cosa è? Che cosa sta facendo per noi? Perché certamente sembra più criptico rispetto ai nostri soliti variabili. 

PUBBLICO: Fa muovere più di un. 

SPEAKER 1: E 'la fa muovere più di un. E per essere più precisi, si memorizza l'indirizzo del nodo che è destinata ad essere semanticamente accanto ad esso, giusto? Quindi non sta andando a spostare necessariamente nulla. E 'solo andando a memorizzare un valore, che è andando ad essere l'indirizzo di altri nodi, ed è per questo che abbiamo detto struct nodo stella, la stella che indica un puntatore o un indirizzo. OK, ora se si assume che abbiamo questo N a nostra disposizione, e facciamo assumere che qualcun altro ha inserito un sacco di numeri interi in una lista collegata. E quella lista collegata è puntata da un certo punto una chiamata lista variabile che è passato qui come parametro, Come posso fare per linea 14 di attuazione ricerca? In altre parole, se io sono l'attuazione funzione la cui scopo nella vita è quello di prendere un int e poi il inizio di una lista collegata, che è un puntatore alla lista collegata. Come prima, che credo David era il nostro volontario il Lunedi, lui stava indicando l'intera lista collegata, è come se stiamo passando David in quanto il nostro argomento qui. Come possiamo fare per l'attraversamento di questa lista? Beh, si scopre che anche se puntatori sono relativamente nuovo ora a noi, possiamo fare questo relativamente semplicemente. 

Ho intenzione di andare avanti e dichiarare una variabile temporanea che per convenzione sta solo andando per essere chiamato puntatore, o PTR, ma si potrebbe chiamare tutto quello che vuoi. E ho intenzione di inizializzare per l'inizio della lista. Così si può sorta di pensare a questo come me l'insegnante, l'altro giorno, tipo di punta a qualcuno tra i nostri umani come volontari. Quindi sono una variabile temporanea che è solo indicando la stessa cosa che il nostro casualmente chiamato volontario Davide stava anche facendo notare. Ora, mentre puntatore è non nullo, perché il richiamo che nulla è un valore speciale sentinel la delimita la fine della lista, Così, mentre io non sto indicando la terra come la nostra ultima volontario era, andiamo avanti e procedere come segue. Se pointer-- e ora io voglio tipo di a fare quello che abbiamo fatto con lo studente structure-- se il puntatore punto accanto equals-- piuttosto, se il puntatore puntino N è uguale uguaglia la variabile N, la argomentazione che è stata passata in, poi voglio andare avanti e dire ritorno vero. Ho trovato il numero N all'interno di uno dei nodi della mia lista collegata. Ma il punto non è più lavora in questo contesto, perché puntatore, PTR, è infatti un puntatore, un indirizzo, abbiamo effettivamente possibile meravigliosamente infine utilizzare un pezzo di sintassi quel tipo di marche senso intuitivo e realtà utilizzare una freccia qui, il che significa che vanno dal che indirizzo all'intero lì. Quindi è molto simile a spirito l'operatore punto, ma perché puntatore non è un puntatore e non un struct vera e propria, usiamo la freccia. 

Quindi, se il nodo corrente che, la variabile temporanea, sto indicando non è N, che cosa voglio fare? Bene, con i miei volontari umani che abbiamo avuto qui l'altro giorno, se il mio primo essere umano non è quello che ho vuole, e forse il secondo umano non è quello che voglio, e il terzo, mi bisogno di continuare a muoversi fisicamente. Come come faccio a passo attraverso una lista? Quando abbiamo avuto un array, appena fatto come me plus plus. Ma in questo caso, è sufficiente fare puntatore, ottiene, puntatore, il prossimo. In altre parole, il campo successivo è come tutte le mani di sinistra che i nostri volontari il Lunedi stavano usando per puntare a qualche altro nodo. Quelli erano i loro vicini di. 

Quindi, se voglio fare un passo in questa lista, Non posso fare io plus plus più, Io invece devo dire Io, puntatore, sta andando per uguagliare qualunque sia il campo successivo è, Il campo successivo è il campo successivo è, seguendo tutte quelle mani sinistra che abbiamo avuto sul palco di puntamento per alcuni valori successivi. E se avrò finito che tutta iterazione, e, infine, mi ha colpito nulla non avendo N trovato ancora, appena ritorno falso. Così ancora una volta, tutto quello che stiamo facendo qui, come per l'immagine di un momento fa, è a partire dalla punta verso la inizio della lista, presumibilmente. E poi posso controllare, è il valore Sto cercando pari a nove? Se è così, torno vero e ho finito. Se no, aggiorno la mia mano, Puntatore AKA, per puntare presso la sede del prossimo freccia e quindi la posizione successiva della freccia, e la successiva. Sto semplicemente camminando attraverso questo array. 

Così ancora una volta, chi se ne frega? Come quello che è questo un ingrediente per? Beh, ricordiamo che abbiamo introdotto il concetto di una pila, che è un tipo di dato astratto, in quanto si tratta di non è una cosa C, non è una cosa CS50, è un'idea astratta, questa idea di accatastamento cose uno sopra l'altro che può essere implementato in mazzi di modi diversi. E un modo abbiamo proposto è stato con un array, o con una lista collegata. E si scopre che canonicamente, un pila supporta almeno due operazioni. E le parole d'ordine sono spinta, a spingere qualcosa nello stack, come un nuovo vassoio nel sala da pranzo, o pop, il che significa per rimuovere il più alto vassoio dalla pila in sala sala, e poi magari un po ' altre operazioni pure. Così come potremmo definire la struttura che ora stiamo chiamando una pila? 

Bene, abbiamo tutti i requisiti sintassi a nostra disposizione in C. Io dico, darmi una definizione di tipo una struttura all'interno di una pila, Io vado a dire è un array, di un tutta una serie di numeri e quindi le dimensioni. Quindi, in altre parole, se voglio per implementare questo in codice, lasciatemi andare e solo tipo di disegnare ciò che questo sta dicendo. Quindi questo sta dicendo, mi dia una struttura che ha ottenuto un array, e io non so che cosa è la capacità, è apparentemente una costante che ho definito altrove, e va bene. Ma supponiamo che sia solo uno, due, tre, quattro, cinque. Così capacità è di 5. Questo elemento interno del mio struttura sarà chiamato numeri. E poi ho bisogno di uno altra variabile a quanto pare chiamato dimensione che inizialmente ho intenzione di stipulare viene inizializzato a zero. Se non c'è niente in lo stack, la dimensione è pari a zero, e suoi valori spazzatura nei numeri. Non ho idea di che cosa è in là ancora. 

Quindi, se voglio spingere qualcosa nello stack, supponiamo che io chiamo la funzione Push, e Dico spingere 50, come il numero 50, dove proporrebbe Vorrei attirare in questo array? Ci sono cinque diverse risposte possibili. Dove si vuole spingere il numero 50? Se l'obiettivo qui, di nuovo, chiamare il funzione push, passare a un argomento di 50, dove lo metto? Cinque possible-- probabilità del 20% di indovinare correttamente. Sì? 

PUBBLICO: Estrema destra. 

SPEAKER 1: Estrema destra. Vi è ora una probabilità del 25% di indovinare correttamente. In modo che sarebbe realmente bene. Per convenzione, lo dirò con una matrice, avremmo generalmente iniziare a sinistra, ma potremmo certamente iniziare a destra. Così lo spoiler qui sarebbe Sono probabilmente andando a disegnare sulla sinistra, proprio come in una matrice normale dove Comincio andare a sinistra a destra. Ma se si può capovolgere l'aritmetica, bene. Non è solo convenzionale. Ok, ho bisogno di fare un altro cambiamento però. Ora che ho spinto qualcosa nello stack, e adesso? 

Va bene, devo incrementare la dimensione. Così mi permetta di andare avanti e basta aggiornare questo, che era pari a zero. E invece ora, sto andando a mettere in valore uno. E ora supponiamo che io spingo un altro numero sullo stack, come 51. Beh, devo fare un altro cambiamento, che è fino alla dimensione due. E poi immagino io spingere un altro numero sullo stack come 61, ora ho bisogno di aggiornare il formato un altro tempo, e ottenere il valore 3 come dimensione. E ora supponiamo che io chiamo pop. Ora pop, per convenzione, non prende un argomento. Con uno stack, tutta punto della metafora cassetto è che non si dispone di discrezionalità per andare a prendere quel vassoio, tutto quello che puoi fare è pop quella superiore da pila, solo perché. Questo è ciò che questa struttura dati fa. 

Quindi, che la logica, se io dire pop, che cosa viene fuori? Così 61. Allora, qual è veramente il computer intenzione di fare in memoria? Che cosa significa il mio codice ha a che fare? Cosa vorresti proporre cambiamo sullo schermo? Che cosa dovrebbe cambiare? Scusate? Così ci liberiamo di 61. Così posso sicuramente farlo. E posso liberarmi di 61. E poi cosa altro cambiamento deve accadere? Dimensioni ha probabilmente tornare a due. E così va bene. Ma aspettate un minuto, formato un momento fa aveva tre anni. Diciamo solo fare un controllo di integrità rapido. Come Non sapevamo che ci voleva sbarazzarsi di 61? Perché stiamo popping. E così ho questo secondo dimensioni proprietà. 

Aspetta un attimo, io sono ripensando a seconda settimana quando abbiamo iniziato a parlare array, dove questa era la posizione a zero, questa era la posizione uno, questo era la posizione due, questa è la posizione di tre, quattro, sembra che il rapporto tra dimensione e l'elemento che voglio rimuovere dalla matrice sembra essere proprio quello? Dimensione meno uno. E così che è come gli esseri umani sappiamo 61 viene prima. Come sta il computer sta per sapere? Quando il codice, dove probabilmente vuole fare una taglia meno, così tre meno uno è di due, e che significa che vogliamo sbarazzarci di 61. E allora possiamo davvero aggiornare le dimensioni in modo che le dimensioni ora va da tre a due. E proprio per essere pedante, io vado a proporre che ho finito, giusto? Avete proposto intuitivamente correttamente dovrei liberarmi di 61. Ma io non ho genere di sorta di deciso di eliminare 61? Ho effettivamente dimenticato che in realtà è lì. E ripensare a PSET4, se avete letto l'articolo sulla medicina legale, il PDF che abbiamo avuto ragazzi leggere, oppure leggerà questa settimana per PSET4. Ricordiamo che si tratta in realtà di germano l'idea di computer forensics. Quello che un computer non è generalmente dimentica proprio dove qualcosa è, ma non va e come cercare di graffiare fuori o di esclusione quei bit con zero e uno o qualche altro modello casuale a meno che non te lo fanno deliberatamente. Quindi la vostra intuizione era a destra, cerchiamo di sbarazzarsi di 61. Ma in realtà, non dobbiamo dare fastidio. Abbiamo solo bisogno di dimenticare che è lì, cambiando la nostra dimensione. 

Ora c'è un problema con questo stack. Se continuo a spingere le cose nello stack, che cosa è ovviamente succederà nel giro di poco tempo momenti? Stiamo andando a corto di spazio. E che cosa facciamo? Stiamo tipo di fottuti. Questa implementazione non consente noi ridimensionare la matrice, perché usando questa sintassi, se ripensare a seconda settimana, una volta che hai dichiarato la dimensione di una matrice, non abbiamo ancora visto un meccanismo dove è possibile modificare la dimensione della matrice. E infatti C non ha questa caratteristica. Se dici darmi cinque Nths, li chiamano numeri, è tutto quello che hai intenzione di farlo. Così facciamo ora a partire da Lunedi, abbiamo la capacità di esprimere una soluzione però, abbiamo solo bisogno di modificare la definizione di una pila di non essere certo di matrice hard-coded, ma solo per memorizzare un indirizzo. 

Ora, perché è questo? Ora non ci resta che stare bene con il fatto che quando il mio programma viene eseguito, Sto presumibilmente intenzione di chiedere l'umano, quanti numeri vuoi salvare? Quindi l'ingresso deve venire da qualche parte. Ma una volta che so che numero, quindi posso solo utilizzare ciò che funziona per dare me un pezzo di memoria? Posso usare malloc. E posso dire qualsiasi numero di byte Voglio tornare per questi Nths. E tutto quello che ho per memorizzare i numeri variabile qui dentro questo struct dovrebbe essere quello? Ciò che in realtà va nel numeri in questo scenario? Sì, un puntatore al primo Byte di quel pezzo della memoria, o più specificamente, l'indirizzo del primo di tali bytes. Non importa se si tratta di un byte o un miliardo di byte, Ho solo bisogno di preoccuparsi prima. Perché ciò che le garanzie malloc e le mie garanzie del sistema operativo, è che il pezzo di memoria I ottenere, che sta per essere contigui. Non ci sara essere lacune. Quindi, se ho chiesto 50 byte o 1.000 byte, sono tutti andando essere back to back to back. E fino a quando mi ricordo di quanto è grande, come tanto che ho chiesto, tutto quello che ho bisogno di sapere è il primo indirizzo. 

Così ora abbiamo la capacità di codice. Anche se, sta andando a prendere noi più tempo per scrivere questo in su, ora abbiamo potuto riallocare che la memoria da solo la memorizzazione di un indirizzo diverso lì se vogliamo una più grande o addirittura un pezzo inferiore di memoria. Così qui per un fuori commercio. Ora abbiamo dinamismo. Noi abbiamo ancora contiguità sto sostenendo. Perché malloc ci darà un blocco contiguo di memoria. Ma questo sta per essere un dolore il collo per noi, il programmatore, al codice realmente in su. E 'solo più lavoro. Abbiamo bisogno di codice simile a quello che ero sbattere fuori solo un momento fa. Molto fattibile, ma aggiunge complessità. E così il tempo di sviluppo, programmatori il tempo è ancora un altro risorsa che potremmo aver bisogno di spendere un po 'di tempo per ottenere nuove funzionalità. E poi, naturalmente, c'è una coda. Non andremo in questo uno in più dettagliato. Ma è molto simile nello spirito. Ho potuto implementare una coda, e le sue operazioni corrispondenti, enqueue o dequeue, come aggiungere o rimuovere, è solo un modo più fantasioso di dirlo, enqueue o dequeue, come segue. Posso solo darmi una struct ha di nuovo allineamento di un numero, ha di nuovo una dimensione, Ma perché ora serve per tenere traccia della parte anteriore di una coda? Non avevo bisogno di sapere la parte anteriore del mio stack. Ebbene, se ancora per un queue-- facciamo solo difficile codice come avere come cinque interi qui potenzialmente. Quindi questo è zero, uno, due, tre, quattro. Questo sta per essere chiamato di nuovo i numeri. E questo sarà chiamato dimensioni. 

Perché non è sufficiente di avere solo le dimensioni? Bene, spingere gli stessi numeri. Così ho pushed-- io accodato, o spinto. Ora ti enqueue 50, e poi 51, e poi 61, e puntini puntini. Ecco, questo è enqueue. I accodato 50, poi 51, poi 61. E che sembra identico ad una pila finora, tranne che ho bisogno di fare un cambiamento. Ho bisogno di aggiornare queste dimensioni, così vado da zero a uno a due per tre ora. Come faccio a DEQUEUE? Che cosa succede con dequeue? Chi dovrebbe venire fuori questa lista prima se è la linea presso l'Apple Store? Quindi 50. Quindi è una specie di complicato questo momento. Considerando che l'ultima volta che era super facile da fare solo un formato meno, Ho arrivare alla fine del mio allineamento efficacemente dove i numeri sono, rimuove 61. Ma io non voglio rimuovere 61. Voglio prendere 50, che era lì a 05:00 in fila per il nuovo iPhone o roba del genere. E così, per sbarazzarsi di 50, I non si può solo fare questo, giusto? Posso barrare 50. Ma abbiamo appena detto noi non c'è bisogno di essere così anale da graffiare fuori o nascondere i dati. Possiamo solo dimenticare dove si trova. 

Ma se cambio la mia taglia subito per due, è questo sufficienti informazioni di sapere cosa sta succedendo nella mia coda? Non proprio. Come la mia taglia è di due, ma dove fa la coda cominciare, soprattutto se ho ancora questi stessi numeri in memoria. 50, 51, 61. Così ho bisogno di ricordare ora dove il fronte è. E così come ho proposto su lì, avremo appena chiamato Fronte all'ennesima potenza, la cui iniziale valore deve essere stato quello che? Zero, solo l'inizio della lista. Ma ora oltre a decremento le dimensioni, si incrementa il proprio fronte. Ora qui è un altro problema. Così una volta Continuo ad andarci. Supponiamo che questo è il numero di come 121, 124, e poi, dannazione, Sono fuori di spazio. Ma aspettate un minuto, non lo sono. Quindi, a questo punto della storia, supponiamo che la dimensione è uno, due, tre, quattro, così supporre che il dimensione è quattro, la parte anteriore è uno, così 51 è nella parte anteriore. Voglio mettere un altro numero qui, ma, dannazione, sono fuori di spazio. Ma io non sono davvero, giusto? Dove ho potuto mettere un po ' valore aggiunto, come la 171? Sì, ho potuto solo tipo di tornare laggiù, giusto? E poi attraversare la 50, o basta sovrascrivere con 171. E se vi state chiedendo perché i nostri numeri si sono così casuale, questi sono comunemente prese di computer corsi di scienza a Harvard dopo CS50. Ma quella era una buona ottimizzazione, perché ora non sto sprecando spazio. Devo ancora ricordare quanto è grande questa cosa è totale. Sono le cinque totale. Perché non voglio iniziare a sovrascrivere 51. Così ora sono ancora fuori di spazio, così lo stesso problema di prima. Ma si può vedere come la società nel codice, probabilmente dovuto scrivere un po 'di più complessità per realizzare questo obiettivo. E in effetti, che cosa operatore in C probabilmente lascia si magicamente fare questo la circolarità? Sì, l'operatore modulo, il segno di percentuale. Allora, qual è genere di freddo su una coda, anche se manteniamo gli array di disegno come queste linee rette, come, se si tipo di pensare a questo come curva intorno come un cerchio, poi basta intuitivamente che tipo di lavori mentalmente Penso che un po 'più pulito. Si sarebbe ancora necessario implementare che modello mentale nel codice. Quindi non è così difficile, in ultima analisi, di attuare, ma abbiamo ancora perde la size-- piuttosto, il capacità di ridimensionare, se non facciamo questo. 

Dobbiamo eliminare l'array, abbiamo sostituirlo con un unico puntatore, e poi da qualche parte nel mio codice ho una chiamata quale funzione per creare effettivamente la matrice numeri chiamati? Malloc, o qualche simile la funzione, esattamente. Tutte le domande di pile o code. Sì? Bella domanda. Cosa modulo usereste qui. Quindi in generale, quando si utilizza mod, si farebbe con la dimensione della intera struttura dati. Così qualcosa come cinque o la capacità, se è costante, probabilmente è coinvolto. Ma solo facendo modulo cinque probabilmente non è sufficiente, perché abbiamo bisogno di sapere fare noi avvolgere intorno qui o qui o qui. Quindi, probabilmente sei anche andando a voler coinvolgere la dimensione della cosa, o la variabile anteriore pure. Quindi è proprio questo relativamente semplice espressione aritmetica, ma modulo sarebbe l'ingrediente fondamentale. 

Quindi, cortometraggio, se vuoi. Un'animazione che alcuni gente di un'altra università messo insieme che abbiamo adatto per questa discussione. Si tratta di Jack apprendimento della fatti circa le code e le statistiche. 

FILM: C'era una volta, c'era un ragazzo di nome Jack. Quando si trattava di farsi degli amici, Jack non ha avuto un talento. Così Jack andò a parlare con il ragazzo più popolare che conosceva. Andò a Lou e chiese, cosa devo fare? Lou vide che il suo amico era davvero in difficoltà. Beh, ha iniziato, solo guarda come sei vestito. Non hai i vestiti con un look diverso? Sì, ha detto Jack. Certo che lo faccio. Vieni a casa mia e Io farò vedere a voi. Così se ne andarono a Jack. E Jack ha mostrato Lou casella dove teneva tutte le sue camicie, i suoi pantaloni e le calze. Lou ha detto, vedo che hai tutti i vostri vestiti in un mucchio. Perché non indossare qualche altri di tanto in tanto? 

Jack ha detto, bene, quando ho rimuovere i vestiti e calzini, Io li lavo e mettere loro via nella scatola. Poi viene il prossimo mattina, e fino io hop. Vado in scatola e ottenere i miei vestiti fuori dalla parte superiore. Lou si rese conto in fretta il problema con Jack. Continuava a vestiti, CD, e libri in pila. Quando ha raggiunto per qualcosa da leggere o da indossare, aveva scelto il libro superiore o la biancheria intima. Poi, quando ebbe finito, lui avrebbe messo subito indietro. Indietro andrebbe, in cima alla pila. So che la soluzione, ha detto un forte trionfante. È necessario imparare a iniziare a utilizzare una coda. Lou ha preso i vestiti di Jack e li appesi nell'armadio. E, dopo aver svuotato la scatola, ha appena lanciò. 

Poi disse, ora Jack, alla fine del il giorno, mettere i vestiti a sinistra quando li metti via. Poi, domani mattina quando si vedere la luce del sole, ottenere i vostri vestiti sulla destra, dalla fine della linea. Non vedi? ha detto Lou. Sarà così bello. Potrai indossare tutto una volta prima di indossare qualcosa di due volte. E con tutto ciò che in coda nel suo armadio e ripiano, Jack ha iniziato a sentirsi abbastanza sicuro di se stesso. Tutto grazie a Lou e la sua meravigliosa coda. SPEAKER 1: Va bene, è adorabile. Quindi, ciò che è stato realmente accadendo in sotto la cappa ora? Che abbiamo puntatori, che abbiamo malloc, che abbiamo la capacità di creare blocchi di memoria per noi stessi dinamicamente. Quindi questo è un quadro che intravisto proprio l'altro giorno. Non abbiamo davvero soffermarsi su di esso, ma questa immagine è andata avanti sotto la cappa da settimane. E così ciò rappresenta, solo un rettangolo che abbiamo disegnato, la memoria del computer. E forse il computer, o CS50 ID, ha un gigabyte di memoria o RAM o due gigabyte o quattro. Non ha molta importanza. Il sistema operativo Windows o Mac OS o Linux, essenzialmente permette al vostro programma pensare che abbia accesso alla totalità del memoria del computer, anche se si potrebbe essere in esecuzione più programmi contemporaneamente. Quindi, in realtà, che in realtà non funziona. Ma è una specie di illusione dato a tutti i programmi. Quindi, se tu avessi due giga di RAM, questo è come il computer potrebbe pensare ad esso. 

Ora guarda caso, uno di questi cose, uno di questi segmenti di memoria, è chiamata una pila. E in effetti in qualsiasi momento finora nella scrittura di codice che hai chiamato un funzione, per esempio principale. Ricordo che ogni volta che ho la memoria del computer disegnato, Ho sempre disegnare una sorta di mezzo di un rettangolo qui e non si preoccupano di parlare su ciò che è al di sopra. Perché quando principale si chiama, io rivendico che si ottiene questo frammento di memoria che scende qui. E se principale chiamato una funzione come scambio, ben di swap va qui. E si scopre, che è dove è finire. Su una cosa chiamata una pila all'interno della memoria del computer. Ora, alla fine della giornata, questo è solo gli indirizzi. E 'come zero byte, Byte uno, byte 2 miliardi. Ma se ci pensate come questo oggetto rettangolare, tutto quello che stiamo facendo ogni tempo che noi chiamiamo una funzione è stratificazione una nuova fetta di memoria. Stiamo dando quella funzione una fetta della propria memoria per funzionare con. 

Ed ora ricordare che questo è importante. Perché se noi abbiamo qualcosa di simile scambio e due variabili locali come A e B e cambiamo quei valori da uno e due a due e uno, richiamo che quando ritorna di swap, è come se questa fetta di memoria è appena andato. In realtà, è ancora lì forense. E qualcosa è ancora realmente lì. Ma concettualmente, è come anche se è completamente sparito. E così principale non conosce alcun lavoro che è stato fatto in quella funzione di scambio, a meno che in realtà è passato in quelli argomenti di puntatore o di riferimento. Ora, la soluzione fondamentale a questo problema con lo scambio sta passando le cose in base all'indirizzo. Ma si scopre, anche, che cosa è sta succedendo sopra di tale parte del rettangolo tutto questo tempo è ma non c'è più memoria lassù. E quando si dinamicamente allocare la memoria, se è dentro di GetString, che abbiamo fatto per voi in CS50 biblioteca, o se voi ragazzi chiamare malloc e chiedere il sistema operativo per un pezzo di memoria, non viene dallo stack. Proviene da un altro luogo nella memoria del computer che si chiama l'heap. E non è affatto differente. E 'la stessa RAM. E 'la stessa memoria. E 'solo la RAM che è fino lì invece di quaggiù. 

E così che cosa significa? Beh, se il computer dispone una quantità limitata di memoria e la pila sta crescendo, così a parlare, e l'heap, secondo a questa freccia, è in crescita verso il basso. In altre parole, ogni ora si chiama malloc, sei stato dato una fetta della memoria dall'alto, allora forse un po 'più basso, poi un po' più basso, ogni volta che si chiama malloc, mucchio, è l'utilizzo, è una specie di crescita, cresce sempre più vicino a quello che? Lo stack. Così fa questo sembra una buona idea? Voglio dire, dove non è davvero chiaro cos'altro si può fare se si solo avere una quantità limitata di memoria. Ma questo è sicuramente male. Queste due frecce sono su una Crash Course uno per l'altro. 

E si scopre che cattivo, le persone che sono particolarmente buoni con la programmazione, e cercando di incidere in computer, in grado di sfruttare questa realtà. Infatti, prendiamo in considerazione un piccolo frammento. Quindi questo è un esempio si può leggere circa più in dettaglio su Wikipedia. Ti segnaliamo voi al articolo, se curioso. Ma c'è un attacco generale noto come buffer overflow che esiste finché umani hanno avuto la capacità di manipolare memoria del computer, in particolare in C. Quindi questo è un programma molto arbitraria, ma leggiamo dal basso verso l'alto. Principale in argc char stella argv. Quindi è un programma che prende argomenti della riga di comando. E tutti i principali fa apparentemente è chiamata una funzione, lo chiamano F per semplicità. E passa in ciò? Argv di uno. Così passa in qualunque F la parola è che l'utente ha digitato al prompt dopo la nome del programma a tutti. Così tanto come Cesare o Vigenere, che si potrebbe ricordare facendo con argv. 

Allora, qual è F? F prende in una stringa come unico argomento, AKA una stella char, stesso cosa, come una stringa. E si chiama arbitrariamente bar in questo esempio. E poi char c 12, solo in termini profani, ciò che è char c staffa 12 che fa per noi? Che cosa fare? L'allocazione della memoria, in particolare 12 byte per 12 caratteri. Esattamente. E poi l'ultima riga, mescolare e copia, probabilmente avete non si vedono. Questa è una copia della stringa funzione la cui scopo nella vita è quello di copiare il suo secondo argomento nel suo primo argomento, ma solo fino a un certo numero di byte. Così il terzo argomento, dice, quanti byte si dovrebbe copiare? La lunghezza della barra, qualunque sia l'utente ha digitato in. E il contenuto di bar, tale stringa, sono copiati nella memoria puntato a C. 

Quindi, questo sembra un po 'stupido, e lo è. E 'un esempio forzato, ma è rappresentante di una classe di vettori di attacco, un modo di attaccare un programma. Tutto è bello e buono se l'utente tipi in una parola che è 11 caratteri o meno, più la barra rovesciata zero. Che cosa succede se l'utente digita in più di 11 o 12 o 20 o 50 caratteri? Che cosa è questo programma intenzione di fare? Colpa Potenzialmente seg. Sta andando copiare ciecamente tutto nella barra in alto alla sua lunghezza, che è letteralmente tutto in bar, nell'indirizzo puntato a C. Ma C solo ha preventivamente dato come 12 byte. Ma non c'è alcun controllo aggiuntivo. Non c'è, se le condizioni. Non c'è alcun controllo qui l'errore. 

E così quello che questo programma è intenzione di fare è appena ciecamente copiare una cosa all'altra. E così, se traiamo questo come un quadro, ecco solo un frammento di spazio di memoria. Così notiamo in fondo, abbiamo avere la variabile locale bar. In modo che il puntatore che sta per store-- piuttosto che l'argomento locale che è andando a memorizzare la barra di stringa. E poi notare solo sopra di esso in una pila, perché ogni volta che si chiede per la memoria in pila, va un po ' sopra di esso pittoricamente, nota che abbiamo 12 byte lì. Quello in alto a sinistra è C staffa zero e il fondo quello di destra è C staffa 11. Questo è solo il modo i computer andando a stenderlo. Quindi, solo intuitivamente, se ha più bar di 12 caratteri in totale, tra cui il backslash a zero, dove si trova il 12 o la staffa C 12 intenzione di andare? O meglio dove è il 12 ° carattere o il carattere di 13 °, il personaggio centesima andare per finire nella foto? Sopra o sotto? 

Giusto, perché, anche se lo stack in sé cresce verso l'alto, una volta che hai messo roba in esso, per motivi costruttivi, mette la memoria dall'alto verso il basso. Quindi, se hai più di 12 byte, avete intenzione di iniziare a sovrascrivere bar. Ora che è un bug, ma è Non è un grosso problema. Ma è un grosso problema, perché c'è più cose in corso in memoria. Quindi, ecco come potremmo mettere ciao, per essere chiari. Se ho digitato ciao al prompt. Backslash a zero H-E-L-L-O, finisce dentro quei 12 byte, e siamo super sicuro. Tutto bene. Ma se digito qualcosa più a lungo, potenzialmente è andando a insinuarsi nello spazio bar. Ma peggio ancora, si trasforma tutto questo tempo, anche se non abbiamo mai parlato di esso, lo stack viene utilizzato per altre cose. Non sono solo le variabili locali. 

C è un linguaggio di livello molto basso. Ed è una sorta di segreto utilizza lo stack anche a ricordare quando un funzione viene chiamata, cosa l'indirizzo è della funzione precedente, in modo che possa tornare indietro a quella funzione. Così, quando le chiamate principali scambiano, tra le cose inseriti nello stack Non sono scambia solo le variabili locali, o dei suoi argomenti, anche segretamente spinti nello stack come rappresentato al taglio il rosso, è l'indirizzo del principale fisicamente nella memoria del computer, in modo che quando è fatto di swap, il computer sa che ho bisogno di tornare a principale e terminare l'esecuzione della funzione principale. Quindi questo è pericoloso ora, perché se l'utente digita in ben più di ciao, tale che l'input dell'utente clobbers o sovrascrive quella sezione rosso, logicamente se del computer solo intenzione di assumere ciecamente che i byte in quella fetta rosso sono l'indirizzo al quale deve restituire, cosa succede se l'avversario è abbastanza intelligente o la fortuna di mettere una sequenza di byte lì che sembra un indirizzo, ma è l'indirizzo del codice che lui o lei vuole il computer per eseguire invece di principale? 

In altre parole, se la cosa utente sta digitando al prompt, non è solo qualcosa come innocuo ciao, ma in realtà è il codice che è equivalente eliminare tutti i file di questo utente? O e-mail la propria password a me? O avviare la registrazione loro battiture, giusto? C'è un modo, cerchiamo di stipulare oggi, che potrebbero digitare non solo ciao il loro nome o il mondo, potevano essenzialmente passare in codice, zero e quelli, che il computer errori sia per il codice e un indirizzo. Così anche se un po astrattamente, se il utente digita abbastanza codice contraddittorio che saremo generalizzare qui A. A è attacco o avversari. Quindi, solo cose cattive. Non ci interessa circa il numeri o gli zeri o quelli oggi, in modo tale che si finisce per sovrascrivendo quella sezione rosso, notare che sequenza di byte. O 835 C zero otto a zero. E ora come l'articolo di Wikipedia qui ha proposto, se ora effettivamente iniziare etichettatura i byte nel computer di la memoria, ciò che l'articolo Wikipedia proponente è che, quello che se l'indirizzo di quel byte alto a sinistra è 80 C 0 3508. 

In altre parole, se il cattivo è abbastanza intelligente con il suo codice per mettere in realtà una serie qui che corrisponde all'indirizzo del codice lui o lei iniettato nel computer, può ingannare il computer a fare qualsiasi cosa. Rimozione dei file, e-mail cose, annusando il traffico, letteralmente qualsiasi cosa potrebbe essere iniettato nel computer. E così un buffer overflow attacco al suo interno è solo uno stupido, stupido prevalente di un array non ha avuto i suoi confini controllati. E questo è ciò che è super pericoloso e allo stesso tempo super potente in C è che abbiamo davvero l'accesso a qualsiasi punto della memoria. Sta a noi, i programmatori, che scrivono il codice originale per controllare la lunghezza di qualsiasi maledettamente array che stiamo manipolando. Quindi, per essere chiaro, qual è la soluzione? Se il rollback a questo codice, non dovrei solo modificare la lunghezza della barra, cosa cosa dovrei controllare? Che altro dovrei fare per prevenire questo attacco del tutto? Io non voglio solo dire alla cieca che è necessario copiare tanti byte come è la lunghezza della barra. Voglio dire, come copiare molti byte, come sono in bar fino al allocato memoria, o 12 al massimo. Quindi ho bisogno di un qualche tipo di condizione if che fa controllare la lunghezza della barra, ma se supera 12, abbiamo il codice solo difficile 12 come la massima distanza possibile. Altrimenti il ​​cosiddetto tampone attacco overflow può succedere. Nella parte inferiore di dette slitte, se siete curiosi di saperne di più è l'articolo originale reale se volete dare un'occhiata. 

Ma ora, tra i prezzi pagati qui era inefficienze. Così che era un rapido basso livello di sguardo a ciò che problemi possono sorgere ora che abbiamo avere accesso alla memoria del computer. Ma un altro problema che abbiamo già inciampato il Lunedi era solo l'inefficienza di una lista collegata. Siamo tornati al tempo lineare. Non abbiamo più un array contiguo. Non abbiamo accesso casuale. Non possiamo usare la notazione parentesi quadra. Abbiamo letteralmente dobbiamo usare un ciclo while come quella che ho scritto poco fa. Ma il Lunedi, abbiamo dichiarato di essere in grado strisciare indietro nel regno di efficienza raggiungimento di qualcosa che è logaritmica forse, o meglio ancora, forse anche qualcosa che è cosiddetto tempo costante. Quindi, come possiamo farlo usando questi nuovi strumenti, questi indirizzi, i puntatori, e filettatura cose della nostra? Bene, supponiamo che qui, si tratta di un gruppo di numeri che vogliamo conservare in un struttura di dati e di ricerca in modo efficiente. Possiamo assolutamente tornare indietro a settimana due, gettare queste in una matrice, e la ricerca utilizzando la ricerca binaria. Divide et impera. E infatti hai scritto ricerca binaria in PSET3, dove è stato implementato il programma di scoperta. Ma si sa che cosa. C'è una specie di più modo intelligente di fare questo. E 'un po' di più forse sofisticato e ci permette di vedere perché binario ricerca è molto più veloce. In primo luogo, introduciamo il concetto di un albero. Che anche se in alberi realtà tipo di crescere come questo, nel mondo di calcolatore la scienza che tipo di crescere verso il basso come un albero di famiglia, dove si ha i vostri nonni o bisnonni o roba del genere nella parte superiore, il patriarca e la matriarca della famiglia, solo un cosiddetta radice, nodo, sotto quali sono i suoi figli, sotto del quale sono i suoi figli, o suoi discendenti più in generale. E chiunque appesi fuori il fondo della famiglia albero, oltre ad essere la più giovane della famiglia, può anche essere solo genericamente chiamato le foglie dell'albero. 

Quindi questo è solo un mucchio di parole e definizioni per qualcosa chiamato un albero di computer scienza, proprio come un albero genealogico. Ma c'è incarnazioni amatore di alberi, uno dei quali viene chiamato un albero binario di ricerca. E si può sorta di presa in giro a parte ciò che questa cosa fa. Beh, è ​​binario in che senso? Da dove viene il binario viene da qui? Scusate? Non è tanto una o. E 'più che ciascuno dei nodi non ha più di due figli, come vediamo qui. In generale, un tree-- e i vostri genitori e nonni può avere come molti ragazzi o nipotini come realmente vogliono, e così per esempio non ci abbiamo tre bambini fuori quel nodo mano destra, ma in un albero binario, un nodo ha zero, uno o due bambini al massimo. E questa è una bella proprietà, perché se è ricoperto da due, stiamo andando a essere in grado di ottenere un po 'logaritmo in base due azione succedendo qui alla fine. Così abbiamo qualcosa logaritmica. Ma più su che in un momento. Cerca albero significa che i numeri sono disposto in modo tale che il bambino sinistra di valore è maggiore rispetto alla radice. E suo figlio destro è più grande della radice. In altre parole, se si prende una qualsiasi delle nodi, i cerchi in questa immagine, e guarda la sua sinistra bambino e suo figlio destro, il primo dovrebbe essere inferiore, il secondo dovrebbe essere superiore. Così la sanità mentale di controllo 55. E 'figlio rimane è 33. E 'meno. 55, suo figlio destro è 77. E 'più grande di. E questa è una definizione ricorsiva. Potremmo controllare ogni uno di quelli nodi e lo stesso schema terrebbe. 

Così che cosa è bello in una albero binario di ricerca, è che uno, possiamo attuarlo con una struttura, proprio come questo. E anche se ci stiamo buttando un sacco di strutture al vostro, sono un po ' intuitivo ora si spera. La sintassi è ancora arcana di sicuro, ma il contenuto di un nodo in questo context-- e continuiamo utilizzando il nodo parola, che si tratti di un rettangolo sullo schermo o un cerchio, è solo un po 'di contenitore generico, in questo caso di un albero, come quello abbiamo visto, abbiamo bisogno di un intero in ciascuno dei nodi e poi ho bisogno di due puntatori di puntamento al figlio sinistro e il figlio destro, rispettivamente. Ecco come potremmo implementare che in una struttura. E come potrei implementarlo in codice? Bene, facciamo un rapido un'occhiata a questo piccolo esempio. Non è funzionale, ma ho copiati e incollati quella struttura. E se la mia funzione per un binario Ricerca albero si chiama ricerca, e questo richiede due argomenti, un numero intero N e un puntatore a un nodo, quindi un puntatore alla struttura o un puntatore alla radice di un albero, come faccio ad andare sulla ricerca di N? Beh, in primo luogo, perché io sono si occupano di puntatori, Ho intenzione di fare un controllo di integrità. Se eguali albero uguale a zero, è N in questo albero o meno in questo albero? Non può essere, giusto? Se io sono passato nulla, non c'è niente. Potrei anche solo ciecamente dire return false. Se mi dai niente, io di certo non posso trovare qualsiasi numero N. Quindi, che cosa potrebbe io controllare ora? Io vado a dire ben altro se N è meno di ciò che è al nodo della struttura che ho consegnato valore N. In altre parole, se il numero sono cercando, N, è inferiore al nodo che sto guardando. E il nodo sto cercando a è chiamato albero, e richiamare dall'esempio precedente per ottenere il valore di un puntatore, Io uso la notazione freccia. Quindi, se N è inferiore a albero freccia N, voglio andare concettualmente sinistra. Come esprimo searching lasciato? Per essere chiari, se questa è il quadro in questione, e sono stato passato che più in alto freccia che è rivolta verso il basso. Questo è il mio puntatore albero. Sto indicando la radice dell'albero. E sto cercando per esempio, per il numero 44, arbitrariamente. È 44 inferiore o maggiore di 55 ovviamente? Quindi è inferiore. E così questo se la condizione si applica. Quindi concettualmente, quello che voglio Ricerca prossimo se sto cercando 44? Sì? 

Esattamente, voglio cercare il figlio sinistro, o il sub-albero a sinistra dell'immagine. E infatti, lasciatemi attraverso l'immagine qui solo per un momento, dal momento che Non riesco a grattare questo fuori. Se inizio qui a 55, e So che il valore 44 Io sto cercando è a la sinistra, è una specie 'come strappare la rubrica telefonica in metà o strappare l'albero a metà. Non ho più a cuore questa intera metà dell'albero. Eppure, stranamente in termini di Struttura, questa cosa qui che inizia con 33, che si è un albero binario di ricerca. Ho detto la parola ricorsiva prima perché anzi questa è una struttura di dati che per definizione ricorsiva. Si potrebbe avere un albero che è questo grande, ma ognuno dei suoi figli rappresenta un albero appena un po 'più piccolo. Invece di essere il nonno o la nonna, ora è solo la mamma or-- Non posso non say-- mamma o papà, che sarebbe strano. Invece i due bambini lì sarebbe come fratello e sorella. Una nuova generazione dell'albero genealogico. Ma strutturalmente, è la stessa idea. E si scopre Ho una funzione con la quale posso cercare una ricerca binaria albero. Si chiama ricerca. Cerco N in albero freccia sinistra altrimenti se N è maggiore del valore che sono attualmente a. 55 nella storia un momento fa. Ho una funzione chiamata di ricerca che posso solo N passare questo e ricorsivamente la ricerca il sub-albero e proprio ritorno qualunque cosa quella risposta. Il resto che ho avuto qualche caso base finale qui. 

Qual è l'ultimo caso? Albero o è nullo. Il valore che sto cercando è uno inferiore o superiore a quella o uguale ad esso. E potrei dire uguale uguale, ma è logicamente pari a poco dire altro qui. Tanto è vero come trovo qualcosa. Quindi spero che questo è un ancor esempio più convincente che la funzione di Sigma stupido abbiamo fatto qualche lezione indietro, dove era altrettanto facile da utilizzare un ciclo a contare tutti i numeri da uno a N. Qui con una struttura di dati che è di per sé in modo ricorsivo definito e ricorsivamente attratti, ora siamo hanno la capacità di esprimere noi stessi nel codice che si è ricorsivo. Quindi questo è esattamente lo stesso codice qui. 

Allora, cosa altro possiamo risolvere i problemi? Così un rapido passo dal alberi per un attimo. Qui è, diciamo, la bandiera tedesca. E c'è chiaramente una modello di questo flag. E c'è un sacco di bandiere del mondo che sono semplice come questo in termini dei loro colori e modelli. Ma supponiamo che questo è memorizzato come .GIF, O una JPEG o bitmap o un ping, qualsiasi formato di file grafici con il quale si ha familiarità, alcuni dei quali siamo giocare con in PSET4. Questo non sembra utile per memorizzare pixel nero, pixel nero, pixel nero, dot, dot, dot, tutta una serie di pixel neri per la prima linea di scansione, o riga, poi tutta una serie di lo stesso, quindi un sacco della stessa, e quindi un mucchio di pixel rossi, pixel rossi, pixel rossi, poi un intero mazzo di giallo pixel, giallo, giusto? 

C'è tale inefficienza qui. Come sarebbe intuitivamente comprimere la bandiera tedesca se la sua attuazione come un file? Come quello che informazioni possiamo non fastidio la memorizzazione su disco in ordine per diminuire la nostra dimensione del file da come un megabyte di un kilobyte, qualcosa più piccolo? Dove sta la ridondanza qui per essere chiari? Che cosa si potrebbe fare? Sì? Esattamente. Perché non ricordare piuttosto che il colore di ogni pixel maledettamente proprio come si sta facendo in PSET4 con il formato di file bitmap, perché non solo rappresenti la colonna più a sinistra di pixel, ad esempio un mucchio di pixel neri, un gruppo di rosso, e un po 'di colore giallo, e poi basta qualche modo codificare il idea di ripetere questo 100 volte o ripetere questo 1.000 volte? Dove 100 o 1000 è solo un numero intero, in modo da può uscire solo con un numero unico invece di centinaia o migliaia pixel di ulteriori. E in effetti, è così che potrebbe comprimere la bandiera tedesca. E Ora, per quanto riguarda la bandiera francese? E un po sorta di esercizio mentale, la cui bandiera può essere compresso più su disco? La bandiera tedesca o francese Bandiera, se prendiamo questo approccio? La bandiera tedesca, perché non c'è ridondanza più orizzontale. E in base alla progettazione, molti file grafico Formati effettivamente funzionano come linee di scansione orizzontalmente. Potevano lavorare verticalmente, solo l'umanità anni fa, che deciso faremo generalmente pensare alle cose fila per riga invece di colonna per colonna. Quindi, in effetti, se tu fossi a guardare il file dimensioni di una bandiera tedesca e una francese bandiera, purché la risoluzione è la stessa, la stessa larghezza e altezza, questo qui sta per essere più grande, perché si devono ripetersi tre volte. È necessario specificare blu, ripetere te, bianco, ripetere te stesso, rosso, ripetersi. Non si può semplicemente andare tutti la strada verso destra. E per inciso, per rendere cancellare la compressione è ovunque, se questi sono quattro fotogrammi da un video-- te potrebbe ricordare che un film o il video è in genere come 29 o 30 fotogrammi al secondo. E 'come un piccolo flip book dove basta vedere l'immagine, immagine, immagine, immagine, immagine appena super veloce così sembra gli attori sullo schermo sono in movimento. Ecco un calabrone su cima di un mazzo di fiori. E anche se potrebbe essere una sorta di difficile capire a prima vista, l'unica cosa che si muove in questo film è l'ape. 

Che cosa è muto sulla memorizzazione video non compresso? E 'una specie di uno spreco per memorizzare il video come quattro immagini quasi identiche che differiscono solo in quanto se l'ape è. Si può buttare via la maggior parte di tali informazioni e solo ricordare, per esempio, il primo fotogramma e l'ultimo fotogramma, fotogrammi chiave se hai mai sentito la parola, e solo memorizzare nella mezzo dove l'ape è. E non c'è bisogno di memorizzare tutti i rosa, e il blu, e il valori del verde come bene. Quindi questo è quello di dire soltanto che compressione è ovunque. E 'una tecnica che usiamo spesso o dare per scontato in questi giorni. 

Ma come si fa a comprimere il testo? Come si fa a comprimere il testo? Ebbene, ciascuno dei caratteri ASCII è un byte o otto bit. E questo è tipo di stupido, giusto? Perché probabilmente si digita A ed E e I e O e U molto il più delle volte come W o Q o Z, a seconda della lingua in cui stai scrivendo certamente. E allora perché stiamo usando otto bit per ogni lettera, compresi i meno lettere popolare, giusto? Perché non utilizzare un minor numero di bit per le lettere super-popolari, E come, le cose che si indovinare prima in Ruota della Fortuna, e utilizzare più bit per le lettere meno popolari? Perché? Perché stiamo solo andando a usarli con minore frequenza. 

Beh, si scopre che ci sono stati tentativi di fare questo. E se vi ricordate dal grado scuola o scuola superiore, il codice Morse. Codice Morse ha punti e trattini che possono essere trasmessa lungo un filo come suoni o segnali di qualche tipo. Ma il codice Morse è un super pulito. E 'una specie di un sistema binario a di avere punti o trattini. Ma se si vede, per esempio, due punti. Oppure, se si ripensa al gestore che va come bip, bip, bip, beep, colpendo un po 'innesco che trasmette un segnale, se si, il destinatario riceve due punti, quale messaggio hanno ricevuto? Del tutto arbitraria. 

IO? IO? O quello che about-- o io? Forse era solo due a destra di E? Quindi c'è questo problema di decodificabilità con Morse codice, per cui a meno che il persona che sta inviando il messaggio in realtà le pause in modo da poter ordinare di vedere o sentire i vuoti tra lettere, non è sufficiente solo inviare un flusso di zero e uno, o punti e linee, perché non c'è ambiguità. E è un singolo punto, quindi se si vedi due punti o sentire due punti, forse è il due di E o forse è uno I. Quindi abbiamo bisogno di un sistema che è un poco più intelligente di quello. Così un uomo di nome Huffman anni fa si avvicinò con esattamente questo. Quindi stiamo solo andando di prendere una rapida occhiata il modo in cui gli alberi sono attinente a questo. Supponiamo che questo è un messaggio stupido che si desidera inviare, composta solo A, B, C di D's ed E di, ma c'è un sacco di ridondanza qui. Non è destinata ad essere inglese. Non è criptato. E 'solo un messaggio stupido con un sacco di ripetizioni. Quindi, se effettivamente contano tutte le A di B, di C di D's, ed E di, ecco la frequenza. 20% delle lettere sono Un di, il 45% delle lettere E sono di, e altri tre frequenze. Abbiamo contato lassù manualmente e appena fatto la matematica. 

Così si scopre che Huffman, qualche tempo fa, resi conto che, si sa quello che, se comincio edificio un albero, o foresta di alberi, se si vuole, come segue, posso effettuare le seguenti operazioni. Io vado a dare un nodo per ogni delle lettere che mi preoccupo e ho intenzione di archiviare all'interno di tale nodo le frequenze come virgola mobile valore, oppure si potrebbe usare un N, troppo, ma ci limiteremo a utilizzare un galleggiante qui. E l'algoritmo che ha proposto è che si prendere questa foresta di singolo nodo alberi, alberi così super corti, e si inizia collegandoli con nuovi gruppi, nuovi genitori, se si vuole. E si esegue questa operazione scegliendo il due frequenze più piccoli alla volta. Così ho preso il 10% e il 10%. Creo un nuovo nodo. E io chiamo il nuovo nodo del 20%. 

Quali sono i due nodi combino prossimo? È un po 'ambiguo. Quindi ci sono alcuni casi angolo a prendere in considerazione, ma per mantenere le cose abbastanza, Ho intenzione di scegliere il 20% - Ora ignoro i bambini. Ho intenzione di scegliere il 20% e 15% e disegnare due nuovi bordi. E ora che due nodi faccio logicamente combinare? Ignorare tutti i bambini, tutti i nipoti, basta guardare alle radici adesso. Quali sono i due nodi si lego insieme? Punto due e 0,35. Così mi permetta di disegnare due nuovi bordi. E poi ho solo uno a sinistra. Quindi, ecco un albero. Ed è stato disegnato deliberatamente a guardare tipo di bella, a meno di notare che i bordi hanno anche definita zero e uno. Così tutti i bordi di sinistra sono zero arbitrariamente, ma in modo coerente. Tutti i bordi a destra sono quelli. 

E così quello che Hoffman proposto è, se si vuole rappresentare una B, piuttosto che rappresentare il numero 66 come un Ascii, che è di otto bit interi, si sa che cosa, appena negozio il modello zero, zero, zero, zero, perché questo è il percorso dal mio albero, l'albero del signor Huffman, alla foglia dalla radice. Se si desidera memorizzare un E, al contrario, non fare invia otto bit che rappresentano un E. Invece, inviare quale schema di bit? Uno. E ciò che è bello di questo è che E è la lettera più popolare, e si sta utilizzando la codice breve per esso. Il prossimo più popolare lettera sembra Era A. E così il numero di bit ti ha proposto utilizzando per questo? Zero, uno. 

E poiché è implementato come questo albero, per ora mi permetta di stipula le c'e ' nessuna ambiguità come in Morse codice, perché tutti i lettere che ti interessano sono alla fine di questi bordi. Ecco, questo è solo uno applicazione di un albero. Questo è-- e io onda la mia mano a questo come si potrebbe implementare questa come una struttura C. Abbiamo solo bisogno di combinare un simbolo, come un char, e la frequenza in a destra ea sinistra. Ma diamo un'occhiata a due esempi finali che avrai ottenere abbastanza familiarità con dopo quiz zero nel problema set five. 

Quindi vi è la struttura dei dati conosciuta come una tabella hash. E una tabella di hash è una specie di raffreddare in quanto ha secchi. E supponiamo ci sono quattro secchi qui, solo quattro spazi vuoti. Ecco un mazzo di carte, e qui è club, vanga, club, diamanti, club, diamanti, club, diamanti, clubs-- quindi questo è il caso. Cuori, hearts-- quindi sono bucketizing tutti gli ingressi qui. E un bisogno tabella di hash a guardare il tuo ingresso, e poi metterlo in un certo mettere in base a ciò che si vede. Si tratta di un algoritmo. E stavo usando un super semplice algoritmo visivo. La parte più difficile del quale era ricordando quello che le foto erano. E poi ci sono quattro cose totali. 

Ora gli stack crescevano, che è un disegno intenzionale cosa qui. Ma che altro potrei fare? Quindi, in realtà qui abbiamo una mucchio di vecchi libri d'esame della scuola. Supponiamo che un gruppo di nomi degli studenti sono qui. Ecco una tabella hash più grande. Invece di quattro secchi, Ho, diciamo 26. E non volevamo andare in prestito 26 le cose dal di fuori [? Annenberg?], Così ecco cinque che rappresentano Dalla A alla Z. E se io vedere uno studente il cui nome inizia con A, Ho intenzione di mettere il proprio quiz lì. Se qualcuno inizia con C, laggiù, A-- in realtà, non voleva farlo. B va qui. Così ho A e B e C. E ora ecco un altro Uno studente. Ma se questa tabella hash è implementato con una matrice, Sono un po 'fregato a questo punto, giusto? I tipi di bisogno di mettere da qualche parte. 

Così un modo per risolvere questo problema è, tutto a destra, A è occupato, B è occupato, C è occupato. Ho intenzione di metterlo in D. Quindi, a prima, ho accesso immediato a caso a ciascuna delle benne per gli studenti. Ma ora è una specie di devoluto in qualcosa di lineare, perché se voglio cercare qualcuno il cui nome inizia con A, controllo qui. Ma se questo non è l'A studente sto cercando, I tipi di dover avviare il controllo i secchi, perché quello che ho fatto era una sorta di linearmente sondare la struttura dei dati. Un modo stupido di dire basta guardare per la prima apertura disponibile, e mettere come un piano B, per così dire, o un piano D in questo caso, il valore in quella posizione, invece. Questo è solo così che se hai ha ottenuto 26 posizioni e non gli studenti con il nome di Q o Z, o qualcosa del genere che, almeno si sta utilizzando lo spazio. 

Ma abbiamo già visto più soluzioni intelligenti qui, giusto? Cosa fareste al posto se si dispone di una collisione? Se due persone hanno il nome A, quale sarebbe stato un intelligente o più soluzione intuitiva che solo mettendo A dove D dovrebbe essere? Perché non mi basta andare al di fuori [? Annenberg?], come malloc, un altro nodo, metterlo qui, e poi mettere che uno studente qui. In modo da avere essenzialmente una sorta di un array, o forse più elegante come siamo iniziando a vedere una lista collegata. 

E così una tabella hash è una struttura che potrebbe apparire solo come questo, ma più intelligente, qualcosa chiamato concatenazioni separate, per cui una tabella hash semplicemente è un array, ciascuno dei i cui elementi non è un numero, è esso stesso una lista collegata. In modo da ottenere un accesso super veloce decidere dove hash vostro valore a. Proprio come con la carte esempio, Ho fatto le decisioni super-veloci. Cuori va qui, diamanti va qui. Stesso qui, A va qui, D va qui, B va qui. Così super veloce look-up, e se vi capita di imbattersi in un caso collisioni in cui avete ottenuto, due persone con lo stesso nome, beh, allora basta avviare il collegamento insieme. E forse tenerli ordinati in ordine alfabetico, forse no. Ma almeno ora abbiamo la dinamicità. Così da un lato abbiamo super veloce costante di tempo, e il tipo di tempo lineare coinvolto se queste liste collegate iniziare a ottenere un po 'lungo. 

Quindi questo tipo di sciocco, anni scherzo geeky fa. Al CS50 hack-a-thon, quando gli studenti check-in, alcuni TF o CA ogni anno pensa che sia divertente per mettere in su un segno come questo, dove solo significa che se il vostro nome inizia con una A, andare in questo modo. Se il tuo nome inizia con una B, andare questo-- OK, è divertente forse più tardi nel semestre. Ma c'è un altro modo di fare questo, anche. Tornate a questo. 

Quindi c'è questa struttura. E questo è il nostro ultimo Struttura per oggi, che è qualcosa che si chiama un trie. T-R-I-E, che per qualche motivo è breve per il recupero, ma si chiama trie. Quindi un trie è un altro interessante amalgama di molte di queste idee. Si tratta di un albero, che abbiamo visto prima. Non è un albero binario di ricerca. E 'un albero con qualsiasi numero di figli, ma ciascuno dei bambini in un trie è un array. Una serie di dimensioni, diciamo, 26 o forse 27 se si desidera supportare nomi sillabate o apostrofi nei nomi delle persone. 

E quindi questa è una struttura di dati. E se si guarda dall'alto in basso, come se si guardare il nodo superiore là, M, è indicando la cosa più a sinistra lì, che viene poi A, X, W, E, L, L. Questo è solo una struttura di dati che arbitrariamente è memorizzare i nomi delle persone. E Maxwell è memorizzato da solo seguendo un percorso di array per array di array. Ma la cosa sorprendente di un trie è che, mentre una lista collegata e anche un array, la migliore che abbiamo mai ottenuto è tempo lineare o logaritmico cercando tempo qualcuno. In questa struttura di dati di un trie, se la mia struttura di dati ha un nome in esso e sto cercando di Maxwell, sono andando a trovarlo abbastanza rapidamente. Mi basta guardare per M-A-X-W-E-L-L. Se questa struttura dati, per contrasto, se N è un milione, se c'è un milioni di nomi in questa struttura dati, Maxwell è ancora in corso per essere rilevabile dopo appena M-A-X-W-E-L-L gradini. E passi David-- D-A-V-I-D. In altre parole, costruendo una struttura di dati che è ottenuto tutti questi array, tutte si supportano l'accesso casuale, Posso iniziare a guardare il popolo di nome utilizzando una quantità di tempo che è proporzionale non il numero di cose nella struttura dati, come un milione di nomi esistenti. La quantità di tempo che ci vuole per trovare M-A-X-W-E-L-L in questa struttura dati è proporzionale non al dimensioni della struttura di dati, ma la lunghezza del nome. E realisticamente la nomi che stanno cercando su sono mai andare a essere pazzo lungo. Forse qualcuno ha un carattere 10 nome, 20 nome del personaggio. E 'certamente finito, giusto? C'è un umano sulla Terra che ha il più lungo possibile nome, ma che nome è una costante lunghezza del valore, giusto? Non varia in alcun senso. Quindi, in questo modo, abbiamo realizzato una struttura di dati cioè costante di tempo di look-up. Ci vuole un certo numero di passi a seconda della lunghezza dell'input, ma non il numero di nome nella struttura dati. Quindi, se raddoppiamo il numero di nomi il prossimo anno da un miliardo a due miliardi, scoperta Maxwell sta andando a prendere esattamente lo stesso numero di sette passi per trovarlo. E così ci sembra di aver raggiunto il nostro Santo Graal di tempo di esecuzione. 

Così un paio di brevi annunci. Quiz a zero sta arrivando. Più su quello sul sito web del corso nei prossimi due giorni. Lunedi di lecture-- è una vacanza qui a Harvard il Lunedi. Non è a New Haven, così noi stiamo prendendo la classe a New Haven per conferenza il Lunedi. Tutto sarà girato e trasmesso in diretta, come al solito, ma finiamo oggi con una seconda clip 30 chiamati "Pensieri profondi" da Daven Farnham, che è stato ispirato lo scorso anno da Sabato "Pensieri profondi" di Night Live da Jack Handy, che dovrebbe ora avere un senso. 

FILM: E ora, "Deep Pensieri "di Daven Farnham. Tabella di hash. 

SPEAKER 1: Va bene, questo è tutto per ora. Ci vediamo la prossima settimana. 

DOUG: per vederlo in azione. Quindi, diamo un'occhiata a che in questo momento. Così qui, abbiamo un array non ordinato. 

IAN: Doug, si può andare avanti e ricominciare questo per un solo secondo, per favore. Va bene, le telecamere sono a rotazione, in modo da azione quando sei pronto, Doug, OK? DOUG: Va bene, allora quello che abbiamo avere qui è un array non ordinato. E ho colorato tutti gli elementi rosso per indicare che è, in effetti, indifferenziati. Così Ricordiamo che la prima cosa che facciamo è ordiniamo la metà di sinistra della matrice. Poi noi ordiniamo il diritto metà dell'array. E ya-da, ya-da, ya-da, noi li uniamo insieme. E abbiamo una matrice completamente ordinato. Ecco come merge sort funziona. 

IAN: Whoa, ehi, ehi, tagliare, tagliare, tagliare, tagliare. Doug non si può solo ya-da, ya-da, ya-da, il vostro senso attraverso merge sort. 

DOUG: Ho appena fatto. Va bene. Siamo pronti a partire. Diciamo basta continuare a tirare. Quindi, comunque, 

IAN: Devi spiegare più pienamente di quello. Questo non è solo sufficiente. DOUG: Ian, non lo facciamo bisogno di tornare a uno. Va bene. Comunque, se continuiamo con merge-- Ian, siamo nel bel mezzo delle riprese. 

IAN: Lo so. E non possiamo solo ya-da, ya-da, ya-da, attraverso l'intero processo. Bisogna spiegare come il due parti vengono fuse insieme. 

DOUG: ma abbiamo già ha spiegato come i due sides-- 

IAN: Hai appena mostrato loro un array di unione. DOUG: sanno il processo. Che stanno bene. Siamo andati oltre dieci volte. 

IAN: Hai appena saltato diritto su di essa. Stiamo tornando a uno, non puoi ya-da, ya-da sopra. Va bene, torna a uno. 

DOUG: Devo andare indietro attraverso tutte le diapositive? Mio Dio. E 'come la sesta volta, Ian. Va bene. 

IAN: Va bene. Sei pronto? Grande. Azione.