[Powered by Google Translate] [Settimana 6] [David J. Malan] [Harvard University] [Questo è CS50.] [CS50.TV] 

Questo è CS50, e questo è l'inizio della settimana 6, quindi un paio di nuovi strumenti sono ora disponibili per voi di sfruttare, il primo dei quali è chiamato CS50 Style. Le probabilità sono, se siete come me o uno dei compagni di insegnamento, probabilmente avete visto un programma il cui stile sembra un po 'di qualcosa come questo. Forse iniziare a tagliare alcune curve a tarda notte, o ne occuperemo in un secondo momento, e poi un TF o CA si avvicina in orario d'ufficio. Poi è difficile per noi da leggere. Beh, questo codice è sintatticamente corretta, e si compila, e sarà effettivamente eseguito. Ma non è sicuramente un 5 per stile. 

Ma ora, se andiamo in questa directory qui- e notare che ho conditions2.c- e corro questo nuovo comando, style50, su questo conditions2.c file, Invio, notare che è mi ha informato che è stata stilizzata. Gedit notato che il file è stato modificato su disco, e se si sceglie ricaricare, tutti i vostri problemi sono ora automatici. [Applausi] Questa è una delle cose che abbiamo fatto in questo fine settimana. Rendetevi conto che è imperfetta, perché ci sono un po 'di codice che semplicemente non sarà in grado di stilizzare perfettamente, ma rendo conto che questo è ormai uno strumento che può trarre vantaggio se non altro per riordinare alcune delle parentesi più errantly posto ricci e simili. 

Ma più interessante è ora CS50 Check. Con CS50 Check, si può effettivamente eseguire le prove di correttezza stessi il proprio codice che i compagni sono in grado di insegnamento. Si tratta di una utility a riga di comando che è ora disponibile in dell'apparecchio non appena si fa un update50 secondo pset 4 Specifiche, e lo si utilizza essenzialmente come questo. Si esegue il comando check50. Poi si passa in un argomento della riga di comando, o più generalmente conosciuto come un interruttore o una bandiera. In generale, le cose che hanno trattini sono chiamati uno switch per un programma a riga di comando, in modo da-c specifica i controlli che si desidera eseguire. 

I test che si desidera eseguire sono identificati in modo univoco da questa stringa, 2012/pset4/resize. In altre parole, questo è solo una stringa arbitraria, ma unico nel suo genere che usiamo per identificare in modo univoco i test di correttezza 4 pset. E poi si specifica un elenco separato da spazi dei file che si desidera caricare per CS50 Controllare per l'analisi. Per esempio, se vado nella mia soluzione qui per resize.c- vorrei aprire un terminale più grande finestra- e vado avanti ed eseguire diciamo check50-c 2012/pset4/resize, e poi andare avanti e specificare i nomi dei file, resize.c, e quindi premere Invio, si comprime, esso arrivi, controlla, e ho appena fallito un sacco di prove. Quello in rosso in alto a sinistra dice che resize.c e bmp esistono. Questa era la prova. Questa era la domanda abbiamo chiesto. Ed è infelice perché la risposta era falsa. Il testo bianco sotto che dice dovrebbe bmp.h di esistere, e questo è solo colpa mia. Ho dimenticato di caricarlo, quindi ho bisogno di caricare entrambi i file, resize.c e bmp.h. Ma ora vedere tutte le altre prove sono di colore giallo, perché non sono stati eseguiti, e così la faccina è verticale perché è né felice né triste, ma dobbiamo correggere questo problema in rosso prima di tali controlli gli altri verrà eseguito. 

Vorrei risolvere questo problema. Vorrei diminuire ed eseguire di nuovo questo, questa volta con bmp.h anche sulla riga di comando, Invio, e ora se tutto va bene, è andare a controllare e poi restituire un risultato di-trattenere il respiro- tutto verde, il che significa che sto facendo molto bene su pset 4 finora. Si può vedere e dedurre dal testo descrittivo qui esattamente quello che abbiamo provato. Abbiamo testato prima fare i file esistono? Abbiamo poi testato viene compilato resize.c? Poi abbiamo provato non lo ridimensionare una 1x1 pixel BMP quando n, il fattore di ridimensionamento, è 1. Ora, se non avete idea di cosa n è, una volta che si sarà tuffarsi pset 4, ma che è semplicemente un controllo di integrità per assicurarsi che non sei il ridimensionamento un'immagine a tutti, se il fattore di ridimensionamento è 1. Se, invece, viene ridimensionato un pixel 1x1 ad una 1x1 pixel BMP a 2x2 correttamente quando n è 2, analogamente, la mia forma conseguenza. 

In breve, questo è destinato a, uno, prendere le attraversano le dita dall'equazione di destra prima di inviare il tuo pset. Saprete esattamente che cosa il vostro TF presto sapere quando si va sull'invio di alcuni di questi insiemi di problemi, e anche la motivazione pedagogica è davvero di mettere l'opportunità di fronte a voi in modo che quando si conosce a priori che ci sono errori nel codice e delle prove che non sono passati, si può mettere in più tempo efficace in attacco per risolvere questi problemi piuttosto che perdere punti, ottenere un feedback dal TF, e poi, "Ahh," come avrei capito. Ora almeno c'è uno strumento per aiutarti a trovare questo. E non ha intenzione di indicare dove il bug è, ma vi dirà ciò è sintomatico di esso. 

Ora realizzare i test non sono necessariamente esaustive. Solo perché si ottiene una schermata piena di verde facce smiley non significa che il codice è perfetto, ma significa che ha superato le prove di alcune prescritte dalle specifiche. A volte non rilascerà assegni. Per esempio, giallo, uno degli aspetti della pset 4, è una specie di deludente se vi diamo la risposta riguardo a quello che è, e c'è un certo numero di modi per rivelare che la persona è in quel rumore rosso. Le specifiche sempre specificare in futuro per pset 5 in poi quali controlli esistono per voi. Noterete c'è questo URL bianco nella parte inferiore. Per ora, si tratta solo di uscita di diagnostica. Se si visita l'URL, si otterrà un sacco di pazzi, messaggi criptici che hai la possibilità di guardare attraverso, ma è soprattutto per il personale in modo da poter diagnosticare e correggere bug in check50 sé. 

Senza indugi, passiamo al punto in cui avevamo lasciato. CS50 biblioteca davamo per scontato per alcune settimane, ma poi la settimana scorsa, abbiamo iniziato sollevando uno degli strati di esso. Abbiamo iniziato mettendo da parte stringa in favore di ciò che, invece? [Gli studenti] Char. Char *, che è stato un char * tutto questo tempo, ma ora non dobbiamo far finta che si tratta di un vero e proprio tipo di dati stringa. Piuttosto, è stato un sinonimo di sorta per char *, e una stringa è una sequenza di caratteri, quindi perché ha senso per rappresentare le stringhe come char * s? Che cosa fa un char * rappresentano nel contesto di questo concetto di una stringa? Si '. >> [Studente] Il primo carattere. Bene, il primo carattere, ma non proprio il primo carattere. Sono i-[Gli studenti] Indirizzo. Bene, l'indirizzo del primo carattere. Tutto ciò che è necessario per rappresentare una stringa nella memoria di un computer è solo l'indirizzo univoco del suo primo byte. Non hanno nemmeno bisogno di sapere quanto tempo ci sia perché come si fa a capirlo in modo dinamico? [Studente] Lunghezza della stringa. È possibile chiamare la lunghezza della stringa, eccellente, ma come si fa il lavoro lunghezza stringa? Che cosa fa? Gia '. [Studente] Continuate fino ad ottenere il carattere null. Sì, esattamente, scorre solo con un ciclo for, while, tutto ciò che da * fino alla fine, e il fine è rappresentato da \ 0, il cosiddetto carattere nul, nul, da non confondere con nulla, che è un puntatore, che entrerà in una conversazione anche oggi. 

Abbiamo sfogliato indietro uno strato di GetInt, e poi abbiamo preso uno sguardo al GetString, e ricordare che entrambe queste funzioni, o realmente, GetString, stava usando una certa funzione per analizzare in realtà, che è, leggere o analizzare l'input dell'utente. E che cosa è che nuova funzione? Scanf e sscanf. Essa è in realtà in una serie di vari gusti. C'è scanf, sscanf c'è, c'è fscanf. Per ora, però, concentriamoci su quello più facilmente illustrato, e lasciami andare avanti e di aprire l'apparecchio in un file come questo, scanf1.c. Questo è un programma super semplice, ma che fa qualcosa che non abbiamo mai fatto senza l'aiuto della biblioteca CS50. Questo diventa un int da un utente. Come funziona? Beh, in linea 16 si, notare che si dichiara una x int chiamato, ed a questo punto della storia, qual è il valore di x? [Risposta degli studenti incomprensibile] [David M.] Giusto, chi lo sa, un certo valore potenzialmente spazzatura, così in 17, abbiamo appena detto che l'utente dammi un numero, per favore, e passo 18 è dove si fa interessante. Scanf sembra prendere in prestito l'idea da printf, in quanto utilizza questi codici di formato tra virgolette. % D è, naturalmente, un numero decimale. Ma perché sto passando e x anziché solo x? Il primo è corretta. Gia '. [Risposta degli studenti incomprensibile] Esattamente, se l'obiettivo di questo programma, come la GetInt funzione stessa, è quello di ottenere un int da parte dell'utente che può passare funzioni tutte le variabili che voglio, ma se non passarli per riferimento o per indirizzo o per puntatore, tutti sinonimi per scopi di oggi, allora che la funzione non è in grado di modificare il contenuto di quella variabile. Ciò sarebbe passato in un solo esemplare, proprio come la versione buggy di swap che abbiamo parlato un paio di volte ora. 

Ma invece, facendo & x, sto letteralmente passare in cosa? [Studente] L'indirizzo. >> L'indirizzo di x. E 'come disegnare una mappa per la funzione di chiamata scanf e dicendo qui, queste sono le indicazioni per un pezzo di memoria del computer che si può andare memorizzare un numero intero trovi Al fine di sscanf fare ora che quale operatore, quale parte di sintassi sta andando ad avere per usare anche se non si vede perché qualcun altro ha scritto questa funzione? In altre parole - che cos'è? [Studente] X leggere. Ci sarà un po 'di lettura, ma solo per quanto riguarda x qui. Se scanf viene passato l'indirizzo di x, sintatticamente, ciò che l'operatore è tenuto ad esistere da qualche parte all'interno di attuazione scanf modo che scanf può effettivamente scrivere un numero da 2 a questo indirizzo? Gia ', in modo che il *. Ricordiamo che il * è il nostro operatore dereference, che significa essenzialmente andare lì. 

Una volta che sei stato consegnato un indirizzo, come è nel caso di specie, scanf è probabilmente, se in realtà abbiamo guardato intorno al suo codice sorgente- sta facendo x * o l'equivalente di andare effettivamente a tale indirizzo e di mettere un po 'il valore lì. Ora, come per come scanf ottiene input dalla tastiera, faremo sventolare le nostre mani per oggi. Basta pensare che il sistema operativo consente di parlare sscanf alla tastiera dell'utente, ma a questo punto ora in linea 19, quando abbiamo semplicemente stampare x, sembra essere il caso scanf che ha messo un int in x. Questo è esattamente come scanf funziona, e richiamare la settimana scorsa che è esattamente come GetString e GetInt e la sua altra famiglia di funzioni lavora in ultima analisi, anche se con leggere variazioni, come sscanf, il che significa che la scansione di una stringa al posto della tastiera. Ma diamo uno sguardo ad una variazione po 'di questo. In scanf2, in realtà ho fatto un casino. Cosa c'è di sbagliato, e io nascondere il commento che spiega come tanto cosa c'è di sbagliato con questo programma, la versione 2? Siate il più tecnico possibile questa volta. Esso sembra piuttosto buono. E 'ben rientrato, ma- Va bene, che ne dici diciamo la potare fino a brevi domande? Linea 16. Cosa c'è di linea 16 facendo in inglese, ma precisa tecnica? Ottenere un po 'imbarazzante. Sì, Michael. [Studente] E 'che punta alla prima lettera di una stringa. 

Va bene, chiudere. Vorrei tweak che un po '. Indicando la prima lettera di una stringa, che si dichiara un buffer variabile chiamata che punterà al primo indirizzo di una stringa, o meglio, che indicherà più specificamente un char. Si noti che non è in realtà che punta da nessuna parte perché non c'è nessun operatore di assegnazione. Non c'è segno di uguale, quindi tutto quello che stiamo facendo è allocare il buffer variabile chiamata. Succede sia a 32 bit, perché si tratta di un puntatore, e il contenuto del buffer presumibilmente eventualmente conterrà un indirizzo di un char, ma per ora, che cosa contiene tampone? Solo un po 'falso, chi lo sa, un po' di spazzatura valore, perché non abbiamo esplicitamente inizializzato, quindi non dobbiamo dare niente per scontato. Bene, ora la linea 17 è, che cosa fa la linea 17 che fare? Forse che scalderà questo. Si stampa una stringa, giusto? Esso stampa String per favore. 

Linea 18 è di tipo familiare ora che abbiamo appena visto una variazione di questo ma con un codice di formato diverso, in modo in linea 18, stiamo raccontando scanf qui è l'indirizzo di un pezzo di memoria. Voglio che tu a suonare in una stringa, come implica% s, ma il problema è che non abbiamo fatto un paio di cose qui. Che uno dei problemi? [Studente] Si sta cercando di risolvere il riferimento di un puntatore nullo. Buono, puntatori nulli o semplicemente altrimenti sconosciuto. Stai consegnando scanf un indirizzo, ma hai detto un momento fa che tale indirizzo è un valore spazzatura, perché in realtà non abbiamo assegnarlo a nulla, e così stai dicendo scanf effettivamente andare inserire una stringa qui, ma non sappiamo dove è ancora qui, quindi non abbiamo fatto memoria allocata per il buffer. Inoltre, ciò che non è nemmeno ancora detto scanf? Supponiamo che si trattava di un pezzo di memoria, e non era un valore di spazzatura, ma non sei ancora scanf dicendo qualcosa di importante. [Studente] Dove è in realtà, la e commerciale. Ampersand, in questo caso, va tutto bene. Perché il buffer è già dichiarato come puntatore con il pezzo * di sintassi, non abbiamo bisogno di usare e commerciale perché è già un indirizzo, ma penso che ho sentito qui. [Studente] Quanto è grande? Bene, non stiamo dicendo scanf quanto è grande questo buffer è, il che significa che anche se fosse un puntatore di buffer, stiamo dicendo scanf, inserire una stringa qui, ma qui potrebbe essere di 2 byte, potrebbe essere di 10 byte, potrebbe essere un megabyte. Scanf non ha idea, e perché questo è un pezzo di memoria presumibilmente, non è ancora una stringa. E 'solo una stringa una volta che scrivere caratteri e un \ 0 a quel pezzo di memoria. Ora è solo un po 'pezzo di memoria. Scanf non si sa quando smettere di scrivere a questo indirizzo. 

Se vi ricordate alcuni esempi in passato, quando ho casualmente digitati sulla tastiera cercando di overflow del buffer, e abbiamo parlato circa il Venerdì esattamente questo. Se un avversario inietta qualche modo nel vostro programma una parola molto più grande o una frase o una frase poi che ti aspettavi è possibile superamento un pezzo di memoria, che può avere conseguenze negative, come la presa in consegna l'intero programma stesso. Abbiamo bisogno di risolvere questo problema in qualche modo. Vorrei diminuire e andare in versione 3 di questo programma. E 'un po' meglio. In questa versione, notare la differenza. Nella riga 16, sto ancora dichiarare un buffer variabile chiamata, ma quello che è ora? Si tratta di una serie di 16 caratteri. Questo è un bene, perché questo significa che posso ora dire scanf qui è un blocco di memoria effettiva. Si può quasi pensare di array come puntatori ora, anche se non sono effettivamente equivalenti. Faranno si comportano diversamente in diversi contesti. Ma è certamente il caso che buffer è riferimento 16 caratteri contigui perché è quello che è un array ed è stato per alcune settimane. 

Ecco, io sto dicendo scanf ecco un pezzo di memoria. Questa volta, in realtà è un pezzo di memoria, ma perché questo programma è ancora sfruttabile? Cosa c'è che non va ancora? Ho detto di darmi 16 byte, ma- [Studente] Che cosa succede se si digita in più di 16? Esattamente, cosa succede se l'utente digita in 17 caratteri o caratteri 1700? In effetti, vediamo se non possiamo inciampare questo errore ora. E 'meglio, ma non è perfetto. Lasciami andare avanti ed eseguire make scanf3 per compilare questo programma. Vorrei correre scanf3, String per favore: ciao, e ci sembra di essere a posto. Fammi provare un po 'più lungo, ciao. Ok, facciamo ciao ci come stai oggi, Invio. Come tipo di fortunati qui, diciamo che ci ciao come stai. Dannazione. Ok, quindi siamo stati fortunati. Vediamo se possiamo risolvere il problema. No, non sta andando a farmi copiare. Proviamo di nuovo. Va bene, stand by. Vedremo quanto tempo posso far finta di mettere a fuoco, pur facendo questo. Dannazione. Questo è piuttosto appropriato, in realtà. Ecco fatto. Punto sollevato. 

Questo, imbarazzante sebbene sia anche, è anche una delle fonti di confusione durante la scrittura di programmi che hanno bug perché si manifestano solo una volta in un po 'a volte. La realtà è che, anche se il codice è completamente rotto, potrebbe essere completamente rotto di tanto in tanto perché a volte, in sostanza quello che succede è il sistema operativo alloca una memoria poco più di quanto effettivamente necessario per qualsiasi motivo, e in modo che nessun altro sta usando la memoria subito dopo il tuo pezzo di 16 caratteri, quindi se si va a 17, 18, 19, qualunque sia, non è un grande affare. Ora, il computer, anche se non si blocca in quel punto, potrebbe eventualmente utilizzare il numero di byte di 17 o 18 o 19 per qualcosa d'altro, a quel punto i dati che hai messo lì, anche se eccessivamente lungo, sta per arrivare potenzialmente sovrascritto da qualche altra funzione. Non è necessariamente andare a rimanere intatto, ma non necessariamente causa un guasto seg. Ma in questo caso, ho finalmente condizione sufficiente di caratteri che sostanzialmente superato il mio segmento di memoria, e bam, il sistema operativo ha detto: "Mi dispiace, questo non va bene, segmentation fault." 

E vediamo ora se ciò che rimane qui nella mia directory notare che ho questo file qui, core. Si noti che questo è di nuovo chiamato un core dump. E 'fondamentalmente un file che contiene il contenuto della memoria del programma nel punto in cui si è schiantato, e solo per provare un piccolo esempio qui lasciami andare qui ed eseguire gdb su scanf3 e quindi specificare un terzo argomento chiamato core, e notare che se qui elencare il codice, saremo in grado come al solito con gdb di iniziare a camminare con questo programma, e posso correre e appena mi ha colpito, come con il comando passo in gdb- appena mi ha colpito la linea potenzialmente buggy dopo aver digitato una stringa enorme, Sarò in grado di identificare realmente qui. Maggiori informazioni su questo, anche se, nella sezione in termini di core dump e così via in modo che si può effettivamente curiosare all'interno del core dump e vedere in quale linea il programma non è riuscito. Tutte le domande poi su puntatori e sugli indirizzi? Perché oggi, abbiamo intenzione di iniziare a prendere per scontato che queste cose esistono e sappiamo esattamente quello che sono. Sì. 

[Studente] Come mai non ha dovuto mettere una e commerciale vicino alla parte- Bella domanda. Come vengo non deve mettere una e commerciale vicino alla matrice di caratteri, come ho fatto in precedenza con la maggior parte dei nostri esempi? La risposta breve è array sono un po 'speciale. Si può quasi pensare un buffer come effettivamente essere un indirizzo, e si da il caso sia il caso che la notazione parentesi quadra è una comodità in modo che possiamo andare in fascia 0, staffa 1, staffa 2, senza dover utilizzare la notazione *. Questo è un po 'una bugia perché gli array e puntatori sono, infatti, un po 'diverso, ma possono spesso, ma non sempre essere interscambiati. In breve, quando una funzione si aspetta un puntatore a un blocco di memoria, è possibile passare un indirizzo che è stato restituito da malloc, e vedremo malloc di nuovo in breve tempo, oppure è possibile passare il nome di un array. Non hanno a che fare con gli array e commerciale, perché sono già essenzialmente come indirizzi. Questa è l'unica eccezione. Le parentesi quadre li rendono speciali. 

Potrebbe mettere una e commerciale accanto al buffer? Non in questo caso. Questo non avrebbe funzionato perché, ancora una volta, di questo caso angolo dove gli array non sono abbastanza in realtà gli indirizzi. Ma noi forse tornare a che, prima lungo con altri esempi. Proviamo a risolvere un problema qui. Abbiamo una struttura di dati che abbiamo usato per qualche tempo noto come un array. Caso in questione, questo è quello che abbiamo appena avuto. Ma array hanno un po 'di aspetti positivi e negativi. Gli array sono belle perché? Che è una cosa che ti piace, nella misura in cui ti piace array-sugli array? Cosa c'è di comodo su di loro? Cosa c'è di interessante? Perché li introduce in primo luogo? Gia '. [Studente] Si può memorizzare un sacco di dati, e non è necessario utilizzare un 'intera cosa. È possibile utilizzare una sezione. Buono, con una serie è possibile memorizzare una grande quantità di dati, e non si devono necessariamente utilizzare tutto questo, in modo da poter overallocate, che potrebbe essere utile se non si conosce in anticipo quanti di qualcosa da aspettarsi. 

GetString è un esempio perfetto. GetString, scritto da noi, non ha idea di quanti caratteri aspettarsi, quindi il fatto che siamo in grado di allocare blocchi di memoria contigua è buona. Gli array anche risolvere un problema che abbiamo visto un paio di settimane fa, ora dove il codice inizia a devolvere in qualcosa di molto mal progettato. Ricordiamo che ho creato una struttura studente di nome David, e poi che era effettivamente alternativa, però, ad avere un nome di variabile chiamato e un'altra variabile chiamata, credo, casa, e un'altra variabile chiamata ID perché in questa storia ho poi voluto introdurre qualcosa di diverso come Rob nel programma, e allora ho deciso di aspettare un minuto, Ho bisogno di rinominare queste variabili. Chiamiamo mia nome1, ID1, house1. Chiamiamo Rob nome2, house2, ID2. Ma aspetta un attimo, che dire di Tommy? Poi abbiamo avuto tre variabili più. Abbiamo introdotto un altro, quattro serie di variabili. Il mondo ha iniziato a ottenere disordinato molto rapidamente, così abbiamo introdotto le strutture, e ciò che è interessante di una struct? Che cosa fa una struct C ti permette di fare? E 'davvero imbarazzante oggi. Che cosa? >> [Risposta degli studenti incomprensibile] Si ', in particolare, typedef consente di creare un nuovo tipo di dati, e struct, la parola chiave struct, permette di incapsulare pezzi concettualmente legati insieme di dati e, successivamente, li chiamano qualcosa di simile a uno studente. 

E 'andata bene perché ora siamo in grado di modellare specie molto più concettualmente coerente l'idea di uno studente in una variabile piuttosto arbitrariamente avente una per una stringa, una per un ID, e così via. Gli array sono bello perché ci permettono di iniziare a pulire il nostro codice. Ma che cosa è un aspetto negativo ora di un array? Che cosa non può fare? Gia '. [Studente] Dovete sapere quanto è grande. Dovete sapere quanto è grande, quindi è una specie di dolore. Quelli di voi con esperienza di programmazione prima sapere che in un sacco di lingue, come Java, si può chiedere un pezzo di memoria, in particolare una matrice, quanto grande sei, con una lunghezza, di proprietà, per così dire, e questo è davvero comodo. In C, non si può nemmeno chiamare strlen su un array generico perché strlen, come la parola implica, è solo per le stringhe, e si può capire la lunghezza di una stringa, perché di questa convenzione umana di avere un \ 0, ma un array, più genericamente, è solo un pezzo di memoria. Se si tratta di un array di interi, non ci sarà un po 'di carattere speciale alla fine che ti aspetta. Bisogna ricordare la lunghezza di un array. Un altro aspetto negativo di un array rialzato la testa in GetString sé. Che è un altro aspetto negativo di un array? Signore, solo io e te oggi. [Risposta degli studenti incomprensibile] >> E 'quello? E 'dichiarato nello stack. Ok, ha dichiarato in pila. Perché non ti piace? [Studente] Perché viene riutilizzato. Essa viene riutilizzato. Ok, se si utilizza una matrice per allocare la memoria, non si può, per esempio, restituire perché è in pila. Ok, e 'uno svantaggio. E per quanto riguarda un altro con un array? Una volta che lo assegna, sei una specie di vite, se avete bisogno di più spazio di tale matrice ha. 

Poi abbiamo introdotto, richiamo, malloc, che ci ha dato la possibilità di allocare dinamicamente la memoria. Ma cosa succede se abbiamo provato un mondo completamente diverso? E se volessimo risolvere un paio di quei problemi così abbiamo invece-la mia penna si è addormentata qui- cosa succederebbe se invece voluto creare in sostanza un mondo che non è più così? Questo è un array, e, naturalmente, questo tipo di deteriora quando abbiamo raggiunto la fine della matrice, e ora non hanno più spazio per un altro numero intero o un altro carattere. E se preventivamente sorta di dire bene, perché non ci rilassiamo questo requisito che tutti questi pezzi di memoria essere contigua back to back, e perché no, quando ho bisogno di un int o un char, Dammi spazio per uno di essi? E quando ho bisogno di un altro, dammi un altro spazio, e quando ho bisogno di un altro, dammi un altro spazio. Il vantaggio di cui è ora che se qualcun altro prende la memoria qui, niente di che. Prendo questo pezzo supplementare di memoria qui e poi questo. 

Ora, l'unico problema è che questo si sente quasi come se avessi un sacco di diverse variabili. Questo si sente come cinque diverse variabili potenzialmente. Ma cosa succede se rubiamo un'idea da stringhe per cui in qualche modo collegare queste cose insieme concettualmente, e se ho fatto questo? Questa è la mia freccia disegnata molto male. Ma supponiamo che ognuno di questi blocchi di memoria indicò l'altro, e questo ragazzo, che non ha fratelli alla sua destra, non ha tale freccia. Questo è infatti quello che si chiama una lista concatenata. Si tratta di una nuova struttura di dati che ci consente di allocare un blocco di memoria, poi un altro, poi un altro, poi un altro, ogni volta che vogliamo nel corso di un programma, e ricordiamo che sono tutti in qualche modo legati letteralmente concatenamento insieme, e ci siamo riusciti pittoricamente qui con una freccia. Ma in codice, quale sarebbe il meccanismo attraverso il quale si potrebbe in qualche modo,, quasi come Gratta e Vinci, un pezzo ad un altro pezzo? Potremmo usare un puntatore, giusto? Perché in realtà la freccia che sta andando dalla piazza in alto a sinistra, questo ragazzo qui per questo, potrebbe contenere all'interno di questa piazza non solo alcuni interi, non solo alcuni char, ma cosa succede se ho effettivamente assegnate un po 'di spazio in più in modo che ora, ognuno dei miei pezzi di memoria, anche se questo verrà a costare me, ora sembra un po 'più rettangolare in cui uno dei blocchi di memoria viene utilizzato per un numero, come il numero 1, quindi se questo tipo memorizza il numero 2, questo pezzo altra memoria è utilizzata per una freccia, o più concretamente, un puntatore. E supponiamo che io memorizzare il numero 3 qui, mentre Io lo uso per puntare a quel ragazzo, e ora questo ragazzo, supponiamo io voglio solo tre blocchi di memoria tali. Io tracciare una linea attraverso quella, indicando null. Non vi è alcun carattere aggiuntivo. 

In effetti, questo è come si possa fare per l'attuazione una cosa che si chiama una lista concatenata. Una lista concatenata è una nuova struttura di dati, ed è un trampolino di lancio verso strutture di dati molto fantasiosi che cominciano a risolvere i problemi lungo le linee di Facebook problemi di tipo Google e problemi di tipo in cui si dispone di grandi insiemi di dati, e non ha più la taglia per conservare qualsiasi modo contiguo e usare qualcosa come ricerca lineare o anche qualcosa di simile ricerca binaria. Vuoi ancora più tempi di esecuzione. In effetti, uno dei Santo Graal ne parleremo più avanti questa settimana o la prossima è un algoritmo cui tempo di esecuzione è costante. In altre parole, ci vuole sempre la stessa quantità di tempo non importa quanto è grande l'ingresso è, e che sarebbe davvero interessante, anche più di qualcosa logaritmica. Che cosa è questo sullo schermo qui? Ciascuno dei rettangoli è esattamente quello che ho appena disegnato a mano. Ma la cosa fino in fondo a sinistra è una variabile speciale. Sta andando essere un puntatore interno, perché il un dettaglio con una lista concatenata, come queste cose sono chiamati, è che si deve appendere su una fine della lista collegata. 

Proprio come con una stringa, è necessario conoscere l'indirizzo del primo carattere. Stessa cosa per le liste collegate. Devi conoscere l'indirizzo del primo blocco di memoria perché da lì, si può raggiungere ogni altra. Downside. Che prezzo stiamo pagando per questa versatilità di avere un dinamico considerevole struttura di dati che, se mai avremo bisogno di più memoria, fine, solo assegnare una porzione di più e disegnare un puntatore da vecchio al nuovo coda della lista? Gia '. [Studente] Prende spazio di circa il doppio. Prende spazio due volte tanto, quindi è sicuramente un aspetto negativo, e abbiamo visto questo compromesso prima tra tempo e spazio e la flessibilità dove ormai, non abbiamo bisogno di 32 bit per ciascuno di questi numeri. Abbiamo davvero bisogno di 64, 32 per il numero e 32 per il puntatore. Ma hey, io ho 2 gigabyte di RAM. L'aggiunta di un altro 32 bit qui e qui non mi sembra un grosso affare. Ma per grandi insiemi di dati, si aggiunge sicuramente fino a letteralmente il doppio. Che è un altro aspetto negativo ora, o che cosa caratteristica ci rinunciare, se rappresentano liste di cose con una lista concatenata e non un array? [Studente] Non si può attraversare a ritroso. Non si può attraversare a ritroso, quindi sei tipo di vite se siete a piedi da sinistra a destra utilizzando un ciclo for o un ciclo while e poi ti rendi conto, "Oh, io voglio tornare all'inizio della lista." Non è possibile perché questi puntatori solo andare da sinistra a destra, come le frecce indicano. 

Ora, si potrebbe ricordare l'inizio della lista con un'altra variabile, ma questa è una complessità da tenere a mente. Un array, non importa quanto lontano tu vada, si può sempre fare meno, meno, meno, meno e tornate da dove siete venuti. Che è un altro aspetto negativo qui? Gia '. [Domanda studente incomprensibile] Si potrebbe, quindi hai in realtà solo ha proposto una struttura di dati chiamata una lista doppiamente concatenata, e in effetti, si dovrebbe aggiungere un altro puntatore a ciascuno di questi rettangoli che va nella direzione opposta, il lato positivo di cui ora si può attraversare avanti e indietro, il rovescio della medaglia che è ora che si sta utilizzando tre volte la quantità di memoria che abbiamo usato per e anche l'aggiunta di complessità in termini di codice da scrivere per farlo bene. Ma questi sono tutti forse compromessi molto ragionevoli, se l'inversione è più importante. Gia '. [Studente] Inoltre, non è possibile avere una lista collegata 2D. Bene, non si può davvero avere una lista collegata 2D. Si potrebbe. E non è così facile come un array. Come un array, si fa parentesi aperta, parentesi chiusa, parentesi aperta, chiusa parentesi, e si ottiene circa il 2-struttura tridimensionale. Si potrebbe implementare un 2-dimensionale lista concatenata Se si aggiungono, come hai proposto, un terzo puntatore a ciascuna di queste cose, e se ci pensi un altro elenco che vengono voi stile 3D dalla schermata a tutti noi, che è solo un'altra catena di qualche tipo. Potremmo farlo, ma non è semplice come digitare parentesi aperta, parentesi quadra. Gia '. [Domanda studente incomprensibile] Bene, quindi questo è un calciatore vero. 

Questi algoritmi che abbiamo pined oltre, come oh, ricerca binaria, è possibile cercare una matrice di numeri sul tabellone e di una agenda molto più rapidamente se si utilizza divide et impera e un algoritmo di ricerca binaria, ma la ricerca binaria richiede due presupposti. Uno, che i dati sono stati ordinati. Ora, si può presumibilmente mantenere questo ordine, quindi forse non è un problema, ma la ricerca binaria anche assunto che si ha avuto accesso casuale alla lista di numeri, e una serie ti permette di avere accesso casuale, e da accesso casuale, Voglio dire, se si è dato un array, quanto tempo ci metti per arrivare a staffa 0? Una operazione, basta usare [0] e tu sei lì. Quanti passi sono necessari per arrivare alla posizione 10? Un passo, basta andare a [10] e siete arrivati. Al contrario, come si fa a raggiungere il numero intero 10 ° in una lista collegata? Bisogna cominciare dall'inizio, perché si sta solo ricordando l'inizio di una lista collegata, come una stringa viene ricordato con l'indirizzo del suo primo carattere, e di scoprire che int 10 o che 10 ° carattere in una stringa, si deve cercare il tutto dannata. 

Anche in questo caso, non stiamo risolvendo tutti i nostri problemi. Stiamo introducendone di nuovi, ma in realtà dipende da cosa si sta cercando di progettare per. In termini di attuazione del presente, siamo in grado di prendere in prestito l'idea da tale struttura studente. La sintassi è molto simile, solo che adesso, l'idea è un po 'più astratto di casa e il nome e l'ID. Ma io propongo che potremmo avere una struttura di dati in C che si chiama nodo, come l'ultima parola sulla diapositiva suggerisce, all'interno di un nodo, un nodo è solo un contenitore generico in informatica. Di solito è disegnato come un cerchio o un quadrato o un rettangolo, come abbiamo fatto. E in questa struttura dati, abbiamo un int, n, quindi questo è il numero che desidera memorizzare. Ma che cosa è questa seconda linea, struct nodo * prossimo? Perché questo è corretto, o che ruolo ha questo gioco cosa, anche se è un po 'criptico, a prima vista? Gia '. [Risposta degli studenti incomprensibile] Esattamente, quindi il tipo * del bottino che si tratta di un puntatore di qualche tipo. Il nome di questo puntatore è arbitrariamente prossima, ma avremmo potuto chiamato tutto ciò che vogliamo, ma che cosa significa questo punto puntatore? [Studente] Un altro nodo. >> Esattamente, che punti a un altro nodo del genere. 

Ora, questa è una sorta di curiosità di C. Ricordiamo che C è letta da un compilatore cima a fondo, da sinistra a destra, che significa che se, questo è un po 'diverso da quello che abbiamo fatto con lo studente. Quando abbiamo definito uno studente, in realtà non ha messo una parola lì. E 'appena detto typedef. Poi abbiamo avuto int id, string name, string casa, e poi studente al fondo della struttura. Questa dichiarazione è un po 'diverso, perché, ancora una volta, il compilatore C è un po 'stupido. E 'solo andando a leggere dall'alto verso il basso, quindi se non raggiunge il 2 ° riga qui dove accanto è dichiarata e si vede, oh, ecco una variabile chiamata successiva. E 'un puntatore ad una struct nodo. Il compilatore è in procinto di realizzare quello che è un nodo struct? Non ho mai sentito parlare di questa cosa prima, perché il nodo parola non potrebbero altrimenti apparire fino in fondo, per cui vi è questa ridondanza. Dovete dire nodo struct qui, che si può quindi accorciare in seguito grazie a typedef quaggiù, ma questo è perché si fa riferimento alla struttura stessa all'interno della struttura. Questo è il un dettaglio qui. 

Alcuni problemi interessanti stanno per sorgere. Abbiamo una lista di numeri. Come si fa a inserire in esso? Come facciamo a cercare? Come si fa a cancellare da esso? Soprattutto ora che dobbiamo gestire tutti questi puntatori. Hai pensato puntatori erano una specie di mind-bending quando si aveva uno di loro solo cercando di leggere un int ad esso. Ora dobbiamo modificare un valore di un intero elenco. Perché non prendere la nostra pausa di 5 minuti qui, e poi porteremo alcune persone sul palco a fare esattamente questo. 

C è molto più divertente quando è recitata. Chi sarebbe letteralmente piacerebbe essere il primo? Va bene, vieni su. Sei il primo. Chi vorrebbe essere 9? Ok, 9. Come circa 9? 17? Una cricca po 'qui. 22 e 26 in quella fila. E poi, come di qualcuno laggiù a cui si punta. Lei è 34. Ok, 34 anni, vieni su. In primo luogo è laggiù. Va bene, tutti e quattro di voi. E chi abbiamo detto per il 9? Chi è il nostro 9? Chi vuole davvero essere 9? Va bene, andiamo, è 9. Ci siamo. 34, ci vediamo là. La prima parte è farvi apparire come tale. 26, 22, 17, buona. Se si può stare a lato, perché stiamo andando a malloc voi in un attimo. 

Bene, bene. Ok, ottimo, quindi cerchiamo di fare un paio di domande. E in realtà, qual è il tuo nome? >> Anita. Anita, va bene, vieni qui. Anita sta per aiutarci a risolvere uno sorta di domanda abbastanza semplice in primo luogo, che è come si fa a trovare o meno un valore è nella lista? Ora, si noti che in primo luogo, qui rappresentata da Lucas, è un po 'diverso, e così il suo pezzo di carta è volutamente lateralmente perché non è molto alto e non occupa come numero di bit, anche se tecnicamente ha lo stesso formato di carta appena ruotato. Ma è un po 'diverso, nel senso che è solo 32 bit per un puntatore, e tutti questi ragazzi sono 64 bit, di cui la metà è il numero, la metà dei quali è un puntatore. Ma il puntatore non è rappresentato, quindi, se voi ragazzi potrebbe un po 'goffamente usare la mano sinistra per indicare la persona accanto a voi. E tu sei il numero 34. Qual è il tuo nome? Ari. Ari, quindi in realtà, tenere il foglio con la mano destra e la mano sinistra va verso il basso. Voi rappresentate nullo a sinistra. 

Ora la nostra immagine umana è molto coerente. Questo è in realtà il modo puntatori funzionano. E se si può scrunch un po 'in questo modo, quindi non sono nel vostro cammino. Anita qui, a trovare il numero 22, ma assume un vincolo di non umani sollevando pezzi di carta, ma questa è una lista, e hai solo Lucas per cominciare perché è letteralmente il primo puntatore. Supponiamo che tu stesso sei un puntatore, e quindi anche voi avete la possibilità di puntare a qualcosa. Perché non iniziare indicando esattamente ciò che Lucas sta puntando? Bene, e fatemi mettere in atto questo fuori qui. Solo per il bene della discussione, vorrei tirare su una pagina vuota qui. Come si scrive il tuo nome? >> Anita. Ok, Anita. Diciamo nodo * anita = lucas. Beh, non vi chiama Lucas. Dovremmo chiamare prima. Perché questo è, infatti, coerente con la realtà qui? Uno, in primo luogo esiste già. In primo luogo è stato assegnato presumibilmente da qualche parte qui. Nodo * primo, ed è stato assegnato un elenco in qualche modo. Non so come sia successo. Questo è accaduto prima della lezione iniziata. Questo elenco collegato di esseri umani è stato creato. E ora a questo punto della storia, tutto questo è in corso su Facebook a quanto pare in seguito- a questo punto della storia, Anita è stato inizializzato per essere uguale al primo, il che non significa che i punti di Anita a Lucas. Piuttosto, essa indica a che cosa egli fa a perché lo stesso indirizzo che è dentro di Lucas 32 bit - 1, 2, 3 - ora è anche dentro di Anita 32 bit - 1, 2, 3. 

Ora trova 22. Come si va a fare questo? Che cosa? >> Punto a qualsiasi altra cosa. Puntare su qualunque cosa, in modo da andare avanti e agire fuori nel miglior modo possibile qui. Bene, bene, e ora si sta puntando a-come ti chiami con il 22? Ramon. >> Ramon, in modo da Ramon sta tenendo 22. Questo punto è stato fatto un controllo. Ha Ramon == 22, e in tal caso, per esempio, siamo in grado di restituire true. Fammi-mentre questi ragazzi sono qui un po 'goffamente- vorrei fare qualcosa in fretta come bool trovare. Ho intenzione di andare avanti e dire (nodo * lista, int n). Io torno subito con voi ragazzi. Non mi resta che scrivere del codice. E adesso ho intenzione di andare avanti e fare questo, nodo * anita list =. E ho intenzione di andare avanti e dire che mentre (anita! = NULL). 

La metafora qui è sempre un po 'teso, ma mentre (anita! = NULL), che cosa voglio fare? Ho bisogno di un modo di fare riferimento il numero intero che Anita è puntato verso. In passato, quando abbiamo avuto strutture, che è un nodo, abbiamo usato la notazione del punto, e vorremmo dire qualcosa come anita.n, ma il problema è che Anita non è una struttura di per sé. Che cosa è? E 'un puntatore, in modo davvero, se vogliamo usare questa notazione dot- e questo è andare a guardare deliberatamente un po 'criptico- dobbiamo fare una cosa del genere vai a mano sinistra ciò che Anita sia puntato verso e quindi ottenere il campo denominato n. Anita è un puntatore, ma ciò che è * anita? Cosa si fa a trovare quando si va a ciò che Anita è puntato verso? Una struttura, un nodo, e un, richiamo nodo, ha un campo denominato n perché è, ricordo, questi 2 campi, accanto e n, che abbiamo visto un momento fa, proprio qui. 

Per effettivamente imitare questo nel codice, abbiamo potuto fare questo e dire se ((* anita). n == n), la n che sto cercando. Si noti che la funzione è stato passato il numero che mi interessa. Allora posso andare avanti e fare qualcosa di simile return true. Altrimenti, se non è questo il caso, che cosa voglio fare? Come faccio a tradurre in codice quello che Anita ha fatto intuitivamente a piedi attraverso la lista? Cosa devo fare qui per simulare Anita prendendo questo passo a sinistra, che passo a sinistra? [Risposta degli studenti incomprensibile] >> Che cos'è? [Risposta degli studenti incomprensibile] Bene, non è una cattiva idea, ma in passato, quando abbiamo fatto questo, abbiamo fatto anita + + perché questo avrebbe aggiunto il numero 1 ad Anita, che in genere puntare la persona accanto, come Ramon, o la persona accanto a lui, o la persona accanto a lui su tutta la linea. Ma non è abbastanza buono qui, perché che cosa significa questa cosa simile in memoria? Non che. Dobbiamo disabilitare questa. Sembra che questo in memoria, e anche se ho disegnato 1 e 2 e 3 vicini l'uno all'altro, se davvero simulare voi questo-can ragazzi, pur indicando le stesse persone, alcuni di voi può fare un passo indietro a caso, alcuni di voi un passo in avanti a caso? 

Questo pasticcio è ancora una lista concatenata, ma questi ragazzi potrebbe essere ovunque in memoria, così anita + + non è andare a lavorare perché? Cosa è in posizione anita + +? Chi lo sa. E 'un altro valore che così succede di essere interposto tra tutti questi nodi per caso, perché non stiamo utilizzando una matrice. Abbiamo assegnato ciascuno di questi nodi singolarmente. Okay, se voi ragazzi può purificatevi backup. Vorrei proporre che invece di Anita + +, noi invece non si anita- Beh, perche 'non andiamo a qualsiasi Anita è puntato verso e poi fare. dopo? In altre parole, si va a Ramon, che ha in mano il numero 22, e poi. successivo è come se Anita sarebbe la copia del puntatore mano sinistra. Ma non sarebbe andata più lontano di Ramon perché abbiamo trovato 22. Ma sarebbe l'idea. Ora, questo è un dio terribile pasticcio. Onestamente, nessuno potrà mai ricordare questa sintassi, e così per fortuna, in realtà è un po 'deliberata-oh, non hai realmente vedere ciò che ho scritto. Questo sarebbe più interessante se si potesse. Voila! 

Dietro le quinte, mi è stato risolvere il problema in questo modo. Anita, a fare quel passo verso sinistra, in primo luogo, ci si va a l'indirizzo che Anita sia puntato verso e dove si trova non solo n, che abbiamo appena controllato per amor di confronto, ma si trovano anche successivo - in questo caso, Mano sinistra Ramon che punta al nodo successivo della lista. Ma questo è il dio terribile pasticcio a cui ho fatto riferimento in precedenza, ma si scopre C ci permette di semplificare questo. Invece di scrittura (* anita), possiamo invece solo scrivere anita-> n, ed è la stessa cosa di vista funzionale, ma è molto più intuitivo, ed è molto più coerente con l'immagine che abbiamo di disegno tutto questo tempo usando le frecce. 

Infine, che cosa dobbiamo fare alla fine di questo programma? C'è una riga di codice rimanente. Ritorno cosa? Falso, perché se si ottiene attraverso l'intero ciclo while e Anita è, infatti, null, che significa che sono andati fino alla fine della lista dove stava indicando, come ti chiami? Mano sinistra Ari. >> Ari, che è nullo. Anita ora è nullo, e mi rendo conto che sei solo qui in piedi goffamente in un limbo perché ho intenzione di sconto su un monologo qui, ma ti coinvolgere di nuovo in un attimo. Anita è nulla in quel punto della storia, in modo che il ciclo while termina, e dobbiamo restituire false, perché se ha ottenuto fino al puntatore nullo Ari allora non c'era numero che cercava nella lista. Siamo in grado di pulire questo troppo, ma questa è una implementazione abbastanza buono quindi di una funzione di attraversamento, una funzione per trovare una lista concatenata. E 'ancora ricerca lineare, ma non è così semplice come + + un puntatore o + + una variabile i perché ora non possiamo indovinare in cui ciascuno di questi nodi sono in memoria. Dobbiamo seguire letteralmente la scia di briciole di pane o, più specificamente, puntatori, per ottenere da un nodo all'altro. 

Ora proviamo un altro. Anita, vuoi tornare qui? Perché non andare avanti e assegnare un'altra persona da parte del pubblico? Malloc-qual è il tuo nome? >> Rebecca. Rebecca. Rebecca è stata malloced da parte del pubblico, e lei è ora memorizzare il numero 55. E l'obiettivo è a portata di mano ora Anita da inserire Rebecca alla lista linkata qui al suo posto appropriato. Vieni qui per un istante. Ho fatto qualcosa di simile. Ho fatto * nodo. E tu come ti chiami? Rebecca. >> Rebecca, va bene. Rebecca si malloc (sizeof (nodo)). Proprio come abbiamo assegnato le cose come gli studenti e tutto il resto, in passato, abbiamo bisogno della dimensione del nodo, così ora Rebecca è puntato verso che cosa? Rebecca ha due campi all'interno della sua, di cui uno 55. Facciamo una cosa, rebecca-> = 55. Ma poi rebecca-> successivo deve essere-come in questo momento, la sua mano è una specie di chi lo sa? Si punta a un certo valore spazzatura, quindi perché non fare per buona misura noi almeno fare in modo che la mano sinistra è ora al suo fianco. Ora Anita, prendere da qui. Hai Rebecca quale sono stati assegnati. Vai avanti e trovare dove si dovrebbe mettere Rebecca. Bene, molto bene. Ok, bene, e ora abbiamo bisogno di voi per fornire un po 'di direzione, così hai raggiunto Ari. La sua mano sinistra è nullo, ma Rebecca appartiene chiaramente a destra, così come dobbiamo modificare tale lista concatenata al fine di inserire Rebecca nella posizione più opportuna? Se si potesse letteralmente spostare mano sinistra della gente intorno, se necessario, dovremo risolvere il problema in questo modo. Ok, bene, e nel frattempo, la mano sinistra di Rebecca è ora al suo fianco. 

E 'stato troppo facile. Proviamo ripartizione: siamo quasi finito, 20. Va bene, vieni su. 20 è stato assegnato, per cui vorrei andare avanti e ripeto qui che abbiamo appena fatto * Saad nodo. Abbiamo malloc (sizeof (nodo)). Abbiamo poi fare la stessa sintassi esatta come abbiamo fatto prima per 20, e farò del prossimo = NULL, e ora tocca a Anita da inserire nella lista è collegata, se si potesse svolgere tale ruolo esattamente lo stesso. Eseguire. Ok, bene. Ora riflettere attentamente prima di iniziare a muoversi mano sinistra intorno. È di gran lunga ottenuto il ruolo più scomodo di oggi. Di chi la mano deve essere mosso per primo? Ok, aspetta, mi sento un po 'non è. Se alcune persone si educatamente piacerebbe aiutare a risolvere una situazione imbarazzante qui. Di chi la mano sinistra dovrebbe prima essere aggiornato forse? Gia '. [Studente] Saad. Ok, Saad, perché, anche se? [Risposta degli studenti incomprensibile] Bene, perché se ci muoviamo-come ti chiami? >> Marshall. Marshall, se spostiamo la prima mano fino a null, ora abbiamo letteralmente orfani quattro persone in questa lista perché era l'unica cosa che punta a Ramon e tutti a sinistra, in modo che l'aggiornamento primo puntatore era male. Facciamo che annulla. Bene, e ora andare avanti e spostare la mano sinistra del caso punta a Ramon. Questo si sente un po 'ridondante. Ora ci sono due persone che puntano a Ramon, ma va bene perché ora come altro possiamo aggiornare la lista? Che d'altra parte si deve muovere? Ottimo, ora abbiamo perso ogni memoria? No, tutto bene, vediamo se non possiamo rompere questo ancora una volta. 

Mallocing per l'ultima volta, il numero 5. Per tutto il tragitto sul retro, vieni giù. E 'molto eccitante. [Applausi] Qual è il tuo nome? >> Ron. Ron, va bene, si malloced con il numero 5. Abbiamo appena eseguito il codice che è quasi identico a questi solo con un nome diverso. Eccellente. Ora, Anita, buona fortuna inserendo il numero 5 nella lista ora. Buono, e? Eccellente, quindi questo è davvero il terzo dei tre casi totali. In primo luogo abbiamo avuto qualcuno, alla fine, Rebecca. Abbiamo poi avuto qualcuno in mezzo. Ora abbiamo qualcuno all'inizio, e in questo esempio, Ora abbiamo dovuto aggiornare Lucas per la prima volta poiché il primo elemento della lista deve ora puntare a un nuovo nodo, che, a sua volta, è indicando numero nodo 9. 

Questa è stata una dimostrazione estremamente imbarazzante, ne sono sicuro, quindi un grande applauso per questi ragazzi se potessi. Ben fatto. Questo è tutto. È possibile mantenere i vostri pezzi di carta come una poca memoria. Si scopre che facendo questo nel codice non è così semplice come solo muovendo le mani intorno e indicando puntatori a cose diverse. Ma si rendono conto che quando arriva il momento di implementare qualcosa di simile una lista collegata o una variante di esso, se ci si concentra sul proprio questi fondamenti di base, i bite-size problemi che devo capire, è questa mano e questa mano, si rende conto che ciò che è altrimenti un programma piuttosto complesso può, infatti, essere ridotto a blocchi piuttosto semplici come questo. 

Prendiamo le cose in una direzione ancora più sofisticato. Ora abbiamo l'idea della lista collegata. Abbiamo anche-grazie al suggerimento là dietro, una lista doppiamente concatenata, che sembra quasi lo stesso, ma ora abbiamo due puntatori all'interno della struttura invece di uno, e probabilmente potrebbe chiamare quei puntatori precedente e successivo o sinistra o destra, ma noi, in effetti, hanno bisogno di due di loro. Il codice dovrebbe essere un po 'più coinvolti. Anita avrebbe dovuto fare di più lavoro qui sul palco. Ma potremmo certamente implementare quel tipo di struttura. In termini di tempo di esecuzione, però, quale sarebbe il tempo di esecuzione per Anita di trovare un numero n in una lista concatenata ora? Ancora grande O di n, quindi non c'è meglio di ricerca lineare. Non possiamo fare ricerca binaria, però, ancora una volta. Perché è così? Non si può saltare. Anche se, ovviamente, vedere tutti gli esseri umani sul palco, e Anita avrebbe potuto eyeballed e disse: "Ecco la metà della lista," lei non avrebbe saputo che se fosse il programma per computer perché l'unica cosa che doveva attaccarsi a all'inizio dello scenario era Lucas, che è stato il primo puntatore. Avrebbe necessariamente seguire quei link, contando la sua strada fino a trovare circa la metà, e anche allora, lei non ha intenzione di sapere quando è raggiunto il centro a meno che lei va tutta la strada fino alla fine per capire quanti ce ne sono, poi fa marcia indietro, e anche questo sarebbe stato difficile se non si ha avuto una lista doppiamente concatenata di qualche tipo. 

Risolvere alcuni problemi di oggi, ma l'introduzione di altri. Che dire di una struttura di dati del tutto diverso? Questa è una fotografia dei vassoi in Mather House, e in questo caso, abbiamo una struttura dati che abbiamo anche un po 'già parlato. Abbiamo parlato di una pila nel contesto della memoria, e che è una sorta di volutamente chiamato perché una pila in termini di memoria è effettivamente una struttura di dati che ha sempre più cose stratificato sopra di esso. Ma la cosa interessante di una pila, come avviene nella realtà, è che si tratta di un particolare tipo di struttura dati. È una struttura di dati in cui il primo elemento è l'ultimo elemento fuori. Se sei il primo cassetto di essere messa in pila, si sta andando ad essere, purtroppo, l'ultimo cassetto da prendere dallo stack, e che non è necessariamente una buona cosa. Al contrario, si può pensare che il contrario, l'ultimo è il primo a scendere. 

Ora, tutti gli scenari vengono in mente dove avere uno stack struttura dei dati in cui si dispone che la proprietà del last in, first out, in realtà è convincente? E 'una buona cosa? E 'una brutta cosa? E 'sicuramente una cosa negativa se i vassoi non sono tutti uguali ed erano tutti i colori speciali diversi o quant'altro, e il colore che vuoi sarà tutta la strada in basso. Naturalmente, non si può ottenere che, senza grande sforzo. Si deve cominciare dalla parte superiore e il tuo lavoro verso il basso. Allo stesso modo, e se tu fossi uno di questi ragazzi fan che aspetta tutta la notte cercando di ottenere un iPhone e le linee in un posto come questo? Non sarebbe bello se la Apple Store erano una struttura dati pila? Yay? No? E 'solo un bene per le persone che si presentano all'ultimo minuto possibile e poi si strappavano la coda. E in effetti, il fatto che ero così propenso a dire coda in realtà è in linea con quello che potremmo chiamare questo tipo di struttura dati, uno in realtà, in cui l'ordine non importa, e si desidera che il primo per essere il primo fuori se non altro per ragioni di equità umana. Ci si chiede anche che una struttura dati coda. 

Si scopre inoltre liste concatenate, siamo in grado di iniziare a utilizzare le stesse idee di base e iniziare a creare nuovi e differenti tipi di soluzioni ai problemi. Per esempio, nel caso di una pila, possiamo rappresentare una pila utilizzando una struttura dati come questo, vorrei proporre. In questo caso, ho dichiarato una struct, e ho detto all'interno di questa struttura è una matrice di numeri e una dimensione variabile chiamata, e ho intenzione di chiamare questa cosa una pila. Ora, perché questo in realtà il lavoro? Nel caso di una pila, ho potuto disegnare questo efficacemente sullo schermo come un array. Ecco il mio stack. Questi sono i miei numeri. E noi li disegnare come questo, questo, questo, questo, questo. E poi ho qualche altro membro dati qui, che si chiama dimensioni, quindi questo è dimensioni, e questo è numeri, e collettivamente, l'iPad tutto qui rappresenta una struttura multistrato. Ora, per impostazione predefinita, la dimensione ha probabilmente avuto modo di essere inizializzato a 0, e ciò che è all'interno della matrice di numeri inizialmente quando ho allocare un array? Garbage. Chi lo sa? E in realtà non importa. Non importa se questo è 1, 2, 3, 4, 5, completamente casuale dalla sfortuna memorizzato nella mia struttura perché finché so che la dimensione dello stack è 0, allora so di programmazione, non guardare in qualsiasi degli elementi della matrice. Non importa quello che c'è. Non guardare a loro, come sarebbe l'implicazione di una dimensione di 0. 

Ma supponiamo ora vado avanti e inserire qualcosa nello stack. Voglio inserire il numero 5, così ho messo il numero 5 qui, e poi che cosa ho messo qui? Ora vorrei davvero mettere giù 1 per le dimensioni, e ora la pila è di dimensione 1. Cosa succede se andare avanti e inserire il numero, diciamo, 7 dopo? Questo viene aggiornato a 2, e poi faremo 9, e quindi questa viene aggiornato a 3. Ma la caratteristica interessante ora di questa pila è che Dovrei eliminare quale elemento se voglio pop qualcosa fuori della pila, per così dire? 9 sarebbe la prima cosa da fare. Come dovrebbe cambiare l'immagine se voglio apparire un elemento dallo stack, molto simile a un vassoio in Mather? Si '. >> [Studente] Imposta la dimensione di 2. Esattamente, tutto quello che faccio è impostare il formato a 2, e cosa devo fare con la matrice? Non c'è bisogno di fare nulla. Ho potuto, solo per essere anale, mettere un 0 non ci o -1 o qualcosa del genere per indicare che questo non è un valore legittimo, ma non importa, perché Sono in grado di registrare al di fuori della matrice stessa quanto è lungo in modo che io conosco solo guardare i primi due elementi di questo array. Ora, se vado e aggiungere il numero 8 di questo array, come si cambia l'immagine successiva? Questo diventa 8, e questa diventa 3. Sto tagliando qualche curva qui. Ora abbiamo 5, 7, 8, e siamo tornati a una dimensione di 3. Questo è abbastanza semplice da implementare, ma quando andiamo a rimpiangere questa decisione di progettazione? Quando le cose iniziano ad andare molto, molto sbagliato? Gia '. [Risposta degli studenti incomprensibile] Quando si desidera tornare indietro e ottenere il primo elemento si mette in 

Risulta qui anche se una pila è un array sotto la cappa, queste strutture di dati che abbiamo iniziato a parlare sono anche noto come strutture dati astratte in cui come vengono attuate è completamente oltre il punto. Una struttura dati come una pila dovrebbe aggiungere il supporto operazioni come spinta, che spinge un vassoio nello stack, e pop, che rimuove un elemento dalla pila, e questo è tutto. Se si dovesse scaricare codice di qualcun altro che ha già messo in atto questa cosa chiamata una pila, quella persona avrebbe scritto solo due funzioni per voi, push e pop, il cui unico scopo nella vita potrebbe essere quella di fare esattamente questo. Tu o lui o lei che ha implementato il programma sarebbe stato del tutto a decidere come implementare la semantica di spinta e spuntando sotto la cappa o la funzionalità di spinta e popping. E ho preso una decisione un po 'miope qui attuando il mio stack con questa struttura di dati semplice perché? Quando questa struttura dati pausa? A che punto devo restituire un errore quando l'utente chiama il metodo push, per esempio? [Studente] Se non c'è più spazio. Esatto, se non c'è più spazio disponibile, se ho superato la capacità, che tutti i tappi perché suggerisce che si tratta di una specie di costante globale. Beh, allora sto solo andando a dire: "Mi dispiace, non può spingere un altro valore nello stack ", molto simile a Mather. 

Ad un certo punto, che stanno andando a colpire la parte superiore di questo stanzino piccolo. Non c'è più spazio o di capacità della pila, a quel punto ci sia qualche tipo di errore. Devono mettere l'elemento da qualche altra parte, il vassoio da qualche altra parte, o da nessuna parte. Ora, con una coda, potremmo implementare un po 'diverso. Una coda è un po 'diverso dal fatto che sotto la cappa, può essere implementato come un array, ma perché, in questo caso, sto proponendo avere anche un elemento di testa che rappresenta la testa della lista, la parte anteriore della lista, la prima persona in fila al negozio di Apple, oltre alle dimensioni? Perché ho bisogno di un pezzo aggiuntivo di dati qui? Pensate a quali numeri è se ho disegnato come segue. Supponiamo che questo è ora una coda invece di una pila, con la differenza, proprio come l'Apple Store-coda è giusto. Il primo in linea all'inizio della lista, numero 5 in questo caso, lui o lei ha intenzione di lasciare in essere il primo negozio. Facciamolo. Supponiamo che questo è lo stato della mia coda in questo momento nel tempo, e ora il negozio Apple si apre e la prima persona, numero 5, è condotto in negozio. Come faccio a cambiare l'immagine, ora che ho de-coda la prima persona nella parte anteriore della linea? Che cosa? >> [Studente] Cambiare la coda. Cambiare la testa, quindi 5 scompare. In realtà, è come se, il modo migliore per fare questo? In realtà, è come se questo ragazzo scompare. Cosa fare numero 7 in un negozio reale? Avrebbero fare un grande passo in avanti. 

Ma che cosa abbiamo imparato ad apprezzare quando si tratta di array e spostare le cose? E 'una sorta di perdita di tempo, giusto? Perché devi essere così anale da avere la prima persona all'inizio della linea fisicamente all'inizio del blocco di memoria? E 'completamente inutile. Perché? Che cosa potrebbe Ricordo solo, invece? >> [Risposta degli studenti incomprensibile] Esattamente, ho potuto solo ricordare con questo ulteriore elemento di testa dati che ora la testa della lista non è più 0, che è stato un momento fa. Ora, in realtà è il numero 1. In questo modo, ho una leggera ottimizzazione. Solo perché ho de-coda qualcuno dalla linea all'inizio della linea presso l'Apple Store non significa che tutti devono passare, che il richiamo è un'operazione lineare. Posso invece passare il tempo costante solo e ottenere quindi una risposta molto più veloce. Ma il prezzo che sto pagando è quello di ottenere che le prestazioni aggiuntive e non dover spostare tutti? Si '. >> [Risposta degli studenti incomprensibile] È possibile aggiungere altre persone, beh, il problema è ortogonale al fatto che non stiamo spostando la gente intorno. E 'ancora un array, quindi se non ci spostiamo tutti, o no- Oh, capisco cosa vuoi dire, va bene. A dire il vero, sono d'accordo con quello che dici nel senso che è quasi come se stiamo mai ora intenzione di utilizzare l'inizio di questa matrice più perché se tolgo 5, poi tolgo 7. Ma ho solo mettere le persone a destra. 

Ci si sente come sto sprecando spazio, e alla fine la mia coda si disintegra nel nulla del tutto, così abbiamo potuto solo avvolgente persone, e si potrebbe pensare di questa matrice veramente come una sorta di struttura circolare, ma usiamo quello operatore in C per fare questo genere di avvolgente? [Risposta degli studenti incomprensibile] >> L'operatore modulo. Sarebbe un po 'fastidioso per pensare a come si fa a fare il avvolgente, ma potremmo farlo, e abbiamo potuto iniziare a mettere le persone a quello che era la parte anteriore della linea, ma basta ricordare con questa variabile testa che il vero capo della linea è in realtà. E se, invece, il nostro obiettivo in ultima analisi, però, è stato quello di cercare i numeri, come abbiamo fatto qui sul palco con Anita, ma vogliamo davvero che il migliore di tutti questi mondi? Vogliamo più sofisticato di matrice consente perché vogliamo la capacità di crescere in modo dinamico la struttura di dati. Ma noi non vogliamo ricorrere a qualcosa che abbiamo sottolineato nella prima conferenza non era un algoritmo ottimale, che di ricerca lineare. Risulta che è possibile, infatti, raggiungere o almeno vicino a costante di tempo, per cui una persona come Anita, se si configura la struttura di dati di non essere una lista concatenata, non essere una pila, di non essere una coda, potrebbe, infatti, venire con una struttura di dati che le permette di guardare le cose, anche le parole, non solo numeri, in ciò che noi chiameremo costante di tempo. 

E infatti, in prospettiva, una delle pset in questa classe è quasi sempre una implementazione di un correttore ortografico, per cui vi diamo ancora una volta alcune parole 150.000 inglesi e l'obiettivo è quello di caricare quelli in memoria e rapidamente essere in grado di rispondere alle domande del modulo questa parola è scritta correttamente? E sarebbe davvero schifo se si dovesse scorrere tutte le 150.000 parole per rispondere a questa. Ma, in realtà, vedremo che si può fare in tempi molto, molto veloce. E sta andando a coinvolgere qualcosa di attuare detta tabella di hash, e anche se a prima vista questa cosa chiamata una tabella hash sta per cerchiamo di raggiungere questi tempi super-rapidi di risposta, risulta che vi è in effetti un problema. Quando arriva il momento di attuare questa cosa chiamata di nuovo, lo sto facendo di nuovo. Io sono l'unico qui. Quando arriva il momento di attuare questa cosa chiamata una tabella hash, stiamo andando a prendere una decisione. Quanto deve essere grande questa cosa in realtà essere? E quando si inizia l'inserimento di numeri in questa tabella di hash, come faremo per memorizzarli in modo che possiamo tornare il più rapidamente li abbiamo ottenuto in? Ma vedremo in breve tempo che la questione di il compleanno di tutti è nella classe sarà abbastanza germano. Si scopre che in questa sala, abbiamo un paio di centinaia di persone, quindi le probabilità che due di noi hanno la stessa data di nascita è probabilmente piuttosto elevato. E se ci fosse solo 40 di noi in questa stanza? Quali sono le probabilità di due persone che hanno lo stesso compleanno? [Gli studenti] Oltre il 50%. Si, oltre il 50%. In effetti, ho portato anche un grafico. Si scopre, e questo è in realtà solo uno sneak preview- se c'è solo il 58 di noi in questa stanza, la probabilità di 2 di noi avente la stessa data di nascita è estremamente elevato, quasi il 100%, e che sta per causare un sacco di dolore per noi il Mercoledì. 

Detto questo, cerchiamo di aggiornare qui. Ci vediamo il Mercoledì. [Applausi] [CS50.TV]