[Powered by Google Translate] [Review] [Test 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Universitatea Harvard]
>> [Acest lucru este CS50.] [CS50.TV]
>> Hei, toată lumea.
Bine ați venit la sesiunea de reexaminare pentru Quiz 0, care are loc miercurea aceasta.
Ceea ce am de gând să faci în seara asta, eu sunt cu 3 TFS alte,
și împreună vom merge printr-o revizuire a ceea ce am făcut în cursul până în prezent.
Acesta nu va fi de 100% complete, dar ar trebui să vă dau o idee mai bună
de ceea ce ai deja în jos și ceea ce aveți nevoie în continuare pentru a studia inainte de miercuri.
Și nu ezitați să ridice mâna cu întrebări ca mergem de-a lungul,
dar păstrează în minte faptul că vom avea, de asemenea, un pic de timp de la sfârșitul anului
în cazul în care vom obține prin intermediul cu câteva minute pentru a de rezervă, pentru a face întrebări generale,
deci rețineți că, în minte, și așa am de gând să înceapă de la început cu săptămâna 0.
>> [Quiz 0 opinie!] [Partea 0] [Lexi Ross] Dar, inainte de a face asta haideți să vorbim despre
logistica de test.
>> [Logistica] [Chestionar are loc miercuri, 10/10 în loc de curs]
>> [(A se vedea pentru detalii http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf)], este miercuri, 10 octombrie.
>> Asta e miercurea aceasta, și dacă te duci la această adresă URL aici,
care este, de asemenea, accesibil din CS50.net-acolo e un link către aceasta,
puteți vedea informații despre unde să mergeți pe baza
Numele dvs. de familie sau de afiliere față de școală, precum și
se spune despre exact ceea ce testul va acoperi și tipurile de întrebări pe care ai de gând să obțineți.
Țineți cont de faptul că veți avea, de asemenea, o șansă de a revizui pentru test în secțiune,
astfel TFS dvs. ar trebui să fie trecând peste unele probleme de practică,
și asta este o altă șansă bună de a vedea în cazul în care aveți în continuare nevoie pentru a studia pentru test.
Să începem de la început cu Bytes 'n' biți.
Amintiți-vă un pic este doar un 0 sau un 1,
și un octet este o colecție de 8 biți a acestor.
Să ne uităm la această colecție de biți chiar aici.
Noi ar trebui să fie în măsură să dau seama cum de multe biți sunt.
În cazul în care ne bazăm nu e doar 8 dintre ei, cu opt unități de 0 sau 1.
Și din moment ce există 8 biți, care e un octet,
și să-l transforme în hexazecimal.
Hexazecimal este baza 16, și este destul de ușor pentru a converti
un număr în binar, care este ceea ce este faptul că, la un număr în hexazecimal.
Tot ce facem este ne uitam la grupuri de 4,
și le converti în cifre hexazecimale corespunzătoare.
Vom începe cu drept de grup-cea mai mare de 4, așa 0011.
Asta va fi un 1 și un 2, astfel încât împreună face 3.
Și atunci să ne uităm la blocul celălalt de 4.
1101. Asta va fi un 1, un 4, și un 8.
Împreună, care va fi 13, care face D.
Și ne vom aminti că, în hexazecimal noi nu mergem la 0 la 9.
Noi mergem la 0 la F, dupa 9, 10 corespunde unei,
11 B, et cetera unde F este de 15.
Aici este un D 13,
astfel încât să converti în zecimal tot ceea ce facem este că, de fapt
trateze fiecare poziție ca o putere a lui 2.
Asta e un 1, o 2, la zero 4s, zero 8s, o 16, et cetera,
și e un pic cam greu pentru a calcula în capul tău, dar dacă mergem la urmatorul slide
putem vedea răspunsul la asta.
>> În esență, mergem peste drum de dreapta spate la stânga,
și suntem înmulțirea fiecărei cifre de puterea corespunzătoare de 2.
Și amintiți-vă, pentru hexazecimal notăm aceste numere cu 0x la început
așa că nu-l confunda cu un număr zecimal.
Continuând pe, acesta este un tabel ASCII,
și ceea ce vom folosi ASCII pentru este de a mapa de caractere la valori numerice.
Amintiți-vă, în PSET criptografie am folosit pe scară largă a Tabelul ASCII
, în scopul de a utiliza diverse metode de criptografie,
Cezar și cifrul Vigenere, pentru a converti litere diferite
într-un șir în conformitate cu cheia dată de utilizator.
Să ne uităm la un pic de matematica ASCII.
Privind la "P" + 1, în formă de caractere care ar fi Q,
și amintiți-vă că "'5 ≠ 5.
Și cum mai exact ne-ar converti între aceste 2 forme?
Nu e de fapt prea greu.
În scopul de a obține 5 scădem '0 '
deoarece sunt 5 locuri între '0 'și '5. "
În scopul de a merge în altă parte vom adăuga doar 0,
deci e un fel de aritmetică regulate.
Doar amintiți-vă că atunci când ceva are citate în jurul valorii de ea e un personaj
și, astfel, corespunde o valoare în tabelul ASCII.
Mutarea în mai multe teme generale de informatică.
Am învățat ce un algoritm este și modul în care ne folosim de programare
să pună în aplicare algoritmi.
Câteva exemple de algoritmi sunt ceva foarte simplu ca
a verifica dacă un număr este par sau impar.
Pentru că ne amintim modez numărul de 2 și verificați dacă rezultatul este 0.
Dacă este așa, e chiar. Dacă nu, e ciudat.
Si asta e un exemplu de algoritm foarte de bază.
>> Un pic de una mult mai implicat este căutare binară,
care vom trece peste mai târziu, în sesiunea de reexaminare.
Și de programare este termenul vom folosi pentru a lua un algoritm
și transformând-o pentru a coda calculatorul poate citi.
2 exemple de programare este Scratch,
care este ceea ce am făcut în săptămâna 0.
Chiar dacă nu ne tastați codul efectiv este o modalitate de punere în aplicare
acest algoritm, care se imprimă numerele 1-10,
și aici facem același lucru în limbajul de programare C.
Acestea sunt echivalente funcțional, doar scrise în limbi diferite sau de sintaxă.
Apoi am învățat despre expresii booleene,
și un boolean este o valoare care este adevărat sau fals,
și de multe ori expresii booleene aici
du-te în interiorul unor condiții, astfel încât, dacă (x ≤ 5),
ei bine, am stabilit deja x = 5, astfel încât condiție este de gând să evalueze la adevărat.
Și dacă e adevărat, tot ce este sub cod condiție
va fi evaluat de către calculator, astfel încât șirul va fi imprimată
la iesirea standard, iar condiția termenul
se referă la ceea ce este în interiorul paranteze de declarația în cazul în care.
Amintiți-vă toți operatorii.
Amintiți-vă && sale și | | atunci cand incercam sa combina 2 sau mai multe condiții,
== = Nu pentru a verifica dacă 2 lucruri sunt egale.
Amintiți-vă că = este pentru atribuirea întrucât == este un operator boolean.
≤, ≥ i apoi finala 2 sunt auto-explicative.
O revizuire generală a logica booleană aici.
Și expresii booleene sunt de asemenea importante în bucle,
care vom trece peste acum.
Am învățat aproximativ 3 tipuri de bucle până în prezent în CS50, pentru, în timp ce, și de a face în timp.
Și e important să știți că în timp ce pentru cele mai multe scopuri
putem folosi de fapt, orice tip de bucla, în general,
există anumite tipuri de scopuri sau modele comune
în programare care suna în mod special pentru una dintre aceste bucle
care îl fac. cel mai eficient sau elegant să-l cod în acest fel
Să trecem peste ceea ce fiecare dintre aceste bucle tinde să fie utilizată pentru cele mai multe ori.
>> Într-o buclă pentru noi, în general, știm deja cum de multe ori dorim să itera.
Asta e ceea ce am pus în stare.
Pentru, i = 0, i <10, de exemplu.
Știm deja că vrem să facem ceva de 10 ori.
Acum, pentru o buclă în timp ce, în general, nu neapărat
știu de câte ori vrem bucla pentru a rula.
Dar stim un fel de condiții pe care vrem să-l
întotdeauna să fie adevărat sau fals să fie întotdeauna.
De exemplu, în timp ce este setat.
Să spunem că e o variabilă boolean.
În timp ce este adevărat că vrem cod pentru a evalua,
deci un pic mai mult extensibil, un pic mai general decât o buclă pentru,
dar orice pentru buclă poate fi, de asemenea, convertite într-o buclă în timp ce.
În cele din urmă, în timp ce face bucle, care pot fi mai dificila de a înțelege imediat,
sunt adesea folosite atunci când vrem să evalueze primul cod
înainte de prima dată când am verifica starea.
Un caz de utilizare comună pentru o face în timp ce bucla
este atunci când doriți să obțineți date introduse de utilizator, și știi că vrei să ceară utilizatorului
pentru intrare cel puțin o dată, dar în cazul în care nu vă dau de intrare bine imediat
doriți să păstrați cerându-le până când îți dă de intrare bun.
Asta e mai comună utilizare a unui buclă în timp ce-mi,
și să ne uităm la structura efectivă a acestor bucle.
Ele de obicei, mereu tendinta de a urma aceste modele.
>> Pe bucla de interior ai 3 componente:
initializare, de obicei, ceva de genul int i = 0 unde i este contra,
condiție, în cazul în care vrem să spunem rulați acest lucru pentru bucla atât timp cât această condiție deține încă,
ca i <10, și apoi în cele din urmă, update, care este modul în care ne incrementa
variabila contor la fiecare punct în buclă.
Un lucru comun pentru a vedea acolo este doar i + +,
ceea ce înseamnă incrementa i cu 1 de fiecare dată.
Ai putea face, de asemenea, ceva de genul i + = 2,
ceea ce înseamnă adaugă 2 la i de fiecare dată când merge prin bucla.
Și apoi face acest lucru doar se refera la orice cod care ruleaza de fapt, ca parte a buclei.
Și pentru o buclă în timp ce, de data aceasta avem de fapt de initializare in afara de bucla,
Deci, de exemplu, să spunem că încercăm să facem același tip de bucla ca tocmai am descris.
Ne-ar spune int i = 0 înainte de a începe bucla.
Apoi ne-am putea spune în timp ce eu <10 face acest lucru,
astfel încât același bloc de cod ca înainte,
și de această dată parte de actualizare a codului, de exemplu, i + +,
de fapt, merge în interiorul buclei.
Și, în sfârșit, pentru o faceți în timp ce, e similar cu bucla în timp ce,
dar trebuie să ne amintim că codul va evalua o dată
înainte de condiție se verifică, asa ca are sens mult mai mult
daca te uiti la ea, în scopul de sus în jos.
Într-o, în timp ce face bucla codul evaluează înainte de a te uiti chiar si la starea în timp ce
întrucât o buclă în timp ce, se verifică mai întâi.
Declarații și variabile.
Atunci când dorim să creăm o nouă variabilă ne-am dori să-l inițializa.
>> De exemplu, bara de int inițializează variabila bar,
dar nu da o valoare, astfel încât ceea ce este valoarea barul lui acum?
Noi nu știm.
Ar putea fi o anumită valoare gunoi care a fost stocat anterior în memorie acolo,
și nu doriți să utilizați ca variabilă
până când vom da de fapt, o valoare,
așa că am să declare aici.
Apoi ne-am inițializa să fie 42 de mai jos.
Acum, desigur, știm că acest lucru poate fi realizat pe o singură linie, int = 42 bar.
Dar, doar pentru a fi clar în mai multe etape care au loc,
declarația și inițializarea se intampla separat aici.
Aceasta se întâmplă pe un singur pas, iar urmatorul, int Baz = bar + 1,
această declarație de mai jos, care Baz incremente, asa ca la sfârșitul acestui bloc de cod
dacă am pentru a imprima valoarea de baz ar fi 44
pentru că ne pronunțăm și inițializa-l să fie de 1 bar>,
și apoi l-am incrementa o dată mai mult cu + +.
Ne-am dus peste acest scurt destul, dar e bine să aibă o
înțelegerea a ceea ce fire și evenimente sunt.
Am făcut acest lucru în principal, Scratch,
astfel încât vă puteți gândi de fire ca mai multe secvențe de cod
rulează în același timp.
În realitate, probabil că nu se execută, în același timp,
dar un fel de abstract ne putem gândi că în acest fel.
>> În Scratch, de exemplu, am avut mai multe sprites.
Ar putea fi de executare alt cod, în același timp.
S-ar putea fi mersul pe jos în timp ce celălalt spune ceva
într-o altă parte a ecranului.
Evenimentele sunt un alt mod de a separa logica
între diferitele elemente ale codului,
și în Scratch am putut pentru a simula evenimente folosind Broadcast,
și că, de fapt, atunci când primesc, nu atunci când aud,
dar în esență, este un mod de a transmite informații
de la un Sprite la alta.
De exemplu, poate doriți să transmită joc de peste,
și atunci când un alt joc de peste Sprite primește,
acesta răspunde într-un anumit fel.
Este un model important pentru a înțelege pentru programare.
Doar pentru a trece peste Săptămâna de bază 0, ceea ce am trecut peste pana acum,
să ne uităm la acest program C simplu.
Textul poate fi un pic mic de aici, dar voi trece peste asta foarte repede.
Suntem inclusiv 2 fisiere antet de la cs50.h de sus, și stdio.h.
Suntem definirea apoi o limită constantă numită să fie 100.
Suntem de punere în aplicare atunci funcția nostru principal.
Din moment ce nu folosim argumente din linia de comandă aici avem nevoie pentru a pune anulate
ca argumente pentru principal.
Ne vedem mai sus int principal. Asta e tipul de retur, deci întoarce 0 la partea de jos.
Și noi suntem folosind funcția de bibliotecă CS50 obține int
să solicite utilizatorului pentru intrare, și l-am păstra în această variabila x,
asa ne pronunțăm x de mai sus, și l-am inițializa cu x = GetInt.
>> Noi apoi atunci a verifica pentru a vedea dacă utilizatorul de intrare ne-a dat bine.
Dacă e TERMENUL ≥ vrem să se întoarcă un cod de eroare de 1 si imprima un mesaj de eroare.
Și, în sfârșit, în cazul în care utilizatorul ne-a dat bine de intrare
vom pătrat numărul și imprima acest rezultat.
Doar pentru a vă asigura că cei toate hit-acasă
puteți vedea etichetele de diferite părți ale codului aici.
Am menționat fișiere constante, antet.
Oh, int x. Asigurați-vă să ne amintim că este o variabilă locală.
Că acesta contrastează dintr-o variabilă globală, pe care vom vorbi despre
un pic mai târziu, în sesiunea de reexaminare,
și ne sunt de asteptare funcția de bibliotecă printf,
așa că, dacă nu am fi inclus fisierul header stdio.h
nu am putea să numim printf.
Și eu cred că săgeata a fost tăiat aici se indică spre d%,
care este un șir de formatare în printf.
Se spune imprima această variabilă ca d% un număr,.
Și asta este pentru săptămâna 0.
Acum, Lucas va continua.
Hei, băieți. Numele meu este Lucas.
Sunt un al doilea de studentie in cea mai buna casa de pe campus, Mather,
și am de gând să vorbesc un pic despre Săptămâna 1 și 2.1.
[Săptămâna 1 și 2,1!] [Lucas Freitas]
Ca Lexi spunea, atunci când am început traducerea codul de la zero la C
unul din lucrurile pe care am observat este că poți nu doar
scrie codul și rulați-l folosind un steag verde mai.
De fapt, va trebui să utilizați unele măsuri pentru a face programul tău C
deveni un fișier executabil.
Practic ceea ce faci atunci cand scrii un program care este
ai traduce ideea într-o limbă pe care o înțelege compilator poate,
asa ca atunci cand scrii un program în C
ceea ce faci este scris de fapt, ceva care compilatorul dvs. este de gând să înțeleagă,
și apoi compilator este de gând să traducem acest cod
în ceva care calculatorul dvs. va înțelege.
>> Și chestia este, computerul este de fapt foarte prost.
Computerul poate înțelege doar 0s și 1s,
astfel încât, de fapt, în primele calculatoare, de obicei, oamenii programat
folosind 0s și 1s, dar nu mai, mulțumesc lui Dumnezeu.
Noi nu trebuie să memoreze secventele de 0s și 1s
pentru o buclă pentru sau pentru o buclă în timp ce și așa mai departe.
De aceea avem un compilator.
Ce face un compilator este în esență traduce codul C,
în cazul nostru, într-o limbă pe care calculatorul dvs. va înțelege,
care este codul obiect, iar compilatorul pe care îl utilizăm
este numit zăngănit, astfel încât acesta este de fapt simbolul pentru zăngănit.
Când aveți programul dumneavoastră, trebuie să faci 2 lucruri.
În primul rând, trebuie să compilați programul dumneavoastră, și apoi ai de gând să rulați programul tău.
Pentru a compila programul dumneavoastră aveți o mulțime de opțiuni pentru a face acest lucru.
Prima dintre ele este de a face program.c zăngănit
în care programul este numele programului.
În acest caz, puteți vedea că spui doar "Hei, compila programul meu."
Tu nu spui "Vreau acest nume pentru programul meu", sau ceva de genul.
>> A doua opțiune este da un nume pentru program.
Se poate spune zăngănit-o și apoi numele pe care îl doriți
fișierul executabil care urmează să fie numit ca și apoi program.c.
Și puteți face, de asemenea, face programul, și să vedem cum, în primele 2 cazuri
Am pus C,. Și, în al treilea am doar programe?
Da, de fapt, nu ar trebui să pună c atunci când utilizați fac..
În caz contrar, compilatorul este, de fapt de gând să țip la tine.
Și, de asemenea, nu știu dacă voi aminti,
dar de multe ori am folosit, de asemenea, lcs50-sau-LM.
Care este numit de legătură.
Ea spune doar compilatorul pe care le va folosi aceste biblioteci acolo,
așa că, dacă doriți să utilizați cs50.h de fapt trebuie să tastați
zăngănit program.c-lcs50.
Dacă nu faci asta, compilatorul nu este de gând să știu
pe care îl utilizați aceste funcții în cs50.h.
Iar atunci când doriți să rulați programul tău aveți 2 opțiuni.
Dacă ați făcut program.c zăngănit nu ai da un nume pentru program.
Trebuie să-l rulați utilizând / a.out..
A.out este un nume standard care ofera zăngănit programul dumneavoastră dacă nu dau un nume.
În caz contrar, ai de gând să faci / programului., Dacă ați dat un nume la program,
și, de asemenea, dacă ai făcut-o face programul de numele pe care un program este mergi la a lua
este deja va fi programat același nume ca fisierul c.
Apoi am vorbit despre tipurile de date și de date.
>> Practic tipuri de date sunt același lucru ca și cutii mici pe care le folosesc
pentru a stoca valori, deci tipuri de date sunt de fapt la fel ca pokemoni.
Ei vin în toate mărimile și tipurile.
Nu știu dacă asta are sens analogie.
Dimensiunea de date, de fapt depinde de arhitectura mașinii.
Toate dimensiunile de date pe care am de gând să arate aici
sunt de fapt pentru o mașină de 32-biți, care este cazul aparatului nostru,
dar dacă sunteți de codificare de fapt, Mac-ul sau într-un Windows, de asemenea,
probabil ai de gând să aibă o mașină de 64-biți,
astfel amintiți-vă că dimensiunile de date pe care am de gând să arate aici
sunt pentru masina de 32-biți.
Primul pe care am vazut a fost un int,
care este destul de simplă.
Puteți utiliza int pentru a stoca un număr întreg.
Am văzut, de asemenea, caracterul, char.
Dacă doriți să utilizați o literă sau un simbol mic esti, probabil, de gând să utilizeze un char.
O char are 1 octet, ceea ce înseamnă 8 biți, cum ar fi spus Lexi.
Practic, avem un tabel ASCII care are 256
combinații posibile de 0s și 1s,
și apoi când tastați un char se va traduce
personaj care intrări un numar pe care îl au în tabelul ASCII, cum a spus Lexi.
Avem, de asemenea, float, pe care le folosim pentru a stoca numere zecimale.
Dacă doriți să alegeți 3.14, de exemplu, ai de gând să utilizați un flotor
sau un dublu care are o precizie mai mult.
Un flotor are 4 octeți.
Un dublu are 8 octeți, astfel încât singura diferenta este de precizie.
Avem, de asemenea, o lungă care este folosit pentru numere întregi,
și puteți vedea pentru o mașină de 32-biți un int și un lung au aceeași dimensiune,
așa că nu prea are sens să utilizeze un lung într-o mașină de 32-biți.
>> Dar, dacă utilizați o mașină de Mac și 64-biți, de fapt, un lung are dimensiune 8,
așa că într-adevăr depinde de arhitectura.
Pentru masina de 32-bit, nu are sens să utilizeze un lung adevărat.
Și apoi un lung timp, pe de altă parte, are 8 octeți,
așa că este foarte bine, dacă doriți să aveți un număr întreg mai mare.
Și, în sfârșit, avem string, care este de fapt un char *,
care este un pointer la un char.
Este foarte ușor să cred că mărimea șir va fi
numărul de caractere pe care le aveți acolo,
dar, de fapt char * sine
are dimensiunea unui pointer la un char, care este de 4 octeți.
Dimensiunea unui char * este de 4 octeți.
Nu contează dacă aveți un cuvânt mic sau o scrisoare sau ceva.
O să fie de 4 octeți.
Am aflat, de asemenea, un pic despre turnare,
Deci, după cum puteți vedea, dacă aveți, de exemplu, un program care spune
int x = 3 si apoi printf ("% d", x / 2)
Știți ce se întâmplă pentru a imprima pe ecran?
>> Cineva >> [Studenții] 2?.
1. >> 1, da.
Când faci 3/2 se va obține 1,5,
dar din moment ce suntem folosind un întreg se va ignora partea zecimală,
și ai de gând să aibă 1.
Dacă nu vrea să se întâmple ceea ce se poate face, de exemplu,
se declară un flotor y = x.
Atunci x, care utilizate pentru a fi 3 este acum de gând să fie în y 3.000.
Și apoi puteți imprima y / 2.
De fapt, ar trebui să am un 2. acolo.
Se va face 3.00/2.00,
și vei primi 1.5.
Și avem această f 0.2 doar pentru a cere pentru 2 unități zecimal în partea zecimală.
Dacă aveți f 0.3 se va avea de fapt 1.500.
Dacă e 2, aceasta va fi 1.50.
Avem, de asemenea, acest caz aici.
Dacă veți face float x = 3.14 si apoi x printf
ai de gând să obțineți 3.14.
Și dacă faci x = int de x,
ceea ce înseamnă tratarea x ca un int și să imprimați x acum
ai de gând să aibă 3.00.
Are vreun sens?
Pentru că te tratează primul x ca un întreg, astfel încât să te ignora partea zecimală,
și apoi imprimați x.
Și, în sfârșit, puteți face acest lucru,
int x = 65, iar apoi să declare un char c = x,
și apoi, dacă imprimați c tu esti de fapt mergi la a lua
A, deci practic ce faci aici
este traducerea în întreg caracterul,
la fel ca tabelul ASCII face.
Am vorbit și despre operatorii de matematica.
Cele mai multe dintre ele sunt destul de simple, așa +, -, *, /,
și, de asemenea, am vorbit despre mod, care este restul de o divizie a 2 numere.
Dacă aveți 10% 3, de exemplu,
aceasta înseamnă împartă 10 cu 3, și ceea ce este restul?
O să fie de 1, asa ca este de fapt foarte util pentru o multime de programe.
Pentru Vigenere și Cezar sunt destul de sigur că voi toți băieți utilizat mod.
Despre operatori de matematica, să fie foarte atenți atunci când combinarea * și /.
>> De exemplu, dacă faci (3/2) * 2 Ce ai de gând să obțineți?
[Studenții] 2.
Da, 2, deoarece 3/2 va fi 1.5,
dar din moment ce faci operațiuni între 2 numere întregi
tu de fapt, doar de gând să ia în considerare 1,
și apoi 1 * 2 va fi 2, asa ca fii foarte, foarte atent
atunci când faci aritmetica cu numere întregi, deoarece
s-ar putea obține că 2 = 3, în acest caz.
Și, de asemenea, să fie foarte atent cu privire la prioritate.
Ar trebui să utilizați, de obicei, între paranteze pentru a fi sigur că știi ce faci.
Unele comenzi rapide utile, desigur, una este i + + sau i + = 1
sau folosind + =.
Acesta este același lucru ca și face i = i + 1.
Puteți face, de asemenea, i - sau i - = 1,
ceea ce este același lucru ca i = i -1,
Ceva ce voi folosi o mulțime de bucle în, cel puțin.
De asemenea, pentru *, dacă utilizați * = și dacă ai face, de exemplu,
i * = 2 este același lucru cu a spune i = i * 2,
și același lucru pentru diviziune.
Dacă veți face i / = 2 e același lucru ca i = I / 2.
>> Acum, despre funcțiile.
Voi aflat că funcțiile sunt o strategie foarte buna pentru a salva code
în timp ce programarea, deci, dacă doriți să efectuați aceeași sarcină
codul nou și din nou, probabil doriți să utilizați o funcție
doar astfel încât să nu trebuie să copiați și să inserați codul de peste si peste din nou.
De fapt, este o funcție principală, și când am să vă arate formatul unei funcții
ai de gând să văd că este destul de evident.
Noi folosim, de asemenea, funcții din unele biblioteci,
de exemplu, printf, GetIn, care este de la bibliotecă CS50,
și alte funcții, cum ar fi toupper.
Toate aceste funcții sunt de fapt puse în aplicare în alte biblioteci,
și atunci când ați pus acele fișiere lega la începutul programului dvs.
vrei să spui că poate, te rog da-mi codul pentru aceste funcții
așa că nu trebuie să le pună în aplicare de unul singur?
Și puteți scrie, de asemenea, propriile funcții, astfel încât atunci când veți începe programarea
îți dai seama că bibliotecile nu au toate funcțiile de care aveți nevoie.
Pentru PSET ultima, de exemplu, am scris trage, goana, și de căutare,
și e foarte, foarte important să fie în măsură să scrie funcții
deoarece acestea sunt utile, iar noi să le utilizeze tot timpul în programare,
și-l salvează o mulțime de cod.
Formatul unei functii este aceasta.
Avem de tip întoarcere la început. Care este tipul de retur?
E doar atunci când funcția dumneavoastră este de gând să se întoarcă.
Dacă aveți o funcție, de exemplu, factorial,
care este de gând să calculeze un factorială a unui număr întreg,
Probabil că va reveni, de asemenea, un număr întreg.
Apoi, tipul de revenire va fi int.
Printf are de fapt un gol tip de retur
pentru că nu te întoarce nimic.
Sunteți de imprimare doar lucrurile la ecranul
si renunti funcția după aceea.
Apoi, aveți numele functiei pe care le puteți alege.
Tu ar trebui să fie un pic rezonabil, ca să nu alegi un nume ca xyz
sau ca x2f.
Încercați să facă un nume care are sens.
>> De exemplu, dacă e factorială, spune factorială.
Daca este o funcție care este de gând să atragă ceva, denumiți-l trage.
Și apoi avem parametri, care sunt, de asemenea, numite argumente
care sunt ca resursele de care are nevoie funcția
din codul dvs. pentru a îndeplini sarcina.
Dacă doriți pentru a calcula factorialul unui număr
probabil ai nevoie de a avea un număr pentru a calcula o factorial.
Unul dintre argumentele pe care ai de gând să aibă este numărul însuși.
Și apoi o să facă ceva și să se întoarcă valoarea de la sfârșitul
excepția cazului în care este o funcție de vid.
Să vedem un exemplu.
Dacă vreau să scrie o funcție care însumează toate numerele într-o matrice de întregi,
în primul rând, tipul de revenire va fi int
pentru că am un tablou de întregi.
Și apoi am de gând să aibă numele funcției ca sumArray,
și apoi se va lua matrice în sine, pentru a nums int,
și apoi lungimea de matrice, așa că știu câte numere trebuie să însumați.
Atunci am pentru a inițializa o sumă variabilă numită, de exemplu, la 0,
și de fiecare dată când văd un element în matrice ar trebui să-l adauge la suma, așa că am făcut o buclă pentru.
La fel ca Lexi a spus, ai făcut int i = 0, i <lungime și i + +.
Și pentru fiecare element în matrice am facut suma intre + = nums [i],
si apoi m-am întors suma, asa ca este foarte simplu, și-l salvează o mulțime de cod
dacă utilizați această funcție o multime de ori.
Apoi am luat o privire la condițiile.
Avem în cazul în care, altfel, și în cazul în care altcineva.
Să vedem ce este diferența dintre cele.
Aruncati o privire la aceste 2 coduri. Care este diferența dintre ele?
Prima a-practic codurile vreau să spun
dacă un număr este de +, -, sau 0.
Prima spune dacă e> 0, atunci e pozitiv.
Dacă e = cu 0, atunci e 0, iar dacă e <0 atunci e negativ.
>> Și cealaltă este de a face în cazul în care, în cazul în care altcineva, altceva.
Diferența dintre cele două este că aceasta este, de fapt de gând să
verificați dacă> 0, <0 sau = 0 de trei ori,
așa că, dacă aveți numărul 2, de exemplu, o să vină aici și să spun
în cazul în care (x> 0), și-l va spune da, așa că am imprima pozitiv.
Dar, chiar dacă știu că e> 0 și nu va fi 0 sau <0
Sunt încă de gând să faci este 0, este <0,
așa că mă duc de fapt, în interiorul fondurilor de investiții care nu am avea de a
pentru că deja știu că nu va satisface oricare dintre aceste condiții.
Eu pot folosi în cazul în care, în cazul în care altcineva, altceva declarație.
Este practic spune că dacă x = 0 I imprima pozitiv.
Dacă nu e, am de gând pentru a testa, de asemenea, acest lucru.
Dacă e 2 nu am de gând să fac asta.
Practic, dacă am avut x = 2 v-ar spune
în cazul în care (x> 0), da, așa imprimați acest lucru.
Acum, că știu că e> 0 și că îndeplinită în cazul în care prima
Eu nu sunt chiar de gând să rulați acest cod.
Codul rulează mai rapid, de fapt, de 3 ori mai repede dacă folosiți asta.
Am învățat, de asemenea, despre și i sau.
Eu nu am de gând să treacă prin acest lucru, deoarece Lexi vorbit deja despre ele.
E doar && si | | operatorului.
>> Singurul lucru pe care voi spune este să fie atenți atunci când avea 3 condiții.
Utilizați paranteze pentru că este foarte confuz atunci când aveți o afecțiune
și un alt unul sau altul.
Utilizați paranteze doar pentru a fi siguri că condițiilor sens
deoarece, în acest caz, de exemplu, vă puteți imagina că
ar putea fi prima condiție și unul sau altul
sau cele 2 condițiile combinate într-o și
sau o treime, astfel încât să fie doar atent.
Și, în sfârșit, am vorbit despre switch-uri.
Un comutator este foarte util atunci când aveți o variabilă.
Să presupunem că aveți o variabilă ca n
care poate fi 0, 1, sau 2, precum și pentru fiecare dintre aceste cazuri,
ai de gând să efectuați o sarcină.
Se poate spune comuta variabilă, și aceasta indică faptul că
valoarea, atunci este ca și cum valoare1 am de gând să fac asta,
si apoi m-am rupe, ceea ce înseamnă că nu am de gând să se uite la oricare dintre celelalte cazuri
pentru că am mulțumit deja acest caz,
și apoi valoare2 și așa mai departe, și am, de asemenea, pot avea un comutator implicit.
Asta înseamnă că în cazul în care nu îndeplinește niciuna dintre cazurile pe care le-am avut
că am de gând să fac altceva, dar asta e optional.
Asta e tot pentru mine. Acum, hai să Tommy.
Bine, asta va fi Săptămâna 3-ish.
Acestea sunt unele dintre subiectele vom fi acoperind, cripto, domeniul de aplicare, matrice, et cetera.
Doar un cuvânt rapid pe cripto. Noi nu suntem de gând să ciocan această casă.
>> Am făcut acest lucru în PSET 2, dar pentru testul asigurați-vă că știți diferența
între cifrul Cezar și cifrul Vigenere,
cum atât de cei care lucrează cifrurilor și ceea ce e ca pentru a cripta
și decripta text folosind cele 2 cifre.
Amintiți-vă, cifrul lui Cezar se rotește pur și simplu, fiecare caracter cu aceeași sumă,
asigurându-vă că Mod de numărul de litere din alfabet.
Și cifrul Vigenere, pe de altă parte, se rotește fiecare caracter
de o sumă diferită, astfel încât mai degrabă decât a spune
fiecare rotit de caractere cu 3 Vigenere se vor roti fiecare caracter
cu o sumă diferită în funcție de cuvinte cheie unele
în cazul în care fiecare literă din cuvântul cheie reprezintă o anumită cantitate diferită
pentru a roti textul clar de.
Să vorbim mai întâi despre domeniul de aplicare variabilă.
Exista 2 tipuri diferite de variabile.
Avem variabile locale, iar acestea urmează să fie definite
în afara de principal sau în afara orice funcție sau bloc,
și acestea vor fi accesibile oriunde în programul tău.
Dacă aveți o funcție și în care funcția este o buclă în timp ce
variabila mare la nivel mondial este accesibil peste tot.
O variabilă locală, pe de altă parte, este luneta la locul unde este definit.
>> Dacă aveți o funcție aici, de exemplu, avem această funcție g,
și în interiorul lui G este o variabilă numită aici y,
și asta înseamnă că aceasta este o variabilă locală.
Chiar dacă această variabilă se numește y
și această variabilă este numit Y aceste 2 functii
nu au nici o idee despre ceea ce variabile reciproc locale sunt.
Pe de altă parte, aici ne spunem int x = 5,
și acest lucru este în afara domeniului de aplicare a oricărei funcții.
E în afara domeniului de aplicare al principal, astfel încât aceasta este o variabilă globală.
Asta înseamnă că în interiorul acestor 2 funcții atunci când spun x - sau x + +
Mă accesarea x același prin care aceasta y și y sunt variabile acest diferite.
Asta e diferența dintre o variabilă globală și o variabilă locală.
În ceea ce privește design-ul este în cauză, uneori este, probabil, o idee mai bună
să păstreze variabilele locale ori de câte ori pot, eventual,
din moment ce o gramada de variabile globale poate obține cu adevărat confuz.
Dacă aveți o grămadă de funcții modificarea tuturor același lucru
s-ar putea uita ceea ce în cazul în care această funcție accidental modifică acest nivel global,
și această altă funcție nu știe despre asta,
și se ajunge destul de confuz cum veți obține mai mult cod.
Păstrarea variabile locale ori de câte ori pot, eventual,
este designul doar bine.
Matrice, amintiți-vă, sunt pur și simplu liste de elemente de același tip.
In interiorul IC nu poate avea o listă cum ar fi 1, 2.0, salut.
Noi chiar nu pot face asta.
>> Când ne-am declara o matrice în C toate elementele trebuie să fie de același tip.
Aici am o serie de 3 numere întregi.
Aici am lungimea de matrice, dar dacă eu sunt doar de declarare în această sintaxă
în cazul în care am specifica ce toate elementele sunt nu am nevoie de acest punct de vedere tehnic 3.
Compilatorul este destul de inteligent să ne dăm seama cât de mare ar trebui să fie matrice.
Acum, când vreau să obțineți sau să setați valoarea unei matrice
aceasta este sintaxa pentru a face asta.
Acest lucru va modifica de fapt, al doilea element al matricei, deoarece, amintiți-vă,
Numerotarea începe de la 0, nu de la 1.
Dacă vreau să citesc această valoare pot spune ceva de genul: int x = array [1].
Sau dacă vreau să setați această valoare, la fel ca fac aici,
Eu pot să spun matrice [1] = 4.
Acel timp accesarea elemente de indicele lor
sau poziția lor, sau în cazul în care acestea sunt în matrice,
și că listarea începe de la 0.
Putem avea, de asemenea, tablouri de matrice,
și aceasta se numește o matrice multi-dimensional.
Când vom avea un tablou multi-dimensional
ceea ce înseamnă că poate avea ceva de genul rânduri și coloane,
și aceasta este doar o modalitate de a vizualiza acest lucru sau gândire despre el.
Când am o matrice multi-dimensional, care înseamnă am de gând să înceapă nevoie
mai mult de 1 index, deoarece în cazul în care am o rețea
doar că ceea ce ești în rând nu ne dea un număr.
Asta într-adevăr doar de gând să ne dea o listă de numere.
Să spunem că am această matrice aici.
Am o matrice numita grilă, și vreau să spun e 2 rânduri și 3 coloane,
și astfel aceasta este o modalitate de a vizualiza acesta.
Când am spus că vreau să obțineți element la [1] [2]
ceea ce înseamnă că, deoarece acestea sunt primele rânduri și apoi coloane
Am de gând să sari la rândul 1, deoarece am spus 1.
>> Apoi, am de gând să vin aici în coloana 2, și am de gând pentru a obține valoarea 6.
Face sens?
Multi-dimensionale matrice, amintește-ți, sunt punct de vedere tehnic doar o serie de tablouri.
Putem avea tablouri de tablouri de matrice.
Noi putem continua, dar de fapt un mod de a gândi despre
modul în care acest lucru este prevăzut afară și ceea ce se întâmplă este să-l vizualizeze
într-o rețea ca asta.
Când ne-am trece la funcții de matrice, au de gând să se comporte
un pic diferit decât atunci când vom trece variabile regulate la funcții
ca trecerea unui int sau un flotor.
Când ne-am trece într-un tip int sau char sau la oricare dintre aceste alte date
am luat doar o privire la cazul în funcția modifică
valoarea acelei variabile care schimbarea nu se va propaga în sus
pentru funcția de asteptare.
Cu o matrice, pe de altă parte, faptul că se va întâmpla.
Dacă aș trece într-o matrice la unele funcții și că funcția schimbă unele din elementele,
când am venit înapoi până la funcția pe care a numit-
matrice mea este acum va fi diferit, și de vocabular pentru că
matrice este sunt transmise prin referință, după cum vom vedea mai târziu.
Acest lucru este legat de modul în care munca indicii, în cazul în care aceste tipuri de bază de date,
pe de altă parte, sunt transmise prin valoare.
>> Ne putem gândi că, în calitate face o copie a unor variabilă și apoi trece în copie.
Nu contează ceea ce facem cu acea variabilă.
Funcția de asteptare nu va fi conștienți de faptul că acesta a fost schimbat.
Matricile sunt doar un pic diferit în această privință.
De exemplu, după cum tocmai am văzut, principalul este pur și simplu o funcție
care poate lua în 2 argumente.
Primul argument pentru funcția principală este argc, sau numărul de argumente,
și al doilea argument este numit argv,
și acestea sunt valorile efective ale acestor argumente.
Să spunem că am un program numit this.c,
și spun asta fac, și am de gând să ruleze acest lucru la linia de comandă.
Acum, pentru a trece în unele argumente pentru a programul meu numit aceasta,
Am putea spune ceva de genul / aceasta este CS 50..
Aceasta este ceea ce ne imaginăm pe David să facă în fiecare zi la terminal.
Dar acum interiorul funcția principală a acestui program
are aceste valori, deci argc este 4.
Ar putea fi un pic confuz, deoarece într-adevăr suntem doar în trecere în cs este 50.
Asta e doar 3.
Dar amintiți-vă că primul element al argv sau primul argument
este numele funcției în sine.
Deci asta înseamnă că avem 4 lucruri aici,
și primul element va fi / aceasta..
Iar acest lucru va fi reprezentat ca un șir.
Apoi, restul elementelor sunt ceea ce am tastat în după numele programului.
Deci, la fel ca o parte, așa cum am văzut, probabil, în PSET 2,
amintiți-vă că șirul 50 este ≠ întregul 50.
Deci nu putem spune ceva de genul, 'int x = argv 3. "
>> Asta nu doar va face sens, deoarece aceasta este un șir, iar acesta este un număr întreg.
Deci, dacă doriți să faceți conversia intre cele 2, amintiți-vă, vom
această funcție magică numită atoi.
Care ia un șir și returnează întreg reprezentat în interiorul acelui șir.
Deci, asta e o greșeală ușor de a face pe test,
doar gândindu-se că aceasta va fi în mod automat tipul corect.
Dar știu doar că acestea vor fi întotdeauna siruri de caractere
chiar dacă șirul conține numai un număr întreg sau un caracter sau un flotor.
Deci, acum să vorbim despre timpul de funcționare.
Când vom avea toate aceste algoritmi care fac toate aceste lucruri nebunești,
devine cu adevărat util să punem întrebarea: "Cât timp nu se iau?"
Noi reprezentăm că, odată cu ceva numit notația asimptotică.
Deci asta înseamnă că - ei bine, hai să spunem că da algoritmul nostru
unele foarte, foarte, foarte mare de intrare.
Dorim să punem întrebarea, "Cât timp se merge să ia?
Câți pași va lua algoritmul nostru pentru a rula
în funcție de mărimea de intrare? "
Deci prima cale putem descrie timpul rula este cu mare O.
Și acest lucru este nostru cel mai rău caz timp de funcționare.
Deci, dacă vrem să sortați o matrice, și ne da algoritmul nostru o matrice
asta e în ordine descrescătoare atunci când ar trebui să fie în ordine crescătoare,
care va fi cel mai rau caz.
Aceasta este superioară nostru legat în durata maximă a timpului algoritmului nostru va lua.
Pe de altă parte, această Ω este de gând să descrie mai bun caz timp de funcționare.
Deci, dacă am da-o matrice deja sortate unui algoritm de sortare,
Cât timp va dura pentru a sorta?
Și aceasta, apoi, descrie o limită inferioară pe timpul de funcționare.
Deci, aici sunt doar cateva cuvinte care descriu uneori comune de funcționare.
Acestea sunt, în ordine crescătoare.
Cel mai rapid timp de funcționare avem este numit constantă.
>> Asta înseamnă că indiferent de cât de multe elemente pe care le dau algoritmului nostru,
indiferent de cât de mare este gama noastră, sortarea acestora
sau de a face tot ce ne facem să matrice va avea întotdeauna aceeași cantitate de timp.
Deci, putem reprezenta că doar cu un 1, care este o constantă.
Noi, de asemenea, sa uitat la momentul execuției logaritmică.
Deci, ceva de genul binar de căutare este logaritmică,
în cazul în care am tăiat în jumătate problema de fiecare dată
și apoi lucrurile devin doar mai mare de acolo.
Și dacă sunteți scris vreodată o O, de orice algoritm factorial,
probabil că nu ar trebui să considere acest lucru ca slujba ta zi.
Când ne-am compara ori de funcționare este important să păstrați în minte aceste lucruri.
Deci, dacă am un algoritm care este O (n), și altcineva
a un algoritm O (2n), acestea sunt de fapt asimptotic echivalente.
Deci, dacă ne imaginăm n sa fie un numar mare ca eleventy miliarde de euro:
asa ca atunci cand suntem fata eleventy miliarde de euro la ceva de genul eleventy miliarde de euro + 3,
dintr-o dată că trei nu face într-adevăr o mare diferență mai.
De aceea vom începe în considerare aceste lucruri să fie echivalente.
Deci lucrurile ca aceste constante de aici, nu e 2 x asta, sau adăugarea de un 3,
Acestea sunt doar constante, iar acestea sunt de gând să scadă în sus.
Deci, de aceea toate aceste 3 din timpul de functionare sunt la fel cu a spune că sunt O (n).
În mod similar, în cazul în care avem de 2 ori de alte rulare, să zicem O (n + 2n ² ³), putem adăuga
+ N, + 7, și apoi avem un alt timpului de funcționare asta e doar O (n ³).
din nou, acestea sunt același lucru, deoarece acestea - acestea nu sunt aceleași.
Acestea sunt aceleași lucruri, îmi pare rău. Deci, acestea sunt aceleași, deoarece
acest ³ n este de gând să domine această ² 2n.
>> Ceea ce nu este același lucru este în cazul în care ne-am fugi de ori ca O (n ³) și O (n ²)
deoarece acest ³ n este mult mai mare decât această ² n.
Deci, dacă avem exponentii, brusc începe să conteze asta,
dar atunci când suntem doar de-a face cu factori de cum suntem noi aici,
atunci nu va conta, deoarece acestea sunt doar de gând să renunțe la.
Să aruncăm o privire la unele dintre algoritmii care le-am vazut pana acum
și să vorbească despre timpul de functionare a acestora.
Primul mod de a privi pentru un număr într-o listă, pe care am văzut, era de căutare liniară.
Și punerea în aplicare a liniară căutare este super simplu.
Noi avem doar o listă, și ne vom uita la fiecare element din listă
până când vom găsi numărul căutăm.
Deci asta înseamnă că, în cel mai rău caz, acest O (n).
Și cel mai rău caz, ar putea fi aici, în cazul în care elementul este
ultimul element, apoi utilizând căutarea liniară trebuie să ne uităm la fiecare element
până când vom ajunge la ultimul, în scopul de a ști că acesta a fost de fapt în listă.
Noi nu putem oferi doar până la jumătate și spune, "Este, probabil, nu acolo."
Cu căutare liniară trebuie sa ne uitam la toată chestia.
Cel mai bun timp la caz funcționare, pe de altă parte, este constant
deoarece, în cel mai bun caz elementul căutăm este doar prima din listă.
Așa că o să ne ia exact 1 pas, indiferent cât de mare este lista
dacă suntem în căutarea pentru primul element de fiecare dată.
>> Astfel încât atunci când veți căuta, amintiți-vă, aceasta nu impune ca lista noastră să fie sortate.
Pentru că suntem pur și simplu de gând să se uite peste fiecare element unic, și nu contează cu adevărat
ce ordine aceste elemente sunt inch
Un algoritm de căutare mai inteligent este ceva de genul căutare binară.
Amintiți-vă, punerea în aplicare a binar de căutare este atunci când ai de gând să
Ți privirea de la mijlocul listei.
Și pentru că ne uităm la mijloc, avem nevoie ca lista este sortată
sau altfel nu știm unde mijloc este, și trebuie să privim peste
întreaga listă să-l găsească, și apoi la acel moment ne pierdem doar de timp.
Deci, dacă avem o listă sortată și vom găsi la mijloc, vom compara mijloc
la elementul căutăm.
Dacă e prea mare, atunci putem uita jumătatea din dreapta
pentru că știm că, dacă elementul nostru este deja prea mare
și totul la dreapta acestui element este chiar mai mare,
atunci nu avem nevoie să te uiți acolo.
În cazul în care, pe de altă parte, în cazul în care elementul nostru este prea mic,
știm totul la stânga acelui element este, de asemenea, prea mic,
așa că nu prea are sens să se uite acolo, fie.
În acest fel, cu fiecare pas și de fiecare dată când ne uităm la mijlocul listei,
am de gând să taie în jumătate problema noastră, deoarece brusc știm
o grămadă de numere care nu pot fi cel pe care îl căutăm.
>> În pseudocod acest lucru ar arata ceva de genul asta,
și pentru că suntem tăierea lista in jumatate de fiecare dată,
noastre cel mai rău caz salturi în timp curgă de la liniar la logaritmică.
Atât de brusc, avem log-in etape, în scopul de a găsi un element într-o listă.
Cel mai bun timp la caz funcționare, însă, este încă constanta
pentru că acum, hai să spunem că elementul-l căutăm este
întotdeauna mijlocul exactă a lista inițială.
Astfel încât să putem crește lista noastră la fel de mare ca vrem, dar dacă elementul căutăm este la mijloc,
apoi se doar de gând să ne ia un pas.
Deci de asta suntem O (log n) si Ω (1) sau constantă.
Să fugi de fapt, binar de căutare pe această listă.
Deci, haideți să spunem că suntem în căutarea pentru elementul 164.
Primul lucru pe care o vom face este să găsească punctul de mijloc al acestei liste.
Pur și simplu așa se întâmplă că punctul de mijloc este de gând să scadă între aceste 2 cifre,
așa că hai să spunem doar că arbitrar, de fiecare dată punctul de mijloc se încadrează între 2 numere,
hai rotunji doar până.
Trebuie doar să ne asigurăm că facem asta în fiecare pas din drum.
Așa că vom rotunji în sus, și vom spune că 161 este mijlocul listei noastre.
So 161 <164, și fiecare element la stânga de 161
De asemenea, este <164, astfel încât știm că nu ne va ajuta deloc
pentru a începe căutarea aici, deoarece elementul căutăm nu poate fi acolo.
Deci, ce putem face este că putem uita doar despre faptul că jumătate din stânga întreaga listă,
iar acum ia în considerare numai de dreptul de departe 161.
>> Deci, din nou, aceasta este punctul de mijloc; să rotunjească doar până.
Acum 175 este prea mare.
Deci știm că nu o să ne ajute în căutarea aici sau aici,
astfel încât să putem arunca doar că distanță, și în cele din urmă vom lovi 164.
Orice întrebări cu privire la căutare binară?
Să trecem de la căutarea printr-o listă deja sortate
de a lua de fapt o listă de numere în orice ordine
și de a face această listă, în ordine crescătoare.
Algoritmul prima ne-am uitat la a fost numit de sortare cu bule.
Și acest lucru ar fi mai simplu de algoritmi le-am văzut.
Sortare bubble spune că atunci când oricare 2 elemente din interiorul listă sunt din loc,
adică există un număr mai mare în partea stângă a unui număr mai mic,
atunci vom pentru a le schimba, pentru că înseamnă că lista va fi
"Mai sortati" decât a fost înainte.
Și noi suntem doar de gând să continue acest proces nou și din nou și din nou
până când în cele din urmă un fel de elemente cu bule de locația lor corectă și avem o listă sortată.
>> Timpul de functionare a acestei va fi O (n ²). De ce?
Ei bine, pentru că, în cel mai rău caz, vom lua fiecare element, și
vom ajunge comparând-o la fiecare alt element din listă.
Dar, în cel mai bun caz, avem o listă deja sortate, cu bule de sortare's
doar de gând să treacă prin o dată, spune "Nu. Nu am face orice swap-uri, așa că am terminat."
Deci, avem un timp mai bun caz de funcționare a Ω (n).
Să ruleze un fel balon pe o listă.
Sau mai întâi, să ne uităm doar la un pseudocod foarte repede.
Vrem să spunem că doriți să urmăriți de, în fiecare iterație a buclei,
ține evidența dacă este sau nu ne-am schimbat elemente.
Deci motivul pentru care este, vom opri atunci când nu ne-am schimbat elemente.
Deci, la începutul buclei noastre nu am schimbat nimic, așa că vom spune că e fals.
Acum, vom merge prin listă și compara elementul i pentru a elementului i + 1
și dacă este cazul în care există un număr mai mare în partea stângă a unui număr mai mic,
atunci suntem doar de gând să le schimba.
>> Și apoi vom aminti că am schimbat un element.
Asta înseamnă că trebuie să treacă prin lista de cel puțin 1 de mai mult timp
deoarece starea în care ne-am oprit este atunci cand intreaga lista este deja sortat,
ceea ce înseamnă că nu am făcut nici un swap.
Deci, de aceea starea noastră aici este "în timp ce unele elemente au fost schimbate."
Așa că haideți să ne uităm acum doar la acest rulează pe o listă.
Am lista de 5,0,1,6,4.
Sortare Bubble este de gând să înceapă tot drumul la stânga, și se va compara
elementele i, astfel încât cifra 0 la i + 1, care este elementul 1.
Se va spune, bine 5> 0, dar acum 5 este la stânga,
așa că am nevoie pentru a schimba 5 și 0.
Când le-am schimba, dintr-o dată I a lua această listă diferită.
Acum 5> 1, deci vom pentru a le schimba.
5 nu este> 6, așa că nu trebuie să facem nimic aici.
Dar 6> 4, așa că trebuie să schimb.
Din nou, avem nevoie pentru a rula prin intreaga lista a descoperi în cele din urmă
că acestea sunt în afara ordinii; le schimba,
și în acest moment avem nevoie pentru a rula prin lista de mai mult timp 1
pentru a vă asigura că totul este în ordine său, și în acest fel bubble punct a terminat.
Un algoritm diferit pentru a lua unele elemente și sortarea lor este un fel de selecție.
Ideea din spatele fel de selecție este că vom construi o parte din lista de sortat
1 element la un moment dat.
>> Și modul în care vom face acest lucru este prin construirea segmentului stângă a listei.
Și, practic, în fiecare - pe fiecare pas, vom lua cel mai mic element care le-am lăsat
care nu a fost încă sortate, iar noi o să-l mute în acest segment sortate.
Asta înseamnă că trebuie să găsim continuu elementul minim nesortate
și să ia apoi că elementul minim și swap cu orice
cea mai din stânga element care nu este sortat.
Timpul a alerga de acest lucru se întâmplă pentru a fi O (n ²), deoarece, în cel mai rău caz,
avem nevoie pentru a compara fiecare element unic pentru fiecare alt element.
Pentru că noi spunem că, dacă începem de la jumătatea stângă a listei, avem nevoie de
pentru a merge prin segmentul dreptul de intreaga pentru a gasi cel mai mic element.
Și apoi, din nou, avem nevoie pentru a trece peste întregul segment drept și
continui peste care de peste si peste si peste din nou.
Asta va fi n ². Vom avea nevoie de o buclă de interior de un altul pentru buclă
ceea ce sugerează ² n.
În gândul cel mai bun caz, să spunem că da o listă deja sortate;
de fapt, noi nu facem mai bine decât ² n.
Pentru ca un fel de selecție nu are nici o modalitate de a ști că
elementul minim este doar cea pe care am întâmplă să se uite la.
Este încă nevoie să se asigure că aceasta este de fapt minim.
>> Și singura modalitate de a vă asigura că este minim, folosind acest algoritm,
este să se uite la fiecare element din nou.
Deci de fapt, dacă-l dau - daca dai un fel de selecție o listă deja sortate,
nu se va face nici mai bine decât dându-i o listă care nu este încă sortate.
Apropo, dacă se întâmplă să fie cazul în care ceva este O (ceva)
și omega a ceva, putem spune doar mai succint că e ceva de θ.
Deci, dacă vedeți că veni oriunde, asta e ceea ce inseamna ca doar.
>> Dacă ceva este teta de n ², acesta este atât de mare O (n ²) și Ω (n ²).
Deci, cel mai bun caz și cel mai rău caz, aceasta nu face o diferență,
algoritm este de gând să facă același lucru de fiecare dată.
Deci, asta este ceea ce pseudocod pentru selectarea fel ar putea arăta.
Suntem practic de gând să spun că vreau să itera peste lista
de la stânga la dreapta, și la fiecare iterație a buclei, am de gând să se mute
elementul minim în această parte a listei sortate.
Și odată ce am muta ceva acolo, nu mai am nevoie să se uite la acest element din nou.
Pentru că de îndată ce am schimba un element in pentru a segmentul stângă a listei, se sortate
pentru că facem totul în ordine crescătoare, prin utilizarea minime.
Așa că am zis, bine, suntem la pozitia i, și trebuie să ne uităm la toate elementele
la dreptul de i, în scopul de a găsi minim.
Asta înseamnă că vrem să te uiți la i + 1 la sfârșitul listei.
Și acum, în cazul în care elementul care ne caută în prezent este mai puțin decât minimul noastre de până acum,
care, amintiți-vă, suntem incepand off minimă să fie doar
orice element de suntem în prezent la; Voi presupune că e minim.
Dacă aș găsi un element care este mai mică decât asta, atunci am de gând să spun, bine,
Ei bine, am găsit un nou minim.
Mă duc să-mi amintesc în cazul în care a fost minimă.
>> Așa că acum, odată ce am trecut prin acel segment nesortate drept,
Eu pot spune că am de gând să schimb elementul minim cu elementul care este în poziția I.
Asta se întâmplă pentru a construi lista mea, partea mea sortate din lista de la stânga la dreapta,
si nu avem nevoie niciodată să se uite la un element nou, odată ce e în acea porțiune.
După ce l-am schimbat.
Deci, haideți să ruleze un fel de selecție pe această listă.
Elementul blue aici este de gând să fi i, iar elementul roșu va fi elementul minim.
Asa ca am incepe tot drumul din partea stângă a listei, astfel încât la 5.
Acum, avem nevoie pentru a găsi elementul minim nesortate.
Așa că spunem 0 <5, astfel încât cifra 0 este de minim noua mea.
>> Dar eu nu pot opri aici, deoarece, chiar dacă putem recunoaște că 0 este cel mai mic,
avem nevoie pentru a rula prin fiecare alt element al listei pentru a vă asigura.
Deci, 1 este mai mare, 6 este mai mare, 4 este mai mare.
Asta înseamnă că după ce se uită la toate aceste elemente, am determinat 0 este mai mic.
Așa că am de gând să swap 5 și 0.
Odata ce am schimba asta, am de gând pentru a obține o listă nouă, și știu că n-am nevoie să te uiți la asta din nou 0
pentru că odată ce l-am schimbat, l-am sortati si am terminat.
Acum, doar așa se întâmplă că elementul albastru este din nou 5,
și trebuie să se uite la 1, 6 și 4 pentru a stabili că: 1
este elementul cel mai mic minim, deci vom schimba de 1 și 5.
Din nou, avem nevoie să se uite la - compara 5 la 6 și 4,
și am de gând să schimb de 4 și 5, și, în final, comparati
cele 2 numere și swap-le până când vom ajunge lista noastră de sortat.
Orice întrebări cu privire la fel de selecție?
Bine. Să trecem la ultimul subiect aici, și că este recursivitate.
>> Recursivitate, amintiți-vă, este acest lucru cu adevărat meta în cazul în care o funcție
în mod repetat se numește.
Deci, la un moment dat, în timp ce fuction noastră este în mod repetat în sine de asteptare,
trebuie să existe un anumit punct în care ne oprim de asteptare noi înșine.
Pentru că dacă nu facem asta, atunci suntem doar de gând să continue să facă acest lucru pentru totdeauna,
și programul nostru nu este doar de gând să rezilieze.
Noi numim această condiție cazul de bază.
Și în cazul de bază spune, mai degrabă decât o funcție de asteptare din nou,
Sunt doar de gând să se întoarcă o valoare.
Deci, odată ce ne-am întors o valoare, ne-am mai sunat pe noi înșine,
și restul apelurilor care le-am făcut până acum, de asemenea, pot reveni.
Opusul din scenariul de bază este cazul recursiv.
Iar acest lucru este atunci când vrem să face un alt apel la funcția pe care suntem în prezent inch
Și noi, probabil, deși nu întotdeauna, doriți să utilizați argumente diferite.
>> Deci, dacă avem o funcție numită f, și f sunat ia 1 argument,
și ne ține doar de asteptare f (1), f (1), f (1), și doar așa se întâmplă că
argumentul 1 cade în caz recursiv, niciodată nu vom mai merge să se oprească.
Chiar dacă avem un caz de bază, trebuie să ne asigurăm că în cele din urmă vom lovi acest caz de bază.
Noi nu ține numai sejurului în acest caz recursiv.
În general, atunci când ne numim, vom avea, probabil, un argument diferită de fiecare dată.
Aici este o funcție foarte simplu recursivă.
Deci, aceasta va calcula factorialul unui număr.
Până top aici avem cazul nostru de bază.
În cazul în care n ≤ 1, noi nu vom apela din nou factorial.
Vom opri; suntem doar de gând să se întoarcă o valoare.
Dacă acest lucru nu este adevărat, atunci vom lovi cazul nostru recursiv.
Observați aici că nu suntem doar asteptare factorial (n), pentru că nu ar fi de foarte mare ajutor.
Vom apela factorială a altceva.
>> Și așa cum puteți vedea, în cele din urmă dacă vom trece ceva factorială (5) sau,
vom apela factorial (4) și așa mai departe, și în cele din urmă vom lovi acest caz de bază.
Deci, acest lucru pare bine. Să vedem ce se întâmplă atunci când vom rula de fapt acest lucru.
Aceasta este stiva, și să spunem că principala este de gând pentru a apela această funcție cu un argument (4).
Deci, odată ce vede și factorială = 4, factorială se va apela.
Acum, dintr-o dată, avem factorială (3).
Deci, aceste funcții sunt de gând să păstreze în creștere până în cele din urmă ne-am lovit cazul nostru de bază.
În acest moment, valoarea returnata de aceasta este întoarcerea (NX valoarea returnata de aceasta),
valoarea returnata de aceasta este nx valoarea returnata de aceasta.
În cele din urmă, avem nevoie pentru a lovi unele număr.
In partea de sus aici, spunem retur 1.
Asta înseamnă că odată ce ne vom întoarce acest număr, ne putem pop de pe acest stiva.
Deci, acest factorial (1) se face.
Când 1 revine, acest factoriale (1) se întoarce, această întoarcere la 1.
Valoarea returnata de aceasta, ține minte, a fost nx valoarea returnata de aceasta.
Deci dintr-o data, tipul ăsta știe că vreau să se întoarcă 2.
>> Deci, amintiți, returna valoarea aceasta este doar nx valoarea de returnare aici.
Deci, acum putem spune 3 x 2, și în cele din urmă, aici, putem spune
acest lucru este doar de gând să fie de 4 x 3 x 2.
Și odată ce acest întoarce, vom ajunge până la un număr întreg interiorul unic de principal.
Orice întrebări cu privire la recursivitate?
Bine. Deci, nu e de mai mult timp pentru întrebări la sfârșitul anului,
dar acum Iosif va acoperi subiecte rămase.
>> [Joseph Ong] În regulă. Deci, acum că ne-am vorbit despre recursions,
hai sa vorbim un pic despre ceea ce este corespondenței fel.
Merge fel este de fapt un alt mod de sortare o listă de numere.
Și cum funcționează este, cu un fel de îmbinare aveți o listă, și ceea ce facem noi este
spunem, să împărțit în 2 jumătăți acest.
Vom rula prima îmbinare fel din nou pe jumătatea stângă,
apoi vom rula îmbinare fel pe jumătatea din dreapta,
și care ne dă acum 2 jumatati, care sunt sortate, iar acum vom combina aceste jumatati împreună.
E un pic cam greu pentru a vedea fara un exemplu, așa că vom trece prin propunerilor de rezoluție și a vedea ce se întâmplă.
Așa că începe cu această listă, l-am impartit in 2 jumatati.
Vom rula un fel îmbinare pe jumătatea stângă prima.
Deci, asta e jumătatea stângă, iar acum le trece prin această listă din nou
care devine trecut în sortare îmbinare, iar apoi ne uităm, din nou,
la partea stângă a acestei liste și vom rula îmbinare fel pe ea.
Acum, ajungem la o listă de 2 numere,
iar acum jumătatea stângă este de numai 1, de mult timp, și nu putem
împărți o listă care doar 1 element în jumătate, așa că am să spun, după ce vom avea 50,
care este doar 1 element, este deja sortate.
>> După ce am terminat cu asta, putem vedea că putem
trece la jumătatea dreaptă a acestei liste,
și 3 este, de asemenea, sortate, și astfel acum că ambele jumatati ale acestei liste sunt sortate
ne putem alătura aceste numere din nou împreună.
Deci ne uităm la 50 și 3; 3 este mai mică de 50, așa că se duce în primul și apoi 50 inch vine
Acum, ce sa făcut, să ne întoarcem până la această listă și sortare e pe jumătate dreptate.
42 este numărul de propria lui, așa că deja sortate.
Deci, acum vom compara aceste 2 și 3 este mai mic decât 42, astfel că se pune în primul rând,
acum 42 se pune în, și 50 se pune inch
Acum, care este sortat, vom merge tot drumul înapoi la partea de sus, 1337 și 15.
Ei bine, acum ne uităm la jumătatea stângă a acestei liste; 1337 este, în sine, așa că sortati si aceeasi cu 15.
Deci, acum vom combina aceste 2 numere pentru a sorta această listă inițială, 15 <1337,
așa că merge în primul rând, apoi merge inch 1337
Și acum am sortat ambele jumatati ale lista inițială până sus.
Și tot ce trebuie să faceți este să combine aceste.
Ne uităm la primele 2 numere din această listă, 3 <15, așa că merge în matrice de sortare primul.
15 <42, deci merge inch Acum, 42 <1337, care merge inch
50 <1337, așa că merge inch Și observați că am luat doar 2 numere de pe această listă.
Deci, nu suntem doar alternând între cele 2 liste.
Căutăm doar la început, și vom lua elementul
care este mai mic și apoi punerea în gama noastră.
Acum, ne-am unit toate jumatati si am terminat.
>> Orice întrebări despre fuziona fel? Da?
[Student] Dacă e divizare în grupuri diferite, de ce nu au doar o dată împărțit
și aveți 3 și 2 în grup? [Restul de neînțeles cauză]
Motivul - deci intrebarea este, de ce nu putem îmbina doar le la acel prim pas după ce le avem?
Motivul pentru care putem face acest lucru, încep de la elementele de stânga, cele mai multe de ambele părți,
și apoi să ia cea mai mică și pune-l în, este că noi știm că aceste
Lista de preturi individuale sunt sortate în ordine.
Deci, dacă mă uit la elementele de cea mai din stânga ale ambelor reprize,
Știu că o să fie cele mai mici elemente ale acestor liste.
Deci, eu le pot pune în pete mai mic element al acestei liste mari.
Pe de altă parte, dacă mă uit la cele 2 liste, în al doilea nivel de acolo,
50, 3, 42, 1337 și 15, acestea nu sunt sortate.
Deci, dacă mă uit la 50 și 1337, am de gând să afișezi 50 în lista de prima mea.
Dar asta nu prea are sens, pentru că 3 este cel mai mic element din toate acestea.
Deci singurul motiv pentru care putem face acest pas, deoarece este combinarea listele noastre sunt deja sortate.
Care este motivul pentru care trebuie să te jos tot drumul la partea de jos
pentru ca atunci cand avem doar un singur număr, știți că un număr unic
în sine este deja o listă sortată.
>> Alte întrebări? Nu?
Complexitate? Ei bine, puteți vedea că, la fiecare pas exista numere finali,
și putem împărți o listă în jurnalul de jumătate de n ori,
care este în cazul în care vom obține acest jurnal n x n complexitate.
Și veți vedea cel mai bun caz pentru sortare îmbinare este n log n, și doar așa se întâmplă
că cel mai rău caz, sau Ω acolo, este, de asemenea, n log n.
Ceva de a păstra în minte.
Mutarea, să mergem pe la unele dosarul de bază, super-I / O.
Dacă te-ai uitat la Scramble, veți observa am avut un fel de sistem de
în cazul în care ați putea scrie într-un fișier jurnal, dacă ai citit prin codul.
Să vedem cum s-ar putea face asta.
Ei bine, avem fprintf, pe care vă puteți gândi ca doar printf,
ci doar imprimarea într-un fișier în loc, și, prin urmare f la început.
Acest tip de cod aici, ceea ce face este, așa cum s-ar putea fi văzut în Scramble,
ea trece prin imprimare matrice 2-dimensional out rând cu rând ce numere sunt.
În acest caz, printf imprimă la terminalul sau ceea ce noi numim de ieșire standard de secțiune.
>> Și acum, în acest caz, tot ce trebuie să faceți este să înlocuiască printf cu fprintf,
Spune-i cum fișier pe care doriți să imprimați, și, în acest caz, doar se imprimă în acest dosar
în loc să-l imprimarea la terminalul.
Ei bine, atunci pune întrebarea: Unde facem obține acest tip de fișier de la, dreapta?
Am trecut conecta la acest fuction fprintf, dar am avut nici o idee de unde a venit de la.
Ei bine, în prima parte a codului, ceea ce am avut a fost această bucată de cod pe aici,
care, practic, spune ca se deschid fișierul solicită log.txt.
Ce facem după aceea este că trebuie să vă asigurați că fișierul este deschis cu succes, de fapt.
Deci, s-ar putea eșua din mai multe motive, nu aveți spațiu suficient pe calculator, de exemplu.
Deci, este întotdeauna important înainte de a face orice operațiuni cu fișierul
pe care le verifice dacă acest dosar a fost deschis cu succes.
Deci, ce că o, care este un argument pentru a fopen, ei bine, putem deschide un fișier în mai multe moduri.
Ceea ce putem face este, putem să-l dați g, ceea ce înseamnă suprascrie fișierul, dacă acesta iese deja,
Putem trece un un, pe care le adăugați la sfârșitul fișierului în loc de aceasta imperative,
sau putem specifica R, ceea ce înseamnă, să deschideți fișierul doar în citire.
Deci, dacă programul încearcă să facă orice modificări la dosar,
tipa la ei si nu-i lasa sa-l faca.
În cele din urmă, odată ce am terminat cu fișierul, terminat fac operațiuni pe ea,
avem nevoie pentru a ne asigura închide fișierul.
Și astfel, la sfârșitul programului dumneavoastră, aveți de gând să-i treacă din nou
acest fișier pe care l-ați deschis, închideți-l și doar.
Deci, asta este ceva important care trebuie să vă asigurați faci.
Deci, amintiți puteți deschide un fișier, le puteti scrie la dosar,
face operațiuni în fișier, dar apoi va trebui să închideți fișierul la sfârșitul anului.
>> Orice întrebări cu privire la dosar de bază I / O? Da?
[Întrebare Student, neinteligibil]
Chiar aici. Întrebarea este, în cazul în care nu apare acest fișier log.txt?
Ei bine, daca da doar log.txt, îl creează în același director ca și executabil.
Deci, dacă Esti - >> [intrebare Student, neinteligibil]
Da. În același dosar, sau în același director, așa cum îl numesc.
Acum memorie, stivă, și heap.
Deci, cum este memoria prevăzută în calculator?
Ei bine, vă puteți imagina de memorie ca un fel de acest bloc aici.
Și în memorie, avem ceea ce se numește heap blocat acolo, iar stiva că e acolo.
Și heap crește în jos și în sus stiva creste.
Deci, ca Tommy sa menționat - Oh, ei bine, și avem aceste alte 4 segmente pe care le voi obține la un al doilea -
Ca Tommy spus mai devreme, știi cum funcțiile sale se numesc și apelați unul pe altul?
Ei construi acest tip de cadru stivă.
Ei bine, în cazul în care solicită principalele foo, foo este pus pe stiva.
Foo solicită bar, să-l punem pe stiva, și că este pus pe stivă după.
Și, după cum se întorc, fiecare dintre ele se iau de pe stivă.
Ce fiecare dintre aceste locații de memorie și mențineți?
Ei bine, de sus, care este segmentul de text, conține programul in sine.
Deci, cod mașină, că e acolo, odată ce compilați programul dumneavoastră.
În continuare, orice initializat variabilele globale.
>> Deci, aveți variabile globale în programul tău, iar tu spui ca, un 5 =,
care se pune în acest segment, și chiar sub care,
aveți orice date neinițializate globale, care este int doar o,
dar nu spune ca e egal cu nimic.
Realizati acestea sunt variabile globale, astfel încât acestea sunt în afara principal.
Deci, acest lucru înseamnă orice variabile globale care sunt declarate, dar nu sunt inițializate.
Deci, ce e în heap? De memorie alocate folosind malloc, pe care vom ajunge la un pic.
Și, în sfârșit, cu stiva aveți orice variabile locale
și orice funcții s-ar putea numi, în oricare din parametrii lor.
Ultimul lucru, nu aveți cu adevărat să știe ce fac variabilele de mediu,
dar ori de câte ori aveți o programul, nu este ceva asociat, cum ar fi
aceasta este numele de utilizator al persoanei care a fugit programului.
Și asta va fi un fel de la partea de jos.
În ceea ce privește adresele de memorie, care sunt valorile hexazecimale,
valorile de la începutul partea de sus de la 0, și care se duc tot drumul până la partea de jos.
În acest caz, dacă sunteți pe sistemul de 32-biți,
adresa la partea de jos va fi 0x, urmat de af, pentru că e de 32 de biți,
care este de 8 octeți, și, în acest caz, 8 octeți pentru a corespunde cifre hexazecimale 8.
Deci, aici ai de gând să aibă, ca, 0xFFFFFF, si acolo ai de gând să aibă 0.
Deci, ce sunt indicii? Unii dintre voi ar putea să nu au acoperit acest lucru în secțiune înainte.
dar am merge peste ea în curs, astfel încât un pointer este doar un tip de date
care de magazine, în loc de un fel de valoare cum ar fi 50, acesta stochează adresa o locație în memorie.
Ca faptul că memoria [neinteligibil].
Deci, în acest caz, ceea ce am este, avem un pointer la un întreg sau o int *,
și conține această adresă hexazecimală de 0xDEADBEEF.
>> Deci, ceea ce avem este, în prezent, această indicatorul de la o locație în memorie,
și că e doar o, valoarea 50 este în această locație de memorie.
Pe unele sisteme 32-biți, pentru toate sistemele pe 32 de biți, indicii dura până biți 32 sau 4 octeți.
Dar, de exemplu, pe un sistem de 64-biți, pointerii sunt pe 64 de biți.
Deci, asta e ceva ce veți dori să păstrați în minte.
Deci, pe un sistem end-biți, este un pointer biți end lung.
Pointeri sunt un fel de greu de digerat, fără lucruri suplimentare,
așa că hai să treacă printr-un exemplu de alocare dinamică a memoriei.
Ce alocare de memorie dinamică face pentru tine, sau ceea ce noi numim malloc,
vă permite să aloce un fel de date din afara setului.
Deci, asta este un fel de date cu caracter mai permanent pentru durata programului.
Pentru că după cum știți, dacă ați declara x în interiorul unei funcții, și care returnează funcția,
nu mai avea acces la datele care au fost stocate în x.
Ce indicii să facem este ca ei să ne stoca valori de memorie sau magazin
într-un segment diferit al memoriei, și anume heap.
Acum, odată ce ne vom întoarce din funcție, atâta timp cât avem un pointer
la acea locație în memorie, atunci ce putem face este doar să ne putem uita la valorile de acolo.
Să ne uităm la un exemplu: Acesta este aspectul nostru de memorie din nou.
Și avem această funcție, principala.
Ceea ce face este - în regulă, atât de simplu, nu? - Int x = 5, asta e doar o variabilă pe stivă în principal.
>> Pe de altă parte, acum avem declara un pointer care cheamă giveMeThreeInts funcției.
Și acum mergem în această funcție și vom crea un cadru nou teanc de ea.
Cu toate acestea, în acest cadru stivă, ne declarăm int * temp,
care, în mallocs 3 numere întregi pentru noi.
Deci, dimensiunea int ne va da cate bytes aceasta este int,
și malloc ne oferă ca multe bytes de spațiu de pe heap.
Deci, în acest caz, am creat spațiu suficient pentru 3 numere întregi,
și heap este drumul până acolo, motiv pentru care l-am redactat mai sus.
După ce am terminat, am venit înapoi aici, aveți nevoie doar de 3 Ints întors,
și returnează adresa, în acest caz peste în cazul în care memoria este.
Și ne-am stabilit indicatorul = comutator, și acolo avem doar un alt indicator.
Dar ceea ce revine funcției este stivuite aici și dispare.
Deci temp dispare, dar încă menține adresa în cazul în care
cele 3 numere întregi se află în interiorul rețelei de alimentare.
Deci, în acest set, pointerii cad pe plan local pentru cadru stivuite,
dar memoria la care se referă este în heap.
>> Are vreun sens?
[Student] Ai putea repeta asta? >> [Iosif] Da.
Așa că, dacă mă întorc doar un pic, vezi ca temp alocate
unele de memorie pe heap acolo.
Deci, atunci când această funcție, giveMeThreeInts retururi, acest teanc aici este de gând să dispară.
Și cu ea oricare dintre variabile, în acest caz, acest pointer care a fost alocată în cadrul stivuite.
Care este de gând să dispară, dar din moment ce ne-am întors temp
și ne-am stabilit indicatorul = temp, indicatorul se acum de gând să arate aceeași memorie de locație ca și temperatură a fost.
Deci, acum, chiar daca vom pierde temp, că indicatorul locală,
am încă mai păstrează adresa de memorie a ceea ce a fost îndreptat spre interior din variabila pointer.
Întrebări? Asta poate fi un fel de un subiect confuz, dacă nu au trecut peste ea în secțiunea.
Noi putem, TF ta va merge cu siguranta peste ea și, desigur, putem răspunde la întrebări
la finalul sesiunii de revizuire pentru acest lucru.
Dar aceasta este un fel de subiect complex, si am mai multe exemple care urmeaza sa apara
care va ajuta la clarificarea ce indicii sunt de fapt.
>> În acest caz, indicii sunt echivalente cu matrice,
așa că am putea folosi doar acest pointer ca același lucru ca o matrice int.
Deci, eu sunt în indexarea 0, se schimba întreg primul la 1,
schimbarea întreg secunde la 2, iar întreg treilea la 3.
Deci, mai mult pe pointeri. Ei bine, amintesc Binky.
În acest caz, am alocat un pointer, sau ne-am declarat un pointer,
dar inițial, când am declarat doar un pointer, nu este îndreptat oriunde în memorie.
E doar valori de gunoi în interiorul de ea.
Deci nu am nici o idee în cazul în care acest indicator este îndreptat spre.
Acesta are o adresă care este doar umplut cu a lui 0 și 1 în cazul în care acesta a fost declarat inițial.
Eu nu pot face nimic cu asta până când am apel malloc pe ea
și apoi dă-mi un pic de spatiu pe movila unde pot pune valori în interiorul.
Apoi, din nou, nu știu ce e în interiorul acestei memorii.
Deci, primul lucru pe care trebuie să faceți este să verificați dacă sistemul a avut suficientă memorie
sa-mi dea inapoi 1 întreg în primul rând, care este motivul pentru care fac asta verifica.
În cazul în care indicatorul este nul, ceea ce înseamnă că nu avea suficient spațiu sau o altă eroare a avut loc,
așa că am ar trebui să ieși din programul meu.
Dar dacă a făcut-o a reuși, acum pot folosi ca indicatorul
și ceea ce face este pointer * rezultă în cazul în care adresa este
pentru a în cazul în care valoarea este, și acesta stabilește l egal cu 1.
Deci aici, suntem de verificare în cazul în care memoria existat.
>> Odată ce știi că există, puteți pune în ea
ce valoare doriți să puneți în ea, în acest caz 1.
După ce am terminat cu el, aveți nevoie pentru a elibera că indicatorul
pentru că avem nevoie să ne întoarcem la sistemul de ca memoria pe care ai cerut, în primul rând.
Deoarece calculatorul nu știu când am terminat cu el.
În acest caz, vom spune în mod explicit că, în regulă, am terminat cu asta de memorie.
În cazul în care alt proces de care are nevoie, un alt program de care are nevoie, nu ezitați să mergeți mai departe și ia-o.
Ce putem face, de asemenea, este, putem obține doar adresa de variabilele locale pe platourile de filmare.
Deci, int x este în interiorul cadrului de stivuite principal.
Și atunci când vom folosi acest ampersand, asta și operatorul, ceea ce face este
este nevoie de x, si x este doar unele date din memorie, dar are o adresă.
Este situat undeva. Deci, prin chemarea & x, ce face asta este ne dă adresa lui x.
Făcând acest lucru, vom face punctul pointer la x, unde este în memorie.
Acum ne-am face ceva de genul * x, vom primi înapoi 5.
Stele este numit dereferencing ea.
Să urmați adresa și veți obține o valoare de ea stocată acolo.
>> Alte întrebări? Da?
[Student] Dacă nu faci chestia 3-colturi, nu-l compilați în continuare?
Da. Dacă nu faci chestia 3-pointer, este încă în desfășurare pentru a compila,
dar vă voi arăta ce se întâmplă într-o secundă, și fără a face acest lucru,
asta e ceea ce noi numim o scurgere de memorie. Tu nu dai sistemul
copii de memoria sa, asa ca dupa un timp programul este de gând să se acumuleze
de memorie care nu este utilizat, și nimic altceva pot folosi.
Dacă ați văzut vreodată Firefox cu 1,5 milioane de kilobiți pe computer,
în task manager, asta e ceea ce se întâmplă.
Ai o scurgere de memorie în programul pe care ei nu sunt de manipulare.
Deci, cum face indicatorul de muncă aritmetica?
Ei bine, aritmetica indicatorul este un fel de indexare ca într-o matrice.
În acest caz, am un pointer, iar ceea ce fac este punctul fac pointer la primul element
din această matrice de 3 numere intregi care le-am alocate.
Deci, acum ce să fac, indicatorul stea schimbă doar primul element din listă.
Stele pointer +1 puncte peste aici.
Deci, indicatorul este de peste aici, indicatorul +1 este aici, indicatorul +2 este aici.
>> Deci, adăugând doar 1 este același lucru ca și în mișcare de-a lungul acestei matrice.
Ceea ce facem este, atunci când facem indicatorul 1 te adresa aici,
și, în scopul de a obține o valoare aici, ai pus o stea de la întreaga expresie
să-l dereference.
Deci, în acest caz, am stabilind prima locatie in aceasta matrice de 1,
doua locatie la 2, și a treia locație la 3.
Atunci ce fac eu aici este că am imprimarea indicatorul nostru +1,
care tocmai îmi dă 2.
Acum sunt incrementarea pointer, astfel încât indicatorul este egal cu indicatorul 1,
care se mișcă înainte.
Și acum, dacă am tipări indicatorul 1, indicatorul 1 este acum 3,
care, în acest caz, imprimă 3.
Și în scopul de a ceva gratuit, indicatorul pe care l-am da
trebuie să fie îndreptată la începutul matrice pe care m-am întors de la malloc.
Deci, în acest caz, dacă ar fi să sun 3 chiar aici, acest lucru nu ar fi corect,
pentru că este în mijlocul matrice.
Trebuie să scadă pentru a ajunge la locația originală
loc inițială înainte pot să-l elibera.
Deci, aici e un exemplu se implice mai mult.
În acest caz, vom aloca 7 caractere într-un sir de caractere.
>> Și în acest caz, ceea ce facem noi e ca suntem looping peste primele 6 dintre ele,
și suntem stabilirea lor la Z.
Deci, pentru int i = 0, i> 6, i + +,
Deci, indicatorul + i se va da doar noi, în acest caz,
indicatorul, indicatorul 1, indicatorul 2, indicatorul 3, și așa mai departe și așa mai departe, în buclă.
Ce va face este faptul că devine adresa, dereferences l pentru a obține valoarea,
și modificările că valoarea unei Z.
Apoi, la sfârșitul retineti aceasta este un șir, nu?
Toate siruri de caractere trebuie să se termine cu caracterul nul de încheiere.
Deci, ceea ce fac este în indicatorul 6 am pus nul caracterul terminator inch
Și acum ce fac eu practic aici este punerea în aplicare a printf pentru un șir, nu?
>> Deci, atunci când se printf acum, când acesta a ajuns la sfârșitul unui șir?
Când va atinge caracterul nul de încheiere.
Deci, în acest caz, punctele mele originale indicatorul la începutul acestei matrice.
Am imprima primul caracter afară. Am muta peste o.
Am imprima acel caracter afară. Am muta peste.
Și am face asta până când voi ajunge la final.
Și acum * indicatorul final va dereference acest lucru și a obține caracterul nul de încheiere înapoi.
Și astfel buclă în timp ce se execută meu numai atunci când acea valoare nu este caracterul nul de încheiere.
Deci, acum am ieși din această buclă.
Și deci, dacă am scădea 6 din acest pointer,
Mă duc înapoi tot drumul de la început.
Amintiți-vă, eu fac asta pentru că trebuie să mă duc la început pentru ao elibera.
>> Deci, eu știu că a fost o foarte mult. Există întrebări?
Te rog, da?
[Neinteligibil întrebare Student]
Poți să spui asta mai tare? Scuze.
[Student] La ultimul diapozitiv chiar înainte de a te-a eliberat indicatorul,
în cazul în care ați fost schimbarea de fapt, valoarea indicatorului?
[Joseph] Deci, chiar aici. >> [Student] Oh, bine.
[Joseph] Deci, am un pointer minus minus, dreapta,
care se mută înapoi cu un lucru, iar apoi l-am elibera,
deoarece acest indicator trebuie să fie arătat la începutul matrice.
[Student] Dar asta nu ar fi nevoie de a te-ai oprit după acea linie.
[Joseph] Deci, dacă aș fi oprit după aceasta, acest lucru ar fi considerat o scurgere de memorie,
pentru că nu am alerga liber.
[Student] I [neinteligibil] după primele trei linii în cazul în care le-ați avut indicatorul 1 [neinteligibil].
[Joseph] Uh-huh. Deci, ce e problema acolo?
Scuze. Nu, nu. Du-te, du-te, te rog.
[Student] Deci, nu te schimba valoarea de pointeri.
Tu nu ar fi trebuit să facă indicatorul minus minus.
[Joseph] Da, exact.
Așa că, atunci când fac indicatorul +1 și indicatorul 2,
Eu nu fac indicatorul este egală cu indicatorul 1.
Deci, indicatorul rămâne doar îndreptat la începutul matrice.
E doar atunci când fac, plus, plus că aceasta stabilește valoarea înapoi indicatorul,
că se mișcă de fapt această de-a lungul.
Bine.
Mai multe întrebări?
>> Din nou, în cazul în care aceasta este un fel de copleșitoare, acest lucru va fi acoperit în sesiune.
Adresați-vă colegii dumneavoastră de predare cu privire la aceasta, și putem răspunde la întrebările de la sfârșitul.
Și, de obicei, nu ne place să facem acest lucru minus.
Acest lucru trebuie să solicite mă ține cont de cât de mult le-am compensat în matrice.
Deci, în general, acest lucru este doar de a explica modul în care funcționează indicatorul aritmetice.
Dar, de obicei, ceea ce ne place să facem este să ne place crea o copie a indicatorului,
și apoi vom folosi această copie atunci când ne mișcăm în jurul valorii de în șir.
Deci, în aceste cazuri, utilizați pentru a imprima copia întregul șir,
dar noi nu trebuie să facem ca indicatorul minus 6 sau a urmări cât de mult ne-am mutat în acest sens,
doar pentru că știm că punctul nostru inițial este încă indicat la începutul listei
și tot ce am modificat a fost această copie.
Deci, în general, să modifice copii ale indicatorul original.
Nu încercați să un fel de - Nu te modifica exemplare originale.
Încercarea de a modifica doar copii ale originalului.
Deci, observați când vom trece în șir printf
nu trebuie să pună o stea în fața lui ca și cum am făcut-o cu toate celelalte dereferences, nu?
Deci, dacă vă tipăriți întregul% s sir așteaptă este o adresă,
și, în acest caz, un pointer sau în acest caz, ca un tablou de caractere.
>> Caractere, char * s, și matrice sunt același lucru.
Pointer este de a caracterelor, și matrice de caractere sunt același lucru.
Și astfel, tot ce trebuie să faceți este să treci în pointer.
Noi nu trebuie să treacă în aceeași pointer * sau ceva de genul asta.
Deci, tablouri și pointeri sunt același lucru.
Atunci când faci ceva de genul x [y] aici pentru o matrice,
ceea ce face sub capota este ea spune, bine, e un sir de caractere,
așa că este un pointer.
Și astfel x sunt același lucru,
și așa mai departe ceea ce face este se adaugă y la x,
ceea ce este același lucru ca și avansează în memorie atât de mult.
Și acum x + y ne dă un fel de adresă,
și am dereference adresa sau urmați săgeata
pentru a în cazul în care locația în memorie este si ajungem valoarea din acea locație în memorie.
Deci, astfel încât acestea două sunt exact acelasi lucru.
E doar un zahăr sintactică.
Ei fac acelasi lucru. Sunt doar syntactics diferite pentru fiecare altul.
>> Deci, ce se poate merge în neregulă cu pointeri? Ca, o mulțime. Bine. Deci, lucruri rele.
Unele lucruri rele pe care le puteți face, nu se verifica dacă apelul malloc returnează null, nu?
În acest caz, vă cer să-mi dea de sistem - ceea ce este că numărul?
Ca 2 miliarde de ori 4, deoarece dimensiunea unei întregi este de 4 octeți.
Eu l cer pentru ca 8 miliard de octeți.
Desigur, calculatorul meu nu va fi în măsură să-mi dea înapoi că multă memorie.
Și nu am verifica daca acest lucru este nulă, astfel încât atunci când vom încerca să-l dereference acolo -
urmați săgeata în cazul în care se va - nu avem acea memorie.
Aceasta este ceea ce noi numim un pointer nul dereferencing.
Și asta în esență, te face să te segfault.
Aceasta este una dintre modalități în care puteți segfault.
Alte lucruri rele pe care le puteți face - oh bine.
Care a fost dereferencing un pointer nul. Bine.
Alte lucruri rele - ei bine, să se stabilească faptul că ai pus doar un cec acolo
care verifică dacă indicatorul este nul
și ieși afară din program daca se intampla ca malloc returnează un pointer null.
Asta e comic xkcd. Oamenii înțeleg acum. Oarecum.
>> Deci, de memorie. Și m-am dus peste asta.
Suntem de asteptare malloc într-o buclă, dar de fiecare dată când ne numim malloc
vom pierde evidența în cazul în care acest indicator este orientată spre,
pentru că noi îl platesti.
Deci, apelul inițial la malloc îmi dă de memorie pe aici.
Pointeri mele pointer la.
Acum, eu nu-l eliberăm, așa că acum eu numesc malloc din nou.
Acum, aceasta subliniază aici. Acum, memoria mea este îndreptată peste aici.
Îndreptată peste aici. Îndreptată peste aici.
Dar am pierdut evidența adresele tuturor memorie de aici pe care am alocat.
Și acum nu am nici o referire la ele mai.
Deci, eu nu le pot elibera in afara de aceasta bucla.
Și astfel, în scopul de a stabili ceva de genul asta,
dacă vă uitați pentru a elibera memorie și veți obține acest scurgere de memorie,
Ai pentru a elibera memoria interiorul această buclă odată ce ai terminat cu ea.
Ei bine, aceasta este ceea ce se întâmplă. Știu o mulțime de urăști asta.
Dar acum - yay! Veți obține ca 44000 kilobytes.
Deci, ai elibera la sfârșitul buclei,
și că va elibera doar de memorie de fiecare dată.
În esență, programul nu are o scurgere de memorie mai.
>> Și acum ceva ce poți face este elibera de memorie pe care le-ați cerut de două ori.
În acest caz, ceva malloc, ai modifica valoarea.
Ai elibereze odată pentru că ai spus că s-au făcut cu ea.
Dar apoi l-am eliberat din nou.
Acest lucru este ceva care este destul de rău.
Acesta nu va segfault inițial,
dar după un timp ce acest lucru nu este dublu eliberarea acestei corupe structura heap,
și veți afla un pic mai mult despre acest lucru, dacă alegeți să luați o clasă ca CS61.
Dar, în esență, după o vreme, computerul se va obține confuz
despre ceea ce locațiile de memorie sunt în cazul în care și în cazul în care este stocat -
în cazul în care datele sunt stocate în memorie.
Și eliberând astfel un pointer de două ori este un lucru rău că nu vrei să faci.
>> Alte lucruri care pot merge prost, nu se utilizează sizeof.
Deci, în acest caz, vă malloc 8 octeți,
și că e același lucru ca două numere întregi, nu?
Deci, asta e perfect sigur, dar este?
Ei bine, după cum Lucas a vorbit despre pe alte arhitecturi diferite,
întregi sunt de lungimi diferite.
Deci, pe aparatul pe care îl utilizați, întregi sunt de aproximativ 4 octeți,
dar pe un alt sistem ar putea fi de 8 octeți sau s-ar putea fi de 16 bytes.
Deci, dacă am folosi doar acest număr aici,
acest program ar putea să funcționeze pe aparat,
dar nu se va aloca suficientă memorie pe un alt sistem.
În acest caz, aceasta este ceea ce operatorul sizeof este utilizat pentru.
Când numim sizeof (int), ce face asta este
aceasta ne dă dimensiunea unui întreg sistem care pe programul se execută.
Deci, în acest caz, sizeof (int) va returna 4 pe ceva de genul aparatul,
și acum această voință 4 * 2, care este de 8,
care este doar cantitatea de spațiul necesar pentru două numere întregi.
Pe un sistem diferit, în cazul în care un int este ca 16 bytes sau 8 octeți,
este doar de gând să se întoarcă bytes suficiente pentru a stoca această sumă.
>> Și, în sfârșit, struct.
Deci, dacă ai vrut să stocați un consiliu de sudoku în memorie, cum am putea face acest lucru?
Ai putea crede ca a unei variabile pentru primul lucru,
o variabilă pentru al doilea lucru, o variabila pentru al treilea lucru,
o variabilă de lucru al patrulea - de rău, nu?
Deci, o îmbunătățire puteți face pe partea de sus a acestei este de a face o matrice 9 x 9.
Asta e bine, dar ce se întâmplă dacă ai vrut să se asocieze cu alte lucruri placa sudoku
ca ceea ce dificultatea de a bord este,
sau, de exemplu, ceea ce este scorul dvs., sau cât de mult timp mi-a luat să rezolve acest forum?
Ei bine, ce poti face este puteți crea un struct.
Ceea ce vreau să spun este practic eu definesc această structură de aici,
si eu o placa definirea sudoku, care constă dintr-un consiliu care este de 9 x 9.
>> Și ce are are indicatori către numele de nivel.
Ea are, de asemenea, x și y, care sunt coordonatele unde sunt acum.
De asemenea, a petrecut timpul [neinteligibil], și are numărul total de mutãri am introduse până acum.
Și astfel, în acest caz, pot grupa o grămadă de date într-o singură structură
în loc de a avea o ca zboară în jurul valorii de la diferite variabile cum ar fi
că nu pot ține evidența într-adevăr.
Și aceasta ne permite să avem doar sintaxa frumos pentru un fel de referire la lucruri diferite interiorul acestei structuri.
Eu doar pot face board.board, iar eu placa sudoku înapoi.
Board.level, am înțeles cât de greu este.
Board.x și board.y da-mi coordonatele unde s-ar putea să fie în bord.
Și așa am accesarea ceea ce noi numim câmpurile struct.
Aceasta definește sudokuBoard, care este un tip de care am.
Și acum suntem aici. Am o variabilă numită "board" de sudokuBoard tip.
Și așa că acum pot accesa toate domeniile care alcătuiesc această structură aici.
>> Orice întrebări despre struct? Da?
[Student] Pentru int x, y, ai declarat amândoi pe o linie? >> [Joseph] Uh-huh.
[Student] Deci, ai putea sa faci doar asta, cu toate acestea?
Ca și în x, y ori de virgulă că totale?
[Joseph] Da, ai putea face cu siguranta asta, dar motivul pentru care am pus x si y pe aceeași linie -
și întrebarea este de ce putem face asta pe aceeași linie?
De ce nu ne pune toate acestea pe aceeași linie este
x și y sunt legate unele de altele,
și acesta este doar stilistic mai corect, într-un sens,
deoarece este gruparea două lucruri pe aceeași linie
acest tip de ca se referă la același lucru.
Și am impartit doar aceste afară. E doar o chestie de stil.
Se face funcțional nici o diferență fel.
Orice alte întrebări cu privire struct?
Puteți defini un Pokedex cu o struct.
Un Pokemon are un număr și are o scrisoare, un proprietar, un tip.
Și apoi, dacă aveți o serie de Pokemon, puteți face un Pokedex, nu?
Bine, bine. Deci, întrebările pe struct. Acestea sunt legate de struct.
>> În cele din urmă, GDB. Ce înseamnă GDB lasa sa faci? Acesta vă permite să depanați programul tău.
Și dacă nu ați utilizat GDB, mi-ar recomanda uitam scurt
și doar trecând peste ceea ce este GDB, modul în care lucrați cu el, cum s-ar putea folosi,
și-l testeze pe un program.
Și deci ce GDB vă permite să faceți este permite pauză [neinteligibil] sus de program
și o linie de practică.
De exemplu, vreau să executare pauză la fel ca linia 3 din programul meu,
și în timp ce eu sunt la linia 3 Pot imprima toate valorile care sunt acolo.
Și astfel ceea ce numim ca oprindu-se într-o linie
noi numim acest lucru se pune un punct de control la acea linie
și apoi putem imprima variabilele de la nivel de stat a programului, la acel moment.
>> Ne putem apoi de acolo pas prin programul linie cu linie.
Și apoi ne putem uita la starea de stivă la momentul respectiv.
Și astfel, în scopul de a utiliza GDB, ceea ce facem noi este o numim zăngănit pe fișierul C,
dar trebuie să-l dați ggdb-pavilion.
Și odată ce am terminat cu asta vom rula doar gdb pe fișierul de ieșire rezultat.
Și astfel încât să obțineți unele masă ca de text de acest fel,
dar de fapt tot ce trebuie să faceți este să tastați în comenzile de la început.
Break principal pune un punct de control la principal.
Lista 400 enumeră linii de cod în jurul valorii de linia 400.
Și astfel, în acest caz, poti sa te uiti doar în jurul și să spună, oh,
Vreau să se stabilească un punct de întrerupere la linia 397, care este această linie,
și apoi programul rulează în această etapă și se va rupe.
O să pauză acolo, și puteți imprima, de exemplu, valoarea scăzută sau ridicată.
Și astfel, există o grămadă de comenzi ce trebuie să știți,
și această prezentare se va merge pe site-ul web,
așa că, dacă doriți doar pentru a face referire acestea sau ca le-a pus pe foi de cheat dvs., nu ezitați.
>> Mișto. Asta a fost Quiz comentariu 0, iar noi vom lipi în jurul valorii de, dacă aveți întrebări.
Bine.
>> [Aplauze]
>> [CS50.TV]