DAVID J. MALAN: Va bene. Quindi benvenuto al primo CS50 postmortem per un quiz. Abbiamo pensato inauguriamo questa tradizione di quest'anno. E questa sarà l'occasione a piedi attraverso il soluzioni per il quiz. E faremo accelerare o rallentare a base di su interessi di coloro che sono qui. 

Allora probabilmente siete qui perché sei interessati a come si potrebbe avere o avrebbe risposto ad alcune di questi problemi. Allora perché non diamo uno sguardo in questa prima sezione? In modo da ottenere stringhe. Questo ti ha dato tre versioni diverse di un programma che era, in ultima analisi, scopo di ottenere una stringa da un utente. Se sia o non ha fatto che era lasciato a voi determinare. 

E abbiamo chiesto in domanda 0, supponiamo che la versione 1 è compilato ed eseguito. Perché potrebbe il programma segmentation fault? A prima vista, qualche suggerimento come mai? Già. 

PUBBLICO: Così mi ricordo di aver visto questo una precedente esempio di guardare il char * s e vedendo la scansione dei s e vedere perché è un puntatore, come ha influenzato quello che scansionato in? E 's o l' indirizzo di s? 

DAVID J. MALAN: OK. Buona. Quindi, in definitiva, la fonte di qualsiasi problema è presumibilmente andando a ridurre a tale variabile s. Ed è infatti una variabile. Il tipo di dati di tale variabile è char *, il che significa che sta per contenere l'indirizzo di un personaggio. E qui sta l'intuizione. Sta andando a contenere l'indirizzo di un carattere o, più in generale, la indirizzo del primo carattere un intero blocco di caratteri. 

Ma il problema è che s scansione, scopo nella vita, viene dato un indirizzo e dato un codice di formato, come% s, leggere una stringa nel pezzo di memoria a quell'indirizzo. Ma perché non c'è segno di uguale prima che virgola al primo riga di codice, perché non lo facciamo davvero allocare qualsiasi memoria con malloc, perché in realtà non allocare una matrice di una certa dimensione, tutti si sta facendo sta leggendo l'utente del input da tastiera in qualche completo valore di immondizia, che è in s per impostazione predefinita. Quindi le probabilità sono che stai andando a segmentation fault se che l'indirizzo non è proprio così capita ad essere un valore che è possibile, infatti, scrivere. Così male non assegnare la memoria lì. 

Così in questione 1, abbiamo chiesto, supponiamo che la versione 2 è compilato ed eseguito. Perché potrebbe questo programma segmentation fault? Quindi questo è meno bacato. E c'è davvero una sola modo ovvio dove è possibile innescare un segfault qui. E questo è tematico. Ogni volta che stiamo utilizzando c in memoria, cosa si potrebbe fare per indurre un segfault con la versione 2? 

AUDIENCE: Se si utilizza quell'ingresso in una stringa che è più lungo di 49 caratteri. 

DAVID J. MALAN: Esattamente. Ogni volta che vedi qualcosa di lunghezza fissa quando si tratta di un array, il vostro radar deve spegnersi, che questo potrebbe essere problematico se non stai controllando la confini di una matrice. E questo è il problema qui. Stiamo ancora utilizzando scanf. Stiamo ancora utilizzando% s, il che significa provare per leggere una stringa dall'utente. Che sta per essere letto in s, che, a questo punto, è di fatto la indirizzo di un pezzo di memoria o è equivalente. E 'il nome di un array di caratteri di memoria. 

Ma esattamente che, se si legge una stringa che è più lungo di 49 caratteri, 49 perché avete bisogno di spazio per la barra rovesciata 0, si sta andando a traboccare buffer. E si potrebbe avere fortuna ed essere in grado di scrivere un personaggio 51a, 52a, 53a. Ma a un certo punto, il sistema operativo sta per dire, no. Questo sicuramente non è la memoria si è permesso di toccare. E il programma sta per segmentation fault. 

Quindi c'è, l'euristica dovrebbero essere qualsiasi il tempo che hai a lunghezza fissa, è necessario per assicurarsi che si sta controllando la lunghezza di qualunque cosa si sta cercando leggere in esso. 

PUBBLICO: Quindi, per risolvere questo, si potrebbe hanno avuto un controllo realmente dichiarazione è la lunghezza maggiore o minore? 

DAVID J. MALAN: Assolutamente. Devi solo una condizione che dice, se - o meglio, non necessariamente sa in anticipo quanti caratteri l' utente sta per digitare, perché avete pollo e l'uovo. Non prima di aver letto che con scanf si può capire quanto tempo è. Ma a quel punto, è troppo tardi, perché avete già letto in qualche blocco di memoria. Così come un a parte, le evita biblioteca CS50 questo problema del tutto, richiamo utilizzando fgetc. E legge un carattere per volta, punta toeing lungo, sapendo che si non può straripare un personaggio se si legge una alla volta. 

Il problema è con richiamo GetString è che dobbiamo costantemente ri-size che pezzo di memoria, che è solo un dolore. E 'un sacco di linee di il codice per farlo. Così un altro approccio sarebbe quello di effettivamente utilizzare un cugino, così di parlare, di scanf. Ci sono varianti di un sacco di questi funzioni che effettivamente controllano la lunghezza di quanti caratteri si potrebbe leggere al massimo. E si potrebbe specificare, non leggere più di 50 caratteri. Quindi, che sarebbe un altro approccio, ma meno accomodante di ingressi più grandi. 

Quindi, domanda 2 chiede, supporre che la versione 3 è compilato ed eseguito. Perché potrebbe quel programma segmentation fault? Così questo è in realtà la stessa rispondere, anche se sembra un po 'più elaborato. Stiamo usando malloc, che si sente come stiamo dando noi stessi più opzioni. E poi stiamo liberando che memoria alla fine. E 'ancora solo 50 byte di memoria. Così potremmo ancora provare a leggere in 51, 52, 1.000 byte. E 'intenzione di segmentation fault per esattamente lo stesso motivo. 

Ma c'è un'altra ragione. Che altro potrebbe malloc ritorno oltre l'indirizzo di un pezzo di memoria? Si potrebbe restituire null. E perché non stiamo controllando che, potremmo fare qualcosa stupido per un altro motivo, che è quella potremmo essere dicendo scanf, leggiamo input dell'utente dalla tastiera in posizione 0, AKA null. E anche questo, sarà sicuramente innescare un segfault. Così, per lo scopo del quiz, avremmo hanno accettato uno di questi come motivo valido. Uno è identico. Uno è un po 'più sfumata. 

Infine, per quanto riguarda il programma di uso della memoria, come fare la versione 2 e versione 3 differiscono? Quindi, per quello che vale, abbiamo visto un fornitura apparentemente infinita di possibili risposte a questo. E tra le risposte della gente, quello che siamo stati sperando, ma abbiamo accettato altri cose, era un po 'menzione del fatto che la versione 2 utilizza il cosiddetto stack. La versione 3 utilizza l'heap. E funzionale, questo in realtà non fare tutto che molta differenza. Alla fine della giornata, siamo ancora solo ottenere 50 byte di memoria. 

Ma quella era una delle possibili risposte che stavamo guardando. Ma vedrete, come si ottiene il quiz indietro dal TF, che abbiamo fatto accettare altre discussioni della loro usi disparati della memoria pure. Ma stack e heap sarebbe stato una risposta facile andare con. Tutte le domande? Vi do Rob. 

ROB BOWDEN: Allora problema 4. Questo è quello in cui si doveva occupare del numero di byte su tutti questi diversi tipi utilizzati. Quindi prima cosa che vediamo. Assumere una architettura a 32 bit, come questo apparecchio CS50. Così una delle cose fondamentali su Architetture a 32 bit, che ci dice esattamente quanto è grande un puntatore sta essere nell'architettura. 

Così subito, sappiamo che qualsiasi puntatore tipo è a 32-bit o 4 byte. Così, guardando a questo tavolo, un nodo * è un tipo di puntatore. Che sta per essere 4 byte. Struct node *, che è letteralmente identico al nodo stella. E così che sta per essere 4 byte. String, così non sembra un puntatore ancora, ma il typedef, un stringa è solo un char *, che è un tipo di puntatore. In modo che sara 'di 4 byte. 

Quindi questi tre sono tutti e 4 byte. Ora, il nodo e studente sono un po 'più complicato. Quindi, guardando al nodo e studente, vediamo nodo come un intero e un puntatore. Ed studente è due puntatori all'interno di esso. Quindi, almeno per nostro caso, il modo che si finisce per calcolare la dimensione del questa struttura è solo aggiungere a tutto che è all'interno della struttura. 

Così per il nodo, abbiamo un numero intero, che è 4 byte. Abbiamo un puntatore, che è 4 byte. E così un nodo sta andando a prendere 8 byte. E allo stesso modo per gli studenti, abbiamo una puntatore che è 4 byte e un altro puntatore che è 4 byte. Quindi, che sta andando a finire per essere 8 byte. Così nodo e studente sono 8 byte. E questi tre sono tutti e 4 byte. Domande su questo? Sì. 

PUBBLICO: E 'stato un 64-bit architettura, vorrei che raddoppiare tutti loro? 

ROB BOWDEN: Non sarebbe raddoppiare tutti. Così architettura a 64 bit, che, di nuovo, modifiche cosa fondamentale che un puntatore è ora 64 bit. Già. Quindi un puntatore è di 8 byte. Quindi questi che erano 4 byte stanno per essere 8 byte. Uno studente, che era due puntatori, bene, ora sta andando a essere di 8 byte, 8 byte. Sta andando a fare 16 byte. 

Ma un nodo è ancora 4 byte. Quindi questo puntatore sta andando essere 8 byte. Questo è 4 byte. Quindi un nodo è solo andare essere di 12 byte. Tutte le altre domande su quello? Quindi il prossimo, questi sono i codici di stato HTTP. E dovessi descrivere circostanze in base al quale questi possono essere rispedito al mittente. un problema che ho sentito alcuni studenti avere è che hanno cercato di fare il errori siano sull'estremità del client. Così, quando cerchiamo di fare la richiesta al server, qualcosa va sbagliato da parte nostra. Ma in generale, i codici sono: essere restituito dal server. Quindi vogliamo capire cosa sta succedendo giusto o sbagliato sul server che fa sì che queste cose devono essere restituiti. Allora perché potrebbe un server restituisce codice di stato 200? Qualche idea? 

Già. Quindi qualcosa su successo la richiesta ha attraversato. E sono in grado di tornare tutto ciò che hai chiesto. Così tutto è andato bene. Che cosa circa 302 trovati? Già. 

PUBBLICO: Il server era alla ricerca per quello che hai richiesto. Ma non poteva trovarlo. Quindi c'è un errore. 

ROB BOWDEN: Quindi il server era ricerca di ciò che si voleva. Quindi basta guardare qui, 302 trovato, è stato in grado di trovarlo. 

PUBBLICO: Mi dispiace. Trovato significa che hanno fatto trovare. Scusi. 

ROB BOWDEN: Quindi 302 found. Il server è in grado di trovare quello che volevi. 

AUDIENCE: Ma non è visualizzarlo? 

ROB BOWDEN: La differenza tra questa 302 e 200 è che sa ciò che si vuole. Ma non è esattamente dove si voleva chiedere. Quindi 302 è un redirect tipico. Quindi hai richiesto una pagina. Si sa, oh, voglio per restituire questo. Ma questo è un URL differente. Così hey, si vuole realmente questo. 

DAVID J. MALAN: E 'un pezzo che ha detto che abbiamo dato voi ragazzi un redirect funzione che utilizza la funzione header che, a sua volta, stampati posizione, colon, e poi l'URL a cui si vuole rifiutare l'utente. Anche se non hai visto 302 esplicitamente lì, questo è ciò che PHP sarebbe magicamente inserire come intestazione dicendo esattamente quello che ha detto Rob lì - trovato. Ma andate qui invece. 

ROB BOWDEN: OK. Così che cosa circa 403 proibito? 

PUBBLICO: Penso che sia che il server è fondamentalmente dicendo che il client non può accedere alla home page. 

ROB BOWDEN: Quindi sì. Bene, la risposta tipica eravamo mi aspettavo qualcosa di simile, i file non sono chmodded appropriato. Questo è probabilmente in quali circostanze li hai visti. Ma c'è una ragione che il cliente potrebbe essere colpa qui. In realtà c'è un altro codice di stato - 401. Quindi questi sono molto simili. 

401 non è autorizzato. E 403 è vietato. E così non autorizzata voi in esclusiva ottenere se non sei loggato Ma login potrebbe significare che si è autorizzati. Ma se siete già connessi ed hai ancora non hanno il permesso, poi è anche possibile ottenere proibito. Quindi, se siete registrati e non hanno permesso, proibito è anche qualcosa che si può ottenere. 

David J. MALAN: E il meccanismo mediante che questi problemi sono solitamente risolto sul server è con quale comando? Chmod, se lo è, infatti, un permesso rilasciare il file o la directory. 

ROB BOWDEN: Quindi 404 non trovato. Già. Quindi, a differenza 302 dove non era esattamente dove si sta chiedendo, ma sa che cosa volete, questo, che ha appena idea di ciò che si desidera. E non si sta chiedendo qualcosa di valido. 418 Sono una teiera e poi 500 server interno. Allora perché potreste ottenere che? 

Così segmentation fault - Io in realtà non so la classificazione standard per questo. Ma se il vostro codice PHP aveva qualcosa di male, in teoria, potrebbe effettivamente segfault, nel qual caso, questa Errore interno del server 500, qualcosa è sbagliato con il server di configurazione. Oppure c'è un errore di sintassi nel codice PHP. O qualcosa di brutto sta accadendo. 

DAVID J. MALAN: abbiamo visto segfault tra le risposte poche persone. E tecnicamente, potrebbe accadere. Ma questo sarebbe un PHP, il programma scritto da altre persone, in realtà segfaulted, che solo se queste persone incasinato e scrisse il codice buggy in il loro interprete sarebbe PHP stesso segmentation fault. Così, anche se 500 è come un segfault nello spirito, è quasi sempre il risultato di un problema di file di configurazione con il server web o, come ha detto Rob, un errore di sintassi, come voi non chiudere un preventivo. Oppure hai perso un punto e virgola da qualche parte. 

AUDIENCE: Così, per la pset Shuttle, ho pensare che quando l'ho fatto una volta ho cliccato l' browser, ma nulla si avvicinò, quello che chiamavano pagina bianca. Ma è stato a causa del codice. Credo che sia stato JavaScript, giusto? 

ROB BOWDEN: Già. 

AUDIENCE: Vorrei che errore ancora venire? 

ROB BOWDEN: Quindi non avreste ottenuto questo errore perché tutto dal punto di vista del server web era completamente soddisfacente. Ma che hai richiesto index.html. È richiesto shuttle.js e service.js. Ed è stato in grado di tornare con successo a voi tutte queste cose - 200. OK. E 'solo quando il browser tenta di interpretare il codice JavaScript che E 'come, aspetta, questo non è errore JavaScript valida. Tutte le altre domande? Bene. 

DAVID J. MALAN: Così la prossima up era il numero 11. E 11 è stata la più spaventosa per un sacco di gente. Quindi la cosa più importante da notare qui era che questo stato, infatti, sulla una lista doppiamente concatenata. Ma questa non era la stessa dello scorso anno problema lista doppiamente concatenata, che non ti ha dato l'avvertenza che l'elenco potrebbe, infatti, essere differenziati. 

Quindi il fatto che l'elenco era indifferenziati e il fatto che tale parola era Sottolineato c'era lo scopo di trasmettere che questo è in realtà una semplificazione di quello che altrimenti sarebbe stato un problema più impegnativo e uno più lungo. Quindi, un errore comune era quello di aver messo la soluzione dello scorso anno sul vostro one pager e poi basta copiare ciecamente che giù come la risposta, che è il diritto rispondere ad una domanda diversa simile nello spirito. Ma le sottigliezze qui sono stati i seguenti. 

Così uno, abbiamo un nodo dichiarata e definito nel modo usuale qui. Poi abbiamo definito la lista di essere globale puntatore inizializzato a null. Poi a quanto pare, ci sono due funzioni abbiamo prototipi di qui, inserto e rimuovere. E poi abbiamo un po 'di codice di esempio qui di fare un gruppo di inserzioni. E allora vi chiediamo di completare l' attuazione dell'inserto seguito in tale un modo che inserisce n nella lista in tempo costante, anche sottolineato, anche se già presente. 

Così la bellezza di poter inserire in tempo costante è che implica che si deve inserire il nuovo nodo dove? Nella parte anteriore. Quindi elimina, per fortuna, almeno uno dei casi che richiedevano ancor più righe di codice, come ha fatto l'anno scorso e anche in classe quando abbiamo parlato attraverso questo genere di cose con gli esseri umani e con qualche verbale pseudo codice. Così nella soluzione qui, saltiamo sopra a che solo per avere una visuale sulla schermo. 

Si noti che stiamo facendo quanto segue. E anche notare l'altra semplificazione era che anche se è già presente, quindi questo significa che anche se il numero è già lì, si può ciecamente inserire un altro copia. E che, troppo, voleva essere un semplificazione, in modo che si potrebbe fuoco, in realtà, alcuni dei più parte intellettualmente interessante e non solo qualche ulteriore controllo degli errori dato il tempo limitato. 

Quindi, in questa soluzione di esempio, destiniamo un puntatore sulla mano sinistra lato qui per un nodo. Ora, realizzare tale puntatore, come Rob ha detto, è solo 32 bit. E in realtà non contiene un indirizzo fino a che assegnare l'indirizzo. E lo facciamo sulla destra lato via malloc. Come un buon cittadino, controlliamo che malloc non è, infatti, nullo, in modo che non creiamo accidentalmente un segfault qui. E ogni volta che si utilizza malloc nella vita, dovrebbe essere controllo per nulla, per timore avete un bug sottile. 

Poi si inizializza che nulla da l'assegnazione di n e precedente e successivo. E in questo caso qui, ho inizializzato precedente nullo, perché questo nuovo nodo sta per essere il nuovo inizio della mia lista. Quindi ci sara ' niente prima. E voglio aggiungere essenzialmente elenco esistente al nuovo nodo impostazione accanto pari a lista stessa. Ma non sono solo ancora finito. Quindi, se la lista stessa esisteva già, e c'era almeno un nodo già in atto, se questa è la lista qui e mi inserisco un nuovo nodo qui, io necessario assicurarsi che il mio ex nodo punti indietro al mio nuovo nodo, perché questo è, di nuovo, una lista doppiamente concatenata. 

Quindi facciamo un controllo di integrità. Se la lista non è nullo, se c'è già uno o più nodi là, allora Aggiungo che torna riferimento per così dire. E poi l'ultima cosa di cui abbiamo bisogno di fare è in realtà aggiornare il mondiale elenco variabile stessa per puntare a quel nuovo nodo. Già. 

AUDIENCE: Nel puntatore a freccia [Incomprensibile] è uguale a null, fa che trattare con l'elenco perché l'elenco è nullo? 

DAVID J. MALAN: Nope. Questo è semplicemente me essere in modo proattivo attenzione, in quanto se questo è il mio lista originale con forse qualche più nodi qui e sto inserendo il mio nuovo nodo qui, ci sta andando essere niente qui. E voglio cogliere questa idea impostando precedente nullo sul nuovo nodo. E presumibilmente, se il mio codice è corretto e non c'è altro modo per inserire nodi diversi da questa funzione, presumibilmente, anche se la lista ha già uno o più nodi in esso, presumibilmente la elenco, il primo nodo, avrebbe un precedente puntatore nullo se stesso. 

PUBBLICO: E solo un follow-up. La ragione per cui si mette puntatore prossimi uguali lista è che stai facendo il puntatore prima lista in che sta puntando alla prossima, credo - Non. - basta liste? 

DAVID J. MALAN: Esattamente. E quindi cerchiamo di realtà consideriamo due casi qui realmente, anche se la fine noi li consideriamo non è abbastanza lo stesso codice. Ma a un livello elevato, se questo rappresenta lista e questo è un 32-bit puntatore, il caso più semplice è che ciò è null di default. E supponiamo che io voglio inserire il il numero 50 è il primo numero. Quindi ho intenzione di andare avanti e allocare un nodo, che sta per contenere tre campi - n, precedente e successivo. 

Ho intenzione di mettere il numero 50 qui, perché questa sarà la n. Questo sarà il prossimo. E questo sarà precedente. E così quello che faccio in questo caso? Beh, ho appena fatto la linea 1 qui. Pointer n diventa n. Sto quindi dicendo precedente dovrebbe ottenere nulla. Quindi questo sarà nullo. Allora io vado a dire dopo sta per ottenere l'elenco. 

E questo funziona bene. Questo è nullo. E così sto dicendo, il nuovo nodo del prossimo campo dovrebbe ottenere tutto ciò che questo è. Così che mette un altro nullo lì. E poi l'ultima cosa Che faccio è controllare qui. Se la lista non è uguale a null, ma è pari a zero, così saltiamo che tutto. E così tutto quello che faccio prossimo è la lista ottiene puntatore, che si traduce pittoricamente in un quadro del genere. Ecco, questo è uno scenario. 

E quello che stavate chiedendo circa in particolare è una situazione come questa, dove abbiamo già una lista di un nodo. E se torno in originale dichiarazione del problema, la prossima faremo inserisci esempio è 34, solo per il bene della discussione. Quindi ho intenzione di appena convenientemente disegnare che nel corso qui. Ho appena malloced. Supponiamo che sto controllando per nulla. 

Ora, ho intenzione di inizializzazione n essere 34. E questo sarà n. Questo sarà il prossimo. E questo sarà precedente. Facciamo in modo che non l'ho fatto ottenere questo indietro. Precedente viene prima nella definizione. Correzione questo. Questa è precedente. Questo è il prossimo. Anche se questi sono identici, teniamolo coerente. 

Precedente. Questo è il prossimo. Così ho appena malloced mia nota, controllato per nulla, assegnato 34 nel nodo. Precedente ottiene nulla. In modo che mi dà questo. Avanti ottiene list. Quindi elenco è presente. Quindi questa è la stessa oggi come disegnare questo freccia, in modo che puntino a uno nella stessa. E poi mi sto controllando se la lista non è uguale a zero. E non è questa volta. Poi ho intenzione di fare la lista precedente ottiene puntatore. 

Quindi lista previous ottiene PTR. Quindi questo ha l'effetto di mettere una freccia grafica qui. E che sta diventando un po ' ondulate, le linee. E poi, infine, aggiorno lista per puntare a puntatore. Così ora questa punta a questo ragazzo. E ora, facciamo un breve controllo di integrità. 

Ecco la lista, che è la variabile globale. Il primo nodo è, infatti, 34, perché Sto seguendo la freccia. E questo è corretto perché voglio inserire all'inizio della lista tutti i nuovi nodi. Il suo prossimo campo mi porta a questo ragazzo. Se continuo ad andarci, mi ha colpito il prossimo è nullo. Quindi non c'è più la lista. Se mi ha colpito precedente, ottengo indietro dove mi aspetto. 

Quindi ci sono ancora alcuni indicatori, ovviamente, per manipolare. Ma il fatto che vi è stato detto di fare questo in tempo costante si intende solo avere un numero finito di cose si è permesso di fare. E qual è quel numero? Potrebbe essere un passo. Potrebbe essere due. Potrebbe essere 1.000 gradini. Ma è finita, il che significa che non è possibile avere qualsiasi tipo di looping in corso qui, nessuna ricorsione, nessun cicli. E 'solo avuto modo di essere linee di hard-coded di codice come abbiamo in questo esempio. 

Quindi, il problema successivo 12 ci ha chiesto di completare l'attuazione di remove di seguito in modo tale che rimuove n dalla lista in tempo lineare. In modo da avere un po 'di più spazio di manovra ora. Si può supporre che n, se presenti nella lista, sarà presente non più di una volta. E anche questo è destinato a essere una basata su quiz ipotesi semplificatrice, così che se si trova il numero 50 da qualche parte nella lista, non lo fai anche devono preoccuparsi di continuare a iterare, alla ricerca di ogni possibile copia di 50, che sarebbe solo devolvere in qualche minuzia in un tempo limitato. 

Quindi, con remove, questo è stato sicuramente più impegnativo e più codice da scrivere. Ma a prima vista, francamente, potrebbe guardare travolgente e come qualcosa non c'è modo si potrebbe avere venire con un quiz. Ma se ci concentriamo sulle singole fasi, si spera, sarà improvvisamente sciopero che ognuno di questi singoli procedura ha senso ovvio in retrospettiva. Quindi diamo un'occhiata. 

Quindi, prima, inizializziamo puntatore di essere lista stessa. Perché voglio tempo lineare, il che significa Ho intenzione di avere qualche loop. E un modo comune per scorrere i nodi in una struttura elenco o qualsiasi tipo della struttura in modo iterativo è quello di prendere un puntatore alla parte anteriore dei dati struttura e poi basta avviare l'aggiornamento e camminare la strada attraverso la struttura di dati. Quindi ho intenzione di fare esattamente questo. 

Mentre puntatore, la mia variabile temporanea, è diverso da null, LET'S andare avanti e controllare. Ho ricevuto fortunato? È il campo n nel nodo Sono attualmente guardando pari alla Numero sto cercando? E se è così, facciamo qualcosa. Ora, notare questo se la condizione circonda l'intero seguenti righe di codice. Questa è l'unica cosa che mi interessa - trovare un numero in questione. Quindi non c'è nessun altro, che semplifica cose concettualmente un po '. 

Ma ora, ho capito, e si potrebbe avere solo capito questo dopo aver pensato attraverso un po ', non c'è in realtà due casi qui. Uno è dove il nodo è al inizio della lista, che è un po 'fastidioso, perché è un caso speciale, perché si ha a che fare con questa cosa, che è l'unica anomalia. Ovunque nella lista, è la stessa cosa. C'è un nodo precedente e una successiva nodo, il nodo precedente, successiva nodo. Ma questo ragazzo è un po 'speciale se è all'inizio. 

Quindi, se il puntatore è uguale lista stesso, così se sono all'inizio di la lista e ho trovato n, ho bisogno per fare un paio di cose. Uno, ho bisogno di cambiare elenco puntare al campo successivo, 50. Quindi suppongo che sto cercando per rimuovere 34. Così questo ragazzo ha avuto modo di andare via in un attimo. 

Quindi ho intenzione di dire, lista viene puntatore prossimo. Beh, questo è il puntatore. Avanti si indica qui. Quindi questo sta cambiando questa freccia destra ora puntare a questo tizio qui. Ora, ricordate, abbiamo una variabile temporanea. Quindi non abbiamo orfano nodi, perché ho anche questo ragazzo nella mia l'attuazione di remove. Così ora, se la lista in sé non è nulla, Ho bisogno di sistemare qualcosa. 

Devo ora fare in modo che questa freccia, che è già puntamento 50-34, questo ha ottenuto di andare via, perché se sto cercando di sbarazzarsi di 34, 50 avevano meglio non mantiene alcun tipo di schiena riferimento ad essa come freccia suggerito. Così ho appena fatto questa linea. Allora ho finito. Tale causa è in realtà piuttosto semplice. Tritare la testa della lista è relativamente semplice. 

Purtroppo, c'è questo fastidioso altro blocco. Così ora, devo considerare il caso dove c'è qualcosa in mezzo. Ma non è troppo terribile, fatta eccezione per la sintassi come questo. Quindi, se non sono all'inizio del elenco, sono da qualche parte nel mezzo. E questa linea qui sta dicendo, inizio a qualunque nodo che ci sei. Vai al campo successivo del nodo precedente e il punto che al puntatore. 

Facciamo questo pittoricamente. Che stava diventando complicata. Quindi, se ho una precedente campi qui - facciamolo - campi successivi qui. Ho intenzione di semplificare la mia puntatori piuttosto di disegnare un intero gruppo di le cose avanti e indietro si incrociano vicenda. E ora, limitiamoci a dire che questo è 1, 2, 3 per il bene della discussione, anche anche se questo non è allineata con il problema in questione. 

Quindi, ecco la mia lista collegata. Sto cercando di rimuovere i due in questo particolare versione della storia. Così ho aggiornato puntatore essere rivolto a questo ragazzo. Quindi questo è PTR. Sta puntando qui. Questa è la lista, che esiste globalmente come prima. E ha rivolto qui non importa cosa. Ed ora, sto cercando di rimuovere due. 

Quindi, se il puntatore punta qui, sono andando a seguire, a quanto pare, l' puntatore precedente, che mi mette a 1. Sto andando poi a dire che il prossimo campo, che mi porta verso questo casella qui, sta per pari indicatore accanto. Quindi, se questo puntatore, questo è prossima. Ciò significa che questa freccia esigenze per puntare a questo ragazzo. 

Allora, cosa che riga di codice ha appena fatto è un po 'di questo. E ora, questo è alla ricerca come un un passo nella giusta direzione. Siamo essenzialmente vogliamo tagliare fuori 2 del mezzo 1 e 3. Quindi ha senso che vogliamo percorso questo puntatore intorno ad esso. Quindi questa riga successiva sta controllando se il puntatore successivo non è nullo, non c'è Al contrario uno a destra di 2, che significa che abbiamo anche a che fare un po 'snip qui. 

Così ora ho bisogno di seguire questo puntatore e aggiornare il puntatore precedente questo ragazzo per fare un po 'di soluzione, qui il punto qui. E ora, visivamente questo è bello. E 'un po' disordinato in che non c'è nessuno indicando la 2 più. 2 sta indicando a sinistra. E 2 sta indicando a destra. Ma lui può fare quello che vuole, perché sta per ottenere liberato. E non importa che cosa tali valori sono più. 

Quello che è importante è che il restante ragazzi sono di routing sopra e sotto di lui. E in effetti, questo è quello che facciamo dopo. Noi puntatore libera, il che significa che diciamo l' il sistema operativo, sei il benvenuto recuperare questo. E poi, infine, ci ritorno. Altrimenti implicitamente, se non hanno ancora restituito, dobbiamo continuare a cercare. Così puntatore è uguale puntatore successiva, significa spostare questo tizio qui. Spostare questo ragazzo qui. Spostare questo ragazzo qui, infatti, non abbiamo trovato il numero stiamo cercando ancora di. 

Quindi, francamente, sembra completamente travolgente, credo, in un primo momento colpo d'occhio, soprattutto se si lottato con questo durante il quiz poi vedere qualcosa di simile. E si pacca sulla schiena. Beh, non c'è modo avrei potuto venire con quello sul quiz. Ma direi, è possibile se si rompe giù in questi individuale casi e solo a piedi attraverso di essa attenzione, anche se, certo, sotto circostanze stressanti. 

Per fortuna, l'immagine ha fatto tutto felice. Si potrebbe disegnare questo qualsiasi numero di modi. Non devi fare lo incrociano cosa qui. Si potrebbe farlo con dritto linee come questo. Ma la sostanza di questo problema, in generale, sia per rendersi conto che la immagine, alla fine, dovrebbe apparire un po ' qualcosa di simile, perché costante di tempo implicava che si mantiene inceppamenti e disturbo e disturbo della nuovi nodi all'inizio dell'elenco. Tutte le domande? Probabilmente il più impegnativo di certamente le domande di codifica. 

AUDIENCE: Così è la lista simile a testa negli esempi precedenti. 

DAVID J. MALAN: Esattamente, esattamente. Basta un nome diverso per una variabile globale. In tutto il mondo che cosa? 

ROB BOWDEN: OK. Quindi questo è quello in cui si dovuto scrivere il paragrafo. Alcune persone hanno scritto saggi per questa domanda. Ma basta usare questi sei termini per descrivere cosa succede quando si tenta di contattare facebook.com. Quindi mi limiterò a parlare attraverso il processo utilizzando tutti questi termini. Così nel nostro browser, digitiamo facebook.com e premere Invio. Così il nostro browser sta andando a costruire un HTTP richiedere che sta andando per inviare attraverso un processo a Facebook per Facebook per rispondere a noi con l' HTML della propria pagina. 

Allora, qual è il processo mediante il che la richiesta HTTP in realtà arriva a Facebook? Quindi in primo luogo, abbiamo bisogno di tradurre Facebook.com. Così appena dato il nome di Facebook.com, dove in realtà fa la richiesta HTTP bisogno di andare? Quindi abbiamo bisogno di tradurre Facebook.com a un indirizzo IP, che univocamente identifica quale macchina abbiamo effettivamente desidera inviare questa richiesta. Il vostro computer portatile ha un indirizzo IP. Tutto ciò connesso a internet ha un indirizzo IP. 

Così DNS, Domain Name System, che è quello che sta succedendo per gestire la traduzione da facebook.com a un indirizzo IP che si vuole realmente mettersi in contatto. Così ci mettiamo in contatto i server DNS e per esempio, che cosa è facebook.com? Si dice, oh, è l'indirizzo IP 190,212 qualcosa, qualcosa, qualcosa. Bene. Ora, so che macchina Voglio contattare. 

Allora si invia la richiesta HTTP oltre a quella macchina. Così come si arriva a quella macchina? Ebbene, la richiesta va da router a router rimbalzo. Ricordate l'esempio in classe, dove abbiamo effettivamente visto il percorso che l' pacchetti preso quando abbiamo cercato comunicare. Abbiamo visto saltare sopra l'Atlantico Mare in un punto o qualsiasi altra cosa. 

Così l'ultimo porto termine. Quindi questo è ora sul vostro computer. È possibile avere più cose attualmente comunicare con Internet. Così posso essere in esecuzione, ad esempio, Skype. Potrei avere un browser web aperto. Potrei avere qualcosa che torrenting file. Quindi, tutte queste cose sono comunicante con l' internet in qualche modo. 

Così, quando il computer riceve alcuni dati da internet, come si fa sapere quale applicazione effettivamente vuole i dati? Come fa a sapere se questa particolare dati è pensato per l' torrenting applicazione in contrapposizione al browser web? Quindi questo è lo scopo di porti che tutte queste applicazioni hanno rivendicato una porta del computer. Così il vostro browser web dice, hey, Sto in ascolto sulla porta 1000. E il programma torrenting sta dicendo, Sto in ascolto sulla porta 3000. E Skype dice, io sto utilizzando la porta 4000. 

Così, quando si ottiene alcuni dati che appartiene ad una di queste applicazioni, i dati è contrassegnato con la quale porta in realtà devono essere inviate insieme al. Così dice questo, oh, io appartengo alla porta 1000. So poi ho bisogno di trasmettere la presente insieme al mio browser web. Quindi la ragione è pertinente qui è che i server web tendono a ascolto sulla porta 80. Così, quando posso contattare Facebook.com, sono comunicare con una macchina. Ma ho bisogno di dire quale porta di quella Macchina voglio comunicare. E server web tendono ad essere in ascolto sulla porta 80. 

Se volevano, potevano impostarlo in modo elenca come sulla porta 7000. E poi in un browser web, ho potuto digitare manualmente Facebook.com: 7000 inviare la richiesta alla porta 7000 di web server di Facebook. 

David J. MALAN: E in questo caso, anche se non abbiamo bisogno che la gente citare questo, in questo caso, la porta Sarebbe la richiesta effettivamente andare a? Prova di nuovo. Esattamente. Non alla ricerca di quella, ma una sottigliezza che è lì nessuno l'ultimo. 

ROB BOWDEN: Così l'HTTPS, dal momento che è ascolto specificamente per l' cifrato, è sulla porta 4430. 

Pubblico: E-mail sono 25, giusto? 

DAVID J. MALAN: Outbound e-mail, 25, sì. 

ROB BOWDEN: Io non so nemmeno la maggior parte dei il - tutte quelle inferiori tendono ad essere riservata per le cose. Penso che tutto sotto 1024 è riservato. 

AUDIENCE: Perché hai detto 3 era il numero sbagliato? 

ROB BOWDEN: Perché in un indirizzo IP, ci sono quattro gruppi di cifre. E sono da 0 a 255. Quindi 192.168.2.1 è un comune locale indirizzo IP di rete. Avviso tutti coloro che sono meno di 255. Così, quando ho iniziato con 300, che non potrebbe avere stato uno dei numeri. 

DAVID J. MALAN: Ma quel clip stupido da - era CSI, dove avevano una numero che era troppo grande per l'indirizzo IP. 

ROB BOWDEN: Tutte le domande su questo? Il prossimo, cambiamento così completo in argomento, ma abbiamo questo array PHP per le case del quad. E abbiamo una lista non ordinata. E vogliamo stampare ogni voce dell'elenco solo che contiene il nome di casa. Così abbiamo un ciclo foreach. Quindi ricorda, la sintassi è foreach matrice come elemento dell'array. Quindi attraverso ogni iterazione del ciclo, casa sta per assumere uno dei I valori all'interno della matrice. 

Nella prima iterazione, la casa sarà Cabot House. In una seconda iterazione, la casa sarà essere Courier House e così via. Così, per ogni quad come casa, siamo basta andare in stampa - si potrebbe anche avere eco - la voce di elenco e quindi il nome della casa e quindi chiudere la voce di elenco. Le parentesi graffe sono opzionali qui. 

E poi abbiamo anche detto nella domanda si, ricordatevi di chiudere il ordinato tag lista. Quindi abbiamo bisogno per uscire dalla modalità PHP per fare questo. Oppure avremmo potuto eco l' chiudere tag lista non ordinata. 

DAVID J. MALAN: bene anche qui sarebbe sono stati per usare una vecchia scuola per ciclo con un $ i = 0 0 e usando conta fino capire la lunghezza del raggio. Totalmente troppo bene, basta un po wordier. 

AUDIENCE: Quindi, se si andavano a [Incomprensibile], faresti - Ho dimenticato come il ciclo [incomprensibile] è. Volete $ supporto quad i? 

DAVID J. MALAN: Esattamente. Sì, esattamente. 

ROB BOWDEN: Nient'altro? 

DAVID J. MALAN: Va bene. Trade-off. Quindi c'erano mazzi di risposte possibile per ciascuno di questi. Siamo rimasti davvero solo in cerca di qualcosa di interessante per un rialzo e un aspetto negativo. E il numero 16 chiese, convalida gli utenti ' Ingresso lato client, come JavaScript, invece di server-side, come con PHP. Così che cosa è un rialzo di facendo client-side? 

Beh, una delle cose che abbiamo proposto è che si riduce la latenza, perché si non devono preoccuparsi di contattare il server, che potrebbe richiedere un paio di millisecondi o anche un paio di secondi evitando che e solo convalida degli utenti in ingresso lato client innescando un gestore on-presentare e solo controllando, ha si digita qualcosa per il nome? Hanno qualcosa tipo a indirizzo email? Hanno scelto un dormitorio da il menu a discesa? 

È possibile dare loro un feedback istantaneo utilizzando il computer gigahertz o qualsiasi altra cosa che hanno che è in realtà sulla loro scrivania. Quindi è solo un utente migliore sperimentare in genere. Ma un lato negativo di fare client-side convalida, se lo si fa anche senza facendo la validazione lato server è che più nessuno esce di CS50 sa che si può semplicemente inviare tutti i dati che si desidera ad un server qualsiasi numero di modi. Francamente, nella maggior parte qualsiasi browser, è possibile cliccare in giro nelle impostazioni e proprio disattivare Javascript, che sarebbe, quindi, disattivare qualsiasi forma di convalida. 

Ma si potrebbe anche ricordare che anche io ha fatto alcune cose arcane in classe utilizzando telnet ed effettivamente fingendo di essere un browser inviando get richieste a un server. E non è certo utilizzando qualsiasi JavaScript. Questo è solo me digitare comandi a una tastiera. Quindi, in realtà, ogni programmatore entro abbastanza comfort con il web e HTTP potrebbe inviare qualsiasi dato lui o lei vuole a un server senza convalida. E se il server non sta controllando, si mi danno un nome, è questo in realtà un indirizzo email valido, ha fatto scelgono un dormitorio, si potrebbe finire up inserendo falso o solo dati vuoto nel database, che probabilmente non sta per essere una buona cosa se eri supponendo che c'era. 

Quindi questa è una realtà fastidiosa. Ma in generale, lato client convalida è grande. Ma significa il doppio del lavoro. Anche se ci fanno esistere vari biblioteche, librerie JavaScript per esempio, che rendono questo molto, molto meno di un mal di testa. E si può riutilizzare parte del codice lato server, client-side. Ma non si rendono conto che si tratta in genere lavoro supplementare. Già. 

AUDIENCE: Quindi, se abbiamo appena detto meno sicuro - 

DAVID J. MALAN: [ride] Ugh. Quelli sono sempre più difficile quelli a provvedere. 

ROB BOWDEN: Che sarebbe sono state accettate. 

DAVID J. MALAN: Cosa? 

ROB BOWDEN: Ho creato questo problema. Ciò sarebbe stato accettato. 

DAVID J. MALAN: Già. 

AUDIENCE: Freddo. 

ROB BOWDEN: Ma noi non accettiamo per la prima - bene, quello che stavamo cercando è qualcosa di simile non si deve comunicare con il server. Non abbiamo accettato solo più veloce. 

AUDIENCE: Che dire Non ricaricare la pagina? 

ROB BOWDEN: sì. Quella era una risposta accettata. 

DAVID J. MALAN: Anything dove ci siamo sentiti era più probabile che non probabile che si sapeva quello che eri dicendo che è un duro Linea per disegnare a volte. Utilizzando una lista collegata invece di un array di mantenere un ordinati elenco di numeri interi. Quindi un rialzo spesso ci ricordiamo con collegata liste che hanno motivato la loro intera introduzione era si ottiene dinamismo. Possono crescere. Essi possono ridursi. Quindi non dovete fare i salti mortali per creare effettivamente più memoria con una matrice. O non avete a poco dire, mi dispiace, l'utente. La matrice viene riempita. Crescita così dinamica dell'elenco. Un aspetto negativo anche se di liste collegate? 

PUBBLICO: E 'lineare. Ricerca su lista concatenata è lineare invece di quello che si accede dentro 

DAVID J. MALAN: Esattamente. Ricerca su una lista collegata è lineare, anche se è risolto, perché si può solo seguire queste briciole di pane, questi puntatori, dall'inizio della lista alla fine. Non è possibile sfruttare l'accesso casuale e, quindi, la ricerca binaria, anche se è ordinati, che si poteva fare con un array. E c'è anche un altro costo. Già. 

AUDIENCE: Memoria inefficiente? 

DAVID J. MALAN: Già. Beh, non sarebbe necessariamente dire inefficiente. Ma ti costa più memoria, perché avete bisogno di 32 bit per ogni nodo per il puntatore supplementare, a almeno per una lista concatenata. Ora, se si sta memorizzando solo numeri interi e si sta aggiungendo il puntatore, che è in realtà sorta di non-banale. È raddoppiando la quantità di memoria. Ma in realtà, se stai memorizzare un lista concatenata di struct che potrebbero avere 8 byte, 16 byte, ancora di più Oltre a questo, forse è meno di un costo marginale. Ma è un costo comunque. Quindi uno di questi avrei stato bene come aspetti negativi. 

18. Utilizzando PHP invece di C per scrivere un programma a riga di comando. Quindi, ecco, è spesso più veloce di utilizzare un linguaggio come PHP o Ruby o Python. Basta aprire rapidamente un editor di testo. Hai molte più funzioni a vostra disposizione. PHP ha il lavello della cucina di funzioni, mentre in C, è sono molto, molto poco. In realtà, i ragazzi la conoscono nel modo più duro che non avete le tabelle hash. Non avete collegato liste. Se volete quelli, dovete attuare da soli. 

Così un rialzo di PHP o realmente qualsiasi linguaggio interpretato è la rapidità con la quale è possibile scrivere codice. Ma un aspetto negativo, abbiamo visto questo quando ho rapidamente montata una Misspeller attuazione in conferenza utilizzando PHP, è che l'utilizzo di un linguaggio interpretato è generalmente più lenta. E abbiamo visto che dimostrabile con un crescere nel tempo da 0,3 secondi a 3 secondi, a causa della interpretazione che in realtà accade. 

Un altro aspetto positivo è che si non devono compilare. Così accelera lo sviluppo per inciso, perché non hai due passi per l'esecuzione di un programma. Devi solo uno. E così che è abbastanza convincente pure. Utilizzando un database SQL invece di un file CSV per memorizzare i dati. Database in modo SQL viene utilizzato per pset7. I file CSV non è stato utilizzato molto. Ma è stato utilizzato indirettamente in pset7 come bene parlando con Yahoo Finance. 

Ma CSV è proprio come un file di Excel, ma super semplice, in cui le colonne sono solo demarked da virgole all'interno di un file di testo altrimenti. E l'utilizzo di un database SQL è un po 'più convincente. E 'un lato positivo, perché si ottiene cose come selezionare e inserire ed eliminare. E si ottiene, presumibilmente, indici MySQL ed altri database, come Oracle, costruire per voi in memoria, che significa che il vostro prescelto non è probabilmente sta per essere top lineare verso il basso. In realtà sarà qualcosa di come la ricerca binaria o qualcosa del genere simile nello spirito. Quindi sono generalmente più veloci. 

Ma un aspetto negativo è che è solo più lavoro. E 'uno sforzo maggiore. Dovete capire database. È necessario configurarlo. Hai bisogno di un server per l'esecuzione quest'ultima il. È necessario capire come configurarlo. Quindi questi sono solo questi tipi di trade-off. Considerando che un file CSV, è possibile creare con gedit. E tu sei a posto. Non c'è complessità di là di questo. 

Utilizzando un trie anziché una tabella hash con concatenazioni separate per memorizzare un dizionario delle parole che ricordano di pset5. Quindi cerca un rialzo, in teoria almeno, è ciò? Costante di tempo, almeno se siete hashing su ciascuno dei singoli le lettere in una parola, come voi potrebbe avere per pset5. Che potrebbe essere cinque, sei hash hash se ci sono cinque o sei lettere nella parola. E questo è abbastanza buono. E se c'è un limite superiore come lungo le vostre parole potrebbero essere, che è tempo infatti asintoticamente costante. 

Considerando che una tabella hash con separata concatenamento, il problema lì con quel tipo di struttura dati è che l' prestazioni di algoritmi di solito dipende dal numero di cose già nella struttura dati. E questo è sicuramente il caso di catene, per cui il più roba metti in una tabella hash, il più quelle catene andare, il che significa che nel peggiore caso, la cosa si potrebbe essere alla ricerca di è fino alla fine di una di quelle catene, che di fatto devolve in qualcosa di lineare. 

Ora, in pratica, potrebbe assolutamente essere il caso che una tabella hash con catene è più veloce di un corrispondente attuazione trie. Ma questo è per vari motivi, tra che sono tentativi utilizzano un sacco di memoria che può, infatti, le cose con calma giù, perché non si ottiene bello vantaggi di qualcosa che si chiama caching, dove le cose che sono vicine tra loro in memoria può essere letta spesso più rapidamente. E a volte si può trovare con davvero una buona funzione di hash. Anche se si deve sprecare un po 'di memoria, si potrebbe, infatti, essere in grado di trovare le cose in fretta e non così male come linearmente. 

Così, in breve, non c'era necessariamente con qualsiasi di questi uno o anche due cose specifiche che stavamo cercando. Davvero nulla convincente come un rialzo e al ribasso generalmente attirato la nostra attenzione. 

ROB BOWDEN: Quindi per il rialzo, abbiamo fatto Non accettare il suo "più veloce". Voi dovuto dire qualcosa al riguardo. Anche se lei ha detto teoricamente più veloce, sapevamo che tipo di capito che è 0 a 1. E tabella hash, in teoria, non è 0 a 1. La menzione nulla di runtime generalmente ottenuto i punti. Ma "più veloce", la maggior parte delle soluzioni su la grande tavola che sono stati tentativi erano oggettivamente più lento di soluzioni che erano tabelle hash. Così veloce in sé e per sé non è proprio vero. 

DAVID J. MALAN: Dom de dom dom. Probabilmente sono l'unico che realizza è così che questo dovrebbe essere pronunciata, giusto? 

ROB BOWDEN: non avevo davvero idea. 

DAVID J. MALAN: Ha fatto senso nella mia testa. 

ROB BOWDEN: sto facendo questo. OK. Quindi questo è quello dove si doveva disegnare il diagramma simile a voi potrebbe hanno visto negli esami precedenti. Così facciamo solo un'occhiata a questo. Quindi dal nodo HTML, abbiamo due bambini, la testa ed il corpo. Così abbiamo Branch - testa e il corpo. La testa ha un tag title. Quindi abbiamo un titolo. 

Ora, l'unica cosa che un sacco di gente dimenticato è che questi nodi di testo sono elementi all'interno di questo albero. Così qui ci capita di disegnarli come ovali per differenziarli da questi tipi di nodi. Ma notate anche qui abbiamo top, centro e in basso finirà per essere nodi di testo. Così dimenticare quelli era un po ' di un errore comune. 

Il corpo ha tre figli - questi tre div. Così div, div, div e poi il testo figli nodi di quei div. Questo è più o meno lo per che domande. 

DAVID J. MALAN: E vale la pena notare, anche se non ci soffermiamo su queste dettagli il tempo che passiamo su JavaScript, che l'ordine fa, in Infatti, la materia tecnicamente. Quindi, se la testa viene prima il corpo nel HTML, allora dovrebbe comparire il sinistra del corpo nel DOM reale. Che la sua è, in generale, solo Cordiali saluti, qualcosa chiamato nell'ordine del documento, in cui lo fa materia. E se tu fossi implementa un parser, un programma che legge HTML in costruzione l'albero in memoria, ad essere onesti, questo è probabilmente quello che intuitivamente fare comunque - dall'alto verso il basso, da sinistra a destra. 

ROB BOWDEN: domande su quello? Devo fare il prossimo? 

DAVID J. MALAN: Certo. 

ROB BOWDEN: OK. Quindi questo è il sovraccarico del buffer questione attacco. La cosa principale da riconoscere: ecco, bene, come potrebbe un trucco avversario questo programma in esecuzione codice arbitrario? Così argv1, la prima riga di comando argomento di questo programma, che può essere arbitrariamente lungo. Ma qui stiamo usando memcpy per copiare argv1, che qui è bar. Stiamo passando come argomento. E così sta prendendo sulla barra di nome. 

Quindi stiamo memcpying bar in questo buffer c. Quanti byte stiamo copiando? Beh, tuttavia molti byte bar succede a essere in uso, la lunghezza di tale argomento. Ma c è largo solo 12 byte. Quindi, se digitiamo un argomento della riga di comando che è più lungo di 12 byte, siamo andando a straripare questo particolare buffer. Ora, come potrebbe un avversario ingannare l' programmare in esecuzione di codice arbitrario? 

Quindi ricorda che qui principale sta chiamando foo. E così poi chiamate principali foo. Cerchiamo di disegnare questo. Quindi abbiamo il nostro stack. Ed principale ha uno stack frame nella parte inferiore. Ad un certo punto, le chiamate principali foo. Ebbene, subito, chiamate principali foo. E così foo ottiene il proprio stack frame. 

Ora, a un certo punto, foo sta per tornare. E andò ritorni foo, abbiamo bisogno di sapere a quale linea di codice all'interno di noi principale erano per sapere dove dobbiamo riprendere principale. Possiamo chiamare foo da tutta una mucchio di luoghi diversi. Come facciamo a sapere dove tornare? Bene, abbiamo bisogno di memorizzare che da qualche parte. 

Così da qualche parte proprio qui, archiviamo dove dovremmo tornare a una volta foo ritorni. E questo è l'indirizzo di ritorno. Così come un avversario potrebbe sfruttare di ciò è il fatto che questo buffer c è immagazzinato, LET'S dire, proprio qui è c. Quindi abbiamo 12 byte per c. Questo è c. E questo è l'anello stack di foo. Quindi, se l'utente malintenzionato entra più byte di 12 o entrano in un comando argomento della linea che è più lungo di 12 personaggi, allora stiamo andando a traboccare questo buffer. 

Possiamo andare avanti. E a un certo punto, andiamo lontano basta che iniziamo sovrascrivendo l'indirizzo di ritorno. Quindi, una volta che sovrascrivere l'indirizzo di ritorno, questo significa che quando foo ritorna, stiamo tornando ovunque l' utente malintenzionato sta dicendo a da qualsiasi valore è entrato, con qualsiasi caratteri che l'utente inserito. E così, se l'utente malintenzionato è in corso particolarmente intelligente, può avere questo tornare da qualche parte nel printDef funzione o da qualche parte nel malloc funzione, solo ovunque arbitraria. 

Ma ancora più intelligente è quello che se ha l'utente ritornare al proprio qui. E poi si inizia l'esecuzione questi come linee di codice. A quel punto, l'utente può immettere quello che vuole in questa regione. E lui ha il controllo completo sopra il vostro programma. Domande su questo? Quindi la domanda successiva è completa l' reimplementazione di foo in modo tale che non è più vulnerabile. 

Quindi ci sono un paio di modi avresti potuto fare questo. Abbiamo ancora solo c essendo di lunghezza 12. Si potrebbe avere modificato questo come parte della soluzione. Abbiamo anche aggiunto un controllo per fare Assicurarsi bar non era nulla. Anche se non hai bisogno che per il credito pieno. Quindi stiamo controllando prima la lunghezza della stringa di bar. Se è maggiore di 12, allora realtà non non fare la copia. Ecco, questo è un modo di risolverlo. 

Un altro modo di fissaggio è invece avendo c sia solo di lunghezza 12, l'hanno essere di lunghezza strlen (bar). Un altro modo di fissaggio è in realtà solo ritorno. Quindi, se si fosse appena deciso di eliminare tutti questo, se si fosse appena cancellato tutti righe di codice, si avrebbero ottenuto pieno credito, poiché questa funzione in realtà non realizzare nulla. E 'copiare la riga di comando argomento in qualche array in il suo stack frame locale. E poi la cosa sta tornando. E qualunque cosa compiuta è andato. Quindi ritorno è stato anche un sufficiente modo di ottenere credito pieno. 

DAVID J. MALAN: Non è proprio lo spirito di la domanda ma accettabile per la spec comunque. 

ROB BOWDEN: Domande sulla niente di tutto questo? L'unica cosa che almeno necessaria per avere la compilazione del codice. Quindi, anche se tecnicamente non si è vulnerabili se il codice non compilare, non abbiamo accettiamo che. Nessuna domanda? OK. 

DAVID J. MALAN: Volete dire questo titolo? 

ROB BOWDEN: No. 

David J. MALAN: Quindi, in questa, questa era sia una buona notizia o una cattiva notizia. Questo è letteralmente lo stesso problema come il primo quiz. Ed è quasi la stessa problema come pset1. Ma è stato volutamente semplificato per essere una piramide più semplice, che può essere risolto con un po ' semplice iterazione. E in realtà, ciò che noi stavamo a qui non era tanto la logica, perché probabilmente, a questo punto, siete più comodo di quello che erano in settimana uno con i cicli for o perché loop, ma in realtà per prendere in giro a parte che sei un po agio con la nozione che PHP non è solo quello programmazione. Si può effettivamente essere utilizzato come un linguaggio scrivere programmi da linea di comando. 

E in effetti, questo è quello che stavamo cercando per attirare la vostra attenzione. Questo è un programma PHP a riga di comando. Quindi, il codice C qui, mentre corretto in C, non correggere per PHP. Ma il codice è davvero la stessa. Se si confrontano le soluzioni per Quiz 0 contro il Quiz 1, vi accorgerete che è quasi identico, tranne alcuni segni del dollaro e per l' assenza di un tipo di dati. In particolare, se diamo uno sguardo qui, vedrai che iteriamo, in questo caso, da 1 a 7. 

Avremmo potuto fare lo 0 indice. Ma a volte, penso che sia solo mentalmente più facile pensare a cose da 1 a 7. Se si desidera che un blocco, poi due blocchi, poi tre, poi dot, dot, dot sette. Abbiamo j essere inizializzato a 1 e poi contare su un massimo di i. E tutto qui è altrimenti identico. Ma degni di nota sono un paio di cose. Noi vi diamo queste due righe, questo primo uno, goffamente nominato come una faccenda per il colpo secco. E che specifica solo il percorso, la cartella, in cui un programma può essere scoperto che si desidera utilizzare interpretare questo file. 

E poi la riga dopo che, di naturalmente, significa entrare in modalità PHP. E la linea in fondo significa uscire dalla modalità PHP. E questo funziona, in generale, con interpretato lingue. È un po 'fastidioso se si scrive un programma in un file chiamato foo.php. E poi gli utenti devono semplicemente ricordare, OK, per eseguire questo programma, ho necessario digitare "spazio php foo.php." Tipo di fastidioso se non altro. E rivela anche che il programma è scritto in PHP, che non è tutto che illuminante per l'utente. 

Quindi, è possibile rimuovere il. Php tutto richiamare da lezione. E si può effettivamente fare. / Pippo se hai chmodded esso rendendolo eseguibile. Così chmod a + x pippo avrebbe fatto. E se anche si aggiunge la baracca qui. Ma in realtà, il problema stava a stampare qualcosa di simile. No HTML, nessun codice C certamente, solo alcuni PHP. Così Milo poi tornato in problema 25. E nel 25, è stata data la seguente codice scheletro, che era un abbastanza semplice pagina web. E la parte succosa HTML-saggio era giù qui, dove abbiamo all'interno del corpo una forma che ha ID univoco di ingressi all'interno del quale era due ingressi, uno con un'idea di nome, una con un'idea di tasto. 

Il primo era tipo di testo, il secondo di tipo submit. E così vi abbiamo dato, in realtà, più ingredienti che avete avuto bisogno, solo così voi ragazzi avevano opzioni con le quali per risolvere questo problema. Non è strettamente necessario tutti questi ID. Ma permette di risolvere in modi diversi. E in cima, si noti che l'obiettivo era quello di innescare una finestra come questa - Ciao, Milo! - a pop-up nel browser utilizzando il super semplice, se non brutto, funzione di avviso. E così, in ultima analisi, questo si riduce concettualmente ad ascoltare qualche modo per osservazioni del lato client forma , Non il lato server, in qualche modo in risposta alla suddetta presentazione da afferrando il valore che l'utente ha digitato per il campo del nome, e poi visualizzarlo nel corpo di un avviso. 

Quindi un modo che si può fare questo è con jQuery, che sembra un po ' sintatticamente perplessi in un primo momento. È possibile farlo con il codice DOM puro - document.getelement da ID. Ma diamo un'occhiata a questa versione. Ho un paio di importanti linee prima. Così uno, disponiamo di questa linea, che è identico a quello che si potrebbe avere visto in, credo, form2.html dalla classe in settimana 9. E questo è solo dicendo, eseguire il codice seguente il documento è pronto. Questo essere importante solo perché Le pagine HTML vengono lette dall'alto verso il in basso, da sinistra a destra. 

E quindi, se si tenta di fare qualcosa nel codice qui a qualche DOM elemento, alcuni tag HTML, che è giù Qui, si sta facendo troppo presto, perché questo ha nemmeno stato letto in memoria. Così dicendo questo document.ready linea, stiamo dicendo, ecco qualche codice del browser. Ma non eseguire questo fino a quando l'intero documento è pronto, pari al DOM albero esiste in memoria. Questo è un po 'più semplice, se sintatticamente un po 'diverso, dove sto dicendo, afferrare l'elemento HTML il cui unico identificatore è ingressi. Questo è ciò che l'hash tag denota, l'ID univoco. E poi sto chiamando. Presentare. 

Quindi. Presentare qui è una funzione, altrimenti noto come metodo, che è all'interno dell'oggetto sulla mano sinistra lato c'è che non ho evidenziare. Quindi, se pensate di input come un oggetto nella memoria - e infatti lo è. E 'un nodo in un albero - . Presentare mezzi quando questo form con questo ID è presentata, eseguire il seguente codice. Non mi interessa che cosa il nome del funzione è sto esecuzione. Così qui sto usando, come prima, ciò che è chiamato la funzione lambda o un funzione anonima. Non è affatto intellettualmente interessante diverso da quello che non ha un nome, che va bene se sei solo mai andare a chiamare una volta. E dentro ci ho effettivamente gestire l'invio del modulo. Io prima dichiarare una variabile chiamato valore. E allora qual è l'effetto di questa evidenziato porzione qui ora? Che cosa fare in un alto livello per me? 

AUDIENCE: Ottiene il valore che l' l'utente non ha nel codice HTML qui sotto. Si ottiene che ID e poi rileva che il valore di esso. 

DAVID J. MALAN: Esattamente. Si afferra il nodo, la cui unica identificatore è il nome. Si ottiene il valore in esso, che è, presumibilmente, ciò che l'utente lui o lei digitato. E poi memorizza che nella variabile chiamata valore. Per inciso, si potrebbe avere anche fatto un po 'diverso. Assolutamente accettabile facendo qualcosa valore bugia var ottiene document.getElementById. Ed è per questo che è un po ' noioso non utilizzare jQuery. "Name" value.. Quindi assolutamente accettabile. Diversi modi per farlo. jQuery solo tende ad essere un po 'più succinta e sicuramente più popolare tra i programmatori. 

Ora, io sto facendo un po 'di sanità mentale controllare, perché nel problema dichiarazione abbiamo esplicitamente detto, se il utente non ha ancora digitato suo nome, non mostrano una avvisi. Ma è possibile verificare che, appena controllando la stringa vuota per un quote-unquote se c'è nulla in realtà c'è. Ma se non è uguale a quote-unquote, Voglio chiamare avvisi. E la parte interessante è che stiamo usando l'operatore più, che fa che cosa in JavaScript? Concatenare. Così è come phps operatore punto. Stessa idea, sintassi leggermente diversa. E sto solo creando la stringa che avete visto la schermata - Ciao, così e così. 

E poi l'ultimo dettaglio è questo. Perché torno falso interno di questa funzione anonima? 

AUDIENCE: Non c'è nessun valore. Hai messo in forma. Dice solo, se il valore non è pari a vuoto, allora fatelo. C'era un vuoto in questo mezzo. 

DAVID J. MALAN: OK. Attenzione però. Non c'è nessun altro qui. E che il ritorno falso è al di fuori del se le condizioni. Quindi questo ha evidenziato linea, restituire false, esegue qualunque cosa quando il modulo viene inviato. Cosa fa ritorno falso interno di questo gestore di eventi, come viene chiamato, l'evento in questione essendo presentazione? 

AUDIENCE: Perché accade solo una volta. 

DAVID J. MALAN: succede solo una volta. Non proprio. Sì? 

AUDIENCE: Impedisce il modulo dal sottoponendo al comportamento predefinito, che renderebbe il ricaricamento della pagina. 

DAVID J. MALAN: Esattamente. Così sto sovraccaricare il termine presentare qui, perché sto dicendo, la forma è presentata. Ma, come lei suggerisce, in realtà non è stata presentata in modo HTTP vero. Quando si fa clic su Invia, a causa della nostra handler onSubmit, stiamo intercettando che la presentazione forma per così dire. Stiamo poi facendo le nostre cose con il codice JavaScript. Ma sto tornando volutamente false, perché quello che io non voglio che accada un frazione di secondo più tardi è per l'intero modulo si da sottoporre al web server con coppie di valori chiave cambiando l'URL di essere qualcosa di simile q = gatti o qualsiasi altra cosa che abbiamo fatto, per esempio, in classe. Io non voglio che ciò accada, perché non c'è ascolto server per questo modulo di presentazione. E 'puramente fatto in codice JavaScript. Ed è per questo che non ho nemmeno un azione attributo sulla mia forma, perché io non intendono per questo mai andare al server. 

Quindi è in corso di presentazione. Ma stiamo intercettando quella forma presentazione e prevenire il default comportamento, che è effettivamente andare fino in fondo al server. 

AUDIENCE: Così mantenendolo client-side. 

DAVID J. MALAN: Mantenere esso lato client. Esattamente. Next up era la mia oh MySQL. 

ROB BOWDEN: OK. Quindi questa prima domanda è stata generalmente di massima per le persone. Anche se quelle successive sono andate meglio. Così si doveva scegliere i dati corretti tipi per entrambe queste colonne. Ed entrambi hanno una certa cose su di loro che rendere la scelta difficile. Quindi int non era un valido tipo di numero. Il motivo è un conto a 12 cifre numero, un int non è abbastanza grande per memorizzare le cifre totali. Quindi una scelta valida sarebbe stato un grande int se vi capita di sapere che. Un'altra scelta avrebbe potuto essere un campo char di lunghezza 12. Quindi, o di coloro che avrebbero funzionato. Int. no. 

Ora, equilibrio, ripensare a pset7. Così abbiamo specificamente usato decimale memorizzare il valore delle azioni o - 

DAVID J. MALAN: Cash. 

ROB BOWDEN: Cash. Abbiamo usato decimale per memorizzare la quantità di denaro che l'utente ha attualmente. Quindi la ragione che facciamo che è perché, ricordate, galleggianti. C'è virgola mobile in precisione. Esso non può memorizzare precisamente la cassa valori come vogliamo qui. Quindi decimale è in grado di precisione negozio qualcosa, dire, due decimali. Ecco perché l'equilibrio, lo vogliamo essere decimale e non galleggiare. 

DAVID J. MALAN: E poi, troppo, anche se avrebbe potuto essere abile in altri contesti a cui pensare, forse questo è una possibilità per un int. Mi limiterò a tenere traccia di cose in centesimi. Perché abbiamo mostrato esplicitamente il default valore dell'essere 100.00, che significa che potrebbe essere solo un int. E un altro sottigliezza troppo con il numero era che non doveva per essere una domanda trabocchetto. Ma ricordare che un int in MySQL, come in C, almeno nella apparecchio, è a 32 bit. E anche se noi non ci aspettiamo di sapere esattamente quante cifre mezzi, mi ricordo che il maggior numero è possibile rappresentare potenzialmente con un numero a 32 bit è più o meno che cosa? 

Che numero possiamo sempre dire? 2 a 32, che è ciò che all'incirca? Non è necessario conoscere con precisione. Ma grosso modo è utile nella vita. Si tratta di circa 4 miliardi. Quindi abbiamo detto che un paio di volte. So che ho detto che un paio di volte. Ed è di circa 4 miliardi. E questa è una buona regola di pollice di sapere. Se si dispone di 8 bit, 256 è il numero magico. Se si dispone di 32 bit, 4 miliardi di prendere o lasciare. Quindi, se avete appena annotate 4 miliardi, vedrai che è meno cifre di 12, il che significa che non è chiaramente sufficiente espressività per catturare una Numero di conto a 12 cifre. 

ROB BOWDEN: OK. Così gli altri sono andati meglio. Quindi supponiamo che la banca impone un 20 dollari mensili canone di manutenzione su tutti i conti. Con quali query SQL potrebbe la banca dedurre $ 20 da ogni conteggio, anche se risulta in alcuni saldi negativi? Quindi, fondamentalmente, ci sono quattro principali tipi di query - Inserisci, selezionare, aggiornare ed eliminare. Allora cosa pensiamo di essere intenzione di utilizzare qui? Aggiornare. 

Quindi diamo un'occhiata. Così qui stiamo aggiornando. Cosa tabella stiamo aggiornando account? Così l'aggiornamento dei conti. E poi la sintassi dice, cosa nei conti stiamo aggiornando? Beh, stiamo impostando saldo pari al il valore corrente della bilancia meno 20. Quindi questo aggiornerà tutte le righe dei conti, sottraendo $ 20 dalla bilancia. 

DAVID J. MALAN: Un errore comune qui, anche se a volte perdonato esso, era di avere effettivamente il codice PHP qui chiamando la funzione di query o la messa virgolette attorno tutto ciò che non ha bisogno di essere lì. 

ROB BOWDEN: Ricordate che MySQL è un linguaggio separato da PHP. Ci capita di scrivere MySQL in PHP. E PHP viene poi trasmette il verso il server MySQL. Ma non avete bisogno di PHP al fine di comunicare con un server MySQL. 

DAVID J. MALAN: Esattamente. Quindi niente variabili con il segno del dollaro dovrebbe essere in questo contesto. Si può solo fare tutti i calcoli all'interno del database. 

ROB BOWDEN: OK. Quindi il prossimo. E 'questo il prossimo? Già. Quindi, con quello query SQL potrebbe la banca recuperare i numeri di conto dei suoi i clienti più ricchi, quelli con saldi superiori a 1.000? Quindi quale dei quattro tipi principali stiamo andando a voler qui? Selezionare. Quindi vogliamo selezionare. Cosa vogliamo selezionare? Cosa colonna vogliamo selezionare? Noi in particolare vuole per selezionare il numero. Ma se lei ha detto stella, abbiamo anche ammesso che. 

Quindi, selezionare il numero da quale tabella? Conti. E allora la condizione che vogliamo? Dove saldo superiore a 1.000. Abbiamo anche accettato una maggiore o uguale. Ultimo. Con quali query SQL potrebbe la banca chiudere, vale a dire, eliminare ogni account che ha un saldo di € 0? Quindi, quale dei quattro siamo andando a voler usare? Elimina. Così la sintassi per questo? Elimina dalla quale tavolo? Conti. E allora la condizione in cui Vogliamo eliminare - dove l'equilibrio è uguale a zero. Quindi, eliminare tutte le righe di conti dove il saldo è zero. Domande su uno di questi? Vuoi fare la fila? 

DAVID J. MALAN: Guida coda. Quindi, in questo, vi abbiamo dato un po ' struttura familiare che abbiamo esplorato un po 'in classe insieme di struct, che era un dato struttura relativa nello spirito. La differenza però con una coda è che abbiamo dovuto ricordare che in qualche modo era sul davanti della coda, in grande parte in modo che potessimo fare più uso efficiente della memoria, almeno se stessimo usando un array. 

Perché richiamo, se abbiamo un array, se, per esempio, questo è il fronte la coda, se mi trovo in coda qui, e poi qualcuno si mette in linea dietro di me, dietro di me, dietro di me, e una persona esce di linea, potrebbe, come abbiamo visto alcuni dei nostri umana volontari in classe, hanno tutti spostare in questo modo. Ma in generale, avendo ognuno faccia qualcosa non è il miglior uso del tempo in un programma, perché significa che il l'algoritmo è in esecuzione in quanto tempo di esecuzione asintotico? E 'lineare. 

E mi sento come che una specie di stupido. Se la persona successiva nella fila è quello persona che si suppone di andare in negozio, non tutti hanno a muoversi insieme. Basta che quella persona sia colto off quando arriva il momento, per esempio. Così possiamo risparmiare un po 'di tempo lì. E così, per fare ciò, però, che i mezzi che la testa della coda o l' anteriore della coda sta per progressivamente spostare sempre più in profondità nella matrice e alla fine potrebbe in realtà avvolgere intorno se stiamo usando un matrice per memorizzare il popolo in questa coda. Così si può quasi pensare al array come un dato circolare struttura in questo senso. 

Quindi devi in ​​qualche modo a tenere traccia del dimensioni di esso o realmente la fine di esso e poi dove l'inizio è. Quindi noi proponiamo che si dichiara una tale coda, chiamata esso q, solo una lettera. Allora noi proponiamo che la parte anteriore sia inizializzato a zero e che la dimensione essere inizializzato a zero. 

Così adesso, non c'è nulla all'interno di tale coda. E vi chiediamo di completare l' attuazione di accodamento di seguito in modo tale che la funzione aggiunge n per fine di q e quindi restituisce true. Ma se q è pieno o negativo, la funzione dovrebbe invece restituire false. E vi abbiamo dato una coppia di ipotesi. Ma non sono realmente funzionale rilevante, solo che bool esiste, perché, tecnicamente, bool non esistere in C, a meno di includere un certo file di intestazione. Così che è stato appena assicurarsi che non vi Non sono stati questo è un trucchetto questione genere di cose. 

Così enqueue, abbiamo proposto nel campione soluzioni per implementare come segue. Uno, per prima cosa controlliamo la facilità, la frutta a basso impiccagione. Se la coda è piena o il numero che si sta cercando di inserire è meno di zero, che abbiamo detto nella specifica del problema dovrebbe non essere consentito, perché vogliamo solo I valori non negativi, allora si dovrebbe semplicemente restituire false immediatamente. Così alcuni relativamente facile il controllo degli errori. Se però si desidera aggiungere quella attuale numero, si doveva fare un po 'di pensare qui. Ed è qui che è un po 'fastidioso mentalmente, perché si deve capire come gestire avvolgente. 

Ma il germe dell'idea qui che è di interesse per noi è che avvolgente spesso implica l'aritmetica modulare e l'operatore mod, il lato per cento, dove si può andare da un valore maggiore torna a zero e poi uno e due e tre e poi indietro intorno a zero, uno e due e tre e così via ancora e ancora. Quindi il modo in cui si propone di fare questo è che noi vogliamo indice nella array chiamato i numeri in cui i nostri numeri interi mentono. Ma per arrivarci, dobbiamo prima vogliamo fare qualunque sia la dimensione della coda è ma poi aggiungere che qualunque sia la anteriore della lista è. E l'effetto di ciò è di metterci a la giusta posizione in coda e Non dare per scontato che la prima persona in linea è all'inizio, che egli o lei assolutamente potrebbe essere se si erano anche spostando tutti. Ma stiamo solo creando lavoro per noi stessi, se abbiamo preso quel particolare percorso. 

Così possiamo mantenere relativamente semplice. Noi dobbiamo ricordare che abbiamo appena aggiunto un int alla coda. E poi abbiamo appena torniamo vero. Nel frattempo, in dequeue, abbiamo chiesto a fare quanto segue. Attuarlo in modo tale che essa viene eliminata dalla coda, cioè rimuove e ritorna, int nella parte anteriore della coda. Per rimuovere l'int, è sufficiente di dimenticarlo. Non è necessario eseguire l'override suo bit. Quindi è ancora effettivamente lì. Proprio come i dati su un disco rigido, stiamo solo ignorando il fatto che ora è lì. E se q è vuota, dovremmo invece di ritorno negativo 1. Quindi, questo si sente arbitraria. Perché ritorno negativo 1 invece di falso? Già. 

AUDIENCE: Q sta memorizzando valori positivi. Dal momento che si memorizzano solo valori positivi nel q, negativo è un errore. 

DAVID J. MALAN: OK, è vero. Quindi perché stiamo memorizzando solo positivo valori o zero, allora è bene per restituire un valore negativo come una sentinella valore, un simbolo speciale. Ma si sta riscrivendo la storia lì, perché la ragione siamo solo restituzione di valori non negativi è perché vogliamo avere un valore sentinella. Quindi, più in particolare, perché non solo return false in caso di errori? Già. 

AUDIENCE: hai fallito per restituire un numero intero. 

DAVID J. MALAN: Esattamente. E questo è dove ottiene C piuttosto vincolante. Se stai dicendo che stai andando per restituire un int, hai per restituire un int. Non è possibile ottenere l'immaginazione e iniziare il ritorno un bool o di un galleggiante o di un stringa o qualcosa di simile. Ora, intanto, JavaScript e PHP e alcune altre lingue può, infatti, avete ritorno diverso tipi di valori. E che può effettivamente essere utile, se si potrebbe tornare ints positivi, zeri, interi negativi, o false o null anche per significare errore. Ma noi non abbiamo che versatilità in C. 

Quindi, con dequeue, quello che abbiamo proporre di fare è - 

ROB BOWDEN: È possibile restituire false. E 'solo che è falso hash definire falso a zero. Quindi, se si torna false, stai tornando a zero. E zero è una cosa valida nella nostra coda, considerando che negativo 1 non è se falso capitato di essere negativa 1. Ma non si dovrebbe nemmeno bisogno di sapere che. 

DAVID J. MALAN: Ecco perché io non lo dissi. 

ROB BOWDEN: Ma non era vero che non si può restituire false. 

DAVID J. MALAN: Certo. Così dequeue, notiamo accettiamo invalidare come argomento. E questo perché non siamo passando nulla dentro Vogliamo solo rimuovere l'elemento nella parte anteriore della coda. Così come potremmo fare per fare questo? Beh, in primo luogo, cerchiamo di fare questo controllo di integrità rapido. Se la dimensione della coda è 0, non c'è nessun lavoro da fare. Rientro negativo 1. Fatto. Ecco, questo è poche righe del mio programma. Quindi solo quattro linee rimangono. 

Così qui ho deciso di diminuire la dimensione. E decrementare la dimensione efficacemente significa che sto dimenticando qualcosa è in là. Ma devo anche aggiornare dove la parte anteriore dei numeri sono. Quindi, per fare questo, ho bisogno di fare due cose. Ho bisogno di ricordare ciò che il numero è nella parte anteriore della coda, perché ho bisogno di tornare quella cosa. Quindi io non voglio dimenticare accidentalmente su di esso e quindi sovrascrivere. Sto solo andando a ricordare in un int. 

E ora, voglio aggiornare q.front da q.front +1. Quindi, se questa è stata la prima persona in linea, ora, voglio fare più 1 per puntare alla prossima persona in linea. Ma devo gestire tale avvolgente. E se la capacità è una costante globale, che sta per permettermi di assicurarsi come indico l'ultima persona in linea, l'operazione di modulo porterà mi riporta a zero al anteriore della coda. E che gestisce l'avvolgente qui. E poi procedo per tornare n. 

Ora, a rigor di termini, non l'ho fatto devono dichiarare n. Non ho avuto per afferrarla e riporlo temporaneamente, perché il valore è ancora lì. Così ho potuto solo fare la media aritmetica di destra al ritorno l'ex capo della coda. Ma ho appena sentito che questo era più chiaro per afferrare effettivamente l'int, metterlo n, e poi tornare che per amor di chiarezza, ma non strettamente necessario. Psst. Sono tutti pronunciabile nella mia testa. 

ROB BOWDEN: Quindi prima questione è il problema albero binario. Quindi prima domanda è, siamo dato questi numeri. E vogliamo inserirli in qualche modo in questi nodi tale che è un valida albero binario di ricerca. Quindi l'unica cosa da ricordare su alberi binari di ricerca è che non è solo che la cosa di sinistra è minore e la cosa il diritto è maggiore. Deve essere che l'intero albero di la sinistra è meno, e l'intero albero a destra è maggiore. 

Quindi, se ho messo 34 qui in alto, e poi Ho messo 20 qui, quindi questo è valido così lontano, perché 34 quassù. 20 sta a sinistra. Ecco, questo è meno. Ma non posso poi mettere 59 qui, perché anche se 59 è sulla destra 20, è ancora a sinistra 34. Quindi, con questo vincolo in mente, il modo più semplice di risolvere questo probabilmente problema è proprio ordinamento di questi numeri - così 20, 34, 36, 52, 59, 106. E quindi inserire quelli da sinistra a destra. 

Quindi 20 va qui. 34 va qui. 36 va qui. 52, 59, 106. E si potrebbe anche aver capito con un po 'di collegare e realizzare, oh, aspetta, non ho abbastanza numeri per colmare questo qui. Quindi ho bisogno tornate di nuovo ciò che il mio nota percorso sta per essere. Ma si noti che in finale tre, se si legge da sinistra a destra, è in ordine crescente. 

Così ora, vogliamo dichiarare ciò che l' struct sta per essere per il nodi di questo albero. Così che cosa abbiamo bisogno in un albero binario? Quindi abbiamo un valore di tipo int, quindi un valore int. Non so quello che abbiamo chiamato nella soluzione - int n. Abbiamo bisogno di un puntatore al figlio sinistro e un puntatore al figlio destro. Così sta andando a guardare come questo. E sarà effettivamente sembrare prima quando ha doppiamente legata elenco roba, quindi gara - Ho intenzione di dover scorrere tutta la via del ritorno verso il basso per problema 11. 

Quindi notare sembra identica a questa, tranne che abbiamo appena capita di chiamare questi nomi diversi. Abbiamo ancora un numero intero valore e due puntatori. E 'solo che invece di trattare la puntatori come indica la prossima cosa e la cosa precedente, stiamo trattando i puntatori per puntare a un figlio sinistro e il figlio destro. OK. Ecco, questo è il nostro nodo struct. E ora, l'unica funzione che abbiamo bisogno di l'attuazione di questo è traversata, che vogliamo andare oltre l'albero, stampa i valori dell'albero in ordine. 

Quindi, guardando qui, vorremmo stampare su 20, 34, 36, 52, 59, e 106. Come possiamo raggiungere questo? Quindi è abbastanza simile. Se avete visto l'esame passato il problema che si voleva stampare l'intero albero con delle virgole tra tutto, in realtà è stato anche facile di quello. Quindi, ecco la soluzione. Questo era significativamente più facile se l'avete fatto in modo ricorsivo. Non so se qualcuno ha tentato per farlo in modo iterativo. 

Ma prima, abbiamo il nostro caso base. Che cosa succede se la radice è nullo? Poi stiamo solo andando a tornare. Noi non vogliamo stampare nulla. Altrimenti stiamo per attraversare ricorsivamente giù. Stampa l'intero sottoalbero sinistro. Così stampare tutto meno che il mio valore corrente. E poi ho intenzione di stampare me stesso. E poi ho intenzione di ricorsione la mia intero sottoalbero destro, quindi tutto maggiore del mio valore. E questo sta andando per la stampa fuori tutto in ordine. Domande su come questo in realtà compie questo? 

PUBBLICO: Ho una domanda il [incomprensibile]. 

ROB BOWDEN: Quindi un modo di affrontare qualsiasi problema ricorsiva è quello di pensare solo su di esso come si deve pensare su tutti i casi d'angolo. Quindi consideriamo che vogliamo stampare l'intero albero. Quindi tutto quello che stiamo andando a concentrarsi su è questo particolare nodo - 36. Le chiamate ricorsive, facciamo finta quelli appena funzionano. Ecco, questa chiamata ricorsiva traversata, noi senza nemmeno pensarci a questo proposito, basta attraversare sinistra tre, immaginare che stampa già 20 e 34 per noi. E poi quando abbiamo finalmente ricorsivamente chiamare traversata sul destra, che verrà corretto stampare 52, 59, e 106 per noi. 

Quindi, dato che questo può stampare 20, 34, e l'altro può stampare 52, 59, 108, tutti abbiamo bisogno di essere in grado di fare è stampare noi stessi nel mezzo di questo. Così stampare tutto prima di noi. Stampare noi stessi, in modo che la stampa nodo corrente 36, printf regolare, e quindi stampare tutto dopo di noi. 

DAVID J. MALAN: Questo è dove ricorsione diventa veramente bello. E 'questo incredibile atto di fede in cui si fa il più piccolo frammento di lavoro. E poi si lascia qualcuno altro fare il resto. E che qualcun altro è, ironia della sorte, si. Così, per gravi punti brownie, se scorrere verso l'alto sulle domande - 

ROB BOWDEN: Sulle domande? 

DAVID J. MALAN: E giù un po 'di i numeri, qualcuno sa dove questi numeri vengono? 

ROB BOWDEN: ho letteralmente idea. 

DAVID J. MALAN: Appaiono tutto il quiz. 

AUDIENCE: Sono gli stessi numeri? 

DAVID J. MALAN: Quei numeri. Un po 'di uovo di Pasqua. Quindi, per quelli di voi guardando online casa, se potete dirci via e-mail a heads@CS50.net cosa il significato di questi ricorrenti sei numeri sono tutta Quiz 1, saremo doccia voi con un'attenzione incredibile alla finale conferenza e una palla stress. Nizza, sottile. 

ROB BOWDEN: Tutte le ultime domande qualsiasi cosa sul quiz?