[Powered by Google Translate] [Tjedan 6] [David J. Malan] [Sveučilište Harvard] [Ovo je CS50.] [CS50.TV] 

Ovo je CS50, a to je početak tjedna 6, tako par novih alata su sada dostupne za vas iskoristiti, od kojih je prvi se zove CS50 stil. Tečajevi su, ako ste poput mene, ili bilo koji od nastavnih bližnjima, Vjerojatno ste vidjeli program čiji stil izgleda malo nešto ovako. Možda ćete početi rezanje neke kutove kasno noću, ili ćete se nositi s njom kasnije, i onda TF ili CA dolazi preko za vrijeme radnog vremena. Tada je teško za nas čitati. Pa, ovaj broj je sintaktički ispravan, a to će sastaviti, a to će zapravo pokrenuti. Ali to definitivno nije 5 za stil. 

Ali sada, ako idemo u ovaj direktorij ovdje- i primjetiti da imam conditions2.c- i ja pokrenuti tu novu naredbu, style50, na ovoj datoteci conditions2.c, Enter primijetiti da me obavijestio da je stilizirana. Gedit primijetio da je datoteka izmijenjena na disku, a ako ja kliknite reload, svi vaši problemi sada su automatizirani. [Pljesak] To je jedna od stvari koje smo učinili ovaj vikend. Shvatite da je nesavršena, jer postoje neki kod da to jednostavno neće moći stilizovati savršeno, ali shvatite ovo je sada alat možete iskoristiti ako je samo pospremiti neke od više errantly stavljen vitičastih zagrada i slično. 

Ali više uvjerljiv sada je CS50 Provjeri. S CS50 provjera, što zapravo može obavljati iste testove ispravnosti na svoj kodu da nastavna momci su u mogućnosti. To je uslužni program naredbenog retka koji dolazi sada u aparatu čim učiniti update50 kao i po pset četiri specifikacije, te ga koristiti u suštini ovako. Možete pokrenuti naredbu check50. Tada ćete proći u argument naredbenog retka, ili više obično poznat kao prekidač ili zastavu. Općenito, stvari koje imaju crtice su pozvani prekidač na programu naredbenog retka, tako-c određuje provjere koje želite pokrenuti. 

Testovi koje želite pokrenuti su identificirani jedinstveno ovog niza, 2012/pset4/resize. Drugim riječima, to je samo proizvoljna, ali jedinstven niz da mi koristiti za jedinstveno identificiranje pset 4 je ispravnosti ispitivanja. I onda odrediti prostor odvojen popis datoteka koje želite prenijeti do CS50 provjera za analizu. Na primjer, ako odem u moje rješenje ovdje za resize.c- neka mi otvoriti veći terminal prozor- i ja ići naprijed i pokrenuti recimo check50-c 2012/pset4/resize, i onda sam ići naprijed i navesti imena datoteka, resize.c, a zatim pritisnite Enter, komprimira, to slike, to provjerava, a ja sam samo propustio hrpu testova. Jedna u crvenom, na gornjem lijevom kaže da resize.c i BMP postoji. To je bio test. To je pitanje. I to je nesretan jer je odgovor bio lažan. Bijeli tekst ispod njega, kaže očekuje bmp.h da postoje, i to je jednostavno moja krivnja. Zaboravio sam ga upload, tako da moram uploadati obje datoteke, resize.c i bmp.h. Ali sada primjetiti sve ostale testove su u žuto, jer oni nisu pokrenuti, i tako smješko je okomita jer je ni sretan ni tužan, ali moramo zadovoljštinu taj problem u crveno prije one druge provjere će se izvoditi. 

Dopustite mi da ovo popraviti. Dopustite mi da smanjivanje i reprizu to, ovaj put s bmp.h također na naredbenog retka, Enter, a sada ako sve ide dobro, to će provjeriti i zatim vratiti rezultat od-zadržite dah- sva zelena, što znači da radim jako dobro na pset 4 do sada. Možete vidjeti i zaključiti iz opisnog teksta ovdje točno ono što je testirali smo. Testirali smo prvi ne datoteke postoje? Mi smo tada testirani radi resize.c sastaviti? Onda smo testirali to nije veličinu 1x1 piksela BMP kada n, veličinu faktor, je jedan. Sada, ako nemate pojma što je n, možete odjednom ćete zaroniti u pset 4, ali to jednostavno razum provjeriti kako bi bili sigurni da niste resize slika na sve ako promjene veličine faktor je 1. Ako, s druge strane, ona mijenja veličinu 1x1 piksel na 1x1 piksela BMP za 2x2 ispravno kada n je 2, tada je na sličan način, mina tvori skladu s tim. 

Ukratko, to je značilo da, jednom, poduzeti prelaze prste iz jednadžbe pravo prije nego što pošaljete svoje pset. Vi ćete znati točno što vaš TF uskoro će se znati kad idete o podnošenju neke od tih problema skupova, i pedagoški motivacija je stvarno staviti prilika ispred vas tako da kada znaš a priori da postoji bugove u kodu i ispitivanja koje se ne prenose, možete staviti u učinkovitijem vremena do pred riješiti te probleme nego izgubiti bodove, dobiti povratnu informaciju od svog TF, i onda ići, "ahh", kao što sam trebao shvatio da van. Sada barem postoji alat će vam pomoći da otkrijete da. To se neće ukazati gdje je bug, ali to će vam reći što je simptomatično to. 

Sada shvatili su testovi nisu nužno iscrpan. Samo zato što ste dobili ekran pun zelenog smješko lica ne znači vaš broj nije savršen, ali to ne znači da je prošao određene testove propisane spec.. Ponekad mi neće objaviti provjere. Na primjer, detektivski roman, jedan od aspekata pset 4, je vrsta razočaravajuće ako vam odgovor kao što je to, a tu je broj načina da se otkrivaju tko je osoba koja je u tom crvenom buke. Spektri uvijek će odrediti u budućnosti za pset 5 nadalje ono što provjerava postoje za vas. Primijetit ćete da je ovaj bijeli URL na dnu. Za sada, ovo je samo dijagnostički izlaz. Ako posjetite taj URL, dobit ćete cijelu hrpu ludih, kriptične poruke da ste dobrodošli gledati kroz, ali to je uglavnom za osoblje tako da možemo dijagnosticirati i ispravljanje bugova u check50 sama. 

Bez teškoća, krenimo na kojoj smo stali. CS50 knjižnica smo uzeli zdravo za gotovo za nekoliko tjedana, ali onda prošlog tjedna, počeli smo piling natrag jedan od slojeva njega. Počeli smo stavljajući na stranu niz u korist onoga što umjesto? [Studenti] Char. Char *, koji je bio char * sve ovo vrijeme, ali sada nemamo se pretvarati da je stvarna vrsta podataka string. Umjesto toga, to je bio sinonim sorti za char *, a niz je niz znakova, pa zašto nema smisla da predstavljaju nizove kao char * s? Što char * predstavljaju u kontekstu ovog koncepta niza? Da. >> [Studentski] Prvi znak. Dobar, prvi znak, ali ne sasvim prvi znak. To su-[Studenti] Adresa. Dobro, adresa prvog karaktera. Sve što je potrebno da predstavljaju niz u memoriju računala je samo jedinstvenu adresu svog prvog bajta. Vi čak ne morate znati koliko dugo to je jer kako možete shvatiti da se dinamički? [Studentski] Gudački dužina. Možete nazvati string duljine, odličan, ali kako se posao duljine niza? Što to učiniti? Da. [Studentski] Nastavite dok ne dobijete null karakter. Da, točno, to samo ponovi s for petlji, while petlja, god od * do kraja, a kraj je zastupljena po \ 0, tzv NUL znak, nul, ne treba brkati s null, koji je pokazivač, koji će se u razgovoru opet danas. 

Mi ljušteno natrag sloj GetInt, a onda mi je uzeo pogledati GetString, i podsjetiti da su od tih funkcija, ili stvarno, GetString, bio koristeći određenu funkciju zapravo analizirati, da se, čitati ili analizirati, korisnikov ulaz. A što je to nova funkcija? Scanf ili sscanf. To je zapravo dolazi u nekoliko različitih okusa. Tu je scanf, tu je sscanf, tu je fscanf. Za sada, međutim, ajmo se usredotočiti na ono najlakše ilustrirati, i pusti me naprijed i otvoriti u aparatu file ovako, scanf1.c. To je super jednostavan program, ali da učini nešto što nikada nismo učinili bez pomoć CS50 knjižnice. To dobiva int od korisnika. Kako se to radi? Pa, u skladu 16 postoji, primijetiti da smo proglasi int nazvan x, au ovom trenutku u priči, što je vrijednost x? [Nečujno učenik odgovor] [David M.] Točno, tko zna, neka vrijednost smeće potencijalno, pa je tako u 17, samo mi recite korisnika daj mi broj, molim vas, i korak 18 je mjesto gdje se dobiva zanimljiv. Scanf čini posuditi ideju s printf u da koristi ove formata kodove u navodnike. % D je naravno decimalni broj. Ali zašto sam ja prolazio & X umjesto samo x? Bivši je ispravan. Da. [Nečujno učenik odgovor] Točno, ako je cilj ovog programa, kao i funkcije GetInt sama, se dobiti int od korisnika mogu proći funkcije sve varijable želim, ali ako ja ih ne prođe upućivanjem ili adresu ili pokazivač, sve sinonim za današnje potrebe, zatim da funkcija nema sposobnost da promijeni sadržaj te varijable. To će proći u kopiji baš kao lud verziji swapa da smo razgovarali o nekoliko puta sada. 

No, umjesto toga, radeći & x, doslovno sam ja prolazi u što? [Studentski] adresa. >> Adresu x. To je kao crtež kartu za funkciju zove scanf i ovdje govori, to su pravci na komad memorije u računalu da možete ići spremiti neke cijeli u. Da bi sscanf sada to učiniti što operater, ono komad sintakse će to morati koristiti iako ne možemo ga vidjeti jer je netko napisao tu funkciju? Drugim riječima - što je to? [Studentski] X pročitati. Tu će biti nekih čitanje, ali samo s obzirom na x ovdje. Ako scanf se prošli adresu x, sintaktički, što operater je dužan da postoji negdje unutar scanf provedbi tako da scanf zapravo može napisati broj dva na tu adresu? Da, tako *. Sjetite se da je naš * dereference operater, koji u suštini znači ići tamo. 

Nakon što ste se predao adresu, kao što je to ovdje slučaj, scanf je vjerojatno, ako smo zapravo gledao oko svoje izvornog koda- radi * x ili njegov ekvivalent zapravo ide na tu adresu i staviti neku vrijednost tamo. Sada, kao i za koliko scanf dobiva ulaz na tipkovnici, ćemo mahati naše ruke za danas. Samo pretpostaviti da operativni sustav omogućuje sscanf razgovarati na korisnikov tipkovnici, ali u ovom trenutku je sada u skladu 19, kada smo jednostavno isprintati x, čini se da je slučaj da scanf je staviti int u x. To je točno kako scanf radi, a podsjetimo prošlog tjedna da je točno kako GetString i GetInt i njegova druga obitelj funkcija u konačnici radi, iako s blagim varijance poput sscanf, što znači skeniranje niz umjesto tipkovnice. Ali ajmo pogledati malo varijance to. U scanf2, zapravo sam zeznuo. Što je krivo, a ja ću sakriti komentar koji objašnjava koliko- što je krivo s ovim programom, verzija 2? Budite kao tehnički moguće ovom trenutku. To izgleda prilično dobro. To je lijepo razvedena, ali- ok, o tome kako ćemo ga orezati do kraćih pitanja? Linija 16. Što je linija 16 radi u preciznom, ali tehnički engleski? Dobivanje malo nespretan. Da, Michael. [Studentski] To ukazuje na prvom slovu nizu. 

Ok, u neposrednoj blizini. Dopustite mi da uštinuti malo. Ukazujući na prvom slovu nizu, ti si deklariranje varijable zove tampon koji će ukazati na prvom adresu niza, odnosno, da će ukazati točnije na char. Obavijest to nije zapravo pokazuje nigdje jer ne postoji operator pridruživanja. Nema znak jednakosti, tako da sve radimo je dodjeljivanje varijable tzv tampon. To se događa da se 32 bita jer je pokazivač, i sadržaj međuspremnika vjerojatno na kraju će sadržavati adresu char, ali za sada, što ne sadrže tampon? Samo neki lažan, tko zna, neko smeće vrijednost, jer nismo izričito inicijaliziran, tako da mi ne bi trebali pretpostavljati ništa. Ok, tako da sada linija 17 se-što ne crta 17 učiniti? Možda da će zagrijati ovo gore. Ona ispisuje niz, zar ne? Ona ispisuje Gudački molim. 

Linija 18 je vrsta poznata sada u koje smo upravo vidjeli varijancu ove ali s drukčijim kodom formatiranja, pa je u skladu 18, mi govori scanf ovdje je adresa komad memorije. Želim da zvoni u nizu, kao implicira% s, ali problem je u tome što nismo učinili par stvari ovdje. Što je jedan od problema? [Studentski] To pokušava dereference null pokazivač. Dobro, null ili samo drugačije nepoznato pokazivače. Vi ste predaje scanf adresu, ali samo rekao maloprije da je adresa je neko smeće vrijednost jer nismo zapravo je dodijeliti ništa, i tako si govorio scanf učinkovito ići staviti string ovdje, ali ne znamo gdje je ovdje ipak je, pa nismo zapravo dodjeljuje memoriju za tampon. Štoviše, što su također ni reći scanf? Pretpostavimo da je to komad memorije, a to nije bilo smeća vrijednost, ali još uvijek ne govori scanf nešto važno. [Studentski] Gdje je to zapravo, znak za struju. Ampersand, tako da u ovom slučaju, to je u redu. Zbog tampon već je proglašen kao pokazivač s * komad sintakse, ne trebamo koristiti ampersand jer to je već adresa, ali mislim da sam ga čuo ovdje. [Studentski] Koliki je to? Dobro, nećemo reći scanf koliko je velika ta tampon je, što znači da čak i ako su tampon pokazivač, Mi tvrdimo scanf, staviti string ovdje, ali ovdje bi mogao biti dva bajta, to bi mogao biti 10 bajtova, to bi mogao biti megabajta. Scanf nema pojma, i jer je to komad memorije vjerojatno, to nije niz gostiju. To je samo niz jednom pišete znakove i \ 0 do tog komad memorije. Sada je samo neki komad memorije. Scanf neće znati kada prestati pisati na tu adresu. 

Ako podsjetiti na neke primjere u prošlosti, gdje sam slučajno upisali na tipkovnici pokušava prelijevati tampon, a razgovarali smo u petak oko upravo to. Ako protivnik nekako ubrizgava u svoj program puno veću riječ ili rečenica ili fraza onda su očekivali možete prekoračenje komad memorije, što može imati loše posljedice, kao što je uzimanje tijekom cijelog samog programa. Moramo to popraviti nekako. Dopustite mi da smanjivanje i ići u verziji 3 ovog programa. To je malo bolje. U ovoj verziji, primijetiti razliku. U skladu 16, ja opet sam deklariranje varijable zove tampon, ali ono što je sada? To je niz od 16 znakova. To je dobro, jer to znači da ja sada mogu reći scanf ovdje je stvarni komad memorije. Gotovo da možete misliti polja kao pokazivače sada, iako oni zapravo ne odgovara. Oni će se ponašati različito u različitim kontekstima. No, to je svakako slučaj da se pufer pozivom 16 susjedni znakovi, jer to je ono što je niz te je za nekoliko tjedana sada. 

Evo, ja govorim scanf evo komad memorije. Ovaj put, to je zapravo komad memorije, ali zašto je ovaj program još uvijek iskoristiv? Što je krivo dalje? Ja sam rekao, dajte mi 16 bajtova, ali- [Studentski] Što ako se upisati u više od 16? Točno, što ako korisnik upiše u 17 znakova ili 1700 znakova? U stvari, neka je vidjeti ako ne možemo spotaknuti ovu pogrešku sada. To je bolje, ali ne i savršena. Pusti me naprijed i pokrenuti napraviti scanf3 sastaviti ovaj program. Dopustite mi pokrenuti scanf3, Gudački molim: Pozdrav, i mi se čini da biti u redu. Dopustite mi da pokušam nešto duža jedan, Hello there. Ok, ajmo halo ne postoji kako ste danas, Enter. Dobivanje vrste sretan ovdje, recimo Hello there kako ste. Dovraga. Ok, tako da smo se posrećilo. Hajdemo vidjeti ako ne možemo popraviti. Ne, to neće pustiti mene kopirati. Pokušajmo ovo ponovno. U redu, stand by. Vidjet ćemo koliko dugo mogu pretvarati da se usredotoče dok je još to. Dovraga. To je prilično prikladno, zapravo. Tu ćemo ići. Točka napravio. 

To je, neugodno iako to također, to je također jedan od izvora velike konfuzije prilikom pisanja programa koji imaju bugove, jer oni se manifestiraju samo jednom u neko vrijeme ponekad. Realnost je da čak i ako je vaš broj je potpuno razbijen, to samo može biti potpuno slomljena jednom u neko vrijeme jer ponekad, bitno ono što se događa je operativni sustav dodijeli malo više memorije nego što je zapravo potrebno za bilo kojeg razloga, i tako nitko drugi ne koristi memoriju odmah nakon komad 16 znakova, tako da ako idete na 17, 18, 19, god, to nije tako velika stvar. Sada, računalo, čak i ako to ne srušiti u tom trenutku, Možda eventualno koristiti byte broj 17 ili 18 ili 19 za nešto drugo, na kojima ističu svoje podatke koje ste stavili tamo, iako pretjerano dugo, će dobiti prebrisana potencijalno nekom drugom funkcijom. To nije nužno će ostati netaknut, ali to ne mora nužno će izazvati SEG kvar. No, u ovom slučaju, napokon sam pod uvjetom dovoljno znakova da sam u suštini premašila moj segment memorije, i bam, operativni sustav je rekao, "Žao mi je, to nije dobro, segmentacija krivnja." 

I neka je vidjeti ako sada ono što ostaje ovdje u mom imeniku- primijetiti da imam ovu sliku ovdje, jezgru. Primijetit ćete da je ovo opet se zove temeljni deponij. To je u osnovi datoteka koja sadrži sadržaj svog programa u memoriju na mjestu na kojem se srušio, i samo pokušati malo primjer ovdje me pusti unutra i pokrenuti gdb na scanf3 a zatim odredite trećine argument zove jezgra, i primijetiti da se ovdje, ako sam popis kôd, moći ćemo kao i obično sa gdb za početak hodanja kroz ovaj program, i ja mogu ga pokrenuti i čim sam pogodio-kao s korak zapovjedništvom u gdb- čim sam pogodio potencijalno lud liniju nakon upišete u veliki niz, Ja ću biti u mogućnosti da se zapravo to prepoznati ovdje. Više o tome, međutim, u dijelu u smislu temeljnih deponija i sviđa, tako da možete zapravo džaku okolo unutar jezgre deponij i vidjeti na što linija program vam nije uspjelo. Sva pitanja onda na pokazivače i na adrese? Budući da je danas na, idemo početi uzimati zdravo za gotovo da se takve stvari postoje i točno znamo što su oni. Da. 

[Studentski] Kako doći nisi morati staviti ampersand pored dijela- Dobro pitanje. Kako doći Nisam morati staviti ampersand pored znaka niz kao što sam učinio prije s većinom naših primjera? Kratak odgovor je nizovi su malo posebna. Gotovo da možete misliti tampon kao zapravo se adresa, i to samo tako dogodi da se slučaj da uglata zagrada zapis je praktičnost, tako da možemo ići u konzolu 0, noseći 1, Nosač 2, bez potrebe za korištenje * zapis. To je malo bijelog laži, jer nizovi i pokazivače su, u stvari, malo drugačiji, ali oni mogu često, ali ne uvijek se koriste naizmjenično. Ukratko, kada funkcija očekuje pokazivač na komad memorije, možete ili proći ga adresu koja je vratio malloc, pa ćemo vidjeti malloc opet prije dugo, ili možete proći mu ime niza. Vi ne morate učiniti ampersand s polja jer su već bitno mi adrese. To je jedna iznimka. Uglatih zagrada bi ih posebno. 

Možete li staviti ampersand uz tampon? Ne u ovom slučaju. To neće raditi jer, opet, ove kutak slučaju gdje nizovi nisu sasvim zapravo adrese. Ali mi možda ću se vratiti na to prije dugo s drugim primjerima. Idemo pokušati riješiti problem ovdje. Imamo strukturu podataka koje smo koristeći za neko vrijeme poznat kao polje. Slučaj u točki, to je ono što smo upravo imali. Ali polja imaju neke odlika i nedostataka. Nizovi su lijepe zašto? Što je jedna stvar koja vam se sviđa, u mjeri u kojoj vam se sviđa polja-o nizovima? Što je povoljno o njima? Što je uvjerljiv? Zašto smo ih predstaviti na prvom mjestu? Da. [Studentski] Oni mogu pohraniti mnogo podataka, a da ne morate koristiti cijelu stvar. Možete koristiti sekciju. Dobro, s nizom možete pohraniti mnogo podataka, i ne moraju nužno koristiti sve to, tako da možete overallocate, što bi moglo biti praktično ako ne znate unaprijed koliko nešto očekivati. 

GetString je savršen primjer. GetString, napisao nas, nema pojma koliko znakova za očekivati, tako je činjenica da možemo izdvojiti komade memorijskog je dobro. Nizovi i riješiti problem što smo vidjeli prije par tjedana sada gdje je vaš broj počinje prenijeti u nešto vrlo loše dizajniran. Sjetite se da sam stvorio studentski strukturu zove David, a zatim da je zapravo alternativa, iako, da imaju promjenjivu zove ime i drugu varijablu zove, mislim, kuća, i još jedna varijabla zove ID, jer je u toj priči onda sam htio uvesti nešto drugo sviđa Rob u program, pa onda sam odlučio pričekati minutu, Moram preimenovati te varijable. Nazovimo minu NAME1, ID1, house1. Nazovimo Rob je NAME2, house2, ID2. Ali onda čekaj malo, što je Tommy? Tada smo imali još tri varijable. Uveli smo netko drugi, četiri seta varijabli. Svijet se počeo neuredan vrlo brzo, tako da smo uveli tvorevina, a ono što je uvjerljiv o struct? Što znači C struct neka vam je činiti? To je stvarno neugodno danas. Što? >> [Nečujno učenik odgovor] Da, posebno, typedef vam omogućuje da stvorite novu vrstu podataka, i rekonstruirati struct ključna riječ, omogućuje vam da zatvoriti u kućište koncepcijski vezane komada podataka zajedno , a nakon toga ih nazvati nešto kao student. 

To je dobro, jer sada možemo modelirati mnogo vrsta koncepcijski dosljedno pojam student u varijablu nego proizvoljno ima jedna za nizu, jedan za ID, i tako dalje. Nizovi su lijepe jer su nam omogućiti početak čišćenja naš kod. No, ono što je minus od sada niz? Što možete učiniti ne? Da. [Studentski] Morate znati koliko je velika. Morate znati koliko je velika, tako da je vrsta boli. Oni od vas s prethodnom programskom iskustva znam da u puno jezika, poput Jave, možete pitati komad memorije, posebno polje, koliki su vam, s dužinom, nekretnina, tako da se govori, a to je stvarno zgodan. U C, ne možete ni nazvati strlen na generičke niz jer strlen, kao riječ implicira, je samo za gudače, i možete shvatiti duljinu niza zbog ovog ljudskog konvencije posjedovanja \ 0, ali lepezu, više općenito, je samo komad memorije. Ako je niz Ints, tamo neće biti neki poseban lik na kraju vas čeka. Morate zapamtiti duljinu niza. Drugi downside niz uzgajaju svoju glavu u sebe GetString. Što je još jedan downside niz? Gospodine, samo ti i ja danas. [Nečujno učenik odgovor] >> To je ono što? To je izjavio na stog. Ok, izjavio je na stogu. Zašto ne sviđa? [Studentski] Zato što dobiva ponovno. Ona dobiva ponovno. Ok, ako koristite niz alocirati memoriju, ne možete, na primjer, da ga vratite, jer je na stogu. Ok, to je nedostatak. A o tome kako jedna druga s nizom? Nakon što ga izdvojiti, ti si vrsta pijan ako trebate više prostora nego da ima niz. 

Zatim smo uveli, podsjetimo, malloc, koji nam je dao mogućnost da dinamički alocirati memoriju. No, što ako smo pokušali drugačiji svijet uopce? Što ako smo htjeli riješiti nekoliko tih problema pa smo umjesto-moja olovka je zaspao ovdje- što ako smo umjesto htjeli biti stvoriti svijet koji je više ovako? To je niz, i, naravno, ova vrsta pogoršava kad smo udarili kraj niza, i ja sada više nemaju prostora za još cijeli ili drugog karaktera. Što ako smo vrsta preventivno reći dobro, zašto ne bismo opustiti ovaj uvjet da su svi ti komadi memorije biti neprekinut natrag na leđa, i zašto ne, kad trebam int ili char, daj mi prostor za jednu od njih? A kad trebam drugi, dajte mi još jedan prostor, i kad trebam drugi, dajte mi još jedan prostor. Prednost koja je sada da ako netko drugi uzima memoriju ovamo, nije velika stvar. Ja ću uzeti ovaj dodatni komad memorije ovdje i onda ovaj jedan. 

Sada, samo kvaka je u tome što je ovo gotovo osjeća kao da imam cijela hrpa različitih varijabli. To se osjeća kao pet različitih varijabli potencijalno. No, što ako mi ukrade ideju od žice pri čemu smo nekako povezati ove stvari zajedno konceptualno, a što ako sam to učinio? Ovo je moj jako slabo nacrtana strelica. Ali pretpostavimo da je svaki od tih komade memorije ukazao na drugu, a ovaj momak, koji nema sestru na svojoj desnoj strani, nema takve strelicu. To je u stvari ono što se zove linked list. Ovo je nova struktura podataka koji nam omogućava da dodijeli komad memorije, zatim još jedan, pa još jedan, pa još jedan, u bilo koje vrijeme želimo tijekom programa, a mi ne zaboravite da su svi nekako povezano doslovno ulančavanje ih zajedno, a mi to učinio slikovito ovdje sa strelicom. No, u kodu, što će biti mehanizam putem kojeg nekako mogao spojiti, gotovo kao Scratch, jedan komad na drugi komad? Mogli bismo koristiti pokazivač, zar ne? Jer stvarno strelica koja ide od gornjeg lijevog kvadrata, ovaj tip ovdje na ovaj jedan, mogao sadržavati unutar ovog trga ne samo neke Ints, a ne samo neke char, ali što ako sam zapravo dodijeljena malo dodatni prostor, tako da sada, svaki od mojih komade memorije, iako će to trošak mene, sada izgleda malo više pravokutnog gdje je jedan od komade memorije koristi se za broj, kao i broj 1, i onda ako taj tip pohranjuje broj 2, ovaj drugi blok memorije se koristi za strelice, ili konkretnije, pokazivač. I pretpostavljam da pohraniti broj 3 ovamo dok sam koristiti ovaj ukazati na tog momka, i sad taj tip, pretpostavimo samo želim tri takve komade memorije. Ja ću povući crtu preko toga, što ukazuje null. Nema dodatnih znakova. 

Doista, to je način kako možemo ići o provedbi nešto što se zove linked list. Povezani popis je nova struktura podataka, a to je odskočna daska prema puno luksuznijih strukture podataka koje počinju za rješavanje problema na tragu Facebook-tipa problema i Google tipa problema gdje imate ogromne skupove podataka, i to više ne reže pohraniti sve contiguously i koristiti nešto poput linearnog pretraživanja ili čak nešto poput binarnog pretraživanja. Želite još bolje izvodi puta. U stvari, jedan od svetih gralova ćemo razgovarati o kasnije ovaj tjedan ili sljedeći je algoritam čije trajanje je konstanta. Drugim riječima, ona uvijek ima istu količinu vremena bez obzira na koliki je ulaz, a da bi doista biti uvjerljiv, čak i više nego nešto logaritamske. Što je to na zaslonu ovdje? Svaka od pravokutnika je točno ono što sam nacrtao rukom. Ali stvar skroz na lijevoj strani je posebna varijabla. To će biti jedan pokazivač jer jedan Gotcha s povezanog popisa, kao što su ove stvari zove, je da morate objesiti na jednom kraju povezana popisa. 

Baš kao i kod niza, morate znati adresu prvog char. Sve posao za povezane liste. Morate znati adresu prvog komad memorije jer od tamo, možete doći svaki drugi jedan. Downside. Što cijena plaćamo za tu svestranost ima dinamički poveliki struktura podataka da ako mi zatreba više memorije, fino, samo izdvojiti još jedan komad i izvući pokazivač iz starog na novi rep popisu? Da. [Studentski] To traje oko dva puta onoliko prostora. To traje duplo puno prostora, tako da je definitivno mana, a vidjeli smo to tradeoff prije između vremena i prostora i fleksibilnosti gdje je do sada, ne trebamo 32 bita za svaki od tih brojeva. Mi stvarno trebamo 64, 32 za broj i 32 za pointer. Ali hej, ja imam dva gigabajta RAM-a. Dodavanje još 32 bita ovdje i ovdje se ne čini da je velika stvar. No, za velike skupove podataka, to je definitivno dodaje do doslovno duplo više. Što je još jedan minus sada, ili što igrani mi odustati, ako mi predstavljaju popise stvari s popisa povezane, a ne polje? [Studentski] Vi ne možete prijeći unatrag. Vi ne možete prijeći unatrag, tako da ste vrsta pijan ako ste hodanje s lijeva na desno pomoću for petlje ili while petlja i onda ste shvatili, "Oh, želim se vratiti na početak popisa." Vi ne možete jer ti upućuje samo ići s lijeva na desno, kao strelice pokazuju. 

Sada, mogao sjetiti početak popisa s nekom drugom varijablom, ali da je složenost imati na umu. Polje, bez obzira koliko daleko idete, uvijek možete napraviti minus, minus, minus, minus i vratiti se odakle si došao. Što je još jedan minus ovdje? Da. [Nečujno učenik pitanje] Ti bi mogao, tako da ste zapravo samo predložio strukturu podataka zove dvostruko povezana lista, i doista, što bi dodati još jedan pokazivač na svaki od tih pravokutnika koji ide u drugom smjeru, naopako koji Sada je možete proći naprijed i natrag, downside koji sada koristite tri puta više memorije kako smo i dodao složenosti u smislu koda morate napisati da se to pravo. No, sve su to možda vrlo razumne kompromise, ako preokret je važnije. Da. [Studentski] Također, ne možete imati 2D povezanu listu. Dobro, ne možete stvarno imati 2D povezanog popisa. Ti bi mogao. To nije gotovo kao jednostavan kao polje. Kao i niz, što učiniti otvorenu zagradu, zatvorena zagrada, otvoren nosač, zatvorena zagrada, i vi dobiti neke 2-dimenzionalnu strukturu. Ti bi mogao provesti 2-dimenzionalni povezanog popisa ako to ne učinite dodatak kao što predlaže-trećine pokazivač na svaki od tih stvari, i ako mislite o drugom popisu dolaze na vas 3D stil na zaslonu za sve nas, što je samo još jedan lanac neke vrste. Možemo to učiniti, ali to nije tako jednostavno kao tipkati otvorenu zagradu, Trg nosača. Da. [Nečujno učenik pitanje] Dobro, tako da je ovo pravi udarač. 

Ovi algoritmi koje smo pined više, kao i oh, binarno pretraživanje, možete pretraživati ​​niz brojeva na ploči ili adresar tako puno brže ako koristite podijeli pa vladaj i binarni algoritam za pretraživanje, ali binarno pretraživanje potrebne dvije pretpostavke. Jedan od njih, koji su podaci razvrstani. Sada smo vjerojatno može zadržati ovu razvrstani, pa možda to nije briga, ali binarno pretraživanje također pretpostavlja da ste imali slučajni pristup popisu brojeva, i niz vam omogućuje da imaju slučajni pristup, te izravnim pristupom, Mislim, ako ste s obzirom niz, koliko vremena to vas odvesti doći do nosača 0? Jedna operacija, samo koristiti [0] i ti si tamo. Koliko koraka je potrebno da biste dobili na lokaciji 10? Jedan korak, možete samo ići na [10] a ti si tamo. Nasuprot tome, kako ste dobili na 10. cijeli u povezanoj listi? Morate početi na početku, jer ste samo sjećanja početak povezane liste, baš kao i niza se sjetio po adresu svog prvog char, i naći taj 10. int ili da 10. znak u nizu, morate tražiti cijeli prokletu stvar. 

Opet, nismo rješavanje svih naših problema. Mi smo uvođenjem novih, ali to stvarno ovisi o tome što pokušavate dizajn za. U pogledu provedbe toga, možemo posuditi ideju iz tog studentskog strukture. Sintaksa je vrlo sličan, osim sada, ideja je malo više apstraktna od kuća i ime i ID. Ali ja predlažem da bismo mogli imati strukturu podataka u C koji se zove čvor, kao posljednja riječ na slajdu sugerira, unutar čvora, a čvor je samo generički kontejner u informatici. To je obično nacrtana kao krug ili kvadrat ili pravokutnik kao što smo učinili. I u ovom strukture podataka, imamo int, n, tako da je broj Želim pohraniti. No, ono što je ova druga linija, struct node * sljedeći? Zašto je to točno, ili koja je uloga ova stvar igra, iako je to malo zagonetan na prvi pogled? Da. [Nečujno učenik odgovor] Točno, tako * vrsta plijena da je pokazivač neke vrste. Ime ovog pokazivač je samovoljno sljedeći, ali mogli smo ga zvali sve što želimo, ali što to pokazivač točka? [Studentski] Drugi čvor. >> Točno, to ukazuje na drugom takvom čvoru. 

Sada, ovo je neka vrsta znatiželje C. Podsjetimo da je C pročitati prevodilac vrha do dna, s lijeva na desno, što znači da ako-to je malo drugačije od onoga što smo radili s učenikom. Kada smo definirali student, mi zapravo nisam stavio riječ postoji. To je samo rekao typedef. Tada smo imali int id, string ime, string kuću, a zatim student na dnu struct. Ova izjava je malo drugačiji, jer, opet, C prevodilac je malo glupo. To samo ide na čitanje vrha do dna, pa ako dođe do 2. liniju ovdje gdje pored je proglašen i to vidi, oh, ovdje je varijabla zove sljedeći. To je pokazivač na struct čvora. Prevodilac će ostvariti ono što je struct čvor? Nikad nisam čuo tu stvar prije, jer čvor riječ inače ne bi mogli pojaviti do dna, tako da je to redundancija. Morate reći struct čvor ovdje, koje zatim možete skratiti kasnije zahvaljujući typedef ovdje dolje, ali to je zato mi smo s pozivom na strukturu sama unutar strukture. To je jedan Gotcha tamo. 

Neke zanimljive problemi će nastati. Imamo popis brojeva. Kako umetnuti u njega? Kako ćemo ga traži? Kako ćemo izbrisati iz njega? Pogotovo sada kada imamo upravljati svim tim pokazivače. Mislili ste pokazivače su vrsta um-savijanje kada je imao jedan od njih samo pokušava pročitati int na njega. Sada moramo manipulirati cijeli popis vrijedi. Zašto ne uzimamo naš 5-minutni predah ovdje, a onda ćemo donijeti neki ljudi na pozornici učiniti upravo to. 

C je puno zabavnije kada je glumio. Tko doslovno bih biti prvi? Ok, dođi na gore. Vi ste na prvom mjestu. Tko želi biti 9? Ok, devet. Kako o 9? 17? Malo klika ovdje. 22 i 26 u tom prvom redu. I kako se onda o nekome tamo se istaknuo u. Vi ste 34. Ok, 34, dolaze na gore. Prvo je tamo. Ok, sve četiri od vas dečki. A tko nije kažemo za 9? Tko je naša 9? Tko doista želi biti 9? Dobro, hajde, biti devet. Ovdje ćemo ići. 34, mi ćemo vas upoznati tamo. Prvi dio je napraviti sami izgledaju kao da. 26, 22, 17, dobro. Ako možete stajati sa strane, jer ćemo vas malloc u trenutku. 

Dobro, dobro. Ok, odličan, pa ajmo postaviti nekoliko pitanja ovdje. I zapravo, ono što je vaše ime? >> Anita. Anita, ok, dođi ovamo. Anita će nam pomoći vrsta riješiti jedan prilično jednostavno pitanje u prvom, koji je kako vam li ili ne vrijednost na popisu? Sada, primijetite da je prvi, i ovdje su zastupljeni Lucas, je malo drugačiji, pa mu je komad papira je namjerno bočno jer to nije sasvim kao visok i ne zauzimaju onoliko bitova, iako tehnički ima istu veličinu papira samo okretati. Ali on je malo drugačiji u smislu da je samo 32 bita za pokazivač, i svi ovi dečki su 64 bita, od kojih polovica je broj, od kojih polovica je pokazivač. Ali pokazivač nije prikazano, pa ako vi mogli nešto nespretno koristiti lijevu ruku ukazati na osobu pored vas. A ti si broj 34. Koje je vaše ime? Ari. Ari, tako da zapravo, držite papir u desnoj ruci, a lijevom rukom ide ravno prema dolje. Vi predstavljate null na lijevoj strani. 

Sada naša ljudska slika je vrlo dosljedan. To je zapravo kako upućuje raditi. I ako možete stiskati malo na ovaj način, tako da nisam u svoj način. Anita ovdje, naći mi broj 22, ali pretpostavljaju ograničenje ne ljudi drži do komada papira, ali ovo je popis, a imate samo Lucas početi s jer on je doslovno prvi pokazivač. Pretpostavimo da ste sami pokazivač, pa vi imate mogućnost da pokazuje na nešto. Zašto ne započeti ukazujući na upravo ono što je Lucas pokazujući na? Dobro, i neka mi donese ovo ovdje. Samo radi rasprave, neka mi podići praznu stranicu ovdje. Kako se piše vaše ime? >> Anita. Ok, Anita. Recimo čvor * Anita = Lucasa. Pa, mi ne bi trebali zvati Lucas. Trebali bismo nazvati prvi. Zašto je to u stvari dosljedan sa stvarnošću ovdje? Jedan od njih, prvi već postoji. Prvo je dodijeljeno vjerojatno negdje ovdje. Čvor * prvi, i to je bio dodijeljen popis nekako. Ne znam kako se to dogodilo. To se dogodilo prije sat počeo. Ovo povezani popis ljudi je stvorio. I sada u ovom trenutku u priču-to sve ide na Facebook-u očito kasnije U ovom trenutku u priči, Anita je inicijalizirana biti jednaka prvi, što ne znači da je Anita bodova na Lucasa. Umjesto toga, ona ukazuje na ono što on ukazuje na jer ista adresa koja je unutar Lucas je 32 bita - 1, 2, 3 - Sada je također unutar Anita je 32 bita - 1, 2, 3. 

Sada pronaći 22. Kako bi vam ići oko radiš? Što je to? >> Rose što god. Pokažite što god, pa ići naprijed i djelovati najbolje što možete ovdje. Dobro, dobro, a sada ste pokazujući na-ono što je vaše ime sa 22? Ramon. >> Ramon, pa Ramon drži do 22. Sada ste učinili ček. Da li Ramon == 22, i ako je tako, na primjer, možemo se vratiti istina. Me-a Neka ti dečki ovdje stajati nešto nespretno- neka mi nešto učiniti brzo kao bool pronaći. Ja ću ići naprijed i reći (čvor * lista, int n). Odmah ću se vratiti s vama. Moram samo napisati neki kod. A sada ću ići naprijed i učiniti ovu, čvor * Anita = popis. I ja ću ići naprijed i reći dok (anita! = NULL). 

Metafora ovdje je uzimajući malo nategnut, ali dok (anita! = NULL), što želim učiniti? Trebam neki način referenciranje cijeli broj koji je Anita pokazujući na. U prošlosti, kada smo imali strukture, koja čvor, koristili smo dot zapis, a mi bi reći nešto poput anita.n, ali problem ovdje je da Anita nije struct po sebi. Što je ona? Ona je pokazivač, tako da stvarno, ako želimo koristiti ovaj dot-notaciju i to će izgledati namjerno malo grobni- moramo učiniti nešto slično ići na ono što Anita lijevoj ruci je pokazujući na i onda se polje pod nazivom n. Anita je pokazivač, ali ono što je * anita? Što vam kad idete na ono što Anita pokazujući na? Rekonstruirati čvor, i čvora, povlačenje, ima polje zove n jer je, podsjetimo, ove dvije stavke, sljedeći i n, da smo vidjeli maloprije ovdje. 

Da zapravo oponašaju to u kodu, bismo mogli to učiniti i reći: if ((* anita). n == n), n da sam u potrazi za. Primijetite da funkcija donesen u broju mi ​​je stalo. Zatim Ja mogu ići naprijed i učiniti nešto poput povratka pravu. Inače, ako to nije slučaj, što ne želim raditi? Kako prevesti kodirati ono što Anita učinio intuitivno šetnjom kroz popisu? Što bih trebao učiniti ovdje simulirati Anita uzimajući taj korak s lijeve strane, taj korak u lijevo? [Nečujno učenik odgovor] >> Što je to? [Nečujno učenik odgovor] Dobro, nije loša ideja, ali u prošlosti, kada smo to učinili, što smo učinili anita + + jer da bi dodali na broj jedan na Anita, koji bi obično upućuju na sljedeću osobu, kao što su Ramon, ili osoba pored njega, ili pored njega osoba niz liniju. No, to nije sasvim dobro ovdje, jer ono to stvar izgledati u sjećanju? Nije da. Moramo onemogućiti da. To izgleda ovako u memoriji, i iako sam nacrtana 1 i 2 i 3 blizu jedna drugoj, ako smo stvarno simuliraju to-mogu ti dečki, dok je još uvijek pokazujući na istim ljudima, može neki od vas uzeti slučajni korak natrag, neki od vas slučajni korak naprijed? 

Ovaj nered je još uvijek povezana lista, ali ovi momci bi mogao biti bilo gdje u memoriji, tako anita + + ne ide raditi zašto? Što je na lokalitetu Anita + +? Tko zna. To je neka druga vrijednost koja samo tako dogodi da se umetnuo među svim tim čvorova slučajno, jer mi ne koristimo niz. Mi dodjeljuje svake od tih čvorova pojedinačno. Dobro, ako vi možete sami očistiti natrag gore. Dopustite mi predložiti da se umjesto anita + +, umjesto toga učiniti Anita dobiva- dobro, zašto ne idemo na ono što Anita pokazujući na, a zatim učinite. sljedeći? Drugim riječima, idemo na Ramon, koji je drži broj 22, i onda. sljedeći je kao da Anita bi se kopiranje lijevoj ruci pokazivač. Ali ona neće ići dalje od Ramon jer smo pronašli 22. No, da bi se ideja. Sada, to je bog-strašno nered. Iskreno, nitko neće pamtiti ovu sintaksu, pa hvala bogu, to je zapravo malo namjerno-oh, niste zapravo vidjeli ono što sam napisao. To će biti uvjerljiviji ako bi mogao. Voila! 

Iza kulisa, bio sam riješiti problem na ovaj način. Anita, poduzeti taj korak s lijeve strane, prvo, mi ne idu na adresu koju je Anita pokazujući na i gdje će se naći ne samo n, koje smo upravo provjerava Usporedbe radi, ali ćete također pronaći sljedeći - u ovom slučaju, Ramon je lijeva ruka pokazuje na sljedeći čvor u popisu. Ali ovo je bog-strašno nered koji sam spomenuo ranije, ali ispada C omogućuje nam pojednostaviti ovaj. Umjesto pisanja (* anita), umjesto toga možete samo napisati Anita-> N, i to je točno ista stvar funkcionalno, ali to je puno više intuitivan, i to je puno više u skladu sa slikom da smo crtanje sve ovo vrijeme koristeći strelice. 

Na kraju, ono što trebamo učiniti na kraju ovog programa? Postoji jedna linija koda preostale. Povratak što? Netočno, jer ako smo dobili kroz cijelu while petlja i Anita je, u stvari, null, to znači da je otišla sve do kraja popisa gdje je pokazujući na-ono zoveš? Ari. >> Ari je lijeva ruka, koja je null. Anita je sada null, i shvaćam da ste samo stajati ovdje nespretno u limbu jer ću off na monolog ovdje, ali mi ćemo vas uključiti opet u samo trenutak. Anita je nula u tom trenutku u priči, tako da while petlja završava, i moramo se vratiti lažna jer ako je dobio sve do Ari je NULL pokazivač tada nije bilo broj koji je tražio u popisu. Možemo očistiti ovo gore previše, ali to je prilično dobra provedba zatim od obuhvaćanje funkcije, pronaći funkciju za povezane popisa. To je još uvijek linearno pretraživanje, ali to nije tako jednostavno kao + + pokazivač ili + + ja promjenjiva jer sada ne možemo nagađati gdje je svaki od tih čvorova su u memoriji. Moramo doslovno slijediti trag mrvice ili, točnije, upućuje, da se iz jednog čvora na drugi. 

Sada ćemo pokušati još jednom. Anita, hoćeš doći ovamo? Zašto ne možemo ići naprijed i dodijeliti jedna drugu osobu iz publike? Malloc-ono što je vaše ime? >> Rebecca. Rebecca. Rebecca je malloced iz publike, i ona je sada pohranu broj 55. A cilj pri ruci sada je za Anita umetnuti Rebecca u povezanoj listi ovdje u svojoj odgovarajuće mjesto. Dođi ovamo na trenutak. Učinio sam nešto ovako. Ja sam učinio čvor *. I ono što je vaše ime ponovno? Rebecca. >> Rebecca, ok. Rebecca dobiva malloc (sizeof (čvor)). Baš kao što smo izdvojili stvari kao što su učenike i sitnica u prošlosti, trebamo veličinu čvora, tako da sada Rebecca pokazuje na što? Rebecca ima dva polja unutar nje, od kojih je jedan 55. Idemo raditi ono, rebecca-> = 55. Ali onda rebecca-> next treba-mi upravo sada, njezina ruka je vrsta, tko zna? To je pokazujući na nekom smeće vrijednosti, pa zašto ne za dobru mjeru mi barem to učiniti, tako da lijeva ruka je sada na njezinoj strani. Sada Anita, uzmi ga ovdje. Imate Rebecca što je dodijeljeno. Idi naprijed i naći gdje smo trebali staviti Rebeccu. Dobro, vrlo dobro. Dobro, dobro, a sada trebamo li osigurati malo smjeru, tako da ste postigli Arija. Njegova mi je lijeva ruka null, ali Rebecca jasno pripada pravo, pa kako ne moramo mijenjati ovu povezan popis kako bi se umetnuti Rebeccu u odgovarajućem mjestu? Ako doslovno mogao pomaknuti tuđe lijeve ruke oko po potrebi, ćemo riješiti problem na taj način. Dobro, dobro, au međuvremenu, Rebecca je lijeva ruka je sada uz nju. 

To je bilo previše lako. Pokušajmo dodjele-Mi smo gotovi, 20. Ok, dođi na gore. 20 je dodijeljeno, pa neka mi ići naprijed i opet reći ovdje upravo smo učinili Saad čvor *. Imamo malloc (sizeof (čvor)). Mi smo tada učiniti isto točno sintaksu kao što smo radili prije za 20, i ja ću učiniti sljedeći = null, a sada je do Anita umetnuti ste u povezane liste, ako bi mogao igrati taj isti ulogu. Izvrši. Dobro, dobro. Sada razmislite prije nego što počnete se kreće lijevo oko ruke. Vi daleko dobio najviše neugodan ulogu danas. Čiju ruku treba biti premještena prvi? Ok, čekajte, ja sam čuo neke ne-a. Ako neki ljudi pristojno željeli pomoći riješiti neugodne situacije ovdje. Čija lijeva ruka treba ažurirati prvi možda? Da. [Studentski] Saad-a. Ok, Saad je, zašto, iako? [Nečujno učenik odgovor] Dobro, jer ako se krećemo-ono što je vaše ime? >> Marshall. Marshall, ako idemo ruku prvi dolje na nulu, sada doslovno smo siročad četvero ljudi na ovom popisu jer je bio jedina stvar ukazujući na Ramon i svatko na lijevoj strani, tako da je pokazivač ažuriranja prvi je bio loš. Ajmo poništiti to. Dobro, a sada ići naprijed i premjestiti na odgovarajuću lijevu ruku pokazujući na Ramon. To se osjeća malo suvišnim. Sada postoje dvije osobe upućuju na Ramon, ali to je u redu jer sada kako drukčije ne možemo ažurirati popis? Što druge strane mora premjestiti? Izvrsno, sad imamo izgubio pamćenje? Ne, tako dobro, neka je vidjeti ako ne možemo razbiti još jednom. 

Mallocing jedan posljednji put, broj 5. Sve način na leđima, hajde dolje. To je vrlo uzbudljivo. [Pljesak] Koje je vaše ime? >> Ron. Ron, ok, ti ​​si malloced kao broj pet. Upravo smo izvršiti kod koji je gotovo identičan njih sa samo pod drugim imenom. Izvrsno. Sada, Anita, sretno umetanjem broj 5 u popis sada. Dobro, i? Izvrsno, tako da je ovo stvarno treći od tri ukupnih slučajeva. Mi smo prvi put imali nekoga na kraju, Rebecca. Mi smo tada imali nekoga u sredini. Sada imamo nekoga na početku, iu ovom primjeru, sada smo morali ažurirati Lucas po prvi put jer je prvi element u popisu sada ima ukazati na novi čvor, koji je, pak, pokazujući na čvoru broj 9. 

To je bio iznimno neugodan demonstracija, siguran sam, tako veliki aplauz za ove dečke, ako bi mogao. Lijepo učinjeno. To je sve. Možete zadržati svoje papiriće kao malo memorije. Ispada da je to u kodu nije baš tako jednostavno kao samo pomicanjem ruke oko i pokazujući upućuje na različite stvari. Ali shvatiti da kada je u pitanju vrijeme provesti nešto poput povezani popis ili varijanta ako se usredotočiti na stvarno ove osnovne osnove, i veličine zalogaja problemi moram shvatiti, je ova ruka ili ova ruka, shvatite da je ono što je inače prilično složen program može, u stvari, biti smanjen na relativno jednostavnih građevnih blokova kao što je ovaj. 

Ajmo uzeti stvari u sofisticiranijim smjeru dalje. Mi sada imamo pojam povezan popisu. Također imamo-zahvaljujući prijedlog tamo-dvostruko povezana lista, koji izgleda gotovo isto, ali sada imamo dva pokazivača unutar struct umjesto jednog, a vjerojatno ćemo se mogli nazvati one pokazivače prethodni i sljedeći ili lijevo ili desno, ali mi, u stvari, trebati dva od njih. Kod će biti malo više uključeni. Anita bi morao učiniti više raditi ovdje na sceni. No, svakako bi mogao provoditi takvu strukturu. U smislu trčanje vremena, iako, što će biti trčanje vrijeme za Anita pronalaženja broj n u povezanoj listi sada? Ipak veliki O n, tako da je nema boljeg od linearnog pretraživanja. Mi ne možemo učiniti binarnog pretraživanja, međutim, opet. Zašto je to tako? Vi ne možete skakati okolo. Iako smo očito vidi sve ljude na pozornici, i Anita mogao ga eyeballed i rekao: "Ovdje je sredinom popisu" ona ne bi znali da li je ona bila računalni program jer je jedino ona je morala uskladiti s početkom u scenariju bio je Lucas, koji je bio prvi pokazivač. Ona bi nužno moraju slijediti te veze, računajući svoj put do našla otprilike u sredini, pa čak i onda, ona neće znati kada je ona dosegla sredini osim ako ona ide skroz do kraja shvatiti koliko postoje, onda backtracks, i da je bilo teško, osim ako je dvostruko povezana lista neke vrste. 

Rješavanje neke probleme i danas, ali uvođenjem druge. Što o različitim strukture podataka uopce? Ovo je fotografija od ladica u Mather House, i, u ovom slučaju, imamo strukturu podataka smo također vrsta već pričaju. Razgovarali smo o hrpi u kontekstu memorije, i to je neka vrsta namjerno zove jer stog u smislu memorije je učinkovito struktura podataka koji ima sve više i više stvari slojevita na vrhu. No zanimljiva stvar o hrpi, kao što je slučaj u stvarnosti, je da je to posebna vrsta podataka strukture. To je struktura podataka kojom prvi element u je posljednji elemenat van. Ako ste prvi ladica da se stavi na hrpu, ćeš biti nažalost posljednji pladanj biti skinut snop, i to nije nužno dobra stvar. Isto tako, možete misliti o tome obrnuto, posljednja u je prvi van. 

Sada, ne bilo scenariji dolaze u obzir gdje ima hrpu struktura podataka u kojoj imate tu imovinu od posljednjih u, prvi van, zapravo uvjerljiv? Je li to dobra stvar? Je li to loše? To je definitivno loša stvar ako ladice nisu svi jednaki i svi su bili posebni različite boje ili sitnica, i boju koju želite je skroz na dnu. Naravno, ne možete dobiti da bez velikog truda. Morate početi od vrha i raditi svoj put prema dolje. Isto tako, što ako ste bili jedan od tih navijačkih dječaka tko čeka cijelu noć pokušavao dobiti iPhone i linije gore na ovakvom mjestu? Zar ne bi bilo lijepo ako Apple store bili struktura stog podataka? Jupi? Naprotiv? To je jedino dobro za ljude koji pokazuju prema gore u zadnji mogući tren i onda se izvukao off red. A u stvari, činjenica da sam toliko bio sklon reći red je zapravo u skladu s onim što bismo mogli nazvati ova vrsta strukture podataka, jedan u stvarnosti u kojoj bi se stvar, i želite prvi u biti prvi jedan od ako se samo radi o ljudskoj pravednosti. Mi općenito ću nazvati da struktura red podataka. 

Ispada osim povezane liste, možemo početi koristiti iste osnovne ideje i početi stvarati nove i drugačije vrste rješenja problema. Na primjer, u slučaju hrpu, možemo predstavljaju snop pomoću strukturu podataka kao što je ovaj, ja bih predložiti. U ovom slučaju, ja sam proglašen struct, a ja sam rekao unutar ove strukture je niz brojeva, a zatim varijablu veličine, i ja ću nazvati ovu stvar hrpu. Sada, zašto se to zapravo radi? U slučaju hrpu, mogao sam izvući ovu učinkovito na zaslonu kao niz. Ovdje je moj stog. To su moji brojevi. A mi ćemo ih povući, jer to, to, to, to, to. I onda imam neke druge podatke član ovdje, koji se zove veličina, tako da je ovo veličina, a to je broj, i kolektivno, cijela ipad ovdje predstavlja jedan slog strukturu. Sada, po defaultu, veličina vjerojatno je dobio inicijalizirane na 0, i ono što je unutar niza brojeva početku kad sam prvi put dodijeliti niz? Odvoz. Tko zna? I to zapravo ne smeta. Nije važno ako je to 1, 2, 3, 4, 5, potpuno slučajno po peh pohranjene u mojoj strukturi, jer tako dugo kao što ja znam da je veličina dimnjaka je 0, onda znam programatski, ne gledati na bilo koji od elemenata u nizu. Nije važno što je tamo. Ne gledaj na njih, kao što će biti implikacija veličine od 0. 

Ali pretpostavimo da sada idem naprijed i umetnite nešto u dimnjaku. Želim umetnuti broj 5, pa sam stavio broj 5 ovdje, i onda što sam stavio ovdje dolje? Sada sam zapravo bi spustio jedan za veličinu, i sada stog je veličine jedan. Što ako sam ići naprijed i umetnuti broj, recimo, sedam sljedeći? To onda dobiva obnovljeno za dva, a onda ćemo napraviti 9, a onda se dobiva obnovljeno do 3. No, zanimljiva je značajka sada ove stog je da Trebao sam to maknuti element koji, ako želim pop nešto izvan dimnjaka, da se tako izrazim? 9 će biti prva stvar ići. Kako bi se slika promijeniti ako želim pop element izvan dimnjaka, volio ladicu u Mather? Da. >> [Studentski] Set veličina za dva. Točno, sve sam učiniti je postaviti veličinu 2, i što da radim s nizom? Nemam ništa učiniti. Mogao bih, samo da bi se analni, staviti 0 tamo ili -1 ili nešto da označi da to nije čitljiv vrijednost, ali to ne smeta jer Ja mogu snimati izvan polja sama koliko je to tako da znam samo pogledate prva dva elementa u ovom polju. Sada, ako odem i dodati broj 8 na ovom polju, kako se slika promijeniti sljedeće? To postaje 8, a to postaje tri. Ja sam rezanje nekoliko ugla ovdje. Sada imamo pet, sedam, osam, a mi smo se vratili na veličinu tri. To je prilično jednostavan za implementaciju, ali kad ćemo požaliti ovaj dizajn odluku? Kada stvari počnu ići jako, jako krivo? Da. [Nečujno učenik odgovor] Kada želite vratiti i dobiti prvi element ste stavili u. 

Ispada ovdje iako stog je niz ispod haube, ove strukture podataka koje smo počeli govoriti o također su općenito poznat kao apstraktne strukture podataka kojim kako oni provode potpuno je osim točke. Struktura podataka kao stog je trebao dodati podršku Operacije poput pritiskom, koji gura u ladicu na stog, i pop, koji uklanja element iz dimnjaka, i to je to. Ako ste bili na preuzimanje tuđe kôd koji se već provodi ova stvar zove snop, ta osoba bi napisao samo dvije funkcije za vas, gurati i pop, čiji je jedini cilj u životu bi učiniti upravo to. Vi ili njega ili nju koji provodi taj program bi bio u potpunosti jednom odlučiti kako će provesti semantika guranje i iskakanje ispod haube ili funkcionalnost guranje i iskakanje. I ja sam napravio nešto kratkovidan odluku ovdje provođenjem moj snop s ovom jednostavnom strukturom podataka zašto? Kada se ovaj pauzu struktura podataka? U kojoj točki moram se vratiti na pogrešku kada korisnik traži pritisak, na primjer? [Studentski] Ako nema više prostora. Točno, ako nema više prostora, ako sam premašio kapacitet, što je sve kape, jer to sugerira da je to neka vrsta globalne konstante. Pa, onda sam samo ću reći, "Žao mi je, ne mogu gurnuti još jednu vrijednost na dimnjak, "volio u Mather. 

U nekom trenutku, oni će pogoditi gornji dio tog malog kabineta. Nema više prostora ili kapaciteta u snopu, u kojem trenutku postoji neka vrsta pogreške. Oni moraju staviti element negdje drugdje, pladanj negdje drugdje, ili nigdje na sve. Sada, s red, mogli bismo provesti ga malo drugačije. Red je malo drugačije u da se ispod haube, to može biti implementiran kao polje, ali zašto, u ovom slučaju, ja predlaganje da imaju glavu elementa koji predstavlja glavu na popisu, Prednji dio popisa, prva osoba u redu u Apple trgovini, osim veličine? Zašto trebam dodatni dio podataka ovdje? Sjetite se što je broj ako sam nacrtana je kako slijedi. Pretpostavimo da je to sada red umjesto stog, razlika se, baš kao što su Apple store-red je pošteno. Prva osoba u redu na početku popisa, broj 5, u ovom slučaju, on ili ona će se pustiti u trgovini na prvom mjestu. Ajmo to učiniti. Pretpostavimo da je to stanje mog red u ovom trenutku u vremenu, a sada Apple store otvara i prva osoba, broj 5, je vodio u trgovini. Kako mogu promijeniti sliku sada da sam de-čekanje prvu osobu na ispred linije? Što je to? >> [Student] Promjena red. Promjena glavu, pa pet nestaje. U stvarnosti, to je kao da-kako najbolje to učiniti? U stvarnosti, to je kao da taj čovjek nestane. Što bi broj 7 učiniti u stvarnoj trgovini? Oni bi veliki korak naprijed. 

No, ono što smo došli da cijenimo kada je u pitanju polja i premještati okolo stvari? To je vrsta otpada svoje vrijeme, zar ne? Zašto moraš biti tako analni kao da imaju prvu osobu na početku linije na fizički početku komad memorije? To je potpuno nepotrebno. Zašto? Što sam mogao samo sjetiti umjesto toga? >> [Nečujno učenik odgovor] Točno, samo sam se mogao sjetiti s ovim dodatnim podacima član glave da je sada na čelu popisa više nije 0, što je bio trenutak prije. Sada je zapravo broj 1. Na taj način, JA dobiti blagi optimizaciju. Samo zato što sam de-čekanje nekoga od linije na početku linije na Apple Store ne znači da svatko ima pomak, koji je opoziv linearna operacija. Ja umjesto toga može provesti stalnu vrijeme samo i postići onda puno brži odgovor. Ali cijena plaćam je ono što se dobije taj dodatni rad a ne da se pomaknuti sve? Da. >> [Nečujno učenik odgovor] Mogu dodati više ljudi, dobro, to je problem ortogonalna na činjenicu da nismo pomicanja ljude oko sebe. To je još uvijek polje, pa da li ili ne možemo pomaknuti sve ili ne- oh, vidim ono što misliš, ok. Zapravo, slažem se s onim što si rekao u da je to gotovo kao da mi smo sada nikada neće koristiti početak ovog niza više jer ako sam ukloniti pet, onda sam ukloniti sedam. Ali ja sam samo staviti ljude na desno. 

To se osjeća kao da sam gubit prostor, i na kraju moj red dezintegrira u ništa at svi, tako da smo samo mogli imati ljudi spustili, i da bismo mogli razmišljati o tom obilju stvarno kao neka vrsta kružnog strukture, ali mi koristimo što operator u C učiniti takvo spustili? [Nečujno učenik odgovor] >> modulo operator. To bi bilo malo neugodno razmisliti kako ćete učiniti na spustili, ali možemo to učiniti, i da bismo mogli početi stavljanjem ljude na ono što je nekad bila ispred linije, ali mi samo sjetiti s ovim glave varijable koji je stvarni šef liniji zapravo je. Što ako, umjesto toga, naš cilj u konačnici, ipak, je potražiti brojeve, kao što smo učinili ovdje na pozornici s Anita, ali mi stvarno želite najbolje od svih tih svjetova? Želimo više sofisticiranosti nego niz dopušta jer želimo sposobnost dinamički raste strukturu podataka. No, mi ne želimo da morati posegnuti za nečim što smo istaknuli u prvom predavanju nije bio optimalan algoritam, da linearnog pretraživanja. Ispada da možete, u stvari, postigla ili barem blizu stalnom vrijeme, pri čemu netko poput Anita, ako ona konfigurira joj strukturu podataka neće biti povezana lista, ne biti stog, da ne bude red, mogao, u stvari, dolazi do strukture podataka koji omogućuje joj da izgleda gore stvari, čak i riječi, a ne samo brojevi, u kojoj ćemo pozvati stalnu vremena. 

A u stvari, gleda naprijed, jedan od psets u ovoj klasi je gotovo uvijek provedba provjere pravopisa, kojim mi vam dati opet neke 150.000 engleskih riječi, a cilj je da učitavanje onima u memoriju i brzo biti u mogućnosti odgovoriti na pitanja u obrascu je ova riječ ispravno napisane? I to bi stvarno sisati ako ste morali ponoviti kroz sve 150.000 riječima odgovoriti. Ali, u stvari, vidjet ćemo što možemo učiniti u vrlo, vrlo kratkom vremenu. I to će uključivati ​​provedbene nešto što se zove hash tablicu, i iako na prvi pogled ova stvar zove hash tablicu će se neka nam se postigla ove super brzi odgovor puta, Ispada da je u stvari problem. Kada dođe vrijeme za provedbu ovu stvar zvanu-opet, ja ću to opet. Ja sam jedini ovdje. Kad je u pitanju vrijeme za provedbu ovu stvar zove hash tablicu, ćemo morati donijeti odluku. Koliki bi ova stvar zapravo biti? A kad počnemo umetanje brojeva u ovom hash tablicu, kako ćemo ih pohraniti na takav način da ih možemo dobiti natrag kao brzo kao što smo ih dobili u? No, vidjet ćemo još mnogo prije nego što je to pitanje od kada svačija rođendan je u razredu će biti vrlo povezan. Ispada da je u ovoj sobi, imamo nekoliko stotina ljudi, pa su izgledi da nas dvoje imaju isti rođendan je vjerojatno prilično visoka. Što ako je bilo samo 40 od ​​nas u ovoj sobi? Kakvi su izgledi za dvije osobe imaju isti rođendan? [Studenti] Preko 50%. Da, preko 50%. U stvari, čak sam donio grafikona. Ispada, a to je zapravo samo doušnik pregled- ako postoji samo 58 od nas u ovoj sobi, vjerojatnost dvije od nas imaju isti rođendan je iznimno visoka, gotovo 100%, i da će izazvati hrpu ozlijeđen za nas u srijedu. 

Sa taj je rekao, hajdemo odgoditi ovdje. Vidimo se u srijedu. [Pljesak] [CS50.TV]