[Predvaja glasba] 

ANDI PENG: Dobrodošli v 6. tednu oddelka. Oddaljil smo iz našega standarda Čas sekcija torek popoldne na to lepo nedeljo zjutraj. Hvala za vse, ki se mi je pridružila danes, ampak resno, krog aplavz. 

To je kar velik napor. Sem skoraj niti ni uspelo v času, vendar je bilo v redu. Zato vem, da vas vse so jo samo na kvizu. First of all, dobrodošli v druga plat tega. 

Drugič, bomo govorili o tem. O tem bomo govorili v kvizu. Bomo govorili o tem, kako delaš v razredu. Boste v redu. Imam svoje kvize za si na koncu tod tako da, če hočete, da bi poglej na njej, popolnoma v redu. 

Tako hitro, preden začnemo se agenda za danes je, kot sledi. Kot lahko vidite, smo v bistvu hitro streljanje skozi cel kup podatkovnih struktur res, res, res hitro. Tako kot tak ne bo super interactive danes. To bo samo se mi nekako kričali stvari, ki jih, in če sem vas zmedlo, če grem prehitro, povej mi. Oni so samo različne podatke strukture, in kot del vašega pset za to prihajajoči teden, boste morali izvajati enega od njih, morda dve them-- dva od njih V vašem pset. OK, tako da sem le, da bo začeti z nekaj objav. Mi bomo šli čez nizov in čakalnih vrst več v globina od tistega, kar smo storili pred kviz. Mi bomo šli čez povezana Seznam enkrat, še enkrat, bolj poglobljeno kot kaj smo imeli pred kviz. In potem bomo govorili o hash mize, drevesa in poskuša, ki so vsi zelo potrebno za vašo pset. In potem bomo šli čez nekaj koristnih nasvetov za pset5. 

OK, tako kviz 0. Povprečna bil 58%. To je bila zelo nizka, in tako vidva vse naredila zelo, zelo dobro, v skladu s tem. 

Precej, pravilo palca je, če ste v standardni odmik od srednje vrednosti še posebej, ker smo v manj udoben oddelek, ste popolnoma v redu. Si na pravi poti. Življenje je dobro. 

Vem, da je strašljivo, da misliš, da Imam kot 40% na tem kvizu. Grem na neuspeh ta razred. Obljubljam vam, da niste dogaja, da ne razred. Vi ste popolnoma v redu. 

Za tiste med vami, ki je dobil več kot srednja, impresivna, impresivno, kot resno dobro opravljeno. Sem jih imel z mano. Vas prosimo, da pridejo jih dobite Na koncu dela. Dovolite mi, da vem, če imate vprašanja, vprašanja z njimi. Če bomo dodali svoj rezultat narobe, nam to sporočite. 

OK, tako pset5, da je to res čudno teden Yale v smislu da je naša pset zaradi Sreda opoldne vključno pozno dan, tako da je dejansko teoretično zaradi torek opoldne. Verjetno nihče ni končana v torek opoldne. To je povsem v redu. Bomo imeli uradnih ur Nocoj kot tudi v ponedeljek zvečer. In vsi oddelki ta teden bo dejansko spremenila v delavnicah, zato vas prosimo, da v pop vsaka sekcija hočeš, in oni bodo vrste mini-pset Delavnice za pomoč pri tem. Tako kot tak, to je samo odsek kjer smo učno gradivo. Vsi ostali oddelki bodo poudarkom izključno na pomoč za pset. Ja? 

OBČINSTVO: Kje so uradne ure? 

ANDI PENG: Govorilne ure tonight-- oh, dobro vprašanje. Mislim, da uradne ure nocoj so v Teal ali na Commons. Če preverite spletno CS50 in greste na uradnih ur, ne bi smelo biti časovni razpored, ki vas, kjer so vse od njih pove. 

Vem, da nocoj bodisi ali jutri je teal, in mislim, da smo lahko commons za drugo noč. Nisem prepričan. Dobro vprašanje. Preverite na CS50. 

Cool, vsa vprašanja v zvezi z urnik za naslednji kot tri dni? Obljubim vam fantje, kot Davidova je dejal, da je to vrh hriba. Vidva sta skoraj tam. Samo še tri dni. Tja, in potem bomo vsi prišli dol. Bomo imeli lepo CS-premor. Se bomo vrnili. Bomo potopite v spletu načrtovanje in razvoj, Stvari, ki so zelo zabavno primerjavi za nekatere druge psets. In to bo chill, in bomo imeli veliko zabave. Bomo imeli več sladkarij. Žal mi je za sladkarije. Pozabil sem sladkarije. Grobo jutro je bilo. Torej, fantje so skoraj tam, in res sem ponosen na vaju. 

OK, tako nizov. Kdo je ljubil vprašanje o Jacku in njegova oblačila na kvizu? Nihče? OK, da je v redu. 

Torej, v bistvu, kot si lahko slika Jack, ta tip tukaj, ljubi vzeti oblačila od vrha dimnika, in on ga postavi nazaj na Sveženj, potem ko je to storjeno. Torej, na ta način, da nikoli ne Zdi se, da postaja na dnu kup v njegovi oblačila. Tako da je ta vrsta opisuje osnovna struktura podatkov o tem, kako se izvaja kup. 

V bistvu, pomislite kup vsaka skladu predmetov kjer si dal stvari na vrhu, in potem jih pop ven iz vrha. Torej LIFO je kratica želimo da use-- Zadnji noter, prvi ven. In tako zadnji noter na vrhu Sveženj je prvi, da pride ven. In tako oba izraza smo želeli povezati s tem se imenujejo potiskanje in pop. Ko potisnete nekaj na kup in ga pop nazaj gor. 

In zato mislim, da je to nekakšna abstrakten pojem za tiste med vami ki želijo videti kot dejansko izvajanje te v resničnem svetu. Koliko od vas je napisal esej morda kot eno uro, preden je bila posledica, in ste pomotoma izbrisali velik kos njem, kot po naključju? In potem, kaj storiti nadzor bomo uporabili, da ga proda nazaj? Control-Z, ja? Control-Z, tako da je količina roki da je Control-Z mi je rešil življenje, je rešil rit, vsakič ki je izvajal prek dimnika. 

V bistvu vse informacije da je na vašem Wordov dokument, da dobi potiska in izstrelil po volji. In tako v bistvu vsakič, ko vas izbrisati ničesar, ga pop nazaj gor. In potem, če jo potrebujete nazaj na vas ga potisnite, ki je tisto, kar Control-C ne. In tako v realnem svetu funkcija kako enostavno strukturo podatkov lahko pomaga pri vašem vsakdanjem življenju. 

Torej struct je način, da smo dejansko ustvarili kup. Tip definiramo struct, in nato pravimo, da kup na dnu. In v skladovnice, imamo dva parametra da bomo lahko v bistvu manipulirati, tako da imamo char zvezdic strune zmogljivosti. 

Vse to počne ustvarja niz da bomo lahko shranite kar hočeš ki jih lahko določi svoje zmogljivosti. Kapaciteta je samo max znesek Predmeti, ki jih lahko postavimo v to paleto. Velikost int je števec, ki ohranja tir koliko predmetov so trenutno v plasteh. Torej, potem bomo lahko spremljate, A, tako, kako velika je dejansko dimnika je, in, B, koliko tega skladovnice smo napolnjena, ker ne želimo, overflow nad tem, kaj je naša zmogljivost. 

Tako, na primer, to čudovito Vprašanje je bilo na kvizu. V bistvu, kako bomo potisnite na vrhu kupa. Zelo preprosta. Če pogledaš na to, bomo sprehod skozi to. Če [neslišno] size-- se spomnite, ko ste želijo dostop do kateregakoli parameter v struct, vam ime struct.parameter. 

V tem primeru je s ime našega dimnika. Želimo, da za dostop do velikosti od tega, da naredimo s.size. Torej, dokler je velikost ne enako kapaciteto ali dokler kot je manjša od prostornine, bodisi bi delo tukaj. 

Želite dostopati do notranjosti žetonov, tako s.strings, in boš dal, da novo številko da želite vstaviti v tam. Recimo samo, da bomo želeli vstavite int n na stack, kar lahko storimo s.strings, nosilci, s.size enaka n. Ker velikost je kje smo Trenutno so v plasteh če bomo za potiskanje je on, smo pravkar dostop povsod, kjer je velikost, Sedanji polnost dimnika, in smo potisnite int n nanjo. In potem smo se želeli prepričati, da smo tudi povečevanje velikosti n, tako da bomo lahko spremljate smo jih dodal dodatno stvar dimnika. Zdaj imamo večjo velikost. Ali to tukaj smiselno vsakdo, kako logično deluje? Bilo je nekako hitro. OBČINSTVO: Lahko greš čez se s.stringss.strings [s.size] spet? ANDI PENG: Seveda, pa kaj počne s.size trenutno nam dali? OBČINSTVO: To je sedanja velikost. ANDI PENG: Točno, zato je tekoči indeks, da je naša velikost na, in tako smo želeli postaviti nov celo število da želimo vstaviti v s.size. Ali to smiselno? Ker s.strings, vse, se je ime array. Vse to se je dostopom do Niz v naši struct, in zato, če želimo, da postavite n v ta indeks, bomo lahko le dostop do njega uporabljajo nosilci s.size. Cool. 

Vredu, pop, sem ga psevdokoda ven za vas, ampak podoben koncept. Ali to smiselno? Če je velikost večja od nič, potem ste veš, da si želiš, da bi nekaj ven, ker če je velikost ne večja od nič, potem ste nimajo nič dimnika. 

Torej si le želite izvesti Ta koda, ki lahko samo to pop če obstaja nekaj, da pop. Torej, če je velikost večja od 0, smo minus velikost. Pojemanje smo velikost in se nato vrnite vse, kar je znotraj njega, ker jih popping, želimo Dostop kar je shranjena v indeksu vrhu kupa. Vse, kar je smiselno? Če sem ti fantje napisali tole, bi vidva lahko to napisali? OK, lahko vidva igral z njim. Brez skrbi, če ga ne bi dobili. Nimamo časa, da kodo ven danes, ker smo jih dobil veliko teh struktur da gredo skozi, vendar v bistvu psevdokoda, zelo, zelo podobno kot potiskanje. Samo sledite skupaj z logiko. Prepričajte se, da dostop do vseh značilnosti vašega struct pravilno. Ja? 

OBČINSTVO: Bo ta diapozitivov in ta stvar lahko še danes-ish? ANDI PENG: Vedno, ja. Bom poskusil, da dajo to gor, kot eno uro kasneje. Bom email Davida, bo David poskušali ga dal gor, kot eno uro po tem. 

OK, potem pa gremo v to drugo Lep podatkovno strukturo, imenovano čakalno vrsto. Kot lahko vi vidite tukaj, A Čakalna vrsta za Britancev med nami, vse, kar je, je črta. Torej, v nasprotju s tem, kar misliš, da stack, čakalna vrsta je natanko tisto, logično mislite, da je. To je potekalo po pravilih FIFO, ki je prvi noter, prvi ven. Če ste prvi eden v vrsti, da ste prvi, ki prihaja iz vrste. 

Torej, kaj mi je všeč, da to imenujemo je dequeueing in enqueueing. Če želimo dodati nekaj za našo vrsto, smo enqueue. Če želimo dequeue, ali pa nekaj proč, smo dequeue. 

Torej enak občutek, da smo nekako ustvarjanje fiksne velikosti elementov, ki smo lahko shranite nekatere stvari, vendar smo lahko tudi spremeniti, kjer smo dajanje parametri znotraj njih temelji na kakšnem tipu funkcionalnost želimo. Torej nizov, smo želeli zadnji on, N, da je prva ven. Čakalna vrsta je želimo, je prva stvar, v biti prva stvar ven. 

Torej je struct-type opredeliti, kot lahko vidite, to je malo drugačna od tistega, kar je bilo kup ker ne samo, da moramo hraniti tir, kjer trenutno je velikost, želimo tudi, da spremljate glave kakor tudi, kjer smo trenutno so. Zato mislim, da je lažje če sem to pripraviti. Torej, kaj je zamisliti imamo čakalno vrsto, tako recimo glava je tukaj. Vodja linije, dajmo samo povem, da je trenutno tam, in želimo, da vstavite nekaj v čakalno vrsto. Bom poklical velikost bistvu je ista stvar kot rep, konec kjerkoli vaša čakalna vrsta je. Naj samo povem, velikost je tukaj. 

Torej, kako en izvedljiv vstavite nekaj v čakalno vrsto? Kaj indeks želimo postaviti kjer želimo vstaviti v. Če je to začetek vašega čakalno vrsto in to je konec tega ali velikost njej, kjer počnemo želite dodati naslednjo predmeta? 

OBČINSTVO: [neslišno] ANDI PENG: Točno, ki jih želite dodati je odvisno od tega, ki ste ga napisali. Ali je to polje prazno ali da je prazen. Torej hočeš, da ga dodate verjetno tukaj, ker če velikost is-- če so ti vse polno, ki jih želite da jo dodate tukaj, kajne? 

In tako, da je, medtem ko je zelo, zelo preprosto, ne čisto vedno pravilna ker glavni razliki med čakalno vrsto in dimnika je, da je čakalna vrsta dejansko manipulira tako da so te spremembe glave odvisno od tega, kje želite začetek vašega iztočnico za začetek. In kot rezultat, svoj rep se tudi dogaja, da spremenite. In tako si oglejte ta koda prav zdaj. Ker so fantje tudi zahteva, da se izpišite na kvizu, enqueue. Mogoče bomo govorili skozi zakaj odgovor je bil, kaj je bilo. 

Nisem mogel povsem fit to vrstico na eni, ampak v bistvu je ta del kode mora biti v eni vrstici. Preživite kot 30 sekund. Oglejte si, in zakaj to je način, da je. 

Zelo, zelo podobna struct, zelo zelo podobno strukturo kot prejšnja kup razen morda ena vrstica kode. In da eno vrstico kode določa funkcionalnosti. In res razlikuje čakalne vrste iz dimnika. 

Kdo želel vzeti stab pri pojasnjevanju, zakaj ste dobil to zapleteno stvar tukaj? Vidimo vrnitev naših čudovit prijatelj modul. Ker bo vidva kmalu prepoznati v programiranju, skoraj kadarkoli boste potrebovali nekaj da ovijte okoli nič, modul se bo pot, da to storite. Torej, vedoč, da se kdo hotel da bi poskušali razložiti to vrstico kode? Ja, vsi odgovori so sprejeta in dobrodošla. OBČINSTVO: Ali ste v pogovoru z mano? ANDI PENG: Ja. OBČINSTVO: Oh, ne opravičujem. ANDI PENG: OK, tako da je sprehod skozi to oznako. Torej, ko ste poskušali kaj dodati na čakalno vrsto, v lepem primeru, da glava zgodi da je prav tukaj, je zelo enostaven za nas samo iti do konca vstavite nekaj, kajne? Toda bistvo čakalno vrsto je da vodja lahko dejansko dinamično spreminjajo glede na to, kje smo želijo začetek našega q biti, in kot tak, repa se tudi dogaja, da spremenite. 

In tako si predstavljam, da to ni bil čakalne vrste, temveč je bila ta čakalna vrsta. Recimo, glava je tukaj. Recimo, da je naša čakalne videti takole. Če bi želeli preusmeriti, kjer začetek liniji, recimo, da smo premaknilo glavo Na ta način in velikosti tukaj. 

Sedaj želimo dodati nekaj to čakalne vrste, ampak kot lahko vi vidite, to ni tako enostavno, kot da samo dodamo kar je po velikosti ker potem mi zmanjka Meje našega dejanskega paleto. Kjer želimo res dodati je tukaj. To je lepota čakalno vrsto je, da je za nas, vizualno pa Izgleda, da je linija gre takole, toda, če je shranjena v podatkovno strukturo, jim ga dal kot kot cikel. To nekako ovije spredaj na enak način, da lahko črta tudi zaviti okoli odvisno od kjerkoli vas želijo začetku vrstice biti. In tako, če vzamemo poglej tukaj, dajmo rekli, da smo želeli ustvariti Funkcija se imenuje enqueue. Želeli smo dodati int n v tem q. Če q.size -Q- bomo pokličem, da naše podatke structure-- če naša queue.size ne enako kapaciteto ali če to je manj kot zmogljivosti, q.strings je matrika v naši q. Gremo nastaviti ki je enaka q.heads, ki je tukaj, plus q.size modul s kapaciteto, ki je zaviti nas spet tukaj. 

Torej, v tem primeru, indeksa glave je 1, kajne? Indeks velikosti 0, 1, 2, 3, 4. Torej ne moremo storiti 1 plus 4 modul jih naše zmogljivosti, ki je 5. Kaj nam daje? Kaj je indeks, ki prihaja iz tega? 

OBČINSTVO: 0. 

ANDI PENG: 0, kar zgodi, da se prav tu, in zato želimo, da bi lahko da vstavite tukaj. In zato je ta enačba tukaj vrsta za preprosto deluje z vsemi številkami odvisno od tega, kje si glava in vaše velikosti so. Če veste, kaj tisti, so stvari, veste točno tam, kjer želite vstaviti kar je po vašem čakalno vrsto. Ali, da je smiselno, da vse? 

Vem vrste možganov teaser še posebej, ker je to prišel v odpravljanju posledic svojega kviza. Ampak upajmo, da vsakdo Zdaj lahko razumemo, zakaj ta rešitev ali je to funkcija je, da ga je. Vsakdo nekoliko nejasno o tem? V REDU. 

In zdaj, če vas želel dequeue, to je, če bi bila naša glava premika ker če bi dequeue, nimamo vzlet konec q. Želimo, da za vzlet glavo, kajne? Tako kot rezultat, glava se bo spremenilo, in da je razlog, zakaj, ko ste enqueue, moraš slediti kjer sta vaša glava in tvoja velikost morajo biti sposobni vstaviti v pravilen položaj. 

In tako, ko dequeue, Prav tako sem psevdokoda ven. Vas prosimo, da, če hočeš poskus kodiranje to. Želite premakniti glavo, kajne? Če sem želel dequeue sem bi se premaknite nad glavo. To bi bila glava. 

In bi naša sedanja velikost odštejemo, ker ne bomo več ima štiri elemente v matriki. Imamo samo tri, nato pa želimo vrniti, kar je bila shranjena v notranjosti glave, ker želimo, da bi to Vrednost ven tako zelo podobna dimnika. Pravkar ste ob iz druge destinacije, in boste morali znova dodelite kazalec na drugo mesto, kot rezultat. Logično je, da vsi sledimo? Great. 

OK, tako da bomo govorili malo bolj poglobljeno o povezanih seznamih ker se bo zelo, zelo dragocen za vas v teku ta teden je psets. Povezani seznam, kot vidva spomnim se, vsi so so vozlišča, ki so vozlišča nekaterih Vrednosti obeh vrednost in kazalcem ki so med seboj povezani s temi kazalci. In tako struct o tem, kako smo ustvarili vozlišče tu smo imajo int n, ki je glede na vrednost v trgovini ali niza n ali karkoli želite pravijo, char zvezda n. Struct vozlišče zvezda, ki je kazalec ki želite imeti v vsakem vozlišču, boste morali, da kazalec točka v smeri naprej. Imeli boste glavo iz povezanega seznama, ki je dogaja, da opozarjajo na preostalo vrednosti tako naprej in tako naprej dokler ne boste sčasoma do konca. In to zadnje vozlišče je le bo še kazalec. To se dogaja, da kažejo na null, in da je, ko veste, da ste zadeli konec vaše povezanega seznama je, ko tvoj zadnji kazalec ne kaže na nič. 

Tako smo šli malo bolj v Globina o tem, kako bi bila ena od možnosti iskati povezani seznam. Spomnite se, kaj so nekateri od slabosti povezanih seznamov prehladna paleto zvezi iskanj. Matrika lahko binarno iskanje, vendar zakaj ne morete storiti, da je v povezanem seznamu? 

OBČINSTVO: Ker oni so vsi povezani, vendar ne povsem vedeli, kje [Neslišno]. 

ANDI PENG: Ja, točno tako, ne pozabite da sijaj array je dejstvo, da smo imeli bralno-pisalnega pomnilnika, kjer če sem hotel vrednost iz indeksa šest, jaz lahko samo rečem indeks šest, daj mi te vrednosti. In to zato, ker so nizi razporejene v sosednjem prostoru pomnilnika na enem mestu, medtem ko je vrsta povezanih seznamov so naključno posejani po vsem, in edini način, boste lahko našli enega je s kazalcem, ki vam pove naslov, kjer je ta dostavo vozlišče. 

In tako posledično edini način iskanje po povezanem seznamu linearna iskanje. Ker mi ni točno vedel, kje 12. Vrednost v povezanem seznamu je, Moram prečkanje celoto od tega povezanega z enim seznamom eden od glave do prvega vozla, Na drugo vozlišče, na tretje vozlišče, vso pot navzdol, dokler sem končno dobil da, kjer je to vozlišče iščem. In tako v tem smislu, iskanje na povezane seznamu vedno n. Vedno je n. To je vedno v linearnem času. 

In tako je koda, v katerem izvajamo to, kar je malo novega za vas, saj ste Fantje so se res ne govorili ali kdaj videl kazalci v tem, kako iskanje po kazalci, tako da bomo sprehod skozi To je zelo, zelo počasi. Torej iskanje bool, desno, Predstavljajmo si želimo ustvariti funkcijo imenovano Iskanje, ki vrne true Če ste našli vrednost znotraj povezano seznam, in ga vrne false drugače. Seznam Node zvezdicami Trenutno samo kazalec na prvi element v vašem povezani seznam. int n je vrednost, ki ste išče na tem seznamu. 

Torej vozlišče zvezda kazalec enak seznam. To pomeni, da smo nastavitev in ustvarjanje kazalec v tem prvim vozliščem znotraj seznama. Vsakdo z mano? Torej, če smo bili, da gredo nazaj, bi moral inicializiran kazalec, ki kaže na glava, kar je ta seznam. 

In potem, ko boste dobili tukaj, medtem ko je kazalec ni enak null, tako, da je zanka, v kateri smo bo nato prečkajo preostali del našega seznama ker tisto, se zgodi, ko kazalec enaka null? Vemo, da smo have-- 

OBČINSTVO: [neslišno] 

ANDI PENG: Točno, zato smo vedeli, da smo prišli do konca seznama, kajne? Če greš nazaj, vsako vozlišče Treba je poudariti, da drugo vozlišče in tako naprej in tako naprej dokler si udaril na koncu rep vašega povezanega seznama, ki ima kazalec, ki le ne kaže nikamor, razen št. In tako ste v bistvu vedeti, da Vaš seznam je še vedno tam gor dokler se kazalec ne enaka null, ker ko je enak null, saj veš, da ni več stvari. 

Tako, da je zanka, v kateri smo dogaja, da imajo dejansko iskanje. In če pointer-- vidiš da vrsta arrow funkcijo tam? Torej, če je kazalec točk, n, če kazalec na n enako enako n, To pomeni, da če kazalec, da ste iskanje na koncu vsakega vozlišče dejansko enaka vrednosti iščete, potem želite vrniti true. Torej v bistvu, če ste na vozlišču, ki je vrednost, ki jo iščete, veste, da ste bili uspešno iskanje. 

V nasprotnem primeru, da želite nastaviti vaš kazalec na naslednje vozlišče. To je tisto, ki črta tu počne. Pointer enak kazalec zraven. Vsi videli, kako je to delovalo? 

In v bistvu boš samo prečkanje celotne seznamu ponastavitev kazalec vsakič, dokler sčasoma dvignil konec seznama. In veš, da ne obstajajo več vozlišč za iskanje skozi, in potem se lahko vrnete false saj veš, da, oh, no, če sem bil sposoben za iskanje preko celotne seznama. Če se v tem primeru, če bi hotel iskati vrednosti 10, in začnem na čelu, in Iščem vso pot navzdol, in sem na koncu prišel do tega, kar kazalec, ki kaže na ničlo, Vem, da je sranje, mislim, da 10 ni ta seznam, ker nisem mogel najti. In jaz sem na koncu seznama. In v tem primeru veš Bom vrnil false. 

Dovolite, da namakate v za malo. To bo lepa pomembna za vašo pset. Logika je zelo preprosta, morda skladenjsko le njeno izvajanje. Vidva želite prepričani, da razumete. Cool. 

OK, tako, kako bi bili vstavljanje vozlišč, desno, v seznam, saj se spomnite kaj so, kaj koristi da imajo povezani seznam versus niz v smislu skladiščenja? 

OBČINSTVO: To je dinamičen, tako da je lažje to-- 

ANDI PENG: Točno, tako da je dinamičen, kar pomeni, da se lahko razširi in skrči glede na potrebe uporabnika. In tako, v tem smislu, da ne potrebujemo zapravljati nepotrebnih spomin, ker sem če ne vem, koliko vrednosti želim za trgovino, pa nima smisla za mene ustvariti array, ker je če želim shraniti 10 vrednosti in sem ustvaril niz 1.000, to je veliko zapravlja spomina, dodeljen. Zato želimo, da uporabite povezan seznam, da bi lahko dinamično spremeniti ali skrči svojo velikost. 

In tako, da omogoča vstavljanje malo bolj zapletena. Ker ne moremo naključno dostop elemente način, da bi iz nabora. Če želim vstaviti element v sedmi indeksa, Jaz lahko samo vstavite v sedmi indeks. Na povezanega seznama, le-ta ne čisto delo tako enostavno, in tako, če smo želeli, da vstavite ena tukaj v povezanem seznamu vizualno, to je zelo težko videti. Pravkar smo želeli, da ga vstavite tam, takoj na začetku seznama, takoj po glavi. 

Ampak način, na katerega moramo prerazporediti so kazalci je nekoliko zapletena ali, logično, je smiselno, ampak želite poskrbite, da ga imate povsem dol, ker zadnja stvar, ki jo želite se prerazporedijo kazalec način, da delamo tukaj. Če vas dereference kazalec od glave do 1, nato pa vse nenadoma preostanek svojega povezanega seznama se izgubi, ker moraš dejansko ne ustvaril začasno ničesar. Ki je opozoril na 2. Če znova kazalec, nato Preostanek vašem seznamu je popolnoma izgubljen. Torej hočeš biti zelo, zelo previdni tukaj najprej dodelite pointer iz Karkoli želite vstaviti v kjerkoli hočeš, nato pa vas lahko dereference preostanek svojega seznama. 

Torej to velja za kamorkoli skušate vstavite. Če želite vstaviti Na glava, če želite, da tu odgovoriti, Če želite vstaviti v konec, no, na koncu sem Verjetno bi le nimajo kazalec, vendar boste želite poskrbite, da ne boste izgubijo preostanek svojega seznama. Vedno si želite zagotoviti vaš novi vozlišče je obrnjena proti karkoli želite vstaviti v, in potem si lahko dodate veriženje naprej. Vsakdo jasno? 

To se bo eden izmed pravih vprašanj. Eden od najbolj pomembnih vprašanj boste imeli na vašem pset je, da greš, da bi poskušali ustvariti med sabo povezan seznam in vstavite stvari potem pa samo izgubili preostanek svojega povezanega seznama. In ti bo všeč, sem Ne vem, zakaj se to dogaja? In to je bolečina, da gredo skozi in iskanje vseh vaših nasvetov. 

In zagotavljam vam na tem pset, pisanje in risanje teh vozlišč ven bo zelo, zelo koristno. Tako boste lahko popolnoma spremljate kje so vsi vaši kazalci, kaj je šlo narobe, kjer so vsi vaši vozlišča, kaj morate storiti, da bi dostopali ali vstavite ali izbrišete ali kateri koli od njih. Vsakdo dobro s tem? Cool. 

Torej, če smo želeli, da pogled na kodo? Oh, ne vem, če smo lahko vidite the-- OK, tako Na vrhu vsega je funkcija imenovan vložek, kjer želimo vstaviti int n v povezano seznamu. Gremo na sprehod skozi to. To je veliko kode, veliko novega sintakse. Mi bo v redu. 

Torej na vrhu, kadar želimo ustvariti ničesar Kaj moramo storiti, še posebej, če vas želim, da bi se ne shranjujejo na kupu vendar v kup? Gremo na knjižnične funkcije malloc, kajne? Tako bomo ustvarili kazalec. Vozlišče, kazalec, novi Ene malloc velikosti vozlišču ker želimo, da je vozlišče, ki bo ustvaril. Želimo količino spomin, da je vozlišče zavzame bodo dodeljene za Ustanovitev novega vozlišča. 

In potem bomo preverite vidim, če novi Ene enaka null. Spomni se, kaj smo rekli? Karkoli vam malloc, Kaj morate vedno narediti? Morate vedno preverite, ali je, da nič. 

Na primer, če je vaš operacijski Sistem je bil povsem poln, če bi imeli nič več pomnilnika na vse in poskusite knjižnične funkcije malloc, da bi se vrnil null zate. In tako, če boste poskušali uporabiti ko je bila obrnjena na ničlo, ti ne boš mogel za dostop do teh informacij. In tako, kot smo želeli, da bi prepričani, da ko ste mallocing, ste vedno preverjanje, da vidim, če da spomin dal je nična. In če je ni, potem lahko gremo o s preostalim naše kode. 

Torej bomo inicializacijo novo vozlišče. Bomo storili nov n enak n. In potem bomo storili nastaviti nov kazalec na novo na nič, ker zdaj ne bomo želim ničesar za to, da kaže. Nimamo pojma, kje to se dogaja, da si dal, in potem, če želimo ga vstavite na čelu, potem bomo lahko znova dodelite kazalec z glavo. Ali vsi sledimo logiki kje, da se dogaja? 

Vsi delamo ustvarja nova vozlišče, ki določa kazalec na ničlo, in nato prerazporeditev je v glavo, če bomo vem, želimo, da ga vstavite v glavo. In potem glava se bo kažejo na to novo vozlišče. Vsakdo v redu s tem? 

Torej, to je dvostopenjski postopek. Imaš do prvega Dodeli kar ste ustvarili. Nastavite, da kazalec na reference, nato pa vas lahko vrsta ciljne datoteke Prvi kazalec in kažejo na novo vozlišče. Kjerkoli jo želite vstaviti, da logika se dogaja, da drži. 

To je nekako kot dodeljevanje začasne spremenljivke. Zapomnite si, da imaš se prepričajte, da vas ne bo zmanjkalo, če ste zamenjavo. Želite, da se prepričajte, da imate začasna spremenljivka, ki nekako ohranja tir, kjer je to stvar se shranijo, tako da boste ne izgubijo katerokoli vrednost med podobnega mesijanski okrog z njim. 

OK, tako da koda bo tukaj. Vidva si oglejte po oddelku. To bo tam. 

Torej, mislim, kako deluje To je drugačna, če smo želeli vstaviti v sredini ali na koncu? Ima kdo idejo, kaj je psevdokoda kot logično referenca da bomo, če bomo želeli da jo vstavite v sredini? Torej, če bi želeli, da ga vstavite Na glava, vse moramo storiti, je ustvariti novo vozlišče. Postavili smo kazalec, ki novo vozlišče na kakršnikoli glavo, in potem smo postavili glavo na novo vozlišče, kajne? Če bomo želeli, da ga vstavite v sredini seznama, kaj bi morali storiti? 

OBČINSTVO: To bi še vedno Podobna Postopek podobnega dodeljevanje kazalec in nato dodelite ta kazalec, vendar bi morali tam poiskati. 

ANDI PENG: Točno tako natanko enak postopek, razen tebe morali poiskati, kje ste želijo, da novi kazalec, da gredo v, tako da, če hočem, da vstavite Sredi povezana list-- OK, recimo, da je naša povezani seznam. Če želimo, da jo vstavite tukaj, bomo ustvarili novo vozlišče. Bomo knjižnične funkcije malloc. Bomo ustvarili novo vozlišče. Bomo dodelite kazalec tega vozlišča tukaj. 

Vendar je problem, ki se razlikuje od koder je glava je, da smo vedeli, točno kjer je glava. Bilo je prav na prvi, kajne? Ampak tukaj imamo slediti kje smo jo vstavite. Če smo vstavljanje naše node tukaj, imamo se prepričajte, da ena od prejšnjih za to vozlišče je tista, ki reassigns kazalec. Torej moraš nekako spremljate dveh stvari. Če spremljate, kjer je to vozlišče trenutno vstavite. Prav tako morajo slediti, kje prejšnja vozlišče, da gledaš je tudi tam. Vsakdo dobro s tem? V REDU. 

Kako približno vstavite do konca? Če bi želel, da ga dodate here-- če sem hotel dodati novo vozlišče na konec seznama, kako bi jaz šel o tem? OBČINSTVO: Torej, trenutno je zadnja je opozoril na nič. ANDI PENG: Ja. Točno, tako da je to ena Trenutno je poudaril, da vedo, in tako mislim, v tem smislu, da je Zelo enostavno dodajanje na konec seznama. Vse kar morate storiti je, da jo nastavite enaka NULL in potem bum. Prav tam, zelo enostavno. Zelo preprosto. 

Zelo podobna glavo, vendar je logično vas želite zagotoviti, da ukrepi jemljete proti delaš vse to, ste po skupaj. To je zelo enostavno, v sredini vaše kode, ujeli na, oh, sem dobil toliko nasvetov. Ne vem, kje vse kaže na. Sploh ne vem, katero vozlišče sem na. Kaj se dogaja? 

Pomiri se, pomiri se, globoko vdihni. Potegnili svoje povezani seznam. Če rečeš, vem, kje točno Moram vstaviti to v in točno vem, kako prerazporediti my kazalci, veliko, veliko lažje sliko out-- veliko, veliko lažje, da se ne izgubijo v hroščev v kodi. Vsakdo v redu s tem? V REDU. 

Tako da mislim, koncept, ki ga imamo, ne res govoril o pred zdaj, in ti veš verjetno ne bodo imeli veliko yet-- to je nekako napredno concept-- je, da smo dejansko imeli podatke struktura se imenuje dvojno povezani seznam. Tako da lahko vi vidite, vse, kar počnete, je ustvarjanje dejanska vrednost, dodatno kazalec na vsakega od naših vozlišč ki kaže tudi s predhodnim vozliščem. Torej, ne samo, da imamo vozlišča kaže na naslednjega. Prav tako opozarjajo, da prejšnji. Grem prezreti teh dveh prav zdaj. 

Torej imate verigo ki se lahko premika v obe smeri, in potem je nekoliko lažje logično sledijo vzdolž. Kot tod namesto sledenja, oh, jaz morali vedeti, da je to vozlišče tisti, ki moram prerazporedijo, Jaz lahko samo iti tu in samo potegnite prejšnji. Potem vem, kje da je, nato pa vas nimajo za prečkanje celota povezanega seznama. To je nekoliko lažje. 

Ampak kot taka, imate dvakrat količina kazalcev, da je dvojna količina pomnilnika. To je veliko nasvetov za sledenje. To je malo bolj zapleteno, vendar je malo bolj prijazen do uporabnika, odvisno o tem, kaj poskušate doseči. 

Tako da je ta vrsta podatkov struktura povsem obstaja, in struktura je zelo, zelo preprosta razen vse, kar imaš, je, namesto samo kazalec na naslednjo, imate tudi kazalec na prejšnji. To je vse, kar je bila razlika. Vsakdo dobro s tem? Cool. 

Vse je v redu, tako da zdaj sem res porabili verjetno kot 15 do 20 minut, ali pa bo večji preostalega časa v oddelku govorimo o hash tabel. Koliko od vas fantov Prebral pset5 spec? Dobro, dobro. To je višja od 50% normalno. To je v redu. 

Tako da bodo fantje videli, ste izziv pset5 bo izvajala slovar kjer si naložiti preko 140.000 besed da smo vam in preverjanje črkovanja je proti vsem besedilu. Mi vam bomo naključno kosov literature. Mi vam bomo Odiseje. Mi vam bomo Iliadi. Mi vam bomo Austin Powers. 

In vaš izziv bo preverjanje črkovanja vsak beseda v vseh od teh slovarjev v bistvu z našo črkovalnik. In tako obstaja nekaj delov ustvarjanja to pset, Prvi hočeš biti lahko dejansko obremenitev vse besede v vašo slovar, nato pa vas želijo biti sposobni črkovati ček vse od njih. In tako, kot je na primer, da boš zahtevajo podatkovna struktura, ki lahko to stori hitro ter učinkovito in dinamično. 

Torej, mislim, da je najlažje način, da to storite, vas Verjetno bi ustvarili niz, kajne? Najlažji način shranjevanja je vas lahko ustvarite niz 140.000 besed in jih vse samo mesto tam in jih nato prečkala s binarnega iskanja ali z izborov ali not-- Žal mi je, da je razvrščanje. Lahko jih uredite in jih nato prečkala s binarnega iskanja ali pa samo linearno iskanje in samo končne besede, temveč da potrebnega ogromno pomnilnika, in to ni zelo učinkovito. 

In tako bomo za začetek govorimo o načinih izdelave naš čas teče bolj učinkovito. In naš cilj je, da bi dobili konstanten čas, kjer to je skoraj tako kot nizi, kjer imate takojšen dostop. Če sem hotel iskati karkoli, Želim, da bi lahko le, boom, da bi našli točno, in ga izvlecite. In tako strukturo, v kateri bomo lahko postali zelo blizu da se lahko dostop konstantna Tokrat je to sveti gral v programiranju konstanta Čas se imenuje hash tabelo. In tako je David že prej omenjeno [Neslišno] malo v predavanju, ampak bomo res potop v globokem tem tednu na kos, ki je v zvezi s kako hash tabela deluje. 

Torej, na način, da je hašiš namizno dela, na primer, če sem hotel, da shranite kup besedami, kup besed v angleškem jeziku, Jaz bi teoretično dal banana, jabolko, kivi, mango, par, in melone vse na samo paleto. Lahko bi prilegajo in jih je najti. To bi bilo nekako v bolečinah iskanje po in dostop, vendar je lažji način za to je, da bomo lahko ustvarili dejansko strukturo imenuje hash tabele, kjer smo izbrskali. Vodimo vse naše ključev prek funkcija hash, enačba, ki jih vse spremeni v nekakšna vrednosti da potem bomo lahko shranite na v bistvu paleto povezani seznam. 

In tako sem, če bomo želeli za shranjevanje angleške besede, smo lahko potencialno samo, jaz ne Veš, pa vse prve črke v v neke vrste številko. In tako, na primer, če sem hotel A sinonim apple-- ali z indeksom od 0, in B sinonim z 1, imamo lahko 26 vnose da lahko samo shranite vse črk alphabet, da bomo začeli z. In potem bomo lahko imeli jabolko na indeks 0. Imamo lahko banano na indeksu 1, melone na indeksu 2, in tako naprej in tako naprej. In zato, če sem hotel iskati moj hash tabele in dostop jabolko, Vem, jabolko začne z A, in točno vem, da mora biti in razpršitve miza na indeksu 0 zato ker funkcije predhodno dodeljena. 

Torej, ne vem, mi smo program uporabniški kadar vam bomo zaračunali z arbitrarily-- ne samovoljno, s poskušajo premišljeno mislim dobrih enačb da se lahko širi iz vseh vaših vrednot na način, ki jih lahko enostavno dostopate je kasneje s podobno enačbo da vas, sami, vem. Torej, v tem smislu, če sem hotel iti mango, vem, oh, se začne z m. Mora biti v indeksu 12. Nimam iskati skozi karkoli. Vem exactly-- sem lahko samo iti indeks 12 in potegnite, da ven. 

Vsakdo jasno, kako Funkcija hash tabele se deluje? To je nekako le bolj kompleksno paleto. To je vse, kar je. V REDU. 

Torej, mislim, da smo zašli v to vprašanje o tem, kaj se zgodi, če imate več stvari da vam isti indeks? Tako pravijo naše delovanje, vse to naredil je bilo to prvi dopis in nato da na A Ustrezni 0 do 25 indeks. To je povsem v redu, če ste le eden od vsakega. Ampak drugi začnete ki imajo več, ste dogaja, da imajo, kaj se ti trčenja. 

Torej, če sem poskusil vstaviti pokopati v hash tabela, ki ima že banano na njem, kaj se bo zgodilo, ko poskusite vstaviti to? Slabe stvari, ker banana že obstaja v indeksu ki jo želite shraniti v. Berry vrsta je všeč, ah, kaj naj storim? Ne vem, kam iti. Kako rešiti to? 

In tako bo vidva vrste glej delamo to težavno stvar kjer bomo lahko nekako dejansko ustvariti povezan seznam iz naših polj. In tako najlažje razmišljati o tem, Vse hash tabela je array povezanih seznamov. In tako, v tem smislu, imate to lepo niz kazalcev, in nato vsak kazalec v da vrednost, v tem indeksu, lahko dejansko kažejo na druge stvari. In tako imaš vse te ločene verige prihajajo off enega velikega polja. 

In tako sem, če sem želel vstaviti jagodami, Vem, OK, bom vhod je po mojem hash funkcijo. Grem na koncu z indeksom 1, in potem bom lahko, da imajo le manjši podmnožica to velikan 140.000 besedo slovar. In potem sem lahko samo pogled skozi 1/26 tega. 

In tako potem bom lahko samo vstavite berry bodisi pred ali po banana v tem primeru? Potem, kajne? In tako boste želeli vstavite to vozlišče po banana, in tako boste, da vstavite na repu tega povezanega seznama. Jaz bom šel nazaj s tem prejšnjo prosojnico, tako da vidva lahko vidite, kako hash funkcija deluje. 

Torej hash funkcija je ta enačba da delate neke vrste vaš prispevek skozi, da bi dobili, kar indeks Jo želite dodeliti smeri. In tako, v tem primeru, vse, kar smo želeli storiti je vzeti prvo pismo, obrnejo, da v indeksu, nato pa smo lahko shranite, da je v našem hash funkcijo. Vsi delamo tu smo pretvorbo prvo pismo. Torej keykey [0], je le prva črka ne glede na niz imava, smo poteka v. Mi smo pretvarjanje, da zgornji del, in smo se odšteje s velikimi črkami A, zato vse, kar počne nam daje številne v katerem bomo lahko izbrskali naše vrednote na. 

In potem bomo vrne hash VELIKOST modul. Bodite zelo, zelo previdni ker, teoretično, tu tvoj hash vrednost je lahko neskončno. To lahko samo pojdi naprej in naprej in naprej. To bi bilo nekaj res, Res velika vrednost, ampak zato, ker vaše hash tabelo, ki ki ste jo ustvarili ima samo 26 indeksov, želite, da vaš modulusing tako da boste ne run-- je isto stvar kot vaš queue-- tako da vam ne zmanjka off dno vašega hash funkcijo. 

Hočeš, da ga ovijte nazaj okoli na enak način, v [neslišno], če ste imeli kot zelo, zelo velika črka, ki jih niso želeli, da bi Samo nogama konec. Ista stvar tukaj, boste želeli, da poskrbite, ne nogama konec embaliranje približno na vrhu tabele. Torej, to je samo zelo preprosto funkcijo razpršitve. Vse, kar si je vzeti prvi pismo o kakršnikoli našega vhoda je in pa, da je v indeksu, ki lahko bi dal v naše hash tabelo. 

Ja, tako kot sem rekel prej, način, da bomo rešili trčenja v našem hash so mize, ki ima, kaj pravimo, veriženje. Torej, če boste poskušali vstaviti multipla Besede, ki se začnejo z isto stvar, boste morali en hash vrednost. Avokado in jabolko, če ste ga vodijo skozi našo hash funkcijo, se dogaja, da bi vam enako število, število 0. In tako način, kako rešiti, da je da bomo lahko dejansko nekako povežejo skupaj preko povezanih seznamov. 

In tako v tem smislu, vidva lahko vidite vrste kako podatkovne strukture, ki smo bili predhodno nastavitev kot rozin povezan seznam naravi za lahko pridejo skupaj v eno. In potem si lahko ustvarite daleč bolj učinkovite podatkovne strukture da zmorem večje količine Podatki, ki dinamično spreminjanje velikosti, odvisno na vaše potrebe. Vsakdo jasno? Vsakdo nekako jasno, o tem, kaj se dogaja tukaj? 

Če sem želel insert-- kaj je sadje, ki se začne z, ne vem, B, razen jagod, banana. 

OBČINSTVO: Blackberry. 

ANDI PENG: Blackberry, blackberry. Kje blackberry gre tukaj? No, pravzaprav niso razporejene še to, vendar teoretično če bi želeli imeti to po abecednem vrstnem redu, kje naj blackberry iti? 

OBČINSTVO: [neslišno] 

ANDI PENG: Točno, potem tukaj, kajne? Ampak, ker je zelo težko reorder-- Mislim, da je do vas. Vidva lahko popolnoma izvajati, kar hočeš. Bolj učinkovit način to početje morda bi bilo razvrstiti vaše povezana seznam v abecednem vrstnem redu, in tako, ko ste vstavljanje stvari, ki jih želite biti prepričani, da jih vstavite v abecednem vrstnem redu tako da potem, ko ste poskušam jih iskati, nimate za prečkanje vse. Točno tam, kjer veš, je, in to je lažje. 

Ampak, če boste nekako morali Stvari vrinjeni naključno, ste še vedno dogaja, da imajo da je prečkanje nekako. In zato, če sem hotel samo vstavite blackberry tukaj in sem hotel iskati da, vem, oh, blackberry se mora začeti z indeksom 1, tako da sem vem, sprašuje samo iskanje na 1. In potem sem lahko nekako prečkala povezan seznam dokler ne pridem do BlackBerry, in then-- ja? 

OBČINSTVO: Če ste poskušali create-- Mislim, da, kot je to zelo preprost hash funkcija. In če smo želeli storiti več plasti te všeč, OK, želimo ločiti v kot vse abecedne črk na in potem spet rad še en niz abecednih črk znotraj, da smo dajanje kot hash miza v hash tabele, ali kot funkcije v odvisnosti? Ali je that-- 

ANDI PENG: Torej vaš hash function-- svoje razpršene tabele lahko tako velika, kot si želite, da bi. Torej, v tem smislu sem mislil je bilo zelo enostavno, zelo enostavno za mene, da nekako temelji na črkami prvo besedo. In tako da je le 26 možnosti. Lahko dobim samo 26 možnosti od Od 0 do 25 let, saj lahko le začeti od A do Ž, ampak če si hotel dodati, morda, več kompleksnosti ali hitreje teči čas, da vaš hash tabele, morate nujno lahko storite vse vrste stvari. Lahko naredite sami enačba, ki vam daje več distribucija v vašem besede, potem ko iščete, to se dogaja, da se hitreje. 

To je povsem odvisno od vas fantje kako želite izvesti to. Pomislite na to kot samo vedri. Če sem hotel imeti 26 žlice, jaz grem razvrstiti stvari v teh vedri. Ampak jaz grem, da imajo kup stvari v posamezne segmente, tako da, če želite, da jo hitrejše in učinkovitejše, Naj imajo sto veder. 

Ampak potem moraš razbrati način, da razvrstite stvari, tako da so v ustrezno vedro morajo biti. Ampak potem, ko ste dejansko želeli videti na tej vedro, to je veliko hitreje, ker obstaja manj stvari v posamezne segmente. In tako, ja, to je dejansko trik za vas v pset5 je, da se boste izzvani, da samo ustvariti karkoli je najučinkovitejši Funkcija si lahko zamislite, da bi lahko shranite in preverite te vrednote. 

Popolnoma do vaju pa hočeš to storiti, ampak to je res dobra točka. Ta vrsta logike želim, da začnete razmišljati o je tudi, zakaj ne naredim več veder. In potem moram iskati zmanjšane za stvari, in potem pa sem imajo drugačno funkcijo razpršitve. 

Ja, tam je veliko načinov, da to storijo pset, nekateri so hitrejši od drugih. Jaz sem popolnoma bomo šele videli, kako hiter je bil najhitrejši vidva bo lahko dobili svoje funkcije za delo. OK, vsi dobro na veriženje in hash tabele? To je dejansko všeč zelo preprosta koncept, če mislite o tem. Vse, kar je, je ločevanje karkoli vaši vložki so v vedra, njihovo razvrščanje in preiskujejo navaja, da je tam povezana s. 

Cool. V redu, sedaj imamo različne vrste strukture podatkov, ki se imenuje drevo. Pojdimo naprej in govori o poskusih ki so izrazito drugačen, vendar pa v isti kategoriji. V bistvu, vse je drevo namesto organizacije podatkov v linearno da ste hash tabela does-- Veste, to je dobil top in dno in potem si nekako povezati off it-- a Drevo ima top, ki ga imenujemo koren, in potem ima liste vse okoli njega. 

In tako vse, kar imamo tukaj je samo vrh vozlišče ki kaže na drugih vozlišč, da točke na več vozlišč, in tako naprej in tako naprej. In tako boste morali delitev vej. To je samo drugačen način organiziranja podatkov, in ker smo to drevo klic, vidva just-- je samo vzoru ven videti kot drevesa. To je razlog, zakaj ga imenujemo drevesa. 

Hash tabela izgleda mizo. Drevo samo izgleda kot drevo. Vse, kar je še posebna način organiziranja vozlišč odvisno od tega, kakšne so vaše potrebe. 

Torej imate korenine in potem imate liste. Tako, da smo lahko še posebej pomislite, da je binarno drevo, binarno drevo je samo posebna vrsta drevesa kjer vsako vozlišče le točke da, na max, dva druga vozlišča. In tako da tukaj imate razlikuje simetrija v drevo ki omogoča lažje nekako pogledati po kakšni ceni ste, ker potem ste še vedno levo ali desno. Nikoli ni kot levi tretjina od levo ali četrti z leve. To je samo imate levo in pravico in lahko iščete eno od teh dveh. In zakaj je to koristno? Tako, da je to koristno je, če iščete iskanje po vrednotah, kajne? Namesto izvajanju binarno iskanje v vrsto napak, če boste želeli, da bi lahko vstavite vozlišč in odnese vozlišč po svoji volji in tudi ohranitev iskanje Zmogljivosti binarnega iskanja. Torej, na ta način, da smo nekako tricking-- se spomniš, ko smo je dejal, povezani seznami ne more binarno iskanje? Mi smo nekako ustvariti podatkovno strukturo da trikov, da v delovni. 

In zato, ker povezani seznami so linearne, so le povezati eno za drugo. Lahko vrste imajo drugačna vrsta kazalcev ki kažejo na različnih vozlišč ki nam lahko pomaga pri iskanju. In tako sem, če sem hotel imajo binarno iskalno drevo, Vem, da je moj sredini, če 55 let. Jaz sem le, da bo ustvaril, da kot moj sredini, kot je moj koren, in potem bom imel Vrednosti spin off od tega. 

Torej, tukaj, če grem za iskanje vrednost 66, lahko začnem pri 55. To je 66 večja od 55? Ja je, zato sem vedel, da sem mus iskanje i n pravica kazalec tega drevesa. Grem do 77. OK, je 66 manj kot ali večji od 77? To je manj kot, tako da boste vedeli, oh, da mora biti v levo vozlišče. 

In tako da tukaj smo nekako ohranjanja vse od velikih stvari o nizi, tako kot dinamično spreminjanje velikosti predmetov, pri čemer je lahko vstavite in brisanje po svoji volji, ne da bi morali skrbeti fiksni Količina prostora. Še vedno ohraniti vse te čudovite stvari hkrati pa lahko, da se ohrani log in iskanje čas binarnega iskanja da smo bili prej samo lahko dobili besedno zvezo. 

Cool podatkovna struktura, vrsta zapletene za izvajanje, vozlišče. Kot lahko vidite, vse to je struct vozlišča je, da imate levo in pravica kazalec. To je vse, kar je. Torej, ne samo ima x ali prejšnja. Imate levo ali desno, in nato jih lahko nekako povezati Vendar pa se tako odločijo. 

OK, smo dejansko dogaja vzemite nekaj minut. Tako smo šli nazaj. Kot sem že rekel, Nekako sem razložil logika, kako smo bi preiskava skozi to. Bomo poskušali pseudocoding to gledat če bomo lahko nekako velja Ista logika binarnega iskanja za drugačno vrsto podatkovne strukture. Če hočete, da bi kot par minut, da le razmišljati o tem. V REDU. V redu, bom dejansko samo vam the-- ne, bomo govorili o psevdokoda prvi. Torej, ali ima kdo rad dati stab, kaj prva stvar, ki jo želite storiti, ko ste začeli ven Iskanje je? Če iščemo vrednost 66, kar je prva stvar, ki jo želite storiti, če želimo binarno iskati to drevo? 

OBČINSTVO: Želite videti v redu in poglej levo in videli [neslišno] večje število. 

ANDI PENG: Ja, točno. Torej boš pogled na vaše korenine. Obstaja veliko načinov, kako lahko kličete to, vaši starša ljudje pravijo. Rad bi rekel, koren, ker da je kot koren drevesa. Greš pogledati svoj koren vozlišče, in vi ste bomo videli, je 66 večja ali manjša od 55. In če je večji od, dobro, da je večja kot, kjer ne želimo iskati? Kje želimo iskati zdaj, kajne? Želimo, da iskanje po Desna polovica tega drevesa. 

Torej imamo priročno, A kazalec, ki kaže na desno. In tako potem lahko nastavite naš novi koren, da bo 77. Mi lahko samo iti kamorkoli kazalec je obrnjena. No, oh, tu začenjamo na 77, in bomo lahko samo To storite tako rekurzivno znova in znova. Na ta način se nekako od imajo funkcijo. Imate način iskanja, ki vas Lahko samo ponovim znova in znova in znova, odvisno od tega, kje želite iskati dokler ne boste na koncu dobili z vrednostjo ki iščete. Ima smisel? 

Sem približno razkazati vi dejansko kodo, in to je veliko kode. Ni potrebe, da znorela. Pogovorila se bova skozi to. 

Pravzaprav ne. To je bila samo psevdokoda. OK, to je bil šele psevdokoda, ki je nekoliko zapletena, ampak to je povsem v redu. Vsakdo po skupaj tukaj? Če je korenina je nična, vrnitev false saj to pomeni nimate ničesar, tudi tam. 

Če koren je n vrednost, tako da, če je zgodi, da je tista, ki jo gledaš, potem boš vrnil true saj veste, da ste jo našli. Ampak, če je vrednost manjša od korena n, ste gre za iskanje levo otrok ali levo krilo, karkoli hočeš, da ga pokličete. In če je vrednost večja od korena, boš poiskati pravo drevo, potem samo zaženite funkcijo z iskanjem znova. 

In če je korenina null, da je ta pomeni, ko ste prišli do konca? To pomeni, da nimate več več listov za iskanje, potem veste, oh, jaz Verjetno je ni tukaj ker ko sem pogledal skozi cela stvar in je ni tukaj, da le ne bi bilo tukaj. 

Ali, da je smiselno, da vse? Torej, to je kot binarnem iskanju ohranjanje Zmogljivosti povezanih seznamov. Ohladimo in tako drugi tip od vas strukture podatkov fantje Lahko poskusite izvajanju na vašem pset, morate le izbrati eno metodo. Toda morda alternativna metoda za hash tabele je tisto, čemur pravimo trie. 

Vse je trie je je posebna vrsta drevesa, ki ima vrednote, ki gredo do drugih vrednot. Torej, namesto da binarna drevo v smislu, da je samo eden stvar, ki se lahko kaže na dvoje, lahko imate ena stvar, ki kažejo na mnogo, mnogo stvari. Vi v bistvu imajo nize znotraj katerega shranite kazalci, ki kažejo na druge nizi. 

Torej vozlišče, kako smo bi definirati Trie se hočemo imeti Boolean, c beseda, kajne? Torej je vozlišče Boolean kot resnična ali neresnična, najprej na čelu da matrika, je to beseda? Drugič, želite imeti kazalce da karkoli so ostali od njih. Le malce zapleteno, malo abstraktno, ampak Bom razložil, kaj to vse pomeni. 

Torej tod na vrhu, če ti imajo niz razglašena že, vozlišče, kjer imate Boolean Vrednost shranjene na prednjem da vam pove, je to beseda? Ali to ni beseda? In potem imate preostanek svojega polja, ki dejansko shranjuje vse možnosti, kaj bi lahko bilo. Tako, na primer, kot na vrhu imate prva stvar, ki pravi, resnična ali false, da ali ne, to je beseda. 

In potem imate 0 do 26 pisma, ki jih lahko shranite. Če bi želel, da tu iskanje za bat, grem na vrh in iščem B. najdem B v moji matrika, in zato vem, OK, je B beseda? B ni beseda, tako da s tem Moram naprej iskati. Grem od B, in gledam na kazalec, da je B opozarja proti in vidim še eno vrsto informacij, enako strukturo, da smo imeli prej. 

In here-- oh, naslednji pismo, v [neslišno] je A. Torej gledamo v tej matriki. Najdemo osmo vrednost, in potem pogledamo, da vidim, oh, hej, je, da je beseda, B-A beseda? To ni beseda. Moramo ohraniti videti. 

In tako potem pogledamo, kje kazalec točk A, in kaže na drug način v ki imamo več vrednost shranjena. In na koncu smo prišli do B-A-T, ki je beseda. In tako naslednjič, ko pogledaš, boš so, da je pregled, ja, to Boolova funkcija je res. In tako v tem smislu, da sva nekako imajo drevo z nizi. 

Torej potem lahko nekako iskanje navzdol. Namesto razprševanja funkcijo in pripisovanje vrednosti, ki jih povezani seznam, lahko samo izvaja načrt trie, ki išče downwords. Res, res zapleteno stvari. Ni enostavno, da razmišljajo o tem, ker sem kot pljuvanje toliko podatkovne strukture ven na vas, vendar ne vse vrste razumeti, kako logika to deluje? 

OK kul. Torej B-A-T, in nato boš iskati. Naslednjič, ko boš da vidim, oh, hej, to je res, Tako vem, da to mora biti beseda. 

Ista stvar za živalski vrt. Torej, tukaj je stvar prav zdaj, če bomo želel iskati živalskem vrtu, prav zdaj, Trenutno zoo ni Beseda v našem slovarju saj, kot lahko vi vidite, prvo mesto, da imamo Boolean return true, je na koncu zoom. Imamo Z-O-O-M. 

In zato je tu, ne bomo dejansko beseda, živalski vrt, v našem slovarju ker je to polje se ne preverja. Torej računalnik ne vemo, da je živalski vrt beseda ker je način, ki smo jih ga shranijo, le zoom tukaj dejansko ima logično vrednost ki je bila obrnil res. Torej, če želimo, da vstavite beseda, zoo, v našem slovarju, Kako bi šel o tem? Kaj moramo storiti, da poskrbite, da naši Računalnik ve, da je Z-O-O beseda in ne prva beseda je Z-O-O-M? 

OBČINSTVO: [neslišno] 

ANDI PENG: Točno, smo želite zagotoviti, da ta tukaj, da Boolova vrednost odkljukali, da je res. Z-O-O, potem bomo, da preveri, tako da smo točno vedeli, hej, zoo je beseda. Bom povedati računalnik, da je beseda tako da ko pregledi računalniške, ve, da je živalski vrt beseda. 

Ker se spomniš vseh teh podatkov strukture, je zelo enostaven za nas reči, oh, bat je beseda. Zoo je beseda. Zoom je beseda. Toda, ko ste ga gradi, računalnik nima pojma. 

Tako da boste morali natančno povedati v katerem trenutku je to beseda? Na kateri točki je ni beseda? In na kateri točki storiti I morali iskati stvari, in na kateri točki moram iti naprej? Vsakdo jasno, da je? Cool. 

In tako potem pride problem, kako bomo iti okoli vstavljanje nekaj da je dejansko ni tam? Torej, kaj je pravkar rekel želimo vstaviti beseda, kopel, v naši trie. Kot lahko Vi vidite kot sedaj vse, kar imamo zdaj, je B-A-T, in ta nova struktura podatkov tam imela vrček, ki opozoril na nič, ker smo prevzeti da, oh, ni besed po B-A-T, zakaj moramo ohraniti ob stvari po tem T. 

Ampak problem nastane, če vas bomo storili želijo imeti besedo, ki prihaja po T-jev. Če imate kopel, ste dogaja, da želijo pravico H. In tako pot bomo za to, da je bomo ustvarili ločen vozlišče. Nismo dodeli ne glede na količino pomnilnika za to novo paleto, in bomo prerazporedijo kazalce. 

Bomo dodelite H, First of all, to null, bomo znebili. Bomo imeli navzdol, se točka H. Če vidimo H, smo ga želeli iti kam drugam. 

In tukaj, lahko nato preverite off ja. Če bomo zadeli H po T, oh, potem vemo, da je ta beseda. Boolean se bo vrnil res. Vsakdo jasno, o tem, kako se je to zgodilo? V REDU. 

Torej v bistvu vse Te podatkovne strukture da smo šli čez danes, nimam res, res hitro šli nad njimi in ne za veliko podrobnost, in to je v redu. Ko začnete zajebavam z njo, boste sledenja, kjer vsi kazalci so, kaj se dogaja v vašem podatkovne strukture, et cetera. Ti bo zelo koristno, in to je do vas, fantje popolnoma ugotovimo, kako želite izvajati stvari. 

In tako pset4, od 5--, da je oh narobe. Pset5 je pravopisne napake. Kot sem že prej povedal, da boš, ko spet prenesete izvorno kodo od nas. Tam se dogaja, da so tri glavne Stvari boste prenesli. Boste prenos slovarjev, lenih in besedil. 

Vse te stvari so se bodisi slovarji besed da želimo, da preverite ali testiranje informacij da želimo, da preverjanje črkovanja. In tako slovarji smo vam gredo da vam dejanske besede, ki jih želimo da si nekako shranite na način, ki je bolj učinkovita kot array. In potem besedila so bo tisto, kar smo vas prosim, da natančno preverite, vse besede so resnične besede. 

In tako so trije bloki programi, ki vam bomo dajejo se imenujejo dictionary.c, dictionary.h in speller.c. In tako vse dictionary.c pa je kaj ste morali izvajati. To obilje besed. To črkovati ček njih, in omogoča, da da vse, kar je pravilno vstavljen. 

diction.h je le knjižnica datoteka da izjavlja, vse te funkcije. In speller.c, bomo, da vam. Vam ni treba spremeniti katerega od njega. Vse speller.c pa je vzel, obremenitve je, nadzira hitrost njej, testi merilo všeč, kako hitro ste sposobni narediti stvari. 

To je Speller. Samo ne igraš z njim, vendar se prepričani, da boste razumeli, kaj to počne. Mi uporabljamo funkcijo imenovano getrusage da testira učinkovitost vašega urok skladiščnik. Vse to pa je v bistvu preskusu z Čas vsega v vašem slovarju, zato poskrbite, da boste razumeli. Bodite previdni, da se ne igraš z njim, ali drugje stvari ne bo deloval pravilno. 

In večino tega izziva je za vidva res spremeniti dictionary.c. Bomo, da vam 140.000 besed v slovarju. Bomo, da vam tekst datoteka, ki ima te besede, in želimo si, da bi lahko organizirali jim v hash tabele ali trie ker ko smo vas prosimo, da urok check-- zamisliti, če ste urok preverjanje, kot Homerjeve Odiseje. To je kot ta velik, velik test. 

Predstavljajte si, če vsak beseda, ki jo je moral pogledati skozi paleto 140.000 vrednot. To bi trajalo celo večnost za vaš stroj teči. To je razlog, zakaj želimo organizirali Podatki v bolj učinkovitih podatkovnih struktur kot je hash tabele ali trie. In potem vidva lahko nekako kdaj iščete dostop stvari lažje in hitreje. 

In zato bodite previdni, da se odpravite trčenja. Boš dobil kup od besed, ki se začnejo z A. Boš dobil kup besed ki se začnejo z B. Do vas Fantje, kako želite, da ga rešiti. Morda je še več učinkovite funkcije razpršitve kot samo prvo črko nekaj, in da je do vas fantje nekako storiti karkoli hočeš. 

Morda želite dodati vse črke skupaj. Morda boste želeli, da je všeč delati čudne stvari da se upošteva število črk, karkoli. Do vaju kaj želite storiti. Če želite narediti hash tabelo, če vas želeli poskusiti Trie, povsem odvisno od vas. Jaz vas bo opozoril pred časom, da je trie je običajno nekoliko težje samo zato, ker tam je veliko več kazalci slediti. Ampak popolnoma do vas. To je veliko bolj učinkovito v večini primerov. Hočeš, da res lahko obdržali Spremljajte vse vaše napotke. Tako kot to isto stvar da sem delal tu. Ko poskušate vstaviti Vrednosti v hash tabele ali izbrisati, se prepričajte, da ste Res sledenja kje je vse, ker to je res enostavno, če sem poskušajo vriniti kot besede, Andy. Naj samo povem, da je to resnična beseda, beseda, andy, v ogromen seznam A besed. 

Če sem slučajno prerazporedijo kazalec narobe, oops, tam gre celoto preostanek mojega povezani seznam. Zdaj je edina beseda, I imeti, je andy, in zdaj vseh ostalih besed v slovar je izgubila. In tako želite poskrbite, da boste slediti vse vaše napotke ali pa boš dobil velike težave v kodi. Draw stvari previdno, korak za korakom. To omogoča veliko lažje razmišljati. 

In nenazadnje, želite, da bi lahko preizkusite svoje delovanje vašega programa na veliki plošči. Če vidva traja poglej CS50 prav zdaj, imamo, kar se imenuje veliki svet. To je ocena stanja najhitreje črkovalnik krat čez vse CS50 zdaj, mislim, da je vrh 10 krat Mislim, osem od njih so zaposleni. Res želimo vama, da nas premagati. 

Vse nas so poskušali izvesti najhitrejši kodo, kot je mogoče. Želimo vama, da bi poskušali izzvati nas in izvajati hitreje od vseh nas lahko. In zato je to res prvič, da smo vas prosi fantje narediti pset da lahko res v kakršni koli metodo ti hočeš. 

Vedno pravim, da je to bolj podobno k rešitvi resničnega življenja, kajne? Sem rekel, hej, moraš to storiti. Zgradite program, ki počne to za mene. Ali jo pa hočeš. Jaz samo vem, da želim na hitro. To je vaš izziv za ta teden. Vi fantje, gremo da vam nalogo. Bomo, da vam izziv. In potem je do vaju popolnoma samo ugotovimo, kaj je najhitrejši in najbolj učinkovit način za izvedbo tega. Ja? 

OBČINSTVO: Ali smo dovolili, da če želel raziskovati hitrejše načine narediti hash tabele na spletu, lahko storimo da, in navajajo številko nekoga drugega? ANDI PENG: Ja, popolnoma v redu. Torej, če vi prebrati spec, tam je linija v spec, ki pravi, da fantje so popolnoma brezplačno za raziskave hash Funkcije o tem, kaj so nekateri od hitrejše hash funkcij teči stvari skozi kot Dokler si citirati to kodo. Torej imajo nekateri ljudje že pogruntal hitre načine početje črkovalniki, hitrega načini shranjevanja podatkov. Popolnoma odvisno od vas, fantje, če vas želijo vzemite, kajne? Prepričajte se, da ste navajanja. Izziv tu res da smo poskušali preizkusiti je zagotoviti, da veste svojo pot okoli kazalca. Kolikor izvajanje dejanska funkcija hash in prihaja do podobnih matematika za to, vidva lahko raziskave karkoli Načini spletu hočete. Ja? 

OBČINSTVO: Lahko navedemo samo s pomočjo [neslišno]? 

ANDI PENG: Ja. Lahko samo v svoj komentar, lahko navedemo, kot so, oh, vzeta iz bla, bla, bla, razpršilna funkcija. Kdo še kakšna vprašanja? Mi dejansko breezed skozi odsek danes. Bom tukaj do odgovoriti na vprašanja, kot dobro. 

Prav tako, kot sem rekel, za pisarne ure nocoj in jutri. Spec ta teden, je dejansko super enostavno in zelo kratko, da se glasi. Jaz bi predlagal ob poglej, samo prebrati skozi celoto njo. 

In Zamyla dejansko vas popelje skozi vsako izmed funkcij morate izvesti, in zato je zelo, zelo jasno, kako narediti vse. Samo se prepričajte, da ste sledenja kazalcev. To je zelo zahtevna pset. 

To ni zahtevna, saj, kot so, oh, koncepti so toliko bolj težko, ali pa boste morali naučiti toliko novih sintaksa pot da si naredil za zadnje pset. To pset je težko, ker obstaja toliko kazalci, in potem je to zelo, zelo enostaven za enkrat imate napako v kodi ne bi mogli najti, če je to bug. 

In tako popolna in popolna vera v vas fantje, da bi lahko premagal našo [neslišno] člankih. Pravzaprav nimam nobenega pisnega rudnik še, ampak sem pisati mine. Torej, medtem ko pišete tvoja, bom pisal rudnik. Bom poskusil, da bi mine hitreje kot tvoje. Bomo videli, kdo ima najhitrejši enega. 

In ja, bom videl vse vidva tukaj v torek. Bom teči nekakšno podobnega delavnici pset. Vse to odsekov teden so pset delavnice, tako da fantje imeli veliko priložnosti za pomoč, uradne ure kot vedno, in res se veselim branje vseh kodo fantje. Imam kvizi tukaj, če vas gor fantje želijo, da pride tistim. To je vse.