[MUSIC JOC] [VIDEO PLAYBACK] -El Minte. -Despre ce? -Eu nu stiu. Deci ce știm? Asta la 09:15, Ray Santoya fost la ATM. Da. Deci, întrebarea este, ce făcea la 09:16? -Shooting 9 milimetru la ceva. Poate a văzut lunetist. Sau a fost de lucru cu el. -Stai asa. Du-te înapoi o. -Ce vezi? Adu fața în sus pe ecran complet. Ochelari -His. -Nu E un reflecție. -Este Echipa de baseball Nuevitas. Asta e logo-ul lor. -Si El vorbește cu oricine poartă jacheta. [END PLAYBACK] DAVID MALAN: Bine. Acest lucru este CS50 și acest lucru este un pic mai mult de [inaudibil] cu care esti abuza cu problema set de patru. Astăzi vom începe să se uite un pic mai mult profund la aceste lucruri numite indicii, care chiar dacă este un subiect destul de arcane, se dovedește că aceasta va să fie mijloacele prin care am poate începe construirea și asamblarea programe mult mai sofisticate. Dar am făcut-o pe ultima zi de miercuri prin intermediul unora claymation primul. Deci acest lucru, amintesc, este Binky și l-am folosit să aruncăm o privire la un program care nu într-adevăr ceva interesant, dar a făcut-o dezvăluie câteva probleme. Deci, pentru a începe astăzi, de ce nu am mers rapid prin câteva dintre aceste etape, încercați să distilare în termeni umani lui exact ceea ce se întâmplă aici și de ce acest lucru este rău, și apoi trece la și de fapt, începe construirea ceva cu aceasta tehnica? Deci, acestea au fost primele două linii în acest program și în termeni de nespecialist, ceea ce sunt aceste două linii faci? Cineva care e rezonabil confortabil cu ceea ce a declarat pe ecran? Ce sunt aceste două linii fac? Nu e tot ce diferită de o saptamana, dar există unele noi simbol special. Da? Acolo. Audiența: Declararea indicii? DAVID MALAN: Spune din nou? Audiența: Declararea indicii? DAVID MALAN: indicii Declararea și să-l rafina un pic mai mult. Audiența: [inaudibil] Adresa x si y, apoi. DAVID MALAN: Și apoi adresa. Deci, exact ceea ce facem este ne declararea două variabile. Aceste variabile, însă, sunt de gând să fie de tip stea Int, care înseamnă mai exact acestea sunt de gând pentru a stoca adresa de int, respectiv, x și y. Acum sunt acolo orice valori? Există adrese reale în aceste două variabile de la acest moment? Nu. E doar așa-numitele valori de gunoi. Dacă nu atribuiți de fapt o variabilă, ce era în RAM anterior se va umple cu zerouri și cele două de aceste variabile. Dar noi nu știm încă ceea ce sunt și asta e va fi cheia de ce Binky a pierdut capul săptămâna trecută. Deci aceasta a fost claymation încarnare a acestui prin care aveți doar două variabile, mici piese circulare de lut, care poate stoca variabile, ci ca săgețile împachetate sus sugerează, ei nu sunt de fapt îndreptat a cunoscut oriunde în sine. Deci, atunci am avut această linie, iar acest lucru era nou săptămâna trecută, malloc pentru memorie alocare, care este doar un mod de lux de a spune sistemul de operare, Linux sau Mac OS sau Windows, Hei, dă-mi niște memorie, și tot ce trebuie să-i spuneți sistemul de operare este ceea ce atunci când solicită memorie. Nu o să aibă grijă ce ai de gând să faci cu ea, dar aveți nevoie să-i spuneți de operare sistem ce prin intermediul malloc. Da? Audiența: Cât de mult? DAVID MALAN: Cât de mult? Cât de mult în bytes, și așa mai departe, acest, din nou, un exemplu contrived, este doar că da-mi dimensiunea unei Int. Acum, dimensiunea int este de patru bytes sau 32 de biți. Deci, aceasta este doar o modalitate de a spunând, hei, sistem de operare, da-mi patru bytes de memorie pe care le pot folosi la dispoziție, și, în special, ceea ce face întoarcere malloc cu respect la care bucată de patru bytes? Audiența: Adresa? DAVID MALAN: Adresa. Adresa de care bucată de patru octeți. Exact. Și așa mai departe asta e ceea ce este stocat în cele din urmă în X și de aceea nu prea pasă ce numărul de pe care Adresa este, indiferent dacă este sau OX1 OX2 sau unele adresa hexazecimal criptice. Doar ne pasă pictural că variabila x este acum subliniind că bucată de memorie. Deci săgeata reprezintă un pointer, sau mai precis, o adresă de memorie. Dar, din nou, nu ne pasă de obicei ce aceste adrese reale sunt. Acum, această linie spune ceea ce în termeni de nespecialist? Stele X devine 42 și virgulă. Ce înseamnă acest lucru? Vrei să mergi? Nu zgâriați gât. Audiența: Adresa de x este la 42. DAVID MALAN: Adresa de x este la 42. Nu chiar. Atat de aproape, dar nu destul, pentru că există steaua care a prefixarea această x. Deci, avem nevoie să tweak un pic. Da? Audiența: valoarea pe care pointer X indică spre este de 42. DAVID MALAN: OK. Valoarea că indicatorul x este arătând spre, să zicem, va fi 42, sau altfel spus, steaua X spune, du-te la orice adresă este în x, fie că este vorba de 1 Oxford Stradă sau 33 Oxford Street sau OX1 sau ox33, indiferent de că adresa numerică este, stele x este dereferencing de X. Deci, du-te la acea adresă și apoi pune numărul 42 acolo. Deci, care ar fi o mod echivalent a spune că. Deci asta e tot bine și apoi ne-ar reprezenta imaginea după cum urmează în cazul în care am adăugat cele 42 de care bucată de patru octeți pe partea dreaptă, dar aceasta linie a fost în cazul în care lucrurile au mers razna și capul lui Binky apărut off în acest moment, pentru că se întâmplă lucruri rele atunci când te dereference valori de gunoi sau dereference invalid indicii, și spun invalid pentru că la acest punct în poveste, ceea ce este în interiorul y? Care este valoarea lui y pe baza pe câțiva pași trecut? Da? Ce-i asta? Audiența: O adresă. DAVID MALAN: O adresă. Ar trebui să fie o adresă dar am o inițializată? Deci, eu nu au încă. Deci, ceea ce este cunoscut a fi acolo? E doar o valoare de gunoi. Ar putea fi orice adresa de la zero la 2 miliarde, dacă aveți două concerte de RAM, sau zero la 4 miliarde, dacă ai Trebuie patru gigabytes de memorie RAM. Este o valoare de gunoi, dar problema este că sistemul de operare, dacă acesta nu a dat că bucată de memorie special că sunteți încercarea de a merge la, se, în general, ceea ce va provoca am văzut ca o eroare de segmentare. Deci, în fapt, oricare dintre voi care au luptat la probleme la ore de birou sau în probleme care e mai mult în general, cu încearcă să dau seama o eroare de segmentare, înseamnă că, în general, te atinge un segment de de memorie pe care nu ar trebui să fie. Ești atinge de memorie care sistemul de operare nu are permis să atingă, fie că este vorba de a merge prea departe în matrice ta sau începând de acum, dacă este pentru că te atinge memorie care este doar o anumită valoare gunoi. Astfel stele X aici se tip de comportament nedefinit. Nu ar trebui să o facă pentru că cote sunt, programul se doar de gând să se prăbușească, pentru că spui, du-te la această adresă și nu aveți nici o idee în cazul în care că adresa este de fapt. Deci sistemul de operare este probabil O să se prăbușească programul ca urmare și, într-adevăr, asta e ceea ce sa întâmplat acolo pentru a Binky. Deci în cele din urmă, Binky fix această problemă cu asta. Astfel încât programul în sine a fost greșită. Dar, dacă un fel de a merge înainte și să execute această linie în schimb, y este egal cu x doar înseamnă orice Adresa este un x, de asemenea, pune-l în y. Și astfel pictural, ne-am reprezentat acest lucru cu două săgeți de la x si y din indicare în același loc. Deci semantic, x este egal a y deoarece ambele celor sunt la fel de stocare adresa, ergo arătând la 42, și acum, când spui stele y, du-te la adresa din y, acest lucru are un efect secundar interesant. Deci, adresa din y este același lucru ca și adresa de la X. Deci, dacă spui duci la adresa în y și modificați valoarea la 13, Cine mai este afectat? X este, punctul D, ca să spunem așa, ar trebui să fie afectate, de asemenea. Și într-adevăr, cum Nick desenat această imagine în claymation a fost exact acest lucru. Chiar dacă urmăm indicatorul y, am ajuns în același loc, și așa, dacă am fost pentru a imprima out X sau Y pointee lui, atunci am vedea valoarea 13. Acum, eu spun pointee să fie în concordanță cu video. Programatorii, pentru a-mi cunoștințe, de fapt, niciodată spune pointee cuvânt, ceea ce este ascuțit la, dar pentru consistență cu video, realiza asta e tot ce a fost însemnat în această situație. Deci, orice întrebări cu privire la claymation sau indicii sau malloc doar încă? Nu? In regula. Deci fără alte ADO, haideți să aruncăm o privire la în cazul în care acest lucru are de fapt fost folosit de ceva timp. Deci am avut această bibliotecă CS50 care are toate aceste funcții. Am folosit getint mult, getString, probabil mai devreme GetLongLong în PSET mea unul sau așa, dar ceea ce a fost de fapt se întâmplă? Ei bine, haideți să aruncăm o privire rapidă sub capota la un program care inspiră de ce am vă dau CS50 bibliotecă, și într-adevăr așa cum a săptămâna trecută, am inceput sa iau cele roți de formare off. Deci, acest lucru este acum sortate de o post-mortem a ceea a fost întâmplă în interiorul bibliotecii CS50, chiar dacă acum va începe să se miște departe de el pentru majoritatea programelor. Deci, acest lucru este un program numit scanf 0. Este foarte scurt. Este doar are aceste linii, dar introduce o funcție numită scanf că suntem de fapt de gând să vezi în un moment în interiorul bibliotecii CS50, deși într-o formă ușor diferită. Deci, acest program de pe linia 16 declară un X variabilă. Deci dă-mi patru octeți pentru un int. A fost spune utilizator, numărul te rog, și apoi aceasta este o linie de interesant faptul că de fapt, leagă împreună săptămâna trecută și asta. Scanf, și apoi observați este nevoie de o string format, la fel ca printf, % i înseamnă un int, iar apoi este nevoie de o al doilea argument care arată un pic funky. E ampersand X, și să reamintească, am văzut doar în această săptămână o dată trecută. Ce ampersand X reprezintă? Ce face ampersand in C? Da? Audiența: Adresa de. DAVID MALAN: Adresa de. Deci e opusul operatorului stele, întrucât operatorul stea spune, du-te la această adresă, operatorul ampersand spune, dau seama de Adresa de această variabilă, și așa mai departe acest lucru este cheia, pentru că Scopul scanf în viața este de a scana utilizatorului de intrare de la tastatură, în funcție de ceea ce el sau ea tipuri, și apoi citiți de intrare care utilizatorului într-o variabilă, dar am văzut în ultimele două săptămâni că funcția de swap pe care le încercat efort să pună în aplicare a fost doar rupt. Amintiți-vă că cu funcția swap, dacă ne-am declarat A și B ca int, ne-am SWAP cu succes două variabile din interiorul schimb la fel ca cu lapte și JO, dar de îndată ce a revenit de swap, care a fost rezultatul cu respect pentru x și y, valorile originale? Nimic. Da. Nu sa întâmplat nimic acel moment, pentru că swap-uri schimba doar de exemplare sale locale, adică, toate de data aceasta, ori de câte ori ne-am fost trecerea în argumente la funcții, suntem doar in trecere copii ale acestor argumente. Puteți face cu asta ce vrei cu ei, dar ei vor avea nici o efect asupra valorilor inițiale. Deci acest lucru este problematic dacă doresc să aibă o funcție ca scanf în viață, al cărei scop este de a scana intrare utilizatorului de la tastatura și apoi completați spațiile libere, astfel încât să vorbesc, că este, da o variabilă ca X o valoare, pentru că dacă aș fi pentru a trece doar x pentru a scanf, dacă ia în considerare logica ultima săptămână, scanf poate face ce vrea cu o copie a X, dar nu a putut schimba permanent X dacă nu vom da scanf o hartă a comorii, ca să spunem așa, unde x marchează locul, prin care trecem în adresa lui x, astfel încât scanf poate merge acolo și, de fapt schimbare valoarea lui x. Și astfel, într-adevăr, toate că acest program nu dacă am face scanf 0, în sursa mea Director 5m, face scanf 0, dot slash scanf, numărul Vă rugăm să 50, multumesc pentru 50. Deci nu e tot ce interesant, dar ce se întâmplă într-adevăr este faptul că, de îndată ce eu numesc scanf aici, valoarea lui x se schimbă în permanență. Acum, acest lucru pare frumos și bine, și, de fapt, ea se pare ca nu avem cu adevărat nevoie de biblioteca CS50 deloc mai. De exemplu, să rulați de data asta mai mult aici. Lasă-mă să-l redeschidă pentru un al doilea. Să încercăm un număr, vă rugăm și în loc de a spune 50 ca înainte, hai să spunem nu. OK, asta e un pic ciudat. BINE. Și doar câteva prostii aici. Deci, nu pare să gestiona situații eronate. Așa că trebuie să minim de pornire adăugând unele erori de verificare pentru a vă asigura că utilizatorul are tastat într-un număr real ca 50, deoarece cuvintele aparent dactilografiere nu este detectat ca fiind problematică, dar probabil ar trebui să fie. Să ne uităm la această versiune acum asta e incercarea mea de a reimplementeze getString. Dacă scanf are toate astea funcționalitate construit în, de ce am fost abuza cu aceste roți de formare, cum ar fi getString? Ei bine, aici este, probabil, propria mea versiune simpla a getString care în urmă cu o săptămână, s-ar putea fi spus, da-mi un șir și îl numesc tampon. Astăzi, am de gând să înceapă doar spunând stele char, care, amintesc, e doar sinonim. Se pare infricosator, dar este exact același lucru. Deci, da-mi un tampon variabilă numită care va stoca un șir, spune șirul de utilizator, vă rugăm, și apoi, la fel ca înainte, să încercăm să împrumute această lecție scanf % s acest moment și apoi să treacă în tampon. Acum, o verificare rapidă bun-simț. De ce nu mi spun ampersand tampon de data asta? Deduce din exemplul anterior. Audiența: Char stele este un pointer. DAVID MALAN: Exact, că de data aceasta, char stele este deja un pointer, o adresă, prin definiție, din care stele a fi acolo. Și dacă scanf așteaptă o adresă, este suficient doar pentru a trece în tampon. Nu am nevoie să spun tampon ampersand. Pentru curiosi, ai putea face ceva de genul asta. Aceasta ar avea sens diferit. Acest lucru ar da un pointer la un pointer, care este de fapt un lucru valabil în C, dar pentru acum, hai să-l păstrați simplu și să păstreze povestea consistent. Mă duc să treacă în tampon și asta e corect. Problema însă este aceasta. Lasă-mă să mergeți mai departe și a alerga acest Programul după compilarea ea. Face scanf 1. La naiba, compilator meu prinderea greșeala mea. Dă-mi o secundă. Zăngăni. Să spunem scanf-1.C. BINE. Nu mergem. Am nevoie de ea. CS50 ID are diferite setările de configurare pe care le proteja împotriva tine. Am nevoie pentru a dezactiva cele de rularea zăngăni manual de data asta. Deci, vă rugăm să șir. Am de gând să mergeți mai departe și tastați în lumea mea preferata salut. OK, null. Asta nu e ceea ce am scris. Deci e un indicator al ceva în neregulă fiind. Lasă-mă să mergeți mai departe și de tip într-un șir foarte lung. Multumesc pentru nul și nu știu dacă am de gând să fie în măsură să-l accident. Să încercăm un pic copie lipiți și a vedea dacă acest lucru vă ajută. Doar inserați o mulțime de acest lucru. Este cu siguranta o mai mare string decât de obicei. Să adevarat scrie. Nu. La naiba. Comanda nu a fost găsită. Așa că e fără legătură. Asta pentru că am lipit unele personaje rele, dar acest lucru se dovedește a nu va funcționa. Să încercăm încă o dată, pentru că e mai distractiv dacă am de fapt, accident. Să acest tip, iar acum, eu sunt merge pentru a copia un șir foarte lung și acum să vedem dacă ne poate prăbuși acest lucru. Observați am omis spații și noi linii și punct și virgulă și toate caracterele funky. Enter. Și acum rețeaua este doar fiind lent. Am apăsat Command-V prea mult timp, în mod clar. La naiba! Comanda nu a fost găsită. BINE. Ei bine, ideea este cu toate acestea, următoarele. Deci, ceea ce se întâmplă de fapt pe de această declarație de tampon stele char pe linia 16? Deci, ce sunt eu obtinerea atunci când am declara un pointer? Tot Primesc este o valoare de patru octet numit tampon, dar ceea ce este în interiorul acestuia Momentan? E doar o valoare de gunoi. Pentru că de fiecare dată când declara o variabilă în C, e doar o valoare de gunoi, si suntem incepand de la excursie pe această realitate. Acum, când am spune scanf, du-te la această adresă și a pus, indiferent de utilizator tipuri de. Dacă utilizatorul tipurile de salut lume, ei bine, unde am pus? Buffer este o valoare gunoi. Deci, asta e un fel de o săgeată care este îndreptat cine știe unde. Poate e îndreptat chiar aici, în memoria mea. Și astfel, atunci când utilizatorul tipurile din lume salut, programul încearcă să pună string Bună ziua lume backslash 0 în bucată de memorie. Dar cu mare probabilitate, dar în mod clar nu 100% probabilitate, computerul va apoi sa se prabuseasca programul deoarece aceasta nu este memorie ar trebui să li se permită să atingă. Deci, pe scurt, acest program este viciată pentru exact acest motiv. Eu fundamental nu este ceea ce faci? Ce măsuri au omis eu, la fel ca am omis cu prim exemplu Binky lui? Da? Audiența: Alocarea de memorie? DAVID MALAN: alocare de memorie. Nu am alocat de fapt orice memorie pentru că șir. Astfel încât să putem rezolva acest lucru în câteva moduri. Unul, putem păstrați-l simplu și, de fapt, acum ești va începe pentru a vedea o neclaritate a liniilor între ceea ce o serie este, ceea ce este un șir, ce stele char este, o serie de caractere este. Iată un al doilea exemplu implicând siruri de caractere și notificare tot ce am făcut pe linia 16 este, în loc de a spune că tampon va fi un char stele, un pointer la o bucată de memorie, Am de gând să dea foarte proactiv eu un tampon pentru 16 caractere, și, de fapt, în cazul în care esti familiarizat cu tamponarea pe termen lung, probabil din lumea de videoclipuri, în cazul în care un video este de tamponare, de tamponare, tamponare. Ei bine, ceea ce este legătura aici? Ei bine, interiorul YouTube și în interiorul playere video în general, este o matrice care este mai mare decât 16. Ar putea fi o serie de dimensiuni unul megabyte, poate 10 megaocteți, și în care matrice nu browser-ul dvs. descărca o grămadă de bytes, o grămadă de megabytes de video și video player, YouTube sau cine e, începe citit octeți de care matrice, și de fiecare dată când vedea pe tamponare cuvânt, de tamponare, ceea ce înseamnă că jucătorul are ajuns la sfârșitul acestei matrice. Rețeaua este atât de lent încât nu are reumplut matrice cu mai multe bytes și așa ai ieșit de biți pentru a afișa pentru utilizator. Deci tampon este un termen apt aici, în care e doar o matrice, o bucată de memorie. Și acest lucru se va rezolva pentru că se pare că pe care le poate trata ca și cum tablouri ele sunt adrese, chiar dacă tampon este doar un simbol, este un secvență de caractere, tampon, care este util pentru mine, programator, puteți trece numele acestuia în jurul ca și cum ar fi fost un pointer, ca și cum ar erau adresa de o bucată de memorie de 16 caractere. Așa că e de spus, eu pot trece scanf exact acest cuvânt și așa mai departe acum, dacă am face acest program, face scanf 2, punct slash scanf 2, și de tip în salut lume, Introduceți, că time-- Hmm, ce sa întâmplat? Șir, vă rugăm. Cu ce ​​am greșit? Bună ziua lume, tampon. Buna, lume. Ah, știu ce face. BINE. Deci e lectură până până la primul spațiu. Deci, haideți să trișeze pentru o clipă și spun că am vrut doar să tastați ceva foarte lung ca aceasta este o propoziție lungă acesta este unul, doi, trei, patru, cinci, șase, șapte, opt, nouă, 10, 11, 12, 13, 14, 15, 16. BINE. Este într-adevăr o propoziție lungă. Deci această teză este mai mult de 16 caractere și așa că atunci când am lovit Enter, ce se va întâmpla? Ei bine, în acest caz de tampon poveste, am declarat a fi de fapt o matrice cu 16 de caractere gata să meargă. Deci unul, doi, trei, patru, cinci, sase, șapte, opt, nouă, 10, 11, 12, 13, 14, 15, 16. Deci 16 de caractere, iar acum, când am citit în ceva de genul acesta este un lung teză, ce se va întâmpla este că am de gând să citesc în acest sens este o lungă S-E-N-T-E-N-C-E, propoziții. Deci acest lucru este în mod deliberat un lucru rău pe care am păstra scris dincolo de limitele de matrice meu, dincolo de granițele de tampon meu. Aș putea avea noroc și programul va continua să fie difuzate și nu le pasă, dar, în general vorbind, acest se va prăbuși într-adevăr programul meu, și este un bug în mea codul momentul în care am pasul dincolo de granițele din matrice, pentru că am Nu știu dacă e neapărat de gând să se prăbușească sau dacă Mă duc pentru a avea noroc. Deci acest lucru este problematic, deoarece în acest caz, se pare să funcționeze și să ispiti soarta aici, chiar dacă IDE pare să tolereze destul de un pic de-- Nu mergem. In cele din urma. Deci, eu sunt singurul care poate vedea acest lucru. Așa că am avut doar o mulțime de distracție dactilografiere o frază foarte lung real că cu siguranță depășit 16 bytes, pentru că am scris în acest nebun lung multi-line frază, și apoi observați ceea ce sa întâmplat. Programul a încercat imprimarea aceasta și apoi a primit o eroare de segmentare defecte de segmentare este atunci când se întâmplă ceva de genul asta și sistemul de operare spune Nu, nu se poate atinge acea memorie. Mergem să-l omoare programul cu totul. Deci, acest lucru pare problematic. Am îmbunătățit programul prin care cel puțin au unele de memorie, dar acest lucru ar părea să se limiteze funcția getString pentru obtinerea șiruri de unele lungime finit 16. Deci, dacă doriți să sprijine mai mult Exemple de mult de 16 de caractere, ce faci? Ei bine, puteți crește Dimensiunea de acest tampon la 32 sau care pare un fel de scurt. De ce nu ne-am face l 1000, dar împinge înapoi. Care este răspunsul intuitiv de evitând doar această problemă prin tampon meu mai mare, cum ar fi de 1.000 de caractere? Prin implementarea getString acest fel. Ce e bun sau rău aici? Da? Audiența: Dacă va obligati o mulțime de spațiu și nu-l utilizați, atunci nu se poate realoca că spațiul. DAVID MALAN: Absolut. E risipă în măsura în care, dacă nu de fapt, nevoie de 900 dintre aceste bytes și totuși ceri pentru 1.000 în total, oricum, esti doar consuma mai multă memorie pe computerul utilizatorului decât aveți nevoie pentru a, și după toate, unele dintre ați întâlnit deja în viață că, atunci când ești rulează o mulțime de programe și ei consumă o mulțime de memorie, acest lucru poate avea un impact de fapt, performanța și experiența utilizatorului pe calculator. Deci asta e un fel de soluție leneș, sigur, și invers, nu e numai risipă, care-i problema rămâne, chiar dacă am face tampon meu 1000? Da? Audiența: Șirul este de lungime 1001. DAVID MALAN: Exact. În cazul în care șirul este de lungime 1001, aveți aceeași problemă exact, și prin argumentul meu, aș face- doar atunci face 2000, dar nu știți în avans cât de mare ar trebui să fie, și totuși, eu nu trebuie să compilați programul meu înainte de a lăsa oamenii folosesc și descărcare aceasta. Astfel încât acesta este exact tipul de chestii care incearca biblioteca CS50 pentru a ne ajuta cu si vom numai ochire la unele dintre această implementare a aici, dar acest lucru este CS50 punct C. Acest este fișierul care a fost pe CS50 IDE toate aceste săptămâni care ați fost utilizați. Este pre-compilate și ai a fost folosind-o în mod automat prin natura de a avea buzna pavilion CS50 L cu zăngănit, dar dacă am defilați în jos prin toate aceste funcții, aici e getString, și doar pentru a vă oferi o gust de ceea ce se întâmplă, haideți să aruncăm o privire rapidă la de complexitatea relativă. Nu e un super lung funcție, dar nu am trebuie să se gândească tot greu despre cum de a merge despre obtinerea siruri de caractere. Deci, aici e tampon mea și eu se pare că inițializa la null. Aceasta, desigur, este același lucru ca stea char, dar am decis în punerea în aplicare a bibliotecii CS50 că, dacă vom fi complet dinamic, Nu știu în avans cât de mare de o Utilizatorii șir de gând să doriți să obțineți. Deci, am de gând să încep cu doar un șir gol și am de gând să construiască cât mai mult Memoria ca am nevoie pentru a se potrivi șir de utilizator și dacă nu am suficient, am de gând să întreb sistemul de operare pentru mai multă memorie. Am de gând să se mute șir lor într-o bucată mai mare de memorie și am de gând să elibereze sau elibera bucată mare de memorie insuficient si noi suntem doar de gând a face acest lucru iterativ. Deci, o privire rapidă, aici e doar o variabilă cu care am de gând să țină evidența din capacitatea de tampon mea. Câte bytes pot potrivi? Iată o variabilă cu n pe care am de gând să păstreze evidența cât de multe bytes sunt de fapt în tamponul sau care utilizatorul a tastat. Dacă nu ați văzut acest lucru înainte, tu poate specifica faptul că o variabilă ca un int este nesemnat, care, așa cum sugerează și numele, înseamnă că este non-negativ, și de ce ar fi Am dori vreodată să deranjez, specificând că un întreg nu este doar un int, dar este un int nesemnate? Este un int non-negativ. Ce înseamnă [neauzit] înseamnă? Audiența: E descrie o cantitate de memorie care poate fi [neauzit]. DAVID MALAN: Da. Deci, dacă spun nesemnate, aceasta este de fapt oferindu-vă un pic de memorie suplimentară și se pare un fel de prostie, dar dacă au un pic de memorie suplimentară, care înseamnă că aveți două ori mai multe valorile pe care le pot reprezenta, deoarece poate fi un 0 sau un 1. Deci în mod implicit, un int poate fi aproximativ negativ 2 miliarde de tot felul până la 2 miliarde de pozitiv. Acestea sunt domenii de mari, dar este încă un fel de risipitor dacă îți pasă doar despre dimensiuni, care tocmai intuitiv ar trebui să fie non-negativ sau pozitiv sau 0, Ei bine, atunci, de ce pierdem 2000000000 Valorile posibile pentru numere negative dacă nu sunteți niciodată de gând să le folosească? Deci, spunând nesemnate, acum Int mei pot fie între 0 și aproximativ 4 miliarde. Deci, aici e doar un int C, din motive nu vom intra în chiar acum ca de ce este un int loc de un char, dar aici este esența a ceea ce se întâmplă pe, și unii dintre voi Este posibil să utilizați, de exemplu, Funcția fgetc chiar și în patru PSET sau după aceea, vom vedea din nou în problemă set de cinci, fgetc este frumos pentru că și numele un fel de, sugerează un fel de arcanely, este o funcție care devine un personaj și așa, ceea ce este fundamental diferit despre ceea ce facem în getString este că nu utilizați scanf în același mod. Suntem doar insinuează de-a lungul pas cu pas peste tot ce utilizatorul a tastat în, pentru că putem aloca întotdeauna unul char, și astfel încât să putem întotdeauna în condiții de siguranță uita-te la un char la un moment dat, și magia începe să se întâmple aici. Am de gând pentru a defila în jos pentru a mijlocul acestei funcții doar pentru a introduce pe scurt această funcție. La fel ca exista o Funcția malloc, nu e o funcție în cazul în care realloc realloc vă permite să realoce o bucată de memorie și să-l mare sau mai mic. Povestea atât de mult timp scurt și cu un val de mâna mea pentru ziua de azi, Știu că ceea ce getString este de a face este un fel de magic în creștere sau scădere tamponul ca utilizatorul tipurile din șir sale. Deci, în cazul în care tipurile de utilizator un string scurt, acest cod numai alocă suficient memorie pentru a se potrivi șir. Dacă utilizatorul continuă să dactilografiere așa cum am făcut-o din nou și din nou și din nou, bine, în cazul în care lui tampon inițial atât de mare și programul realizează, la Stai puțin, eu sunt din spațiu, se va dubla dimensiunea buffer- și apoi dublați dimensiunea memoriei tampon și codul care face dublarea, dacă ne uităm la ea aici, e doar acest inteligent one-liner. S-ar putea să nu fi văzut această sintaxă înainte, dar dacă spui stele este egal, acest lucru este același lucru ca și spune ori de capacitate 2. Deci, doar ține dublarea capacitatea tamponului și apoi spune realloc pentru a da se că mult mai multă memorie. Acum, ca o paranteză, acolo sunt alte funcții de aici că nu vom uita în detaliu altele decât pentru a arăta în getint, vom folosi getString în getint. Noi verificam ca nu este nul, care, amintesc, este valoarea specială pe care înseamnă ceva a mers prost. Suntem din memorie. Mai bine verifica acest lucru. Și ne întoarcem o valoare santinelă. Dar voi amâna la comentariile cu privire la de ce și apoi vom folosi acest văr de scanf numit sscanf și se pare că că scanf sscanf, sau șir, vă permite să aruncăm o privire la linia care utilizatorul a tastat și l-ai lăsat analizeze, în esență, și ceea ce sunt aici este că spun sscanf, analiza indiferent utilizatorul are tastat și asigurați-vă că% i, există un întreg în ea, și nu vom intra in ziua de azi exact de ce există, de asemenea % o C aici, dar că, în scurt permite ne pentru a detecta dacă utilizatorul a introdus în ceva fals, după numărul. Deci, motivul pentru care getint și getString vă spun să încercați din nou, încercați din nou, încercați din nou este cauza tuturor acest cod am scris, e un fel de a privi la intrarea utilizatorului în a face sigur că e în întregime numeric sau este un plutitoare real Valoarea punct sau altele asemenea, în funcție de ceea ce valoare funcționează pe care îl utilizați. Whew. BINE. Asta a fost o gura dar punctul de aici este că motivul pentru care am avut aceste roți de formare privind se datorează faptului că la cel mai scăzut nivel, există doar atât de multe lucruri pe care pot merge prost pe care ne-am dorit să se ocupe de preemptively aceste lucruri cu siguranță în primele săptămâni de la clasa, dar acum cu PSET patru și cinci și PSET dincolo va veți vedea că e mult până te dar, de asemenea esti mai capabil de rezolvarea acestor tipuri de probleme te. Orice întrebări cu privire la getString sau getint? Da? Audiența: De ce ai dubla capacitatea tamponului mai degrabă decât doar în creștere prin suma exactă? DAVID MALAN: Bună întrebare. De ce ne-ar dubla capacitatea de din tamponul spre deosebire la doar o creștere de o anumită valoare constantă? A fost o decizie de design. Tocmai am decis că, deoarece tinde să fi un pic mai scump timp înțelept pentru a cere sistemul de operare pentru memorie, nu am vrei să ajungi intra in o situație pentru siruri de caractere mari că am fost cere sistemul de operare nou și din nou și din nou și din nou în succesiune rapidă pentru memorie. Deci, ne-am decis, oarecum arbitrar dar sperăm rezonabil, că, știi ce, hai să să încercați să obțineți înainte de noi înșine și chiar a păstra dublarea în așa fel încât am minimizarea cantității de ori avem de a apela sau malloc realloc, dar o judecată totală apel în lipsa de cunoaștere ceea ce utilizatorii ar putea dori să tastați în. Ambele moduri ar putea fi discutabil. Se poate argumenta că bine. Deci, haideți să aruncăm o privire la un cuplu de alte efecte secundare de memorie, lucruri care pot merge prost și instrumente pe care le puteți utiliza pentru a prinde aceste tipuri de greșeli. Se pare că voi toți, chiar dacă check50 nu ți-a spus la fel de mult, au scris buggy Codul de la o saptamana, chiar dacă toate testele sunt check50 trecut, și chiar dacă și TF dvs. sunt super încrezători că codul funcționează ca destinate. Codul dvs. a fost buggy sau viciată în care voi toți, în utilizarea bibliotecii CS50, au fost scurgeri de memorie. Ai cerut sistemul de operare pentru memorie în majoritatea programelor ai scris, dar ai nu dat de fapt înapoi. Ai sunat getString și getint și GetFloat, dar cu getString, ai nu numit unGetString sau Dă String Înapoi sau altele asemenea, dar am vazut că getString nu aloca memorie prin intermediul malloc sau această Funcția realloc, care este doar foarte similare în spirit, și totuși, am fost cere sistemul de operare pentru de memorie și memoria nou și din nou dar nu-l da înapoi. Acum, ca o parte, se pare că atunci când un program se închide, toate de memorie este eliberat în mod automat. Deci nu a fost o afacere uriașă. Nu va pentru a rupe IDE sau lucruri încetini, dar atunci când programele face scurgeri de memorie, în general, și ei de funcționare pentru o lungă perioadă de timp. Dacă ați văzut vreodată puținul prost minge de plajă în Mac OS sau clepsidra pe Windows în cazul în care este un fel de încetinirea sau de gândire sau de gândire sau pur și simplu într-adevăr începe pentru a încetini la un crawl, este foarte posibil ar putea fi rezultatul unei scurgeri de memorie. Programatorii care au scris software-ul pe care îl utilizați cere sistemul de operare pentru memorie la fiecare câteva minute, în fiecare oră. Dar, dacă rulați software-ul, chiar dacă este minimizat în calculatorul dumneavoastră timp de ore sau zile în șir, s-ar putea să ceri mai mult și mai mult memorie și niciodată de fapt, folosind-o și așa mai departe codul ar putea fi, sau programe pot fi scurgeri de memorie, și dacă începeți să scurgeri de memorie, există mai puțină memorie pentru alte programe, iar efectul este de a încetini totul. Acum, acest lucru este de departe una dintre programele cele mai atroce veți avea oportunități pentru a rula în măsura CS50 ca producția sa este chiar mai mult de ezoterice lui zăngăni sau face sau orice a comenzii programe de linie am rula înainte, dar Din fericire, încorporate în producția este câteva sfaturi foarte utile care va fi util fie pentru PSET patru sau cu siguranță PSET cinci. Deci, Valgrind este un instrument care poate fi folosită pentru a căuta pentru pierderi de memorie din programul dumneavoastră. Este relativ simplu pentru a rula. Tu a alerga Valgrind și apoi, chiar deși este un pic verbose, liniuță de verificare a scurgerilor liniuță este egal completă, și apoi dot slash și numele programului dumneavoastră. Deci, Valgrind va rula apoi programul și la sfârșitul programului dumneavoastră rulează înainte de a închide și vă oferă o altă promptă, se va analiza dvs. Programul în timp ce a fost difuzate și să vă spun ai scurgeri orice memorie și mai bine, ai atinge de memorie care nu vă aparține? Ea nu poate prinde totul, dar e destul de bun la prinderea cele mai multe lucruri. Deci, aici e un exemplu de a avea alerga meu acest program, având alerga Valgrind, pe un program numit memorie, și am de gând pentru a evidenția liniile de care sunt în cele din urmă de interes pentru noi. Deci nu e chiar mai mult de distragere care le-am șters din diapozitiv. Dar hai să vedem ce aceasta Programul este capabil de a ne spune. Este capabil de a spune lucruri noi ca scrie invalid de dimensiuni 4. Cu alte cuvinte, dacă atingeți de memorie, în special 4 bytes de memorie că nu ar trebui să aibă, Valgrind vă pot spune că. Scrie invalid de dimensiuni 4. Ai atins patru bytes că nu ar trebui să aibă. În cazul în care ai făcut asta? Aceasta este frumusetea. Dot memorie C linie 21 este în cazul în care greșit și de aceea este util. La fel ca GDB, acesta poate ajuta vă punctul de la eroarea actuale. Acum, asta e un pic mai mult verbose, dacă nu confuze. 40 bytes in 1 blocuri sunt cu siguranta pierdut în evidență pierderea 1 din 1. Ce înseamnă asta? Ei bine, aceasta înseamnă doar ai cerut 40 bytes și niciodată nu a dat înapoi. Ai sunat malloc sau te-a chemat GetString și sistemul de operare ai 40 de bytes, dar ți-a dat niciodată eliberat sau eliberat că memoria, și pentru a fi corect, am niciodată arăta cum să dea înapoi de memorie. Se pare că există un super Funcția simplu numit gratuit. Ia un argument, lucru pe care doriți să elibereze sau să dea înapoi, dar 40 de bytes, se pare, în acest program au fost pierdute la linia 20 de memorie dot c. Deci, să vedem acest program. E foarte inutil. Demonstrează doar această eroare special. Deci, haideți să aruncăm o privire. Iată principalele și principalele, anunț, apeluri o funcție numită întoarce F și apoi. Deci, nu tot ceea ce interesant. Ce face f? Observați nu am deranjez cu un prototip. Am vrut să păstreze codul pe cât posibil minim. Așa că am pus f de mai sus principal și asta e bine, cu siguranță, pentru programe scurte, cum ar fi acest lucru. Deci, f nu se întoarce nimic și nu nu ia nimic, dar nu face acest lucru. Declară, la fel ca în exemplul Binky, un pointer numit X, care se întâmplă pentru a stoca adresa de int. Deci asta e partea stângă. În limba engleză, ceea ce este partea dreaptă faci? Oricine? Ce este aceasta face pentru noi? Da? Audiența: [inaudibil] ori mai mare decât un int care este de 10 ori mai mare decât [Inaudibil] DAVID MALAN: Bine și lasă-mă să rezuma. Deci, aloca suficient spatiu pentru 10 numere întregi sau 10, ceea ce este de dimensiunea unei Int, e patru octeți, astfel încât de 10 ori 4 este 40, astfel încât partea dreaptă care le-am evidențiată este da-mi 40 de bytes și stoca adresa primului octet în x. Și acum, în sfârșit, și în cazul în care aici este acest program este buggy, ceea ce este în neregulă cu linie 21 bazat pe logica asta? Ce e în neregulă cu linia 21? Da? Audiența: Nu poți index în X [neauzit]. DAVID MALAN: Da. Nu ar trebui să indice în x de genul asta. Deci sintactic, e OK. Ce e frumos este, la fel ca tine poate trata numele unui tablou ca și cum este un pointer, în mod similar poate trata un indicator ca și cum e o matrice, și așa am putea sintactic spune X Suport ceva, x suport I, dar 10 este problematic. Ce? Audiența: Pentru că nu e înăuntru. DAVID MALAN: Nu este în interiorul că bucată de memorie. Care este cea mai mare valoare ar trebui să fi punerea în aceste paranteze drepte? 9, 0 la 9. Din cauza indexare zero. Deci, la 0 la 9 ar fi bine. Bracket 10 nu este bun și dar, deși amintesc, de fiecare dată Se pare că încerca să facă CS50 IDE accident prin tastarea în valori false, aceasta nu cooperează întotdeauna, și într-adevăr, de multe ori noroc doar pentru că Sistemul de operare nu observați că ați vreodată atât de ușor trece unele bucată de memorie, pentru că ai rămas în vedere tehnic segment, dar mai mult pe faptul că într-o clasă sisteme de operare, și așa ceva de genul asta ar putea merge foarte usor nedetectate. Programul tău nu se va prăbuși în mod constant, dar poate din cand in cand. Și astfel să încercăm Valgrind în acest sens, și aici e în cazul în care vom avea copleșit de ieșire momentan. Deci, asigurați-memorie de verificare a scurgerilor Valgrind este egal cu complet de memorie punct slash. Si iata de ce promit acest lucru ar copleși. Iată ce Valgrind, aici e ceea ce un programator, câțiva ani ago- decis că ar fi o idee bună pentru producția sa arate ca. Așa că haideți să facem sens de acest lucru. Deci tot drumul pe-o parte stânga parte pentru nici un motiv bun este ID-ul de proces a programului ne-am rula, identificatorul unic pentru programul tocmai am fugit. Am eliminat de la care slide, dar nu este unele informații utile aici. Să derulați până la foarte de sus. Iată unde am început. Deci, nu e tot atât de mult de ieșire. Iată că a scrie invalid de mărime 4 pe linia 21. Ei bine, ceea ce a fost linia 21? Line 21 a fost exact acest lucru și este logic că eu sunt în mod valabil scris 4 bytes pentru că eu sunt încercarea de a pune acest întreg, care ar putea fi orice, se întâmplă să fie zero, dar am încercat să-l pună într-o locație care nu-mi aparține. Mai mult, în jos de aici, 40 de bytes într-o blocuri sunt cu siguranta pierdut în înregistrare 1. Asta pentru că, atunci când am apel malloc aici, n-am elibera de fapt memoria. Deci, cum putem rezolva această problemă? Lasă-mă să merg mai departe și să fie un pic mai sigur și de a face 9 acolo și să-mi aici gratuit x. Aceasta este noua funcție de ziua de azi. Dacă acum rulați face dot memorie slash, să ruleze Valgrind pe el din nou, maximiza fereastra mea și a lovi Enter. Acum, e bine. Ei îngropa vestea bună în toate această ieșire. Toate blocurile heap au fost libere. Ne vom întoarce la ceea ce heap este, dar există scurgeri sunt posibile. Deci, aceasta este doar un alt instrument pentru kit instrument cu care puteți începe să găsi acum erori de genul asta. Dar să vedem ce mai pot merge prost aici. Să tranziție acum la rezolvarea de fapt o problemă. Ca o paranteza, daca acest lucru va scuti o pic de confuzie sau tensiune, acest lucru este acum amuzant. Da. Asta e destul de bun. Deoarece indicii sunt adresele și adresele sunt, în general, prin convenție scris cu hexazecimal. Ha, ha,, e amuzant acum. Oricum, Să acum rezolva de fapt o problemă. Acest lucru a fost super, super-nivel scăzut până acum, si putem face de fapt utile lucruri cu aceste detalii de nivel scăzut. Deci, am introdus câteva săptămâni acum noțiunea de matrice. O serie a fost frumos pentru că este greu pentru a curăța codul nostru pentru că dacă am vrut să scrie o program cu multiple studenți sau mai multe nume și case și cămine și colegii și toate astea, am putea stoca tot mai curat în interiorul unei matrice. Dar propune un dezavantaj de o serie de până acum. Chiar dacă nu ați suferit-te într-un program, doar instinctiv, ceea ce este un lucru rău despre un tablou, poate? Am auzit niște murmure. Audiența: Este dificil pentru a modifica dimensiunea. DAVID MALAN: Este dificil pentru a modifica dimensiunea. Nu puteți modifica dimensiunea al unui tablou, în fapt, în sine în C. Puteți aloca o altă matrice, muta totul, de la cel vechi în noi, și acum au unele spațiu suplimentar, dar nu e ca o limbă ca Java sau Python sau orice număr de alte limbi cu care unii dintre voi s-ar putea să fie familiarizat în cazul în care pot păstra doar adăugarea lucruri ad nauseam la sfârșitul unei matrice. Când aveți o serie de Dimensiunea 6, care este dimensiunea sa, și atât de mult ca ideea mai devreme având un tampon de o anumită dimensiune, va trebui să ghicească din poarta ce dimensiune vrei să fie? Dacă ați ghicit prea mare, îți pierzi spațiu. Dacă ați ghicit prea mici, nu se poate stoca aceste date, cel puțin fără o mult mai mult de lucru. Așa că astăzi, datorită indicii, putem începe împletit împreună propriul nostru personalizat structuri de date, și în De fapt, aici este ceva care arată un pic mai mult criptic la prima vedere, dar acest lucru este ceea ce numim noi o legătură vom listă, iar numele său a rezumă fel aceasta. Este o listă de numere, sau în acest caz, o listă de numere, dar ar putea fi o listă de nimic, dar e legate între ele prin intermediul săgeți, și să ia doar o presupunere cu ce tehnica vom fi capabili la cusatura împreună, un fel de floricele cu un fir, un legat liste dreptunghiuri aici? Numerele sale? Care este funcția de bază de limbă? Audiența: Un pointer. DAVID MALAN: Un pointer. Deci, fiecare dintre aceste săgeți reprezintă aici un pointer sau doar o adresă. Deci, cu alte cuvinte, dacă vreau pentru a stoca o listă de numere, Nu pot să-l păstrează dacă vreau capacitatea de a dezvolta și micșora structura mea de date într-o matrice. Așa că am nevoie pentru a avea un pic de mai mult rafinament, dar observați că această Imaginea fel de sugerează că, dacă tocmai ați luat fire mici conectarea totul împreună, probabil, nu este așa de greu pentru a face loc între două dintre aceste dreptunghiuri sau două dintre aceste noduri, așa cum vom începe numindu-le, a pus într-un nou nod, și apoi cu unele noi fir, doar șanț cele trei noduri împreună, prima, ultima, și cea pe care tocmai ați introdus în mijloc. Și într-adevăr o listă legată, spre deosebire de o matrice, este dinamic. Se poate să crească și se poate psihiatru și nu Trebuie să știi sau de îngrijire în avans cum Date de mult ai de gând să fie stocarea, dar se pare că trebuie să fie un pic atent cu privire la modul în care să pună în aplicare acest lucru. Deci, în primul rând să ia în considerare modul în care punem în aplicare unul dintre aceste dreptunghiuri mici. Este ușor să pună în aplicare un int. Tu spui doar int n și apoi te 4 octeți pentru un int, dar cum a face I a lua un int, o numesc n, și apoi un pointer, să o numim viitor. Am putea numi aceste lucruri orice vrem dar am nevoie de o structură de date personalizat. Da? Audiența: Ampersand [neauzit]. DAVID MALAN: Deci ampersand vom folosi pentru a obține adresa unui nod potențial. Dar avem nevoie de un alt caracteristică de C, în scopul să-mi dea posibilitatea de a crea acest dreptunghi personalizate, acest obicei variabilă dacă vreți, în memorie. Audiența: Un struct. DAVID MALAN: A struct. Amintiți de săptămâna trecută, am introdus struct, acest cuvânt cheie relativ simplu care ne permite să face lucruri de genul asta. C nu a venit cu o date structura numita elev. Acesta este dotat cu Int și float și char și astfel, dar aceasta nu vine cu elevul, dar putem crea un tip de date de student, o structură de student, cu această sintaxă Aici. Și veți vedea acest lucru din nou și din nou. Deci, nu vă faceți griji cu privire la memorarea cuvintele cheie, dar cuvântul cheie care este important este doar faptul că am spus struct și apoi l-am sunat de student și în interiorul de student a fost un nume și o casă sau un cămin sau altele asemenea. Și așa acum astăzi, să propună acest lucru. Am adăugat câteva cuvinte, dar dacă vreau să pună în aplicare acest dreptunghi care este Trebuie atât un int și o pointer, știi ce, eu sunt O să declare o struct numit nod. Sunt, de asemenea,, în interiorul acestuia, de gând să spun că un nod, acest dreptunghi, are un int și vom numi n și are un pointer următoare. Și aceasta este un pic verbose, dar dacă te gândești la asta, săgețile care erau în imagine un moment în urmă sunt de ce tip de date? În cazul în care fiecare dintre aceste săgeți este îndreptat la ce tip de structură de date? Nu este îndreptat doar la un int sine. Este arătând spre toată chestia dreptunghiular și chestia aia dreptunghiulară, am spus, este numit un nod. Și așa am un fel de trebuie să defini recursiv acest cum că un nod, vom spune, va conține un int numit n și un pointer numita viitor și tip de structură de date la care că indicatorul este aparent va fi nod struct. Deci acest lucru este enervant verbose și doar pentru a fi pedant, motivul pentru care nu putem doar spun acest lucru, care sincer pare mult mai ușor de citit, se datorează faptului că amintesc că C citit lucruri de sus în jos, la stânga la dreapta. Nu e până când vom obține punct și virgulă că de fapt există nodul de cuvinte cheie. Deci, dacă vrem să avem acest tip de referință ciclică interiorul a datelor structură, trebuie să facem acest lucru, în cazul în care spunem nod struct în partea de sus, care ne oferă o modalitate de a descrie acest mai lucru, apoi în interiorul spunem nod struct, și apoi în ultimul linie spunem, bine, C, de altfel, sună al naibii de tot acest lucru un nod și se va opri folosind cuvinte cheie struct cu totul. Deci, aceasta este doar un fel de sintactic truc pe care în cele din urmă ne permite să creați ceva care arată exact ca aceasta. Deci, dacă presupunem acum putem punerea în aplicare a acestui lucru în C, cum putem de fapt începe traversează acest? Ei bine, de fapt, tot ce trebuie să faceți este să repeta de la stânga la dreapta și doar un fel de a introduce noduri sau șterge noduri sau sa cautati lucruri oriunde ne-o dorim, dar pentru a face acest lucru, să mergem mai departe și să facă lucrurile un pic mai real, deoarece acest a fost super-nivel scăzut până acum. Vrea cineva literalmente pentru a fi primul? BINE. Haide sus. Care e numele tău? DAVID: David. DAVID MALAN: David. Îmi pare bine să te cunosc. Eu la fel. In regula. Și avem nevoie de un număr de 9. Nu la fel de bun ca primul, poate. OK, numărul 9. Un număr de 17, vă rog. Lasă-mă să mă întorc un pic mai departe. Numărul 22, te rog, și Ce zici de departe înapoi dacă pot vedea orice mâinile cu toată lumina sau nu. Cineva sa oferit voluntar să fie chiar acolo. Vrei să vină? Antebratul este forțat în creștere. OK, 17. 22. 26 vine în jos. Ar dori să oricine altcineva forcefully-- Haide sus. Un voluntar actuale. Deci foarte repede, în cazul în care voi putea aranja vă place doar nodurile de pe ecran. Multumesc. Și veți fi 26. Toate introduceri corecte și rapide. Deci, eu sunt David și tu sunt, de asemenea? DAVID: David. DAVID MALAN: Și tu ești? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Excelent. Deci, acestea sunt voluntarii nostri pentru ziua de azi și mergeți mai departe și trecerea în acest fel un pic, și du-te mai departe și să păstreze exploatație numerele ca esti sau dvs. Primul semn și cu mâna stângă, mergeți mai departe și să pună în aplicare doar aceste săgeți, doar astfel încât mâna stângă este literalmente arătând la tot ce ar trebui să arate la, si da-te unele cameră, astfel încât putem vedea vizual bratele de fapt îndreptat, și vă poate indica doar un fel de la sol este bine. Deci, aici avem o listă legată de una, două, trei, patru, cinci noduri inițial, și observați avem această speciale pointer la începutul cine e cheie, deoarece avem de a urmări din toata lista lungime cumva. Tipii ăștia, chiar dacă ele sunt lăsate la dreapta, spate în spate în memorie, ele pot fi de fapt oriunde în memoria calculatorului. Deci tipii ăștia ar putea fi picioare oriunde pe scena și asta e bine, atâta timp cât acestea sunt de fapt, arătând spre un altul, dar pentru a menține lucrurile curat și simplu, vom doar le trage la stânga la dreapta la fel ca acest lucru, dar ar putea exista lacune masive între aceste noduri. Acum, dacă vreau să insera de fapt, unele valoare nouă, să mergem mai departe și de a face acest lucru. Avem o oportunitate de acum pentru a alege un alt nod. Spune să începem cu mallocing 55. Ar deranja cineva fiind malloc? OK, haide sus. Care e numele tău? RAINBOW: Rainbow. DAVID MALAN: Rainbow? In regula. Malloc Rainbow. Haide sus. Deci, acum trebuie să ne întrebăm algoritmic unde putem pune 55. Deci, noi toți știm, evident, în cazul în care ea, probabil, aparține dacă încercăm pentru a menține această sortate și dacă voi putea lua o un pas înapoi ca să nu cad de pe etapa, care ar fi grozav. Deci, de fapt, Rainbow, începe aici cu mine, pentru că noi, ca computerul acum poate vedea doar o variabilă la un moment dat. Deci, dacă acest lucru este primul nod. Observați că nu este un nod, e doar un pointer, și de aceea el atras de fi numai dimensiunea unui pointer, nu unul dintre acele dreptunghiuri pline. Deci vom verifica la fiecare iterație este mai mică de 55 9? Nu. Este mai puțin de 55 17? Nu. Mai puțin de 22? Mai puțin de 26? Mai puțin de 34? Și așa acum, în mod evident, Curcubeu face parte, la sfârșitul. Deci, să fie clar, și ce a fost numele tău, Taylor? TAYLOR: Taylor. DAVID MALAN: Deci între lui Taylor stânga și mâinile Rainbow e aici, a cărui mână are nevoie pentru a indica la ce în Pentru a insera 55 în această listă? Ce trebuie să facem? Da? Audiența: mâna lui Taylor trebuie să punctul din stanga. DAVID MALAN: Exact. Deci, introducerea unui nod în capătul listei este destul de simplu, deoarece Taylor doar ului trebuie sa fie, in loc de la sol sau vom numi nul, nul este un fel de lipsa de un pointer sau o special pointer la zero, ești merge de la punctul cu stânga mână la Rainbow și apoi Rainbow, în cazul în care ar trebui să stânga mână, probabil, punctul? Jos. Nu e bine, dacă mâna este un fel de îndreptat off aici sau orice fel de in ce directie. Asta ar fi considerate o valoare de gunoi, dar dacă ea arată spre o valoare cunoscută, vom numesc zero sau nul, e OK pentru că avem un termen în acest și știm lista acum este completă. Deci, ce este un alt caz relativ simplu? Putem malloc 5? Haide sus. Care e numele tău? TIFFANY: Tiffany. DAVID MALAN: Îmi pare rău? TIFFANY: Tiffany. DAVID MALAN: Tiffany. In regula. Tiffany a fost malloced cu valoarea 5. Haide sus. Asta e relativ usor de asemenea, dar să luăm în considerare pentru a operațiunilor de acum. A fost destul de ușor cu Taylor la sfârșitul anului. Numărul 5 este, desigur, mai puțin de 9, și așa ne-am pe David, avem Tiffany, și ceea ce a fost numele tău? JAKE: Jake. DAVID MALAN: Jake. Tiffany, Jake, și David. A cărui mână ar trebui să fie actualizate în primul rând? Ce vrei să faci aici? Există câteva posibile moduri, dar există, de asemenea una sau mai multe moduri greșite. Audiența: Începeți cu stânga. DAVID MALAN: Începeți cu cel mai din stânga. Cine e cel mai din stânga aici atunci? Audiența: Prima. DAVID MALAN: OK. Deci, începe cu primul și în cazul în care nu-i doriți să actualizați mâinile lui David să fie? Audiența: Spre 5. DAVID MALAN: OK. Deci David, punct de la cinci sau Tiffany aici, și acum? Audiența: Tiffany puncte la 9? DAVID MALAN: Perfect, cu excepția lui Binky șef doar un fel de a căzut, nu? Pentru că ceea ce e în neregulă cu această imagine literalmente? Audiența: Nimic nu este îndreptat. DAVID MALAN: Nimic nu este arătând spre Jake acum. Am orfani literalmente 9 și 17, și ne-am literalmente scurgeri toate acestea memorie, deoarece de actualizarea mâna lui David în primul rând, asta e amendă în măsura în care este în mod corect arătând la Tiffany acum, dar dacă nimeni nu a avut previziune pentru a indica la Jake, apoi ne-am pierdut toate elementele de lista. Deci, haideți să anulați. Deci, asta a fost un lucru bun pentru excursie peste dar să corecteze acum. Ce ar trebui să facem mai întâi în schimb? Da? Audiența: Tiffany ar trebui să punct la 9? DAVID MALAN: Nu pot obține că aproape de tine. Cine ar trebui să arate la 9? Audiența: Tiffany. DAVID MALAN: Bine. Deci, ar trebui să Tiffany primul punct la 9. Deci, ar trebui să ia Tiffany pe o valoare identică David, care pare redundant pentru un moment, dar asta e bine pentru că acum, în al doilea rând pas, putem actualiza mâna lui David la punctul de la Tiffany, și apoi, dacă noi doar un fel de curat lucrurile ca și cum acest lucru este un fel de-primăvară cum ar fi, Acum, că e un introducere corectă. Deci excelent. Deci, acum suntem aproape acolo. Să introduceți un finală Valoarea ca valoarea 20. Dacă am putea malloc o voluntar finală? Haide sus. Deci asta e un pic mai complicat. Dar, de fapt, codul suntem scris, deși verbal, este la fel ca având un buchet de cazul în care condițiile acum, nu? Am avut o stare a verifica dacă acesta face parte la final, poate la început. Avem nevoie de un fel de buclă la găsi locul în mijloc. Deci, hai sa facem asta cu care e numele tău? ERIC: Eric. DAVID MALAN: Eric? Eric. Îmi pare bine să te cunosc. Deci avem 20. Mai puțin de cinci? Nu. Mai puțin de nouă? Nu. Mai puțin de 17? Nu. BINE. El aparține aici și numele voastre din nou sunt? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, și? ERIC: Eric. DAVID MALAN: Eric. Ale căror mâini nevoie pentru a obține actualizate primul? Audiența: Eric. BINE. Deci, Eric ar trebui să arate la unde? La 22. Bine. Și acum ce urmează? Sue poate indica apoi la Eric și acum, dacă voi doar face unele cameră, ceea ce este bine vizual, acum am făcut introducerea. Deci, haideți să considerăm acum o întrebare, dar vă mulțumesc foarte mult pentru voluntarii nostri. Foarte bine facut. Puteți să vă păstrați cei, dacă doriți. Și avem un cadou minunat de despărțire, dacă ai dori să ia fiecare o minge de stres. Lasă-mă să trec acest jos. Deci, ce este MENIUL de asta? Aceasta pare a fi uimitor în măsura în care avem acum introdus o alternativă la un matrice care nu este atât de limitat la o serie de unele dimensiune fixă. Ele se pot dezvolta dinamic. Dar la fel ca le-am vazut in saptamani trecut, nu am primit nimic gratis, ca sigur nu e un compromis aici. Deci, cu o cu susul unui legat lista, este acest dinamism? Acest lucru capacitatea de a dezvolta și sincer, am fi putut face de ștergere și am putea reduce după cum este necesar. Ce preț plătim? De doua ori mai mult spațiu, în primul rând. Dacă te uiți la imagine, nu mai sunt eu stocarea o listă de numere întregi. Am stocarea o listă de întregi, plus indicii. Deci, eu sunt dublarea cantității de spațiu. Acum, poate că nu e așa o mare de 4 bytes, 8 octeți, dar s-ar putea adăuga cu siguranță pentru seturi mari de date. Ce este un alt dezavantaj? Da? Audiența: Trebuie să le traversa-o de-o. DAVID MALAN: Da. Trebuie să le traversa-o de-o. Știi ce, am renunțat la acest super- caracteristică convenabil de suport pătrat notație, mai adecvat cunoscut sub numele de acces aleatoriu, unde putem sări doar la un element individual dar acum, dacă am avut încă voluntari mele de aici, dacă am vrut pentru a găsi numărul 22, nu pot doar sări la suport ceva ceva. Trebuie să se uite peste lista, mult ca exemplele noastre de cautare avansata liniar, pentru a găsi numărul 22. Deci, se pare că am plătit un preț acolo. Dar putem, totuși, rezolva alte probleme. De fapt, permiteți-mi să introducă doar o pereche de imagini. Deci, dacă ați fost în jos pentru a Sală de mese Mather recent, vei aminti că lor stive de tăvi de acest fel, am împrumutat de la acestea Annenberg înainte de clasă. Deci, acest teanc de tăvi, deși, este reprezentativ de fapt de o structură de date informatică. Există o structură de date în informatică cunoscut ca un stack care foarte bine se pretează la exact acest vizuală. Deci, dacă fiecare dintre aceste tăvi nu este o tava dar ca un număr și am vrut pentru a stoca numere, am ar putea pune o jos aici și am putea pune un alt aici, și să continue stivuire numere pe partea de sus a unul pe altul, și ceea ce este potențial utile despre acest este că ceea ce este implicarea de această structură de date? Ce număr pot scoate Primul cel mai convenabil? Cel mai recent, o pune pe acolo. Deci, asta este ceea ce am numi în informatică o structură de date LIFO. Ultima în, primul ieșit. Și vom vedea înainte de mult timp de ce care ar putea fi utilă, dar pentru acum, ia în considerare doar de proprietate. Și e un fel de prost, dacă credeți despre modul în care sala de mese o face. De fiecare dată când tăvi curate și pune cele mai proaspete pe partea de sus, ai putea avea un curat anterior dar în cele din urmă foarte murdar și plin de praf tava la partea de jos foarte Dacă nu, de fapt ajunge la partea de jos a care stack, pentru că doar păstra punerea noi și cele curate pe partea de sus a acesteia. Același lucru s-ar putea întâmpla într-un supermarket prea. Dacă aveți un caz de afișare de lapte și de fiecare dată CVS sau oricine devine mai mult lapte, doar împinge tipurile de lapte aveți deja în spate și ai pus cele noi în față, vei avea unele destul de urât lapte la capătul structurii de date, pentru că este întotdeauna în partea de jos sau echivalent este întotdeauna la partea din spate. Dar există un alt mod de a gândi despre alinierea datelor și, de exemplu, aceasta. Daca esti unul din acei oameni care îi place pentru a alinia în afara magazinelor Apple atunci când un nou produs vine out, esti, probabil, nu folosind un date stivă Structura pentru că ar îndepărta oricine altcineva care este garnitură de până la cumpere o nouă jucărie. Mai degrabă, esti, probabil, utilizați Ce fel de structură de date sau ce fel de sistem în lumea reală? Sperăm că este o linie, sau mai mult în mod corespunzător sau mai mult British-cum ar fi, o coadă. Și se pare că o coadă este de asemenea un structură de date în informatică, dar o coadă are o foarte proprietate diferite. Nu e LIFO. Ultima în, primul ieșit. Doamne ferește. Este în schimb FIFO. În primul rând, în, primul ieșit. Si asta e un lucru bun de dragul corectitudinii " cu siguranță atunci când sunteți căptușeală up super-devreme în dimineața. Dacă ajungi acolo în primul rând, vă doriți să obțineți mai întâi, de asemenea. Și astfel toate aceste date structuri, cozile și stive și ciorchini de alții, se dovedește te poate gândi la acest lucru ca doar un tablou. Aceasta este o matrice, poate o dimensiune fixă ​​de 4, dar ar fi un fel de frumos dacă am putea îngrămădi doar tăvi aproape infinit de înalt, dacă ne-am au ca multe tăvi sau numere. Deci, poate vrem să utiliza o listă legată aici, dar compromisul va fi potențial că avem nevoie de mai multă memorie, ia un pic mai mult timp, dar am nu limitează înălțimea stivei, la fel ca vitrina Mather lui s-ar putea limita dimensiunea stivei, și astfel încât acestea sunt decizii de proiectare sau opțiunile disponibile pentru a ne în cele din urmă. Deci, cu aceste date structuri, am început văzând noi limite superioare potențial asupra a ceea ce anterior a fost super rapid și în cazul în care vom pleca off astăzi și în cazul în care vom sperăm să ajungem la este miercuri, vom începe să se uite la o date structură care ne permite să căuta prin date în timp final jurnal din nou. Și am văzut că, amintesc, în săptămâna zero, și unul cu căutare binară sau divizare și cuceri. Vine înapoi și mai bine, Sfântul Graal pentru miercuri va fi de a veni cu structură de date care ruleaza cu adevărat sau teoretic în constantă de timp, în care nu contează cât de multe milioane sau miliarde de lucruri avem în structura de date, se va du-ne constantă de timp, poate cu un pas sau două etape sau 10 pasi, dar numărul de pași constante pentru a căuta prin această structură de date. Că într-adevăr va fi Sfântul Graal dar mai mult pe faptul că miercuri. Ne mai vedem atunci. [MUSIC JOC]