[Powered by Google Translate] [Recensione] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University]
>> [Questo è CS50.] [CS50.TV]
>> Ciao a tutti.
Benvenuti alla sessione recensione di Quiz 0, che si sta svolgendo questo Mercoledì.
Quello che andremo a fare questa sera, io sono con 3 TF altri,
e insieme abbiamo intenzione di passare attraverso un giudizio su ciò che abbiamo fatto nel corso finora.
Non sarà al 100% completo, ma dovrebbe darvi un'idea migliore
di ciò che già verso il basso e quello che ancora bisogno di studiare prima di Mercoledì.
E sentitevi liberi di alzare la mano con domande come stiamo andando avanti,
ma di tenere presente che avrete anche un po 'di tempo alla fine-
se vogliamo ottenere attraverso con pochi minuti di scorta per fare domande di carattere generale,
in modo da tenere a mente, e così andremo a cominciare dall'inizio con la settimana 0.
>> [Quiz 0 Commenta!] [Parte 0] [Lexi Ross] Ma prima di farlo che ti permette di parlare di
la logistica del quiz.
>> [Logistica] [Quiz si svolge il Mercoledì 10/10 in sostituzione della lezione]
>> [(Vedi http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf per i dettagli)] E 'il Mercoledì, 10 ottobre.
>> E 'questo Mercoledì, e se andate a questo URL qui,
che è anche accessibile da CS50.net-ci 's un link ad esso,
è possibile visualizzare le informazioni su dove andare in base a
il tuo cognome o affiliazione scuola, così come
si racconta esattamente ciò che il quiz coprirà e le tipologie di domande che si sta andando ad ottenere.
Tenete a mente che avrete anche la possibilità di rivedere il quiz in sezione,
in modo che le TF dovrebbe andare su alcuni problemi pratici,
e questa è un'altra buona occasione per vedere dove hai ancora bisogno di studiare per il quiz.
Cominciamo dall'inizio con Bytes Bits 'n'.
Ricorda un po 'è solo uno 0 o un 1,
ed un byte è una raccolta di 8 di questi bit.
Diamo un'occhiata a questa raccolta di bit proprio qui.
Dovremmo essere in grado di capire quanti bit ci sono.
Dove contiamo c'è solo 8 di loro, otto 0 o 1 unità.
E poiché ci sono 8 bit, questo è 1 byte,
e cerchiamo di convertirlo in esadecimale.
Esadecimale è base 16, ed è abbastanza facile da convertire
in un numero binario, che è ciò che è, ad un numero esadecimale.
Tutto quello che facciamo è guardare a gruppi di 4,
e li converte alla cifra esadecimale appropriato.
Si comincia con il più a destra un gruppo di 4, quindi 0011.
Che sta per essere un 1 e un 2, così insieme che fa 3.
E poi guardiamo l'altro blocco di 4.
1101. Che sta per essere un 1, un 4 e un 8.
Insieme che sta per essere di 13, il che rende D.
E ci ricorda che in esadecimale non ci limitiamo a passare da 0 a 9.
Andiamo da 0 a F, così dopo 9, 10 corrisponde a A,
11 a B, et cetera dove F è 15.
Qui 13 è un D,
in modo da convertirlo in decimale tutto ciò che facciamo è in realtà
trattare ogni posizione di una potenza di 2.
Questo è un 1, un 2, zero 4s, zero 8s, uno 16, et cetera,
ed è un po 'difficile da calcolare nella tua testa, ma se andiamo alla diapositiva successiva
siamo in grado di vedere la risposta a questo.
>> In sostanza stiamo andando di fronte a destra di nuovo a sinistra,
e stiamo moltiplicando ogni cifra per la potenza di 2 corrispondente.
E ricordate, per esadecimale indichiamo questi numeri con 0x all'inizio
in modo da non confondere con un numero decimale.
Proseguendo, si tratta di una tabella ASCII,
e quello che usiamo per ASCII è quello di mappare dai caratteri ai valori numerici.
Ricordate nel pset crittografia abbiamo fatto ampio uso della tabella ASCII
al fine di utilizzare vari metodi di crittografia,
il Cesare e il cifrario di Vigenère, per convertire le lettere diverse
in una stringa secondo la chiave fornita dall'utente.
Diamo un'occhiata a un po 'di matematica ASCII.
Guardando 'P' + 1, in forma di carattere che sarebbe Q,
e ricordate che '5 '≠ 5.
E come esattamente dovremmo convertire tra queste 2 forme?
Non è davvero troppo difficile.
Al fine di ottenere 5 sottraiamo '0 '
perché ci sono 5 posti tra '0 'e il '5'.
Al fine di andare nella direzione opposta basta aggiungere lo 0,
quindi è un po 'come l'aritmetica normale.
Basta ricordare che quando qualcosa ha virgolette intorno è un personaggio
e corrisponde quindi a un valore nella tabella ASCII.
Trasferirsi in argomenti riguardanti i computer più generali della scienza.
Abbiamo imparato che cosa è un algoritmo e come utilizzare la programmazione
per implementare algoritmi.
Alcuni esempi di algoritmi sono qualcosa di veramente semplice come
verificare se un numero è pari o dispari.
Per questo ricordo che mod il numero per 2 e verificare se il risultato è 0.
Se è così, è ancora. In caso contrario, è strano.
E questo è un esempio di un algoritmo molto di base.
>> Un po 'di uno più coinvolto è ricerca binaria,
quale ci occuperemo più avanti nella sessione di revisione.
E la programmazione è il termine che usiamo per prendere un algoritmo
e la conversione di codificare il computer può leggere.
2 esempi di programmazione Scratch,
che è quello che abbiamo fatto in settimana 0.
Anche se in realtà non digitare il codice è uno strumento di attuazione
questo algoritmo, che sta stampando i numeri 1-10,
e qui noi facciamo lo stesso nel linguaggio di programmazione C.
Questi sono funzionalmente equivalenti, appena scritto in diverse lingue o di sintassi.
Abbiamo poi imparato a conoscere le espressioni booleane,
e un valore booleano è un valore che è true o false,
ed espressioni booleane qui spesso
andare all'interno di condizioni, quindi se (x ≤ 5),
bene, abbiamo già fissato x = 5, in modo che la condizione sta per restituiscono true.
E se è vero, tutto ciò che il codice è sotto la condizione
sarà valutata dal computer, in modo tale stringa sta per essere stampato
sullo standard output, e la condizione di termine
si riferisce a tutto ciò che è all'interno delle parentesi l'istruzione if.
Ricordati di tutti gli operatori.
Ricordatevi che è && e | | quando stiamo cercando di combinare 2 o più condizioni,
== = Non per verificare se 2 cose sono uguali.
Ricordate che è = per l'assegnazione, mentre == è un operatore booleano.
≤, ≥ e quindi gli ultimi 2 sono auto-esplicativi.
Un riesame generale di logica booleana qui.
E le espressioni booleane sono importanti anche in loop,
che andremo finita.
Abbiamo imparato circa 3 tipi di cicli finora in CS50, for, while e do while.
Ed è importante sapere che, mentre per la maggior parte degli scopi
si può effettivamente utilizzare qualsiasi tipo di loop in generale
ci sono alcuni tipi di scopi o modelli comuni
in programmazione che specificamente richiedono una di queste anse
che lo rendono il più efficiente o elegante per il codice in questo modo.
Andiamo su ciò che ciascuno di questi cicli tende ad essere utilizzato per la maggior parte spesso.
>> In un ciclo for che generalmente già sappiamo quante volte si vuole iterare.
Questo è quello che abbiamo messo nella condizione.
Per, i = 0, i <10, per esempio.
Sappiamo già che vogliamo fare qualcosa di 10 volte.
Ora, per un ciclo while, in genere non necessariamente
sai quante volte vogliamo che il ciclo per l'esecuzione.
Ma sappiamo una sorta di condizione che noi vogliamo che
sempre vera o sempre falsa.
Per esempio, mentre è impostato.
Diciamo che è una variabile booleana.
Anche se è vero che vogliamo il codice di valutare,
quindi un po 'più estensibile, un po' più generale di un ciclo for,
ma per ogni ciclo può anche essere convertito in un ciclo while.
Infine, do while, che possono essere più difficile di comprendere subito,
sono spesso utilizzati quando si vuole valutare il primo codice
prima che la prima volta che si controlla la condizione.
Un caso d'uso comune per un do while
è quando si desidera ottenere l'input dell'utente, e si sa che si desidera chiedere all'utente
per l'ingresso almeno una volta, ma se non ti danno input validi subito
si desidera continuare a chiedere loro fino a quando ti danno l'input bene.
Questo è l'uso più comune di un ciclo Do While,
e guardiamo l'attuale struttura di questi cicli.
Di norma, tendono sempre a seguire questi modelli.
>> Il ciclo per la parte interna si dispone di 3 componenti:
inizializzazione, di solito qualcosa come int i = 0 dove i è il contatore,
condizione, in cui vogliamo dire eseguire questo ciclo for finché questa condizione ancora tiene,
come i <10, e poi finalmente, l'aggiornamento, che è il modo in cui incrementare
la variabile contatore in ogni punto del circuito.
Una cosa comune vedere c'è solo i + +,
che significa incrementare i di 1 ogni volta.
Si potrebbe anche fare qualcosa di simile i + = 2,
il che significa aggiungere 2 per i ogni volta che si passa attraverso il ciclo.
E poi il fare questo si riferisce solo a qualsiasi codice che viene eseguito in realtà come parte del ciclo.
E per un ciclo while, questa volta in realtà abbiamo l'inizializzazione al di fuori del ciclo,
così per esempio, diciamo che stiamo cercando di fare lo stesso tipo di ciclo, come ho appena descritto.
Diremmo int i = 0 prima dell'inizio del ciclo.
Allora potremmo dire, mentre i <10 fare questo,
così lo stesso blocco di codice come prima,
e questa volta la parte di aggiornamento del codice, per esempio, i + +,
va effettivamente all'interno del loop.
E, infine, per un do while, è simile al ciclo while,
ma dobbiamo ricordare che il codice valuterà una volta
prima che la condizione è verificata, quindi ha molto più senso
se la si guarda in ordine di cima a fondo.
In un ciclo Do While il codice di valuta prima ancora di guardare la condizione, mentre,
considerando che un ciclo while, verifica prima.
Le dichiarazioni e le variabili.
Quando si vuole creare una nuova variabile che vuole prima di inizializzarlo.
>> Per esempio, bar int inizializza la barra variabile,
ma non le conferisce un valore, quindi qual è il valore bar adesso?
Non lo sappiamo.
Potrebbe essere qualche valore spazzatura che è stato precedentemente memorizzato lì,
e non si desidera utilizzare tale variabile
fino a quando in realtà dare un valore,
così abbiamo dichiariamo qui.
Poi inizializzarlo ad essere 42.
Ora, naturalmente, sappiamo che questo può essere fatto in una sola riga, int = 42 bar.
Ma proprio per cancellare essere le più passaggi che sono in corso,
la dichiarazione e l'inizializzazione si stanno verificando separatamente qui.
Succede a un passo, e la prossima, int baz = bar + 1,
questa dichiarazione seguente, che baz incrementi, così, alla fine di questo blocco di codice
se dovessimo stampare il valore di baz sarebbe 44
perché dichiarare e inizializzare di essere 1 bar>,
e poi incrementarlo ancora una volta con i tasti + +.
Siamo andati oltre questo breve abbastanza, ma è bene avere un generale
comprensione di ciò che le discussioni e gli eventi sono.
Abbiamo soprattutto fatto in Scratch,
in modo da poter pensare di thread come sequenze multiple di codice
esecuzione contemporaneamente.
In realtà, probabilmente non è in esecuzione al tempo stesso,
ma una sorta di astratto possiamo pensare in quel modo.
>> In Scratch, ad esempio, abbiamo avuto i più sprite.
Si potrebbe eseguire codice diverso allo stesso tempo.
Si potrebbe essere a piedi, mentre l'altro sta dicendo qualcosa
in un'altra parte dello schermo.
Gli eventi sono un altro modo di separare la logica
tra i diversi elementi del codice,
e in Scratch siamo stati in grado di simulare gli eventi utilizzando il Broadcast,
e che in realtà quando ricevo, non quando sento,
ma essenzialmente è un modo per trasmettere informazioni
da uno sprite a un altro.
Ad esempio, si può decidere di trasmettere game over,
e quando un altro sprite riceve game over,
risponde in un certo modo.
Si tratta di un modello importante per capire per la programmazione.
Giusto per andare oltre la settimana di base 0, quello che abbiamo superato finora,
diamo un'occhiata a questo programma in C semplice.
Il testo può essere un po 'piccola da qui, ma io vado su di esso molto veloce.
Siamo tra 2 file di intestazione in alto, cs50.h e stdio.h.
Siamo quindi definire un limite costante chiamata ad essere 100.
Stiamo quindi implementare la nostra funzione principale.
Dal momento che non utilizzare gli argomenti della riga di comando qui abbiamo bisogno di mettere nulla
come gli argomenti per principale.
Vediamo int sopra principale. Questo è il tipo di ritorno, quindi restituire 0 in fondo.
E stiamo usando CS50 funzione di libreria ottenere int
chiedere all'utente per l'input, e conservarla in questa variabile x,
in modo da dichiarare x sopra, e lo inizializza con x = GetInt.
>> Abbiamo poi verificare se l'utente ci ha dato input validi.
Se è LIMITE ≥ vogliamo restituire un codice di errore di 1 e un messaggio di errore.
E, infine, se l'utente ci ha dato input validi
stiamo andando a quadrare il numero e stampare tale risultato.
Giusto per fare in modo che coloro che tutti colpiti a casa
è possibile vedere le etichette di diverse parti del codice qui.
Ho accennato costanti, file di intestazione.
Oh, int x. Assicurati di ricordare che è una variabile locale.
Che contrasta da una variabile globale, che parleremo
un po 'più tardi nella sessione di revisione,
e stiamo chiamando la funzione di libreria printf,
quindi se non avessimo incluso il file di intestazione stdio.h
non saremmo in grado di chiamare printf.
E credo che la freccia che ha tagliato fuori qui si punta al% d,
che è una stringa di formattazione di printf.
Si dice di stampare questa variabile come d% un numero,.
E questo è per la Settimana 0.
Ora Lucas è destinata a continuare.
Ehi, ragazzi. Il mio nome è Lucas.
Sono al secondo anno nel migliore casa nel campus, Mather,
e ho intenzione di parlare un po 'di settimana 1 e 2.1.
[Settimana 1 e 2.1!] [Lucas Freitas]
Come Lexi diceva, quando abbiamo iniziato a tradurre il codice da zero in C
una delle cose che abbiamo notato è che non si può semplicemente
scrivere il codice ed eseguirlo con una bandiera verde più.
In realtà, è necessario utilizzare alcuni passi per rendere il vostro programma C
diventare un file eseguibile.
Fondamentalmente quello che si fa quando si sta scrivendo un programma che è
di tradurre la vostra idea in un linguaggio che un compilatore in grado di capire,
così quando si sta scrivendo un programma in C
quello che stai facendo è in realtà scrivere qualcosa che il compilatore sta per capire,
e poi il compilatore sta per tradurre il codice
in qualcosa che il computer capirà.
>> E la cosa è, il computer è in realtà molto stupido.
Il computer può comprendere solo 0 e 1,
quindi in realtà i primi computer la gente di solito programmato
con 0 e 1, ma ora non più, grazie a Dio.
Non c'è bisogno di memorizzare le sequenze di 0 e 1
per un ciclo for o per un ciclo while e così via.
Questo è il motivo per cui abbiamo un compilatore.
Che cosa fa è un compilatore traduce fondamentalmente il codice C,
nel nostro caso, di un linguaggio che il computer capirà,
che è il codice oggetto, e il compilatore che stiamo usando
si chiama clang, quindi questo è in realtà il simbolo per fragore.
Quando hai il tuo programma, devi fare 2 cose.
In primo luogo, è necessario compilare il programma, e poi avete intenzione di eseguire il programma.
Per compilare il programma si ha un sacco di opzioni per farlo.
Il primo è quello di fare program.c clang
in cui il programma è il nome del programma.
In questo caso si può vedere che stanno solo dicendo "Hey, compilare il mio programma".
Non stai dicendo "voglio questo nome per il mio programma" o qualcosa.
>> La seconda opzione è dare un nome al vostro programma.
Si può dire clang-o e poi il nome che si desidera
il file eseguibile per essere nominato e poi program.c.
E si può anche fare il programma make, e vedere come nei primi 2 casi
Ho messo. C, e nel terzo ho solo programmi?
Si ', in realtà non dovrebbe mettere. C quando si utilizza fare.
In caso contrario, il compilatore è in realtà sta per urlare contro di voi.
E anche, non so se voi ragazzi ricordate,
ma un sacco di volte abbiamo usato anche lcs50-o-LM.
Che è chiamato collegamento.
Si dice solo il compilatore che si intende utilizzare quelle librerie proprio lì,
quindi se si desidera utilizzare cs50.h effettivamente necessario digitare
clang program.c-lcs50.
Se non lo facciamo, il compilatore non ha intenzione di conoscere
che si sta utilizzando queste funzioni in cs50.h.
E quando si desidera eseguire il programma si hanno 2 opzioni.
Se avete fatto program.c clang che non ha dato un nome al programma.
Si deve eseguire usando. / A.out.
A.out è un nome standard che clang restituisce il programma se non dargli un nome.
In caso contrario, si sta andando a fare. / Programma, se ti ha dato un nome al programma,
e anche se avete fatto fare il nome del programma che un programma sta per arrivare
è già in corso da programmare lo stesso nome del file c.
Poi abbiamo parlato di tipi di dati e di dati.
>> Fondamentalmente i tipi di dati sono la stessa cosa, come piccole scatole che utilizzano
per memorizzare i valori, quindi i tipi di dati sono in realtà proprio come Pokemon.
Essi sono disponibili in tutte le dimensioni e tipologie.
Non so se questa analogia ha un senso.
La dimensione dei dati in realtà dipende l'architettura della macchina.
Tutti i formati di dati che ho intenzione di mostrare qui
sono in realtà una macchina a 32 bit, che è il caso del nostro apparecchio,
ma se in realtà si sta scrivere il vostro Mac o in un ambiente Windows anche
probabilmente si sta andando ad avere un computer a 64 bit,
in modo da ricordare che le dimensioni dei dati che ho intenzione di mostrare qui
sono per il 32-bit.
Il primo che abbiamo visto era un int,
che è abbastanza semplice.
È utilizzare int per memorizzare un numero intero.
Abbiamo anche visto il carattere, il carattere.
Se si desidera utilizzare una lettera o un piccolo simbolo probabilmente stai andando ad utilizzare un char.
Un char è 1 byte, il che significa 8 bit, come Lexi ha detto.
In pratica abbiamo una tabella ASCII che dispone di 256
possibili combinazioni di 0 e 1,
e poi quando si digita un carattere che sta per tradurre
il carattere che gli ingressi voi un numero che si ha nella tabella ASCII, come Lexi ha detto.
Abbiamo anche il galleggiante, che si usa per memorizzare i numeri decimali.
Se si desidera scegliere 3.14, per esempio, si sta andando ad utilizzare un galleggiante
o un doppio che ha più precisione.
Un galleggiante dispone di 4 byte.
Un doppio ha 8 byte, quindi l'unica differenza è la precisione.
Abbiamo anche una lunga che viene utilizzato per gli interi,
e si può vedere una macchina a 32 bit di un int e un lungo hanno la stessa dimensione,
quindi non ha molto senso usare un lungo in un computer a 32 bit.
>> Ma se si sta utilizzando un computer Mac e 64-bit, in realtà una lunga ha dimensione 8,
in modo che in realtà dipende l'architettura.
Per la macchina a 32 bit non ha senso usare una lunga davvero.
E quindi un lungo tempo, invece, ha 8 byte,
quindi è molto buona se si vuole avere un maggiore numero intero.
E, infine, abbiamo stringa, che in realtà è un char *,
che è un puntatore ad un char.
E 'molto facile pensare che la dimensione della stringa sta per essere come
il numero di caratteri che hai lì,
ma in realtà la stessa char *
ha la dimensione di un puntatore ad un char, che è 4 byte.
La dimensione di un char * è di 4 byte.
Non importa se si dispone di una piccola parola o una lettera o altro.
E 'intenzione di essere di 4 byte.
Abbiamo anche imparato un po 'di getto,
così come si può vedere, se si ha, ad esempio, un programma che dice
int x = 3 e poi printf ("% d", x / 2)
non sapete cosa sta andando per la stampa su schermo?
>> Qualcuno? >> [Gli studenti] 2.
1. >> 1, si '.
Quando si fare 3/2, sta per arrivare 1.5,
ma dal momento che stiamo usando un intero sta andando a ignorare la parte decimale,
e si sta andando ad avere 1.
Se non vogliamo che ciò accada ciò che si può fare, ad esempio,
si dichiara un float y = x.
Poi x che un tempo 3 è ora sta per essere 3.000 in y.
E poi si può stampare il y / 2.
A dire il vero, dovrei avere un 2. laggiù.
E 'intenzione di fare 3.00/2.00,
e si sta andando ad ottenere 1.5.
E abbiamo questa .2 f solo per chiedere per 2 unità decimali nella parte decimale.
Se si dispone di 0,3 f che sta per avere effettivamente 1.500.
Se è 2 si sarà 1.50.
Abbiamo anche questo caso.
Se lo fai float x = 3.14 e quindi si x printf
si sta andando ad ottenere 3.14.
E se lo fai x = int x,
il che significa che trattano x come un int e si stampa x ora
si sta andando ad avere 3.00.
Ha senso?
Perché sei prima trattando x come un intero, in modo che stai ignorando la parte decimale,
e poi si sta stampando x.
E, infine, si può anche fare questo,
int x = 65, e quindi si dichiara un char c = x,
e poi se si stampa il c si sta effettivamente andando ottenere
A, quindi fondamentalmente quello che stai facendo qui
sta traducendo il numero intero nel personaggio,
proprio come la tabella ASCII fa.
Abbiamo anche parlato di operatori matematici.
La maggior parte di loro sono piuttosto semplici, in modo da +, -, *, /,
e anche abbiamo parlato di mod, che è il resto di una divisione di 2 numeri.
Se si dispone di 10% 3, per esempio,
significa dividere 10 per 3, e ciò che è il resto?
E 'intenzione di essere 1, quindi in realtà è molto utile per un sacco di programmi.
Per Vigenère e Cesare sono abbastanza sicuro che tutti voi ragazzi usato mod.
Informazioni sugli operatori matematici, essere molto attenti quando si combinano * e /.
>> Ad esempio, se si fa (3/2) * 2 cosa hai intenzione di ottenere?
[Gli studenti] 2.
Si ', 2, in quanto 3/2 è sta per essere 1.5,
ma dal momento che si sta facendo le operazioni tra 2 numeri interi
si sta effettivamente solo andando a prendere in considerazione 1,
e quindi 1 * 2 sta per essere 2, in modo da essere molto, molto attenti
quando fare calcoli con numeri interi, perché
si potrebbe ottenere che 2 = 3, in questo caso.
E anche stare molto attenti a precedenza.
Di solito si deve utilizzare le parentesi per essere sicuri di sapere cosa si sta facendo.
Collegamenti utili, naturalmente, si è i + + o + i = 1
o usando + =.
Questa è la stessa cosa che i = i + 1.
È anche possibile che faccio - o i - = 1,
che è la stessa cosa che i = i -1,
qualcosa voi ragazzi l'uso molto in cicli for, almeno.
Inoltre, per *, se si utilizza * = e se lo fai, per esempio,
i * = 2 è la stessa cosa che dire i = i * 2,
e la stessa cosa per la divisione.
Se fate i / = 2 è la stessa cosa che i = i / 2.
>> Ora sulle funzioni.
Voi ragazzi imparato che le funzioni sono una buona strategia per salvare il codice
mentre si sta programmando, quindi se si desidera eseguire lo stesso compito
nel codice più e più volte, probabilmente si desidera utilizzare una funzione
solo così non c'è bisogno di copiare e incollare il codice più e più volte.
In realtà, è una funzione principale, e quando vi mostro il formato di una funzione
si sta andando a vedere che questo è abbastanza evidente.
Usiamo anche le funzioni di alcune librerie,
per esempio, printf, Getin, che è dalla biblioteca CS50,
e altre funzioni come toupper.
Tutte queste funzioni sono effettivamente attuate in altre biblioteche,
e quando si mette quei file legano all'inizio del programma
stai dicendo che si può per favore darmi il codice per le funzioni
quindi non c'è bisogno di attuarle da solo?
E si può anche scrivere le proprie funzioni, in modo che quando si avvia la programmazione
ci si rende conto che le biblioteche non hanno tutte le funzioni di cui avete bisogno.
Per l'pset scorso, per esempio, abbiamo scritto disegnare, corsa, e di ricerca,
ed è molto, molto importante essere in grado di scrivere le funzioni
perché sono utili, e li usiamo per tutto il tempo nella programmazione,
e fa risparmiare un sacco di codice.
Il formato di una funzione è questa.
Abbiamo tipo di ritorno all'inizio. Qual è il tipo di ritorno?
E 'solo quando la funzione sta per tornare.
Se si dispone di una funzione, ad esempio, fattoriale,
che sta per calcolare un fattoriale di un numero intero,
probabilmente sta andando a restituire un numero intero anche.
Poi il tipo di ritorno sarà int.
Printf ha in realtà un vuoto tipo di ritorno
perché non sei niente di ritorno.
Stai solo stampando le cose sullo schermo
e uscire dalla funzione in seguito.
Poi ci sono il nome della funzione che si può scegliere.
Si dovrebbe essere un po 'ragionevole, come non scegliere un nome come xyz
o come X2F.
Provate a fare un nome che abbia un senso.
>> Ad esempio, se si tratta di fattoriale, dicono fattoriale.
Se si tratta di una funzione che sta per disegnare qualcosa, il nome disegnare.
E poi ci sono i parametri, che sono anche chiamati argomenti,
che sono come le risorse che la funzione ha bisogno
dal codice per eseguire il suo compito.
Se si vuole calcolare il fattoriale di un numero
probabilmente è necessario disporre di un numero per calcolare un fattoriale.
Uno degli argomenti che si sta andando ad avere è il numero stesso.
E poi va a fare qualcosa e restituire il valore alla fine
meno che non sia una funzione void.
Vediamo un esempio.
Se voglio scrivere una funzione che somma tutti i numeri in un array di interi,
prima di tutto, il tipo di ritorno sarà int
perché ho un array di interi.
E poi ho intenzione di avere il nome della funzione come sumArray,
e poi sta andando a prendere la matrice stessa, a nums int,
e poi la lunghezza della matrice quindi so quanti numeri devo sommare.
Poi devo inizializzare una somma variabile chiamata, per esempio, a 0,
e ogni volta che vedo un elemento dell'array devo aggiungere alla somma, così ho fatto un ciclo for.
Proprio come Lexi ha detto, si fa int i = 0, i lunghezza <i + +.
E per ogni elemento della matrice che ho fatto somma + = nums [i],
e poi ho restituito la somma, quindi è molto semplice, e fa risparmiare un sacco di codice
se si sta utilizzando questa funzione un sacco di volte.
Poi abbiamo preso uno sguardo a condizioni.
Abbiamo if, else e else if.
Vediamo qual è la differenza tra quelli.
Date un'occhiata a questi 2 codici. Qual è la differenza tra loro?
Il primo è, in fondo i codici che tu dica
se un numero è +, -, o 0.
Il primo dice se è> 0 allora è positivo.
Se è = a 0 allora è 0, e se è <0 allora è negativo.
>> E l'altro sta facendo if, else if, else.
La differenza tra i due è che questo è effettivamente andando
controllare se> 0, <0 = 0 o tre volte,
quindi se avete il numero 2, per esempio, che sta per venire qui e dire:
if (x> 0), e che sta per dire di sì, così mi stampa positiva.
Ma anche se so che è> 0 e non sarà 0 o <0
Sto ancora intenzione di fare è 0, è <0,
quindi sto effettivamente andando dentro di se e che non c'era bisogno di
perché so già che non sta andando a soddisfare una delle seguenti condizioni.
Posso usare il se, else if, else.
Dice in fondo se x = 0 stampare il positivo.
Se non lo è, ho intenzione di provare anche questo.
Se è 2 non ho intenzione di farlo.
In pratica se avessi x = 2 si direbbe
if (x> 0), sì, così stampare questa.
Ora che so che è> 0 e che ha soddisfatto il primo, se
Non ho nemmeno intenzione di eseguire questo codice.
Il codice è più veloce, in realtà, 3 volte più veloce se si utilizza questo.
Abbiamo anche imparato a conoscere e ed o.
Non ho intenzione di passare attraverso questo perché Lexi già parlato di loro.
E 'solo i && e | operator |.
>> L'unica cosa che dirò è stare attenti quando si hanno 3 condizioni.
Utilizzare le parentesi perché è molto confusa quando si ha una condizione
e un altro o un altro.
Utilizzare le parentesi solo per essere sicuri che le vostre condizioni di dare un senso
perché in tal caso, ad esempio, si può immaginare che
potrebbe essere la prima condizione e l'una o l'altra
o le 2 condizioni combinati in e
o il terzo, quindi basta stare attenti.
E, infine, abbiamo parlato di switch.
Un interruttore è molto utile quando si dispone di una variabile.
Diciamo che hai una variabile come n
che può essere 0, 1 o 2, e per ciascuno di questi casi
si sta andando a eseguire un compito.
Si può dire cambiare la variabile, e indica che
il valore è quindi come value1 ho intenzione di fare questo,
e poi mi rompo, il che significa che non ho intenzione di guardare uno qualsiasi degli altri casi
perché abbiamo già soddisfatto questo caso
e poi valore2 e così via, e può anche avere un interruttore predefinito.
Questo significa che se non soddisfa nessuno dei casi che ho avuto
che ho intenzione di fare qualcosa di diverso, ma questo è facoltativo.
Questo è tutto per me. Ora andiamo a Tommy.
Va bene, questo sarà settimana 3-ish.
Questi sono alcuni dei temi che tratteremo, crypto, campo di applicazione, gli array, et cetera.
Solo una breve parola sulla crittografia. Non stiamo andando a battere questa casa.
>> Lo abbiamo fatto in pset 2, ma per il quiz assicurarsi di sapere la differenza
tra il cifrario di Cesare e il cifrario Vigenère,
come sia di quelli di lavoro cifre e cosa vuol dire per crittografare
e decifrare il testo utilizzando questi 2 cifre.
Ricorda, il cifrario di Cesare semplicemente ruota ogni carattere per lo stesso importo,
avendo cura di mod per il numero di lettere dell'alfabeto.
E il cifrario Vigenère, invece, ruota ogni carattere
da un importo diverso, quindi, invece di dire
ogni rotazione di caratteri del 3 Vigenère ruoterà ogni carattere
di una quantità diversa a seconda qualche parola
dove ogni lettera la parola chiave rappresenta una certa quantità differente
per ruotare il testo chiaro.
Parliamo innanzitutto sulla portata variabile.
Ci sono 2 tipi diversi di variabili.
Abbiamo variabili locali, e questi saranno definiti
al di fuori della principale o fuori di ogni funzione o blocco,
e questi saranno accessibili in qualsiasi punto del programma.
Se si dispone di una funzione e in tale funzione è un ciclo while
la grande variabile globale è accessibile ovunque.
Una variabile locale, invece, è nell'ambito del luogo in cui è definita.
>> Se si dispone di una funzione di qui, per esempio, abbiamo questa funzione g,
e all'interno di g è una variabile denominata qui y,
e ciò significa che si tratta di una variabile locale.
Anche se questa variabile si chiama y
e questa variabile si chiama y queste 2 funzioni
non hanno idea di ciò che le variabili locali di ciascuno sono.
D'altra parte, qui diciamo int x = 5,
e questo è fuori della portata di qualsiasi funzione.
E 'al di fuori del campo di applicazione principale, quindi questa è una variabile globale.
Ciò significa che all'interno di queste 2 funzioni quando dico x - x + o +
Sto x l'accesso alla stessa in base al quale questo e questo y y sono variabili diverse.
Questa è la differenza tra una variabile globale e una variabile locale.
Per quanto riguarda il design è interessato, a volte è probabilmente una migliore idea
per mantenere le variabili locali ogni volta che il possibile
dal momento che avere un gruppo di variabili globali può ottenere davvero confuso.
Se hai un po 'di tutte le funzioni modificare la stessa cosa
si può dimenticare ciò che se questa funzione modifica accidentalmente questo mondiale,
e questa funzione altro non può sapere nulla,
e lo fa ottenere abbastanza confuso come si ottiene più codice.
Mantenere le variabili locali ogni volta che il possibile
è il design solo buono.
Array, ricordate, sono semplicemente liste di elementi dello stesso tipo.
All'interno di CI non può avere un elenco come 1, 2.0, ciao.
Noi non possiamo farlo.
>> Quando si dichiara una matrice in C tutti gli elementi devono essere dello stesso tipo.
Qui ho un array di 3 interi.
Qui ho la lunghezza della matrice, ma se sto solo dichiarare in questa sintassi
dove specificare tutti gli elementi che non sono tecnicamente bisogno di questo 3.
Il compilatore è abbastanza intelligente da capire quanto è grande l'array dovrebbe essere.
Ora, quando voglio ottenere o impostare il valore di un array
questa è la sintassi per farlo.
Questo effettivamente modificare il secondo elemento della matrice perché, ricordate,
numerazione parte da 0, non da 1.
Se voglio leggere quel valore che posso dire qualcosa di simile int x = array [1].
Oppure, se voglio impostare tale valore, come sto facendo qui,
Posso dire array [1] = 4.
Quella volta l'accesso a elementi dal loro indice
o loro posizione o quando sono nella matrice,
e che la quotazione parte da 0.
Possiamo anche avere array di array,
e questo si chiama un array multi-dimensionale.
Quando abbiamo un array multi-dimensionale
questo significa che può avere qualcosa di simile a righe e colonne,
e questo è solo un modo di visualizzare questo o di pensarci.
Quando ho un array multi-dimensionale che significa che ho intenzione di iniziare a dover
più di 1 indice perché se ho una griglia
solo dicendo quello che sei in fila non ci dà un numero.
Questo è in realtà solo ci darà una lista di numeri.
Diciamo che ho questo array qui.
Ho un array denominato griglia, e io sto dicendo che è 2 righe e 3 colonne,
e quindi questo è un modo di visualizzarlo.
Quando dico che voglio ottenere l'elemento in [1] [2]
ciò significa che, poiché si tratta di righe e poi le colonne
Ho intenzione di passare alla riga 1 da quando ho detto 1.
>> Poi ho intenzione di venire qui a colonna 2, e ho intenzione di ottenere il valore 6.
Fai senso?
Array multidimensionali, ricordiamo, sono tecnicamente solo un array di array.
Possiamo avere array di array di array.
Siamo in grado di andare avanti, ma in realtà un modo di pensare
come questo è organizzato e quello che sta succedendo è quello di visualizzarlo
in una griglia come questo.
Quando si passa di array a funzioni, che stanno andando a comportarsi
un po 'diverso rispetto a quando si passa alle funzioni variabili regolari
come passare un int o un float.
Quando si passa in un tipo int o char o uno qualsiasi di questi altri dati
abbiamo appena preso uno sguardo se la funzione modifica
il valore di tale variabile che il cambiamento non sta per propagare fino
alla funzione chiamante.
Con un array, invece, che avverrà.
Se passo in un array ad una funzione e che funzione cambia alcuni elementi,
quando torno fino alla funzione che l'ha chiamata
il mio array è ora di andare a essere diverso, e il vocabolario di tale
è array sono passati per riferimento, come vedremo più avanti.
Questo è legato al modo in cui il lavoro puntatori, dove questi tipi di dati di base,
d'altra parte, sono passati per valore.
>> Si può pensare a questo come fare una copia di una variabile e poi passare nella copia.
Non importa ciò che facciamo con quella variabile.
La funzione chiamante non saranno consapevoli del fatto che è stato cambiato.
Gli array sono solo un po 'diverso al riguardo.
Per esempio, come abbiamo appena visto, principale è semplicemente una funzione
che può prendere in 2 argomenti.
Il primo argomento della funzione principale è argc, o il numero di argomenti,
e il secondo argomento è chiamato argv,
e questi sono i valori effettivi di tali argomenti.
Diciamo che ho un programma chiamato this.c,
e lo dico fare questo, e ho intenzione di eseguire questo nella riga di comando.
Ora per passare alcuni argomenti al mio programma che si chiama questo,
Potrei dire una cosa del genere. / Questa è la cs 50.
Questo è ciò che immaginiamo David a fare tutti i giorni presso il terminale.
Ma ora l'interno funzione principale di tale programma
ha questi valori, quindi argc è 4.
Potrebbe essere un po 'di confusione perché in realtà siamo solo di passaggio in è cs 50.
Questo è solo 3.
Ma ricordate che il primo elemento di argv o il primo argomento
è il nome della funzione stessa.
Quindi questo significa che ci sono 4 cose qui,
e il primo elemento sarà. / questo.
E questo sarà rappresentato come una stringa.
Poi i restanti elementi sono ciò che digitato dopo il nome del programma.
Così come una parte, come abbiamo probabilmente visto in pset 2,
ricordare che la stringa 50 è il numero intero ≠ 50.
Quindi non si può dire una cosa del genere, 'int x = argv 3.'
>> Ma non è solo andare a dare un senso, perché questa è una stringa, e questo è un numero intero.
Quindi, se si desidera convertire tra i 2, ricordate, stiamo andando a
hanno questa funzione magica chiamata atoi.
Che prende una stringa e restituisce il numero intero rappresentato all'interno di quella stringa.
Ecco, questo è un errore facile da fare il quiz,
solo pensare che questo sarà automaticamente il tipo corretto.
Ma è sufficiente sapere che questi saranno sempre essere stringhe
anche se la stringa contiene solo un numero intero o un personaggio o di un galleggiante.
Così ora parliamo di tempo di esecuzione.
Quando abbiamo tutti questi algoritmi che fanno tutte queste cose folli,
diventa davvero utile a porre la domanda: "Quanto tempo hanno preso?"
Noi rappresentiamo che con qualcosa chiamato notazione asintotica.
Quindi questo significa che - beh, diciamo che diamo il nostro algoritmo
alcuni input davvero, davvero, davvero grande.
Vogliamo fare la domanda, "quanto tempo ci vorrà?
Quante misure intende prendere il nostro algoritmo per l'esecuzione
in funzione della dimensione dell'input? "
Quindi il primo modo possiamo descrivere fase di esecuzione è con grande O.
E questo è il nostro caso peggiore tempo di esecuzione.
Quindi, se si desidera ordinare un array, e diamo il nostro algoritmo di un array
che è in ordine decrescente, mentre dovrebbe essere in ordine crescente,
che sta per essere il caso peggiore.
Questo è il nostro limite superiore della lunghezza massima di tempo nostro algoritmo avrà.
D'altra parte, questa Ω sta per descrivere caso migliore tempo di esecuzione.
Quindi, se diamo un array già ordinati ad un algoritmo di ordinamento,
quanto tempo ci vorrà per risolvere la cosa?
E questo, poi, descrive un limite inferiore sul tempo di esecuzione.
Così qui sono solo alcune parole che descrivono alcuni momenti comuni di funzionamento.
Questi sono in ordine crescente.
Il tempo di esecuzione più veloce che abbiamo si chiama costante.
>> Ciò significa che non importa quanti elementi diamo il nostro algoritmo,
non importa quanto grande è la nostra gamma, smistamento
o fare tutto ciò che stiamo facendo per l'array avrà sempre la stessa quantità di tempo.
Quindi possiamo rappresentare che solo con un 1, che è una costante.
Abbiamo anche guardato in fase di esecuzione logaritmico.
Quindi, qualcosa come la ricerca binaria è logaritmica,
dove tagliare il problema a metà ogni volta
e poi le cose solo ottenere più da lì.
E se si sta scrivendo un mai O di qualsiasi algoritmo fattoriale,
probabilmente non dovrebbe considerare questo come il vostro lavoro di giorno.
Quando confrontiamo tempi di esecuzione è importante tenere a mente queste cose.
Quindi, se ho un algoritmo che è O (n), e qualcun altro
è un algoritmo di O (2n) questi sono realmente asintoticamente equivalenti.
Quindi, se immaginiamo di n per essere un numero grande come eleventy miliardi di euro:
così quando stiamo confrontando eleventy miliardi a qualcosa di simile eleventy miliardi + 3,
improvvisamente che tre in realtà non fare una grande differenza più.
È per questo che abbiamo intenzione di cominciare a considerare queste cose equivalenti.
Quindi le cose come queste costanti qui, ci sono 2 x questo, o l'aggiunta di un 3,
queste sono solo costanti, e questi stanno per cadere up.
Ecco perché tutti e 3 di questi tempi di funzionamento sono gli stessi dicendo che sono O (n).
Allo stesso modo, se abbiamo 2 tempi di esecuzione di altri, diciamo O (n + 2n ³ ²), possiamo aggiungere
+ N, + 7, e poi abbiamo un altro in fase di esecuzione che è solo O (n ³).
ancora, questi sono la stessa cosa perché questi - questi non sono gli stessi.
Queste sono le stesse cose, mi dispiace. Quindi questi sono gli stessi perché
questa ³ n sta per dominare questa ² 2n.
>> Ciò che non è la stessa cosa è se abbiamo tempi di esecuzione come O (³ n) e O (n ²)
perché questo ³ n è molto più grande di questo ² n.
Quindi, se abbiamo esponenti, improvvisamente questa comincia ad essere importante,
ma quando siamo solo che fare con fattori come noi siamo qui,
quindi non sta andando alla materia perché sono solo andando a cadere fuori.
Diamo uno sguardo ad alcuni degli algoritmi che abbiamo visto fino ad ora
e parlare della loro fase di esecuzione.
Il primo modo di cercare un numero in un elenco, che abbiamo visto, era ricerca lineare.
E l'attuazione della ricerca lineare è super semplice.
Non ci resta che una lista, e stiamo andando a guardare ogni singolo elemento della lista
fino a trovare il numero che stiamo cercando.
In modo che significa che nel caso peggiore, questo O (n).
E il caso peggiore qui potrebbe essere se l'elemento è
l'ultimo elemento, quindi utilizzando ricerca lineare dobbiamo guardare ogni singolo elemento
fino ad arrivare all'ultima, per sapere che era in realtà nella lista.
Non possiamo rinunciare a metà strada e dire: "Probabilmente non è lì."
Con la ricerca lineare, dobbiamo guardare a tutta la faccenda.
Il caso migliore tempo di esecuzione, invece, è costante
perché nel migliore dei casi l'elemento che stiamo cercando è solo il primo della lista.
Quindi sta per portarci esattamente 1 punto, non importa quanto grande l'elenco è
se stiamo cercando il primo elemento ogni volta.
>> Così, quando si esegue una ricerca, ricordate, non è necessario che la nostra lista sia ordinata.
Perché stiamo semplicemente andando a guardare su ogni singolo elemento, e non ha molta importanza
quale ordine questi elementi trovi
Un algoritmo di ricerca più intelligente è qualcosa di simile ricerca binaria.
Ricordate, l'implementazione della ricerca binaria è quando si sta andando a
continuare a guardare il mezzo della lista.
E poiché stiamo guardando al centro, è necessario che l'elenco è ordinato
altrimenti non sappiamo dove al centro è, e dobbiamo guardare oltre
l'intera lista di trovarlo, e poi a quel punto stiamo solo perdendo tempo.
Quindi, se abbiamo una lista ordinata e si trova al centro, andremo a confrontare la media
l'elemento che stiamo cercando.
Se è troppo alta, allora possiamo dimenticare la metà destra
perché sappiamo che se il nostro elemento è già troppo alta
e tutto a destra di questo elemento è ancora più elevata,
allora non c'è bisogno di guardare più lì.
Dove invece, se il nostro elemento è troppo basso,
sappiamo tutto a sinistra di tale elemento è troppo bassa,
quindi non ha molto senso cercare nemmeno lì.
In questo modo, ad ogni passo e ogni volta che guardiamo a metà della lista,
stiamo andando a tagliare il nostro problema in due perché improvvisamente sappiamo
un sacco di numeri che non possono essere quello che stiamo cercando.
>> In pseudocodice questo sarebbe qualcosa di simile,
e perché stiamo tagliando la lista a metà ogni volta,
i nostri nel caso peggiore salta run da lineare a logaritmica.
Così improvvisamente abbiamo log-in fasi, al fine di trovare un elemento in una lista.
Il miglior tempo di esecuzione caso, però, è ancora costante
perché ora, limitiamoci a dire che l'elemento che stiamo cercando è
sempre al centro esatto della lista originale.
Così possiamo far crescere il nostro elenco come grande quanto vogliamo, ma se l'elemento che stiamo cercando è al centro,
allora è solo andare a prendere noi 1 passo.
Ecco perché siamo O (log n) e Ω (1) o costante.
Facciamo effettivamente eseguire ricerca binaria su questa lista.
Quindi diciamo che stiamo cercando per l'elemento 164.
La prima cosa che ci accingiamo a fare è trovare il punto medio di questo elenco.
Si dà il caso che il punto centrale sta per cadere in mezzo a questi 2 numeri,
così facciamo solo arbitrariamente dire, ogni volta che il punto medio è compreso tra 2 numeri,
facciamo solo arrotondare.
Abbiamo solo bisogno di essere sicuri di fare questo ogni passo del cammino.
Quindi stiamo andando a radunare, e stiamo andando a dire che 161 è il centro della nostra lista.
So 161 <164, e ogni elemento a sinistra di 161
è anche <164, quindi sappiamo che non sta andando per aiutare noi a tutti
per iniziare a cercare qui, perché l'elemento che stiamo cercando non può essere lì.
Quindi, ciò che possiamo fare è che possiamo solo dimenticare che la metà tutta a sinistra della lista,
e ora in considerazione solo dalla destra del poi 161.
>> Quindi, di nuovo, questo è il punto centrale, diciamo solo arrotondare.
Ora, 175 è troppo grande.
Quindi sappiamo che non sta andando per aiutarci a guardare qui o qui,
in modo che possiamo semplicemente gettare via tutto, e alla fine ci ha colpito la 164.
Hai domande su ricerca binaria?
Passiamo da ricerca attraverso un elenco già ordinato
a prendere effettivamente una lista di numeri in qualsiasi ordine
e fare l'elenco in ordine crescente.
Il primo algoritmo abbiamo guardato è stato chiamato bubble sort.
E questo sarebbe più semplice degli algoritmi che abbiamo visto.
Bubble sort dice che quando le 2 elementi all'interno della lista sono fuori luogo,
cioè non vi è un numero superiore a sinistra di un numero inferiore,
poi andremo a scambiare, perché questo significa che l'elenco sarà
"Più ordinato" di quanto non fosse prima.
E stiamo solo andando a continuare questo processo di nuovo e ancora e ancora
finché alla fine il tipo elementi di bolla alla loro posizione corretta e abbiamo una lista ordinata.
>> Il tempo di esecuzione di questa sta per essere O (n ²). Perché?
Bene, perché nel peggiore dei casi, stiamo andando a prendere ogni elemento, e
stiamo andando a finire confronto ad ogni altro elemento della lista.
Ma nel migliore dei casi, abbiamo un elenco già ordinato, sorta di bolla
solo andando a passare attraverso una volta, dire "No.. non ho fatto alcuna swap, quindi ho finito."
Quindi abbiamo un caso migliore tempo di esecuzione di Ω (n).
Corriamo a bolle in un elenco.
Oppure, facciamo solo un'occhiata ad alcuni pseudocodice molto velocemente.
Vogliamo dire che vogliamo tenere traccia di, in ogni iterazione del ciclo,
tenere traccia di se o non abbiamo cambiato elementi.
Così la ragione di ciò è, stiamo andando a fermarsi quando non abbiamo scambiato alcun elemento.
Così, alla partenza del nostro ciclo non abbiamo scambiato nulla, quindi dovremo dire che è falso.
Ora, stiamo per scorrere l'elenco e confrontare elementi i per elemento i + 1
e se è il caso che vi è un numero grande a sinistra di un numero minore,
allora stiamo solo andando a scambiarle.
>> E poi andiamo a ricordare che ci siamo scambiati un elemento.
Questo significa che abbiamo bisogno di scorrere l'elenco almeno 1 più tempo
perché la condizione in cui si è fermato quando l'intero elenco è già ordinato,
che significa che non sono state apportate swap.
Ecco perché la nostra condizione quaggiù è 'mentre alcuni elementi sono stati scambiati.'
Quindi ora facciamo solo guardare a questa esecuzione su un elenco.
Ho la lista 5,0,1,6,4.
Bubble sort sta per iniziare tutta la strada a sinistra, e sta andando a confrontare
gli elementi i, in modo da 0 a i + 1, che è l'elemento 1.
Sta andando a dire ben 5> 0, ma in questo momento 5 è a sinistra,
quindi ho bisogno di scambiare il 5 e lo 0.
Quando li scambiano, improvvisamente ho questa lista diversa.
Ora 5> 1, quindi stiamo andando per scambiarle.
5 non è> 6, quindi non abbiamo bisogno di fare nulla qui.
Ma 6> 4, quindi abbiamo bisogno di scambiare.
Ancora una volta, abbiamo bisogno di scorrere l'intera lista per scoprire alla fine
che questi non sono in ordine, li scambiano,
ea questo punto abbiamo bisogno di scorrere l'elenco degli orari altri 1
fare in modo che tutto sia nel suo ordine, e, a questo punto bubble sort è terminato.
Un algoritmo diverso per prendere alcuni elementi e lo smistamento è una sorta di selezione.
L'idea alla base di ordinamento per selezione è che stiamo andando a costruire una parte ordinata della lista
1 elemento alla volta.
>> E il modo in cui abbiamo intenzione di farlo è quello di costruire il segmento sinistro della lista.
E in fondo, tutti - ad ogni passo, stiamo andando a prendere il più piccolo elemento che abbiamo lasciato
che non è stato ancora risolto, e abbiamo intenzione di spostarlo in quel segmento ordinato.
Questo significa che abbiamo bisogno di trovare continuamente l'elemento minimo unsorted
e poi prendere l'elemento minimo e scambiarlo con qualsiasi
più a sinistra elemento che non è ordinato.
Il tempo di esecuzione di questa sta per essere O (n ²), perché nel peggiore dei casi
abbiamo bisogno di confrontare ogni singolo elemento di ogni altro elemento.
Perché stiamo dicendo che se si inizia a metà sinistra della lista, abbiamo bisogno di
passare attraverso l'intero segmento di destra per trovare l'elemento più piccolo.
E poi, ancora una volta, abbiamo bisogno di andare oltre l'intero segmento di destra e
andare avanti oltre che più e più e più volte.
Questo sarà ² n. Stiamo andando a bisogno di un ciclo per interni di un altro ciclo for
che suggerisce ² n.
Nel pensiero migliore dei casi, diciamo che diamo un elenco già ordinato;
in realtà non fare meglio di ² n.
Perché per selezione non ha modo di sapere che
l'elemento minimo è proprio quello che mi capita di essere alla ricerca di.
Si deve ancora fare in modo che questo è in realtà il minimo.
>> E l'unico modo per essere sicuri che sia il minimo, con questo algoritmo,
è quello di esaminare ogni singolo elemento nuovo.
Quindi, in realtà, se si dà - se si dà per selezione di un elenco già ordinato,
non sta andando a fare di meglio che dare un elenco che non è ordinato ancora.
Tra l'altro, se capita di essere il caso che qualcosa è O (qualcosa)
e l'omega di qualcosa, possiamo solo dire più brevemente che si tratta di θ di qualcosa.
Quindi, se si vede che vieni da nessuna parte, questo è ciò che significa semplicemente.
>> Se qualcosa è theta di n ², è al tempo stesso grande O (n ²) e Ω (n ²).
Quindi meglio e caso peggiore dei casi, non fa la differenza,
l'algoritmo sta per fare la stessa cosa ogni volta.
Quindi questo è quello che per pseudocodice per selezione potrebbe sembrare.
Stiamo fondamentalmente per dire che voglio scorrere la lista
da sinistra a destra, e ad ogni iterazione del ciclo, ho intenzione di spostare
l'elemento minimo in questa porzione della lista ordinata.
E una volta che mi muovo qualcosa, non ho mai bisogno di guardare a tale elemento nuovo.
Perché non appena scambiare un elemento per il segmento sinistro della lista, è ordinato
perché stiamo facendo tutto in ordine crescente in base minimi.
Così abbiamo detto, okay, siamo nella posizione i, e abbiamo bisogno di guardare a tutti gli elementi
a destra di i per trovare il minimo.
Quindi significa che vogliamo guardare da i + 1 alla fine della lista.
E ora, se l'elemento che stiamo attualmente esaminando sia inferiore al nostro minimo fino ad ora,
che, ricordiamo, stiamo iniziando la bassa minima per essere solo
qualsiasi elemento che siamo attualmente, darò per scontato che è il minimo.
Se trovo un elemento che è più piccolo di quello, allora io sto per dire, va bene,
bene, ho trovato un nuovo minimo.
Io vado a ricordare dove fosse quel minimo.
>> Così ora, una volta che ho vissuto quel segmento diritto indifferenziati,
Posso dire che sto per scambiare l'elemento minimo con l'elemento che si trova in posizione i.
Che sta per costruire la mia lista, la mia parte ordinata della lista da sinistra a destra,
e non abbiamo mai bisogno di guardare a un elemento ancora una volta che è in quella parte.
Una volta che l'abbiamo scambiato.
Quindi cerchiamo di correre per selezione in questo elenco.
L'elemento blu qui sta per essere la i, e l'elemento rosso sta per essere l'elemento minimo.
Così ho avviato tutta la strada a sinistra della lista, quindi a 5.
Ora abbiamo bisogno di trovare l'elemento minimo indifferenziati.
Quindi diciamo 0 <5, così 0 è il mio nuovo minimo.
>> Ma non riesco a smettere qui, perché, anche se siamo in grado di riconoscere che 0 è il più piccolo,
abbiamo bisogno di correre attraverso ogni altro elemento della lista per essere sicuri.
Quindi 1 è più grande, 6 è più grande, 4 è più grande.
Ciò significa che, dopo aver guardato tutti questi elementi, ho determinato 0 è il più piccolo.
Quindi ho intenzione di scambiare il 5 e lo 0.
Una volta che scambiare, io vado a prendere un nuovo elenco, e so che non ho mai bisogno di guardare ancora una volta che 0
perché una volta ho scambiato, ho risolto e abbiamo finito.
Ora si da il caso che l'elemento blu è di nuovo il 5,
e abbiamo bisogno di guardare l'1, il 6 e il 4 per determinare che 1
è l'elemento più piccolo minimo, quindi dovremo scambiare l'1 e il 5.
Ancora una volta, abbiamo bisogno di guardare - confrontare il 5 al 6 e il 4,
e abbiamo intenzione di scambiare il 4 e il 5, e, infine, confrontare
questi 2 numeri e scambiare loro fino a quando avremo il nostro elenco ordinato.
Hai domande su ordinamento per selezione?
Va bene. Passiamo all'ultimo argomento qui, e che è la ricorsione.
>> Ricorsione, ricordiamo, è davvero cosa meta in cui una funzione
chiama ripetutamente stessa.
Così a un certo punto, mentre il nostro fuction viene ripetutamente che si definisce,
ci deve essere un certo punto in cui ci fermiamo chiamarci.
Perché se non lo facciamo, allora stiamo solo andando a continuare a farlo per sempre,
e il nostro programma non è solo andare a terminare.
Chiamiamo questa condizione il caso base.
E il caso base, dice, piuttosto che chiamare una funzione ancora una volta,
Sto solo andando a restituire un valore.
Quindi, una volta che abbiamo restituito un valore, abbiamo smesso di chiamare noi stessi,
e il resto delle chiamate che abbiamo fatto finora può anche restituire.
L'opposto del caso base è il caso ricorsivo.
E questo è quando si vuole effettuare un'altra chiamata alla funzione che siamo attualmente;
E probabilmente, anche se non sempre, desidera utilizzare argomenti diversi.
>> Quindi, se abbiamo una funzione chiamata f, f e ha chiamato prendere 1 argomento,
e abbiamo appena continuano a chiamare f (1), f (1), f (1), e si dà il caso che
l'argomento 1 cade in caso ricorsivo, stiamo ancora mai intenzione di smettere.
Anche se abbiamo un caso base, abbiamo bisogno di fare in modo che alla fine stiamo andando a colpire quel caso base.
Noi non solo continuare a stare in questo caso ricorsivo.
In generale, quando ci chiamano, noi probabilmente stai andando ad avere un argomento diverso ogni volta.
Ecco una funzione molto semplice ricorsiva.
Quindi questo sarà calcolare il fattoriale di un numero.
Fino all'inizio qui abbiamo il nostro scenario di base.
Nel caso in cui n ≤ 1, non stiamo andando a chiamare fattoriale di nuovo.
Stiamo andando a fermarsi, stiamo solo andando a restituire un valore.
Se questo non è vero, allora stiamo andando a colpire il nostro caso ricorsivo.
Notiamo qui che non stiamo solo chiamando fattoriale (n), perché non sarebbe molto utile.
Stiamo andando a chiamare fattoriale di qualcosa d'altro.
>> E così si può vedere, alla fine se si passa a qualcosa di fattoriale (5) o,
stiamo andando a chiamare fattoriale (4) e così via, e alla fine stiamo andando a colpire tale scenario di base.
Quindi questo sembra buono. Vediamo cosa succede quando in realtà esegue questo.
Questa è la pila, e diciamo che si sta per chiamare questa funzione con un argomento (4).
Quindi, una volta fattoriale vede e = 4, si fattoriale stessa chiamata.
Ora, improvvisamente, abbiamo fattoriale (3).
Quindi queste funzioni stanno per continuare a crescere fino alla fine abbiamo raggiunto il nostro scenario di base.
A questo punto, il valore di ritorno di questo è il ritorno (nx il valore restituito),
il valore di ritorno di questo nx è il valore di ritorno di questo.
Alla fine abbiamo bisogno di colpire un certo numero.
Nella parte superiore qui, diciamo di ritorno 1.
Ciò significa che una volta che torniamo quel numero, siamo in grado di pop questo dallo stack.
Quindi questo fattoriale (1) è fatto.
Quando 1 restituisce, questo fattoriali (1) ritorna, questo ritorno alla 1.
Il valore di ritorno di questo, ricordiamo, era nx il valore di ritorno di questo.
Così improvvisamente, questo ragazzo sa che voglio tornare 2.
>> Quindi ricorda, restituire valore di questo è solo nx il valore di ritorno qui.
Così ora possiamo dire 3 x 2, e infine, qui si può dire
questo è solo andare a essere 4 x 3 x 2.
E una volta che questo ritorna, si arriva fino a un singolo intero all'interno del principale.
Hai domande su ricorsione?
Bene. Quindi c'è più tempo per le domande alla fine,
ma ora Joseph abbraccia i temi rimanenti.
>> [Joseph Ong] Va bene. Quindi, ora che abbiamo parlato di ricorsioni,
parliamo un po 'di quello merge sort è.
Merge sort è fondamentalmente un altro modo di ordinare un elenco di numeri.
E come funziona è, con merge sort si dispone di un elenco e quello che facciamo è
diciamo, cerchiamo di dividere questo in 2 metà.
Ecco ora eseguire merge sort di nuovo sulla metà sinistra,
poi ci eseguire merge sort nella metà destra,
e che ci offre ora 2 tempi che sono ordinati, e ora stiamo andando a combinare questi due metà insieme.
E 'un po' difficile da vedere senza un esempio, quindi andremo con i movimenti e vedere cosa succede.
Quindi si parte da questa lista, abbiamo diviso in 2 metà.
Noi usiamo merge sort sulla metà prima a sinistra.
Ecco, questo è la metà sinistra, e ora che sono eseguiti, attraverso questa lista di nuovo
che viene passato in merge sort, e poi guardiamo, ancora una volta,
sul lato sinistro di questa lista e corriamo merge sort su di esso.
Ora, scendere ad una lista di 2 numeri,
e ora la metà di sinistra è solo 1 elemento a lungo, e non possiamo
dividere un elenco che è solo 1 elemento in mezzo, quindi ci limitiamo a dire, una volta che abbiamo 50,
che dista solo 1 elemento, è già ordinato.
>> Una volta che abbiamo finito con questo, possiamo vedere che possiamo
passare alla parte destra di questa lista,
e 3 è anche ordinata, e ora che le due metà di questa lista sono ordinati
siamo in grado di partecipare a questi numeri di nuovo insieme.
Quindi guardiamo a 50 e 3, 3 è inferiore a 50, in modo che entri per primo e il 50 entra in gioco
Ora, questo è fatto, si risale a quella lista e ordinare è metà di destra.
42 è il suo numero, quindi è già ordinato.
Così ora confrontiamo questi 2 e 3 è inferiore a 42, così che viene messo in prima,
ora 42 viene messo in, e 50 viene messo dentro
Ora, che è ordinato, si va tutta la strada verso l'alto, 1337 e 15.
Bene, ora guardiamo alla metà sinistra della lista; 1337 è di per sé in modo che sia ordinato e lo stesso con 15.
Così ora abbiamo combinare questi 2 numeri per ordinare la lista originale, 15 <1337,
in modo che entri per primo, poi 1337 si trovi a
E ora abbiamo risolto entrambe le metà della lista originale sulla parte superiore.
E tutto quello che dobbiamo fare è combinare questi.
Guardiamo i primi 2 numeri di questo elenco, 3 <15, così si va nella matrice odrina.
15 <42, così si va in Ora, 42 <1337, che va trovi
50 <1337, così si va in E notare che abbiamo appena preso 2 numeri di fuori di questo elenco.
Quindi non stiamo solo alternando le 2 liste.
Stiamo solo guardando l'inizio, e stiamo prendendo l'elemento
che è più piccolo e poi metterlo nel nostro array.
Ora che abbiamo unito tutte le parti e abbiamo finito.
>> Avete domande su merge sort? Sì?
[Studente] Se si tratta di dividere in gruppi diversi, perché non basta una volta divisi
e si dispone di 3 e 2 in un gruppo? [Resto del incomprensibile domanda]
La ragione - quindi la domanda è, perché non possiamo semplicemente si fondono in quel primo passo dopo li abbiamo?
La ragione per cui siamo in grado di fare questo, partono più a sinistra gli elementi di entrambe le parti,
e poi prendere quello più piccolo e metterlo dentro, è che sappiamo che queste
singole liste sono ordinati negli ordini.
Quindi, se io sto guardando più a sinistra gli elementi di entrambe le metà,
So che sta andando ad essere i più piccoli elementi degli elenchi.
Quindi posso metterli in luoghi più piccoli elementi di questo elenco di grandi dimensioni.
D'altra parte, se guardo a quei 2 liste nel secondo livello laggiù,
50, 3, 42, 1337 e 15, quelli che non sono ordinati.
Quindi, se guardo a 50 e il 1337, ho intenzione di mettere 50 nel mio primo elenco.
Ma che in realtà non ha senso, perché 3 è il più piccolo elemento di tutti quelli.
Quindi l'unica ragione per cui siamo in grado di fare questo passo che unisce è perché le nostre liste sono già ordinati.
Ed è per questo che dobbiamo scendere fino al fondo
perché quando abbiamo solo un numero unico, si sa che un solo numero
in sé e per sé è già un elenco ordinato.
>> Hai ancora domande? No?
Complessità? Beh, si può vedere che ad ogni passo ci sono i numeri finali,
e possiamo dividere una lista in mezzo log n volte,
che è dove riusciamo ad ottenere questo log n x n complessità.
E vedrete il caso migliore per il merge sort è n log n, e si da il caso
che il caso peggiore, o Ω là, anche n log n.
Qualcosa da tenere a mente.
Passando, andiamo a qualche lima eccellente di base di I / O.
Se hai guardato Scramble, noterete che abbiamo avuto una sorta di sistema
dove si poteva scrivere in un file di registro se si leggono attraverso il codice.
Vediamo come si potrebbe fare.
Bene, abbiamo fprintf, che si può pensare solo come printf,
ma solo la stampa su un file, e quindi la f all'inizio.
Questo tipo di codice qui, ciò che fa è, come forse avrete già visto in Scramble,
passa attraverso il tuo a 2 dimensioni di stampa su matrice riga per riga quello che i numeri sono.
In questo caso, stampa printf fuori al vostro terminale o quello che noi chiamiamo lo standard output di sezione.
>> Ed ora, in questo caso, tutto quello che dobbiamo fare è sostituire printf con fprintf,
indicare cosa file che si desidera stampare, e in questo caso si limita a stampare fuori a quel file
invece di esso stampare sul terminale.
Beh, allora che pone la domanda: Dove possiamo ottenere questo tipo di file da, giusto?
Passammo accedere a questa fuction fprintf, ma non avevamo idea di dove venisse.
Beh, all'inizio del codice, quello che avevamo era questo pezzo di codice qui,
che in pratica dice che si aprono il file log.txt chiama.
Quello che facciamo dopo che è che dobbiamo fare in modo che il file è in realtà aperto con successo.
Così potrebbe non riuscire per diverse ragioni, non si ha abbastanza spazio sul vostro computer, per esempio.
Quindi è sempre importante prima di fare qualsiasi operazione con il file
che verificare se il file è stato aperto con successo.
Allora, cosa che una, che è un argomento di fopen, beh, siamo in grado di aprire un file in molti modi.
Quello che possiamo fare è, possiamo passare w, il che significa che l'override del file se esistono già,
Siamo in grado di passare un a, che aggiungere alla fine del file, invece di scavalcarlo,
oppure possiamo specificare r, il che significa che, cerchiamo di aprire il file in sola lettura.
Quindi, se il programma tenta di apportare modifiche al file,
urlare contro di loro e non lasciarli fare.
Infine, una volta che abbiamo finito con il file, finito di fare le operazioni su di esso,
abbiamo bisogno di essere sicuri di chiudere il file.
E così, alla fine del programma, che si sta per passare di nuovo
questo file che è stato aperto, e basta chiuderla.
Quindi questa è una cosa importante che si deve fare in modo di fare.
Quindi ricorda è possibile aprire un file, allora si può scrivere nel file,
fare operazioni nel file, ma poi si deve chiudere il file alla fine.
>> Hai domande su file di base di I / O? Sì?
[Domanda Studente, incomprensibile]
Proprio qui. La domanda è: da dove viene questo file log.txt apparire?
Beh, se basta dare log.txt, lo crea nella stessa directory del file eseguibile.
Quindi, se tu sei - >> [domanda Studente, incomprensibile]
Sì. Nella stessa cartella, o nella stessa directory, come la chiami tu.
Ora la memoria, stack e heap.
Così come è la memoria di cui nel computer?
Beh, si può immaginare come una sorta di memoria di questo blocco qui.
E in memoria abbiamo quello che si chiama il mucchio bloccato laggiù, e lo stack che è laggiù.
E l'heap cresce verso il basso e lo stack cresce verso l'alto.
Così come Tommy detto - oh, bene, e abbiamo questi altri 4 segmenti che ci arriverò in un secondo -
Come Tommy detto in precedenza, si sa come le sue funzioni si dicono e si chiamano?
Essi costruire questo tipo di stack frame.
Beh, se le chiamate principali pippo, pippo viene messa in pila.
Foo chiama bar, get messa in pila, e che viene messa in pila dopo.
E tornano, a ciascuno di essi preso dallo stack.
Cosa ciascuno di questi luoghi e la memoria tenere?
Ebbene, la parte superiore, che è il segmento di testo, comprende il programma stesso.
Quindi, il codice macchina, che è lì, una volta che la compilazione del programma.
Quindi, qualsiasi inizializzate le variabili globali.
>> In modo da avere le variabili globali nel programma, e si dice come, a = 5,
che viene messo in questo segmento, e proprio in forza di tale,
si dispone di tutti i dati non inizializzati globali, che si sta int a,
ma non dire che è uguale a niente.
Realizzare questi sono variabili globali, quindi sono al di fuori della principale.
Quindi questo significa che tutte le variabili globali che vengono dichiarate ma non sono inizializzati.
Così che cosa è nel mucchio? La memoria allocata con malloc, che ci arriveremo tra un po '.
E, infine, con lo stack avete qualche variabili locali
e tutte le funzioni che si potrebbe chiamare in uno qualsiasi dei loro parametri.
L'ultima cosa, in realtà non è necessario sapere quali sono le variabili di ambiente fare,
ma ogni volta che si esegue programma, c'è qualcosa di associato, come
questo è il nome della persona che ha eseguito il programma.
E che sta per essere una sorta di in fondo.
In termini di indirizzi di memoria, che sono i valori esadecimali,
i valori iniziali in alto a 0, e si fanno tutta la strada fino in fondo.
In questo caso, se siete sul sistema a 32 bit,
l'indirizzo in fondo sta per essere 0x, seguito da af, perché è a 32 bit,
che è di 8 byte, e in questo caso 8 byte corrisponde a 8 cifre esadecimali.
Quindi, qui si sta andando ad avere, come, 0xffffff, e lassù si sta andando ad avere 0.
Quindi quali sono i puntatori? Alcuni di voi non hanno coperto in questa sezione prima.
ma abbiamo fatto andare su di esso in conferenza, quindi un puntatore è solo un tipo di dati
quali negozi, invece di una sorta di valore come 50, memorizza l'indirizzo di qualche posizione nella memoria.
Come quella memoria [incomprensibile].
Quindi, in questo caso, ciò che abbiamo è, abbiamo un puntatore ad un intero o un int *,
e contiene l'indirizzo esadecimale di 0xDEADBEEF.
>> Quindi ciò che abbiamo è, ora, questo puntatore punta a un certo indirizzo di memoria,
e questo è solo uno, il valore di 50 è in questa posizione di memoria.
Su alcuni sistemi a 32 bit, su tutti i sistemi a 32 bit, i puntatori occupano 32 bit o 4 byte.
Ma, per esempio, su un sistema a 64 bit, i puntatori sono 64 bit.
Ecco, questo è qualcosa che si vorrà tenere a mente.
Quindi, su un end-bit del sistema, un puntatore è bit di fascia lunga.
I puntatori sono una sorta di difficili da digerire senza cose in più,
quindi cerchiamo di passare attraverso un esempio di allocazione dinamica della memoria.
Che allocazione dinamica della memoria fa per voi, o ciò che noi chiamiamo malloc,
vi permette di assegnare una sorta di dati al di fuori del set.
Quindi questo tipo di dati è più permanente per la durata del programma.
Perché, come si sa, se si dichiara x all'interno di una funzione, e che i ritorni di funzione,
non hai più accesso ai dati che sono stati memorizzati in x.
Cosa puntatori facciamo è che ci ha lasciato tenere i valori di memoria o un negozio
in un diverso segmento della memoria, cioè la heap.
Ora, una volta torniamo fuori della funzione, fino a quando abbiamo un puntatore
in quella posizione in memoria, quindi quello che possiamo fare è che può solo guardare i valori lì.
Vediamo un esempio: Questo è il nostro nuovo layout di memoria.
E noi abbiamo questa funzione principale.
Ciò che fa è - bene, così semplice, giusto? - Int x = 5, che è solo una variabile sullo stack in main.
>> D'altra parte, ora si dichiara un puntatore che chiama i giveMeThreeInts funzione.
E così ora andiamo in questa funzione e creare una nuova cornice dello stack per esso.
Tuttavia, in questo stack frame, dichiariamo int * temp,
che in mallocs 3 interi per noi.
Così dimensione di int ci darà il numero di byte int è questo,
malloc e ci dà tale numero di byte di spazio sul mucchio.
Quindi, in questo caso, abbiamo creato spazio sufficiente per 3 interi,
e l'heap è lassù, è per questo che ho disegnato più in alto.
Una volta che abbiamo finito, torniamo qui, avete solo bisogno di 3 int restituito,
e restituisce l'indirizzo, in questo caso oltre che la memoria in cui è.
E noi ad impostare il puntatore = interruttore, e lì abbiamo solo un altro puntatore.
Ma che cosa restituisce la funzione è accatastato qui e scompare.
Così temperatura scompare, ma abbiamo ancora mantengono l'indirizzo del luogo in cui
quei 3 numeri interi sono dentro di rete.
Quindi, in questa serie, i puntatori sono limitate a livello locale per il telaio impilati,
ma la memoria a cui si riferiscono è nell'heap.
>> Ha senso?
[Studente] Può ripetere? >> [Joseph] Sì.
Quindi, se torno solo un po ', si vede che temperatura assegnata
un po 'di memoria sul mucchio lassù.
Così, quando questa funzione, giveMeThreeInts restituisce, questo stack qui sta andando a scomparire.
E con esso qualsiasi variabile, in questo caso, il puntatore che è stata assegnata in cornice impilati.
Questo sta andando a scomparire, ma dal momento che siamo tornati temperatura
e impostare il puntatore = temp, puntatore sta ora andando a puntare la stessa memoria di posizione come temperatura era.
Così ora, anche se si perde temperatura, tale puntatore locale,
si conservano ancora l'indirizzo di memoria di ciò che stava puntando verso l'interno di quel puntatore variabile.
Domande? Che può essere una specie di un argomento confusione se non sono andati su di esso nella sezione.
Siamo in grado, il TF sarà sicuramente andare su di esso e, naturalmente, siamo in grado di rispondere alle domande
al termine della sessione commenti per questo.
Ma questa è una sorta di un argomento complesso, e non ho più esempi che stanno per presentarsi
che aiuterà a chiarire ciò puntatori in realtà sono.
>> In questo caso, i puntatori sono equivalenti a matrici,
quindi posso solo utilizzare questo puntatore come la stessa cosa di un array int.
Quindi sono l'indicizzazione in 0, e cambiando il primo numero intero a 1,
cambiando il secondo intero per 2, e l'intero terzo a 3.
Quindi più sui puntatori. Beh, ricordo Binky.
In questo caso abbiamo assegnato un puntatore, o abbiamo dichiarato un puntatore,
ma inizialmente, quando ho appena dichiarato un puntatore, non è che punta a dovunque in memoria.
E 'solo i valori della spazzatura all'interno di esso.
Quindi non ho idea di dove questo puntatore punta a.
Esso ha un indirizzo che è appena riempito con 0 e 1, dove è stato inizialmente dichiarato.
Io non posso fare niente con questo fino a quando non chiama malloc su di esso
e poi mi dà un po 'di spazio nel mucchio, dove posso mettere i valori al suo interno.
Poi di nuovo, non so cosa c'è dentro di questa memoria.
Quindi la prima cosa che devo fare è verificare se il sistema ha memoria sufficiente
di darmi indietro 1 intero, in primo luogo, che è per questo che sto facendo questo controllo.
Se il puntatore è nullo, il che significa che essa non dispone di spazio sufficiente o qualche altro errore si è verificato,
quindi dovrei uscire dal mio programma.
Ma se così fosse successo, ora posso usare tale puntatore
e ciò che fa è puntatore * ne consegue in cui l'indirizzo è
dove tale valore è, e pone uguale ad 1.
Così qui, stiamo controllando se la memoria esistente.
>> Una volta che sai che esiste, si può mettere in esso
quale valore che si desidera mettere in esso, in questo caso 1.
Una volta che abbiamo finito con esso, è necessario liberare tale puntatore
perché abbiamo bisogno di tornare al sistema che memoria che hai chiesto, in primo luogo.
Poiché il computer non sa quando avremo finito con esso.
In questo caso stiamo dicendo esplicitamente, va bene, abbiamo finito con quel ricordo.
Se qualche altro processo di cui ha bisogno, un altro programma di cui ha bisogno, sentitevi liberi di andare avanti e prendere.
Quello che possiamo anche fare è che possiamo solo ottenere l'indirizzo delle variabili locali sul set.
Quindi x int è all'interno della cornice pila di principale.
E quando usiamo questo e commerciale, questo e operatore, ciò che fa è
prende x, ed x è solo alcuni dati in memoria, ma ha un indirizzo.
Si trova da qualche parte. Quindi chiamando & x, cosa che fa è che ci dà l'indirizzo di x.
In questo modo, stiamo facendo il punto indicazione di dove x è in memoria.
Ora dobbiamo solo fare qualcosa di simile a * x, stiamo andando ottenere 5 indietro.
La stella si chiama deferenziandolo.
Si segue l'indirizzo e si ottiene il valore di esso memorizzate.
>> Hai ancora domande? Sì?
[Studente] Se non si fanno le 3 punte cosa, ha ancora compilato?
Sì. Se non si esegue il 3-pointer cosa, è ancora in corso di compilazione,
ma ti faccio vedere cosa succede in un secondo, e senza fare che,
questo è ciò che noi chiamiamo una perdita di memoria. Lei non è dando il sistema
sostenere la sua memoria, così dopo un po 'il programma sta andando ad accumularsi
memoria che non è in uso, e niente altro può utilizzare.
Se hai mai visto Firefox con 1,5 milioni di kilobyte sul computer,
nel task manager, questo è quello che sta succedendo.
Hai una perdita di memoria nel programma che non è la manipolazione.
Così come puntatore lavoro aritmetica?
Beh, l'aritmetica dei puntatori è una sorta di indicizzazione, come in una matrice.
In questo caso, ho un puntatore, e quello che faccio e 'far puntare il puntatore al primo elemento
di questo array di 3 interi che ho assegnato.
Così ora che cosa faccio, puntatore stella cambia solo il primo elemento della lista.
Star Pointer +1 punti qui.
Così puntatore è qui, puntatore +1 è qui, puntatore +2 è qui.
>> Quindi, solo l'aggiunta di 1 è la stessa cosa che si muove lungo questa matrice.
Quello che facciamo è, quando facciamo uno puntatore si ottiene l'indirizzo qui,
e al fine di ottenere il valore qui, si mette una stella in da l'intera espressione
per risolvere il riferimento di esso.
Quindi, in questo caso, sto impostando la prima posizione in questo array a 1,
seconda posizione a 2, e la terza posizione a 3.
Allora quello che sto facendo qui è che sto stampando il nostro puntatore +1,
che dà solo a me 2.
Ora sto incremento del puntatore, in modo uguale puntatore puntatore +1,
che si muove in avanti.
E così ora se stampare puntatore +1, puntatore +1 è ora 3,
che in questo caso viene stampato 3.
E per qualcosa di gratuito, il puntatore che ho dato
deve essere rivolto all'inizio della matrice che sono tornato da malloc.
Quindi, in questo caso, se dovessi chiamare 3 proprio qui, questo non sarebbe giusto,
perché è nel mezzo della matrice.
Devo togliere per raggiungere la posizione originale
il punto iniziale del nome prima che io possa liberare.
Quindi, ecco un esempio più coinvolti.
In questo caso, stiamo assegnando 7 caratteri in un array di caratteri.
>> E in questo caso quello che stiamo facendo è che stiamo ciclare su il 6 primo di essi,
e li stiamo impostando alla Z.
Così, per int i = 0, i> 6, i + +,
Quindi, puntatore + i sarà solo ci darà, in questo caso,
puntatore, puntatore 1, 2 pointer, puntatore 3, e così via e così via nel ciclo.
Che cosa sta andando a fare è diventa tale indirizzo, dereferenziazioni per ottenere il valore,
e le modifiche che il valore di una Z.
Poi alla fine ricordate che questo è una stringa, giusto?
Tutte le stringhe devono terminare con il carattere nullo di terminazione.
Quindi, quello che faccio è in puntatore 6 Ho messo il carattere nullo di terminazione trovi
E ora quello che sto praticamente facendo qui sta attuando printf per una stringa, giusto?
>> Così, quando si printf ora quando è arrivato alla fine di una stringa?
Quando si colpisce il carattere nullo di terminazione.
Quindi, in questo caso, i punti puntatore originale fino all'inizio di questa matrice.
Stampare il primo carattere fuori. La muovo più di un.
A stampare quel personaggio fuori. Lo muovo sopra.
E continuare a fare questo fino a raggiungere la fine.
E ora il puntatore * finale sarà dereference questo e di ottenere il carattere di terminazione null indietro.
E così il mio ciclo while viene eseguito solo quando tale valore non è il carattere nullo di terminazione.
Così, ora uscire da questo ciclo.
E quindi se io sottrarre 6 da questo puntatore,
Torno fino all'inizio.
Ricordate, sto facendo questo perché devo andare all'inizio, al fine di liberarlo.
>> Quindi, so che era un sacco. Ci sono domande?
Per favore, sì?
[Incomprensibile domanda lo studente]
Si può dire che il più forte? Scusi.
[Studente] Sulla diapositiva a destra prima di liberare il puntatore,
in cui sono stati effettivamente cambiando il valore del puntatore?
[Giuseppe] Così, proprio qui. >> [Studente] Oh, va bene.
[Giuseppe] Così, ho un puntatore meno meno, a destra,
che si muove la cosa indietro di una, e poi l'ho liberare,
perché questo puntatore deve essere indicato all'inizio della matrice.
[Studente] Ma non sarebbe stato necessario se aveste fermato dopo quella linea.
[Giuseppe] Quindi, se avessi smesso dopo questo, questo sarebbe considerato una perdita di memoria,
perché non è stata eseguita la libera.
[Studente] I [incomprensibile] dopo le prime tre righe in cui si doveva puntatore +1 [incomprensibile].
[Joseph] Uh-huh. Allora, qual è la domanda lì?
Scusi. No, no. Andate, andate, per favore.
[Studente] Quindi, non stai cambiando il valore dei puntatori.
Non avrebbe dovuto fare puntatore meno meno.
[Giuseppe] Sì, esattamente.
Così, quando faccio puntatore puntatore +1 e +2,
Non sto facendo il puntatore è uguale puntatore +1.
Quindi, il puntatore rimane semplicemente puntando all'inizio della matrice.
E 'solo quando lo faccio plus plus che imposta il valore di nuovo dentro il puntatore,
che si muove in realtà questo insieme.
Bene.
Altre domande?
>> Ancora una volta, se questa è una sorta di travolgente, questo sarà coperto in sessione.
Chiedi al tuo compagno di insegnare, e siamo in grado di rispondere alle domande alla fine.
E di solito non ci piace fare questa cosa meno.
Questo ha a che mi obbligano tenere traccia di quanto ho compensato nella matrice.
Quindi, in generale, questo è solo per spiegare come funziona aritmetica dei puntatori.
Ma ciò che di solito piace fare è ci piace creare una copia del puntatore,
e poi useremo la copia quando ci stiamo muovendo in giro per la stringa.
Così, in questi casi si utilizza la copia per stampare l'intera stringa,
ma non c'è bisogno di fare come puntatore meno 6 o tenere traccia di quanto ci siamo trasferiti in questo,
solo perché sappiamo che il nostro punto di partenza è ancora indicato l'inizio della lista
e tutto ciò che abbiamo modificato era questa copia.
Quindi, in generale, alterare copie del puntatore originale.
Non cercare di specie di - Don 't modificare copie originali.
Cercando di modificare solo le copie degli originali.
Quindi, si nota quando si passa la stringa in printf
non c'è bisogno di mettere una stella di fronte ad essa come abbiamo fatto con tutti gli altri dereferenziazioni, giusto?
Quindi, se si stampa l'intera stringa% s si aspetta è un indirizzo,
e in questo caso un puntatore o in questo caso come un array di caratteri.
>> Personaggi, char * s, e gli array sono la stessa cosa.
Pointer è quello di caratteri e array di caratteri sono la stessa cosa.
E così, tutto quello che dobbiamo fare è passare il puntatore.
Non c'è bisogno di passare come puntatore * o qualcosa di simile.
Così, vettori e puntatori sono la stessa cosa.
Quando si sta facendo qualcosa di simile x [y] qui per un array,
quello che sta facendo sotto il cofano è che sta dicendo, va bene, si tratta di un array di caratteri,
quindi è un puntatore.
E così x sono la stessa cosa,
e così ciò che fa è si aggiunge y a x,
che è la stessa cosa di andare avanti nella memoria più di tanto.
E ora x + y ci dà una specie di indirizzo,
e noi dereference l'indirizzo o seguire la freccia
al punto in cui quella posizione in memoria è e si ottiene il valore di quella posizione in memoria.
Così, per cui questi due sono esattamente la stessa cosa.
E 'solo uno zucchero sintattico.
Fanno la stessa cosa. Sono solo sintattica diversi uno per l'altro.
>> Allora, che cosa può andare male con i puntatori? Come, molto. Va bene. Quindi, cose cattive.
Alcune cose cattive che si possono fare non si verifica se la chiamata malloc restituisce null, giusto?
In questo caso, mi sto chiedendo il sistema di darmi - qual è quel numero?
Come 2 miliardi di volte 4, poiché la dimensione di un numero intero di 4 byte.
Mi sto chiedendo come 8 miliardi di byte.
Naturalmente il computer non sarà in grado di darmi quella schiena di memoria.
E non abbiamo fatto controllare se questo è nullo, in modo che quando si cerca di dereferenziarlo laggiù -
seguite la freccia per dove sta andando a - non abbiamo che la memoria.
Questo è ciò che noi chiamiamo dereference un puntatore nullo.
E questo fa sì che essenzialmente di segfault.
Questo è uno dei modi in cui puoi segfault.
Altre cose cattive che si possono fare - oh, va bene.
Questo è stato dereference un puntatore nullo. Va bene.
Altre cose cattive - bene, per risolvere questo basta mettere un check-in vi
che controlla se il puntatore è nullo
e uscire dal programma se accade che malloc restituisce un puntatore nullo.
Questo è il fumetto xkcd. La gente lo capisco adesso. Più o meno.
>> Quindi, la memoria. E sono andato su questo.
Stiamo chiamando malloc in un ciclo, ma ogni volta che chiamiamo malloc
stiamo perdendo traccia di dove questo puntatore punta a,
perché stiamo sovrascrivere.
Quindi, la chiamata iniziale a malloc mi dà la memoria qui.
I miei puntatori puntatore a questo.
Ora, io non lo liberare, così ora io chiamo malloc di nuovo.
Ora che punti qui. Ora la mia memoria è di puntamento sopra qui.
Indicare qui. Indicare qui.
Ma ho perso il conto degli indirizzi di tutta la memoria qui che ho assegnato.
E così ora non ho alcun riferimento a loro più.
Quindi, non posso liberare al di fuori di questo ciclo.
E così, al fine di risolvere una cosa del genere,
se si dimentica di liberare la memoria e si ottiene questa perdita di memoria,
È necessario liberare la memoria interna di questo ciclo una volta che hai fatto con esso.
Bene, questo è ciò che accade. So che molti di voi Odio tutto questo.
Ma ora - yay! Si ottiene come 44.000 kilobyte.
Quindi, si libera alla fine del ciclo,
e che sta andando a liberare solo la memoria ogni volta.
In sostanza, il programma non dispone di una perdita di memoria più.
>> E ora qualcosa di diverso si può fare è liberare la memoria che hai chiesto per due volte.
In questo caso, una cosa malloc, cambi il suo valore.
Lo liberare una volta, perché hai detto che sono stati fatti con esso.
Ma poi lo abbiamo liberato di nuovo.
Questo è qualcosa che è piuttosto male.
E non ha intenzione di segfault inizialmente,
ma dopo un po 'ciò che questo non fa altro che doppio liberando questo corrompe la struttura heap,
e potrai imparare un po 'di più su questo se si sceglie di prendere una classe come CS61.
Ma in sostanza dopo un po 'il computer sta per confondersi
su ciò che locazioni di memoria in cui sono e dove è memorizzato -
in cui i dati sono memorizzati nella memoria.
E così liberare un puntatore è due volte un male che non si vuole fare.
>> Altre cose che possono andare male non utilizza sizeof.
Quindi, in questo caso si malloc 8 byte,
e questa è la stessa cosa di due interi, giusto?
Quindi, questo è perfettamente sicuro, ma è vero?
Beh, come Lucas ha parlato su differenti architetture,
interi sono di lunghezze diverse.
Così, l 'apparecchio che si sta utilizzando, numeri interi sono circa 4 byte,
ma su qualche altro sistema potrebbero essere 8 byte o potrebbero essere di 16 byte.
Quindi, se mi basta usare questo numero qui,
questo programma potrebbe funzionare l'apparecchio,
ma non ha intenzione di allocare memoria sufficiente su qualche altro sistema.
In questo caso, questo è ciò che l'operatore sizeof viene utilizzato per.
Quando chiamiamo sizeof (int), cosa che fa è
ci dà la dimensione di un intero nel sistema che il programma è in esecuzione.
Quindi, in questo caso, sizeof (int) restituisce 4 su qualcosa come l'apparecchio,
e ora questo 4 * volontà 2, che è 8,
che è solo la quantità di spazio necessario per due interi.
Su un sistema diverso, se un int è come 16 byte o 8 byte,
è solo andare per tornare abbastanza byte per memorizzare tale importo.
>> E, infine, le strutture.
Quindi, se si vuole memorizzare una scheda di sudoku in memoria, come potremmo fare?
Si potrebbe pensare di come una variabile per la prima cosa,
una variabile per la seconda cosa, una variabile per la terza cosa,
una variabile per la quarta cosa - male, vero?
Così, un miglioramento che si può fare al di sopra di questo è di fare un 9 x 9 matrice.
Va bene, ma cosa succede se si desidera associare l'altro con la scheda di sudoku
come quello che la difficoltà della scheda è,
o, ad esempio, che cosa il vostro punteggio è, o quanto tempo ci è voluto voi per risolvere questo forum?
Beh, cosa si può fare è che si può creare una struttura.
Quello che sto dicendo è che in fondo sono la definizione di questa struttura qui,
e io sono la definizione di una scheda di sudoku che consiste in una tavola che è 9 x 9.
>> E quello che ha che ha puntatori al nome del livello.
Ha anche x e y, che sono le coordinate di dove mi trovo in questo momento.
Essa ha anche il tempo trascorso [incomprensibile], ed ha il numero totale di mosse ho immessi finora.
E così in questo caso, posso raggruppare un insieme di dati in una sola struttura
invece di averlo come volare in giro come diverse variabili
che non posso tenere traccia di.
E questo ci permette di avere solo la sintassi bello per genere di riferimento cose diverse all'interno di questa struttura.
Posso solo fare board.board, e ho la scheda di sudoku posteriore.
Board.level, ho capito quanto è difficile.
Board.x e board.y mi danno le coordinate di dove potrei essere in consiglio di amministrazione.
E così sto accedendo ciò che noi chiamiamo campi della struct.
Questo definisce sudokuBoard, che è un tipo che ho.
E ora siamo qui. Ho una variabile chiamata "asse" di sudokuBoard tipo.
E così ora posso accedere a tutti i campi che compongono questa struttura qui.
>> Avete domande su strutture? Sì?
[Studente] Per int x, y, si sia dichiarato in una riga? >> [Joseph] Uh-huh.
[Studente] Allora, hai potuto fare con tutti loro?
Come in x, y volte virgola che il totale?
[Giuseppe] Sì, si potrebbe sicuramente fare, ma la ragione per cui ho messo x e y sulla stessa linea -
e la domanda è: perché possiamo solo fare questo sulla stessa linea?
Perché non basta mettere tutti questi sulla stessa linea è
X e Y sono legati tra loro,
e questo è solo stilisticamente più corretto, in un certo senso,
perché è il raggruppamento due cose sulla stessa linea
quella specie come di riguardare la stessa cosa.
E ho appena diviso questi pezzi. E 'solo una cosa stile.
Si fa funzionalmente alcuna differenza.
Altre domande su strutture?
È possibile definire un Pokédex con una struttura.
Un Pokémon ha un numero ed ha una lettera, un proprietario, un tipo.
E poi se si dispone di una serie di Pokémon, è possibile effettuare un Pokédex, giusto?
Ok, fresco. Così, le questioni relative strutture. Questi sono correlate a strutture.
>> Infine, GDB. Che cosa ti permette di fare GDB? Esso consente di eseguire il debug del programma.
E se non avete usato GDB, avrei consigliato a guardare il breve
e solo andando su ciò che GDB è, come si lavora con esso, come si potrebbe utilizzare,
e provarla su un programma.
E così quello che GDB permette di fare è permette mettere in pausa il [incomprensibile] il vostro programma
e una linea pratica.
Per esempio, io voglio mettere in pausa l'esecuzione come la linea 3 del mio programma,
e mentre sono in linea 3 Sono in grado di stampare tutti i valori che ci sono.
E così ciò che noi chiamiamo come pausa in una linea
è che noi chiamiamo questo mettere un punto di interruzione in quella linea
e poi siamo in grado di stampare le variabili allo stato del programma in quel momento.
>> Possiamo poi da lì il passaggio attraverso il programma linea per linea.
E poi siamo in grado di guardare lo stato dello stack al momento.
E così, al fine di utilizzare GDB, quello che facciamo è che chiamiamo clang sul file C,
ma dobbiamo passare il flag-ggdb.
E una volta che abbiamo finito con questo abbiamo basta eseguire gdb sul file di output risultante.
E in modo da ottenere un po 'di massa come di testo come questo,
ma in realtà tutto quello che dovete fare è digitare i comandi all'inizio.
Rompere principale mette un punto di interruzione principale.
Lista 400 elenca le righe di codice attorno alla riga 400.
E così in questo caso si può solo guardarsi intorno e dire: oh,
Voglio impostare un punto di interruzione alla riga 397, che è questa linea,
e poi il programma viene eseguito in quella fase e sta andando a rompere.
E 'intenzione di mettere in pausa lì, ed è possibile stampare, ad esempio, il valore di basso o alto.
E così ci sono un sacco di comandi che dovete sapere,
e questo slideshow saliranno sul sito web,
quindi se si desidera fare riferimento questi o come metterli sul vostro cheat sheet, non esitate.
>> Cool. Era Quiz Review 0, e si proverà in giro se avete domande.
Bene.
>> [Applausi]
>> [CS50.TV]