>> [Glazbom]
>> [VIDEO PLAYBACK]
>> -On Laže.
>> -O čemu?
>> -Ne Znam.
>> -Pa Što znamo?
>> -To Na 9:15, Ray Santoya bio na bankomatu.
-Da.
Dakle, pitanje je, što je radio u 9:16?
>> -Shooting Na 9 milimetar na nešto.
Možda je vidio snajper.
>> -Ili Je radio s njim.
>> -Wait.
Vrati se jedan.
>> -Što vidiš?
>> -Bring Lice do punog zaslona.
>> -His Naočale.
>> -Postoji Je odraz.
>> -To Je Nuevitas bejzbol momčad.
To je njihov logo.
>> -I On je u razgovoru s tko je nosio tu jaknu.
>> [END PLAYBACK]
>> DAVID Malan: U redu.
Ovo je CS50 i to je malo više od [nečujan] s kojima ste
brbljanje s problemom postaviti četiri.
Danas ćemo početi gledati malo više Duboko u te stvari zovu naputke,
koji, iako je prilično Arcane tema,
ispada da će biti sredstvo kojim ćemo
možete početi graditi i montaže mnogo više sofisticirane programe.
Ali mi je to na prošlu srijedu pomoću nekog prvog claymation.
Dakle, to, podsjetimo, je Binky ga koristili smo
uzeti pogledati program koji zapravo nije to ništa zanimljivo,
ali je otkrio nekoliko problema.
Dakle, za početak danas, zašto ne živimo brzo kroz neke od tih koraka,
pokušati destilirati u ljudske uvjete upravo ono što se događa ovdje
i zašto je to loše, a zatim prijeđite na i zapravo početi graditi nešto
s ovom tehnikom?
Dakle, to su bili prvi dvije linije u ovom programu
te u laik uvjete, što se su ove dvije linije radi?
Netko tko je razumno udoban s tim što je proglasio na zaslonu?
Koje su to dvije linije rade?
To nije sve što je razlikuje od tjedan jednom,
ali postoji neki novi poseban simbol.
Da?
Povratak postoji.
>> PUBLIKA: Onaj upućuje?
DAVID Malan: Reci opet?
PUBLIKA: Onaj upućuje?
DAVID Malan: proglašavanje naputke i budimo pročistite malo više.
PUBLIKA: [nečujan] Adresa X i zatim y.
DAVID Malan: I onda rješavati.
Dakle, konkretno što radimo je da se proglašenje dvije varijable.
Te varijable, ipak, idu biti tipa int zvijezde, koje
točnije znači oni su idući za pohranu
adresu int, odnosno, X i Y.
Sada postoje li vrijednosti?
Postoje li stvarni adrese u njih dvije varijable u ovom trenutku?
Ne.
To je samo tzv vrijednosti smeće.
Ako ne zapravo dodijeliti varijabla, sve što je u RAM
prethodno će se popuniti s nulama i one su obje od tih varijabli.
Ali mi još uvijek ne znam što su i kako je
će biti ključ zašto Binky izgubio glavu prošli tjedan.
>> Dakle, to je bio claymation utjelovljenje toga
gdje imate samo dvije varijable, mali kružne komada gline,
koji može pohraniti varijable, ali kao je zavrsio strelice ukazuju,
oni ne zapravo pokazujući gdje se samo po sebi poznato.
Pa onda smo imali ovu liniju, a to je nova prošlog tjedna, malloc za pamćenje
raspodjele, koji je samo fancy način reći operativni sustav, Linux
ili Mac OS ili Windows, hej, dajte mi neke memorije,
i sve što morate reći operativni sustav
je ono kad ga pita za pamćenje.
To neće brinuti što ti ćeš učiniti s njim,
ali to ne treba reći radom Sustav ono putem malloc.
Da?
>> PUBLIKA: Koliko?
DAVID Malan: Koliko?
Koliko u bajtovima, i tako, to, opet, neprirodan primjer, samo je rekao:
daj mi veličinu int.
Sada, veličina int je četiri bajta ili 32 bita.
Dakle, ovo je samo način govoreći, hej, operativni sustav,
daj mi četiri bajta memorije da ja mogu koristiti na mom raspolaganju,
a posebno, što se malloc povratak s poštovanjem
na taj komad četiri bajta?
PUBLIKA: Adresa?
DAVID Malan: adresa.
Adresa tog komad četiri bajta.
Točno.
I tako to je ono što je pohranjena u konačnici u X i to je razlog zašto mi ne stvarno
briga što je broj koji adresa, da li je ox1 ili OX2
ili neki zagonetan heksadecimalni adresu.
Mi smo samo stalo slikovno da je varijabla x je sad
pokazujući na taj komad memorije.
Dakle strelica predstavlja pokazivač, ili točnije, memorijsku adresu.
Ali opet, mi obično ne briga ono što oni stvarni adrese su.
Sada, ovaj redak govori ono što je u laik uvjete?
Star x dobiva 42 zarezom.
Što to znači?
Želiš ići?
Nemojte ispočetka vrat.
>> PUBLIKA: Adresa X na 42.
>> DAVID Malan: Adresa X na 42.
Ne baš.
Tako blizu, ali ne sasvim, jer je zvijezda koja je prefixing ovaj x.
Dakle, moramo štipanje malo.
Da?
>> PUBLIKA: Vrijednost da pokazivač x ukazuje na je 42.
DAVID Malan: U redu.
Vrijednost da pokazivač x ukazujući na, recimo, bit će 42,
ili staviti drugi način, zvijezdu X kaže, ići na bilo adresu
je x, bilo da je 1 Oxford Ulica ili 33 Oxford Street
ili ox1 ili ox33, što god da numerička adresa,
Star je x dereferencing x.
Dakle, ići na tu adresu i zatim staviti broj 42 tamo.
Tako da bi bilo ekvivalent način govoreći da je.
Tako da je sve u redu, a zatim bismo predstavljaju sliku
kako slijedi kojoj smo dodali 42 na taj komad četiri
bajtova na desnoj strani, ali Ova linija je gdje stvari ode naopako
i Binky glava popped off u ovom trenutku,
jer se loše stvari događaju kada što dereference vrijednosti smeća
ili dereference nevažeći naputke, a ja kažem nevažeći
jer u ovom trenutku u Priča, ono što je unutar y?
Što je vrijednost y temelji na proteklih nekoliko koraka?
Da?
Što je to?
>> PUBLIKA: adresu.
DAVID Malan: adresu.
To bi trebao biti adresa ali sam ga inicijalizirati?
Dakle, imam još nisu.
Dakle, što se zna da je tamo?
To je samo neki smeća vrijednost.
To bi mogao biti bilo adresa od nula do 2 milijarde ako imate dva nastupa RAM,
ili nula do 4 milijarde, ako ste dobio četiri gigabajta RAM-a.
To je neka smeća vrijednost, ali problem je
koji operativni sustav, ako nije ti dao
koji komad memorije posebno da ste pokušavate ići,
općenito će izazvati što vidjeli smo kako je greške segmentacije.
Dakle, u stvari, bilo tko od vas koji imaju borili na probleme u uredovno vrijeme
ili problemima koje je više obično s pokušavate odgonetnuti
segmentiranja kvar, to obično znači
ti dira segment memorije da ne bi trebalo biti.
Vi dira sjećanje koje operativni sustav nema
dopustio da dotakne, da li je tako ide predaleko u svom nizu
ili početkom sad, je li to je zato jer ste dira
memorije da je samo neka smeće vrijednost.
>> Dakle, radi zvijezda x ovdje vrsta nedefiniranog ponašanja.
Vi nikada ne bi trebao to učiniti, jer izgledi su, program samo će srušiti,
zato što govoriš, idite na ovu adresu
a vi nemate pojma gdje to je zapravo adresa.
Pa operativni sustav je vjerojatno će se srušiti vaš program
kao rezultat i doista, to je što se dogodilo tamo Binky.
Dakle u konačnici, Binky fiksna ovaj problem s tim.
Dakle, taj program sam po sebi je manjkav.
Ali ako vrsta kretati i izvršiti tu liniju, umjesto,
y jednako x samo znači ono adresa je x, također ga staviti u y.
>> I tako slikovito, mi smo zastupljena s dvije strelice
od X i od y usmjerenim na istom mjestu.
Dakle semantički, x je jednaka y jer obje onih
pohranjujete isti adresa, ergo pokazujući na 42,
i sad, kad kažeš zvijezda y, idite na adresu u y,
to ima zanimljivu nuspojavu.
Dakle adresa y je Ista stvar kao adresu u x.
Dakle, ako ti kažeš ići na adresu u y i promijenite vrijednost na 13,
tko još je pod utjecajem?
X, točka D, da tako kažemo, treba utjecati, kao dobro.
>> I doista, kako je Nick nacrtao ovu sliku u claymation je upravo to.
Iako pratimo pokazivač y, završili smo na istom mjestu,
pa ako smo bili za ispis iz X ili Y je pointee,
onda bismo vidjeli vrijednost 13.
Sada, ja kažem pointee se u skladu sa slikom.
Programeri, na moje znanje, zapravo nikada
reci pointee, ono što je šiljasta
, ali zbog dosljednosti s video, shvatiti
to je sve što je bilo znači u toj situaciji.
Dakle bilo kakvih pitanja o claymation ili naputke ili malloc samo još?
Ne?
U redu.
>> Dakle, bez daljnjeg ado, neka je pogledati
u kojoj to ima zapravo je korišten za neko vrijeme.
Tako smo imali ovu CS50 knjižnici koji je dobio sve te funkcije.
Koristili smo GetInt puno, GetString, Vjerojatno GetLongLong ranije
u mom PSet jedan ili tako, ali Što se zapravo događa?
Pa, neka je uzme brzi pogled ispod haube na program koji
nadahnjuje zašto smo Vam dati CS50 knjižnica, i doista od prošlog tjedna,
počeli smo uzimati one Trening kotači off.
Dakle, to je sada razvrstani o nakon smrti onoga
traje unutar CS50 knjižnici,
iako smo sada će početi kreće daleko od toga za većinu programa.
>> Dakle, ovo je program pod nazivom scanf 0.
To je super kratka.
To je upravo ove retke, ali to uvodi funkcija zove scanf
da smo zapravo ćete vidjeti trenutak unutar CS50 knjižnici,
iako u nešto drugačijem obliku.
Dakle, ovaj program na liniji 16 je proglašenje varijablu x.
Pa daj mi četiri bajta za int.
To je bio govorio korisnika, Broj molimo, a potom
ovo je zanimljiv linija koja zapravo veže zajedno prošli tjedan
i to.
Scanf, a zatim primijetite da traje Format string, baš kao printf,
% i znači int, a onda to traje Drugi argument koji izgleda malo
funky.
To je znak za struju x, i podsjetiti, smo vidjeli samo ovaj put prošli tjedan.
Što znak za struju x predstavlja?
Što učiniti u znak za struju C?
Da?
>> PUBLIKA: Adresu.
DAVID Malan: Adresu.
Dakle, to je suprotno operatora zvjezdice,
dok je operator zvijezda kaže, idite na ova adresa, znakom operater
kaže, shvatiti adresu te varijable,
pa to je ključ, jer scanf je svrha u životu
je skenirati korisnik je unos s tipkovnice,
ovisno o tome što on ili ona vrste, a zatim pročitao da je ulaz korisnika
u varijablu, ali mi Vidio je u protekla dva tjedna
da je zamjena funkcija koje smo Pokušao napora za provedbu
Samo slomljen.
Sjetite se da s funkcijom swapu, ako mi samo proglasio A i B, kao Ints,
uspješno je swap dvije varijable unutar swapa
baš kao i sa mlijekom i SL, ali čim se vratio zamjena,
što je bio rezultat s obzirom za x i y, izvorne vrijednosti?
Ništa.
Da.
Ništa se nije dogodilo da je vrijeme, jer je swaps promijeniti samo svoje lokalne kopije,
što će reći, sve ovaj put, kad god imamo
prolazio je u argumentima funkcijama, mi smo
samo u prolazu kopije tih argumenata.
To možete učiniti s tim što god želite s njima,
ali oni će imati nikakav utjecati na izvorne vrijednosti.
Dakle, to je problematično, ako vas Želite imati funkciju kao scanf
u životu, čija je svrha za skeniranje korisnikov unos s tipkovnice
a zatim popuniti praznine, tako da se govore, odnosno, dati varijablu poput x
vrijednost, jer ako sam ja samo proći X za scanf,
ako uzmete u obzir logiku posljednji tjedna, scanf može raditi što god želi
s kopijom x, ali to ne može trajno promijeniti x osim dajemo
scanf karta blaga, da se tako izrazim, gdje je X označava mjesto, pri čemu
prolazimo adresu x tako da scanf može ići tamo i zapravo promjene
vrijednost x.
I tako doista, sve da je ovaj program radi
ako bi scanf 0, u mom izvoru 5m katalog, provjerite scanf 0,
dot slash scanf, broj molim 50, hvala na 50.
>> Dakle, to nije sve što je zanimljivo, ali ono što doista događa
je da čim sam nazvao scanf ovdje, vrijednost x
se stalno mijenjaju.
Sada, ovo izgleda lijepo i dobro, i zapravo, to
Čini se kao da stvarno ne treba CS50 knjižnica na sve više.
Na primjer, neka je trčanje ovo još jednom ovdje.
Dopustite mi da ga ponovno na sekundu.
Pokušajmo broj molimo te umjesto da kaže 50 kao i prije,
neka je samo reći ne.
U redu, to je malo čudno.
U REDU.
I samo su neke gluposti ovdje.
Dakle, to ne čini da nositi pogrešnih situacije.
Dakle, trebamo minimalno početak dodao neke pogreške pravopisa
kako bi bili sigurni da korisnik ima upisali u stvarnog broja kao i 50,
jer očito upisivanjem riječi nije otkrivena kao problematično,
ali vjerojatno bi trebao biti.
>> Pogledajmo ovu verziju sada je to moj pokušaj da reimplement GetString.
Ako scanf ima sve to funkcionalnost sagrađena,
Zato smo bili brbljanje s njima Trening kotači poput GetString?
Pa, ovdje je možda moja jednostavna verzija GetString
gdje je prije tjedan dana, možda sam rekao, dajte mi string i nazvati ga tampon.
Danas ću početi jednostavno rekavši char zvijezdu, koja je, opoziv,
to je samo sinonimi.
Izgleda strasnije, ali to je točno istu stvar.
Pa daj mi varijablu naziva tampon koje će pohraniti string,
reći korisnički string molimo, a onda, baš kao i prije,
pokušajmo posuditi ovu lekciju scanf % s ovog puta, a zatim prođe u puferu.
Sada, brza provjera razum.
Zašto se ne govori znak za struju tampon ovaj put?
Zaključiti iz prethodnog primjera.
PUBLIKA: Char zvijezda je pokazivač.
DAVID Malan: Točno, jer ovaj put, char
Star je već pokazivač, adresa, po definiciji tog zvijezde biti tamo.
A ako scanf očekuje adresu, dovoljno je samo da prođe u puferu.
Ne trebam reći ampersand tampon.
Za radoznale, što bi učiniti nešto ovako.
Bilo bi drugačije značenje.
To će vam dati pokazivač na pokazivač, koji je zapravo
valjana stvar u C, ali za Sada, neka je i dalje ostane jednostavan
i zadržati priču dosljedna.
Samo ću proći u buffer i to je točno.
Problem je ipak to.
Dopustite mi ići naprijed i pokrenuti ovaj Program nakon što ga sastavljanju.
Napravite scanf 1.
Kvragu, moj prevodilac je uhvatiti moju pogrešku.
Daj mi jednu sekundu.
Jeka.
Recimo scanf-1.c.
U REDU.
Idemo tamo.
Ja ga treba.
CS50 ID ima razne postavke konfiguracije
koja vas štiti od sebe.
Morao sam onemogućiti one strane trčanje zveket ručno ovaj put.
Dakle niz molim.
Ja ću ići naprijed i upišite u mom omiljenom Hello World.
OK, null.
To nije ono što sam upisali.
Dakle, to je indikativno nešto što nije u redu.
Dopustite mi ići naprijed i upišite u jako dugom nizu.
Hvala na null, a ja ne znam ako ću biti u mogućnosti da ga srušiti.
Pokušajmo malo kopiju paste i vidjeti ako to pomaže.
Samo zalijepite mnogo toga.
To je svakako veći string nego obično.
Ajmo stvarno napisati.
Ne.
Prokletstvo.
Naredi nije pronađen.
Dakle, to je nevezano.
To je zato što sam zalijepiti neke loše likove,
ali to ispada ne ide na posao.
>> Pokušajmo to još jednom, jer to je zabavnije, ako smo zapravo srušiti ga.
Idemo ovaj tip, a sada sam će kopirati jako dugi niz
a sad ćemo vidjeti ako mi mogu srušiti ovu stvar.
Obavijest izostavljen sam prostore i nove linije i zarezom
i sve funky znakova.
Unesite.
A sada je mreža je samo biti spor.
Držao sam dolje Command-V predugo, jasno.
Prokletstvo!
Naredi nije pronađen.
>> U REDU.
Pa, poanta je ipak sljedeće.
Dakle, ono što se zapravo događa o ovoj izjavi
Čar tampon zvjezdica na liniji 16?
Dakle, ono što sam ja sve kad sam proglasiti pokazivač?
Sve sam uzimajući je četiri bajta vrijednost zove tampon, ali ono što je unutar nje
Trenutno?
To je samo neki smeća vrijednost.
Jer bilo kojem trenutku deklarirati varijablu u C, to je samo neki smeća vrijednost,
a mi smo počeli zapeti ove stvarnosti.
Sada, kada sam rekao scanf, idite na ovu adresu
i staviti bez obzira na vrstu korisnika u.
Ako korisnik upiše u pozdravi svijet, dobro, gdje sam ga stavio?
Buffer je vrijednost smeća.
>> Dakle, to je vrsta poput strijele što se pokazuje tko zna gdje.
Možda to ukazuje upravo ovdje u mom sjećanju.
I tako kada korisnik vrste u svijetu, zdravo
program pokušava staviti string Hello World backslash 0
u tom komad memorije.
No, s velikom vjerojatnošću, ali očito nije 100% vjerojatnosti,
računalo će tada srušiti program, jer to nije
memorija mi treba dopustiti da dodir.
Dakle ukratko, ovaj program je manjkav za točno tog razloga.
Ja sam u osnovi ne radi ono?
Koje korake izostavili sam, baš kao i smo izostavili s Binky je prvi primjer?
Da?
>> PUBLIKA: dodjela memorije?
>> DAVID Malan: dodjela memorije.
Nisam zapravo dodijeljeno bilo memorija za taj niz.
Tako možemo popraviti u nekoliko načina.
Jedan, možemo ga zadržati jednostavan i zapravo, sada si
će početi da biste vidjeli zamućenje linija između onoga što
niz je, što je string, što char zvijezda je, što se niz znakova
je.
Evo Drugi primjer uključuje žice i obavijesti
Sve što sam učinio na liniji 16 je, umjesto da kaže
da tampon će biti char zvijezda, pointer na komad memorije,
Idem vrlo proaktivno dati ja tampon 16 znakova,
i zapravo, ako ste upoznati s pojmom međuspremnika,
Vjerojatno iz svijeta video, gdje je video je pufersko, puferski,
puferski.
Pa, što je veza ovdje?
Pa, Unutar YouTube i unutar video player
općenito je niz koji je veći od 16.
To bi moglo biti niz veličine jedne megabajt, možda 10 megabajta,
i na taj niz ne preglednik preuzeti hrpu bajtova,
cijela hrpa megabajta video i video player,
YouTube je ili tko je, počinje čitajući bajtova iz tog niza,
i svaki put kad vidi Riječ puferski, puferski,
to znači da igrač mora dobivši na kraju tog polja.
Mreža je tako sporo da je ne puniti u polje s više bajtova
pa ti si iz bitova prikazati korisniku.
>> Dakle tampon je sposoban pojam ovdje da to je samo niz, komad memorije.
A to će se popraviti jer ispada
koje možete liječiti polja kao da je oni su adrese, iako tampon
je samo simbol, to je slijed znakova, pufer,
to je korisno za mene, programer, možete proći svoje ime oko
kao da je to bila pokazivač, kao da je to
bili adresu komad memorije za 16 znakova.
Dakle, to je za reći, ja mogu proći scanf upravo ta riječ
pa sad, ako sam napraviti ovaj program, bi scanf 2, točka Slash scanf 2,
i upisati Hello World, Unesite, da time--
>> Hmm, što se dogodilo?
Gudački molim.
Što sam učinio krivo?
Pozdrav svijetu, tampon.
Bok svijete.
Ah, ja znam što radi.
U REDU.
Dakle, to je čitanje gore do prvog mjesta.
Tako ćemo varaju samo na trenutak i Samo sam htio reći da upišete nešto
stvarno dugo kao što je to duga kazna To je jedan, dva, tri, četiri, pet,
šest, sedam, osam, devet, 10, 11, 12, 13, 14, 15, 16.
U REDU.
To je doista duga rečenica.
Dakle, ova rečenica je dulje od 16 znakova
pa kad sam pritisnite Enter, što će se dogoditi?
Pa, u ovom slučaju od Priča, sam proglasio tampon
zapravo se niz sa 16 znakova spremni otići.
Dakle, jedan, dva, tri, četiri, pet, šest, sedam, osam, devet, 10, 11, 12, 13, 14,
15, 16.
Tako 16 znakova, a sada, kada sam pročitati u nešto kao što je to dug
rečenica, što će se dogoditi je da ću čitati ovo je dugo
S-E-N-T-E-C-N-E, rečenica.
>> Dakle, ovo je namjerno loša stvar koju sam
držati pisanja s onu stranu Granice moje polje,
izvan granica moje pufera.
Sam mogao dobiti sretan i program će se zadržati na trčanje, a ne briga,
ali općenito govoreći, to će doista srušiti moj program,
i to je bug u mom kodirajte trenutak sam korak
izvan granica tog polja, jer sam
Ne znam je li to nužno će se srušiti
ili ako ja samo ću dobiti sretan.
Dakle, to je problematično, jer u ovaj slučaj, čini se da rade
i neka je iskušati sudbinu ovdje, iako IDE čini tolerirati vrlo malo
of--
>> Idemo tamo.
Konačno.
Dakle, ja sam jedini koji može vidjeti.
Dakle, samo sam imala puno zabave tipkanja iz jako dugo stvarne frazu
da je sigurno veći 16 bajtova, jer sam
upisali u ovom ludom dugo višelinijski izraz, a zatim primijetite što se dogodilo.
Program je pokušao tiskanje a onda je dobio grešku segmentiranja
i segmentacija greške kada nešto slično se to dogodi
a operativni sustav, kaže ne, ne može dirati tu memoriju.
Idemo ubiti program uopce.
>> Dakle, to se čini problematično.
Ja sam poboljšao program kojim barem imaju neke memorije,
ali to bi čini se ograničiti funkcija GetString za dobivanje
nizovi nekog konačnih duljine 16.
Dakle, ako želite podržati više rečenice od 16 znakova,
što radiš?
Pa, možete povećati Veličina ove tampon do 32
ili se to čini nekako kratko.
Zašto ne možemo jednostavno napraviti je 1000, ali gurati natrag.
Što je odgovor intuitivno od Upravo izbjegavanje ovaj problem tako što
moj tampon veći, kao što je 1000 znakova?
Uvođenjem GetString na ovaj način.
Što je dobro ili loše ovdje?
Da?
PUBLIKA: Ako vežu se puno prostora i ne ga koristiti,
onda ne možete preraspodijeliti taj prostor.
DAVID Malan: Apsolutno.
To je razoran ukoliko ako ne zapravo treba 900 onih bajtova
a ti tražiš 1.000 ukupno svejedno,
ti si jednostavno konzumiranje više memorije na korisnikovo računalo nego što je potrebno,
i nakon svega, neke od već ste naišli
u životu kad ste radi puno programa
i oni jede puno memorije, to zapravo može utjecati na performanse
i korisnički doživljaj na kompjuteru.
Dakle, to je vrsta lijen rješenje, sigurno, i obratno,
to ne samo rastrošna, ono što je problem i dalje, čak i ako sam izraditi moj tampon
1.000?
Da?
>> PUBLIKA: Niz je duljina 1.001.
DAVID Malan: Točno.
Ako vaš string duljine 1.001, imate isti problem,
i moj argument, ja bih Samo onda bi 2000,
ali ne znate u unaprijed koliko velika treba biti,
a ipak, ja moram sastaviti moj program prije nego ostavljajući ljudi koriste i preuzimanje
to.
Dakle, to je točno vrsta stvari koje su CS50 knjižnica pokušava
da nam pomogne, a mi ćemo samo ukratko na neke od provedbe temeljne
Ovdje, ali ovo je točka CS50 C. Ovaj je datoteka koja je bila na CS50 IDE
Svi ovi tjedni koji ste koristili.
To je unaprijed sastavljen i da ste bio koristeći automatski
po prirodi koji ima crtica L CS50 zastavu s zveket,
ali ako sam se pomaknite prema dolje kroz sve ove funkcije, evo GetString,
i samo da vam dati djelić onoga što se događa,
neka je uzme brzi pogled na relativna složenost.
To nije super dugo funkcija, ali nismo
moramo razmišljati sve teško o kako ići oko dobivanja žice.
>> Dakle ovdje je moj tampon i ja očito ga inicijalizirati na nulu.
To, naravno, je Ista stvar kao char zvijezda,
ali sam odlučio u provedbu CS50 knjižnici
da, ako ćemo biti potpuno dinamičan,
Ne znam unaprijed koliko je velika string korisnici htjeti doći.
Zato ću početi sa samo prazan string
a ja ću izgraditi koliko memorije kako moram stati korisnički string
a ako nemam dosta, idem pitati
operativni sustav za više memorije.
Idem da se presele svoje string u veći komad memorije
i ja ću objaviti ili besplatno nedovoljno veliki komad memorije
i samo ćemo to učiniti iterativno.
>> Tako brz pogled, Ovdje je samo varijabla
s kojima ću pratiti kapaciteta moje tampon.
Koliko bajtova mogu stati?
Evo varijabla n s koje ću zadržati
Staza koliko bajtova su zapravo u tampon ili da je korisnik upisali.
Ako nisam vidio ovo prije, vas može odrediti da varijabla poput int
je nepotpisan, koji kao što ime sugerira, znači da je ne-negativni, i zašto bi
Sam ikada htio gnjaviti navodeći da int nije samo int,
ali to je tipa unsigned int?
To je ne-negativni int.
Što [nečujan] znači?
>> PUBLIKA: To opisuje iznos memorije koja može biti [nečujan].
>> DAVID Malan: Da.
Dakle, ako ja kažem ružan, to je zapravo dajući vam jedan malo extra memorije
a čini vrsta glup, ali ako vas imaju jedan malo dodatne memorije, da
znači da imate dvostruko više Vrijednosti možete zastupaju,
jer može biti 0 ili 1.
Pa po defaultu, int može biti grubo negativna 2 milijarde skroz
do pozitivnog 2 milijarde.
Oni su veliki rasponi, ali to je još uvijek vrsta rasipan
ako je samo stalo veličina, koji je upravo intuitivno
treba biti pozitivan ili pozitivan ili 0, i onda,
zašto trošiš 2 milijarde Vrijednosti za negativne brojeve
ako nikada ćeš ih koristiti?
Tako rekavši nepotpisan, sada moj int mogu biti između 0 i oko 4 milijarde.
>> Dakle, ovdje je samo int C razloga nećemo ući samo sada kao
zašto je to int umjesto od char, ali ovdje je
suština onoga što se događa na, a neki od vas
može se koristiti, na primjer, fgetc funkcija čak četiri PSet
ili nakon toga, mi ćemo ga vidjeti opet u problemu postaviti pet,
fgetc je lijepo, jer kao ime vrsta, vrsta arcanely sugerira,
je funkcija koja dobiva karakter i tako,
ono što je bitno drugačija o tome što radimo u GetString
je što ne koristite scanf na isti način.
Mi samo puzanje po korak-po-korak više god je korisnik upisali u,
jer uvijek možemo izdvojiti jedan char, i tako možemo uvijek sigurno
pogledajte jedan char na vrijeme, i čarolija počinje događati ovdje.
Idem pomaknite se dolje do usred ove funkcije
samo ukratko predstaviti ovu funkciju.
Slično kao i tu je malloc funkcija, postoji
realloc funkcija gdje realloc omogućuje preraspodijeliti komad memorije
a čine ga veći ili manji.
Dakle duljimo i val ruci za danas,
znam da je ono što GetString radi je to vrsta
od magično raste ili smanjivanjem pufer kao korisnik
vrste u svom nizu.
>> Dakle, ako korisnik upiše Ukratko niz, ovaj kod
Samo izdvaja dovoljno memorije da stane string.
Ako korisnik drži tipkati kao što sam to učinio ponovno i ponovno
i opet, dobro, ako je tampon je u početku ovaj veliki
a program realizira, da se Čekaj malo, ja sam iz prostora,
to će se udvostručiti veličina pufera
a zatim dvaput veličinu pufera i kod koji radi udvostručenje,
ako ćemo gledati na to ovdje, to je samo ovaj pametan jedan brod.
Vi ne bi vidjeli ovu sintaksu prije, ali ako ti kažeš zvijezda jednak,
to je ista stvar kao rekavši puta kapaciteta 2.
Tako da samo čuva udvostručenje kapacitet pufera
a onda reći realloc dati Sama da je mnogo više memorije.
>> Sada, kao stranu, postoji i druge funkcije u ovdje
da nećemo gledati u bilo detalje osim pokazati u GetInt,
koristimo GetString u GetInt.
Mi smo provjeriti da to nije null, koja je, podsjetimo,
je posebna vrijednost koja znači nešto pošlo po zlu.
Mi smo iz memorije.
Bolje provjerite to.
I vraćamo čuvara vrijednosti.
Ali ja ću odgoditi na komentare kao da zašto i onda koristiti ovaj rođak scanf
zove sscanf i ispada da sscanf ili niz scanf,
omogućuje pogledati na liniji koja je korisnik upisali u i neka vas
analizirati ga u biti i što sam radiš ovdje govorim sscanf,
analizirati ono što korisnik ima upisali i pobrinite% ja,
postoji cijeli broj u njoj, i nećemo dobiti u danas točno zašto tu je i
A% c ovdje, ali da je u Ukratko omogućuje nam otkriti ako je korisnik upisali
nešto lažnom nakon broja.
Dakle razlog da GetInt i GetString kažem vam da ponovno pokušamo, ponovite, ponovno pokušati
je zbog sve da kod nas napisano,
To je vrsta gleda na korisnikov unos u tome da je u potpunosti numerička
ili je to stvarna Plutajući Točka vrijednost ili slično,
Ovisno o tome što vrijednost funkcionirati koju koristite.
>> Uh.
U REDU.
To je bila mala količina ali poanta je da se ovdje
da je razlog što smo imali ti trening kotača na
je zato na najnižoj razini, Postoji samo toliko stvari koje
možete pogriješiti da smo htjeli da preventivno obraditi
te stvari sigurno u Najraniji tjedana klase,
ali sada s PSet četiri i pet i PSet izvan vidjet ćete da je to više k
ti već da si sposobnija rješavanja tih vrsta problema
sami.
Bilo kakva pitanja o GetString ili GetInt?
Da?
>> PUBLIKA: Zašto bi udvostručiti kapacitet pufera
a ne samo povećanje to je točan iznos?
>> DAVID Malan: Dobro pitanje.
Zašto bismo udvostručiti kapacitet pufera nasuprot
samo ga porastu neki konstantnu vrijednost?
Bilo je dizajn odluka.
Upravo smo se odlučili jer je sklon biti malo skupo vrijeme pametno pitati
operativni sustav za pamćenje, nismo
želite završiti uzimajući u situacija za velike žice
koje smo pitali i opet OS
i opet i opet u redom za pamćenje.
Tako smo samo odlučili, nešto proizvoljno, ali nadamo se razumno,
da, znate što, neka je pokušati dobiti ispred sebe
i samo bi ga udvostručenje da smo smanjili količinu vremena
moramo zvati malloc ili realloc, ali ukupno presuda
poziv u nedostatku poznavanja što korisnici možda želite upisati.
Oba načina bi mogao biti sporan.
Uvjerljivo dobro.
>> Tako ćemo pogledati par drugih nuspojava pamćenja,
stvari koje mogu poći po zlu i alata koje možete
koristiti za ulov ove vrste pogreške.
Ispada sve vas, iako check50 nije ti rekao koliko,
su pisanje lud broj jer tjedan jednu,
čak i ako su svi check50 testovi prošlo, pa čak i ako vi i vaš TF
su super sigurni da Vaš broj radi onako kako bi trebalo.
Vaš broj je lud ili pogrešno, da svi vi,
u korištenju CS50 knjižnici, su curenje memorije.
Vi ste bili pitate operativnog sustava za memoriju u većini programa
si napisao, ali ste Nikad zapravo vraćen.
Vi ste pozvani GetString i GetInt i GetFloat,
ali s GetString, vi ste Nikad se zove unGetString ili dati
Gudački Natrag ili slično, ali smo vidjeli da GetString se alocirati memoriju
putem malloc ili ovo Funkcija realloc, što je samo
vrlo slični u duhu, a opet, mi smo bili
traži operativni sustav za memorije i pamćenja opet i opet
ali nikada to davanje natrag.
>> Sada, kao stranu, ispada da kada program zatvara, sve memorije
automatski oslobođen.
Dakle, to nije bio veliki posao.
To neće razbiti IDE ili usporiti stvari,
ali kad programe učiniti uglavnom curenje memorije
i oni trčanje za dugo vremena.
Ako ste ikada vidjeli glupa mala lopta za plažu u Mac OS ili pješčanog sata
na Windowsima gdje je vrsta usporavanje ili misli ili misli
ili samo stvarno počinje usporiti na puzati,
to vrlo vjerojatno mogao biti rezultat memorijske curenja.
Programeri koji su napisali softver koji koristite
pitajte operacijski sustav memorije svakih nekoliko minuta, svaki sat.
Ali, ako ste trčanje softver, čak i ako je
minimiziran na vašem računalu za nekoliko sati ili dana na kraju,
možda se traži sve više i više memorije i nikad ga zapravo koristi
i tako je vaš broj može biti ili programi mogu se curenje memorije,
a ako počnu curiti memorije, ima manje memorije za druge programe,
a učinak je usporiti sve dolje.
>> Sada, ovo je daleko jedan od su najokrutniji programi
imat ćete prilike pokrenuti u CS50 mjeri
kao svoj izlaz je još ezoterička od zveket a ili napraviti-a ili bilo koje naredbe
crta programe smo pokrenuti prije nego srećom, ugrađen u svoj izlaz
je neki super korisnih savjeta koji će biti koristan ni za PSet četiri
ili svakako PSet pet.
Dakle Valgrind je alat koja se može koristiti da izgleda
curenja memorije na vašem programu.
To je relativno jednostavan za pokretanje.
Možete pokrenuti Valgrind i onda, čak i iako je malo preopširan,
crtica crtica provjera propuštanja jednako pun, a zatim dot
slash i ime vašeg programa.
Tako Valgrind onda će pokrenuti vaš program a na samom kraju svog programa
pokrenut prije nego što je podnio ostavku i daje vam još jedan redak,
to će analizirati svoje Program dok je bio pokrenut
i reći da si curiti bilo memorije i još bolje,
Jeste li dirajte uspomenu da ne pripada vama?
To se ne može uhvatiti sve, ali to je prilično dobar u lov većinu stvari.
>> Dakle ovdje je primjer moje ima vožnji Ovaj program, koji ima run Valgrind,
na program pod nazivom memorije, a ja ću
označite linije koje su u konačnici od interesa za nas.
Dakle, tu je još više distractions da sam izbrisan iz slajda.
Ali neka je samo vidjeti što je to Program je sposoban nam reći.
To je u stanju reći nam stvari kao nevažeće pisati veličine 4.
Drugim riječima, ako touch memorije, konkretno 4 bajta memorije
da ne bi trebali imati, Valgrind mogu vam reći da.
Pogrešna pisati veličine 4.
Dotakla si četiri bajta da ne bi trebali imati.
Gdje si to učinio?
To je ljepota.
Memorija točka c linija 21, gdje vas zajebao i to je razlog zašto je to korisno.
Slično kao GDB, to može pomoći te ukazati na stvarne pogreške.
>> Sad, ovo je malo više preopširan, ako ne i konfuzno.
40 bajtova u 1 blokovi su svakako izgubljena u gubitak rekord 1 od 1.
Što to znači?
Pa, to samo znači da ste zatražili 40 bajtova i nikad ga vrati.
Zvao si malloc ili naziva GetString i operativni sustav
dao vam 40 bajtova, ali nikad oslobođen ili objavio tu memoriju,
i da se pošteno, mi nikada pokazati vam kako vratiti memoriju.
Ispalo je da postoji super jednostavna funkcija zove besplatno.
Uzeti jedan argument, stvar Želite li osloboditi ili vratiti,
ali 40 bajtova, očito, u ovom programu
su izgubili na liniji 20 memorije točke c.
>> Tako ćemo vidjeti ovaj program.
To je super beskorisno.
To samo pokazuje ovaj greška.
Tako ćemo pogledati.
Ovdje je glavni i glavni, najave, pozive funkcija zove F i zatim se vraća.
Dakle, nije sve što je zanimljivo.
Što f učiniti?
Obavijest Nisam gnjaviti s prototip.
Želio sam zadržati kod što je minimalna što je više moguće.
Pa sam stavio f iznad glavnog i to je u redu, sigurno,
za kratke programe kao što je ovaj.
Dakle f ne vrati ništa i ne ne uzeti ništa, ali to ne učiniti.
To izjavljuje, slično kao u Binky primjer,
pokazivač zove x da će pohraniti adresu int.
Tako da je Lijeva strana.
U engleskom jeziku, što je desna strana radi?
Bilo tko?
Što je to za nas?
Da?
>> PUBLIKA: [nečujan] puta veći od int
što je 10 puta da [nečujan]
DAVID Malan: Dobro i neka mi ukratko.
Dakle izdvojiti dovoljno prostora za 10 brojeva ili 10, što je veličina int,
to je četiri bajtova, pa 10 puta 4 je 40, tako da desna strana koje sam
Istaknuta je daj mi 40 bajtova i pohraniti adresu prvog bajta
u x.
I sada na kraju, a evo i gdje ovaj program je lud, ono što je
u redu sa linije 21 na temelju toj logici?
Što nije u redu s linije 21?
Da?
PUBLIKA: Ne možete Indeks na x [nečujan].
DAVID Malan: Da.
Nisam trebao indeks u X kao što je to.
Dakle sintaktički, to je u redu.
Što je lijepo je, baš kao i ti može liječiti ime niza
kao da je pokazivač, na sličan način možete liječiti pokazivač kao da je
niz, pa ja mogu sintaktički kažu x noseći nešto, x nosač ja,
ali 10 je problematično.
Zašto?
>> PUBLIKA: Budući da nije unutra.
>> DAVID Malan: Nije unutar tog komad memorije.
Što je najveća vrijednost trebam se stavljanjem u tim uglatim zagradama?
9, 0 do 9.
Zbog nula indeksiranja.
Tako 0 do 9 bi bilo u redu.
Nosač 10 nije dobro i ali, sjećam ipak, svaki put
Čini mi se da pokušati napraviti CS50 IDE sudar upišete u lažnim vrijednostima,
to ne uvijek surađuju, i doista, često
dobiti sretan samo zato što je Operativni sustav ne
primijetiti da ste ikada tako nešto proći neke komad memorije,
zato što je ostao u tehnički Vaša segmentu, no više o tome
u operacijskim sustavima klase, i tako nešto kao što je ovaj
bi vrlo lako mogao otići neprimijećen.
Vaš program nikad neće srušiti dosljedno ali možda jednom u neko vrijeme.
>> I tako pokušajmo Valgrind o tome, i ovdje je
gdje ćemo dobiti osvaja od izlaza na trenutak.
Tako bi memorije ček Valgrind curenja jednako punu točkica kose crte memorije.
A evo i zašto obećajem to bi pobijediti.
Evo što Valgrind, evo što programer, nekoliko godina ago-
odlučio da će to biti dobra ideja za izlaz izgledati.
Tako ćemo shvatiti ovo.
Dakle, sve na lijevom strana bez dobrog razloga
je proces ID programa mi samo trčanje, jedinstveni identifikator
za program mi samo trčao.
Izbrisali smo da je od slajd, ali postoji
neke korisne informacije ovdje.
>> Idemo dođite do samog vrha.
Evo gdje smo počeli.
Dakle, to nije sve što je mnogo izlaz.
Evo kako nevažeća pisati veličine 4 na liniji 21.
Pa, što je redak 21?
Linija 21 je upravo ovo i ima smisla
da sam u valjano pisanje 4 bajta, jer sam
pokušavam staviti ovaj cijeli broj, koji bi mogao biti bilo što,
to samo događa da se nula, ali ja pokušavam
staviti ga na mjestu koji ne pripada meni.
Štoviše, ovdje dolje, 40 bajtova u jedan blokovi su definitivno izgubili u rekordnom 1.
To je zato što kad ja zovem malloc Ovdje, nikada nisam zapravo osloboditi memoriju.
>> Pa kako možemo popraviti ovo?
Dopustite mi ići naprijed i biti malo sigurniji i to 9 tamo i neka me ovdje besplatno x.
Ovo je nova funkcija za danas.
Ako ja sada ponoviti napraviti memorije dot crta, neka je trčanje Valgrind na to opet,
povećala sam prozor i pritisnite Enter.
Sada, to je dobro.
Oni pokopam dobre vijesti u svim ovim izlaz.
Svi hrpu blokova bili slobodni.
Mi ćemo se vratiti na ono što je gomila je, ali nema curenja su moguće.
Dakle, ovo je samo još jedan alat za vaš alat kit
s kojima možete početi nalaze se sada pogreške kao što je to.
>> Ali da vidimo što Više možete pogriješiti ovdje.
Idemo prijelaz sada zapravo rješavanje problema.
Kao na stranu, ako je to će osloboditi malo konfuzije ili napetosti,
ovo je sada smiješno.
Da.
To je vrlo dobro.
Zbog pokazivače su adrese i adrese
uglavnom po konvenciji napisan s heksadecimalnom.
Ha, ha, to je smiješno sada.
U svakom slučaju, pa neka je sada zapravo riješiti problem.
To je super, super niske razine do sada,
i mi zapravo može učiniti korisnim stvari s tim detaljima niske razine.
>> Tako smo uveli nekoliko tjedana Prije pojam niza.
Niz je lijepo, jer to je teško očistiti našu šifru
jer ako smo htjeli napisati Program s više studenata
ili više imena i kuće i dorms i visokih škola i sve to,
možemo pohraniti sve više čisto unutar niza.
No, predlaže jedan minus od niza do sada.
Čak i ako ne sam to trpio sebe u programu, samo instinktivno,
ono što je loše o nizu, možda?
Čujem neke murmurs.
PUBLIKA: Teško je za promjenu veličine.
DAVID Malan: Teško je za promjenu veličine.
Ne možete promijeniti veličinu od niza, u stvari, kao takvi
u C. Možete izdvojiti još jedan niz, premjestiti sve od stare
u novi, a sada imaju neki dodatni prostor,
ali to ne sviđa jezik poput Java ili Python
ili bilo kojom drugom jezika s kojih su neki od vas
možda upoznati gdje vas mogu samo držati dodajući stvari
gadosti na kraj niza.
Kada imate niz Veličina 6, da je njegova veličina,
i tako mnogo kao ideja ranije ima pufera određene veličine,
morate pogoditi od vrata što veličini želiš da bude?
Ako pogodite prevelika, ste gubit prostor.
Ako pogodite premala, te Ne mogu pohraniti te podatke, barem
bez puno rada.
>> Tako je danas, zahvaljujući pokazivača, možemo započeti povezivanjem vlastite običaj
strukture podataka, te po Činjenica, ovdje je nešto
da izgleda malo više grobni na prvi pogled,
ali to je ono što ćemo nazvati povezan Lista, a ime vrste rezimira
to.
To je popis brojeva, ili ovaj slučaj, popis brojeva,
ali to bi mogao biti popis svega, ali to je međusobno povezane preko strelice,
i samo uzeti pogodak s tim što je tehnika
ćemo biti u mogućnosti bodom zajedno,
vrsta kao kokica s navojem, je povezani popisi pravokutnici ovdje?
Njegovi brojevi?
Što je jezik lik podlozi?
>> PUBLIKA: Pokazivač.
>> DAVID Malan: Pokazivač.
Dakle, svaki od tih strelice ovdje predstavlja pokazivač ili samo adresa.
Dakle, drugim riječima, ako želim pohraniti popis brojeva,
Ne mogu ga samo spremiti ako želim sposobnost da raste i smanjiti
moja struktura podataka u polja.
Dakle, moram imati malo više sofisticiranost,
ali primijetiti da je ovaj Slika vrsta sugerira
da, ako ste upravo je dobio malo teme povezivanje sve zajedno,
vjerojatno nije da je teško napraviti prostor između dva od tih pravokutnika
ili dva od tih čvorova, kao što ćemo početi nazivajući ih, stavite u novi čvor,
a onda s nekim novim konac, samo jarku tri čvorova zajedno,
prvi, zadnji i onaj da se samo umetne u sredini.
>> I doista popis povezani, za razliku od niza, je dinamičan.
To može rasti i to može smanjiti, a vi ne
znati ili briga unaprijed koliko mnogo podataka da ćeš biti pohranjivanje,
ali ispada da moramo biti malo Pazite kako implementirati ovaj.
Prvo ćemo razmotriti kako ćemo provesti jednoga od ovih najmanjih pravokutnika.
To je jednostavan za implementaciju int.
Vi samo reći int n, a zatim dobivate 4 bajta za int,
ali kako mogu dobiti int, zovu ga n, a zatim pokazivač, nazovimo ga sljedeći.
Mogli bismo nazvati njih stvari sve što želimo
ali moram struktura prilagođenih podataka.
Da?
>> PUBLIKA: Ampersand [nečujan].
>> DAVID Malan: Tako znak za struju ćemo koristiti za dobili adresu čvora potencijalno.
No, moramo još značajka C kako
da mi daju mogućnost stvaranja Ovaj običaj pravokutnik, ovaj običaj
varijabla ako hoćete, u memoriju.
PUBLIKA: a struct.
DAVID Malan: a struct.
Sjetite se od prošlog tjedna, uveli smo struct, ovaj relativno jednostavan ključne riječi
koji omogućuje nam da stvari kao što je ovaj.
C nije došao s podacima Struktura zove student.
Ona dolazi s int i float i char i takav, ali to ne dolazi s studenta,
ali možemo stvoriti tip studenta podataka, student struktura, s ovim sintaksa
ovdje.
I vidjet ćete to opet i opet.
Zato ne brini memoriranje riječi,
ali ključna riječ koja je važna samo činjenica da smo rekli struct
a onda smo ga zove student i unutar studenta je ime i kuća
ili domu ili slično.
>> I tako sad i danas, neka predloži ovo.
Ja sam dodao nekoliko riječi, ali ako želim implementirati ovaj pravokutnik koji je
dobio oba int i A pokazivač, znate što, ja sam
će proglasiti struct zove čvor.
Ja sam također, unutar njega, reći da čvor, ovaj pravokutnik, ima int
a mi ćemo ga zvati n i ima sljedeći pokazivač.
A to je malo preopširan, ali ako mislite o tome,
strelice koje su na slici trenutak prije su na vrstu podataka?
Gdje je svaki od tih strelica ukazuje na kakvu vrstu strukture podataka?
Nije upućuju samo na int po sebi.
To ukazuje na Cijela stvar pravokutni
i da pravokutnog stvar, rekli smo, zove se čvor.
I tako smo vrsta moramo rekurzivno definira ovo kao
da čvor, ćemo reći, će sadržavati int zove n
a pokazivač zove pored te vrsta strukture podataka na koje
da pokazivač bodova je očito će biti struct čvor.
>> Dakle, ovo je dosadno preopširan i samo da se pedantan,
razlog zašto ne možemo samo reći ovo, što iskreno
izgleda puno više čitati, je zato Podsjetimo da je C pročitati
stvari od vrha do dna, s lijeva na desno.
To nije sve dok ne dobijete zarezom da je ključna riječ čvor zapravo postoji.
Dakle, ako želimo imati ovu vrstu ciklična referenca unutar podataka
Struktura, moramo to učiniti, gdje kažemo struct čvor na vrhu, što
daje nam duži način opisivanja ove stvar, a onda iznutra kažemo struct čvor,
a onda u zadnji redak kažemo, u redu, C, usput,
samo nazvati cijelu ovu osuditi stvar čvor i zaustaviti
pomoću ključnih riječi struct uopce.
Dakle, ovo je samo neka vrsta sintaktička Trik koji u konačnici omogućuje nam stvaranje
nešto što izgleda upravo ovako.
>> Dakle, ako pretpostavimo sada možemo provesti ovo u C,
kako radimo zapravo početi poprijeko ovo?
Pa, zapravo, sve što morate učiniti je ponoviti s lijeva na desno i samo
vrsta umetanje čvora ili brisanje čvorova ili tražiti stvari gdje god želimo,
ali za to, idemo naprijed i učiniti stvari malo realnije, jer je ova
je super niske razine do sada.
Bi li netko doslovno htjeli biti prvi?
U REDU.
Dođi gore.
Kako se zoveš?
>> DAVID: David.
DAVID Malan David.
Drago mi je.
Ja isto.
U redu.
I trebamo broj 9.
Nije dobar kao prvi, možda.
OK, broj 9.
Broj 17, molim vas.
Pusti me da se vratim malo dalje.
Broj 22, molim te o tome kako dalje natrag
ako ja mogu vidjeti bilo ruke sa svim svjetlo ili ne.
Netko se dobrovoljno javio upravo tamo.
Želite li doći gore?
Vaš podlaktice prisilno ide gore.
OK, 17.
22.
26 silazi.
Bi li itko drugi želio forcefully-- Dođi gore.
Stvarna volonter.
>> Tako vrlo brzo, ako se vi mogli dogovoriti
sami baš kao čvorovi na zaslonu.
Hvala.
I vi ćete biti 26.
Svi pravi i brzo upoznavanje.
Dakle, ja sam David i vi ste također?
DAVID: David.
DAVID Malan: A vi ste?
Jake: Jake.
SUE: Sue.
ALEX: Alex.
RAPHAEL: Raphael.
TAYLOR: Taylor.
DAVID Malan: Taylor.
Izvrsno.
Dakle, to su naši volonteri za danas i ići naprijed
i guraju malo na taj način, i samo ići naprijed i držati
drži svoje brojeve kao što su ili vaš Prvi znak i lijevom rukom,
ići naprijed i samo provesti ove strelice, samo
tako da tvoja lijeva ruka doslovno pokazujući na sve što treba istaknuti
na, i dati vam malo mjesta, tako da vizualno može vidjeti vaše ruke zapravo
bodovnom, a vi samo možete istaknuti vrsta na terenu je u redu.
>> Dakle, ovdje imamo povezani popis jednog, dva, tri, četiri, pet čvorova početku,
i primjetiti imamo ovaj posebni pokazivač na početku tko je
Ključ jer moramo pratiti cijelog popisa duljine nekako.
Ovi momci, iako su oni ostavili na desno, natrag na leđa u memoriji,
oni zapravo može biti bilo gdje u memoriju računala.
Dakle, ti dečki mogu biti stoji nigdje na pozornici
i to je u redu, tako dugo dok su oni zapravo pokazujući jedan drugome,
ali da bi stvari čist i jednostavan, mi ćemo
samo ih privući lijeva na desno kao što je to, ali moglo bi biti masivna praznine
između tih čvorova.
>> Sada, ako želim da zapravo umetnuti neke nova vrijednost, idemo naprijed i učiniti.
Imamo priliku sada odabrati neki drugi čvor.
Recimo Počnimo s mallocing 55.
Bi li netko smeta što malloc?
U redu, hajde gore.
Kako se zoveš?
RAINBOW: Rainbow.
DAVID Malan: Rainbow?
U redu.
Malloc Rainbow.
Dođi gore.
Zato sada moramo zapitati algoritamski gdje možemo staviti 55.
Dakle, svi mi znamo, Očito, gdje je vjerojatno
pripada ako nastojimo zadržati ovu razvrstani
a ako vi mogli uzeti jedan korak natrag, tako da ne padne
na pozornici, to bi bilo sjajno.
Pa zapravo, Rainbow, početi ovamo sa mnom,
jer mi kao računalo može sada vidjeti samo jednu varijablu u isto vrijeme.
Dakle, ako je to prvi čvor.
Obavijest on nije čvor, on je samo pokazivač,
i to je razlog zašto je on privlači biti samo veličina pokazivač, ne
jedan od onih punih pravokutnika.
Tako ćemo provjeriti kod svakog iteracija je 55 manje od 9?
Ne.
Je li 55 manje od 17?
Ne.
Manje od 22?
Manje od 26?
Manje od 34?
I tako sada, očito Duga spada na kraju.
Dakle, da bude jasno, i što je vaše ime, Taylor?
>> TAYLOR: Taylor.
DAVID Malan: Tako među Taylor je lijeva ruka i Rainbow ruke ovdje,
koga treba ukazati na ono što je u narediti da ubacite 55 u ovaj popis?
Što trebamo učiniti?
Da?
>> PUBLIKA: Taylor ruku treba istaknuti lijevo.
>> DAVID Malan: Točno.
Dakle umetanje čvora u kraju liste
je prilično jednostavan, jer je Taylor samo mora istaknuti, umjesto na terenu
ili ćemo ga nazvati null, null je vrsta odsutnosti
od pokazivača ili posebna nula pokazivač, ti si
ide do točke s lijeve strane ruku na Rainbow i zatim Rainbow,
Gdje bi vaš lijevi Ruka vjerojatno ukazati?
Dolje.
To nije dobro ako joj je ruka je vrsta ukazivanja off ovdje ili nekako bilo
koji put.
To bi se smatrati vrijednost smeća,
ali ako je ona ukazuje na neki poznati vrijednost, mi ćemo
nazovite ga nula ili nula, to je u redu jer imamo termin u to
a znamo popis je potpun.
>> Dakle, ono što je još relativno jednostavan slučaj?
Možemo malloc 5?
Dođi gore.
Kako se zoveš?
TIFFANY: Tiffany.
DAVID Malan: Žao mi?
TIFFANY: Tiffany.
DAVID Malan: Tiffany.
U redu.
Tiffany je malloced s vrijednošću 5.
Dođi gore.
Ovaj je relativno lako previše, ali uzmimo redoslijed operacija sada.
Bilo je prilično lako s Taylor na kraju.
Broj 5 je naravno manji od 9, i tako smo Davida, imamo Tiffany,
i što je vaše ime?
>> Jake: Jake.
>> DAVID Malan: Jake.
Tiffany, Jake, i David.
Čija ruka treba biti obnovljeno prvi?
Što želite raditi ovdje?
Postoji nekoliko mogućih načina, ali tu je i jedna ili više pogrešne načine.
>> PUBLIKA: Počnite s lijevom.
>> DAVID Malan: Počnite s lijevom.
Tko je lijevom onda ovdje?
PUBLIKA: Prvo.
>> DAVID Malan: U redu.
Dakle, početi s prva i gdje vi želite ažurirati Davidove ruke da bude?
PUBLIKA: Prema 5.
DAVID Malan: U redu.
Tako je David, točka na pet ili Tiffany ovdje i sada?
>> PUBLIKA: Tiffany ukazuje na 9?
DAVID Malan: Savršen, osim Binky je glava samo vrsta pao, zar ne?
Zato što nije u redu s ta slika doslovno?
PUBLIKA: Ništa se ne pokazuje.
DAVID Malan: Ništa se pokazujući Jake sada.
Mi smo doslovno smo siročad 9 i 17, a mi smo doslovno
procurila sve ove memorije, jer po ažuriranje Davida ruku prvo, to je
fino utoliko što je ispravno pokazujući na Tiffany sada,
ali ako nitko nema Predviđanja ukazati na Jakea,
onda smo izgubili cjelokupnost tog popisa.
Tako ćemo poništiti.
Dakle, to je dobra stvar za spotakne ali ćemo ispraviti sada.
Ono što trebamo učiniti prvi umjesto toga?
Da?
>> PUBLIKA: Tiffany treba ukazati na 9?
DAVID Malan: Ne mogu dobiti tu blizu tebe.
Tko bi trebao ukazati na 9?
>> PUBLIKA: Tiffany.
>> DAVID Malan: U redu.
Dakle Tiffany trebali prvo mjesto na 9.
Dakle Tiffany treba uzeti na identičnom vrijednost
Davidu, što se čini suvišan na trenutak,
ali to je u redu, jer sada, drugi korak, možemo ažurirati Davida za ruku
ukazati na Tiffany, a onda, ako mi samo vrsta čista stvari
kao da je to neka vrsta proljeće-poput, sada da je točna umetanja.
Tako izvrsno.
Dakle, sada smo skoro tamo.
Idemo umetnite jedan finale vrijednost poput vrijednosti 20.
Ako smo mogli malloc posljednji volonter?
Dođi gore.
Dakle, ovaj je malo lukav.
Ali stvarno, kod smo pisanje, iako verbalno,
je samo kao da hrpa odnosno ako uvjeti sada, zar ne?
Imali smo stanje provjere da li to spada
Na kraju, možda na početku.
Trebamo neku vrstu petlje na naći mjesto u sredini.
Tako ćemo učiniti s onim što je vaše ime?
>> ERIC: Eric.
>> DAVID Malan: Eric?
Eric.
Drago mi je.
Dakle, imamo 20.
Manje od pet?
Ne.
Manje od devet?
Ne.
Manje od 17?
Ne.
U REDU.
On pripada ovdje i vaša imena su opet?
SUE: Sue.
DAVID Malan: Sue.
ALEX: Alex.
DAVID Malan: Sue, Alex, a?
ERIC: Eric.
DAVID Malan: Eric.
Čije ruke je potrebno da biste dobili ažurirani prvi?
>> PUBLIKA: Eric.
U REDU.
Dakle, Eric je trebao ukazati na kojoj?
U 22.
Dobra.
A sada što je sljedeće?
Sue onda može ukazati na Erica a sad, ako dečki jednostavno
napravite malo mjesta, što je u redu vizualno, sada smo učinili umetanje.
Tako ćemo sada razmotriti pitanje, ali hvala vam toliko za naše volontere.
Vrlo dobro učinio.
Možete zadržati one, ako vam se sviđa.
I mi imamo loptu oproštajne dar, ako ti bi svako želio uzeti stres loptu.
Dopustite mi samo proći ovo.
Dakle, ono što je takeaway to?
Čini se da je nevjerojatna utoliko što imamo danas
uvela alternativa za niz koji nije toliko ograničen
na niz neke fiksne veličine.
Oni mogu rasti dinamički.
>> No, baš kao što smo vidjeli u nekoliko tjedana prošlosti, mi nikada ne dobiti ništa besplatno,
kao što sigurno postoji trade-off ovdje.
Dakle, s naopako povezanog Lista je to dinamika?
Ova sposobnost da raste i iskreno, smo mogli učiniti za brisanje
i da bismo mogli smanjiti po potrebi.
Što cijenu plaćamo?
Dvostruko više prostora, prije svega.
Ako pogledate na slici, više nije sam spremanje popis brojeva.
Ja spremanje popis integers plus naputke.
Tako sam udvostručenje količinu prostora.
Sad, možda to nije tako velika stvar 4 bajta, 8 bitova,
ali svakako može dodati za velike skupove podataka.
Što je još jedan minus?
Da?
>> PUBLIKA: Moramo proći ih jednog po jednog.
DAVID Malan: Da.
Moramo ih proći jedan po jedan.
Znaš što mi je dao ovu super zgodan značajka uglata zagrada
zapis, točnije poznat kao slučajni pristup,
gdje mi samo može skočiti za pojedinog elementa
ali sada, ako sam još uvijek imao moji volonteri ovdje,
ako sam htjela pronaći broj 22, ne mogu jednostavno
skok na nosač nešto nešto.
Moram gledati preko popisa, mnogo poput naših potrazi primjera linearno,
naći broj 22.
Zato mi se čini da su platili cijenu tamo.
Ali možemo svejedno riješiti ostale probleme.
>> U stvari, neka mi se predstavimo samo par vizuala.
Dakle, ako ste bili do Mather blagovaonici nedavno,
vi ćete se sjetiti da je njihov hrpe ladice kao što je ovaj,
smo posudili od njih Annenberg prije nastave.
Dakle, ovaj snop ladice, ipak, prikazuje zapravo
od računalnih znanosti strukture podataka.
Tu je struktura podataka u računalnoj znanosti
poznat kao stog koji vrlo lijepo pada u upravo to vizualni.
Dakle, ako svaki od tih ladica nije ladica, ali kao broj i ja sam htjela
za spremanje brojeva, ja mogao staviti ovdje jedan dolje,
i ja mogao staviti još ovdje, i dalje slaganje brojeva
na vrhu jedan drugoga, i što je potencijalno korisno o tome
je da je ono što je implikacija ove strukture podataka?
Koji broj mogu izvaditi Prvi najprikladnije?
Najviše je nedavno jedan staviti tamo.
>> Dakle, to je ono što bismo nazvali u informatika LIFO struktura podataka.
Posljednji u, prvi van.
I vidjet ćemo ubrzo zašto to bi moglo biti korisno, ali za sada,
Samo razmislite imovine.
I to je vrsta glupo ako mislite o tome kako je blagovaonica to radi.
Svaki put kad su čiste posude i staviti najsvježije one na vrhu,
možete imati prethodno čista ali na kraju vrlo prljav i prašnjav
ladicu na samom dnu Ako nikad zapravo
doći do dna da stog, jer ste upravo
zadržati stavljajući novi i Čiste one na vrhu.
Ista stvar se može dogoditi u supermarketu previše.
Ako imate slučaj prikaza mlijeka i svaki put CVS
ili tko dobiva više mlijeka, ti samo gurati mlijeka
već imate na leđima i ste stavili nove up front,
ti si idući u imati neki prilično gadan mlijeka na kraju strukture podataka,
jer je uvijek na dnu ili ekvivalentno je uvijek na leđima.
>> No, postoji još jedan način razmišljanja o podstava gore podatke i na primjer, to.
Ako ste jedan od onih ljudi koji vole da se postroje izvan Apple trgovinama
kada novi proizvod dolazi van, vjerojatno ste
Ne koristite stog podatke Struktura zbog tebe
bi otuđiti svi drugi koji je podstava gore kupiti neku novu igračku.
Umjesto toga, vjerojatno ste koristeći kakva struktura podataka
ili kakav sustav u stvarnom svijetu?
Nadam se da je linija ili više ispravno ili više Britansko-kao, red.
I ispada red je i struktura podataka u računalnoj znanosti,
ali red je vrlo različite imovine.
Nije LIFO.
Posljednji u, prvi van.
Bože sačuvaj.
To je umjesto FIFO.
Prvi u, prvi van.
I to je dobra stvar za pravednost 'radi
sigurno kada ste obloge se super u ranim jutarnjim satima.
Ako doći prvi, vi želite izaći prvi, kao dobro.
>> I tako sve ove podatke strukture, redovi i hrpe
i grozdovima drugih, ispada vas mogu misliti na to kao samo polje.
To je niz, možda fiksna veličina 4, ali to bih
biti vrsta lijepo da smo mogli samo gomilati ladice gotovo beskrajno visok ako mi
ima da mnogi ladice ili brojeve.
Dakle, možda želimo koristite popis povezano ovdje
ali trade-off će biti potencijalno da trebamo više memorije,
Potrebno je malo više vremena, ali smo ne ograničavaju visinu dimnjaka,
slično kao Mather je prikaz slučaja može ograničiti veličinu iz dimnjaka,
pa to su dizajn odluke ili Opcije dostupne za nas u konačnici.
Dakle, s ovim podacima strukture, koje smo započeli
vidim nove gornje granice potencijalno na ono što je prethodno bilo super brzi
i gdje ćemo ostaviti off danas i gdje
mi ćemo se nadam da bi se je u srijedu, mi ćemo
početi gledati na podatke struktura koja omogućuje nam da traži
kroz podatke u log kraj vremena opet.
A vidjeli smo da je, podsjećamo, u tjednu nula i jedan s binarnim pretraživanje ili podijeli
i osvojiti.
Dolazi natrag i još bolje, Sveti Gral za ovu srijedu
bit će da se s struktura podataka koji se izvodi doista
ili teoretski u vremenska konstanta, pri čemu
nije važno koliko je milijuni ili milijarde stvari
imamo u strukture podataka, to će uzeti nam stalnu vremena, možda jedan korak
ili dva koraka ili 10 koraka, ali stalni broj koraka
tražiti kroz tu strukturu podataka.
To će doista biti sveti gral ali više o tome u srijedu.
Vidimo se onda.
>> [Glazbom]