[Powered by Google Translate] [Settimana 4] [David J. Malan] [Harvard University] [Questo è CS50.] [CS50.TV] Va bene, questo è CS50, e questo è l'inizio di settimana 4, e questo è uno dei possibili algoritmi di ordinamento più lento. Quale è stato che abbiamo appena visto lì? Era bubble sort, in grande ordine O (n ^ 2) + somma, e in effetti non siamo gli unici in questo mondo a sembrare di sapere che tipo bolla è o il suo tempo di esecuzione. In effetti, questo è stato un colloquio con Eric Schmidt di Google e l'ex senatore Barack Obama a pochi anni fa. Ora, Senatore, tu sei qui a Google, e mi piace pensare alla presidenza come un colloquio di lavoro. Ora, è difficile trovare un lavoro come presidente, e si sta andando attraverso i rigori adesso. E 'anche difficile trovare un lavoro presso Google. Abbiamo domande, e chiediamo le nostre domande ai candidati, e questo è da Larry Schwimmer. Voi pensate che stia scherzando? E 'proprio qui. Qual è il modo più efficace per ordinare un milione di interi a 32 bit? [Risate] Well- Mi dispiace. >> No, no, no, no. Credo che il bubble sort sarebbe il modo sbagliato di procedere. Andiamo, chi disse questo? La scorsa settimana richiamare abbiamo preso una pausa dal codice, almeno per un giorno, e ha iniziato a concentrarsi su alcune idee di livello superiore e di problem solving, più in generale nell'ambito della ricerca e l'ordinamento, e abbiamo introdotto qualcosa che non abbiamo uno schiaffo questo nome la settimana scorsa, ma la notazione asintotica, il Big O, l'Omega Big, e talvolta la notazione Big Theta, e questi erano semplicemente modi di descrivere il tempo di esecuzione di algoritmi, quanto tempo ci vuole per un algoritmo per l'esecuzione. E si può ricordare che lei ha parlato il tempo di esecuzione in termini di dimensioni dell'ingresso, che noi generalmente chiamiamo n, qualunque sia il problema potrebbe essere, dove n è il numero di persone in sala, il numero di pagine in una rubrica telefonica, e abbiamo iniziato a scrivere le cose come O (n ^ 2) e O (n) o O (n log n), e anche quando la matematica non ha funzionato in modo perfetto ed era n ² - n / 2 o qualcosa del genere ci sarebbe invece solo buttare via alcuni dei termini di ordine inferiore, e la motivazione è che ci vuole veramente un sorta di passaggio obiettivo di valutare le prestazioni dei programmi o le prestazioni degli algoritmi che alla fine della giornata non ha nulla a che fare, per esempio, con la velocità del vostro computer di oggi. Per esempio, se si implementa bubble sort, o si implementa merge sort sorta o la selezione del computer di oggi, un computer 2 GHz, e lo si esegue, e ci vuole un certo numero di secondi, il prossimo anno c'è un 3 GHz o un 4 GHz del computer, e si potrebbe quindi affermare che "Wow, il mio algoritmo è ora due volte più veloce, "quando in realtà non è questo il caso, ovviamente. E 'solo l'hardware ha ottenuto più veloce, ma il computer non ha, e quindi vogliamo davvero buttare via le cose come multipli di 2 o multipli di 3, quando si tratta di descrivere la velocità o la lentezza è un algoritmo e davvero concentrarsi solo il n o qualche fattore della stessa, qualche potere loro, come nel caso dei tipi di settimana. E ricordare che con l'aiuto di merge sort siamo stati in grado di fare molto meglio di bubble sort e selection sort e anche l'inserimento di ordinamento. Siamo arrivati ​​fino al n log n, e di nuovo, Ricordiamo che log n genere si riferisce a qualcosa che cresce più lentamente n, per cui n log n finora era buona perché era meno di ² n. Ma per raggiungere n log n con merge sort quello che era il germe di un'idea di base che abbiamo dovuto sfruttare che abbiamo anche sfruttato nuovo in settimana 0? Come abbiamo fatto a risolvere il problema di ordinamento sapientemente con merge sort? Qual è stata l'intuizione fondamentale, forse? Chiunque a tutti. Ok, facciamo un passo indietro. Descrivere merge sort con parole tue. Come ha funzionato? Ok, ci remare a 0 alla settimana. Ok, si '. [Incomprensibile-studente] Ok, bene, quindi abbiamo diviso la matrice di numeri in 2 pezzi. Abbiamo risolto ciascuno di questi pezzi, e poi li abbiamo uniti, e abbiamo visto questa idea prima di prendere un problema che è questo grande e tagliare in su in un problema che è questo grande o così grande. Ricordiamo l'esempio rubrica telefonica. Ricordiamo l'auto-conteggio algoritmo settimane fa, ordina quindi unire è stato riassunto da questo pseudocodice qui. Quando si è dato n elementi, in primo luogo è stato controllo di integrità. Se n <2 allora non fare nulla perché se n <2 allora n è ovviamente 0 o 1, e quindi se è 0 o 1 non c'è niente da ordinare. Il gioco è fatto. La lista è già banalmente ordinato. Ma per il resto se hai 2 o più elementi di andare avanti e di dividerli in 2 parti, a destra ea sinistra. Ordina ciascuna di queste parti, e quindi unire le due metà ordinate. Ma il problema è che a prima vista questo sembra che stiamo andare in barca. Questa è una definizione circolare, nel senso che se ti ho chiesto di ordinare questi elementi n e tu mi stai dicendo "Va bene, va bene, ci ordinare tali elementi n / 2 e le n / 2," allora la mia prossima domanda sarà "Bene, come si fa a ordinare la n / 2 elementi?" Ma a causa della struttura di questo programma, perché c'è questo caso base, per così dire, questo caso particolare che dice che se n è un valore fisso > Sara, va bene. Kelly. >> Kelly e? Willy. >> Willy, Sara, Kelly, e Willy. In questo momento mi è stato chiesto da qualcuno la domanda quante persone siano in questa fase, e non ho idea. Si tratta di un elenco molto lungo, e così invece ho intenzione di fare questo trucco. Ho intenzione di chiedere alla persona accanto a me per fare la maggior parte del lavoro, e una volta che si è fatto fare la maggior parte del lavoro Ho intenzione di fare la minor quantità di lavoro possibile e solo aggiungere 1 a tutto ciò che la sua risposta è, quindi ci siamo. Mi è stato chiesto quante persone sono sul palco. Quante persone sono sul palco a fianco di te? La sinistra di me? >> Va bene, ma non barare. Va bene, è vero, ma se vogliamo continuare questa logica supponiamo che si desidera allo stesso punt questo problema a sinistra di te, così invece di rispondere direttamente andare avanti e basta passare la palla. Oh, quante persone sono a sinistra di me? Quante persone sono a sinistra? 1. [Risate] Ok, quindi 0, quindi quello che ora Willy ha fatto è che hai restituito la risposta questa direzione dicendo 0. Ora, cosa si deve fare? >> 1. Ok, quindi tu sei l'uno, in modo da dire: "Va bene, ho intenzione di aggiungere 1 a tutto ciò che conta Willy era, "in modo da 1 + 0. Ora sei 1 in modo la vostra risposta a destra è ora- 1. >> E la mia sarebbe 2. Bene, allora si sta prendendo la risposta precedente di 1, aggiungendo la minima quantità di lavoro che si vuole fare, che è +1. Si dispone ora di 2, e quindi si darmi quale valore? 3, voglio dire, mi dispiace, 2. Buona. Beh, abbiamo avuto da 0 a sinistra. Poi abbiamo avuto uno, e poi aggiungere 2, e ora mi stai consegnando il numero 2, e così dico, va bene, +1, 3. Ci sono infatti 3 persone in piedi accanto a me in questa fase, così abbiamo potuto, ovviamente, fatto questo molto lineare, molto nel modo ovvio, ma cosa abbiamo realmente? Abbiamo preso un problema di dimensione 3 inizialmente. Abbiamo poi si è rotto in un problema di dimensione 2, quindi un problema di dimensione 1, e infine il caso base era davvero, oh, non c'è nessuno, a questo punto Willy restituito efficacemente un hard-coded in un paio di volte, e la seconda è stata poi gorgogliare, gorgogliare, gorgogliare, e poi aggiungendo a questa ulteriore 1 abbiamo implementato questa idea di base della ricorsione. Ora, in questo caso non è davvero risolvere un problema più efficace allora che abbiamo visto finora. Ma pensare a degli algoritmi che abbiamo fatto sul palco finora. Abbiamo avuto 8 pezzi di carta alla lavagna, il video quando Sean cercava il numero 7, e che cosa ha realmente fatto? Beh, non ha fatto alcun tipo di divide et impera. Non ha fatto alcun tipo di ricorsione. Piuttosto ha appena fatto questo algoritmo lineare. Ma quando abbiamo introdotto il concetto di numeri ordinati in scena dal vivo la settimana scorsa poi abbiamo avuto questo istinto di andare verso il centro, a quel punto abbiamo avuto un elenco più ridotto di dimensione 4 o un altro elenco di dimensione 4, e poi abbiamo avuto lo stesso identico problema, quindi abbiamo ripetuto, ripetuto, ripetuto. In altre parole, ci recursed. La ringrazio molto per i nostri 3 volontari qui per dimostrare la ricorsione con noi. Vediamo se possiamo fare questo ora un po 'più concreta, soluzione di un problema che ancora una volta abbiamo potuto fare abbastanza facilmente, ma lo useremo come un trampolino di lancio per l'attuazione del presente idea di base. Se voglio calcolare la somma di una serie di numeri, per esempio, se si passa il numero 3, Io voglio dare il valore di sigma 3, quindi la somma di 3 + 2 + 1 + 0. Voglio tornare la risposta 6, quindi dovremo implementare la funzione di sigma, questa funzione sommatoria che, ancora una volta, prende in ingresso, e quindi restituisce la sommatoria di tale numero fino in fondo a 0. Si potrebbe fare questo piuttosto semplice, no? Potremmo farlo con un qualche tipo di struttura di ciclo, così mi permetta di andare avanti e ottenere questo è cominciato. Include stdio.h. Lasciate che mi entrare in principale per lavorare qui. Salviamo questo come sigma.c. Poi ho intenzione di andare qui, e ho intenzione di dichiarare un int n, e ho intenzione di eseguire le seguenti operazioni mentre l'utente non collabora. Anche se l'utente non mi ha dato un numero positivo lasciatemi andare avanti e chiederà loro per GetInt n =, e fammi dare loro alcune istruzioni per quanto riguarda cosa fare, così printf ("numero intero positivo per favore"). Solo una cosa relativamente semplice come questo in modo che per il momento ci ha colpito la linea 14 ora abbiamo un numero intero positivo presumibilmente in n. Ora facciamo qualcosa con esso. Lasciatemi andare avanti e calcolare la somma, in modo int sum = sigma (n). Sigma è solo somma, quindi mi sto solo scrivendo nel modo più fantasioso. Noi chiameremo solo sigma lì. Questa è la somma, e ora ho intenzione di stampare il risultato, printf ("La somma è% d \ n", somma). E poi io restituire 0 per buona misura. Abbiamo fatto tutto quello che questo programma richiede se non la parte interessante, che è di attuare effettivamente la funzione sigma. Lasciami andare qui in fondo, e mi dichiaro funzione sigma. E 'avuto modo di prendere una variabile che è di tipo intero, e che tipo di dati voglio tornare presumibilmente da sigma? Int, perché voglio in modo da soddisfare le mie aspettative sulla linea 15. Qui dentro mi lasci andare avanti e realizzare questo in modo abbastanza semplice. Andiamo avanti e dire int sum = 0, e ora ho intenzione di andare un po 'per il ciclo qui che sta per dire qualcosa del genere, for (int i = 0; I <= numero, i + +) somma + = i. E poi ho intenzione di tornare somma. Avrei potuto implementato questo in molti modi. Avrei potuto usare un ciclo while. Avrei potuto saltato utilizzando la variabile somma, se volevo davvero, ma in breve, non ci resta che una funzione che, se non mi goof dichiara somma è 0. Poi scorre da 0 in su attraverso il numero, e ad ogni iterazione aggiunge che il valore corrente di somma e quindi restituisce somma. Ora, c'è una leggera ottimizzazione qui. Questo è probabilmente un passo sprecato, ma così sia. Questo va bene per ora. Siamo almeno in maniera accurata e andando 0 tutto il senso in su. Non è molto difficile e piuttosto semplice, ma si scopre che con la funzione sigma abbiamo la stessa possibilità come abbiamo fatto qui sul palco. Sul palco abbiamo contato quante persone erano accanto a me, ma se volessimo contare il numero 3 + 2 + 1 su fino a 0 potevamo punt simile a una funzione che io invece descrivere come ricorsiva. Qui facciamo un rapido controllo sanità mentale e assicurarsi che non l'ho fatto goof. So che c'è almeno una cosa in questo programma che ho fatto di sbagliato. Quando premi invio faccio a ottenere qualsiasi tipo di inveire contro di me? Cosa farò da urlato a circa? Si ', ho dimenticato il prototipo, quindi sto usando una funzione chiamata sigma sulla linea 15, ma non è dichiarata fino a riga 22, quindi meglio andare in modo proattivo qui e dichiarare un prototipo, e dirò int sigma (int numero), e questo è tutto. È implementato in basso. Oppure un altro modo avrei potuto risolvere il problema, Potrei spostare la funzione lassù, che non è male, ma almeno quando i vostri programmi cominciano a diventare lungo, francamente, Penso che ci sia un valore in avere sempre principale nella parte superiore in modo che nel lettore può aprire il file e poi subito a vedere cosa sta facendo il programma senza dover cercare attraverso di essa cercando quella funzione principale. Scendiamo alla mia finestra di terminale qui, provare a fare sigma fare sigma, e ho fatto un casino anche qui. Dichiarazione implicita di GetInt funzione significa che ho dimenticato di fare che altro? [Incomprensibile-studente] Bene, così apparentemente un errore comune, quindi cerchiamo di mettere questo qui, cs50.h, e ora torniamo alla mia finestra di terminale. Io pulire lo schermo, e io eseguire nuovamente fare sigma. Sembra che sia compilato. Permettetemi ora di correre sigma. Io digitare il numero 3, e io ho avuto 6, quindi non è un controllo rigoroso, ma almeno sembra funzionare a prima vista, ma ora andiamo li tiri fuori, e cerchiamo di sfruttare effettivamente l'idea di ricorsione, ancora una volta, in un contesto molto semplice in modo che nel giro di qualche settimana quando si inizia ad esplorare le strutture dati più elaborate rispetto alle matrici abbiamo un altro strumento nel toolkit con cui manipolare le strutture dati come vedremo. Questo è l'approccio iterativo, il loop approccio. Vorrei invece ora fare questo. Vorrei invece dire che la somma del numero di su fino a 0 è in realtà la stessa cosa numero + sigma (numero - 1). In altre parole, proprio come sul palco ho giocato d'azzardo a ciascuna delle persone accanto a me, che a loro volta tenuti andare in barca fino a quando abbiamo finalmente toccato il fondo a Willy, che ha dovuto restituire un hard-coded risposta del tipo 0. Qui ora stiamo simile punting a sigma la stessa funzione come originariamente chiamato, ma l'idea chiave qui è che non stiamo chiamando sigma identico. Non stiamo passando n. Siamo chiaramente di passaggio in numero - 1, così un problema leggermente più piccolo, problema leggermente più piccolo. Sfortunatamente, questo non è del tutto una soluzione ancora, e prima di rivolgere il quello che potrebbe essere che salta fuori come ovvio alcuni di voi lasciatemi andare avanti ed eseguire di nuovo fare. Sembra che per compilare bene. Permettetemi di eseguire di nuovo con 6 sigma. Ops, vorrei eseguire di nuovo con 6 sigma. Abbiamo visto prima, anche se il tempo accidentalmente scorso. Perché ho ricevuto questo errore criptico di segmentazione? Gia '. [Incomprensibile-studente] Non c'è nessun caso di base, e più in particolare, quello che probabilmente è successo? Questo è un sintomo di ciò che il comportamento? Di 'un po' più forte. [Incomprensibile-studente] Si tratta di un ciclo infinito in modo efficace, e il problema con cicli infiniti quando coinvolgono ricorsione in questo caso, una funzione che si definisce, ciò che accade ogni volta che si chiama una funzione? Beh, ripenso a come abbiamo posto la memoria in un computer. Abbiamo detto che c'è questo pezzo di memoria chiamata stack che è in basso, e ogni volta che si chiama una funzione di memoria un po 'più viene messo su questa cosiddetta pila contenente variabili locali di quella funzione o parametri, quindi se sigma Le chiamate sigma sigma chiama sigma  chiama sigma da dove viene questa storia finirà? Beh, alla fine superamenti l'importo totale di memoria che avete a disposizione sul vostro computer. È sovraccarico il segmento che si suppone di rimanere all'interno, e si ottiene questo errore di segmentazione, core dumped, e che cosa vuol dire core dumped è che ora ho un file chiamato core che è un file che contiene zero e uno che in realtà, in futuro saranno utili alla diagnosi. Se non è evidente a voi dove il bug è si può effettivamente fare un po 'di analisi forense, per così dire, su questo file core dump, che, ancora una volta, è solo un insieme di zero e uno che rappresenta in sostanza lo stato del programma in memoria nel momento in cui si è schiantato in questo modo. La correzione è che non possiamo tornare alla cieca sigma, il numero + sigma di un problema un po 'più piccolo. Abbiamo bisogno di avere un qualche tipo di scenario di base qui, e quale dovrebbe essere il caso base probabilmente? [Incomprensibile-studente] Va bene, a condizione che il numero è positivo in realtà dovremmo restituire questo, o per dirla in altro modo, se il numero è, per esempio, <= a 0 sai una cosa, io vado avanti e restituire 0, molto simile a Willy ha fatto, e il resto, ho intenzione di andare avanti e restituire il presente, quindi non è che molto più breve rispetto alla versione iterativa che abbiamo montata per prima con un ciclo for, a meno di notare che c'è questo tipo di eleganza ad esso. Invece di restituire un numero e l'esecuzione di tutto questo per la matematica e aggiungendo le cose con le variabili locali si sta invece dicendo: "Va bene, se questo è un problema super facile, come il numero è <0, fammi tornare immediatamente 0. " Non abbiamo intenzione di preoccuparsi di supporto i numeri negativi, così ho intenzione di codificare il valore 0. Ma per il resto, per attuare questa idea di riassumere tutti questi numeri insieme si può effettivamente prendere un piccolo morso di risolvere il problema, proprio come abbiamo fatto qui sul palco, poi punt il resto del problema alla persona successiva, ma in questo caso la persona è prossima stessi. Si tratta di una funzione con nome identico. Basta passare un problema sempre più piccola e più piccola di volta in volta, e anche se non abbiamo cose molto formalizzati nel codice qui questo è esattamente quello che stava succedendo nella settimana 0 con la rubrica. Questo è esattamente quello che stava succedendo nelle scorse settimane con Sean e con le nostre dimostrazioni di ricerca di numeri. Si sta prendendo un problema e che divide ancora e ancora. In altre parole, c'è un modo ora di tradurre questo costrutto mondo reale, questo costrutto livello superiore di dividere e conquistare e fare qualcosa di nuovo e di nuovo nel codice, quindi questo è qualcosa che vedremo di nuovo nel corso del tempo. Ora, da parte, se siete nuovi a ricorsione si dovrebbe almeno capire ora perché questo è divertente. Ho intenzione di andare a google.com, e sto andando alla ricerca di alcuni consigli e suggerimenti su ricorsione, digitare. Dite alla persona accanto a te, se non ridevano solo ora. Intendevi ricorsione? Intendevi-ah, ci siamo. Ok, ora che è il resto di tutti. Un piccolo uovo di Pasqua incorporato da qualche parte in Google. Per inciso, uno dei link che abbiamo messo sul sito web del corso per oggi è proprio questa griglia di vari algoritmi di ordinamento, alcuni dei quali abbiamo visto la scorsa settimana, ma la cosa bella di questa visualizzazione come si tenta di avvolgere la vostra mente intorno a varie cose legate agli algoritmi sapere che si può molto facilmente ora iniziare con diversi tipi di ingressi. Tutti gli ingressi invertiti, gli ingressi principalmente filtrate, gli ingressi casuale e così via. Come si tenta di, ancora una volta, distinguere queste cose nella tua mente si rendono conto che questo URL sul sito web del corso sulla pagina Lectures potrebbe aiutare a ragionare su alcuni di questi. Oggi finalmente a risolvere il problema da un po 'indietro, che è stato che questa funzione di scambio non ha funzionato, e quello che era il problema fondamentale con questo swap funzione, il cui obiettivo è, ancora una volta, a scambiare un valore qui e qui in modo tale che questo accade? Questo in realtà non funziona. Perché? Gia '. [Incomprensibile-studente] Esattamente, la spiegazione di questo bugginess era semplicemente perché quando si chiamano funzioni in C e queste funzioni richiedono argomenti, come a e b qui, si passa su una copia di qualsiasi valore si sta fornendo a tale funzione. Non si forniscono i valori originali stessi, così abbiamo visto questo nel contesto di buggyc, buggy3.c, che sembrava un po 'di qualcosa come questo. Ricordiamo che avevamo x ed y inizializzato a 1 e 2, rispettivamente. Abbiamo poi stampato quello che erano. Ho poi sostenuto che stavo scambiando chiamando scambio di x, y. Ma il problema era che la scambio ha funzionato, ma solo nell'ambito dello swap stesso funzionamento. Non appena abbiamo raggiunto la linea 40 quei valori invertiti sono stati gettati via, e quindi nulla nella funzione principale originale è stato effettivamente cambiato affatto, quindi se pensate allora da come si presenta in termini della nostra memoria se questo lato sinistro della scheda rappresenta- e io farò del mio meglio per tutti di vedere questo, se questo lato sinistro della scheda rappresenta, per esempio, la RAM, e lo stack è destinato a crescere su in questo modo, e che noi chiamiamo una funzione come principale, e principale dispone di 2 variabili locali, x e y, cerchiamo di descrivere quelli come x qui, e cerchiamo di descrivere questi come y qui, e mettiamo i valori 1 e 2, quindi questo è qui principale, e quando chiama la funzione principale di scambio del sistema operativo dà la funzione swap sua striscia sua memoria sullo stack, proprio quadro sullo stack, per così dire. Si assegna anche 32 bit per questi int. Succede a chiamarli a e b, ma questo è del tutto arbitraria. Si potrebbe li hanno chiamati ciò che vuole, ma cosa succede quando principale chiamate di swap è che ci vuole questo 1, inserisce una copia lì, mette una copia lì. C'è 1 altra variabile locale in swap, però, detto che cosa? >> Tmp. Tmp, quindi lasciate che mi dia un altro 32 bit qui, e quello che ho fatto in questa funzione? Ho detto tmp int ottiene un, quindi una ha 1, così ho fatto questo, quando abbiamo giocato l'ultima volta con questo esempio. Poi una si b, quindi b è 2, così ora questo diventa 2, e ora b ottiene temp, quindi temperatura è 1, così ora b diventa questo. E 'fantastico. Ha funzionato. Ma poi, non appena la funzione restituisce memoria di swap scompare in modo efficace in modo che possa essere riutilizzato da qualche altra funzione in futuro, ed è ovviamente del tutto invariato. Abbiamo bisogno di un modo per risolvere questo problema fondamentale, e oggi avremo finalmente un modo di fare questo in base al quale possiamo introdurre qualcosa chiamato un puntatore. Si scopre che siamo in grado di risolvere questo problema non passando copie di x ed y ma passando in quello, pensi che, per la funzione di swap? Si ', per quanto riguarda l'indirizzo? Non abbiamo ancora parlato di indirizzi in molti dettagli, ma se questo lavagna rappresenta la memoria del mio computer potremmo certamente iniziare la numerazione dei byte nella mia RAM e dire questo è byte # 1, questo è il byte # 2, # 3 byte, byte # 4, # byte ... 2 miliardi di euro se ho 2 gigabyte di RAM, così abbiamo potuto sicuramente trovare un qualche schema di numerazione arbitraria per tutti i singoli byte nella memoria del mio computer. E se invece quando chiamo di swap piuttosto che passare una copia di x e y perchè non ho invece passare l'indirizzo di x qui, l'indirizzo di y qui, in sostanza, l'indirizzo postale di x e y perché poi scambiare, se è informato l'indirizzo in memoria di x ed y, poi scambiare, se lo ha formato un po ', egli potrebbe guidare a tale indirizzo, per così dire, x, e cambiare il numero di là, quindi proseguire per l'indirizzo di y, modificare il numero lì, anche se in realtà non ottenere copie di se stesso quei valori, quindi, anche se abbiamo parlato di questo come la memoria principale e questo scambio come nella memoria dei potenti e la parte pericolosa di C che è una funzione di memoria può toccare qualsiasi parte del computer, e questo è potente in quanto si possono fare cose molto elaborate con programmi per computer in C. Questo è pericoloso perché si può anche rovinare molto facilmente. In effetti, uno dei modi più comuni per i programmi in questi giorni da sfruttare non è ancora per un programmatore di realizzare che lui o lei sta permettendo un dato da scrivere in una locazione di memoria che non era destinato. Per esempio, lui o lei dichiara un array di dimensione 10 ma poi cerca di mettere accidentalmente 11 byte in quella matrice di memoria, e di iniziare a toccare parti di memoria che non sono più validi. Solo per questo contestuale, alcuni di voi potrebbe sapere che Il software richiede spesso per i numeri di serie o chiavi di registrazione, Photoshop e Word e programmi come questo. Esistono crepe, come alcuni di voi sanno, on-line dove è possibile eseguire un piccolo programma, e voilà, nessuna richiesta di più per un numero di serie. Come è che funziona? In molti casi, queste cose sono semplicemente trovare nei computer segmenti di testo in zeri reali del computer e quelli dove è quella funzione in cui è richiesto il numero di serie, e sovrascrivere quello spazio, o mentre il programma è in esecuzione è possibile capire dove la chiave è in realtà memorizzati usando una cosa chiamata un debugger, e si può rompere il software in questo modo. Questo non vuol dire che questo è il nostro obiettivo per i prossimi due giorni, ma ha molto reali ramificazioni. Quello succede a coinvolgere furto di software, ma c'è anche compromissione di intere macchine. In effetti, quando i siti web in questi giorni sono sfruttati e compromesso e dati è trapelato e le password sono rubati questo molto spesso si riferisce ad una cattiva gestione della propria memoria, oppure, nel caso di banche dati, mancata anticipazione ingresso contraddittorio, in modo più su che nelle settimane a venire, ma per ora solo in anteprima il tipo di danno che si può fare da non capire bene come funzionano le cose sotto la cappa. Andiamo di capire perché questo è rotto con uno strumento che diventerà sempre più utile i nostri programmi diventano più complessi. Finora quando hai avuto un bug nel programma come sei andato sul debug di esso? Quali sono le vostre tecniche stato così lontano, se insegnata dal TF o semplicemente autodidatta? [Studente] Printf. Printf, così printf è stato probabilmente il tuo amico nel senso che se volete vedere quello che sta succedendo all'interno del vostro programma basta mettere printf qui, printf qui, printf qui. Poi lo si esegue, e si ottiene un sacco di roba sullo schermo che è possibile utilizzare per dedurre allora che cosa è in realtà che non va nel programma. Printf tende ad essere una cosa molto potente, ma è un processo molto manuale. Dovete mettere un printf qui, un printf qui, e se lo metti in un loop si potrebbe ottenere 100 linee di output che è quindi necessario passare al setaccio. Non è un meccanismo molto facile da usare e interattivo per programmi di debug, ma per fortuna esistono alternative. C'è un programma, ad esempio, chiamato GDB, il debugger GNU, che è un po 'arcano nel modo in cui lo si utilizza. E 'un po' complessa, ma, francamente, questa è una di quelle cose in cui, se si mettono in questa settimana e la prossima il cambio di capire qualcosa come GDB ti farà risparmiare probabilmente decine di ore nel lungo periodo, E con questo, mi permetta di darle un teaser di come funziona questa cosa. Sono nella mia finestra di terminale. Lasciatemi andare avanti e compilare questo programma, buggy3. E 'già aggiornata. Vorrei correre, proprio come abbiamo fatto un po 'indietro, e anzi, si è rotto. Ma perché questo? Forse ho sbagliato la funzione di swap. Forse è a e b. Non mi ha ancora li muoversi correttamente. Lasciatemi andare avanti e farlo. Piuttosto che correre buggy3 lasciatemi invece eseguire questo programma GDB, e ho intenzione di dire l'esecuzione buggy3, e ho intenzione di inserire un parametro della riga di comando,-tui, e noi provvederemo a mettere questo in futuro problemi a spec per ricordare. E ora questa interfaccia in bianco e nero sono saltate fuori che, ancora una volta, è un po 'opprimente in un primo momento, perché c'è tutta questa informazioni sulla garanzia qui, ma almeno c'è qualcosa di familiare. Nella parte superiore della finestra è il mio codice attuale, e se scorrere verso l'alto qui permettetemi di scorrere fino alla cima del mio file, e in effetti, c'è buggy3.c, e notare in fondo a questa finestra Ho questo prompt GDB. Questo non è lo stesso come il mio normale John Harvard prompt. Si tratta di un messaggio che sta per permettermi di controllare GDB. GDB è un debugger. Un debugger è un programma che ti permette di camminare attraverso esecuzione del programma riga per riga per riga, lungo la strada a fare tutto quello che vuoi al programma, anche chiamare le funzioni, o in cerca, ancora più importante, a valori di variabili diverse. Andiamo avanti e farlo. Ho intenzione di andare avanti e digitare al prompt di esecuzione del GDB, in modo da notare in basso a sinistra dello schermo che ho digitato correre, e ho premere invio, e che cosa ha che fare? E 'letteralmente correva il mio programma, ma non ho davvero visto molto andare qui perché non ho effettivamente detto il debugger per mettere in pausa in un particolare momento nel tempo. Basta digitare esecuzione esegue il programma. Io in realtà non vede nulla. Non posso manipolare. Invece vorrei fare questo. In questo prompt GDB vorrei invece digitare pausa, entrare. Non è quello che volevo scrivere. Facciamo invece digitare pausa principale. In altre parole, voglio impostare qualcosa chiamato un punto di interruzione, che è giustamente chiamato perché si romperà o mettere in pausa esecuzione del programma in quel determinato luogo. Principale è il nome della mia funzione. Si noti che GDB è abbastanza intelligente. È capito che succede principale per avviare o meno allo linea 18 di buggy3.c e osservare qui in alto a sinistra b + è proprio accanto alla linea 18. Questo mi ricorda che ho impostato un punto di interruzione alla riga 18. Questa volta, quando si digita run, ho intenzione di eseguire il mio programma fino al punto di interruzione che colpisce, in modo che il programma si fermerà per me in linea 18. Ci siamo, correre. Niente sembra essere successo, ma notate in basso a sinistra programma iniziale, buggy3, breakpoint 1 in linea principale buggy3.c 18. Cosa posso fare adesso? Notate che può iniziare a digitare cose come stampa, Non printf, x stampa, e ora che è strano. Il $ 1 è solo una curiosità, come vedremo ogni volta che si stampa qualcosa che si ottiene un nuovo valore di $. E 'così che si può fare riferimento ai valori precedenti solo nel caso in cui, ma per ora quello che stampa mi sta dicendo è che il valore di x a questo punto della storia è apparentemente 134514032. Cosa? Da dove che anche viene? [Incomprensibile-studente] In effetti, questo è ciò che chiamo un valore di spazzatura, e non abbiamo ancora parlato di questo, ma la ragione per cui si inizializza le variabili è, ovviamente, in modo che abbiano un certo valore che si desidera loro di avere. Ma il problema è ricordare che è possibile dichiarare variabili come ho fatto io poco fa nel mio esempio sigma senza peraltro riuscire a dare un valore. Ricordiamo quello che ho fatto qui in sigma. Dichiarai n, ma che valore ha lo do? Nessuna, perché sapevo che in poche righe GetInt si sarebbe preso cura del problema di mettere un valore all'interno di n. Ma a questo punto della storia della linea 11 e 12 la linea e la linea 13 e linea 14 durante tali righe qual è il valore di n? In C proprio non lo so. E 'in genere un valore spazzatura, qualche numero del tutto casuale che è rimasto essenzialmente da qualche funzione precedente essendo stato eseguito, in modo da il programma viene eseguito Ricordiamo che la funzione riceve, funzione, funzione. Tutte queste strutture vengono messe sulla memoria, e poi quelli di ritorno funzioni, e proprio come ho proposto con la gomma la loro memoria alla fine viene riutilizzato. Beh, si da il caso che questa variabile x in questo programma sembra aver contenuto un certo valore come spazzatura 134514032 da qualche funzione precedente, non quello che ho scritto. Potrebbe essere qualcosa che viene efficacemente con il sistema operativo, qualche funzione sotto la cappa. Va bene, va bene, ma andiamo ora passare alla riga successiva. Se scrivo "accanto" al prompt di GDB mia e mi ha colpito entrare, notare che l'evidenziazione si sposta fino alla linea 19, ma l'implicazione logica è che la linea 18 ha finito "print x" l'esecuzione, quindi se ho di nuovo tipo Vorrei ora apparire 1, e anzi, lo faccio. Anche in questo caso, il $ roba è un modo di GDB ricordando ciò che la storia di stampe sono che hai fatto. Ora lasciatemi andare avanti e stampare y, e in effetti, y è un valore folle pure, ma niente di grave, perché in linea 19 che stiamo per assegnare il valore 2, per cui vorrei scrivere "Avanti". E ora siamo in linea printf. Lasciami fare x stampa. Lasciami fare y stampa. Francamente, mi sto un po 'stanco della stampa di questo. Meglio invece digitare "x display" e "visualizzazione y," e ora ogni volta che si digita un comando, in futuro Sarò ricordato di ciò che è x e y, che cosa è x e y, che cosa è x e y. Posso anche, per inciso, digitare "informazioni locali". Info è un comando speciale. La gente del posto significa che mi mostra le variabili locali. Solo nel caso in cui ho dimenticato o si tratta di un pazzo, la funzione complessa che io o qualcun altro ha scritto locals informazioni vi dirà quali sono tutte le variabili locali all'interno di questa funzione locale che si potrebbe preoccuparsi se volete curiosare. Ora, è printf per l'esecuzione, per cui vorrei andare avanti e basta digitare "prossimo". Perché siamo in questo ambiente non stiamo realmente vedendo eseguire qui, a meno di notare sta diventando un po 'martoriato qui. Ma bando è prevalente lo schermo lì, quindi non è un programma perfetto qui, ma va bene perché posso sempre curiosare con stampa, se voglio. Permettetemi di tipo successivo di nuovo, e ora ecco la parte interessante. A questo punto della storia y è 2, ed x è 1, come suggerito qui, e ancora una volta, la ragione per cui questo viene automaticamente la visualizzazione di ora è perché ho usato il comando x display e display y, in modo che il momento in cui ho digitato successivamente in teoria x ed y dovrebbe diventare scambiati. Ora, sappiamo già che non sarà il caso, ma staremo a vedere in un momento come si può scendere ad una profondità di capire perché è vero. Avanti, e purtroppo, è ancora y 2 e x è ancora 1, e posso confermare tanto. Stampa x, y stampa. Infatti, nessun scambio è effettivamente accaduto, quindi cerchiamo di iniziare questo corso. Chiaramente swap è rotto. Facciamo invece di tipo "run" di nuovo. Permettetemi di dire di sì, voglio riavviarlo dall'inizio, entrare. Ora sono di nuovo fino alla riga 18. Ora notate x e y sono valori spazzatura di nuovo. Poi, dopo, dopo, dopo. Se mi annoio posso anche semplicemente digitare n per il prossimo. È possibile abbreviare la sequenza più breve possibile di caratteri. Swap è ormai rotto. Tuffiamoci in, quindi invece di digitare prossimo, ora ho intenzione di scrivere passo, in modo che io passo all'interno di questa funzione modo che io possa camminare attraverso di essa, così ho colpito passo e quindi immettere. Si noti che i salti evidenziando più in basso nel mio programma per la linea 36. Ora, quali sono le variabili locali? Informazioni locali. Niente appena ancora, perché non abbiamo avuto modo di quella linea, quindi cerchiamo di andare avanti e dire "accanto". Ora ci sembra di avere tmp, tmp stampa. Valore Garbage, giusto? Credo di sì. Che ne dici di stampare una, stampa b, 1 e 2? In un attimo, non appena ho digitato successivamente di nuovo tmp sta per assumere un valore di 1, si spera, perché tmp sta per essere assegnato il valore di una. Ora facciamolo stampa a, b di stampa, ma ora stampare tmp, ed è davvero 1. Lasciami fare. Lasciami fare. Ho finito la funzione di swap. Sono ancora dentro di esso in linea 40, per cui vorrei stampare una, stampa b, e non mi importa di quello che è tmp. Sembra di swap è corretto quando si tratta di scambiare a e b. Ma se io ora digitato successivamente, Faccio un salto indietro alla riga 25, e, naturalmente, se digito x e y stampa sono ancora invariata, quindi non abbiamo risolto il problema. Ma diagnosticamente ora forse con questo programma GDB abbiamo ottenuto almeno un passo avanti verso la comprensione cosa c'è di sbagliato senza lettiera nostro codice mettendo un printf qui, printf qui, printf qui e poi in esecuzione di nuovo e di nuovo cercando di capire cosa c'è di sbagliato. Ho intenzione di andare avanti e uscire da questo tutto con smettere. Si dirà poi, "Esci comunque?" Sì. Ora sono tornato al mio normale prompt, e ho fatto usando GDB. Per inciso, non è necessario utilizzare questo-tui bandiera. Infatti, se si omette si ottiene essenzialmente la metà inferiore dello schermo. Se quindi digitare pausa principale e quindi eseguire Posso ancora eseguire il mio programma, ma quello che farà è più testualmente mi mostrano quello attuale riga alla volta. Il-tui, interfaccia utente testuale, mostra solo una più del programma in una sola volta, che è probabilmente un po 'più semplice concettualmente. Ma in effetti, posso solo fare dopo, dopo, dopo, e sto andando a vedere una riga alla volta, e se voglio davvero vedere che cosa sta succedendo Posso digitare lista e vedere un sacco di linee vicine. C'è un video che abbiamo chiesto che si guarda per il problema set 3 Nate in cui vengono illustrate alcune delle complessità di GDB, e questa è una di quelle cose, onestamente, dove alcuni non banale percentuale di voi non potrà mai toccare GDB, e che sarà una cosa negativa perché letteralmente si finirà per spendere di più tempo dopo questo semestre dare la caccia ai bug allora si avrebbe se si mette in quella mezz'ora / ora questa settimana e l'apprendimento accanto a mettersi a proprio agio con GDB. Printf era tuo amico. GDB dovrebbe essere tuo amico. Hai domande su GDB? Ed ecco una breve lista di alcuni dei comandi più utili e potenti. Si '. >> È possibile stampare una stringa? È possibile stampare una stringa? Assolutamente. Essa non deve essere solo numeri interi. Se una variabile s è una stringa è sufficiente digitare s stampa. Essa vi mostrerà ciò che è variabile di stringa. [Incomprensibile-studente] Vi darà l'indirizzo e la stringa stessa. Essa vi mostrerà entrambi. E un ultima cosa, solo perché questi sono troppo buono a sapersi. Backtrace e telaio, fammi tuffarsi in questo tempo ultimo, stesso programma esatto con GDB. Lasciami andare avanti ed eseguire la versione testuale interfaccia utente, rottura principale. Lasciatemi andare avanti e correre di nuovo. Eccomi. Ora lasciami andare dopo, dopo, dopo, dopo, dopo, passo, entrare. E ora supponiamo che io sono ora in scambio deliberatamente, ma io sono come "Accidenti, quello che era il valore di x?" Non posso fare x più. Non posso fare y perché non sono portata. Non sono in un contesto, ma nessun problema. Posso digitare backtrace. Questo mi mostra tutte le funzioni che sono eseguite fino a questo punto nel tempo. Si noti che quella sul fondo, principale, si allinea con la principale essendo sul fondo della nostra immagine qui. Il fatto che è al di sopra di swap si allinei con scambio di essere al di sopra nella memoria qui, e se voglio tornare alla pagina principale temporaneamente posso dire "frame". Che numero? Principale è frame # 1. Ho intenzione di andare avanti e dire "frame 1." Ora sono di nuovo in main, e posso stampare x, e posso stampare y, ma non riesco a stampare a o b. Ma posso se dico: "Va bene, aspetta un attimo. Dov'era lo swap?" Lasciatemi andare avanti e dire "0 cornice." Ora sono di nuovo dove voglio essere, e per inciso, ci sono anche altri comandi, come se siete veramente ottenere digitando annoiato dopo, dopo, dopo, dopo, si può generalmente dire cose come "prossimi 10", e che è possibile scorrere i prossimi 10 linee. Si può anche scrivere "continua" quando si ha realmente stufo di passo attraverso di essa. Continua il programma verrà eseguito senza interruzioni fino a raggiungere un altro punto di interruzione, se in un ciclo o più in basso nel vostro programma. In questo caso abbiamo continuato fino alla fine, e il programma è terminato normalmente. Questo è un modo di fantasia, di processo inferiore. Solo il tuo programma è terminato normalmente. Più su quello nel video e nelle sessioni di debug a venire. E 'stato molto. Prendiamo la nostra pausa di 5 minuti qui, e torneremo con le strutture e file. Se si è tuffato in pset di questa settimana già saprete che usiamo nel codice di distribuzione, il codice sorgente che forniamo a voi come un punto di partenza, alcune nuove tecniche. In particolare, abbiamo introdotto questa nuova parola chiave struct chiamato, per la struttura, in modo da poter creare variabili personalizzate di sorta. Abbiamo inoltre introdotto il concetto di file di I / O, file di input e output, e questo è il modo che si possa salvare lo stato della tavola Scramble in un file su disco in modo che i compagni di insegnamento e posso capire quello che sta succedendo all'interno del programma senza dover giocare manualmente decine di giochi di Scramble. Possiamo fare questo più automatedly. Questa idea di una struttura risolve un problema abbastanza convincente. Supponiamo di voler implementare qualche programma che in qualche modo tiene traccia delle informazioni sugli studenti, e studenti potrebbe avere, per esempio, un ID, un nome e una casa in un posto come Harvard, per cui questi sono 3 pezzi di informazioni vogliamo tenere in giro, per cui vorrei andare avanti e iniziare a scrivere un piccolo programma qui, includere stdio.h. Lasciate fare a me sono cs50.h. E poi iniziare la mia funzione principale. Non voglio perdere tempo con gli argomenti della riga di comando, e qui voglio avere uno studente, così ho intenzione di dire uno studente ha un nome, così ho intenzione di dire "nome di stringa." Poi ho intenzione di dire che uno studente ha anche un ID, così int id, e uno studente ha una casa, così ho anche intenzione di dire "casa di stringa." Poi mi ordinare questi un po 'più pulito come questo. Ok, ora ho 3 variabili con cui rappresentano uno studente, in modo da "uno studente". E ora voglio per popolare questi valori, per cui vorrei andare avanti e dire qualcosa del tipo "Id = 123". Nome sta per arrivare David. Diciamo casa sta per arrivare Mather, e poi ho intenzione di fare qualcosa di arbitrariamente come printf ("% s, il cui ID è% d,% vive in s. E ora, che cosa voglio collegare qui, uno dopo l'altro? Nome, id, casa, di ritorno 0. Va bene, a meno che non ho sbagliato da qualche parte qui Penso che abbiamo un programma abbastanza buono che memorizza uno studente. Naturalmente, questo non è tutto ciò che interessa. Cosa devo fare se voglio avere 2 studenti? Questo è un grosso problema. Sono in grado di supportare 2 persone. Lasciatemi andare avanti e mettere in evidenza questo e scendere qui, e posso dire "id = 456" per uno come Rob che vive a Kirkland. Ok, aspetta, ma non posso chiamare queste la stessa cosa, e sembra che ho intenzione di dover copiare questo, quindi lasciatemi dire che questi saranno Davide variabili, e mi permetta di ottenere alcune copie di questi per Rob. Chiameremo questi Rob ma questo non è andare a lavorare ora perché ho-aspetta, mi fa cambiare id1, nome1 e house1. Rob sarà 2, 2. Ho avuto modo di cambiare questo qui, qui, qui, qui, qui, qui. Aspetta, che dire di Tommy? Facciamolo di nuovo. Ovviamente se pensate ancora che questo è un buon modo di fare questo, non è, quindi copia / incolla male. Ma abbiamo risolto questo una settimana fa. Qual è stata la nostra soluzione quando volevamo avere più istanze dello stesso tipo di dati? [Gli studenti] Matrice. Un array, per cui vorrei provare a pulire questo. Permettetemi di fare un po 'camera per me in cima, e lasciatemi invece farlo qui. Chiameremo queste persone, e invece ho intenzione di dire "id int," e ho intenzione di sostenere noi 3 per ora. Io vado a dire "i nomi di stringa," e io ti appoggio 3 di noi, e poi ho intenzione di dire "case di stringa", e ho intenzione di supportare 3 di noi. Ora, qui invece di Davide ottenere le sue proprie variabili locali siamo in grado di sbarazzarsi di quelle. Che si sente bene che stiamo pulire questo. Posso quindi dire che David sta per essere [0] e nomi [0] e case [0]. E poi Rob possiamo analogicamente risparmiare su questo. Mettiamo questo qui, così sarà arbitrariamente id [1]. Sta per essere nomi [1], e poi infine, case [1]. Ancora un po 'noioso, e ora devo questo numero, quindi diciamo "nomi [0], id [0], case [0], e cerchiamo di questo plurale. Ids, id, id. E ancora, lo sto facendo, così ancora una volta, sto già ricorrere a copiare / incollare di nuovo, così probabilità sono c'è un'altra soluzione qui. Probabilmente posso pulire questo ulteriormente con un ciclo o qualcosa del genere, Così, in breve, è un po 'meglio, ma ha ancora voglia di Sono ricorso a copiare / incollare, ma anche questo, io sostengo, non è davvero fondamentalmente la soluzione giusta perché E se qualche volta si decide sai una cosa? Abbiamo davvero avrebbe dovuto memorizzare indirizzi e-mail per David e Rob e tutti gli altri in questo programma. Dovremmo anche memorizzare i numeri di telefono. Dovremmo anche memorizzare numeri di contatto di emergenza. Abbiamo tutti questi pezzi di dati che vogliamo conservare, così come si fa a farlo? Si dichiara un altro array in alto, e poi aggiungere manualmente un indirizzo di posta elettronica [0], indirizzo di posta elettronica [1] per David e Rob e così via. Ma non c'è davvero solo un presupposto fondamentale di questo progetto che si sta usando il sistema onore di sapere che [I] in ciascuna delle più array così succede per riferirsi alla stessa persona, in modo da [0] a id è il numero 123, e ho intenzione di assumere che i nomi [0] è la stessa persona di nome e case [0] casa è la stessa persona e così via per tutte le matrici diverse che creano. Ma nota che non c'è legame fondamentale tra i 3 pezzi di informazioni, id, il nome e la casa, anche se l'entità che stiamo cercando di modello in questo programma non è array. Gli array sono proprio in questo modo programmatico di fare questo. Che cosa vogliamo veramente modellare nel nostro programma è una persona come Davide, una persona come Rob all'interno del quale o incapsulamento è un nome e un ID e una casa. Possiamo in qualche modo esprimere questa idea di incapsulamento in base al quale una persona ha un ID, un nome e una casa e non ricorrere a proprio questo hack per cui abbiamo appena fiducia che qualcosa di staffa si riferisce alla stessa entità umana in ciascuna di queste matrici disparati? Si può effettivamente fare questo. Lasciami andare sopra principale per ora, e lasciami creare il mio proprio tipo di dati realmente per la prima volta. Abbiamo usato questa tecnica in Scramble, ma qui ho intenzione di andare avanti e di creare un tipo di dati, e sai una cosa, ho intenzione di chiamarlo studente o persona, e ho intenzione di usare typedef per definire un tipo. Io vado a dire che questa è una struttura, e poi questa struttura sta per essere di tipo studente, diremo, anche se è un po 'datato ormai per me. Diremo "int id." Diremo "nome di stringa." Poi diremo "casa stringa" così ora per la fine di queste poche righe di codice Ho appena insegnato clang che esiste un tipo di dati int, oltre, oltre le stringhe, oltre raddoppia, oltre a carri. Da questo momento in linea di tempo 11, ora c'è un nuovo tipo di dati chiamato gli studenti, e ora posso dichiarare una variabile studente dove voglio, così mi permetta di scorrere verso il basso qui per le persone. Ora posso liberarmi di questo, e non posso andare giù a David qui, e per David posso effettivamente dire che David, possiamo letteralmente il nome della variabile dopo di me, sta per essere dello studente tipo. Questo potrebbe sembrare un po 'strano, ma questo non è poi così diverso da dichiarare qualcosa come un int o una stringa o di un galleggiante. Si dà il caso di essere chiamato ora studente, e se voglio mettere qualcosa all'interno di questa struttura Ora è necessario utilizzare un nuovo pezzo di sintassi, ma è piuttosto semplice, david.id = 123, david.name = "David" di capitale D, e david.house = "Mather," e ora può sbarazzarsi di questa roba qui. Avviso ora abbiamo ridisegnato il nostro programma in realtà un modo molto migliore a che ora il nostro programma rispecchia il mondo reale. C'è un mondo reale nozione di una persona o di uno studente. Qui abbiamo ora una versione C di una persona o più precisamente uno studente. All'interno di questa persona sono queste caratteristiche peculiari, ID, il nome e la casa, in modo da Rob diventa essenzialmente la stessa cosa qui, così studente rob, e ora rob.id = 456, rob.name = "Rob". Il fatto che la variabile è denominata Rob è una sorta di senso. Avremmo potuto chiamato x o y o z. Abbiamo appena chiamato Rob di essere semanticamente coerente, ma in realtà il nome è all'interno di quel campo stesso, così ora ho questo. Anche questo non si sente come il migliore design che ho hardcoded David. Ho hardcoded Rob. E ho ancora bisogno di ricorrere a un po 'di copia e incolla ogni volta che voglio nuove variabili. Inoltre, devo dare apparentemente ognuna di queste variabili un nome, anche se mi piacerebbe molto meglio descrivere queste variabili  studenti più genericamente come. Ora siamo in grado di unire le idee che hanno lavorato bene per noi e invece dire: "Sai una cosa, dammi di studenti variabile chiamata, e lasciare che sono sia di dimensione 3 ", così ora posso definire questa ulteriore, sbarazzarsi del manuale ha dichiarato David, e posso invece dire una cosa del genere gli studenti [0] qui. Posso quindi dire che gli studenti [0] qui, studenti [0] qui, e così via, e posso andare in giro e la pulizia che per Rob. Potrei anche andare in giro ora forse l'aggiunta di un ciclo e l'utilizzo di GetString e GetInt realmente per ottenere questi valori da parte dell'utente. Potrei fare per aggiungere una costante, perché questo è generalmente cattiva pratica codificare un numero arbitrario come 3 proprio qui e poi basta ricordare che si dovrebbe mettere non più di 3 studenti in esso. Probabilmente sarebbe meglio usare # define nella parte superiore del mio file e il fattore che fuori, così effettivamente, lasciami andare avanti e questo generalizzare. Vorrei aprire un esempio che è tra di oggi esempi in anticipo, structs1. Si tratta di un programma più completo che utilizza # define qui e dice che stiamo andando ad avere 3 studenti per impostazione predefinita. Qui sto dichiarando un valore di classe di studenti, così una classe di studenti, e ora sto usando un ciclo solo per rendere il codice un po 'più elegante, popolare la classe con l'input dell'utente, in modo da scorrere da i = 0 su un massimo di studenti, che è 3. E poi richiedere all'utente in questa versione  ciò che è ID dello studente, e lo ottiene con GetInt. Che il nome dello studente, e poi ho capito con GetString. Cosa c'è di casa dello studente? Ho capito con GetString. E poi in fondo qui ho deciso di cambiare come sto stampando questi fuori e di utilizzare effettivamente un ciclo, E chi sono io la stampa? Secondo il commento che sto stampando nessuno in Mather, e che è così Rob e Tommy e così via, in realtà Tommy a Mather. Tommy e David sarebbe stato stampato in questo caso, ma come è questo lavoro? Non abbiamo visto questa funzione prima, ma prendere a indovinare da quello che fa. Confronta le stringhe. E 'un po' non ovvio come si confronta stringhe perché si scopre se restituisce 0 significa che le stringhe sono uguali. Se restituisce -1 significa che si arriva in ordine alfabetico dopo l'altro, e se restituisce +1 che significa che l'altra parola è in ordine alfabetico prima degli altri, e si può guardare online o presso la pagina man per vedere esattamente in che direzione è che, ma tutto questo ora sta facendo è che sta dicendo se [i]. casa è uguale a "Mather" poi andare avanti e stampare così ed è così in Mather. Ma ecco qualcosa che non abbiamo mai visto prima, e torneremo a questo. Non ricordo di aver mai a che fare questo in uno dei miei programmi. Gratuito è apparentemente riferimento alla memoria, liberando la memoria, ma ciò che la memoria a quanto pare sto liberando in questo ciclo in fondo a questo programma? Sembra che io stia liberando nome di una persona e la casa di una persona, ma perché? Si scopre tutte queste settimane che hai utilizzato GetString abbiamo tipo di introdotto un bug in ogni uno dei vostri programmi. GetString da disegno in memoria allocata in modo che possa tornare a voi una stringa, come David, o Rob, e si può fare quello che vuoi con quella stringa nel programma perché abbiamo riservato la memoria per voi. Il problema è che per tutto questo tempo ogni volta che si chiama GetString noi, gli autori di GetString, hanno chiesto il sistema operativo per darci un po 'di RAM per questa stringa. Dacci un po 'di RAM per questa stringa successiva. Dacci un po 'di RAM in più per questa stringa successiva. Quello che, il programmatore, non sono mai fatto che ci sta dando indietro la memoria, così per queste diverse settimane tutti i programmi che hai scritto hanno avuto quello che si chiama un salto di memoria in base al quale continuare ad usare memoria sempre di più ogni volta che si chiama GetString, e va bene. Abbiamo volutamente farlo nelle prime settimane perché non è così interessante doversi preoccupare di dove la stringa proviene. Tutto quello che vuoi è la parola Rob di tornare quando l'utente lo tipi poll Ma andare avanti ora dobbiamo iniziare a ricevere più sofisticato su questo. Ogni volta che l'allocazione della memoria è meglio eventualmente restituire. In caso contrario, nel mondo reale sul vostro Mac o PC è possibile che di tanto in tanto con esperienza sintomi in cui il computer è il blocco totale alla fine o la palla stupida spiaggia filatura è solo occupando del computer attenzione l'intero e non si può fare le cose. Questo può essere spiegato con un qualsiasi numero di bug, ma tra i possibili bug sono cose chiamate perdite di memoria in base al quale una persona che ha scritto quel pezzo di software si sta utilizzando non ricordava per liberare memoria che lui o lei ha chiesto al sistema operativo per, non utilizzando GetString, perché questa è una cosa CS50, ma utilizzando funzioni simili che chiedono il sistema operativo per la memoria. Se voi o loro vite e mai realmente tornare la memoria un sintomo che può essere che un programma rallenta e rallenta e rallenta a meno che non si ricorda di chiamare gratis. Torneremo a quando e perché si potrebbe chiamare libero, ma andiamo avanti per buona misura e prova ad eseguire questo particolare programma. Questo è stato chiamato structs1, entrare. Lasciami andare avanti ed eseguire structs1, 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, e vediamo di David a Mather, Tommy in Mather. Questo è solo un controllo di integrità sul fatto che il programma è in funzione. Ora, purtroppo, questo programma è un po 'frustrante in quanto Ho fatto tutto questo lavoro, ho digitato in 9 diverse stringhe, premere invio, è stato detto che era in Mather, ma ovviamente sapevo che era in Mather già perché l'ho scritto. Sarebbe bello se almeno questo programma è più simile a un database e ricorda davvero quello che ho digitato così non ho mai più avere a inserire questi record degli studenti. Forse è come un sistema registrarial. Possiamo farlo utilizzando questa tecnica nota come I / O file, file di input e output, un modo molto generico di dire ogni volta che si desidera leggere i file o scrivere file si può fare questo con un certo insieme di funzioni. Lasciatemi andare avanti e aprire questo structs2.c esempio, che è quasi identico, ma vediamo cosa fa ora. Nella parte superiore del file dichiaro una classe di studenti. Ho quindi popolare la classe con l'input dell'utente, in modo che le righe di codice sono esattamente come prima. Poi scorrere verso il basso se qui mi stampa tutti coloro che sono in Mather arbitrariamente come prima, ma questa è una novità interessante. Queste righe di codice sono nuovi, e introducono qualcosa qui, FILE, tutti i tappi, e che ha in * anche qui. Vorrei spostare questo qui, a * qui pure. Questa funzione non abbiamo visto prima, fopen, ma significa aprire il file, quindi cerchiamo di sfogliare questi, e questo è qualcosa che torneremo al pset future, ma questa linea qui si apre essenzialmente un file chiamato di database, e si apre specificamente in modo da poter fare ciò che ad esso? [Incomprensibile-studente] Giusto, quindi "w" significa semplicemente che sta dicendo il sistema operativo aprire questo file in modo che io possa scrivere in essa. Non voglio leggerlo. Io non voglio guardare solo a questo. Voglio cambiare e aggiungere roba potenzialmente ad esso, e il file sta per essere chiamato database. Questo potrebbe essere chiamato niente. Questo potrebbe essere database.txt. Questo potrebbe essere. Db. Questo potrebbe essere una parola come foo, ma arbitrariamente scelto di assegnare un nome al file di database. Si tratta di un controllo di integrità poco che torneremo al dettaglio nel corso del tempo, se fp, per puntatore a file, non NULL uguale significa che tutto va bene. Per farla breve, funzioni come fopen a volte falliscono. Forse il file non esiste. Forse sei fuori di spazio su disco. Forse non hai i permessi per quella cartella, quindi se fopen restituisce qualcosa di brutto è accaduto nulla. Al contrario, se fopen non restituisce nulla va tutto bene e io posso iniziare a scrivere a questo file. Ecco un nuovo trucco. Si tratta di un ciclo che sta per iterare su ognuno dei miei studenti, e questo sembra così simile a quello che abbiamo fatto prima, ma questa funzione è un cugino di printf chiamato fprintf per file printf, e notare è diverso in soli 2 modi. Uno, inizia con f al posto di p, ma poi il suo primo argomento è apparentemente cosa? [Gli studenti] del file. >> Si tratta di un file. Questa cosa chiamata fp, di cui parleremo alla fine prendere in giro a parte quello che è un puntatore a file, ma per ora fp rappresenta semplicemente il file che ho aperto, così fprintf qui sta dicendo stampare ID di questo utente al file, non sullo schermo. Stampare il nome dell'utente al file, non sullo schermo, la casa al file, non sullo schermo, e poi giù qui, ovviamente, chiudere il file, e poi giù qui liberare la memoria. L'unica differenza tra la versione 2 e la versione 1 è l'introduzione di fopen e questo file con * e questa nozione di fprintf, quindi cerchiamo di vedere che cosa il risultato finale è. Lasciami andare nella mia finestra di terminale. Vorrei correre structs2, entrare. Sembra che tutto va bene. Facciamo eseguire nuovamente structs2. 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, entrare. Sembra che comportava lo stesso, ma se io ora fare ls notare ciò che file è qui in mezzo a tutto il mio codice, database, quindi cerchiamo di aprire quella, gedit di database, e guardare a questo. Non è la più sexy di formati di file. E 'davvero un pezzo di linea dati per riga per riga, ma quelli di voi che usano i file di Excel o CSV, valori separati da virgola, Potrei certamente ho usato fprintf per fare, invece forse qualcosa di simile in modo da poter effettivamente creare l'equivalente di un file Excel separando le cose con una virgola, non solo nuove linee. In questo caso, se avessi invece usato le virgole al posto di nuove linee Potrei letteralmente aprire il file di database in Excel se ho invece fatto simile a questa. In breve, ora che abbiamo il potere di scrivere i file ora possiamo iniziare a dati persistenti, tenendolo in giro su disco in modo da poter mantenere le informazioni in giro ancora e ancora. Si noti un paio di altre cose che ora sono un po 'più familiare. Nella parte superiore di questo file C abbiamo un typedef perché abbiamo voluto creare un tipo di dati che rappresenta una parola, quindi questo tipo è chiamato parola, e all'interno di questa struttura è un po 'più elaborato ora. Perché è una parola composta da un array a quanto pare? Che cosa è una parola solo intuitivamente? Si tratta di un array di caratteri. Si tratta di una sequenza di caratteri back to back to back. LETTERE in tutti i tappi sembra essere arbitrariamente dire la lunghezza massima di qualsiasi parola nel dizionario che stiamo usando per Scramble. Perché ho un +1? Il carattere null. Ricordate quando abbiamo fatto l'esempio Bananagrams abbiamo bisogno di un valore speciale alla fine della parola per tenere traccia di dove le parole in realtà ha finito, e come la definizione di un set problema dice qui stiamo associando a una parola data un valore booleano, una bandiera, per così dire, vero o falso. Hai trovato questa parola già, perché ci rendiamo conto abbiamo veramente bisogno di un modo di ricordare non solo ciò che una parola è in Scramble ma se si, l'umano, l'hanno trovato in modo che se si fa trovare la parola "il" non si può semplicemente digitare il, entrare, la, entrare, l', immettere e ottenere 3 punti, 3 punti, 3 punti, 3 punti. Vogliamo essere in grado di lista nera quella parola impostando un bool true se hai già trovato, e così è per questo che abbiamo incapsulato in questa struttura. Ora, qui in Scramble c'è questa struttura altro chiamato dizionario. Assenti qui è la parola typedef perché in questo caso abbiamo bisogno di incapsulare l'idea di un dizionario, e un dizionario contiene un sacco di parole, come sottintende questa matrice, e quante di queste parole ci sono? Beh, qualunque sia questa dimensione variabile chiamata dice. Ma abbiamo solo bisogno di un dizionario. Non abbiamo bisogno di un tipo di dati chiamato dizionario. Abbiamo solo bisogno di uno di loro, così si scopre in C che se non si dice typedef, hai appena detto struct, quindi all'interno delle parentesi graffe si mette le variabili, poi metti il ​​nome. Questo sta dichiarando un dizionario variabile chiamata che assomiglia a questo. Al contrario, queste righe sono la creazione di una struttura di dati chiamata riutilizzabile parola che è possibile creare più copie di, proprio come abbiamo creato più copie di studenti. Che cosa significa questo in ultima analisi, ci permettono di fare? Torniamo in, diciamo, un esempio più semplice da tempi più semplici, e lasciami aprire, diciamo, compare1.c. Il problema qui a portata di mano è realmente staccare lo strato di una stringa e iniziare a prendere da queste ruote di formazione perché si scopre che una stringa tutto questo tempo è come abbiamo promesso in settimana 1 in realtà solo un soprannome, un sinonimo dalla libreria CS50 per qualcosa che sembra un po 'più criptico, char *, e abbiamo visto questa stella prima. Lo abbiamo visto nel contesto dei file. Vediamo ora perché abbiamo tenuto nascosto questo dettaglio da qualche tempo. Ecco un file chiamato compare1.c, e chiede a quanto pare l'utente per 2 stringhe, s e t, e poi prova a confrontare le stringhe per l'uguaglianza in linea 26, e se sono uguali si dice: "È stato digitato la stessa cosa," e se non sono uguali si dice: "È stato digitato cose diverse." Lasciami andare avanti ed eseguire questo programma. Lasciami andare nella mia directory di origine, fare un compare1. E 'compilato bene. Vorrei correre compare1. Io lo zoom, inserire. Inserisci commento. CIAO. Dirò qualcosa di nuovo. CIAO. Io sicuramente non scrivere cose diverse. Fammi provare di nuovo. BYE BYE. Sicuramente non diverso, quindi che cosa sta succedendo qui? Ebbene, ciò che è veramente a confronto in linea 26? [Incomprensibile-studente] Sì, così si scopre che una stringa, tipo di dati, è una specie di bugia. Una stringa è un char *, ma quello che è un char *? Un char *, come si dice, è un puntatore, e un puntatore è effettivamente un indirizzo, una posizione somma in memoria, e se vi capita di aver digitato una parola come CIAO, ricordo dalle discussioni passate stringhe questo è come la parola CIAO. Ricordate che una parola come CIAO può essere rappresentato come un array di caratteri come questo e quindi con un carattere speciale alla fine chiamato il carattere nullo, come denota \. Che cosa è in realtà una stringa? Si noti che questo è più blocchi di memoria, e in effetti, la fine è noto soltanto allorché si guarda attraverso l'intera stringa cercando per il carattere speciale null. Ma se questo è un pezzo di memoria dalla memoria del mio computer, diciamo arbitrariamente dire che questa stringa semplicemente fortunato, e ha posto all'inizio della RAM del mio computer. Questo è il byte 0, 1, 2, 3, 4, 5, 6 ... Quando dico qualcosa come GetString e faccio string s = GetString cosa sta realmente restituiti? Per queste ultime settimane, ciò che sta realmente essere memorizzati in s non è questa stringa di per sé, ma in questo caso ciò che viene memorizzato è il numero 0 perché ciò che realmente fa GetString è non fisicamente restituire una stringa. Che non ha nemmeno molto senso concettuale. Ciò che fa di ritorno è un numero. Questo numero è l'indirizzo del CIAO in memoria, stringa s e quindi, se togliere questo strato, stringa in realtà non esiste. E 'solo una semplificazione nella libreria CS50. Questo è davvero qualcosa che si chiama char *. Char ha un senso, perché ciò che è una parola, come CIAO? Beh, si tratta di una serie di caratteri, una serie di caratteri. * Char significa che l'indirizzo di un personaggio, così che cosa significa per restituire una stringa? Una bella, modo semplice di restituendo una stringa è piuttosto che cercare di capire come torno a 5 o 6 byte differenti vorrei tornare al cui indirizzo byte? La prima. In altre parole, mi permetta di darle l'indirizzo di un carattere in memoria. Questo è ciò che * char rappresenta, l'indirizzo di un singolo carattere in memoria. Chiama quella variabile s. Conservare in s questo indirizzo particolare, che ho arbitrariamente detto è 0, solo per mantenere le cose semplici, ma in realtà è in genere un numero più grande. Aspetta un attimo. Se solo mi dà l'indirizzo del primo carattere, come faccio a sapere che cosa l'indirizzo è del carattere secondo, il terzo, il quarto e il quinto? [Incomprensibile-studente] Devi solo sapere dove la fine della stringa è per mezzo di questo trucco a portata di mano, in modo che quando si usa qualcosa come printf, che letteralmente printf prende come argomento, Ricordiamo che usiamo questo segnaposto% s, e poi si passa a la variabile che è la memorizzazione di una stringa. Quello che stai veramente passando è l'indirizzo del primo carattere della stringa. Printf poi usa un ciclo for o un ciclo while dopo aver ricevuto tale indirizzo, per esempio, 0, per cui vorrei farlo ora, printf ("% s \ n", s); Quando chiamo printf ("% s \ n", s); quello che sto veramente fornire con printf è l'indirizzo del primo carattere in s, che in questo caso è arbitraria H. Come fa sapere esattamente cosa printf per visualizzare sullo schermo? La persona che ha implementato printf implementato un ciclo while o un ciclo for che dice che fa questo personaggio uguale al carattere speciale null? In caso contrario, la stampa. Che ne dici di questa? Se non stampatelo, stampa, stampare, stamparla. Oh, questo è speciale. Interrompere la stampa e ritornare all'utente. E questo è letteralmente tutto quello che sta accadendo sotto il cofano, e questo è molto da digerire nel primo giorno di una classe, ma per ora è davvero il blocco di costruzione di capire tutto che sta succedendo all'interno della memoria del nostro computer, e alla fine faremo prendere in giro questa parte con un piccolo aiuto da uno dei nostri amici a Stanford. Professor Nick Parlante alla Stanford ha fatto questa sequenza meravigliosa dei video da ogni sorta di lingue diverse che hanno introdotto questo piccolo Claymation Binky carattere. La voce che state per ascoltare in un furtivo anteprima alcuni secondi è quella di un professore di Stanford, e si stanno ottenendo solo 5 o 6 secondi di questo proprio ora, ma questa è la nota su cui ci conclude oggi e iniziare il Mercoledì. Vi do Fun Pointer con Binky, l'anteprima. [♪ Musica ♪] [Professore Parlante] Ehi, Binky. Svegliati. E 'tempo per il divertimento puntatore. [Binky] Che cos'è? Ulteriori informazioni sui puntatori? Oh, goody! Ci vediamo il Mercoledì. [CS50.TV]