[Glazbom] SPEAKER 1: U redu. Svatko dobrodošli natrag u odjeljku. Nadam se da su svi uspješno oporavio od kviza od prošlog tjedna. Znam da je malo luda vremena na vrijeme. Kao što sam rekao prije, ako ste unutar standardne devijacije, stvarno ne brinite o tome, pogotovo za manje udoban dijelu. To je otprilike gdje bi trebali biti. Ako jeste super, onda super. Čast da vas. A ako se osjećate kao da je potrebno malo više pomoći, molimo slobodno doći na bilo koji od TFS. Svi smo ovdje da vam pomognemo. 

Zato učimo. Zato sam ovdje svaki ponedjeljak za vas momci i na uredu sati četvrtkom. Dakle, slobodno javite mi Ako ste zabrinuti o bilo čemu ili ako postoji išta na kvizu da li stvarno želite baviti. 

Dakle, program za danas je sve o strukturama podataka. Neki od njih su samo će biti samo da bi ste upoznati s tim. Ne smijete nikada provoditi oni u ovoj klasi. Neki od njih ćete, kao što je za svoj bukvar pset. 

Vi ćete imati svoj izbor između hash tablica i pokušaja. Tako smo definitivno ćemo se ide preko njih. To će biti definitivno više vrsta od razine dijelu visokog danas, ipak, jer postoji puno njih, a ako smo išli u detalje provedbe na sve to, mi ne bi čak i dobiti kroz povezanim popisima i možda malo hash tablica. 

Dakle nose sa mnom. Nećemo se radi koliko kodiranja ovaj put. Ako imate bilo kakvih pitanja o tome ili ako želite vidjeti provodi ili ga isprobali, Ja svakako preporučujemo će study.cs50.net, koji ima primjera sve to. To će imati svoje PowerPoints s bilješkama koje smo imaju tendenciju da koriste kao neki programiranje vježbe, pogotovo za stvari kao što povezanim popisima i binarnom drveće hrpe i mehanizme. Pa malo više na visokoj razini, što može biti lijepo za vas dečki. 

Dakle, s tim ćemo početi. I također, yes-- kvizova. Mislim da većina vas koji su u moj poglavlje ima svoje kvizove, ali tko dolazi u ili nekog razloga ne, oni su upravo ovdje u prednjem. 

Tako povezane liste. Znam ovu vrstu ide Sigurnosno prije kviza. To je bilo prije tjedan dana koje smo naučili o tome. No, u ovom slučaju, samo ćemo idu malo više u dubinu. 

Pa zašto bismo mogli odabrati povezani popis preko niza? Ono što ih razlikuje? Da? 

PUBLIKA: možete proširiti povezan popis u odnosu na niz je fiksne veličine. SPEAKER 1: Točno. Niz je fiksna veličina, dok povezani popis ima promjenjivu veličinu. Dakle, ako ne znamo kako koliko želimo pohraniti, Popis povezani daje nam velika način da to učinite, jer možemo samo dodaj na drugom čvoru i dodati na još jedan čvor i dodati na drugom čvoru. No, ono što bi moglo biti trade-off? Se bilo tko sjetiti trade-off između polja i povezane liste? Mmhmm? 

PUBLIKA: Morate proći kroz sve način po popisu povezan naći element u popisu. U nizu, možete samo pronaći element. 

SPEAKER 1: Točno. Tako je s arrays-- 

PUBLIKA: [nečujan]. 

SPEAKER 1: S polja, imamo ono što se naziva izravnim pristupom. Znači da, ako želimo ono što je ikada peta točka popisa ili peta točka našeg polje, mi samo možemo ga zgrabiti. Ako je popis povezani, imamo za prolazak kroz, zar ne? Dakle, pristup element u Niz je konstanta vrijeme, dok je s popisa povezan To bi najvjerojatnije biti linearno vrijeme, jer možda naš element je sve na kraju. Moramo tražiti kroz sve. Dakle, sa svim tim podacima strukture idemo treba provesti malo više vremena na, što su plusa i negative. Kad možda želimo koristiti jedan nad drugim? I to je vrsta veća stvar oduzeti. 

Tako imamo ovdje definicija čvora. To je kao jedan element u naš popis povezani, zar ne? Tako smo svi upoznati s našim typedef konstrukt, koji smo otišli više u pregledu prošli put. To je zapravo samo stvaranje druga vrsta podataka koje smo mogli koristiti. 

I u ovom slučaju, to je neki čvor koje će održati neki broj u. I što onda je drugi dio ovdje? Svatko? 

PUBLIKA: [nečujan]. 

SPEAKER 1: Da. To je kazaljka na sljedeći čvor. Dakle, to bi zapravo trebao biti ovdje. To je pokazivač tipa čvor na sljedeću stvar. I to je ono što oni obuhvaća naše čvor. Cool. 

U redu, u potrazi, kao što smo bili Upravo govoreći prije ruke, ako ste ide pretraživanje, morate se zapravo ponoviti kroz popis povezane. Dakle, ako smo u potrazi za broj 9, mi bi početi u našoj glavi i to nas upućuje na početku našeg popisa povezani, zar ne? A mi kažemo, u redu, to čini čvor sadrže broj 9? Ne? 

U redu, idite na sljedeću. Slijedite ga. Sadrži li broj 9? Ne. Slijedite sljedeći. 

Dakle, moramo se zapravo ponoviti kroz naše liste povezane. Ne možemo samo ići izravno na kojoj 9. A ako ti dečki zapravo žele vidjeti neke pseudo-koda tamo gore. Imamo neku funkciju pretraživanja ovdje koji traje in-- ono što je potrebno u? Što ti misliš? Tako lako. Što je ovo? PUBLIKA: [nečujan]. SPEAKER 1: Broj tražimo. Pravo? A što bi to odgovarati? To je pokazivač? 

PUBLIKA: čvor. 

SPEAKER 1: čvor na popis da gledamo, zar ne? Dakle, imamo neke čvorovi su kazaljke ovdje. To je točka koja će se zapravo ponoviti kroz naše liste. Mi ga postaviti jednaka popis jer to je samo postavljanje je jednaka početak našeg popisa povezane. 

I dok to nije NULL, dok je još uvijek imamo stvari u našem listu, provjerite je li taj čvor ima Broj tražimo. Povratak istina. Inače, ažurirati ga, zar ne? 

Ako je NULL, izađemo iz naše while petlja i povratak lažna jer to znači da nismo ga pronašli. Da li su svi dobili kako se to radi? U redu. 

Tako je s umetanja, što imaju tri različita načina. Možete prepend, možete dodati i možete umetnuti u ponekog. U ovom slučaju, mi smo će napraviti prepend. Se bilo tko znati kako one tri slučaja mogao razlikovati? 

Tako prepend znači da ste stavili je na prednjoj strani popisa. Dakle, to bi značilo da bez obzira što je vaš čvor je, bez obzira na što je vrijednost, idete da ga upravo ovdje ispred, u redu? To će biti prvi element u svoj popis. 

Ako ga dodati, to će ići na stražnjoj strani popisa. I umetnuti u ponekog znači da ste će staviti stvari na mjesto gdje se čuva vaš popis povezani razvrstani. Opet, kako se koristiti one i kada koristite njih će varirati ovisno o vašem slučaju. Ako to ne treba biti razvrstani, prepend teži da bude ono što većina ljudi koristiti, jer vi ne moraju proći kroz cijeli popis pronaći kraj da ga dodati na, zar ne? Vi samo možete ga staviti u pravu. 

Tako ćemo proći Umetanje 1 upravo sada. Dakle, jedna stvar koju ću Preporučujemo na ovoj pset je izvući stvari, kao i uvijek. To je vrlo važno da ažurirate svoje naputke u ispravnom redoslijedu jer ako ih ažurirati malo izvan reda, ti ćeš završiti gubi dijelove svog popisa. 

Tako na primjer, u ovom slučaju, mi smo govoreći glavu na samo točka na 1. Ako mi samo to bez spremanja ovaj 1, nemamo pojma što 1. treba ukazati sada jer smo izgubili ono što Glava je ukazao na. Dakle, jedna stvar koju treba zapamtiti kada radite prepend je spasiti što se glava ukazuje na prvom, zatim ga preraspodijeliti, a zatim ažurirati što je vaš novi čvor trebao ukazati. U ovom slučaju, to je jedan od načina da to učinite. 

Dakle, ako smo to učinili na taj način gdje smo samo rasporediti glavu, gubimo osnovi našu stranicu cijeli popis, zar ne? Jedan od načina da to učinite je da se 1 bod za Sljedeći, a zatim su glave točku na 1. Ili možete učiniti vrsta kao privremenog skladištenja, što sam govorio o tome. 

Ali prenamjene vaš upućuje u ispravnom redoslijedu će biti vrlo, vrlo važno za ovaj pset. Inače, ti ćeš imati mljeveno meso tablice ili pokušati to samo će biti samo dio riječi koje Želite a zatim you're-- mmhmm? PUBLIKA: Što je privremena pohranu stvar koju su razgovarali? SPEAKER 1: privremeno skladištenje. Tako je u osnovi jedan način na koji možete to učiniti je pohraniti glavu nešto, kao što su pohraniti ga na privremenu varijablu. Dodijeliti na 1 i zatim ažurirati 1 do točke što god glava koristi ukazati. Na taj način je očito više elegantan, jer vas ne trebaju privremenu vrijednost, ali Upravo nudi još jedan način da to učinite. A mi zapravo nemamo neki kod za to. Tako povezani popisu, mi zapravo imaju neki kod. Dakle stavite ovdje, ovo je prepending. Dakle, ovaj ga ulazi u glavu. 

Dakle, prva stvar koju trebate stvoriti novi čvor, naravno, i provjerite NULL. Uvijek dobro. A onda morate dodijeliti vrijednosti. Kad god stvoriti novi čvor, te ne znam što to pokazuje na sljedeći, tako da ga želite inicijalizirati na nulu. Ako to ne završiti upućuje na nešto drugo, ona dobiva rasporediti i to je u redu. Ako je to prva stvar na popisu, to treba ukazati na nulu, jer to je kraj popisa. 

Pa onda da ga ubacite, vidimo ovdje pripisuju sljedeći vrijednost našeg čvora da se sve što je glava, što je ono što smo imali ovdje. To je ono što smo mi napravili. A onda smo dodjeljivanje glave do točke na naš novi čvor, jer zapamtite, Novi je neki pointer na čvoru, i to je upravo ono što je glava. To je upravo razlog zašto smo ima tu strelicu Accessor. Cool? Mmhmm? 

PUBLIKA: Moramo li inicijalizirati nove Dalje da NULL prvi, ili možemo samo ga resetirali na glavu? 

SPEAKER 1: Novi iduće treba biti NULL za početak jer ne znate gdje će biti. Također, ova je vrsta Baš kao paradigmu. Možete ga postaviti jednak NULL samo da bi sigurni da su svi vaši kladionica prije nego što učinite bilo preraspodjelu tako da ti si uvijek zajamčeno da će se ukazuje na određenu vrijednost u odnosu poput vrijednosti smeća. Jer, da, mi dodijeliti Novi iduće automatski, ali to je više kao dobra praksa za inicijalizaciju na taj način, a zatim preraspodijeliti. 

U redu, tako da dvostruko povezani popisi sada. Što mi mislimo? Ono što je drugačije s dvostruko povezani liste? 

Dakle, u našim povezanim popisima, možemo pomicati samo u jednom smjeru, zar ne? Imamo samo sljedeći. Možemo samo ići naprijed. 

S popisa dvostruko povezana, možemo pomaknuti unatrag. Dakle, imamo ne samo broj koji želimo pohraniti, imamo gdje se ukazuje na sljedeći i gdje smo upravo došli. Dakle, to omogućuje neki bolji obuhvaćanje. 

Dakle, dvostruko povezani čvorovi, Vrlo slično, zar ne? Jedina razlika je sad imaju sljedeća i prethodna. To je jedina razlika. 

Dakle, ako bismo prepend ili append-- smo nemaju kod za ovo gore here-- ali ako ste bili pokušati umetnite ga, važnu stvar je li potrebno napraviti jeste li dodjeljivanje i svoje prethodne i vaši Sljedeći pokazivač ispravno. Dakle, u ovom slučaju, što bi ne samo inicijalizirati iduće, što inicijalizirati prethodna. Ako smo na čelu popisa, mi bi ne samo glava jednaka nova, ali naš novi prethodna trebao ukazuju na glavu, zar ne? 

To je jedina razlika. A ako želite više prakse s te s povezanim popisima, s umetanje, s brisanjem, s umetkom u assorted popis, molimo provjerite study.cs50.net. Postoji hrpa velikih vježbi. Ja visoko preporučiti ih. Volio bih da smo imali vremena proći kroz njih ali ima puno strukture podataka da se kroz. 

U redu, tako da hash tablice. Ovo je vjerojatno najviše korisne bitni za vaš pset ovdje, jer ti ćeš biti provedbe jednog od njih, ili probati. Volim hash tablice. Oni su prilično cool. 

Tako je u osnovi ono što događa je hash tablicu je kada smo stvarno treba brze umetanje, brisanje i pretraživanje. To su stvari koje smo prioriteta u hash tablici. Oni mogu biti prilično velika, ali kao što ćemo vidjeti pokušaja, postoje stvari koje su mnogo veći. 

Ali u osnovi, sve ljestve stol je hash funkcija da vam kaže što kantu staviti svaki vaših podataka, svaki od svojih elemenata. Jednostavan način da razmišljaju o hash tablicu je da je samo kante stvari, zar ne? Dakle, kada ste sortiranje stvari koje kao prvo slovo svog imena, to je vrsta kao što su hash tablicu. 

Dakle, ako su za skupinu vi je u skupinama tko ime počinje s ovamo, ili tko je rođendan je u siječnju, veljači, ožujku, što god da je učinkovito stvarajući hash tablicu. To je samo stvaranje kante koje li sortirati elemente u tako da možete pronaći ih lakše. Dakle, ovaj put, kada mi je potrebno pronaći jedan od vas, Ja ne moram tražiti kroz svaki od vaših imena. Mogu biti kao, oh, znam da Danielle rođendan je in-- PUBLIKA: --April. Zvučnik 1: travanj. Tako sam gledati u mom travnja kanta, i uz malo sreće, ona će biti samo jedan u postoji i moje vrijeme je bio konstanta u tom smislu, a ako moram gledati kroz cijelu hrpa ljudi, to će potrajati mnogo duže. Dakle, hash tablice su stvarno samo kante. Jednostavan način da misle o njima. 

Dakle, vrlo važna stvar o hash tablica hash funkcija. Dakle, ono što sam upravo govorio, kao što su Vaše prvo slovo svoje ime ili vaš rođendan mjeseca, To su ideje koje stvarno korelira s hash funkcije. To je samo način odlučivanja koji Bucket ste elementa ide u, u redu? Tako je za ovu pset, možete pogledati prilično mnogo bilo hash funkcija želite. 

Ne moraju biti svoj. Postoje neke stvarno cool one iz ima koji radimo sve vrste lude matematici. A ako želite napraviti svoj spellchecker super brzi, Ja bih svakako gledati u jednu od njih. 

No, tu su i one jednostavne, poput računati zbroj riječi, kao što su svako slovo ima broj. Izračunaj sumu. To određuje kantu. Oni također imaju one lako da su baš kao i svi ovdje, sve B je ovdje. Bilo koji od njih. 

U osnovi, to samo govori što Indeks lepezu svoga elementa treba ići u. Samo odlučivanju bucket-- to je sve hash funkcija. Dakle, ovdje imamo primjer koji je Samo prvo slovo niza da sam samo pričaju. 

Dakle, imate neke mljeveno meso to je samo Prvo slovo vašeg gudački minus A, koji će vam dati neke broj između 0 i 25. A ono što želite učiniti je pobrinite se da to predstavlja veličina vašeg mljeveno meso table-- koliko kante postoje. Uz mnoge od tih hash funkcije, oni su će se vraćaju vrijednosti koje bi moglo biti daleko iznad broja kante da zapravo imaju u svom hash tablici, tako da je potrebno napraviti je li i mod oni. Inače, to će reći, Oh, to bi trebalo biti u kantu 5000 ali imate samo 30 kante u vašem hash tablici. I naravno, svi znamo da je će rezultirati u nekim ludim pogreške. Dakle, pobrinite se da mod po veličina vašeg hash tablice. Cool. Tako sudara. Je li sve dobro do sada? Mmhmm? 

PUBLIKA: Zašto bi povratak takav masivan vrijednost? 

SPEAKER 1: Ovisno o algoritmu da je vaš hash funkcija koristi. Neki od njih će učiniti luda množenja. I to je sve o uzimajući čak i distribucije, pa oni su neki stvarno lude stvari ponekad. To je sve. Bilo što drugo? U redu. 

Tako sudara. Uglavnom, kao što sam rekao ranije, U najboljem slučaju, bilo kantu gledam je će imati jednu stvar, tako da ne moram gledati na sve, zar ne? Ja ni znati da je tamo ili je to ne, i to je ono što stvarno želite. Ali ako imamo na desetke tisuća Točke podataka i manje od tog broja žlica, ćemo imati sudari gdje na kraju nesto će morati završiti u Kanta koja već ima jedan element. 

Dakle, pitanje je, što radimo u tom slučaju? Što nam je činiti? Mi već imamo nešto tamo? Nemojte mi samo ga izbaciti? 

Ne. Moramo zadržati obojicu. Dakle, način na koji smo obično to je ono? Kakva je struktura podataka samo smo razgovarali o tome? PUBLIKA: Vezana lista. SPEAKER 1: Popis povezani. Tako sada, umjesto da svaki od njih kante samo ima jedan element, to će sadržavati povezano popis elementi koji su raspršene u nju. OK, ne svi vrsta dobiti tu ideju? Budući da nismo mogli imati niz jer mi ne znamo kako mnoge stvari će biti tamo. Popis povezani omogućuje nam da imaju samo točan broj koji su raspršene u tu kantu, zar ne? 

Dakle linearno sondiranja je osnovi to idea-- to je jedan od načina da se bave sudara. Ono što možete učiniti je li, u ovom Slučaj, bobica je raspršen u 1 a već imamo nešto postoji, samo zadržati ide prema dolje dok nađete prazan utor. To je jedan od načina da ga obrađuju. Drugi način da obrađuju što je s onim što smo upravo called-- povezan Popis naziva ulančavanje. 

Dakle, ova ideja funkcionira, ako Vaš hash tablicu mislite je mnogo veći od Vaši podaci postaviti ili ako vas želite probati i minimizirati ulančavanje dok je to neophodno. Dakle, jedna stvar je linearna sondiranja očito znači da je vaš hash funkcije nije baš tako korisna jer ćeš završiti pomoću Vaš hash funkcija, uzimajući do točke, što Linearna probe do neko mjesto koje je na raspolaganju. Ali sada, naravno, ništa ostalo što se završava tamo, ti si idući u morati traži još dalje. 

A tu je puno više Rashodi za pretraživanje koji ide u unos element u svom hash tablicu sada, zar ne? I sada kada idete i pokušati naći bobica opet, ti ćeš ga hash, a to će reći: oh, gledati u kantu 1, i to neće biti u kantu 1, tako da ste će morati proći kroz ostatak njih. Tako da je ponekad korisno, a u većini slučajeva, ćemo reći da ulančavanje je ono što želite učiniti. 

Tako smo razgovarali o tome i ranije. Imam malo ispred sebe. Ali ulančavanje je u osnovi da svaka kanta u vašem hash tablici je samo popis povezani. 

Dakle drugi način, ili više tehničkih način, razmišljati o hash tablicu je da je to samo niz povezanih popisima, koji kada pišete svoj rječnik a vi pokušavate učitati, razmišljam o tome kako je niz povezanih popisa učinit će to puno lakše za vas pokrenuti. 

PUBLIKA: Pa hash tablicu ima unaprijed određenu veličinu, kao [nečujan] iz kante? 

SPEAKER 1: Točno. Tako da ima određeni broj kante koje determine-- koji ti dečki trebali slobodno igrati. To može biti prilično cool da vidi što se događa kao što promijeniti svoj broj kante. Ali da, to je postaviti broj kante. Ono što vam omogućuje da stane kao mnogi elementi kao što je potrebno je to zasebna ulančavanje gdje vas su povezane liste u svakoj ćeliji. To znači da svoj hash tablicu će biti točno veličine da to treba biti, zar ne? To je cijela točka povezanih liste. Cool. 

Dakle, svatko ima redu? U redu. Ah. Što se upravo dogodilo? Stvarno je sada. Pogodite netko me ubija. 

OK ćemo ići u pokušaja, koji su malo ludi. Volim hash tablice. Mislim da su stvarno cool. Pokušava su cool, previše. 

Tako se bilo tko sjetiti što je probati? Trebali su otišli preko je kratko predavanje? Sjećate li se takav kako se to radi? PUBLIKA: Ja sam samo površno da smo išli preko njega. SPEAKER 1: Mi ne idu preko njega. U redu, mi stvarno ćemo ići preko njega je ono što govoriš. 

PUBLIKA: To je za dohvat stabla. 

SPEAKER 1: Da. To je pronalaženje stablo. Strašan. Dakle, jedna stvar za primijetiti je da smo gleda na pojedine likove ovdje, zar ne? 

Dakle, prije nego s našim hash funkcije, mi gledali riječi u cjelini, a sada tražimo više na likove, zar ne? Dakle, imamo Maxwell ovamo i Mendel. Tako je u osnovi try-- način razmišljanja je o tome da je svaka razina ovdje je niz pisama. Dakle, ovo je vaša root čvor ovdje, zar ne? To je sve likove abeceda za početak svaku riječ. 

A ono što želite učiniti je recimo, u redu, imamo neke M riječ. Idemo tražiti Maxwell, tako idemo na M. i M poena na cijeli Drugi niz u kojem svaki riječi, dok god postoji je riječ koja ima kao drugo slovo, dok god postoji riječ koja ima B kao drugi pismu, to će imati pokazivač ide na neki sljedeći niz. 

Tu je vjerojatno nije Riječ koja MP nešto, pa na P položaju u to polje, to će samo biti NULL. To će reći, u redu, ne postoji riječ da je M slijedi P, u redu? Dakle, ako mislimo o tome, svaku jedan od tih manjih stvari zapravo je jedan od tih velika polja od A do Z. Dakle, što bi moglo biti jedna od stvari to je vrsta carine probati? 

PUBLIKA: puno memorije. 

SPEAKER 1: To je tonu memorije, zar ne? Svaki od tih blokova ovdje predstavlja 26 mjesta, 26 elementa niz. Tako pokušava dobiti nevjerojatno prostor teška. 

No, oni su vrlo brzo. Dakle, nevjerojatno brzo, ali stvarno prostor neučinkovita. Vrsta moraju shvatiti iz koje želite. To su stvarno super za vaše pset, ali oni ne zauzimaju puno memorije, tako da se trgovina off. Da? 

PUBLIKA: Bi li bilo moguće postaviti probati, a zatim nakon što su svi podaci u njemu da need-- Ne znam je li to bi imalo smisla. Bio sam uzimajući osloboditi od svega NULL likovi, ali onda da ne bi bio u stanju indeks them-- 

SPEAKER 1: Još uvijek ih je potrebno. 

PUBLIKA: - na isti način svaki put. SPEAKER 1: Da. Morate se nulta znakove pustiti znaš ako nije riječ tamo. Ben si imate nešto što želite? U redu. U redu, idemo ići malo više u tehničke detalje iza probati i raditi kroz primjer. 

U redu, tako da je to ista stvar. Dok je u popisu povezane, naš glavni vrsta of-- što je riječ želim? - kao što je izgradnja blok bio čvor. U pokušaju, imamo i čvor, ali je definirana drugačije. 

Dakle, imamo neke bool da predstavlja li riječ zapravo postoji na ovom mjestu, a zatim imamo neku niz here-- odnosno, ovo je pokazivač Niz od 27 znakova. A to je za, u ovom slučaju, to 27-- Siguran sam da ste svi kao, čekaj, ima 26 slova abecede. Zašto imamo 27? 

Dakle, ovisno o Način na koji provesti ovo, To je od pset da dopušteno za apostrofe. Pa to je zato dodatni jedan. Također ćete imati u nekim slučajevi null terminator uključen kao jedan od likovi koji to smiju biti, a to je kako su provjeriti je li to kraj riječi. Ako ste zainteresirani, check out Kevin video na study.cs50, kao i Wikipedia ima neke dobre resurse tamo. 

Ali ćemo proći samo vrsta kako biste mogli raditi kroz probati ako si dao jedan. Dakle, imamo super jednostavan jedan ovdje ima riječi "palicu" i "zoom" u njima. I kao što vidimo ovdje, ovaj mali prostor ovdje predstavlja našu bool da kaže, da, ovo je riječ. A onda ovaj je naš nizovi znakova, zar ne? 

Tako ćemo proći pronalaženje "šišmiša" u tom pokušaju. Dakle, početi na vrhu, zar ne? A mi znamo da je b odgovara Drugi indeks, drugi element U ovom nizu, jer i b. Tako otprilike drugi. 

I to kaže, OK, super, proizlazi da se u Sljedeći niz, jer ako se sjetimo, to ne znači da je svaki od tih zapravo sadrži element. Svaki od tih polja sadrži pokazivač, zar ne? To je važna razlika napraviti. 

Znam da će ovo be-- pokušava se stvarno je teško dobiti na prvi put, pa čak i ako je to drugi ili treći put i to je još uvijek vrsta od činilo teško, Obećajem, ako idete gledati Ukratko ponovno sutra, vjerojatno će napraviti puno više smisla. Potrebno je mnogo da probaviti. Ja još uvijek ponekad sam kao, čekaj, što je probati? Kako koristiti ovaj? 

Tako smo b u ovom slučaju, što je naš drugi indeks. Ako smo imali, recimo, c ili d ili bilo koji drugi pismo, moramo mapirati taj leđa indeksa našeg polja da to odgovara. Dakle, mi bi kao rchar a mi samo oduzmite off to preslikati na 0-25. Svi su dobri koliko smo mi map naše znakove? U redu. 

Dakle, idemo na drugom i mi vidim da, da, to je da ne NULL. Možemo prijeći na ovom sljedeći niz. Dakle, idemo na ovom sljedeći niz ovdje. 

A mi kažemo, OK, sada smo trebate vidjeti ako je ovdje. Je null ili to radi zapravo krenuti naprijed? Tako zapravo kreće proslijediti u ovom nizu. A mi kažemo, u redu, t je naš zadnji pismo. Dakle, idemo na t na indeksu. A onda ćemo krenuti naprijed jer ima još jedan. A to se kaže da je u osnovi, da, ona kaže da je riječ here-- da ako slijedite ovaj put, došli ste u riječi, što znamo da je "šišmiša". Da? 

PUBLIKA: Je li standardni da se taj kao što je indeks 0, a zatim imaju neku vrstu na 1 ili da su na kraju? 

SPEAKER 1: Ne Dakle, ako se osvrnemo na našem Deklaracija ovdje, to je bool, tako da je njezin vlastiti element u vašem čvor. Dakle, to nije dio polja. Cool. Dakle, kada smo završili našu riječ, a mi smo na ovom polju, ono što želite učiniti je napraviti provjeru je to riječ. I u ovom slučaju, to će se vratiti da. 

Dakle, na toj bilješci, znamo da je "zoološki vrt" - znamo što je ljude da "zoo" je riječ, zar ne? Ali se probati ovdje bi kažu, ne, to nije. I to bi se reći da je zbog toga mi nisu ga označen kao riječ ovdje. Iako možemo proći do tog niza, to probati bih da, ne, Zoološki vrt nije u svom rječniku jer nemamo je označen kao takav. 

Tako je jedan način da to učinite that-- oh, oprostite, ovo je jedan. Dakle, u ovom slučaju, "zoološki vrt" nije riječi, ali to je u našem pokušaju. No, u tom jednom, reci mi to želimo uvedu riječ "kupka", što će se dogoditi je slijedimo through-- B, A, t. Mi smo u tom nizu, a idemo tražiti h. 

U ovom slučaju, kada se pogledajte pokazivača na sat, to ukazuje na NULL, u redu? Dakle, osim ako je to izričito ukazujući na drugom polju, pretpostavimo da su sve upućuje U tom nizu ukazuju na nulu. Dakle, u ovom slučaju, h se ukazuje na nulu tako da ne možemo ništa učiniti, tako da bi također vratiti netočno, "kupka" nije ovdje. Dakle, sada smo zapravo će proći Kako bismo zapravo reći da je "zoološki vrt" je u našem pokušaju. Kako umetnuti "zoološki vrt" u našem pokušaju? Dakle, na isti način na koji smo započeli naš popis povezani, počinjemo u korijenu. Kada su u nedoumici, započeti u Korijen tih stvari. 

A mi ćemo reći: OK, z. z postoji u tome, a on ne. Tako ste se kreće na Vaš sljedeći niz, u redu? A onda se na sljedeći, kažemo, u redu, ne o postoji? To čini. To opet. 

I tako dalje naš sljedeći smo rekao, U redu, "zoo" već postoji ovdje. Sve što trebate učiniti je postavljena jednaka da istina, da je riječ tamo. Ako ste slijedili sve do prije tog trenutka, to je riječ, pa samo postavljen je jednaka kao. Da? 

PUBLIKA: Tako to radi znači da "ba" je riječ također? 

SPEAKER 1: Ne Dakle, u ovom slučaju, "ba", dobili bismo ovdje, rekli bismo da je riječ, i to će i dalje biti. OK? Mmhmm? 

PUBLIKA: Dakle, nakon što je to riječ i reći da, onda je to sadržavat će ići na m? 

SPEAKER 1: Pa to ima veze with-- ste učitava to. Kažete "zoo" je riječ. Kad idete na check-- kao što su, kažu želiš reći, ne "zoološki vrt" postoje u ovom rječniku? Vi ste samo ide tražiti "zoološki vrt" a zatim provjerite da li je riječ. Nikada nećete premjestiti do m jer to nije ono što tražite. 

Dakle, ako mi zapravo htjeli dodati "kupka" u tom pokušaju, bismo napraviti istu stvar kao što smo učinili s "zoološki vrt" osim bismo vidjeti da kad smo pokušati doći do h, to ne postoji. Dakle, možete misliti kako je to težak dodati novi čvor u popis povezana, tako da bi trebao dodati još jedan jedan od tih polja, kao što je tako. I onda ono što radimo je da samo postavite h element ovog niza upućuju na to. 

I onda ono što bismo htjeli raditi ovdje? Dodaj to jednako vrijedi jer je riječ. Cool. Znam. Pokušava nisu najuzbudljiviji. Vjeruj mi, znam. 

Dakle, jedna stvar je shvatiti s pokušaja, Rekao sam, oni su jako učinkovit. Tako smo vidjeli zauzimaju tona prostora. Oni vrsta zbunjujuće. Pa zašto bi mi ikada koristiti ove? Mi koristimo to, jer oni su nevjerojatno učinkovit. 

Dakle, ako ste ikada tražiš do riječi, vi ste samo Omeđen duljinu riječi. Dakle, ako ste u potrazi za Riječ koja je dužine pet, ti si samo ikada morati bi najviše pet usporedbe, u redu? Dakle, čini to u osnovi konstantna. Poput umetanja i pretraživanja su u osnovi vremenska konstanta. 

Dakle, ako ste ikada može dobiti nešto u stalnom vremenu, to je kao dobar kao Internet dobiva. Ne može bolje od konstanta vrijeme za takve stvari. Tako da je jedan od ogromne pluseve od pokušaja. 

Ali, to je puno prostora. Dakle, vrsta morati odlučiti ono što je važnije za vas. A na današnjim računalima, Prostor koji pokušaj može potrajati Možda ne utječe ste toliko, ali možda imate posla s nečim koji je daleko, daleko više stvari, i pokušati jednostavno nije razumno. Da? 

PUBLIKA: Čekaj, pa imate 26 slova u svakog pojedinca? 

SPEAKER 1: Mmhmm. Da, imate 26. Imate neki je riječ marker i onda imate 26 upućuje na svakoga. I oni point-- 

PUBLIKA: I svaki 26, oni svaki ima 26? 

SPEAKER 1: Da. I zato, kao što možete vidi, ona širi vrlo brzo. U redu. Tako ćemo dobiti u stabala, koja Osjećam se sviđa je lakše i vjerojatno će biti lijepi mali predah od pokušaja tamo. Dakle, nadam se većina vas Vidio stablo prije. Ne sviđa lijepa one izvan, koje sam Ne znam je li itko otišao je nedavno otvorenom. Otišao sam u berbu jabuka, ovaj vikend, i oh moj Bože, bilo je lijepo. Nisam znao lišće moglo izgledati da je lijepa. 

Dakle, ovo je samo stablo, zar ne? To je samo neki čvor, i to ukazuje na hrpu drugih čvorova. Kao što vidite ovdje, ovo je vrsta ponavljajućih temu. Čvorovi ukazuje na čvorove je vrsta suština mnogih struktura podataka. To samo ovisi o tome kako ćemo ih upućuju jedni drugima i kako smo prošli kroz njih i kako smo umetati stvari koje određuje njihove različite karakteristike. 

Dakle, samo su neki terminologiju, što sam se prije. Dakle, korijen je ono što je na samom vrhu. To je mjesto gdje smo uvijek početi. Možete misliti o njemu kao glavi također. Ali za drveće, skloni smo odnosi se na to što je u korijenu. 

Sve u donjem here-- na vrlo, vrlo bottom-- smatraju lišće. Tako to ide zajedno s cijela stabla stvar, zar ne? Listovi su na rubu svog stabla. 

A onda imamo i nekoliko Uvjeti za razgovor o čvorova u odnosu međusobno. Tako imamo roditelja, djeca, braća i sestre. Dakle, u ovom slučaju, 3 roditelj 5, 6 i 7. Dakle, roditelj je ono što je jedan korak naprijed što god da ste pozivajući se, pa samo poput obiteljskog stabla. Nadajmo se, to je sve pomalo malo više intuitivno nego pokušaja. 

Braća i sestre su bilo koje imaju Isto roditelj, zar ne? Oni su na istoj razini ovdje. A onda, kao što sam bio govoreći, djeca su samo sve što je jedan korak u nastavku čvor u pitanju, u redu? Cool. Dakle, binarno stablo. Može li itko nasumice pogađati na jednom od karakteristike binarnom stablu? 

PUBLIKA: Max dva lista. 

SPEAKER 1: Točno. Dakle, max dva lista. Tako je u ovom jednom prije, imali smo tu jednu koji je imao tri, ali u binarnom stablu, imate max dva Djeca po roditelja, zar ne? Postoji još jedan Zanimljivo obilježje. Zna li netko to? Binarno stablo. 

Dakle, binarno stablo će imati sve na the-- ovo nije sorted-- ali u sortirane binarnom stablu, sve na desnoj strani veća od roditelja, i sve na lijevoj manja od roditelja. I to je bio kviz Pitanje prije, pa je dobro znati. Dakle, način na koji smo definirali to, opet, imamo još jedan čvor. To izgleda vrlo slično kao što? Dvostruko 

PUBLIKA: Povezani popisi 

SPEAKER 1: Popis dvostruka povezani, zar ne? Dakle, ako bismo zamijenili ovo uz prethodni i sljedeći, to će biti popis dvostruko povezani. No, u ovom slučaju, mi zapravo ima lijevo i desno i to je to. Inače, to je točno isto. Mi još uvijek imamo element tražiš, a vi samo dvije upućuje ide na sve što je sljedeće. Da, tako binarno pretraživanje stablo. Ako primijetite, sve na ovdje je veći than-- ili je sve odmah da upravo ovdje je veći od svega, Ovdje je manje od. 

Dakle, ako smo bili na pretraživanje ga, trebao izgledati vrlo blizu binarnom pretraživanje ovdje, zar ne? Osim umjesto da gleda na pola polja, samo mi se gleda na bilo lijevo strana ili desna strana stabla. Tako se dobiva malo jednostavnije, mislim. 

Dakle, ako je vaš korijen je NULL, Očito je to samo lažna. A ako je tamo, očito je to istina. Ako je manje od, tražimo lijevu. Ako je veći od, tražimo pravo. To je točno kao binarni pretraživanje, Samo različite strukture podataka da smo putem. Umjesto niza, to je samo binarno stablo. 

U redu, gomila. I također, to izgleda kao mi možda ima malo vremena. Ako to učinimo, ja sam sretna da ide više bilo to opet. U redu, tako da gomila. Se bilo tko sjetiti što stacks-- sve karakteristike stog? 

U redu, tako da većina nas, mislim, jesti u blagovaonicu halls-- koliko smo možda željeli. No, očito, možete misliti na stog doslovno samo kao hrpu pladnjeva ili snop stvari. I ono što je važno shvatiti je da je something-- karakteristika da ga zovu by-- je LIFO. Zna li netko što to znači? Mmhmm? 

PUBLIKA: posljednji u, prvi van. 

SPEAKER 1: Pravo, trajati u, prvi van. Dakle, ako znamo, ako smo slaganje stvari gore, najjednostavnija stvar da zgrabite off-- a možda i jedino što možemo zgrabiti isključiti ako naš stog je velika enough-- je da je vrh elementa. Dakle, sve što je stavljen na last-- kao što vidimo ovdje, god je gurnula na većini recently-- je će biti prvi Ono što mi pući, u redu? 

Dakle, ono što imamo ovdje još jedna typedef struct. Ovo je stvarno baš kao pad tečaja u strukturi podataka, tako da je puno bačena na vas dečki. Znam. Dakle, još jedan struct. Jupi za strukture. 

I u ovom slučaju, to je neki pointer na niz koji ima neki kapacitet. Dakle, to predstavlja našu stog Ovdje, kao i našeg stvarnog niz koja drži naše elemente. A onda ovdje imamo neku veličinu. 

I obično, želite zadržati trag koliko je velik vaš stog jer ono što se događa kako bi se omogućilo što trebate učiniti je, ako znate veličina, to vam reći, OK, ja sam u svojstvu? Mogu li dodati nešto više? I to također govori gdje je vrh stacka tako da znate što vas zapravo može poletjeti. I to je zapravo ide biti malo više jasno ovdje. 

Tako je za guranje, jedna stvar, ako vas ikada provesti gurati, kao što sam rekao, vaš stog ima ograničenu veličinu, zar ne? Naš niz je neki kapacitet. To je niz. To je fiksna veličina, tako da ćemo morati pobrinite se da nećemo više stavljajući u naš niz od nas zapravo imaju prostor za. 

Dakle, kada ste stvaranje gurati funkcija, prva stvar koju trebate učiniti je recimo, u redu, imam prostor u mom stog? Jer ako ne, ispričavam se, Ne mogu spremiti svoj element. Ako radim, onda želite pohraniti je na vrhu dimnjaka, zar ne? 

I to je razlog zašto smo pratiti naše veličine. Ako ne pratiti naše veličine, ne znamo gdje da ga stavi. Mi ne znamo kako mnoge stvari su već naše ponude. Kao i očito postoje načini da možda bi mogao to učiniti. Ti bi mogao inicijalizirati sve na nulu a zatim provjeriti najnovije NULL, ali mnogo lakše stvar je samo reći, OK, pratiti veličine. Kao što ja znam imam četiri elementa u mom nizu, tako da sljedeća stvar koje smo stavili na, mi smo namjeravate pohraniti na indeks 4. I onda, naravno, to znači da je ste uspješno gura nešto na čipova, što žele povećati veličinu tako da znate gdje ste tako da možete gurnuti više stvari dalje. 

Dakle, ako mi pokušavamo pop nešto izvan dimnjaka, što bi moglo biti prva stvar da želimo provjeriti? Pokušavaš uzeti nešto izvan čipova. Jeste li sigurni da postoji nešto u vašem stog? Ne. Pa što bi moglo želimo provjeriti? 

PUBLIKA: [nečujan]. SPEAKER 1: Provjerite veličinu? Veličina. Dakle, želimo provjeriti da li naša veličina je veća od 0, u redu? A ako je, onda želimo smanjiti naša veličina za 0 i povratak to. Zašto? 

U prvoj smo guranje, gurnuo mi na veličinu i zatim obnovljeno veličini. U ovom slučaju, mi smo se smanjuje veličinu a zatim ga polijetanje, to čupanja iz naše ponude. Zašto bismo mogli to učiniti? Dakle, ako ja imam jednu stvar na mom stog, što bi bilo moje veličine u tom trenutku? 1. 

A gdje je element 1 pohranjene? U ono indeks? PUBLIKA: 0. SPEAKER 1: 0. Dakle, u ovom slučaju, mi Uvijek trebate napraviti sure-- umjesto povratka Veličina minus 1, jer mi znamo da je naš element će se čuva na 1 manje bez obzira na naša veličina, to samo se brine o njoj. To je nešto više elegantan način. A mi samo umanjuje našu stranicu Veličina, a zatim se vratiti veličinu. Mmhmm? 

PUBLIKA: Valjda samo u cjelini, zašto bi ova struktura podataka biti koristan? 

SPEAKER 1: To ovisi o vašem kontekstu. Tako da za neke teorije, ako radite with-- redu, daj da vidim postoji li jedan koristan koji je koristan za više od vani CS. S dimnjaka, u bilo koje vrijeme vam je potrebno pratiti nešto što je nedavno dodao je kada idete da želite koristiti hrpu. 

A ja ne mogu misliti na dobro Primjer za to upravo sada. No, kad god najnovije što je najvažnije za vas, to je kad snop će biti korisna. Pokušavam da ako postoji dobar za to. Ako mislim dobar primjer u sljedećoj 20 minuta, ja definitivno će vam reći. 

No sve u svemu, ako postoji nešto, kao što sam rekao većina, gdje je najnovija je najvažnije, da je gdje je snop dolazi u igru. Dok redovima su vrsta suprotno. I svi su mali psi. Nije li to sjajno, zar ne? Osjećam se kao da sam trebao samo imaju zeko videozapis desno u sredini dio za vas dečki jer ovo je intenzivna poglavlje. 

Dakle, red. Uglavnom red je poput linije. Vi Siguran sam da upotreba ove svakodnevice, baš kao u našim blagovaona dvoranama. Dakle, moramo ići u i dobiti naše ladice, ja sam sigurni morate čekati u redu ukrasti ili dobiti hranu. 

Dakle, razlika ovdje je da je to FIFO. Dakle, ako LIFO bio posljednji u prvom out, FIFO je prvi u, prvi van. Dakle, ovo je mjesto gdje god ste stavili na prvom je najvažniji. Dakle, ako ste bili na čekanju u line-- može vas zamislite da ste otišli u ići dobiti novi iPhone i to je bio dimnjak, gdje Posljednja osoba u skladu je dobio prvi, ljudi bi se međusobno ubijaju. 

Dakle FIFO, svi smo dobro upoznati sa u stvarnom svijetu ovdje, i sve to ima veze s zapravo vrsta ponovno cijelu ovu liniju i čekanjem strukturu. Dakle, dok je s stog, moramo gurati i pop. Uz red, imamo Postavi u red i dequeue. Tako u red osnovi znači stavio ga na leđa, i dequeue sredstva potrajati off sprijeda. Tako je naša struktura podataka malo više komplicirano. Imamo drugu stvar za praćenje. 

Dakle, bez glave, to Upravo stog, zar ne? To je ista struktura kao stog. Jedino što sada drugačije je što ima tu glavu, što što mislite će pratiti? 

PUBLIKA: Prvi. 

SPEAKER 1: Pravo, Prva stvar koju smo stavili u. Glava našeg red. Tko je prvi u redu. U redu, pa ako radimo u red. Opet, s bilo kojim od ove strukture podataka, jer smo koja se bavi nizom, moramo provjeriti da li imamo prostora. 

To je vrsta kao što mi govori ti dečki, ako otvorite datoteku, trebate provjeriti null. Uz bilo koji od tih dimnjaka a redovi, trebate da li postoji prostor jer smo bavi fiksnom veličine polja, kao što smo vidjeli here-- 0, 1 sve do 5. Dakle, što nam je činiti u tom slučaju je provjera da li još uvijek imamo prostora. Je li naša veličina manje od kapaciteta? 

Ako je tako, moramo ga pohraniti u rep i ažuriramo našu veličinu. Dakle, što bi rep se u ovom slučaju? To nije izrijekom napisano van. Kako bismo to pohraniti? Što će biti rep? 

Tako ćemo prošetati kroz ovaj primjer. Dakle, ovo je niz veličine 6, zar ne? I mi smo upravo sada, naša veličina je 5. A kad smo ga stavili u, to se događa ići u peti indeksa, zar ne? Dakle pohraniti na repu. 

Drugi način napisati rep bi samo biti naš polje na indeksu veličini, zar ne? To je veličina 5. Sljedeća stvar će ići u 5. Cool? U redu. Ona dobiva nešto složeniji kada počnemo petljaju s glave. Da? 

PUBLIKA: Znači li to da smo bi proglasio niz koji Bio pet elemenata dug i onda mi dodajemo na njega? 

SPEAKER 1: Ne Dakle, u ovom slučaju, to je dimnjak. To će biti proglašen kao niz veličine 6. I u ovom slučaju, mi samo jedno mjesto ulijevo. 

U redu, tako da jedna stvar je u tome slučaj, ako je naša glava je na 0, onda mi samo možemo ga dodati na veličinu. Ali to dobiva malo trickier jer zapravo, oni nemaju slajd za to, pa ću nacrtati jedan, jer to nije vrlo je jednostavno jednom vas početi uzimajući osloboditi od stvari. Dakle, dok je s hrpom imate samo ikada brinuti o tome što je veličina kada dodajete nešto na, uz red također je potrebno napraviti sigurni da je vaša glava činili, jer je super stvar o redovima je da ako niste na kapacitet, što zapravo može učiniti zaokrenuti. 

U redu, tako da jednu stvar oh, ovo je strašno krede. Jedna stvar koju treba uzeti u obzir je slučaj. Samo ćemo napraviti pet. U redu, tako da ćemo kažu glava ovdje. To je 0, 1, 2, 3, 4, 

Glava je tamo, i molimo se stvari u njima. I želimo dodati nešto, zar ne? Dakle, ono što trebamo znam je da je glava uvijek će se premjestiti na taj način i onda povratna petlja oko, u redu? 

Tako je ovaj red ima mjesta, zar ne? To je prostor u samom početku, vrsta suprotno od toga. Dakle, ono što trebamo učiniti je da potrebno je izračunati rep. Ako znate da je vaš Glava nije preselio, rep je samo tvoj niz, na Indeks veličine. 

No, u stvarnosti, ako koristite red, glavu vjerojatno se ažurira. Dakle, ono što trebate učiniti je zapravo izračunati rep. Dakle, ono što mi radimo je ova formula ovdje, što ću vas pustiti Dečki razmišljaju o, i onda ćemo razgovarati o tome. Dakle, to je kapacitet. 

Dakle, to će zapravo vam dati način da to učinite. Budući da u ovom slučaju, što? Naša glava je na 1, naša veličina je 4. Ako mod koji je za 5, dobivamo 0, što je gdje smo trebali ga unijeti. 

Pa onda u sljedećem slučaju, ako smo to učinili, kažemo, u redu, neka je dequeue nešto. Mi dequeue to. Mi se ovaj element, zar ne? 

A sada naša glava pokazuje ovdje, i želimo dodati još jedna stvar. To je u osnovi natrag na našu liniju, zar ne? Redovi može omotati oko polja. To je jedan od glavnih razlika. Hrpe, ne možete to učiniti. 

Uz redova, možete jer sve što je bitno je da znate što je nedavno dodao je. Budući da sve ide kako treba dodati u to lijevi smjer, u ovom slučaju, a zatim zaokrenuti, možete nastavljaju stavljanjem u novim elementima na prednjem dijelu polja jer to zapravo nije Prednji dio niza više. Možete misliti na početak Niz kao gdje ti je glava zapravo jest. 

Dakle, ova formula je kako je izračunati svoj rep. Da li to smisla? U redu. U redu, dequeue, a zatim vi imate 10 minuta mi postavljati pitanja razjasnili želite, jer znam da je lud. 

U redu, tako da u istom way-- Ja ne znam je li vi primijetili, ali CS je sve o obrascima. Stvari su prilično mnogo Isto, samo sa sitnim ugađanje. Dakle, ista stvar ovdje. Moramo provjeriti da li smo zapravo ima nešto u našem redu, zar ne? Recimo, u redu, naš je veličina veća od 0? Cool. 

Ako to učinimo, onda ćemo premjestiti naše glave, što je ono što sam upravo ovdje pokazao. Mi ažurirati svoju glavu da se još jedan. I onda mi umanjuje naše Veličina i vratiti element. 

Tu je puno konkretniji kod na study.cs50.net, i ja visoko preporučiti ide kroz nju, ako imate vremena, čak i ako je samo pseudo-koda. A ako vi želite razgovarati putem da je sa mnom jedan na jedan, javite mi znate. Bio bih sretan da. Strukture podataka, ukoliko uzmete CS 124, vi ćete znam da strukture podataka dobiti vrlo zabavna i to je tek početak. 

Tako da znam da je teško. To je u redu. Mi se bore. I danas je tako. Dakle, ne brinite previše o tome. 

Ali to je u osnovi vaš pad tečaja u strukturama podataka. Znam da je to puno. Postoji li nešto što bismo željeli ići ispočetka? Sve što želimo razgovarati putem? Da? 

PUBLIKA: Na tom primjeru, tako Novi rep je na 0 nad tim? SPEAKER 1: Da. PUBLIKA: U redu. Pa onda prolazi kroz, ne bi se 1 plus 4 or-- 

SPEAKER 1: Znači li rekli, kada želimo ići to učiniti opet? PUBLIKA: Da. Dakle, ako ste bili figuring out-- gdje su što izračuna rep s time što? 

SPEAKER 1: Pa rep Bio in-- sam to mijenja. Dakle, u ovom primjeru ovdje, ovo je bio Niz gledamo, u redu? Dakle, imamo stvari u 1, 2, 3 i 4. Dakle, mi imamo glava jednaka 1 na ovom trenutku, a naša veličina je jednaka 4 u ovom trenutku, zar ne? 

Vi svi se slažu da je to slučaj? Dakle, radimo na glavu plus veličine, što daje nam 5, a onda smo mod za 5. Mi smo dobili 0, što nam govori da je 0 Gdje je naš rep, gdje imamo prostora. 

PUBLIKA: Koja je kapa? 

SPEAKER 1: kapacitet. Oprostite. Tako da je veličina vašeg polja. Da? 

PUBLIKA: [nečujan] prije vraćamo element? 

SPEAKER 1: Tako se krećemo glavu ili vratiti trenutak? Dakle, ako se krećemo jedan, umanjuje veličinu? Držite se. Ja definitivno zaboravio drugu. Nema veze. Ne postoji jedna formula. Da, ti bi htio da se vrate glavu, a zatim ga premjestiti natrag. 

PUBLIKA: OK, jer se na taj točka, glava je bila na 0, a zatim se želite vratiti indeks 0, a zatim bi glavu 1? 

SPEAKER 1: Točno. Mislim da postoji još jedan Formula vrsta kao što je ovaj. Ja ga nemate na vrhu moje glave kao Ne želim da vam krivi jedan. Ali mislim da je savršeno valjana za recimo, u redu, spremite ovaj element-- god Glava je element koji is-- opadanje svoje veličinu, premjestiti glavu iznad i povratak što god to element. To je savršeno valjana. U redu. Osjećam se kao da to nije kao most-- niste će izaći odavde kao, da, znam pokušaja. Sam dobio sve. To je u redu. Obećavam. No, strukture podataka su nešto što je potrebno puno vremena da se navikne. Vjerojatno jedan od najtežih stvari, mislim, u tijeku. 

Dakle, to je definitivno potrebno ponavljanje i gleda at-- I zapravo nije znao povezane liste dok sam previše s njima, na isti način na koji nisam stvarno shvatiti upućuje dok sam ga morao učiti za dvoje godine i to moje vlastite psets s njim. Potrebno je puno vremena i ponavljanja. I na kraju, to će vrsta kliknuti. 

No, u međuvremenu, ako imate kakav od razumijevanja visokoj razini onoga to učiniti, njihovi pro cons-- i što je što mi stvarno imaju tendenciju naglasiti, posebno u intro tijeku. Kao, zašto bi mi koristimo probati preko niza? Kao što su pozitivci i negativa svake od njih? 

I razumijevanje ustupke između svakog od ovih konstrukcija je ono što je puno važnije upravo sada. Tu može biti jedan ludi Pitanje ili dva koji je će vas pitati za provedbu gurati ili provedbu pop ili u red i dequeue. No, za najveći dio, da ima viša razina razumijevanja i više više intuitivno razumijevanje je važniji nego zapravo biti u mogućnosti da ga provede. 

Bilo bi stvarno super ako sve vas mogao izaći i otići provesti probati, ali razumijemo to nije nužno većina razumnih stvar upravo sada. No, možete u svom pset, ako želite da, i onda ćete dobiti praksu, a onda možda ćete stvarno ga razumijem. Da? 

PUBLIKA: U redu, tako da one koje su što znači da se koristi u pset? Trebam li koristiti jedan od njih? SPEAKER 1: Da. Dakle, imate svoj izbor. Mislim da u ovom slučaju, možemo govoriti o pset malo jer sam prošao kroz to. Tako je u svom pset, imate svoj Izbor pokušaja ili hash tablice. Neki ljudi će pokušati i koristiti cvatu filtere, ali oni tehnički nisu točne. Zbog njihove probabilističkoj prirode, daju neistinit ponekad. Oni su super pogled u, iako. Preporučujemo potrazi na njih najmanje. No, imate izbor između hash stol i probati. I to će biti tamo gdje ulažete u svom rječniku. 

A vi ćete morati odabrati Vaš hash funkcija, morate odabrati koliko kante imate, a to će se razlikovati. Kao i ako imate više kante, možda će se izvoditi brže. No, možda ste gubit puno prostora na taj način, iako. Morate to shvatiti. Mmhmm? 

PUBLIKA: Rekli ste prije toga možemo koristiti i druge hash funkcije, da mi ne moramo stvoriti hash funkciju? 

SPEAKER 1: Da, u pravu. Dakle, doslovno za svoj hash funkcije, kao što je google "hash funkcija" i tražiti neke cool one. Ne očekuje se graditi vlastiti hash funkcije. Ljudi troše svoje Teze o tim stvarima. 

Dakle, ne brinite o izgradnji vlastite. Pronađite jedan online za početak. Neki od njih morate manipuliraju malo kako bi bili sigurni tipovi povratak podudaraju i sitnica, pa je u početku, Ja bih preporučio nešto pomoću stvarno lako da možda jednostavno hashes na prvom pismu. I onda nakon što su taj rad, sjedinjavanje hladnije funkciju hash. Mmhmm? 

PUBLIKA: Biste pokušati biti ili učinkovita, ali samo teže, like-- 

SPEAKER 1: Pa pokušaj, mislim, intuitivno je teško provesti ali je vrlo brzo. Međutim, zauzima više prostora. Opet, možete optimizirati i onih u različite načine i postoje načini to-- PUBLIKA: Kako smo polaže na to? Da li to matter-- 

SPEAKER 1: Znači ocjenjuju normalan način. Ti ćeš se polaže na dizajn. Koji god način radite, želite uvjerite se da je kao elegantan kao što može biti te kao učinkovito kao što može biti. Ali, ako se odlučite probati ili mljeveno meso stol, dok to radi, smo sretni s tim. A ako koristite nešto što hashes na prvom pismu, to je u redu, kao što možda kao dizajn-mudar. Mi smo također dosežu točka u ovom semester-- Ja ne znam je li vama Dečki noticed-- ako ste pset razreda odbiti malo zbog dizajna i sitnica, to je savršeno u redu. To je sve do točke u kojoj je vaš Programi su sve složeniji. Postoji više mjesta možete poboljšati. 

Tako da je sasvim normalno. To ne znači da ste radiš gore na vašem pset. To je jednostavno smo se teže na vas sada. Dakle, svatko je to osjećaj. Upravo sam polaže sve svoje psets. Znam da svi to osjećaj. 

Zato nemojte biti zabrinuti zbog toga. A ako imate bilo kakvih pitanja o prethodna psets ili načina na koje možete poboljšati, Pokušavam i komentirati specifične mjestima, ali ponekad je kasno i ja dobiti umorna. Ima li kakvih drugih stvari oko strukture podataka? Siguran sam da ti dečki stvarno ne želim govoriti o njima više, ali ako postoje, ja sam sretan ide preko njih, kao i sve od predavanja ovu prošlom tjedan ili prošli tjedan. 

Znam prošli tjedan je sve pregled, tako da možda smo preskočili neke pregled od predavanja. Ima li još pitanja mogu odgovoriti? U redu, u redu. Pa, ti dečki izaći 15 minuta ranije. 

Nadam se da je to bio polu-korisno barem, i ja ću vas vidjeti dečki sljedeći tjedan, ili četvrtak radno vrijeme. Postoje zahtjevi za grickalice za sljedeći tjedan, to je stvar? Budući da sam zaboravio slatkiše danas. I ja sam donio slatkiše posljednju tjedan, ali to je Columbus Day, tako da su bili poput šest ljudi koji imao četiri vreće slatkiša za sebe. Ja mogu donijeti zvjezdana prašina opet, ako vam se sviđa. Zvjezdana prašina? OK, zvuči dobro. Imati veliki dan, momci.