[Powered by Google Translate] [Săptămâna 6] [David J. Malan] [Universitatea Harvard] [Acest lucru este CS50.] [CS50.TV] 

Acest lucru este CS50, iar acest lucru este începutul Săptămâna 6, astfel încât o serie de instrumente noi sunt acum disponibile pentru tine de a profita de, care primul se numește CS50 Style. Cote sunt, dacă ești ca mine sau la oricare dintre semenii didactice, le-ați văzut, probabil, un program al cărui stil arata ceva de genul asta. Poate începe de tăiere unele colțuri târziu în noapte, sau vei face cu ea mai târziu, și apoi un TF sau CA vine timpul orelor de birou. Atunci e greu pentru noi să citească. Ei bine, acest cod este corect sintactic, și se va compila, și se va desfășura de fapt. Dar nu e cu siguranta un 5 pentru stil. 

Dar acum, dacă vom intra în acest director aici, și observați că am conditions2.c- și am rula această comandă nouă, style50, pe acest conditions2.c dosar, Enter, observa că acesta ma informat că a fost stilizat. Gedit observat că fișierul a fost modificat pe disc, și dacă fac clic pe reîncărca, toate problemele tale sunt acum automatizate. [Aplauze] Asta e unul din lucrurile pe care le-am făcut în acest weekend. Dau seama că este imperfect, deoarece există unele cod că pur și simplu nu va fi capabil de a stiliza perfect, dar realiza acest lucru este acum un instrument puteți profita de în cazul în care numai pentru a pune în ordine unele dintre cele mai acolade errantly plasat cret si place. 

Dar mai convingătoare este acum CS50 Data Check. Cu CS50 Cec, puteți efectua, de fapt, aceleași teste corectitudinii pe propriul cod care colegii de predare sunt în măsură să. Acesta este un utilitar linie de comandă care vine acum în aparat de îndată ce vă faceți un update50 ca pe PSET 4 caietul de sarcini, și să-l utilizați în esență, ca asta. Puteti rula check50 comanda. Apoi, treci într-un argument de linie de comandă, sau mai multe, în general, cunoscut ca un comutator sau un steag. În general, lucruri care au cratime sunt chemați un comutator la un program de linie de comandă, așa-c specifică controalele pe care doriți să le executați. 

Testele pe care doriți să le executați sunt identificate unic prin acest șir, 2012/pset4/resize. Cu alte cuvinte, e doar un șir arbitrar, ci unic pe care le folosim pentru a identifica în mod unic teste de 4 PSET lui corectitudine. Și apoi să specificați o listă separată spațiu de fișiere pe care doriți să încărcați Verificați să CS50 pentru analiză. De exemplu, dacă mă duc în soluția mea aici pentru resize.c- lasă-mă să deschideți un terminal mai mare fereastră- și am merge mai departe și a alerga să zicem c-check50 2012/pset4/resize, si apoi am merge mai departe și specificați numele fișierelor, resize.c, și a lovit apoi Enter, se comprimă, it încarcă, se verifică, și am reușit doar o grămadă de teste. Una în roșu din stanga sus spune că resize.c și BMP există. Asta a fost de testare. Aceasta a fost întrebarea-am cerut. Și e nefericită pentru că răspunsul a fost falsă. Textul de mai jos alb se spune de așteptat să existe bmp.h, și asta e pur si simplu vina mea. Am uitat să-l trimiti, pentru ca am nevoie pentru a încărca ambele fișiere, resize.c și bmp.h. Dar observați acum toate celelalte teste sunt în galben, deoarece acestea nu au rulat, și astfel fața zâmbitoare este verticală, deoarece el nu este nici fericit, nici trist, dar trebuie să remedieze această problemă în roșu înainte de aceste alte controale va rula. 

Lasă-mă să repar asta. Lasă-mă să zoom out și rulați din nou acest lucru, de data aceasta cu bmp.h, de asemenea, pe linia de comandă, Enter, și acum, dacă totul merge bine, se va verifica și apoi să se întoarcă un rezultat de-țineți respirația ta- toate verde, ceea ce înseamnă că eu fac foarte bine pe PSET 4 până în prezent. Puteți vedea și deduce din text descriptiv aici exact ce este testat de noi. Am testat prima nu există fisierele? Apoi am testat nu compila resize.c? Apoi am testat nu-l redimensiona un pixel BMP 1x1-atunci n, factorul de redimensionare, este de 1. Acum, în cazul în care nu aveți nici o idee despre ceea ce n este, veți odată ce scufunda in PSET 4, dar faptul că este pur și simplu un bun-simț să verificați pentru a vă asigura că nu ești redimensionare o imagine la toate, dacă factorul de redimensionare este 1. În cazul în care, prin contrast, se redimensionează un pixel 1x1 la un 1x1 pixel BMP la 2x2 corect când n este 2, atunci în mod similar, a mea face în consecință. 

Pe scurt, acest lucru este menit să, unul, ia de trecere a degetelor din ecuație chiar înainte de a trimite PSET ta. Veti sti exact ce TF va ști în curând când te duci cu privire la trimiterea unele dintre aceste seturi de probleme, și, de asemenea, motivația pedagogică este într-adevăr să afișezi oportunitate în fața ta, astfel că atunci când știi a priori că există bug-uri în codul dvs. și teste care nu sunt trecute, puteți pune în timp mai eficace în față pentru a rezolva aceste probleme mai degrabă decât pierde puncte, pentru a primi feedback de la TF dvs., și du-te apoi, "Ah," ca și cum aș fi dat seama. Acum, cel puțin există un instrument pentru a vă ajuta să găsiți asta. Acesta nu va arate unde bug-ul este, dar vă va spune ceea ce este simptomatic din ea. 

Acum realiza testele nu sunt neapărat exhaustivă. Doar pentru că veți obține un ecran plin de verde fețe zâmbitoare nu înseamnă codul este perfect, dar aceasta nu înseamnă că a trecut anumite teste prevăzute de spec.. Uneori nu ne va elibera cecuri. De exemplu, roman sau film polițist, unul dintre aspectele PSET 4, este un fel de dezamăgitor dacă am da Răspunsul la ceea ce este, și există un număr de moduri de a descoperi care persoana este în acel zgomot roșu. Spec. va specifica întotdeauna în viitor, pentru PSET 5 mai departe ce verifică exista pentru tine. Veți observa că e URL-ul alb la partea de jos. Pentru moment, aceasta este doar de ieșire de diagnosticare. Daca vizitati că URL-ul, veți obține o grămadă de mesaje criptice, nebun că ești binevenit să se uite prin, dar este mai ales pentru personalul astfel încât să putem diagnostica și a depana bug-uri în check50 sine. 

Fără formalități, să trecem la unde am rămas. Biblioteca CS50-am luat de-a gata pentru câteva săptămâni, dar apoi săptămâna trecută, am început peeling, unul din straturile de ea. Am început punerea deoparte șir în favoarea a ceea ce în schimb? [Elevii] Char. * Char, care a fost un char * tot acest timp, dar acum nu avem de a pretinde că este un real de date de tip șir. Mai degrabă, a fost un sinonim pentru felul de char *, și un șir este o secvență de caractere, așa că de ce nu se face sens pentru a reprezenta siruri de caractere ca e char *? Ce face un char * reprezintă, în contextul acestui concept a unui șir? Da >> [Student]. Primul caracter. Bine, primul caracter, dar nu destul de primul caracter. E de-[Studenții] Adresa. Bine, adresa primului caracter. Tot ceea ce este necesar pentru a reprezenta un șir în memoria unui computer este doar adresa unică de octet primul său. Tu nu au nici măcar să știu cât timp mai este deoarece cum poți seama de asta dinamic? [Student] lungimea șirului. Puteți apela lungimea șirului, excelent, dar cum nu Distanța de muncă șir? Ce face? Da. [Student] Continuă să mergi până când veți obține caracterul nul. Da, exact, doar cu o iterează pentru buclă, în timp ce bucla, indiferent de la * până la capăt, și sfârșitul este reprezentată de \ 0, caracterul așa-numitul nul, Nul, a nu se confunda cu nul, care este un pointer, care va veni intr-o conversatie din nou astăzi. 

Am cojit înapoi un strat de GetInt, iar apoi am luat o privire la getString, și reamintească faptul că aceste două funcții, sau într-adevăr, GetString, a fost folosind o anumita functie pentru a analiza, de fapt, care este, citi sau analiza, intrarea utilizatorului. Și ce a fost asta nouă funcție? Scanf sau sscanf. Este de fapt, vine într-un arome câteva diferite. Nu e scanf, sscanf e, nu e fscanf. Pentru moment, însă, să se concentreze pe cea mai ușor de ilustrat, și lasă-mă să merg mai departe și deschide în aparat un fișier ca asta, scanf1.c. Acesta este un program de super-simplu, dar care face ceva ce nu am făcut fără ajutorul bibliotecii CS50. Acest lucru devine o int de la un utilizator. Cum funcționează? Ei bine, în linia 16 acolo, observați că ne pronunțăm un x int numit, și în acest moment, în poveste, ceea ce este valoarea lui x? [Răspuns studentul neauzit] [David M.] Corect, cine stie, o valoare gunoi potențial, atât în ​​17, am spune doar utilizatorul da-mi un număr, vă rugăm, și pasul 18 este în cazul în care acesta devine interesant. Scanf pare să împrumute de la o idee printf prin faptul că utilizează aceste coduri format în ghilimele. D% este, desigur, un număr zecimal. Dar de ce sunt eu de întâlnire, în loc de x & x doar? Fosta este corectă. Da. [Răspuns studentul neauzit] Exact, dacă scopul acestui program, la fel ca GetInt funcția în sine, este de a obtine o int de la utilizatorul pot trece funcții toate variabilele vreau, dar dacă nu le trece prin trimitere sau prin adresa sau prin indicatorul, toate sinonim pentru scopuri de astăzi, atunci această funcție nu are capacitatea de a schimba conținutul acestei variabile. Acest lucru ar trece într-un exemplar la fel ca versiunea buggy a swap-ului pe care le-am vorbit despre câteva ori acum. 

Dar, în loc, făcând & x, eu sunt literalmente trece în ce? [Student] adresa. >> Adresa lui x. E ca și cum desen o hartă pentru funcția scanf numit și spune aici, acestea sunt orienta spre o bucată de memorie în calculatorul pe care poti sa te duci stoca unele întreg inch Pentru sscanf pentru a face acum, că ce operatorul, ce bucată de sintaxă este că va trebui să utilizeze chiar dacă nu putem să-l vadă pentru că altcineva a scris această funcție? Cu alte cuvinte - ce e asta? [Student] X citit. Nu va fi o lectură, dar numai în ceea ce privește x aici. Dacă scanf este trecut adresa lui x, punct de vedere sintactic, ceea ce operatorul este obligat să existe undeva în interiorul punerii în aplicare, astfel încât scanf scanf pot scrie de fapt, un număr de 2 la acea adresă? Da, așa *. Amintiti-va ca * este operatorul nostru dereference, care, în esență înseamnă du-te acolo. 

După ce ați fost înmânat o adresă, așa cum este cazul aici, scanf este, probabil, de fapt, dacă ne-uitat în jurul valorii de sursa acesteia code- este de a face * x sau echivalent pentru a merge de fapt la acea adresă și a pus acolo o anumită valoare. Acum, ca și pentru modul în care scanf primeste de intrare de la tastatură, ne vom flutura mainile noastre din ziua de azi. Doar presupunem că sistemul de operare permite sscanf pentru a vorbi la tastatura utilizatorului, dar în acest moment acum în linia 19, atunci când am imprima pur și simplu x, pare a fi cazul scanf care a pus-o în int x. Asta e exact cum functioneaza scanf, și amintesc săptămâna trecută asta e exact cum getString și GetInt și familia acestuia a altor funcții în cele din urmă funcționează, deși cu o ușoară variație ca sscanf, ceea ce înseamnă scana un șir în loc de tastatură. Dar haideți să aruncăm o privire la o variație mică a acestui. În scanf2, de fapt am dat-on bară. Ceea ce este greșit și-mi voi ascunde comentariu care explica la fel de mult- ceea ce este în neregulă cu acest program, versiunea 2? Să fie cât mai tehnic posibil de data asta. Se pare destul de bine. E frumos indentat, dar- bine, cum să-l prune despre despre jos întrebări scurte? Linia 16. Ce e linia 16 face în limba engleză, dar precis tehnic? Noțiuni de bază un pic ciudat. Da, Michael. [Student] E indică spre prima literă a unui șir. 

Bine, aproape. Permiteți-mi să tweak că un pic. Arătând spre prima literă a unui șir, se declară o variabilă numită tampon care va indica la prima adresă a unui șir, sau, mai degrabă, că va indica mai precis la un char. Observă că nu este de fapt îndreptat oriunde, deoarece nu exista nici o operatorului de atribuire. Nu e nici un semn egal, asa ca tot ce facem este alocarea tampon variabila numita. Se întâmplă să fie 32 de biți, deoarece este un pointer, și conținutul buffer probabil în cele din urmă va conține o adresă a unui char, dar pentru acum, ceea ce nu conține tampon? Doar unele false, cine știe, unii gunoi valoare, pentru că nu am în mod explicit initializat, așa că nu ar trebui să-și asume nimic. Ok, deci acum linia 17 este-ceea ce nu face linia 17? Poate că va incalzi asta. Se imprimă un șir, nu? Se imprimă String rog. 

Linia 18 este un fel de familiară acum în faptul că am văzut doar o variație a acestei dar cu un cod format diferit, astfel încât în ​​linia 18, ne spune scanf aici este adresa o bucată de memorie. Vreau să sune într-un șir, așa cum se sugerează de către% s, dar problema este că nu am făcut câteva lucruri aici. Care este una dintre problemele? [Student] Încearcă să dereference un pointer nul. Indicii bine, nule sau pur și simplu altfel necunoscute. Ești predarea scanf o adresă, dar tocmai ai spus-o clipă în urmă că această adresă este o anumită valoare gunoi, deoarece nu am atribui fapt la nimic, și așa mai spui scanf merge în mod eficient a pus un șir de aici, dar nu știm unde este încă aici, deci nu am alocat efectiv de memorie tampon pentru. Mai mult decât atât, ceea ce ești, de asemenea, nu spune chiar scanf? Să presupunem că aceasta a fost o bucată de memorie, și nu a fost o valoare gunoi, dar tu încă nu spui scanf ceva important. [Student] În cazul în care este de fapt, ampersand. Ampersand, astfel încât în ​​acest caz, e în regulă. Deoarece tampon este deja declarat ca un pointer cu piesa * de sintaxă, nu avem nevoie de a utiliza ampersand pentru ca este deja o adresă, dar cred că l-am auzit aici. [Student] Cât de mare este? Bine, nu ne spune cât de mare scanf acest buffer este, ceea ce înseamnă, chiar dacă au fost tampon un pointer, spunem scanf, a pus un șir de aici, dar aici ar putea fi 2 octeți, aceasta ar putea fi de 10 bytes, ar putea fi un megabyte. Scanf are nici o idee, și pentru că aceasta este o bucată de memorie probabil, nu e un șir încă. E doar un șir de caractere, odată ce scrie și un 0 \ la faptul că bucata de memorie. Acum e doar o bucată de memorie. Scanf nu va ști când să se oprească scris la acea adresă. 

Dacă vă reamintesc câteva exemple din trecut unde am tastat la întâmplare pe tastatură încercând să se reverse un tampon, si am vorbit vineri despre exact asta. În cazul în care un adversar oarecum injecteaza în programul tău un cuvânt mult mai mare sau o propoziție sau frază, atunci te așteptai puteți depășire o bucată de memorie, care poate avea consecințe negative, cum ar fi preluarea întregului program în sine. Avem nevoie de a remedia această cumva. Lasă-mă să zoom out și du-te în versiunea 3 a acestui program. Asta e un pic mai bine. În această versiune, observați diferența. În linia 16, am declarat din nou un tampon variabilă numită, dar ceea ce este acum? Este o serie de 16 caractere. Acest lucru este bun pentru că acest lucru înseamnă că pot spune acum scanf aici este o bucată reală de memorie. Vă puteți gândi la aproape de matrice ca fiind pointeri acum, chiar dacă acestea nu sunt de fapt echivalent. Vor comporta diferit în contexte diferite. Dar e cu siguranță cazul în care buffer-ul este de afiliere 16 caractere învecinate, deoarece asta e ceea ce este o matrice și a fost pentru câteva săptămâni acum. 

Aici, eu spun scanf aici e un segment de memorie. De această dată, este de fapt o bucata de memorie, dar de ce este acest program încă de exploatat? Ce e în neregulă încă? Am spus să-mi dai 16 bytes, dar- [Student] Ce dacă tastați în mai mult de 16? Exact, ce se întâmplă dacă utilizatorul tipurile din 17 caractere sau caractere 1700? De fapt, hai să vedem dacă nu putem împiedica de această greșeală acum. E mai bine, dar nu perfect. Lasă-mă să mergeți mai departe și să rulați make pentru a compila scanf3 acest program. Lasă-mă să rulați scanf3, te rog String: Buna ziua, am si par a fi în regulă. Lasă-mă să încerc una ceva mai lung, hello there. Bine, hai să facem hello there ce mai faci astăzi, Enter. Noțiuni de bază un fel de norocos aici, hai să spunem hello there ce mai faci. La naiba. Bine, așa că am avut noroc. Să vedem dacă nu putem rezolva această problemă. Nu, nu o să-mi copia. Să mai încercăm o dată. În regulă, stand by. Vom vedea cât de mult pot pretinde să se concentreze în timp ce faci asta încă. La naiba. Asta e destul de caz, de fapt. Acolo mergem. Punctul făcut. 

Acest lucru, de asemenea, jenant deși este, este de asemenea una dintre sursele de confuzie mare atunci când scrieți programe care au bug-uri, deoarece acestea se manifestă doar o singură dată într-un timp uneori. Realitatea este că, chiar dacă codul dvs. este complet rupt, ar putea fi complet rupt o dată într-un timp pentru că, uneori, în esență, ceea ce se întâmplă este alocă sistemului de operare o memorie pic mai mult decat ai de fapt nevoie pentru orice motiv, și astfel încât nimeni altcineva foloseste memorie imediat dupa bucată ta de 16 caractere, așa că, dacă te duci la 17, 18, 19, oricare ar fi, nu e un astfel de afacere mare. Acum, calculatorul, chiar dacă nu accident în acel moment, ar putea folosi în cele din urmă numărul de octeți 17 sau 18 sau 19 pentru altceva, la care punctul datele pe care le pune acolo, deși excesiv de lungă, este mergi la a lua suprascrise potențial de o alta functie. Nu e neapărat o să rămână intacte, dar nu va provoca în mod necesar o defecțiune seg. Dar în acest caz, am furnizat în cele din urmă caractere suficiente că am depășit în esență, segmentul meu de memorie, și bam, sistemul de operare a spus, "Îmi pare rău, că nu e vina bine, segmentare." 

Și să vedem acum dacă ceea ce rămâne aici, în directorul meu de- observați că am acest fișier aici, de bază. Observați că aceasta se numește din nou o groapa de bază. Este în esență un fișier care conține conținutul memoriei programului tău la punctul în care sa prăbușit, și doar să încerce un exemplu pic aici, lasă-mă să merg aici și a alerga gdb pe scanf3 și apoi specificați un al treilea argument numit miez, și observați aici, că, dacă am lista codul, vom fi capabili, ca de obicei, cu gdb pentru a începe de mers pe jos prin intermediul acestui program, si eu pot rula și de îndată ce am lovit-ca cu comanda pas în gdb- de îndată ce m-am lovit linia potențial buggy, după tastarea într-un șir imens, Voi fi în măsură să identifice, de fapt aici. Mai multe despre acest lucru, deși, în secțiunea din punct de vedere al haldelor de bază și ca, astfel încât să puteți împinge de fapt, în jurul valorii de interiorul haldei de bază si vezi pe ce linie programul a eșuat. Orice întrebări, apoi pe pointeri și pe adresele? Pentru că astăzi, ne-am de gând să începeți să luați pentru a acordat ca aceste lucruri exista și știm exact ce sunt. Da. 

[Student] Cum de nu ai avut de a pune un ampersand lângă partea- Bună întrebare. Cum de nu am avut de a pune un ampersand lângă matrice de caractere cum am făcut-o anterior cu cele mai multe dintre exemplele noastre? Răspunsul scurt este matrice sunt un pic aparte. Vă puteți gândi la aproape un tampon ca fiind de fapt o adresă, și doar așa se întâmplă să fie cazul în care pătrat suportul notația este o comoditate, astfel încât să putem intra în suport 0, suport 1, Suport 2, fără a fi nevoie de a utiliza notația *. Asta e un pic de o minciună albă, deoarece tablouri și pointeri sunt, de fapt, un pic diferit, dar ele pot fi de multe ori, dar nu întotdeauna folosite alternativ. Pe scurt, atunci când o funcție se așteaptă un pointer la o bucată de memorie, aveți posibilitatea să treci, fie ea o adresă care a fost returnat de malloc, și vom vedea din nou înainte de malloc lung, sau puteți trece-l numele unui tablou. Tu nu trebuie să faci ampersand cu matrice, deoarece acestea sunt deja în esență, ca adrese. Asta e singura excepție. Parantezele pătrate a le face speciale. 

Puteți să puneți un ampersand lângă tampon? Nu în acest caz. Asta nu ar funcționa, deoarece, din nou, de acest caz colț în cazul în care nu sunt destul de matrice, de fapt adrese. Dar vom veni, probabil, înapoi la faptul că înainte de lung, cu alte exemple. Să încercăm să rezolve o problemă aici. Avem o structură de date pe care le-am folosit de ceva timp cunoscut ca un tablou. Cazul de față, asta e ceea ce am avut. Dar matrice avea unele dezavantaje și upsides. Matrice sunt frumoase ce? Ce e un lucru care vă place, în măsura în care vă place matrice Despre matrici? Ce e convenabil despre ei? Ce e convingatoare? De ce am le introducă în primul rând? Da. [Student] Acestea pot stoca o mulțime de date, și nu trebuie să utilizați un lucru întreg. Aveți posibilitatea să utilizați o secțiune. Bine, cu o matrice se pot stoca o mulțime de date, și nu trebuie neapărat să utilizeze toate de ea, astfel încât să puteți overallocate, care ar putea fi convenabil dacă nu știe în avans cum mulți dintre ceva să se aștepte. 

GetString este un exemplu perfect. GetString, scrisă de noi, nu are nici o idee cum de multe caractere să se aștepte, astfel faptul că putem aloca bucăți de memorie contiguă este bun. Matricele rezolva, de asemenea, o problemă-am văzut acum câteva săptămâni acum în cazul în care codul dvs. începe să revină în ceva foarte prost proiectat. Amintiti-va ca am creat o structura elev a chemat pe David, și apoi că a fost de fapt o alternativă, însă, pentru a avea un nume de variabilă numită și o altă variabilă numit, cred, casa, și un alt variabilă numită ID-ul, deoarece în această poveste pe care am vrut apoi să introducă altceva Rob place în program, așa că am decis apoi așteptați un minut, Am nevoie pentru a redenumi aceste variabile. Să numim mea NAME1, ID1, house1. Să numim lui Rob nume2, house2, ID2. Dar apoi așteptați un minut, ceea ce despre Tommy? Apoi am avut trei mai multe variabile. Am introdus altcineva, patru seturi de variabile. Lumea a început să se dezordonat foarte repede, deci am introdus struct, și ceea ce e convingatoare despre un struct? Ce face un struct C lăsa să faci? E foarte ciudat azi. Ce >> [elevului răspunsul neauzit]? Da, în mod special, typedef vă permite să creați un nou tip de date, și struct, cuvântul cheie struct, vă permite să îngloba piese conceptual legate de date, împreună și, ulterior, le numim ceva ca un elev. 

Asta a fost bună pentru că acum putem modela un fel mult mai mult din punct de vedere conceptual coerentă noțiunea de un student într-o variabilă , mai degrabă decât având în mod arbitrar unul pentru un șir, unul pentru un ID, și așa mai departe. Matricile sunt frumoase, deoarece acestea ne permit să înceapă curățarea codul nostru. Dar ceea ce este un dezavantaj acum de o matrice? Ceea ce nu pot face? Da. [Student] Trebuie sa stii cat de mare este. Trebuie să știi cât de mare este, deci este un fel de durere. Aceia dintre voi cu experienta in programare prealabilă știu că într-o mulțime de limbi, cum ar fi Java, puteți solicita o bucată de memorie, mai precis o matrice, cât de mare ești, cu o lungime, de proprietate, ca să spunem așa, și asta e foarte convenabil. În C, nu puteți apela chiar strlen pe o matrice generică deoarece strlen, după cum cuvântul implică, este doar pentru siruri de caractere, și vă puteți da seama lungimii unui șir din cauza acestei convenții umane de a avea o 0 \, ci o matrice, mai generic, este doar o bucată de memorie. Dacă e o serie de Ints, nu va fi un caracter special la sfârșitul așteptare pentru tine. Trebuie sa ne amintim lungimea unui array. Un alt dezavantaj al unei matrice crescute capul în getString sine. Ce este un alt dezavantaj al unei matrice? Domnule, doar tu și cu mine azi. [Răspuns studentul nu pot fi auzite] >> E ce? Este declarat pe stiva. Bine, a declarat pe stiva. De ce nu vă place asta? [Student], deoarece este reutilizat. Acesta devine refolosite. Bine, dacă utilizați o matrice pentru a aloca memorie, nu se poate, de exemplu, să îl înapoieze pentru că e pe stivă. Bine, asta e un dezavantaj. Și cum despre celălalt cu o matrice? După ce-l aloce, ești un fel de greșit, dacă aveți nevoie de mai mult spațiu decât faptul că are matrice. 

Apoi am introdus, rechemare, malloc, care ne-a dat capacitatea de a aloca dinamic memorie. Dar ce se întâmplă dacă am încercat-o lume cu totul alta? Ce se întâmplă dacă am vrut să rezolve o serie de aceste probleme asa ca am loc de-pen-ul meu a adormit aici, Ce se întâmplă dacă am vrut să creăm loc în esență, o lume care nu mai este așa? Aceasta este o matrice, și, desigur, acest tip de deteriorează o dată ne-am lovit la sfârșitul matrice, iar eu acum nu mai am spațiu pentru un alt număr întreg sau un alt caracter. Ce se întâmplă dacă am un fel de prevenitor spun bine, de ce nu ne relaxa această cerință ca toate aceste bucati de memorie contiguă fie spate în spate, si de ce nu, atunci când am nevoie de un int sau un char, da-mi spațiu pentru una dintre ele? Și când am nevoie de altul, da-mi un alt spațiu, și atunci când am nevoie de un alt, dă-mi un alt spațiu. Avantajul de care acum este că, dacă altcineva ia memorie de aici, nu e mare lucru. Voi lua această bucată suplimentară de memorie aici și apoi aceasta. 

Acum, Captura doar aici este faptul că această aproape simte ca am o gramada de variabile diferite. Acest lucru se simte ca cinci variabile diferite de potential. Dar ce se întâmplă dacă am fura o idee din siruri de caractere prin care ne lega cumva aceste lucruri împreună conceptual, și ce dacă am făcut asta? Acest lucru este mea de săgeată foarte slab trase. Dar să presupunem că fiecare din aceste bucăți de memorie arătat la alta, iar acest tip, care nu are nici fratele său la dreapta, nu are nici o săgeată astfel. Acest lucru este, de fapt, ceea ce se numește o listă legat. Aceasta este o structură de date nouă, care ne permite să aloce un segment de memorie, apoi alta, apoi alta, apoi alta, în orice moment dorim în timpul unui program, și ne amintim că toate acestea sunt într-un fel legate de prin înlănțuirea literalmente le împreună, și am făcut-o aici, pictural cu o săgeată. Dar în cod, ceea ce ar fi mecanismul prin care ai putea conecta cumva, aproape ca Scratch, o bucată la alta bucată? Am putea folosi un pointer, nu? Deoarece într-adevăr pe săgeata care se întâmplă de la pătrat din stânga sus, acest tip aici cu acesta, ar putea conține în interiorul acestui pătrat nu doar unele Ints, nu doar un char, dar dacă de fapt am alocat un spațiu suplimentar pic, astfel că acum, fiecare dintre bucăți mele de memorie, chiar dacă acest lucru este de gând să mă coste, acum pare un pic mai mult dreptunghiulară în cazul în care una dintre bucăți de memorie este folosit pentru un număr, cum ar fi numărul 1, și apoi, dacă acest tip stochează numărul 2, această bucată de alte memorie este folosit pentru o săgeată, sau mai concret, un pointer. Și să presupunem că am păstra numărul 3 de aici în timp ce eu folosesc aceasta pentru a indica la tipul ăla, și acum tipul ăsta, să presupunem Vreau doar trei bucati astfel de memorie. Voi trage o linie prin care, indicând nul. Nu există nici un caracter suplimentar. 

Într-adevăr, acest lucru este modul în care putem merge despre punerea în aplicare a ceva ce se numește o listă legat. O listă legată este o structura de date nouă, și este o piatră de temelie spre structuri de date mult mai frumoase, care încep să rezolve problemele de-a lungul liniilor de Facebook-tip problemelor și Google de tip probleme în cazul în care aveți seturi imense de date, și nu-l mai taie pentru a stoca și de a folosi tot ceea ce contiguously ceva de genul căutare liniară sau chiar ceva de genul căutare binară. Vrei ori chiar mai bune de funcționare. De fapt, una dintre cele mai grails sfinte vom vorbi despre mai târziu în această săptămână sau viitoare este un algoritm al cărui timp de rulare este constantă. Cu alte cuvinte, este nevoie întotdeauna aceeași cantitate de timp, indiferent de cât de mare de intrare este, și că ar fi într-adevăr convingătoare, chiar mai mult decât ceva logaritmică. Ce este acest lucru pe ecran aici? Fiecare dintre dreptunghiuri este exact ceea ce am desenat de mână. Dar lucrul tot drumul din stânga este o variabilă specială. O să fie un pointer unic, pentru că Te-am prins o cu o listă legată, astfel cum aceste lucruri sunt numite, este că trebuie să stea pe un capăt al listei legate. 

La fel ca și cu un șir de caractere, trebuie să știți adresa char primul. Aceeași afacere pentru listele legate. Trebuie să știi adresa bucată primul de memorie pentru că de acolo, puteți ajunge la fiecare celălalt. Dezavantaj. Ce preț vom plăti pentru această versatilitate de a avea o dinamică sizable structură de date pe care, dacă avem nevoie de tot mai multă memorie, fin, aloca doar o bucată mai mult și trage un pointer la vechi la coada noua listă? Da. [Student] Este nevoie de spațiu aproximativ de două ori la fel de mult. Este nevoie de spațiu de două ori la fel de mult, așa că e cu siguranta un dezavantaj, și am văzut această compromis între înainte de timp și spațiu și flexibilitate în cazul în care până acum, nu avem nevoie de 32 biti pentru fiecare dintre aceste numere. Avem nevoie de 64 de ani, 32 pentru numărul și 32 pentru indicatorul. Dar, hei, am 2 GB de RAM. Adăugarea unui alt 32 de biți aici si aici nu pare că mare lucru. Dar, pentru seturi mari de date, cu siguranta se adaugă până la literalmente de două ori la fel de mult. Ce e un alt dezavantaj acum, sau ce caracteristică nu ne dăm bătuți, dacă ne reprezintă liste de lucruri cu o listă legată, și nu un tablou? [Student] Nu-l poți traversa spate. Nu-l poți traversa inapoi, deci ești un fel de greșit, dacă sunteți de mers pe jos de la stânga la dreapta folosind un pentru buclă sau o buclă în timp ce și apoi îți dai seama, "Oh, vreau să mă întorc la începutul listei." Tu nu pot, deoarece aceste indicii merge doar de la stânga la dreapta, după cum indică săgețile. 

Acum, ați putea aminti începutul listei cu o altă variabilă, dar asta e un complexitate a păstra în minte. O matrice, indiferent cât de departe te duci, poti sa faci mereu minus, minus, minus, minus și du-te înapoi de unde ai venit. Ce este un alt dezavantaj aici? Da. [Întrebare elev neauzit] Ai putea, deci ai de fapt, a propus doar o structură de date numit-o listă dublu legat, și într-adevăr, ar trebui să adăugați un alt indicator pentru fiecare dintre aceste dreptunghiuri care merge cealalta directie, capul de care este acum puteți traversa înainte și înapoi, Dezavantajul de care este acum pe care îl utilizați de trei ori mai multa memorie ca am folosit pentru a și, de asemenea, adăugarea de complexitate în ceea ce privește codul pe care trebuie să scrie să-l dreapta. Dar toate acestea sunt, probabil, foarte compromisuri rezonabile, dacă inversare este mai important. Da. [Student] Puteți, de asemenea, nu poate avea o listă 2D legat. Bine, nu poți avea într-adevăr o listă legată 2D. Ai putea. Nu e aproape la fel de ușor ca o matrice. Ca un tablou, ce faci suport deschis, suport închis, suport deschis, închis suport, și veți obține o anumită structură de 2-dimensionale. Ai putea pune în aplicare o listă 2-dimensionale legate de dacă faci add-a propus ca tine-un pointer treia la fiecare dintre aceste lucruri, și dacă te gândești la o altă listă vine la tine de stil 3D de la ecran pentru noi toți, care este doar un alt lant de un anumit fel. Am putea face asta, dar nu e la fel de simplu ca tastând suport deschis, suport patrat. Da. [Întrebare elev neauzit] Bine, astfel încât acesta este un fotbalist adevarat. 

Aceste algoritmi pe care le-am pined peste, cum ar fi oh, căutare binară, puteți căuta o serie de numere de la bord sau o carte de telefon atât de mult mai rapid dacă utilizați dezbina si cucereste și un algoritm de căutare binară, dar binar de căutare este necesar două ipoteze. Una, că datele au fost sortate. Acum, putem păstra probabil acest sortate, asa ca poate asta nu e un motiv de îngrijorare, dar, de asemenea, presupune căutarea binară pe care ați avut acces aleatoriu la lista de numere, și o matrice vă permite să aveți acces aleatoriu, și de acces aleatoriu, Adică, dacă ai dat-o matrice, cât de mult timp este să luați pentru a ajunge la reglaj 0? O singură operațiune, utilizați doar [0] si tu esti acolo. Câți pași este nevoie pentru a ajunge la locația 10? Un pas, te duci la [10] și că ești acolo. Prin contrast, cum ajungi la întreg zecea într-o listă legată? Trebuie să începem cu începutul, deoarece esti doar amintindu- începutul unei liste legate, la fel ca un șir este amintit de adresa char primul său, și pentru a găsi că int zecea sau că personajul zecea într-un șir, trebuie să căutați totul naibii. 

Din nou, nu suntem rezolvarea tuturor problemelor noastre. Suntem introducerea de noi, dar într-adevăr depinde de ceea ce sunteți încercarea de a proiecta pentru. În ceea ce privește punerea în aplicare a prezentei de, putem împrumuta o idee de la care structura de student. Sintaxa este foarte asemanatoare, cu exceptia acum, ideea este un pic mai abstract decât casa și numele și ID-ul. Dar eu propun ca am putea avea o structură de date în C care este numit nod, ca ultimul cuvânt pe diapozitiv sugerează, în interiorul unui nod, și un nod este doar un container generic în informatică. Este, de obicei, elaborat ca un cerc sau un pătrat sau dreptunghi ca am facut. Și în această structură de date, avem un int, n, asa ca asta e numarul vreau pentru a stoca. Dar ce este această a doua linie, struct nod * următor? De ce este acest lucru corect, sau ce rol are acest joc lucru, chiar daca e un pic criptic, la prima vedere? Da. [Răspuns studentul neauzit] Exact, deci un fel de * prăzii că este un pointer de un anumit fel. Numele acestui indicator este arbitrar următoare, dar am putut numi orice vrem, dar ceea ce face acest punct pointer la? [Student] Un alt nod >> Exact,. Punctele de la un alt nod astfel. 

Acum, acest lucru este un fel de curiozitate a lui C. Reamintească faptul că C este citit de un compilator de sus în jos, de la stânga la dreapta, ceea ce înseamnă că, dacă-acest lucru este un pic diferit de ceea ce am făcut cu elevul. Când ne-am definit un student, am de fapt, nu a pus o vorbă acolo. Pur și simplu a spus typedef. Apoi am avut int id, nume șir de caractere, șir casa, și apoi student la partea de jos a struct. Această declarație este un pic diferit, deoarece, din nou, compilatorul C este un pic prost. E doar de gând să citesc de sus în jos, așa că, dacă se ajunge la linia de două aici în cazul în care este declarată următor și-l vede, oh, aici e o variabilă numită următoare. E un pointer la un nod struct. Compilator este de gând să realizeze ceea ce este un nod struct? N-am mai auzit de chestia asta înainte, deoarece nodul cuvântul nu s-ar putea să apară altfel până la partea de jos, astfel încât nu există această redundanță. Trebuie sa spui nod struct aici, pe care le pot scurta apoi mai târziu datorită typedef aici, dar acest lucru este din cauza ne fac referire la structura însăși interiorul structurii. Asta e prins de acolo. 

Unele probleme interesante sunt de gând să apară. Avem o listă de numere. Cum putem introduce în ea? Cum l-am căuta? Cum putem sterge din el? Mai ales acum că avem de a gestiona toate aceste indicii. Te-ai gândit indicii au fost un fel de minte-îndoire când ai avut unul dintre ei doar încearcă să citească un int la acesta. Acum avem de a manipula în valoare de o lista intreaga lui. De ce nu luăm nostru de 5 minute de pauză aici, și apoi vom aduce unii oameni până pe scenă pentru a face exact acest lucru. 

C este mult mai distractiv atunci când este acționat. Cine ar dori să fie primul literal? Bine, vino sus. Sunteți primul. Cine ar dori să fie 9? Bine, 9. Ce zici de 9? 17? Un pic de clica aici. 22 și 26 din acel rând față. Și apoi cum despre cineva acolo fiind subliniat de la. Sunteți 34. Bine, 34, vino sus. În primul rând este acolo. Bine, toate cele patru dintre voi. Și cine ne-am spus pentru 9? Cine este de 9 nostru? Cine vrea cu adevărat să fie 9? În regulă, haide, să fie 9. Aici vom merge. 34, vă vom întâlni acolo. Prima parte este de a face vă arate ca asta. 26, 22, 17, bine. Dacă puteți sta într-o parte, pentru că am de gând să vă malloc într-un moment. 

Bine, bine. Bine, excelent, deci hai să ceară câteva întrebări aici. Și, de fapt, care e numele tau? >> Anita. Anita, bine, vino aici. Anita este de gând să ne ajute fel de a rezolva o întrebare destul de simplă în primul rând, care este modul în care vă găsiți dacă este sau nu este o valoare în listă? Acum, observăm că în primul rând, reprezentată aici de Lucas, este un pic diferit, și așa mai departe bucată de hârtie sa este în mod deliberat lateral pentru că nu e la fel de inalt si nu se ia ca multi biti, punct de vedere tehnic, chiar dacă el are aceeași dimensiune a hârtiei doar rotit. Dar e un pic diferit, în care el este doar 32 de biți pentru un pointer, și toate aceste tipi sunt 64 de biți, din care jumătate este numărul, din care jumatate este un pointer. Dar indicatorul nu este reprezentată, așa că dacă voi putea oarecum penibil folosi mana stanga la punctul de la persoana de lângă tine. Și tu ești numărul 34. Care e numele tău? Ari. Ari, așa, de fapt, țineți hârtia în mâna dreaptă, mâna stângă și merge direct în jos. Tu reprezinți nul pe stânga. 

Acum, imaginea noastră umană este foarte consistent. Aceasta este de fapt modul în care funcționează pointeri. Și dacă poți mesteca cu zgomot un pic acest fel, asa ca nu sunt in drumul tau. Anita aici, găsește-mi numărul 22, dar presupun o constrângere de a nu oamenii rezistă bucăți de hârtie, dar aceasta este o listă, iar tu trebuie doar să înceapă cu Lucas pentru că el este literalmente indicatorul primul. Să presupunem că vă sunt un pointer, și așa ai prea capacitatea de a indica la ceva. De ce nu începi prin a indica la exact ceea ce Lucas este îndreptat la? Bine, și lasă-mă să adopte asta de aici. Doar de dragul discuției, permiteți-mi să trag o pagină goală aici. Cum se scrie numele tau? >> Anita. Bine, Anita. Să spunem nod * Anita = Lucas. Ei bine, noi nu ar trebui să-ți spun Lucas. Ar trebui să te sun mai întâi. De ce este acest fapt, în conformitate cu realitatea aici? Unul, primul deja există. În primul rând a fost alocată probabil undeva aici. Nod * în primul rând, și a fost alocată o listă într-un fel. Nu știu cum sa întâmplat. Asta sa întâmplat înainte de a începe clasa. Această listă legată de om a fost creat. Și acum, în acest moment, în povestea-toate acestea sunt întâmplă pe Facebook aparent mai târziu, în acest moment, în poveste, Anita a fost pregătit pentru a fi egală cu prima, ceea ce nu înseamnă că punctele de Anita la Lucas. Mai degrabă, ea arată la ceea ce el arată spre deoarece aceeași adresă care este în interiorul a lui Lucas 32 biti - 1, 2, 3 - este acum, de asemenea, în interiorul Anita 32 de biți - 1, 2, 3. 

Găsi acum 22. Cum ti-ar merge despre a face acest lucru? Ce e asta ideea? >> La orice. Indicați spre orice, merge atât de departe și de a acționa este mai bun ca tine poate aici. Bine, bine, iar acum te-arătând spre ceea ce este numele tau cu 22? Ramon. >> Ramon, astfel încât Ramon rezistă 22. Ați făcut acum un cec. Are Ramon == 22, și, dacă da, de exemplu, ne putem întoarce adevărat. Lasă-mă să-în timp ce băieții ăștia stau aici, oarecum penibil- lasa-ma sa fac ceva rapid ca bool găsi. Am de gând să merg mai departe și spun (nod * lista, int n). Voi reveni imediat cu voi. Trebuie doar să scrie un cod. Și acum am de gând să merg mai departe și de a face acest lucru, nod * Anita lista =. Și am de gând să merg mai departe și spun în timp ce (Anita = NULL!). 

Metafora aici este obtinerea un pic întins, dar în timp ce (Anita = NULL!), Ceea ce vreau să fac? Am nevoie de un fel de referire întreg care Anita este îndreptat la. În trecut, atunci când am avut structuri, care este un nod, am folosit notația punct, și ne-ar spune ceva de genul anita.n, dar problema este că Anita nu este o struct în sine. Ce este ea? E un pointer, deci într-adevăr, dacă dorim să folosim această notație dot- și acest lucru este de gând să arate în mod deliberat un pic criptic- trebuie să facem ceva de genul du-te la mâna stângă, indiferent Anita este îndreptat la și de a lua apoi câmp denumit nr. Anita este un pointer, dar ceea ce este * anita? Ce ți se pare atunci cand te duci la ce Anita este îndreptat la? Un struct, un nod, și un nod, rechemare, are un câmp denumit n pentru că le-a, amintesc, aceste 2 domenii, pentru următoarele și n, că am văzut acum un moment chiar aici. 

Pentru a imita de fapt, acest cod în, am putea face acest lucru și spun că dacă ((* Anita). n == n), n care caut. Observați că funcția a fost trecut în numărul îmi pasă. Atunci pot merge mai departe și de a face ceva de genul return true. Altfel, în cazul în care nu e cazul, ceea ce vreau să fac? Cum traduc pentru a coda ce Anita a făcut atât de intuitiv de mers pe jos prin lista? Ce ar trebui să fac aici, pentru a simula Anita a lua acest pas la stânga, ca pas spre stânga? [Răspuns studentul nu pot fi auzite] >> Ce e asta? [Răspuns studentul neauzit] Bine, nu este o idee rea, dar în trecut, atunci când am făcut asta, am făcut anita + + deoarece acest lucru ar adăuga numărul 1 la Anita, care ar indica de obicei, la următoarea persoană, cum ar fi Ramon, sau persoana de lângă el, sau lângă el persoanei în jos linie. Dar asta nu e destul de bun aici, pentru că ceea ce înseamnă acest lucru arata ca in memoria? Nu asta. Trebuie să dezactivați asta. Se pare ca acest lucru în memorie, și chiar dacă le-am atras 1 și 2 și 3 aproape unul de altul, dacă dorim cu adevărat simula această-can voi, în timp ce încă arătând spre aceleași persoane, poate unii dintre voi ia un pas înapoi aleatoare, unii dintre voi un pas înainte întâmplare? 

Această mizerie este încă o listă legat, dar tipii ăștia ar putea fi oriunde în memorie, astfel Anita + + nu este de gând să lucreze de ce? Ce e la locația Anita + +? Cine stie. E o alta valoare pe care doar așa se întâmplă să fi interpus Printre toate aceste noduri de șansă pentru că nu utilizați un tablou. Ne alocate în fiecare dintre aceste noduri individual. Bine, dacă voi puteți să vă curăța înapoi. Permiteți-mi să propun ca in loc de Anita + +, am loc facem anita se- Ei bine, de ce nu mergem la orice Anita este îndreptat la și de a face apoi. viitoare? Cu alte cuvinte, vom merge la Ramon, care a deține numărul 22, și apoi următor este. ca și cum ar fi copierea Anita indicatorul mâna stângă. Dar ea nu va merge mai departe decât Ramon pentru că am găsit 22. Dar asta ar fi ideea. Acum, acest lucru este un dezastru zeu-groaznic. Sincer, nimeni nu va aminti vreodată această sintaxă, și așa fericire, de fapt e un pic deliberată-oh, nu ai vedea de fapt ceea ce am scris. Acest lucru ar fi mai convingătoare dacă ai putea. Voila! 

În spatele scenei, am fost rezolvarea problemei în acest fel. Anita, sa faca acest pas la stânga, în primul rând, facem mergem la adresa pe care Anita este îndreptat la și în cazul în care ea va găsi nu numai n, pe care tocmai am verificat de dragul lui comparație, dar veți găsi, de asemenea, următoarea - în acest caz, Mâna stângă a lui Ramon, ce indică spre nodul următor din listă. Dar acest lucru este mizerie zeul-îngrozitor la care m-am referit mai devreme, dar se pare că C ne permite să simplifice acest lucru. În loc de scris (* anita), se poate scrie în schimb doar anita-> n, si este exact același lucru funcțional, dar e mult mai intuitiv, si e mult mai în concordanță cu imaginea pe care ne-am fost de desen în tot acest timp cu ajutorul săgeților. 

În cele din urmă, ceea ce avem nevoie pentru a face la sfârșitul acestui program? Există o linie de cod rămase. Reveniți ce? Fals, pentru că dacă vom trece prin întreaga buclă în timp ce Anita și este, de fapt, nulă, înseamnă că ea a mers tot drumul până la sfârșitul listei în cazul în care ea a fost îndreptat la-care e numele tău din nou? Ari Ari >>. Lui mâna stângă, care este nul. Anita este acum nul, si imi dau seama ca esti doar stai aici penibil în uitare pentru că am de gând off pe un monolog aici, dar vă vom implica din nou într-o clipă. Anita este nulă în acel moment, în poveste, astfel încât în ​​timp ce bucla se termină, și trebuie să ne întoarcem fals, deoarece în cazul în care ea a ajuns tot drumul spre pointer nul lui Ari atunci nu era nici un număr pe care ea a căutat în listă. Noi putem curăța acest prea, dar aceasta este o implementare destul de buna, apoi a unei funcții traversal, o găsi funcție pentru o listă legată. E încă căutare liniară, dar nu e la fel de simplu ca un indicator + + sau + + o variabila i că acum nu putem ghici în cazul în care fiecare dintre aceste noduri sunt în memorie. Noi trebuie să urmeze traseul literalmente de pesmet sau, mai precis, pointeri, pentru a obține de la un nod la altul. 

Acum, hai sa incercam alta. Anita, vrei să vii înapoi aici? De ce nu mergem mai departe și să aloce o altă persoană din public? Malloc-Care este numele tau? >> Rebecca. Rebecca. Rebecca a fost malloced de audiență, și ea este acum stocarea numărul 55. Și gol la îndemână acum este pentru Anita pentru a insera Rebecca în lista legat aici, în locul său adecvat. Vino aici pentru o clipă. Am făcut ceva de genul asta. Am facut nod *. Si ceea ce este numele tau din nou? Rebecca. >> Rebecca, bine. Rebecca devine malloc (sizeof (nod)). La fel cum am alocat lucruri, cum ar fi studenții și fleacuri în trecut, avem nevoie de dimensiunea nodului, asa ca acum Rebecca este îndreptat la ce? Rebecca are două câmpuri din interiorul ei, dintre care unul este de 55. Să facem ceea ce, Rebecca-> = 55. Dar apoi Rebecca-> următor ar trebui să fie-dori acum, mâna ei este un fel de cine știe? Se indică, la o valoare gunoi, așa că de ce nu pentru o bună măsură am cel puțin face acest lucru, astfel încât mâna stângă este acum la partea ei. Acum Anita, luați-o de aici. Ai Rebecca-au fost alocate. Du-te și pentru a găsi în cazul în care ar trebui să punem Rebecca. Bine, foarte bine. Bine, bine, și acum avem nevoie de tine pentru a oferi un pic de direcție, deci ai ajuns Ari. Mâna stângă este nul, dar Rebecca aparține în mod clar drept, asa cum avem de a modifica această listă legată în scopul de a introduce Rebecca în locul potrivit? Dacă ai putea muta literalmente mâinile oamenilor stânga în jurul valorii de cum este necesar, vom rezolva problema în acest fel. Bine, bine, și în același timp, mâna stângă a lui Rebecca este acum de partea ei. 

Asta a fost prea ușor. Să încercăm alocarea-Suntem aproape gata, 20. Bine, vino sus. 20 a fost alocat, asa ca lasa-ma merge mai departe și spune din nou aici am facut doar * Saad nod. Avem malloc (sizeof (nod)). Noi facem atunci exact aceeasi sintaxa așa cum am făcut înainte de 20, și voi face în continuare NULL =, iar acum este de până la Anita pentru a insera vă în lista de legat, dacă ați putea juca acest rol exact același lucru. Executare. Bine, bine. Acum, gândește-te bine înainte de a începe să mișcați mâinile în jurul valorii de stânga. Ai de departe ai rolul cel mai ciudat astăzi. A cărui mână ar trebui să fie mutate mai întâi? Bine, stai, am auzit niște nr. În cazul în care unii oameni ar dori să ajute la rezolvarea politicos o situație penibilă aici. Mâna stângă a căror ar trebui să fie actualizate prima poate? Da. [Student] a lui Saad. Bine, a lui Saad, de ce, totuși? [Răspuns studentul neauzit] Bine, pentru că dacă am muta-care e numele tau? >> Marshall. Marshall, dacă vom muta mana primul până la nul, acum ne-am orfani literalmente patru oameni în această listă pentru că el a fost singurul lucru arătând spre Ramon și toată lumea la stânga, actualizarea astfel încât indicatorul primul a fost rău. Să anula asta. Bine, și acum mergeți mai departe și pentru a muta mâna stângă indică corespunzător la Ramon. Acest lucru se simte un pic redundant. Acum nu mai e la doi oameni îndreptate Ramon, dar asta e bine deoarece acum cum altfel ne actualiza lista? Ce altă parte, are să se mute? Excelent, au acum ne-am pierdut orice memorie? Nu, atât de bine, să vedem dacă nu putem rupe de această dată mai mult. 

Mallocing pentru ultima oară, numărul 5. Tot felul în spate, haide jos. E foarte interesant. [Aplauze] Care e numele tău? >> Ron. Ron, bine, ești malloced ca numărul 5. Am executat doar codul care este aproape identic cu acestea doar cu un nume diferit. Excelent. Acum, Anita, noroc introducerea numărul 5 în lista de acum. Bine, și? Excelent, astfel încât acesta este într-adevăr al treilea trei cazuri totale. Am avut cineva pentru prima oara la sfârșitul anului, Rebecca. Am avut atunci cineva în mijloc. Acum avem pe cineva de la început, și, în acest exemplu, am avut acum pentru a actualiza Lucas pentru prima dată deoarece primul element din listă are acum la punctul de la un nod nou, care, la rândul său, este îndreptat la numărul nodului 9. 

Aceasta a fost o demonstrație extrem de incomode, sunt sigur, asa o rundă de aplauze pentru acești tipi, dacă ai putea. Bine lucrat. Asta e tot. Puteți păstra piesele tale de hârtie ca o amintire putin. Se pare că a face acest lucru în cod nu este la fel de simplu ca mutarea doar mâinile în jurul valorii de și arătând indicii de la lucruri diferite. Dar dau seama că, atunci când vine vorba de timp pentru a pune în aplicare ceva de genul o listă legat sau o variantă a acesteia, dacă vă concentrați asupra adevarat aceste fundamente de bază, problemele musca-size le am să dau seama, este această mână sau mâna asta, dau seama că ceea ce este de altfel un program destul de complex poate, de fapt, să fie redusă la blocurile destul de simple, cum ar fi acest lucru. 

Să luăm lucrurile într-o direcție mult mai sofisticat încă. Avem acum noțiunea de listă legată. Avem, de asemenea, datorită-sugestia acolo-o listă de două ori legat, care arata aproape la fel, dar acum avem doi pointeri interiorul struct în loc de una, și am putea numi, probabil, aceste indicii precedent și următor sau la stânga sau la dreapta, dar noi nu, de fapt, nevoie de doi dintre ei. Codul ar fi un pic mai implicat. Anita ar fi trebuit să facă mai mult de lucru aici, pe scena. Dar am putea implementa cu siguranță, acest tip de structură. În ceea ce privește timpul de funcționare, însă, ceea ce ar fi timpul de funcționare Anita pentru a găsi un număr n într-o listă legată acum? Încă mare O din N, deci nu e mai bună decât căutarea liniară. Noi nu putem face binar de căutare, deși, din nou. De ce a fost cazul? Nu poți să sari în jurul valorii de. Chiar dacă am vedea în mod evident toti oamenii de pe scena, Anita și ar fi putut să-l eyeballed și a zis: "Iată mijlocul listei," ea nu ar ști că, dacă ar fi fost program de calculator deoarece singurul lucru pe care a trebuit sa dispozitivul de blocare pe la începutul scenariului a fost Lucas, care a fost primul indicatorul. Ea ar trebui neapărat să urmeze aceste link-uri, numărare felul ei până când a găsit aproximativ mijloc, și chiar și atunci, ea nu va ști când ea a ajuns la mijloc cu excepția cazului în ea merge tot drumul până la sfârșit să ne dăm seama cât de multe sunt, apoi backtracks, și că prea ar fi greu dacă nu ai avut o listă de două ori legat de un anumit fel. 

Rezolvarea unor probleme de astăzi, dar introducerea altora. Ce zici de o structură de date cu totul alta? Aceasta este o fotografie a tăvilor în Mather House, și, în acest caz, avem o structură de date care le-am, de asemenea, un fel de deja vorbit despre. Am vorbit despre un teanc în contextul de memorie, și că e un fel de mod deliberat, deoarece numit un teanc în termeni de memorie este efectiv o structură de date care are mai multe lucruri și mai așezate pe partea de sus a acesteia. Dar lucrul interesant despre o stivă, așa cum este cazul în realitate, este faptul că este un tip special de structuri de date. Este o structura de date prin care primul element din este ultimul element afară. Dacă sunteți tava prima care urmează să fie pus pe stivă, ai de gând să fie, din păcate, tava ultimul care urmează să fie luate de pe stivă, Și asta nu e neaparat un lucru bun. În schimb, vă puteți gândi la asta invers, ultimul este primul ieșit. 

Acum, nu orice scenarii vin în minte în cazul în care având o stivă structură de date în cazul în care aveți că proprietatea din ultimul, în primul rând, este, de fapt convingătoare? Este un lucru bun? Este ca un lucru rău? E cu siguranta un lucru rău, în cazul în care tăvile nu au fost toate identice și ei au fost toate culorile speciale sau diferite fleacuri, și culoarea dorită este tot drumul de la partea de jos. Desigur, nu se poate obține că fără mare efort. Va trebui să înceapă de la partea de sus și de a lucra drum în jos. În mod similar, dacă ai fost unul dintre acesti baieti ventilator care așteaptă toată noaptea încercarea de a obține un iPhone și liniile de sus într-un loc ca ăsta? Nu ar fi frumos dacă Apple Store au fost o structură de date stiva? Yay? Nay? E numai bun pentru oamenii care apar la ultimul minut și de a lua apoi smuls coada. Și, de fapt, faptul că am fost atât de înclinați să spunem coadă este de fapt în concordanță cu ceea ce noi am numi acest tip de structură de date, una în realitate, în cazul în care ordinea este importantă, și doriți primul pentru a fi primul din dacă numai pentru motive de echitate umane. Vom numi, în general, că o structură de date coadă. 

Se pare că în afară de listele legate, putem începe să utilizați aceste idei de bază aceleași și să înceapă crearea de noi tipuri și diferite de soluții la probleme. De exemplu, în cazul unei stive, am putea reprezenta o stivă utilizând o structură de date de acest fel, mi-ar propune. În acest caz, am declarat o struct, și am spus interiorul acestei structuri este o serie de numere și apoi o dimensiune variabilă numită, și am de gând pentru a apela acest lucru o stivă. Acum, de ce înseamnă acest lucru de fapt? În cazul în care un stack, am putea trage acest mod eficient pe ecran ca o matrice. Aici este stack-ul meu. Acestea sunt numerele mele. Și le vom trage ca aceasta, acest, acest, acest, acest lucru. Și apoi am unele state alte date aici, care se numește dimensiune, astfel încât aceasta este dimensiunea, și acest lucru este numere, și colectiv, iPad întregul aici reprezinta o structura stiva. Acum, în mod implicit, dimensiunea a ajuns probabil să fie inițializat la 0, și ceea ce este în interiorul matrice de numere inițial atunci când am aloca o matrice primul? Gunoi. Cine știe? Și nu contează de fapt. Nu contează dacă acest lucru este de 1, 2, 3, 4, 5, complet aleator de ghinion stocate în structura mea, deoarece atâta timp cât știu că dimensiunea stivei este 0, atunci știu programatic, nu te uita la oricare din elementele din matrice. Nu contează ce e acolo. Nu te uita la ei, cum ar fi implicarea de o dimensiune de 0. 

Dar să presupunem acum merge mai departe și introduceți ceva în stivă. Vreau să inserați numărul 5, așa că am pus aici numărul 5, si apoi ce am pus aici? Acum aș pune de fapt în jos 1 pentru dimensiunea, iar acum stack este de marimea 1. Ce se întâmplă dacă am merge mai departe și introduceți numărul, să zicem, 7 următor? Acest lucru devine apoi actualizat la 2, iar apoi vom face 9, și apoi acest lucru devine actualizat la 3. Dar caracteristica interesanta a acestui stack acum este faptul că Eu ar trebui să elimine elementul pe care dacă vreau să pop ceva de pe stiva, ca să spunem așa? 9 ar fi primul lucru pentru a merge. Cum ar trebui să schimbe imaginea, dacă vreau să pop un element de pe stivă, ca de mult o tavă în Mather? Da >> [elevului] Setați dimensiunea la 2.. Exact, tot ce fac este setat dimensiunea la 2, și ce fac cu matrice? Eu nu trebuie să fac nimic. Aș putea, doar pentru a fi anal, a pus un 0 acolo sau un -1 sau ceva pentru a semnifica faptul că aceasta nu este o valoare legit, dar nu contează, deoarece Eu pot înregistra în afara matrice în sine cât de mult este astfel încât să știu uita doar la primele două elemente din această matrice. Acum, dacă mă duc și se adaugă numărul 8 de la acest tablou, cum se schimba imaginea următoare? Acest lucru devine 8, iar acest lucru devine 3. Sunt de tăiere a colțurilor câteva aici. Acum avem 5, 7, 8, și ne-am întors la o dimensiune de 3. Acest lucru este destul de simplu pentru a pune în aplicare, dar atunci când vom regreta această decizie de design? Când lucrurile încep să meargă foarte, foarte greșit? Da. [Răspuns studentul neauzit] Când vrei să te întorci și să obțină primul element-ai pus inch 

Se pare că aici, chiar dacă o stivă este o matrice sub capota, aceste structuri de date care le-am început să vorbim despre sunt, de asemenea, în general, cunoscut sub numele de structuri de date abstracte, prin modul în care sunt puse în aplicare este complet pe langa subiect. O structură de date ca o stivă se presupune a adăuga suport operațiuni, cum ar fi împingere, care împinge o tavă pe stivă, și pop, care elimină un element din stivă, și asta e tot. Dacă ar fi să descărcați codul altcuiva care deja puse în aplicare acest lucru numit-o stivă, acea persoană ar fi scris doar două funcții pentru tine, împinge și pop, al cărui unic scop în viață ar fi să facă exact acest lucru. Tu sau el sau ea care a implementat acest program ar fi fost în întregime o să decidă cum să pună în aplicare semantica de împingere și popping sub capota sau funcționalitatea de a impinge și popping. Și am luat o decizie oarecum miop aici prin punerea în aplicare a stack-ul meu cu această structură de date simplu de ce? Atunci când face acest lucru pauză structuri de date? În ce moment trebuie să am pentru a reveni o eroare atunci când utilizatorul solicită împinge, de exemplu? [Student] În cazul în care nu există mai mult spațiu. Exact, dacă nu există spațiu nici mai mult, dacă l-am depășit capacitatea, care este toate capacele, deoarece sugerează că e un fel de constantă la nivel mondial. Ei bine, atunci eu sunt doar de gând să trebuie să spun, "Îmi pare rău, eu nu pot împinge o altă valoare pe stivă, "ca de mult în Mather. 

La un moment dat, au de gând să lovit partea de sus a cabinetului mic. Nu e nici mai mult spațiu sau de capacitate, în stivă, moment în care exista un fel de eroare. Ei trebuie să pună elementul în altă parte, tava de altă parte, sau nicăieri deloc. Acum, cu o coada, am putea implementa un pic diferit. O coadă este un pic diferită în faptul că sub capota, acesta poate fi pus în aplicare ca o matrice, dar de ce, în acest caz, eu propun să aibă, de asemenea, un element de cap care reprezintă capul listei, partea din față a listei, prima persoană la coadă la magazin Apple, în plus față de dimensiunea? De ce am nevoie de o bucată suplimentară de date aici? Gandeste-te la ceea ce numere este dacă am desenat-l, după cum urmează. Să presupunem că acest lucru este acum o coadă în loc de o stivă, diferența fiind-ca Apple Store-coada este corect. Prima persoană la coadă la începutul listei, numărul 5 în acest caz, el sau ea este de gând să fie lăsați în primul magazin. Să facem asta. Să presupunem că aceasta este starea de coada mea în acest moment, iar acum magazinul Apple se deschide și prima persoană, numărul 5, este condus în magazin. Cum pot schimba imaginea de acum că am dezinstalate-coadă prima persoană la partea din față a liniei? Ce-i asta >> [Student]? Schimbați coada. Modificarea cap, așa 5 dispare. În realitate, e ca și cum cel mai bine-how-ul pentru a face acest lucru? În realitate, e ca și cum tipul ăsta dispare. Ce ar face numărul 7 intr-un magazin real? Acestea ar avea un mare pas înainte. 

Dar ceea ce am ajuns să apreciem atunci când vine vorba de matrice și se deplasează în jurul valorii de lucruri? Asta e un fel de pierdere de timp, nu? De ce trebuie să fie atât de anal pentru a avea prima persoană de la începutul liniei de la fizic începutul bucată de memorie? Asta e complet inutil. De ce? Ce-aș putea să amintesc doar locul >> [elevului răspunsul neauzit]? Exact, am putea aminti doar cu acest cap de date suplimentare membru că, în prezent cap de listă nu mai este 0, care a fost un moment în urmă. Acum e de fapt numărul 1. În acest fel, am obține o optimizare ușoară. Doar pentru că am dezinstalate-coadă pe cineva de la linie la începutul liniei de la magazinul Apple nu înseamnă că toți trebuie să se schimbe, care amintesc este o operație liniară. Eu pot petrece timpul în loc singura constantă și pentru a atinge apoi un raspuns mult mai rapid. Dar prețul Plătesc este ceea ce a obține că performanțele suplimentare și să nu fi nevoie să schimbe toată lumea? Da >> [elevului răspunsul neauzit]. Pot adăuga mai multe persoane, ei bine, această problemă este ortogonală pentru faptul că nu vom schimba oamenii în jurul valorii de. E încă un tablou, astfel încât indiferent dacă suntem sau nu trece toata lumea sau nu- oh, am vedea ce vrei să spui, bine. De fapt, eu sunt de acord cu ceea ce spui, în sensul că e aproape ca și cum niciodată nu vom acum de gând să utilizeze începutul acestei matrice mai pentru că dacă am scoate 5, apoi m-am scoate 7. Dar am pus doar oameni la dreapta. 

Se simte ca și cum aș pierde spațiu, și în cele din urmă mi se dezintegrează în coada de nimic, la toate, asa ca am putea avea doar oameni curbat, și am putea gândi la această matrice într-adevăr ca un fel de structură circulară, dar vom folosi ceea ce operatorul în C pentru a face acest tip de curbat? [Răspuns studentul nu pot fi auzite] >> Operatorul modulo. Acesta ar fi un pic enervant de a gândi, prin modul în care faci curbat, dar am putea face acest lucru, și am putea începe să punem oamenii la ceea ce folosit pentru a fi partea din față a liniei, dar ne amintim doar cu această variabilă cap care șeful real al liniei este de fapt. Ce se întâmplă dacă, în schimb, obiectivul nostru în cele din urmă, totuși, a fost de a căuta numere, așa cum am făcut-o aici, pe scenă cu Anita, dar ne dorim într-adevăr cel mai bun din toate aceste lumi? Ne dorim mai mult de sofisticare matrice permite pentru că vrem capacitatea de a dezvolta dinamic structura de date. Dar noi nu vrem să aibă de a recurge la ceva ce am arătat în primă lectură nu a fost un algoritm optim, că de căutare liniară. Se pare că se poate, de fapt, atingerea sau cel puțin aproape de constanta de timp, prin care cineva ca Anita, dacă ea configurează structura ei de date să nu fie o listă legat, să nu fie o stivă, să nu fie o coadă, ar putea, de fapt, veni cu o structură de date care îi permite să privească lucrurile, chiar cuvinte, nu doar numere, în ceea ce vom numi timp constant. 

Și, de fapt, privind în perspectivă, una dintre cele mai psets din această categorie este aproape întotdeauna punerea în aplicare a unui spellchecker, prin care noi vă oferim din nou câteva cuvinte în limba engleză și 150000 scopul este de a încărca în memorie și cei rapid fie în măsură să răspundă la întrebări de forma este acest cuvânt scris corect? Și ar suge într-adevăr, dacă ați avut pentru a itera prin toate cuvintele 150000 a răspunde la această. Dar, de fapt, vom vedea că o putem face in timp foarte, foarte rapid. Și se va implica ceva punerea în aplicare a numit un tabel hash, și chiar dacă la prima vedere acest lucru numit un tabel hash este de gând să sa ne putem atinge aceste momente super-rapide de răspuns, se dovedește că există, de fapt, o problemă. Când vine vorba de timp pentru a pune în aplicare acest lucru numit din nou, eu o fac din nou. Eu sunt singurul de aici. Când vine vorba de timp pentru punerea în aplicare acest lucru numit un tabel hash, vom avea de a face o decizie. Cât de mare ar trebui să fie de fapt acest lucru? Și când vom începe să numere inserarea în acest tabel hash, cum am de gând să le stocați într-un mod pe care le putem lua înapoi cât mai repede le-am în? Dar vom vedea în scurt timp că această chestiune a atunci când toată lumea ziua de nastere a lui este în clasa va fi destul de Germane. Se pare că, în această cameră, am luat câteva sute de persoane, astfel sansele ca doi dintre noi au aceeași zi de naștere este, probabil, destul de mare. Ce se întâmplă dacă au existat doar 40 de noi în această cameră? Care sunt sansele de a două persoane care au aceeași zi de naștere? [Elevii] Peste 50%. Da, peste 50%. De fapt, chiar am adus-o diagramă. Se pare-și acest lucru este de fapt doar un sneak-preview în cazul în care există numai 58 de noi în această cameră, probabilitatea de 2 dintre noi având în aceeași zi de naștere este extrem de mare, de aproape 100%, și că va provoca o grămadă de răni pentru noi, miercuri. 

Cu care a spus, hai să amână aici. Ne vedem miercuri. [Aplauze] [CS50.TV]