[RIPRODUZIONE DI BRANI MUSICALI] 

[RIPRODUZIONE VIDEO] 

-Sta mentendo. 

-Riguardo cosa? 

-Non lo so. 

-Allora Cosa sappiamo? 

-Che Alle 9:15, Ray Santoya era al bancomat. -Già. Quindi la domanda è, cosa ci faceva alle 9:16? 

-Shooting Il 9 millimetri a qualcosa. Forse ha visto il cecchino. 

-O Stava lavorando con lui. 

Aspetta. Torna uno. 

-Cosa vedi? 

-Portare Il suo volto fino a schermo intero. 

-Il Suo bicchieri. 

-C'è Una riflessione. 

-E 'La squadra di baseball Nuevitas. Questo è il loro logo. 

-E Sta parlando di chi indossa quella giacca. 

[FINE RIPRODUZIONE] 

DAVID MALAN: Va bene. Questo è CS50 e questo è un po 'più di [incomprensibile] con cui sei dilettarsi con il problema di impostare quattro. Oggi iniziamo a guardare un po 'di più profondamente in queste cose chiamate puntatori, che anche se è un argomento piuttosto arcano, si scopre che sta andando di essere il mezzo con cui può iniziare a costruire e assemblare programmi molto più sofisticati. Ma abbiamo fatto il Mercoledì scorso attraverso alcuni claymation primo. Quindi questo, richiamo, è Binky e abbiamo usato lui per dare un'occhiata a un programma che non ha davvero fare qualcosa di interessante, ma ha rivelato alcuni problemi. Quindi, per cominciare oggi, perché non camminiamo rapidamente attraverso alcuni di questi passaggi, provare a distillare in termini di umani esattamente quello che sta succedendo qui e perché questo è un male, e poi passare ed effettivamente iniziare a costruire qualcosa con questa tecnica? Quindi questi sono stati i primi due righe di questo programma e in termini profani, cosa stanno facendo queste due linee? Qualcuno che è abbastanza confortevole con ciò che è dichiarato sullo schermo? Quali sono queste due linee che fanno? Non è tutto ciò che diverso da prima settimana, ma c'è qualche nuovo simbolo speciale. Sì? Là dietro. 

PUBBLICO: Dichiarare puntatori? DAVID MALAN: Dire di nuovo? PUBBLICO: Dichiarare puntatori? DAVID MALAN: puntatori Dichiarare e cerchiamo di affinare un po 'di più. PUBBLICO: [incomprensibile] indirizzo x e poi y. DAVID MALAN: E poi affrontare. Quindi in particolare quello che stiamo facendo è che stiamo dichiarando due variabili. Queste variabili, però, sono in corso essere di tipo int stella, che significa più specificamente stanno andando a memorizzare l'indirizzo di un int, rispettivamente, X e Y. Ora ci sono i valori? Ci sono indirizzi effettivi in ​​questi due variabili in questo momento? No. E 'solo i cosiddetti valori di immondizia. Se in realtà non si assegna un variabile, ciò che era nella RAM in precedenza sta andando a riempire con zeri e quelle due di queste variabili. Ma noi non sappiamo ancora cosa sono e questo è andando ad essere la chiave per il motivo per cui Binky perso la testa la scorsa settimana. 

Quindi questa è stata la claymation incarnazione di questo per cui si hanno solo due variabili, piccoli pezzi circolari di argilla, che può memorizzare variabili, ma come le frecce avvolto suggeriscono, non stanno in realtà punta al noto ovunque per sé. Allora abbiamo avuto questa linea, e questo era nuovo la settimana scorsa, per la memoria malloc assegnazione, che è solo un modo elegante di raccontare il sistema operativo, Linux o Mac OS o Windows, ehi, dammi un po 'di memoria, e tutto quello che hai da raccontare il sistema operativo è quello che quando si chiede che per la memoria. Non sta andando a cura ciò che si sta andando a che fare con esso, ma si ha bisogno di raccontare la operativo Sistema cosa per mezzo di malloc. Sì? 

PUBBLICO: Quanto? DAVID MALAN: Quanto? Quanto in byte, e quindi, questo, di nuovo, un esempio forzato, sta solo dicendo, dammi la dimensione di un int. Ora, la dimensione di un int è quattro byte o 32 bit. Quindi questo è solo un modo di dicendo, hey, il sistema operativo, dammi quattro byte di memoria che posso usare a mia disposizione, e in particolare, ciò fa ritorno malloc rispetto a quel pezzo di quattro byte? PUBBLICO: Indirizzo? DAVID MALAN: L'indirizzo. L'indirizzo di quel pezzo di quattro byte. Esattamente. Ed è quello che è memorizzato in ultima analisi, in x ed è per questo non lo facciamo davvero interessa cosa il numero di tale indirizzo è, che si tratti di OX1 o OX2 o qualche indirizzo esadecimale criptico. Abbiamo appena preoccupiamo pittoricamente che la variabile x è ora punta a quel pezzo di memoria. Così la freccia rappresenta un puntatore oppure più specificamente, un indirizzo di memoria. Ma ancora una volta, non ci importa tipicamente ciò che quegli indirizzi reali sono. Ora, questa linea, dice ciò che in parole povere? Stella x ottiene 42 e virgola. Cosa significa questo? Vuoi andare? Non graffiare il collo. 

PUBBLICO: L'indirizzo di x è al 42. 

DAVID MALAN: L'indirizzo di x è a 42. Non proprio. Così vicino, ma non del tutto, perché c'è la stella che è prefisso questo x. Quindi abbiamo bisogno di modificare un po '. Sì? 

PUBBLICO: Il valore che la puntatore x sta indicando è 42. DAVID MALAN: OK. Il valore che è il puntatore x indicando, diciamo, sono 42, o per dirla in altro modo, la stella x dice, andare a qualunque indirizzo è in x, che si tratti di uno di Oxford Street o 33 Oxford Street o OX1 o OX33, qualunque tale indirizzo numerico è, stella x è la dereferenziazione di x. Quindi, andare a questo indirizzo e poi mettere il numero 42 c'è. Quindi sarebbe un equivalente di dire che. In modo che è tutto bene e poi vorremmo rappresentare l'immagine come segue dove abbiamo aggiunto il 42 di quel pezzo di quattro byte sul lato destro, ma questa linea era dove le cose sono andate male e la testa di Binky spuntato off a questo punto, perché le cose brutte accadono quando si dereference valori della spazzatura oppure si dereference non valida puntatori, e lo dico non valida perché a questo punto nel storia, ciò che è dentro di y? Qual è il valore di y base sugli ultimi passi? Sì? Che cos'è? 

PUBBLICO: Un indirizzo. DAVID MALAN: Un indirizzo. Dovrebbe essere un indirizzo ma ho inizializzato esso? Quindi non ho ancora. Quindi, ciò che è noto per essere lì? E 'solo un certo valore spazzatura. Potrebbe essere qualsiasi indirizzo da zero a 2 miliardi se si hanno due giga di RAM, o zero a 4 miliardi se hai ha ottenuto quattro gigabyte di RAM. E 'certo valore spazzatura, ma il problema è che il sistema operativo, se non è dato che pezzo di memoria specificamente che si sta cercando di andare, è generalmente causerà cosa abbiamo visto come un segmentation fault. Quindi, in realtà, qualcuno di voi che hanno lottato a problemi in orario d'ufficio o problemi che è più generalmente con il tentativo di capire un errore di segmentazione, questo significa che in genere stai toccando un segmento di memoria che non si dovrebbe essere. Stai toccando memoria il sistema operativo non ha vi ha permesso di toccare, che si tratti di andando troppo lontano nella propria matrice o da adesso, se è perché stai toccando memoria che solo è un valore spazzatura. 

Così facendo stella x qui è tipo di comportamento non definito. Non si dovrebbe mai farlo perché le probabilità sono, il programma sta solo andando in crash, perché stai dicendo, vai a questo indirizzo e non avete idea di dove tale indirizzo è in realtà. Quindi il sistema operativo è probabile andare a sbattere il vostro programma come risultato e anzi, che è quello che è successo lì a Binky. Quindi in definitiva, Binky fisso questo problema con questo. In modo che il programma stesso è stato difettoso. Ma se si ordina di andare avanti ed eseguire questa linea, invece, y è uguale x significa semplicemente qualunque indirizzo è un x, messa anche in y. 

E così pittoricamente, abbiamo questo rappresentato con due frecce da x e y da puntamento nello stesso posto. Così semanticamente, x è uguale ay a causa sia di quelli sono la conservazione della stessa indirizzo, ergo che punta a 42, e ora, quando si dice stella y, andare all'indirizzo di y, questo ha un effetto collaterale interessante. Così l'indirizzo in y è il stessa cosa come l'indirizzo di x. Quindi, se si dice andare all'indirizzo in y e modificare il valore di 13, chi altro è interessato? X è, punto D, per così dire, dovrebbero essere colpiti pure. 

E in effetti, come Nick ha disegnato questa immagine in claymation era esattamente questo. Anche se seguiamo il puntatore y, abbiamo finito nello stesso posto, e quindi se dovessimo stampare fuori x o pointee di y, allora vedremmo il valore di 13. Ora, io dico di essere pointee coerente con il video. I programmatori, al mio conoscenza, mai realmente dire la parola pointee, ciò che è appuntita a, ma per coerenza con il video, realizzare questo è tutto quello che era inteso in tale situazione. Quindi tutte le domande su claymation o puntatori o malloc appena ancora? No? Tutto ok. 

Quindi, senza ulteriori indugi, diamo uno sguardo dove questo ha in realtà stato utilizzato per qualche tempo. Così abbiamo avuto questa libreria CS50 che è avuto tutte queste funzioni. Abbiamo utilizzato GetInt molto, GetString, probabilmente GetLongLong precedenza nel mio PSet uno o così, ma cosa sta realmente succedendo? Bene, diamo un rapido sguardo sotto la cappa ad un programma che ispira per questo che vi diamo il CS50 biblioteca, e anzi come della scorsa settimana, abbiamo iniziato a prendere quelli ruote di formazione off. Quindi questo è ora ordinato di un post-mortem di ciò che va avanti all'interno della libreria CS50, anche se ora inizia a muoversi lontano da essa per la maggior parte dei programmi. 

Quindi questo è un programma chiamato scanf 0. E 'super breve. Ha solo queste righe, ma introduce una funzione chiamata scanf che realmente stiamo andando a vedere in un momento all'interno della biblioteca CS50, anche se in una forma leggermente diversa. Quindi questo programma on line 16 è dichiarazione di una variabile x. Quindi dammi quattro byte per un int. E 'stato dice utente, numero di favore, e poi questa è una linea interessante che in realtà lega insieme la scorsa settimana e questo. Scanf, e quindi notare ci vuole un stringa di formato, proprio come printf, % i significa un int, e quindi ci vuole un Il secondo argomento che sembra un po ' funky. E 'commerciale x, e ricordare, abbiamo visto solo una volta la settimana scorsa. Che cosa significa e commerciale x rappresenta? Cosa fa e commerciale fa in C? Sì? 

PUBBLICO: L'indirizzo del. DAVID MALAN: L'indirizzo. Quindi è il contrario dell'operatore stella, mentre l'operatore stella dice, andare a questo indirizzo, l'operatore commerciale dice, capire il indirizzo di questa variabile, e quindi questo è fondamentale, perché scopo di scanf nella vita è quello di eseguire la scansione l'utente del input dalla tastiera, seconda qualunque lui o lei tipi, e poi leggere input dell'utente in una variabile, ma ha visto nelle ultime due settimane che tale funzione di scambio che abbiamo cercato sforzo per implementare è stato appena rotto. Ricordiamo che con la funzione swap, se abbiamo appena dichiarato A e B come interi, abbiamo scambiamo con successo il due variabili all'interno di scambio proprio come con il latte e succo d'arancia, ma non appena tornato scambio, quello che era il risultato con rispetto axey, i valori originali? Niente. Già. Non è successo niente quel tempo, perché swap cambiano solo i suoi copie locali, vale a dire, tutte questa volta, ogni volta che abbiamo stato passando argomenti alle funzioni, siamo solo di passaggio le copie di tali argomenti. Si può fare con quel quello che vuoi con loro, ma che stanno andando a non avere effetto sui valori originali. Quindi questo è problematico se si vogliono avere una funzione come scanf in vita, il cui scopo è quello di eseguire la scansione input dell'utente dalla tastiera e poi riempire gli spazi vuoti, in modo da parlare, cioè, dare una variabile come x un valore, perché se fossi passare solo x a scanf, se si considera la logica dello scorso settimana, scanf può fare quello che vuole con una copia di x, ma non poteva modificare in modo permanente x se non diamo scanf una mappa del tesoro, per così dire, dove x indica il luogo, in cui passiamo l'indirizzo di x in modo che scanf può andare lì e in realtà il cambiamento il valore di x. E così effettivamente, tutte che questo programma fa se faccio scanf 0, a mia fonte Directory 5m, fare scanf 0, dot taglio su scanf, numero si prega di 50, grazie per il 50. 

Quindi non è tutto così interessante, ma quello che sta succedendo davvero è che non appena mi chiamo scanf qui, il valore di x viene cambiato in modo permanente. Ora, questo sembra bello e buona, e infatti, sembra che non abbiamo veramente bisogno la biblioteca CS50 affatto più. Ad esempio, corriamo questo ancora una volta qui. Mi permetta di riaprire per un secondo. Proviamo un numero per favore e invece di dire 50 come prima, diciamo solo che non. OK, questo è un po 'strano. OK. E proprio qualche sciocchezza qui. Quindi non sembra gestire le situazioni sbagliate. Quindi abbiamo bisogno di minimamente inizio l'aggiunta di un po 'di controllo degli errori per assicurarsi che l'utente disponga digitato un numero reale come 50, perché le parole apparentemente di battitura Non viene rilevato come problematico, ma probabilmente dovrebbe essere. 

Diamo un'occhiata a questa versione ora che è il mio tentativo di reimplementare GetString. Se scanf ha tutto questo funzionalità integrato, perché abbiamo stato dilettarsi con questi ruote di formazione come GetString? Bene, qui è forse la mia semplice versione del GetString per cui una settimana fa, avrei potuto dire, dammi una stringa e lo chiamano tampone. Oggi, ho intenzione di iniziare a solo dicendo char stella, che, ricordo, è solo sinonimo. Sembra più paura, ma è la stessa identica cosa. Quindi dammi un buffer variabile chiamata che sta per memorizzare una stringa, dire la stringa user per favore, e poi, proprio come prima, cerchiamo di prendere in prestito questa lezione scanf % s questa volta e quindi passare in tampone. Ora, un controllo di integrità rapido. Perché non mi dicendo ampersand tampone questa volta? Dedurre dall'esempio precedente. PUBBLICO: Char stella è un puntatore. DAVID MALAN: Esattamente, perché questa volta, char stella è già un puntatore, un indirizzo, per definizione, di quella stella essere lì. E se scanf aspetta un indirizzo, è sufficiente solo per passare in tampone. Non ho bisogno di dire di buffer e commerciale. Per i curiosi, si potrebbe fare qualcosa di simile. Avrebbe significato diverso. Questo darebbe un puntatore a un puntatore, che è in realtà una cosa valida in C, ma per ora, teniamolo semplice e mantenere la storia coerente. Sto solo andando a passare in tampone e questo è corretto. Il problema è se questo. Lasciami andare avanti ed eseguire questo programma dopo compilarlo. Fai scanf 1. Dannazione, il mio compilatore di cattura il mio errore. Dammi un secondo. Clang. Diciamo che scanf-1.c. OK. Ci siamo. Ne ho bisogno. ID CS50 ha varie impostazioni di configurazione che si proteggono contro se stessi. Avevo bisogno di disattivare quelle di esecuzione clang manualmente questo momento. Quindi, per favore corda. Ho intenzione di andare avanti e digitare nel mio mondo ciao preferito. OK, null. Non è quello che ho scritto. Quindi è indicativo di qualcosa che è sbagliato. Lasciami andare avanti e digito in una lunghissima corda. Grazie per il nulla e non so se ho intenzione di essere in grado di crash. Proviamo un po 'di copia incolla e vedere se questo aiuta. Basta incollare un sacco di questo. E 'sicuramente un grande stringa del solito. Diciamo solo davvero scrivere. No. Accidenti. Comando non trovato. Ecco, questo è estraneo. Ecco perché ho incollato alcuni personaggi cattivi, ma questo risulta non è andare a lavorare. 

Proviamo questo una volta di più, perché è più divertente se abbiamo effettivamente crash. Proviamo quindi a digitare questo e ora, io sono andando a copiare una lunghissima corda e ora vediamo se siamo può mandare in crash questa cosa. Notate ho omesso spazi e nuove linee e punti e virgola e tutti i personaggi funky. Invio. E ora la rete è solo di essere lento. Ho tenuto giù Comando-V troppo lungo, chiaramente. Accidenti! Comando non trovato. 

OK. Bene, il punto è comunque il seguente. Così che cosa sta realmente accadendo su alla presente dichiarazione di char buffer di stella sulla linea 16? Così Cosa ottengo quando dichiaro un puntatore? Tutto quello che sto ricevendo è un valore quattro byte chiamato buffer, ma quello che c'è dentro di esso al momento? E 'solo un certo valore spazzatura. Perché ogni volta che si dichiara una variabile in C, è solo un po 'di valore spazzatura, e stiamo cominciando a viaggio su questa realtà. Ora, quando dico scanf, vai a questo indirizzo e mettere qualunque l'utente digita. Se l'utente digita ciao mondo, beh, dove lo metto? Buffer è un valore spazzatura. 

Ecco, questo è un po 'come una freccia che sta puntando chissà dove. Forse è rivolto proprio qui nella mia memoria. Così, quando l'utente Tipi di mondo, ciao il programma tenta di mettere il stringa ciao mondo backslash 0 in quel pezzo di memoria. Ma con alta probabilità, ma chiaramente non 100% di probabilità, il computer sta per schiantarsi poi il programma perché questo non è ricordo che dovrebbe essere permesso di toccare. Così, in breve, questo programma è incrinato proprio per questo motivo. Io non sto facendo quello che fondamentalmente? Quali passi sono ho omesso, proprio come abbiamo omesso di primo esempio di Binky? Sì? 

PUBBLICO: Allocazione di memoria? 

DAVID MALAN: allocazione della memoria. Non ho effettivamente allocato qualsiasi memoria per quella stringa. Così siamo in grado di risolvere questo in un paio di modi. Uno, siamo in grado di mantenere le cose semplici e in effetti, ora sei sta per iniziare a vedere una sfocatura delle linee tra ciò che un array è, ciò che una stringa è, ciò che un char stella è, ciò che un array di caratteri è. Ecco un secondo esempio coinvolgendo stringhe e preavviso tutto quello che ho fatto on line 16 è, invece di dire tale buffer sarà un char stella, un puntatore a un pezzo di memoria, Ho intenzione di dare molto in modo proattivo io un buffer per 16 caratteri, e in effetti, se si ha familiarità con il termine buffering, probabilmente dal mondo di video, dove un video è buffering, buffering, buffering. Ebbene, qual è la connessione qui? Beh, Dentro di YouTube e dentro di lettori video generalmente è un array che è più grande di 16 anni. Potrebbe essere un array di dimensione uno megabyte, forse 10 megabyte, e in tale matrice fa il browser scaricare un sacco di byte, un sacco di megabyte di video e il lettore video, YouTube o chiunque sia, inizia leggere i byte da quella matrice, e ogni volta che si vede il parola buffering, buffering, questo significa che il giocatore ha ottenuto al termine di tale matrice. La rete è così lento che non ha riempito l'array con più byte e così sei fuori di bit per visualizzare all'utente. 

Quindi buffer è un termine adatto qui in quella è solo un array, un pezzo di memoria. E questo lo risolverà perché si scopre che è possibile trattare gli array come se sono indirizzi, anche se tampone è solo un simbolo, è un sequenza di caratteri, tampone, che è utile per me, il programmatore, si può passare il suo nome in giro come se si trattasse di un puntatore, come se erano l'indirizzo di un pezzo di memoria per 16 caratteri. Ecco, questo è da dire, posso passare scanf esattamente quella parola e così ora, se faccio questo programma, fare scanf 2, puntino barra scanf 2, e digitare ciao mondo, Invio, che tempo-- 

Hmm, che cosa è successo? Stringa prego. Che cosa ho fatto di sbagliato? Ciao mondo, buffer. Ciao mondo. Ah, io so quello che sta facendo. OK. Quindi è leggendo fino al primo spazio. Quindi cerchiamo di imbrogliare per un attimo e Dico Volevo solo digitare qualcosa molto lungo come questo è una lunga frase questo è uno, due, tre, quattro, cinque, sei, sette, otto, nove, 10, 11, 12, 13, 14, 15, 16. OK. Si tratta infatti di una lunga frase. Così questa frase è più di 16 caratteri e così quando ho colpito Enter, che cosa accadrà? Ebbene, in questo caso del buffer di storia, avevo dichiarato in realtà essere una matrice con 16 caratteri pronto a partire. Quindi uno, due, tre, quattro, cinque, sei, sette, otto, nove, 10, 11, 12, 13, 14, 15, 16. Così 16 personaggi, e ora, quando io letto in qualcosa di simile a questo è un lungo frase, cosa sta andando accadere è che ho intenzione di leggere in questo è una lunga S-E-N-T-E-N-C-E, frase. 

Quindi questo è volutamente una cosa negativa che ho continuare a scrivere al di là del confini della mia matrice, oltre i confini della mia buffer. Potrei avere fortuna e il programma continuerà a correre e non si preoccupano, ma in generale, questo sarà davvero in crash il mio programma, e si tratta di un bug nel mio codificare il momento faccio un passo oltre i confini di tale matrice, perché io Non so se si tratta di necessariamente andare a sbattere o se sto solo andando di avere fortuna. Quindi questo è problematico perché in questo caso, non sembra funzionare e cerchiamo di sfidare il destino qui, anche se l'IDE sembra tollerare un po ' di-- 

Ci siamo. Finalmente. Quindi io sono l'unico che può vedere questo. Così ho avuto un sacco di divertimento battitura fuori una lunghissima frase reale che certamente superato 16 byte, perché io digitato in questo lungo multi-linea pazzo frase, e poi notare ciò che è accaduto. Il programma ha tentato di stamparlo e poi abbiamo preso un segmentation fault e difetti di segmentazione è quando qualcosa di simile accade e il sistema operativo dice no, non si può toccare quel ricordo. Stiamo andando a uccidere il programma del tutto. 

Quindi questo sembra problematico. Ho migliorato il programma per cui almeno avere qualche ricordo, ma questo sembra confinare la funzione GetString per ottenere stringhe di qualche lunghezza finita 16. Quindi, se volete sostenere più a lungo frasi di 16 caratteri, che fai? Beh, è ​​possibile aumentare la dimensioni di questo buffer a 32 o che sembra genere di breve. Perché non solo facciamo essa 1.000 ma spingere indietro. Qual è la risposta intuitivamente di semplicemente evitare questo problema rendendo il mio tampone più grande, come 1.000 caratteri? Con l'implementazione di GetString questo modo. Cosa c'è di buono o cattivo qui? Sì? PUBBLICO: Se si associa un sacco di spazio e non ne fanno uso, allora non si può riallocare lo spazio. DAVID MALAN: Assolutamente. E 'uno spreco, in quanto se non lo fai effettivamente bisogno 900 di quei byte ma stai chiedendo 1.000 in totale in ogni caso, si sta solo consumando più memoria su il computer dell'utente che è necessario, e dopo tutto, alcuni hai già incontrato nella vita che quando sei esecuzione di un sacco di programmi e che stanno divorando grandi quantità di memoria, questo può effettivamente influire sulle prestazioni e l'esperienza dell'utente sul computer. Ecco, questo è una specie di soluzione di pigro, di sicuro, e viceversa, non è solo uno spreco, quale problema rimane ancora, anche se mi metto a tampone 1000? Sì? 

PUBBLICO: La stringa è di lunghezza 1.001. DAVID MALAN: Esattamente. Se la stringa è di lunghezza 1.001, si ha lo stesso identico problema, e il mio argomento, vorrei solo poi ne fanno 2000, ma non si sa in anticipo quanto grande dovrebbe essere, e tuttavia, devo compilare il mio programma prima di lasciare la gente usa e scaricare esso. Quindi questo è esattamente il tipo di roba che i tentativi di libreria CS50 per aiutarci con e faremo solo colpo d'occhio ad alcuni dei implementazione sottostante qui, ma questo è CS50 punto C. Questo è il file che è stato il CS50 IDE tutte queste settimane che hai utilizzato. E 'pre-compilato e hai stati utilizzando automaticamente dalla natura di avere la dash L bandiera CS50 con clangore, ma se ho scorrere verso il basso attraverso tutti queste funzioni, ecco GetString, e solo per darvi un assaggio di quello che sta succedendo, diamo un rapido sguardo a la relativa complessità. Non è un super lunga funzione, ma non l'abbiamo fatto deve pensare tutto dura circa come fare per ottenere stringhe. 

Quindi, ecco il mio buffer e io a quanto pare inizializzarla a null. Questo, naturalmente, è il stessa cosa come char stelle, ma ho deciso di attuazione della biblioteca CS50 che se stiamo andando a essere completamente dinamico, Non so in anticipo come di un grande gli utenti di stringa stanno andando a voler ottenere. Quindi ho intenzione di iniziare a con solo una stringa vuota e ho intenzione di costruire il più memoria, come ho bisogno di adattare la stringa user e se non ho abbastanza, ho intenzione di chiedere il sistema operativo per più memoria. Ho intenzione di spostare la loro corda in un pezzo più grande di memoria e ho intenzione di rilasciare o liberare il sufficientemente grande pezzo di memoria e stiamo solo andando per fare questo in modo iterativo. 

Quindi una rapida occhiata, qui è solo una variabile con cui ho intenzione di tenere traccia della capacità del mio tampone. Il numero di byte posso andare bene? Ecco una variabile n con che ho intenzione di continuare a traccia di quanti byte sono in realtà in il buffer o che l'utente ha digitato. Se non avete visto questo prima, può indicare che una variabile come un int non è firmato, che come suggerisce il nome, significa che è non negativo, e perché avrebbe fatto Ho sempre voglia di preoccuparsi specificando che un int non è solo un int, ma è un unsigned int? Si tratta di un int non negativo. Che cosa significa il [incomprensibile] significa? 

PUBBLICO: Si descrive un importo di memoria che può essere [incomprensibile]. 

DAVID MALAN: Sì. Quindi, se io dico senza segno, questo è in realtà dando un bit di memoria aggiuntiva e sembra sorta di sciocco, ma se si avere un bit di memoria aggiuntiva, che significa avere il doppio I valori si possono rappresentare, perché può essere 0 o 1. Così per impostazione predefinita, un int può essere più o meno negativo 2 miliardi di tutta la strada fino a 2 miliardi di positivo. Questi sono grandi cucine, ma è ancora un po 'uno spreco se vi interessa soltanto dimensioni, che solo intuitivamente dovrebbe essere non negativo o positivo o 0, beh, allora, perché stai sprecando 2 miliardi valori possibili per i numeri negativi se non si è mai intenzione di usarli? Così dicendo non firmato, ora il mio int possibile essere compreso tra 0 e circa 4 miliardi. 

Quindi, ecco solo un int C per motivi noi non entreremo in proprio ora come per questo che è un int invece di un carattere, ma qui è il senso di quello che sta succedendo , e alcuni di voi potrebbe utilizzare, per esempio, la funzione fgetc anche in PSet quattro o successivamente, lo vedremo di nuovo in cinque set problema, fgetc è bello perché, come il nome tipo di, una sorta di arcanamente suggerisce, è una funzione che ottiene un personaggio e così, cosa c'è di fondamentalmente diverso su quello che stiamo facendo in GetString è che non stiamo usando scanf nello stesso modo. Stiamo solo strisciando lungo passo-passo su tutto ciò che l'utente ha digitato, perché possiamo sempre attribuire uno char, e in modo che possiamo sempre tranquillamente guardare uno char alla volta, e la magia comincia ad accadere qui. Io vado a scorrere verso il basso per Al centro di questa funzione solo introdurre brevemente questa funzione. Proprio come c'è un la funzione malloc, c'è una funzione realloc dove realloc consente di riallocare un pezzo di memoria e renderlo più grande o più piccolo. Così lunga storia breve e con un gesto della mano per oggi, sapere che ciò che GetString sta facendo è una specie di magicamente crescita o riducendo il buffer come utente tipi della sua corda. 

Quindi, se l'utente digita una breve stringa, questo codice alloca solamente abbastanza memoria per adattarsi alla stringa. Se l'utente tiene digitazione come ho fatto ancora e ancora e ancora, bene, se la Buffer di questo grande inizialmente e il programma realizza, a aspetta un attimo, sono fuori dello spazio, sta andando a raddoppiare la dimensione del buffer e quindi il doppio della dimensione del buffer e il codice che fa il raddoppio, se guardiamo qui, è solo questo intelligente one-liner. Si potrebbe non aver visto questa sintassi prima, ma se dici stella è uguale, questa è la stessa cosa dicendo volte di capacità 2. Quindi continua a raddoppiare la capacità del buffer e poi dire realloc per dare sé che molto più memoria. 

Ora, come una digressione, ci sono altre funzioni in qui che non vedremo nei dettagli altro che mostrare a GetInt, usiamo GetString in GetInt. Controlliamo che non è null, che, ricordo, è il valore speciale che significa qualcosa è andato storto. Siamo esaurito la memoria. Meglio controllare per questo. E torniamo un valore sentinella. Ma io rimetto ai commenti per quanto riguarda perché e poi usiamo questo cugino di scanf chiamò sscanf e si scopre che scanf sscanf, o una stringa, consente di dare un'occhiata alla linea che l'utente ha digitato e consentono di analizzare essenzialmente e cosa sto facendo qui è che sto dicendo sscanf, analizzare ciò che l'utente ha digitato e assicurarsi% i, vi è un numero intero, e noi non lo farà entrare oggi esattamente il motivo per cui c'è anche un% c qui, ma che in poche parole permette di rilevare se l'utente ha digitato in qualcosa falso dopo il numero. Quindi la ragione che GetInt e GetString dirvi di riprovare, riprovare, riprovare è causa di tutti che codice che abbiamo scritto, è una specie di guardare l'input dell'utente nel fare in modo che sia interamente numerico o si tratta di un vero e proprio galleggiamento valore del punto o simili, a seconda che valore funzione che si sta utilizzando. 

Accidenti. OK. Quello era un boccone ma il punto qui è che il motivo per cui abbiamo avuto quelle ruote di formazione su perché è al livello più basso, ci sono solo tante cose che può andare male che volevamo di gestire preventivamente quelle cose certamente in prime settimane della classe, ma ora con PSet quattro e cinque e PSet là si vede che è più unto voi, ma anche sei più capace di risolvere questo tipo di problemi te stesso. Hai domande su GetString o GetInt? Sì? 

PUBBLICO: Perché si raddoppiare la capacità del buffer piuttosto che solo l'aumento facendo l'importo esatto? 

DAVID MALAN: Bella domanda. Perché dovremmo raddoppiare la capacità del buffer in opposizione ad appena aumentandola da qualche valore costante? E 'stata una decisione di progettazione. Abbiamo appena deciso che in quanto tende a essere un po 'costoso di tempo-saggio di chiedere il sistema operativo per la memoria, non abbiamo vuole finire per ottenere in una situazione per i grandi archi che abbiamo chiesto ripetutamente l'OS e ancora e ancora in rapida successione per la memoria. Così abbiamo semplicemente deciso, un po ' arbitrariamente ma speriamo ragionevolmente, che, si sa che cosa, cerchiamo di cercare di andare avanti di noi stessi e tenere solo il raddoppio in modo che minimizziamo la quantità di volte dobbiamo chiamare malloc o realloc, ma un giudizio totale chiamare in assenza di sapere ciò che gli utenti potrebbero voler digitare. Entrambi i modi possono essere discutibili. Probabilmente buona. 

Quindi, diamo un'occhiata a un paio di altri effetti collaterali di memoria, cose che possono andare male e strumenti che è possibile usare per la cattura di questi tipi di errori. Si scopre tutto di te, anche se check50 non è detto che il più, hanno scritto buggy codice dalla settimana uno, anche se tutti i test sono check50 passò, e anche se tu e il tuo TF sono super sicuri che il tuo codice funziona come previsto. Il tuo codice è stato buggy o viziato in che tutti voi, utilizzando la libreria CS50, sono state perdite di memoria. Sei stato chiedendo il sistema operativo per la memoria nella maggior parte dei programmi che hai scritto, ma hai in realtà mai dato indietro. Hai chiamato GetString e GetInt e getFloat, ma con GetString, hai mai chiamato unGetString o dare Posteriore della stringa o simili, ma abbiamo visto che GetString fa allocare memoria attraverso malloc o questo la funzione realloc, che è solo molto simile nello spirito, e tuttavia, siamo stati chiedendo il sistema operativo memoria e la memoria ripetutamente ma non mollare mai indietro. 

Ora, come una digressione, si scopre che quando un programma viene chiuso, tutta la memoria viene liberato automaticamente. Quindi non è stato un grande affare. Non sta andando a rompere il IDE o rallentare le cose, ma quando i programmi fanno generalmente una perdita di memoria e sono in esecuzione per molto tempo. Se hai mai visto il piccolo stupido pallone da spiaggia in Mac OS o la clessidra su Windows dove è una specie di rallentando o pensare o pensando o semplicemente inizia davvero a rallentare a passo d'uomo, che molto probabilmente potrebbe essere il risultato di una perdita di memoria. I programmatori che hanno scritto il software che si sta utilizzando richiedere al sistema operativo per la memoria ogni pochi minuti, ogni ora. Ma se si sta eseguendo il software, anche se è minimizzato nel vostro computer per ore o giorni e giorni, si potrebbe chiedere di più e di più memoria e mai effettivamente usarlo e così il vostro codice potrebbe essere, o programmi potrebbero essere perdite di memoria, e se si inizia a perdere la memoria, c'è meno memoria per altri programmi, e l'effetto è quello rallenta tutto giù. 

Ora, questo è di gran lunga uno i programmi più atroci avrete opportunità per l'esecuzione in CS50 misura come la sua uscita è ancora più esoterico di clang di effettuare o di o del comando programmi da linea che abbiamo eseguito prima ma per fortuna, all'interno della sua uscita è alcuni suggerimenti utili che super- sarà utile sia per PSet quattro o certamente PConfigurare cinque. Così Valgrind è uno strumento che può essere utilizzato per guardare per perdite di memoria nel programma. E 'relativamente semplice da eseguire. Si esegue valgrind e poi, anche anche se è un po 'prolisso, dash controllo delle perdite dash è uguale a pieno, e poi dot slash il nome del programma. Così valgrind poi eseguire il programma e alla fine del programma esecuzione prima si chiude e ti dà un altro prompt, sta andando ad analizzare il tuo programma mentre è stato in esecuzione e dire hai fatto Hai perdite qualsiasi memoria e meglio ancora, hai toccato memoria non appartengono a voi? Non può catturare tutto, ma è abbastanza bravo a catturare la maggior parte delle cose. 

Quindi, ecco un esempio di mia hanno percorso questo programma, che hanno percorso valgrind, su un programma chiamato la memoria, e ho intenzione per evidenziare le linee che sono in ultima analisi, di interesse per noi. Quindi c'è ancora più distrazioni che ho cancellato dalla diapositiva. Ma facciamo solo vedere cosa questo programma è in grado di dirci. E 'in grado di dirci cose come scrive invalido di dimensioni 4. In altre parole, se si tocca la memoria, in particolare 4 byte di memoria che non si dovrebbero avere, Valgrind posso dire che. Scrittura non valido di dimensioni 4. Hai toccato quattro byte che non si deve avere. Dove l'hai fatto? Questa è la bellezza. Dot memoria c linea 21 è dove si incasinato ed è per questo che è utile. Proprio come GDB, può aiutare si punta a l'errore effettivo. 

Ora, questo è un po 'più verbose, se non confusione. 40 byte in 1 blocchi sono sicuramente perso in perdita record 1 di 1. Che cosa significa? Beh, significa solo che hai chiesto per 40 byte e hai mai dato indietro. Hai chiamato malloc o hai chiamato GetString e il sistema operativo voi 40 byte, ma ti ha dato mai liberato o rilasciato quella memoria, e ad essere onesti, non abbiamo mai mostriamo come dare indietro la memoria. Si scopre che c'è un super semplice funzione chiamata gratuita. Prende un argomento, la cosa si vuole liberare o restituire, ma 40 byte, a quanto pare, in questo programma sono stati persi in linea 20 della memoria dot c. 

Quindi cerchiamo di vedere questo programma. E 'super inutile. Dimostra solo questo particolare errore. Quindi, diamo uno sguardo. Ecco principali e principali, avviso, chiamate una funzione chiamata restituisce fe poi. Quindi non tutto ciò che interessante. Cosa fa f fare? Notate Non ho disturbato con un prototipo. Volevo mantenere il codice come minimo possibile. Così ho messo sopra f principale e va bene, certo, per i programmi brevi come questo. Quindi f non restituisce nulla e fa Non prendere nulla, ma lo fa fare questo. Dichiara, molto simile nell'esempio Binky, un puntatore chiamato x che sta andando per memorizzare l'indirizzo di un int. Ecco, questo è il lato sinistro. In inglese, qual è la lato destro facendo? Chiunque? Che cosa sta facendo questo per noi? Sì? 

PUBBLICO: [incomprensibile] volte la dimensione di un int che è 10 volte che [incomprensibile] DAVID MALAN: Buon e vorrei riassumere. Così allocare spazio sufficiente per 10 numeri interi o 10, qual è la dimensione di un int, è quattro byte, quindi 10 volte 4 è 40, in modo che a destra che ho evidenziata è dammi 40 byte e memorizzare l'indirizzo del primo byte in x. Ed ora, infine, e qui è dove questo programma è bacato, che cosa è sbagliato con la linea 21, basato su questa logica? Cosa c'è di sbagliato con la linea 21? Sì? PUBBLICO: non è possibile indice in x [incomprensibile]. DAVID MALAN: Sì. Non dovrei indice in x del genere. Così sintatticamente, va bene. Il bello è, proprio come si può trattare il nome di un array come se fosse un puntatore, similmente si può trattare di un puntatore come se fosse un array, e quindi posso sintatticamente dire x staffa qualcosa, x staffa i, ma il 10 è problematica. Perché? 

PUBBLICO: Perché non è dentro. 

DAVID MALAN: Non è dentro quel pezzo di memoria. Qual è il valore più grande che dovrebbe essere messa in quelle parentesi quadre? 9, da 0 a 9. A causa dello zero indicizzazione. Così da 0 a 9 andrebbe bene. Staffa 10 non è buono e ma, ricordare però, ogni volta Mi sembra di provare a fare CS50 IDE incidente digitando valori falsi, non sempre collabora, e anzi, spesso fortunato solo perché il sistema operativo non lo fa notare che si sempre leggermente passare qualche pezzo di memoria, perché Sei già entro tecnicamente proprio segmento, ma più su quello in una classe di sistemi operativi, e così qualcosa di simile potrebbe facilmente passare inosservate. Il vostro programma è mai andare a sbattere costantemente ma forse una volta ogni tanto. 

E così proviamo valgrind su questo, ed ecco dove ci arriveremo sopraffatti dall'uscita momentaneamente. Quindi, fare memoria controllo delle perdite valgrind uguale pieno di memoria puntino barra. Ed ecco perché lo prometto questo sarebbe sopraffare. Ecco cosa valgrind, ecco cosa un programmatore, alcuni anni fa- ha deciso che sarebbe una buona idea per l'uscita per assomigliare. Quindi cerchiamo di dare un senso di questo. Quindi tutto il percorso sulla mano sinistra lato per nessuna buona ragione è l'ID di processo del programma abbiamo appena corriamo, l'identificatore univoco per il programma abbiamo appena finito. Abbiamo eliminato che dal la slitta, ma ci alcune informazioni utili qui. 

Facciamo scorrere fino alla cima. Ecco dove abbiamo cominciato. Quindi non è più di tanto l'uscita. Ecco che in scrittura non valida di dimensioni 4 sulla linea 21. Ebbene, qual era la linea 21? Linea 21 era esattamente questo e ha senso che sono in validamente scrivere 4 byte perché io sono cercando di mettere questo intero, che potrebbe essere qualsiasi cosa, succede solo per essere pari a zero, ma sto cercando per dirla in una posizione che non appartiene a me. Inoltre, quaggiù, 40 byte in uno blocchi sono definitivamente persi nel record 1. Questo perché quando chiamo malloc qui, non ho mai realmente liberare la memoria. 

Quindi, come possiamo risolvere questo problema? Lasciami andare avanti ed essere un po 'più sicuro e fare 9 lì e mi lasciare qui gratis x. Questa è la nuova funzione per oggi. Se ora eseguire di nuovo fare puntino memoria barra, corriamo valgrind nuovo su di esso, massimizzare la mia finestra e premere Invio. Ora, va bene. Seppelliscono la buona notizia in tutta questa uscita. Tutti i blocchi heap erano liberi. Torneremo a quello che il cumulo è, ma perdite sono possibili. Quindi questo è solo un altro strumento per il vostro kit di attrezzi con la quale si può iniziare a ora trovare gli errori del genere. 

Ma vediamo cosa più può sbagliare. Diamo ora a transizione effettivamente risolvere un problema. Per inciso, se questo sarà alleviare un po 'di confusione o di tensione, questo è ora divertente. Già. Questo è abbastanza buono. Poiché i puntatori sono indirizzi e indirizzi sono generalmente per convenzione scritto con esadecimale. Ah, ah, questo è divertente ora. Comunque, quindi cerchiamo di ora in realtà risolvere un problema. Questo è stato eccellente, super-basso livello finora, e possiamo effettivamente fare utili le cose con questi dettagli di basso livello. 

Così abbiamo introdotto un paio di settimane fa l'idea di un array. Un array era bello perché è difficile per ripulire il nostro codice perché se volevamo scrivere un programma con più studenti o più nomi e case e dormitori e collegi e tutto questo, abbiamo potuto conservare tutto più pulito all'interno di una matrice. Ma proporre uno svantaggio di un array finora. Anche se non hai sofferto da te in un programma, solo per istinto, ciò che è una brutta cosa su un array, forse? Ho sentito alcuni mormorii. PUBBLICO: E 'difficile per modificare le dimensioni. DAVID MALAN: E 'difficile per modificare le dimensioni. Non è possibile modificare le dimensioni di una matrice, infatti, di per sé in C. È possibile assegnare un altro array, spostare tutto da quello vecchio nel nuovo, e ora avere un po 'di spazio in più, ma non è come un linguaggio come Java o Python o un qualsiasi numero di altri lingue con le quali alcuni di voi potrebbe essere familiare in cui si può solo continuare ad aggiungere le cose nausea alla fine di un array. Quando si dispone di una serie di dimensioni 6, che è la sua dimensione, e così tanto come l'idea precedente avente un buffer di una certa dimensione, dovete indovinare fuori dal cancello che formato voi volete che sia? Se si indovina troppo grande, stai sprecando spazio. Se si indovina troppo piccolo, si non può memorizzare i dati, almeno senza un lavoro molto di più. 

Così oggi, grazie a puntatori, possiamo iniziare a cucire insieme la nostra personalizzato strutture di dati, ed in Infatti, qui è qualcosa che sembra un po 'di più criptico a prima vista, ma questo è ciò che chiameremo un collegato lista, e il suo nome tipo di sintetizza esso. Si tratta di una lista di numeri, o in questo caso, un elenco di numeri, ma potrebbe essere un elenco di nulla, ma è collegato insieme per mezzo di frecce, e basta prendere una supposizione con quale tecnica abbiamo intenzione di essere in grado a cucire insieme, una specie di popcorn con un filo, una legata elenca rettangoli qui? I suoi numeri? Qual è la caratteristica del linguaggio di base? 

PUBBLICO: Un puntatore. 

DAVID MALAN: Un puntatore. Così ognuno di questi rappresenta frecce qui un puntatore o semplicemente un indirizzo. Quindi, in altre parole, se voglio per memorizzare un elenco di numeri, Non posso conservarla se voglio la capacità di crescere e ridursi la mia struttura dati in un array. Così ho bisogno di avere un po ' più raffinatezza, a meno di notare che questo foto tipo di suggerisce che se hai appena avuto piccoli fili collegando tutto insieme, Probabilmente non è così difficile fare spazio tra due di detti rettangoli o due di quei nodi, come inizieremo li chiama, messo in un nuovo nodo, e poi con qualche nuovo thread, solo fosso i tre nodi insieme, il primo, l'ultimo, e quello che appena inserito in mezzo. 

E in effetti una lista collegata, a differenza di una matrice, è dinamico. Si può crescere e può compattare e non fare devono sapere o di assistenza in anticipo come molti dati che si sta andando ad essere l'archiviazione, ma si scopre che dobbiamo essere un po ' attenti a come implementare questa. Quindi, prima prendiamo in considerazione il modo in cui implementiamo uno di questi piccoli rettangoli. E 'facile da implementare un int. Basta dire int n e poi si ottiene 4 byte per un int, ma come faccio a ottenere un int, chiamare n, e poi un puntatore, chiamiamolo prossimo. Potremmo chiamare questi cose tutto ciò che vogliamo ma ho bisogno di una struttura di dati personalizzato. Sì? 

PUBBLICO: Ampersand [incomprensibile]. 

DAVID MALAN: Così commerciale useremo per ottenere l'indirizzo di un nodo potenzialmente. Ma abbiamo bisogno di un altro caratteristica di C al fine per darmi la possibilità di creare questo rettangolo usanza, questa usanza variabile se si vuole, in memoria. PUBBLICO: Un struct. DAVID MALAN: una struct. Richiamo dalla settimana scorsa, abbiamo introdotto struct, questo relativamente semplice parola chiave che ci permette di fare cose come questa. C non è venuto con un data struttura chiamata studente. Viene fornito con int e float e char e tale, ma non sono dotati di studente, ma siamo in grado di creare un tipo di dati degli studenti, una struttura studente, con la seguente sintassi Qui. E vedrete di nuovo e di nuovo. Quindi non preoccuparti memorizzare le parole chiave, ma la parola chiave che è importante è solo il fatto che abbiamo detto struct e poi abbiamo chiamato studente e dentro dello studente era un nome e una casa o un dormitorio o simili. 

E così ora di oggi, cerchiamo di proporre questo. Ho aggiunto qualche parola, ma se voglio di attuare questo rettangolo che è ottenuto sia un int e un puntatore, si sa che cosa, io sono andando a dichiarare una struct chiamato nodo. Sono anche, al suo interno, per dire che un nodo, questo rettangolo, ha un int e che chiameremo n e ha un puntatore successivo. E questo è un po 'prolisso, ma se ci pensate, le frecce che erano nella foto un momento fa sono di che tipo di dati? Dove ognuno di quelle frecce sta indicando a quale tipo di struttura dati? Non è rivolto solo a un int di per sé. Si punta alla tutto rettangolare e che cosa rettangolari, abbiamo detto, è chiamato un nodo. E così abbiamo tipo di dover ricorsivamente definire questo come che un nodo, diremo, conterrà un int chiamato n e un puntatore chiamato successivo e la tipo di struttura dati a cui che i punti di puntatore è apparentemente sta per essere nodo struct. 

Quindi questo è fastidiosamente verbose e solo per essere pedanti, il motivo per cui non possiamo solo dire questo, che francamente sembra molto più leggibile, è perché ricordo che C Lettura cose dall'alto in basso, da sinistra a destra. Non è fino a quando si ottiene il punto e virgola che il nodo parola esiste realmente. Quindi, se vogliamo avere questo tipo di riferimento ciclica interna dei dati struttura, dobbiamo fare questo, dove diciamo struct node in alto, che ci dà un modo più lungo di descrivere questo cosa, poi dentro diciamo nodo struct, e poi l'ultima riga diciamo, va bene, C, tra l'altro, basta chiamare tutta questa maledetta cosa un nodo e fermarsi utilizzando la parola chiave struct del tutto. Quindi questo è solo una sorta di sintattica trucco che permette alla fine a creare qualcosa che appare esattamente come questo. 

Quindi, se assumiamo ora possiamo implementare questa cosa in C, come si fa in realtà iniziare l'attraversamento di questa? Beh, in effetti, tutto quello che dobbiamo fare è scorrere da sinistra a destra e basta tipo di inserire nodi o eliminare i nodi o la ricerca di cose dove vogliamo, ma per fare questo, andiamo avanti e fare le cose un po 'più reale perché questo è stato super-basso livello finora. Chiunque sarebbe letteralmente piace essere il primo? OK. Vieni su. Come ti chiami? 

DAVID: David. DAVID MALAN: David. Felice di conoscerti. Anch'io. Tutto ok. E abbiamo bisogno di un numero 9. Non buono come prima, forse. OK, numero 9. Un numero 17, per favore. Torniamo un po 'più lontano. Numero 22, per favore, e come su più indietro se riesco a vedere tutte le mani con tutta la luce o no. Qualcuno è essere volontariamente proprio lì. Vuoi venire? Il vostro avambraccio viene forzatamente salendo. OK, 17. 22. 26 è venuta giù. Qualcuno altro piacerebbe forcefully-- Vieni su. Un volontario effettivo. 

Quindi molto rapidamente, se voi ragazzi potrebbe organizzare Proprio come voi i nodi sullo schermo. Grazie. E sarete 26. Tutte le introduzioni di destra e veloci. Quindi sono Davide e tu sei anche? DAVID: David. DAVID MALAN: E tu sei? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Eccellente. Quindi questi sono i nostri volontari per oggi e andare avanti e spostare un po 'in questo modo, e solo andare avanti e mantenere tiene i numeri come siete o il vostro primo segno e con la mano sinistra, andare avanti e basta implementare queste frecce, solo in modo che la mano sinistra è letteralmente che punta a qualunque è necessario indicare la a, e datevi qualche camera in modo che possiamo vedere visivamente le braccia in realtà puntamento, e si può solo puntare sorta di a terra va bene. 

Quindi qui abbiamo una lista concatenata di uno, due, tre, quattro, cinque nodi inizialmente, e notare abbiamo questo speciale puntatore all'inizio che è chiave perché dobbiamo tenere traccia di tutta la lista di lunghezza in qualche modo. Questi ragazzi, anche se sono lasciati a destra, back to back in memoria, essi possono effettivamente essere ovunque nella memoria del computer. Così questi ragazzi potrebbero essere piedi ovunque sul palco e va bene, fintanto che sono in realtà indica l'un l'altro, ma per mantenere le cose pulito e semplice, faremo disegnarle semplicemente da sinistra a destra come questo, ma ci potrebbe essere lacune enormi tra questi nodi. 

Ora, se voglio inserire in realtà un po ' il nuovo valore, andiamo avanti e fare questo. Abbiamo un'opportunità ora di scegliere un altro nodo. Dire cominciamo via con mallocing 55. Qualcuno dispiacerebbe essere malloc? OK, andiamo su. Come ti chiami? RAINBOW: Rainbow. DAVID MALAN: Rainbow? Tutto ok. Malloc Arcobaleno. Vieni su. Quindi ora dobbiamo chiederci algoritmicamente dove possiamo mettere 55. Quindi, tutti noi sappiamo, ovviamente, dove probabilmente appartiene se stiamo cercando per mantenere questa risolto e se voi ragazzi poteste prendere una un passo indietro in modo da non cadere fuori il palcoscenico, che sarebbe grande. Quindi, in realtà, Arcobaleno, iniziare qui con me, perché noi, come il computer può ora vedere solo una variabile alla volta. Quindi, se questo è il primo nodo. Notate che non è un nodo, lui è solo un puntatore, ed è per questo che ha disegnato per essere solo la dimensione di un puntatore, non uno di quei rettangoli pieni. Quindi stiamo andando a controllare ad ogni iterazione è 55 inferiore a 9? No. È 55 meno di 17? No. Meno di 22? Meno di 26? Meno di 34? E così ora, ovviamente Arcobaleno appartiene alla fine. Quindi, per essere chiari, e che cosa era il tuo nome, Taylor? 

TAYLOR: Taylor. DAVID MALAN: Quindi fra Taylor la mano sinistra e le mani di Arcobaleno qui, la cui mano ha bisogno di puntare a che cosa Per inserire 55 in questa lista? Che cosa dobbiamo fare? Sì? 

PUBBLICO: La mano di Taylor deve puntare a sinistra. 

DAVID MALAN: Esattamente. Quindi inserendo un nodo nella fine dell'elenco è abbastanza semplice perché basta Taylor deve puntare, anziché alla terra o che chiameremo nullo, null è una sorta di assenza di un puntatore o una speciale puntatore a zero, sei andando a puntare con la sinistra mano a Rainbow e poi Arcobaleno, dove dovrebbe sinistra mano probabilmente puntare? Giù. Non va bene se la sua mano è sorta di puntamento off qui o qualsiasi tipo di quale via. Che potrebbe essere considerato un valore spazzatura, ma se lei indica qualche valore noto, faremo chiamare zero o nullo, va bene perché abbiamo un termine in questo e sappiamo che la lista ora è completo. 

Allora, qual è un altro caso relativamente semplice? Potremmo malloc 5? Vieni su. Come ti chiami? TIFFANY: Tiffany. DAVID MALAN: Mi dispiace? TIFFANY: Tiffany. DAVID MALAN: Tiffany. Tutto ok. Tiffany è stato malloced con il valore 5. Vieni su. Questo è relativamente facile troppo, ma prendiamo in considerazione ordine delle operazioni ora. E 'stato abbastanza facile con Taylor alla fine. Numero 5 è ovviamente inferiore a 9, e quindi abbiamo David, abbiamo Tiffany, e qual era il tuo nome? 

JAKE: Jake. 

DAVID MALAN: Jake. Tiffany, Jake, e David. La cui mano dovrebbe essere aggiornato prima? Cosa vuoi fare qui? C'è un paio di modi possibili, ma c'è anche uno o sensi più sbagliate. 

PUBBLICO: Inizia con più a sinistra. 

DAVID MALAN: Iniziare con il più a sinistra. Chi è il più a sinistra qui, allora? PUBBLICO: Primo. 

DAVID MALAN: OK. Così inizia con la prima e dove si fa desidera aggiornare le mani di David di essere? AUDIENCE: verso il 5. DAVID MALAN: OK. Davide, punto in cinque o Tiffany qui, e ora? 

PUBBLICO: Tiffany punta al 9? DAVID MALAN: Perfetto, tranne Binky di testa solo tipo di caduto, giusto? Perché quello che c'è di sbagliato con questa immagine letteralmente? AUDIENCE: Nulla sta indicando. DAVID MALAN: Niente è indicando Jake ora. Abbiamo letteralmente orfani 9 e 17, e abbiamo letteralmente perdeva di questa memoria, perché da aggiornare la mano di David prima, che è bene nella misura in cui è correttamente che punta a Tiffany ora, ma se nessuno aveva il lungimiranza di puntare a Jake, poi abbiamo perso il totalità di tale elenco. Quindi cerchiamo di annullare. Così che era una buona cosa per inciampare ma cerchiamo di correggere ora. Cosa dobbiamo fare prima, invece? Sì? 

PUBBLICO: Tiffany dovrebbe puntare al 9? DAVID MALAN: non posso ottenere che vicino a voi. Chi dovrebbe puntare al 9? 

PUBBLICO: Tiffany. 

DAVID MALAN: Va bene. Così Tiffany dovrebbe primo punto al 9. Così Tiffany dovrebbe prendere su un valore identico David, che sembra ridondante per un istante, ma va bene perché ora, secondo passo, possiamo aggiornare la mano di David per indicare a Tiffany, e poi se abbiamo solo tipo di pulire le cose come se questo è una specie di primaverile, ora che è un corretto inserimento. Così eccellente. Così ora ci siamo quasi. Inseriamo un finale valore come il valore 20. Se potessimo malloc un volontario finale? Vieni su. Quindi questo è un po 'più complicato. Ma in realtà, il codice siamo la scrittura, anche se verbalmente, è proprio come avere un mucchio se le condizioni di ora, giusto? Abbiamo avuto una condizione controllare se appartiene alla fine, forse l'inizio. Abbiamo bisogno di un qualche tipo di ciclo per trovare il punto nel mezzo. Allora, facciamo che con quello che è il tuo nome? 

Eric: Eric. 

DAVID MALAN: Eric? Eric. Felice di conoscerti. Quindi abbiamo 20. Meno di cinque? No. Meno di nove? No. Meno di 17? No. OK. Egli appartiene qui e i nomi sono di nuovo? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, e? Eric: Eric. DAVID MALAN: Eric. Le cui mani hanno bisogno di ottenere aggiornato prima? 

PUBBLICO: Eric. OK. Così Eric dovrebbero puntare a dove? A 22 anni. Bene. E ora che cosa è il prossimo? Sue può quindi puntare a Eric e ora, se voi ragazzi solo fare spazio, che va bene visivamente, ora abbiamo fatto l'inserimento. Quindi cerchiamo di Consideriamo una domanda ma grazie mille per i nostri volontari. Molto ben fatto. È possibile mantenere quelle, se volete. E abbiamo un bel regalo d'addio se avresti ogni piace prendere una palla antistress. Lasciatemi passare questo giù. Allora, qual è l'asporto di questo? Questo sembra essere sorprendente nella misura in cui abbiamo ora introdotto alternativa a una matrice che non è così limitato a un array di qualche dimensione fissa. Possono crescere in modo dinamico. 

Ma proprio come abbiamo visto in settimane passato, non abbiamo mai ottenere nulla gratis, come sicuramente c'è un trade-off qui. Quindi, con un rialzo di un collegato lista, è questo dinamismo? Questa capacità di crescere e, francamente, avremmo potuto fare di cancellazione e abbiamo potuto ridursi a seconda delle necessità. Quale prezzo stiamo pagando? Doppio dello spazio, prima di tutto. Se guardate la foto, non più sono io Memorizzazione di una lista di numeri interi. Sto memorizzare una lista di interi più puntatori. Così sto raddoppiando la quantità di spazio. Ora, forse non è così un grande affare 4 byte, 8 byte, ma potrebbe certamente aggiungere per grandi insiemi di dati. Che cosa è un altro aspetto negativo? Sì? 

PUBBLICO: Dobbiamo attraversarli uno per uno. DAVID MALAN: Sì. Dobbiamo attraversare loro uno per uno. Sai una cosa, abbiamo rinunciato questo super comoda funzione di parentesi quadra notazione, più propriamente noto come accesso casuale, dove possiamo saltare solo ad un singolo elemento ma ora se avevo ancora i miei volontari qui, se volevo trovare il il numero 22, non posso solo saltare a staffa qualcosa qualcosa. Devo guardare oltre l'elenco, tanto come i nostri esempi Ricerca in modo lineare, per trovare il numero 22. Quindi ci sembra di aver pagato un prezzo lì. Ma possiamo comunque risolvere altri problemi. 

In realtà, mi permetta di introdurre solo un paio di immagini. Quindi, se siete stati fino a Mather Dining Hall di recente, vi ricordate che il loro pile di vassoi come questo, abbiamo preso in prestito da questi Annenberg prima della lezione. Quindi questa pila di vassoi, però, è in realtà rappresentativa di una struttura di dati informatica. Vi è una struttura di dati in informatica noto come uno stack molto ben si presta ad esattamente questo visiva. Quindi, se ciascuno di questi vassoi non è un vassoio ma come un numero e volevo di memorizzare i numeri, io potrebbe mettere uno qui, e ho potuto mettere un altro qui, e continuare numeri accatastamento uno sopra l'altro, e ciò che è potenzialmente utile su questo è che ciò che è l'implicazione di questa struttura dati? Quale numero posso tirare fuori prima il più convenientemente? La più recente una calzata lì. 

Quindi questo è quello che noi chiameremmo in informatica una struttura dati LIFO. Last in, first out. E vedremo fra poco perché che potrebbe essere utile, ma per ora, basta considerare la proprietà. Ed è una specie di stupido se si pensa su come la sala da pranzo lo fa. Ogni volta che i vassoi e puliti mettere quelli freschi sulla parte superiore, si potrebbe avere una precedentemente pulito ma alla fine molto sporca e polverosa vassoio in fondo se non avete mai realmente andare a fondo di tale pila, perché basta continuare a mettere il nuovo e quelle pulite su di esso. La stessa cosa potrebbe accadere in un supermercato troppo. Se si dispone di una vetrina di latte e ogni volta CVS o chi ottiene più latte, basta infilare il latte hai già alla schiena e si mettono i nuovi in ​​attacco, si sta andando ad avere un po 'piuttosto brutta latte alla fine della struttura di dati, perché è sempre in fondo o equivalentemente è sempre sul retro. 

Ma c'è un altro modo di pensare fila di dati e per esempio, questo. Se siete una di quelle persone che ama a schierarsi al di fuori di negozi di Apple quando un nuovo prodotto viene fuori, probabilmente sei non si utilizza una pila di dati struttura perché si sarebbe alienare tutti gli altri che è in fila per l'acquisto di qualche nuovo giocattolo. Piuttosto, probabilmente stai usando che tipo di struttura dati o che tipo di sistema nel mondo reale? Speriamo che sia una linea, o più correttamente o altro britannico-like, una coda. E si scopre una coda è anche un struttura dati in informatica, ma una coda ha una molto proprietà diversa. Non è LIFO. Last in, first out. Dio non voglia. E 'invece FIFO. Il primo che entra è il primo ad uscire. E questa è una buona cosa per l'amor di equità ' certamente quando si sta in fila up molto presto la mattina. Se si arriva prima, è vuole uscire prima pure. 

E così tutti questi dati strutture, code e pile e mazzi di altri, risulta voi può pensare a questo come solo un array. Questo è un array, forse una dimensione fissa a 4, ma che sarebbe essere genere di bello se potessimo solo accumulare vassoi quasi infinitamente alto se avere che molti vassoi o numeri. Così forse vogliamo utilizzare una lista collegata qui, ma il trade-off sarà potenzialmente che abbiamo bisogno di più memoria, prende un po 'di tempo, ma noi non limitano l'altezza della pila, tanto come vetrina di Mather potrebbe limitare la dimensione dello stack, e così si tratta di decisioni di progettazione o opzioni a nostra disposizione definitiva. Quindi, con questi dati strutture, abbiamo iniziato vedere nuovi limiti superiori potenzialmente su quello che in precedenza era super veloce e dove lasceremo via oggi e dove ci auguriamo di arrivare a è il Mercoledì, faremo iniziare a guardare un dato struttura che ci permette di ricercata attraverso i dati in tempo fine del registro di nuovo. E abbiamo visto che, ricordano, in settimana lo zero e uno con ricerca binaria o dividere e conquistare. Sta tornando e meglio ancora, il Santo Graal per questo Mercoledì sarà quello di venire con la struttura di dati che corre veramente o teoricamente in costante di tempo, per cui non importa quanti milioni o miliardi di cose abbiamo nella struttura dati, lo farà Ci vorrà del tempo costante, forse un passo o due passi o 10 passi, ma i numeri costanti passi per la ricerca in tale struttura di dati. Che in effetti sarà il Santo Graal ma più che il Mercoledì. Ci vediamo allora. 

[RIPRODUZIONE DI BRANI MUSICALI]