[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]