[Predvajanje glasbe] SPEAKER 1: Dobro. Vsi dobrodošli nazaj na oddelek. Upam, da ste vsi uspešno odpočili od kviza od prejšnjega tedna. Vem, da je malo nor na trenutke. Kot sem rekel prej, če ste v okviru standardnega odklona, Res ne skrbi, še posebej, za manj udobno oddelku. To je o tem, kje bi morali biti. Če si velik, potem pa super. Čast za vas. In če se počutite všeč, kar potrebujete malo več pomoči, prosim vas prosimo, da se doseže ven kateremkoli od TF. Vsi smo tukaj, da vam pomaga. 

Zato učimo. Zato sem tukaj vsak ponedeljek za vas fantje in v pisarni ur ob četrtkih. Torej, vas prosimo, da mi sporočite Če ste v skrbeh, kaj ali če je kaj na kvizu da boš res všeč obravnavati. 

Torej agenda za danes Vse o podatkovnih struktur. Nekatere od teh so le, da bo prav da se boste seznanili z njimi. Ne smete nikoli izvajati jim v tem razredu. Nekateri od njih se boste, kot je za vaš Speller pset. 

Boste imeli svojo izbiro med hash tabel in poskusih. Torej bomo zagotovo šli čez tiste. To bo zagotovo več vrst strokovne skupine na visoki ravni še danes, čeprav, ker obstaja veliko od njih, in če smo šli v podrobnosti izvajanja na vse to, da ne bi celo dobili s povezanimi seznami in morda malo hash tabel. 

Tako nosijo s seboj. Ne bomo, da se delaš toliko kodiranje tokrat. Če imate kakršna koli vprašanja o tem ali želite videti izvaja ali ga preizkusite sami, Jaz vsekakor priporočam bo study.cs50.net, ki ima primere vseh teh. Da bomo imeli svoje Powerpointi s pojasnili, ki jih nagibajo k uporabi, kakor tudi nekaj programiranja vaje, zlasti za stvari kot povezanih seznamih in binarno drevesa cevi in ​​palice. Tako malo bolj na visoki ravni, ki bi bilo lepo za vaju. 

Torej, s tem, bomo začeli. In tudi, yes-- kvizi. Mislim, da večina od vas, ki so v moj oddelek ima svoje kvize, toda kdo prihaja v ali nekega razloga ne, oni so tukaj v ospredju. 

Tako povezana seznamov. Vem, da te vrste gre nazaj pred kvizu. To je bil teden dni pred da smo se učili o tem. Toda v tem primeru bomo samo iti malo bolj v globino. 

Torej, zakaj bi mi izbrati povezani seznam preko matrike? Kaj jih loči? Ja? 

OBČINSTVO: Lahko razširite povezana Seznam versus fiksne velikosti array je. SPEAKER 1: Right. Niz je fiksna velikost medtem povezani seznam spremenljivo velikost. Torej, če ne vemo, kako veliko želimo shraniti, povezani seznam nam daje velik način za to, ker smo lahko samo dodamo na drugem vozlišču in dodajte na drugo vozlišče in dodamo na drugo vozlišče. Toda kaj lahko trade-off? Ali kdo spomnite kompromis med nizi in povezanih seznamov? Mmhmm? 

OBČINSTVO: Moraš gredo skozi vse poti skozi povezani seznam poiskati element na seznamu. V matriki, lahko samo najti element. 

SPEAKER 1: Right. Torej z arrays-- 

OBČINSTVO: [neslišno]. 

SPEAKER 1: Z nizi, imamo kar se imenuje random access. Pomeni, da tisto, kar je, če želimo kdaj Peta točka seznama ali Peta točka našega matrika, lahko smo samo zagrabiti. Če je povezani seznam, imamo Ponovil skozi, kajne? Torej dostop element pri matrika konstantna čas, ker s seznamom povezano, da bi najverjetneje linearni čas, ker morda naš element je vso pot na koncu. Moramo iskati skozi vse. Torej z vsemi temi podatki strukture gremo ki se porabi malo več časa, kaj so plusi in negativov. Ko bi mi želeli uporabite enega nad drugim? In to je nekako večja stvar vzeti. 

Torej imamo tukaj definicija vozlišča. To je kot enega elementa v naš povezani seznam, kajne? Torej smo vsi seznanjeni z našimi typedef konstruktov, ki smo šli čez v pregledu zadnjič. To je bil v bistvu samo ustvarjanje druga vrsta podatkov, da bi lahko uporabili. 

In v tem primeru, to je nekaj vozlišče da bo imela nekaj celo v. In kaj potem je drugi del tukaj? Kdorkoli? 

OBČINSTVO: [neslišno]. 

SPEAKER 1: Ja. To je kazalec na naslednje vozlišče. Torej, to bi moralo dejansko biti tukaj. To je kazalec tipa vozlišče na naslednjo stvar. In to je tisto, kar Obsega naše vozlišče. Cool. 

Vse je v redu, tako da z iskanjem, saj smo bili samo rekel pred roko, če ste gre za iskanje skozi, moraš dejansko Ponovil prek povezanega seznama. Tako da, če iščemo številko 9, bi morali začeti na naši glavi in ki nas opozarja na začetku našega povezani seznam, kajne? In smo rekli, v redu, pa to vozlišče vsebuje številko 9? Ne? 

Vse je v redu, pojdite na naslednjo. Sledi mu. Ali vsebuje številko 9? No. Sledite naslednjo. 

Zato moramo dejansko Ponovil preko našega povezani seznam. Ne moremo iti neposredno do mesta, kjer je 9. In če vi dejansko želijo videli nekaj psevdo-kodo gor. Imamo nekaj funkcijo iskanja tukaj ki traja in-- kaj je potrebno v? Kaj menite? Tako lahka. Kaj je to? OBČINSTVO: [neslišno]. SPEAKER 1: Število iščemo. Kajne? In kaj bi to ustreza? To je kazalec? 

OBČINSTVO: vozlišče. 

SPEAKER 1: vozlišče na seznam da gledaš, kajne? Torej imamo nekaj vozlišč kazalec tukaj. To je točka, ki se dogaja, da dejansko ponovitev prek našega seznama. Postavili smo ga enak seznam ker je to ravno nastavitev je enaka začetek našega povezani seznam. 

In medtem ko to ni NULL, medtem imamo še vedno stvari v našem seznamu, preverite, če ima to vozlišče Število iščemo. Return true. V nasprotnem primeru ga dopolni, kajne? 

Če je NULL, zapustimo naš while zanko in vrne false ker to pomeni, da nismo ga našli. Ali so vsi dobili, kako to deluje? OK. 

Torej z vstavljanje, si imajo tri različne načine. Moramo dodati, lahko pripnemo in ga lahko vstavite v kompletu. V tem primeru smo bo naredil prepend. Ali kdo ve, kako tiste, trije primeri se lahko razlikujejo? 

Torej prepend pomeni, da si dal je na sprednji strani vašega seznama. Tako, da bi to pomenilo, da ni važno, kaj je tvoj vozlišče, ne glede na to, kakšna je vrednost, boš da bi ga tukaj spredaj, OK? To se dogaja, da je treba najprej element na seznamu. 

Če ga priložiti, da se bo da gredo na zadnji strani vašega seznama. In vstavite v kompletu pomeni, da ste bo dal dejansko v mestu kjer se ohranja vaš povezani seznam razporejene. Again, kako uporabljate tisti, in ko uporabljate jim bo odvisno od vašega primera. Če to ni potrebno treba sortirati, prepend nagiba da je tisto, kar večina ljudi uporabljati, ker si ne iti skozi celoten seznam da bi našli konec, da ga dodate na, kajne? Lahko samo držijo desno. 

Torej bomo šli skozi vstavljanje 1 zdaj. Torej, ena stvar, ki jo bom Priporočam, o tem pset je pripraviti stvari, kot vedno. To je zelo pomembno, da posodobite vaši kazalci v pravilnem vrstnem redu ker če jih posodablja nekoliko v okvari, boš na koncu izgubili dele vašega seznama. 

Tako na primer, v tem primeru, da smo pripoveduje glavo na samo točko 1. Če bomo samo to, da brez shranjevanja to 1, nimamo pojma, kaj 1 je treba poudariti, da je sedaj ker smo izgubili, kar glava opozoril. Torej, ena stvar, da se spomnimo ko delaš prepend je rešiti, kaj je glava kaže na prvi, nato pa jo dodelite, in nato posodobite kaj bi bilo vaše novo vozlišče opozarjajo. V tem primeru, to je eden od načinov za to. 

Torej, če smo to storili na ta način kjer smo samo prerazporedili glavo, izgubimo v bistvu Nostra Celoten seznam, kajne? Eden od načinov za to je, da ima 1 točko Naslednji, nato pa imajo glavno točko 1. Ali lahko narediš nekako kot začasno skladiščenje, kar sem govoril. 

Ampak prerazporeditev Vam nadaljne kazalci v pravilnem zaporedju se bo zelo, zelo Pomembno za to pset. V nasprotnem primeru boste imeli hash tabele ali poskus, ki je le, da bo treba le del besed, ki jih želijo in potem you're-- mmhmm? OBČINSTVO: Kaj je bilo začasno shranjevanje stvar, ki jo je bilo govoriš? SPEAKER 1: začasno skladiščenje. Torej v bistvu drugo Tako boste lahko to storite je shranjevanje glavo nečesa, kot Shranite ga začasno spremenljivko. Dodelite 1 in nato posodobite 1 točko da ne glede na glavo, s katero kažete. Tako je očitno bolj elegantno, ker vas ne potrebujejo začasno vrednost, vendar samo ponujajo še en način, da to storite. In dejansko imajo del kode za to. Tako za povezani seznam, smo dejansko imajo neko kodo. Torej vstaviti tukaj, to je prepending. Torej, to ga vklopi na glavi. 

Torej prva stvar, morate ustvarite novo vozlišče, seveda, in preverite NULL. Vedno dobro. In potem boste morali dodeliti vrednosti. Vsakič, ko ustvarite novo vozlišče, vas Ne vem, kaj je to kaže na naslednjo, tako da boste želeli, da ga zažene na NULL. Če se to ne končajo kar kaže na nekaj, drugje, dobi prerazporediti in to je v redu. Če je prva stvar, na seznamu, ki jih potrebuje izpostaviti, ker NULL da je konec seznama. 

Torej, da ga vstavite, vidimo tu so dodeljevanje naslednjo vrednost našega vozlišča da se ne glede na glavo, ki je tisto, kar smo imeli tukaj. To je tisto, kar smo pravkar storil. In potem smo dodeljevanje glave do točke za našo novo vozlišče, saj se spomnite, Novo je nekaj kazalec na vozlišče, in to je točno tisto, kar glava. To je točno, zakaj smo imajo to puščico accessor. Cool? Mmhmm? 

OBČINSTVO: Ali moramo zagnati nov Naprej najprej NULL, ali lahko samo inicializacijo na glavo? 

SPEAKER 1: New Naslednja mora biti NULL začeti ker ne veste, kjer se dogaja, da se. Tudi to je vrsta tako kot paradigmo. Nastavite, da enaka NULL samo, da bi Prepričajte se, da so zajete vse vaše baze preden to storite tako, da kakršno koli prerazporeditev ste vedno zagotovljeno, da se bo se kaže na določeno vrednost primerjavi kot smeti vrednosti. Ker, ja, moramo določiti Nov dostavo samodejno, ampak to je bolj tako kot dobra praksa inicializacijo na ta način in potem prerazporedil. 

OK, tako da dvojno povezani seznam zdaj. Kaj menite? Kaj je drugačen z dvojno povezani seznam? 

Torej, v naših povezanih seznamov, smo lahko premikate samo v eno smer, kajne? Imamo samo naslednje. Gremo lahko le naprej. 

Z dvojno povezani seznam, bomo lahko tudi umakne nazaj. Torej imamo poleg Številka, ki jih želite shraniti, imamo kje pa opozarja, da poleg in kje smo pravkar prišli. Torej, to omogoča nekaj bolje prečkanje. 

Torej dvakrat povezanih vozlišč, zelo podobni, kajne? Edina razlika je, zdaj smo imajo naslednji in prejšnji. To je edina razlika. 

Torej, če smo bili, da moramo dodati ali append-- smo nimajo nobene kode za ta up here-- ampak, če ste bili, da poskusite in jo vstavite, pomembno stvar se morate, da Preverite, ali ste dodeljevanje tako vaše prejšnje in vaš Naslednji kazalec pravilno. Torej, v tem primeru, bi vam ne le zagnati zraven, ponastaviti prejšnje. Če smo na vrhu seznama smo bi ne samo glava enako novo, ampak naša nova prejšnje naj opozarjajo na glavo, kajne? 

To je edina razlika. In če si želite več vaditi z ti so povezani s seznami, s vstavljanje, z brisanjem z vložkom je v urejenem seznamu Prosimo preverite study.cs50.net. Tam je kup odličnih vaj. Toplo jih priporočam. Želim si, da je imel čas, da gredo skozi njih ampak tam je veliko podatkovnih struktur priti skozi. 

OK, tako razpršene tabele. To je verjetno najbolj koristno bit za vaše pset tukaj, ker boš biti izvajanje enega od teh, ali poskusiti. Res mi je všeč hash tabele. Oni so zelo kul. 

Torej v bistvu, kaj zgodi, je razpršena tabela je, ko res potrebujemo hitro vstavljanje, brisanje in iskanje. To so stvari, ki sva prednostno v hash tabelo. Lahko dobijo precej velik, ampak kot smo videli pri poskusih, obstajajo stvari, ki so veliko večje. 

Ampak v bistvu, vse hash Miza je funkcija hash ki vam pove, katero bucket dati vsak vaših podatkov, vsako od vaših elementov. Preprost način, da razmišljajo o hash tabele je, da je le vedra stvari, kajne? Torej, ko ste sortiranje stvari, ki jih kot prvo črko svojega imena, to je nekako kot hash tabele. 

Torej, če bi bil jaz skupini vidva je v skupine kdor začne ime z več kot tukaj, ali kdor je za rojstni dan je v januarju, februarju, marcu, karkoli, da je učinkovito ustvarjanjem razpršene tabele. To je samo ustvarjanje žlice, ki ste razvrstiti elemente v tako da boste lahko najti jih je lažje. Torej, na ta način, ko moram da bi našli enega izmed vas, Nimam za iskanje skozi vsako od vaših imen. Lahko sem kot, oh, vem, da Danielle rojstni dan je in-- OBČINSTVO: --April. SPEAKER 1: april. Zato sem pogledal v mojo april vedro, in z malo sreče, ona je samo ena tam in moj čas je bil stalnica v tem smislu, ker se, če moram iskati skozi cel kup ljudi, da bo trajalo veliko dlje. Tako razpršene tabele so res le vedra. Enostaven način, da razmišljajo o njih. 

Tako zelo pomembna stvar hash tabela je funkcija hash. Torej stvari, sem govoril o, kot so tvoja prva črka vaše ime ali vaš rojstni dan, mesec, To so ideje, ki Res korelaciji s funkcijo razpršitve. To je samo način odločanja, ki ste bucket ste element gre v, OK? Torej za to pset, si lahko ogledate do precej koli funkcija hash želite. 

Ni nujno, da bo svoje. Obstaja nekaj res kul tisti iz tam, da stori vse vrste nor matematiki. In če želite, da bo vaš črkovalnik super hitro, Jaz bi definitivno poglej v eno od teh. 

Vendar pa obstajajo tudi preprosti tisti, kot compute vsota besed, kot vsaka črka ima številko. Izračunajte vsoto. Ki določa vedro. Imajo tudi enostavno tisti, ki so tako kot vse je tukaj, vse B je tukaj. Koli od teh. 

V bistvu, to samo ti pove, katere matrika indeks vaše element mora iti v. Samo odločanju o bucket-- to je vse razpršilna funkcija je. Torej, tu imamo primer, ki je Samo prvo črko niza da sem pravkar govoril. 

Torej imate nekaj hash, ki je pravkar prva črka vašega godalni minus A, ki vam bo dala nekaj število med 0 in 25. In tisto, kar želite storiti, je poskrbite, da to predstavlja velikost vašega hash table-- koliko vedra obstajajo. Z mnogimi od teh zgoščevalne funkcije, oni dogaja se vrača vrednosti, ki bi lahko biti daleč nad številom žlice da ste dejansko imajo V vašem hash tabele, tako da boste morali, da bi prepričani, in mod tisti. Sicer pa je reči, oh, bi moralo biti v vedru 5000 vendar imate le 30 vedra v vašem hash tabelo. In seveda, vsi vemo, da je bo povzročilo nekaj norega napak. Zato poskrbite, da mod, ki ga velikost vašega hash tabele. Cool. Torej trčenj. So vsi dobro, tako daleč? Mmhmm? 

OBČINSTVO: Zakaj bi bilo vrnete tako veliko vrednost? 

SPEAKER 1: Glede na algoritmu da vaš hash funkcija uporablja. Nekateri od njih bodo storili noro množenje. In to je vse približno pridobivanje enakomerna porazdelitev, da počnejo nekaj res Včasih noro stvari. To je vse. Kaj drugega? OK. 

Torej trčenj. V bistvu, kot sem rekel že prej, v najboljšem primeru vsaka bucket sem pogledati v je dogaja, da imajo eno stvar, tako da mi ni treba gledati na vse, kajne? Jaz niti vedel, da je tam, ali pa je ne, in to je tisto, kar si resnično želimo. Ampak, če imamo več deset tisoč podatkovne točke in je nižja od te številke žlic, bomo imeli Trki kjer na koncu nekaj se dogaja, da imajo na koncu leta bucket, ki že ima element. 

Torej, vprašanje je, kaj storimo v tem primeru? Kaj naj naredimo? Imamo že nekaj tam? Ali smo samo vrgel ven? 

No. Moramo ohraniti oba. Torej način, da smo značilno to, da je kaj? Kakšna je struktura podatkov smo pravkar govorili? OBČINSTVO: Povezan seznam. SPEAKER 1: povezani seznam. Torej sedaj, namesto da vsak od teh vedra le imajo en element, to se dogaja, da vsebujejo povezan seznam elementi, ki so zgoščene v njej. OK, pa vsi nekako dobil to idejo? Ker nismo mogli imeti niz ker ne vemo, kako veliko stvari se bo tam. Povezani seznam nam omogoča, da imajo samo točno številko, ki so zgoščene v tisto vedro, kajne? 

Torej linearni merilni sistem se v bistvu je to idea-- to je eden od načinov, da se ukvarjajo z trčenja. Kaj lahko storite, je, če se v tem Primer je bil berry zgoščen v 1 in že imamo nekaj tam, si nadaljuj, dokler boste našli prazno režo. To je eden od načinov za ravnanje z njimi. Drug način za obravnavanje da je s tem, kar smo pravkar called-- povezana Seznam imenujemo veriženje. 

Tako da je ta ideja deluje, če Vaše hash tabela menite je veliko večja od vaš nabor podatkov ali če vas želeli poskusiti in zmanjšati verižni dokler je to nujno potrebno. Torej, ena stvar je linearna sondiranje seveda pomeni, da vaš hash funkcijo ni tako koristno ker boste na koncu z uporabo Vaše hash funkcijo, dobili do točke, ste linearna sonda navzdol nekem kraju, ki je na voljo. Toda zdaj, seveda, kaj drugega, ki se konča tam, boste morali iskanje še navzdol. 

In tam je veliko več Odhodki za iskanje, da gre v vnesla element v hash tabelo zdaj, kajne? In zdaj, ko greš in poskusite najti berry spet ste tekoč, da ga hash, in to se dogaja, da se reči, oh, poglej v vedro 1, in to ne bo v vedro 1, tako da ste bodo morali za prečkanje Cez teh. Tako da je včasih koristno, vendar v večini primerov, bomo rekli, da veriženje je tisto, kar želite narediti. 

Torej, o tem smo govorili že prej. Imam malo pred sebe. Vendar veriženje je v bistvu, da vsak vedro v hash tabelo je samo povezani seznam. 

Torej še en način, ali bolj tehnični način, da razmišljajo o hash tabele je, da je le niz povezanih seznamov, ki Ko pišete slovar in skušaš ga naložiti, razmišljam o njem kot Niz povezanih seznamov bo veliko lažje za vas, da se zažene. 

OBČINSTVO: Torej hash tabela vnaprej določeno velikost, kot [neslišno] veder? 

SPEAKER 1: Right. Torej ima določeno število vedra, ki jih determine-- ki vidva naj vas prosimo, da igrajo z. To je lahko precej kul da vidite, kaj se zgodi, kot ste spremenili svoje število segmentov. Ampak ja, to je nastavite število veder. Kaj vam omogoča, da se prilega kot veliko elementov, kot jih potrebujete je to ločen veriženje, kjer vas so povezane sezname v posamezne segmente. To pomeni, da si razpršene tabele bo točno velikost da jo je treba, kajne? To je bistvo, povezanih seznamov. Cool. 

Tako da vsakdo tam OK? Vse je v redu. Ah. Kaj se je zgodilo? Res zdaj. Ugani, kdo me ubija. 

OK bomo šli v poskusih, ki so malo nori. Všeč mi je hash tabele. Mislim, da so res kul. Poskuša so kul, preveč. 

Torej, ali kdo se spomnite, kaj je poskusiti? Moral bi šla čez je na kratko predavanje? Se spomnite vrste, kako to deluje? OBČINSTVO: Jaz sem samo prikimava da nismo šel skozi njo. SPEAKER 1: Mi ne gredo nad njim. OK, smo res šli nad njim, zdaj je tisto, kar govoriš. 

OBČINSTVO: To je za arhiviranje drevo. 

SPEAKER 1: Ja. To je iskanje drevo. Super. Torej, ena stvar, ki sem opazil je, da smo iščete na posameznih znakov tukaj, kajne? 

Torej, preden se z našo hash funkcijo, smo iskali na besede kot celote, in zdaj iščemo več na znake, kajne? Torej imamo Maxwell sem in Mendel. Torej v bistvu try-- način, da razmišljajo pri tem je, da je vsak nivo tukaj je niz črk. Torej je to tvoj koren node tukaj, kajne? Ta ima vse znake abeceda za začetek vsako besedo. 

In tisto, kar želite storiti, je recimo, OK, imamo nekaj M besedo. Bomo iskali Maxwell, zato gremo na M. in M ​​točke na celoten drugi niz, kjer je vsak beseda, dokler obstaja je beseda, ki ima kot drugo pismo, Dokler obstaja beseda, ki ima B kot drugo pismo, da bo imela kazalec bo za nekatere naslednjo paleto. 

Verjetno ne beseda, ki MP nekaj, tako v P pozicijo v to matrika, bi bilo prav, je nična. Bilo bi rekli, v redu, ni beseda da je M sledi P, OK? Torej, če razmišljamo o tem, vsak eden od teh manjših stvari je dejansko eden od teh velike nize od A do Ž Torej, kaj lahko ena od stvari, da je nekako povračila poskusiti? 

OBČINSTVO: veliko spomina. 

SPEAKER 1: To je ton spomina, kajne? Vsak od teh blokov tukaj predstavlja 26 mest, 26 elementov array. Tako poskuša priti neverjetno prostor težka. 

Ampak oni so zelo hitro. Tako zelo hitro, vendar res prostor neučinkovito. Nekako morali ugotoviti , katero želite. To so res kul za vaš pset, vendar pa traja veliko pomnilnika, tako da kompromis. Ja? 

OBČINSTVO: Ali bi bilo mogoče da ustanovi poskusiti in potem ko imate vse Podatki v to, da ste need-- Ne vem, če bi bilo to smiselno. Sem se znebi vseh NULL znakov, vendar se je nato si ne bi mogli indeks them-- 

SPEAKER 1: Še vedno jih potrebujete. 

OBČINSTVO: - enak način vsak čas. SPEAKER 1: Ja. Potrebujete znaka NULL, da naj veš, če tam ni beseda tam. Ben si imel kaj želite? OK. Vse je v redu, tako da bomo iti malo bolj v tehnične podrobnosti izza poskusite in delo s primerom. 

OK, tako da je to ista stvar. Ker se v povezani seznam, naša glavna vrsta of-- kaj beseda želim? - kot gradnik je vozlišče. V poskusu, imamo tudi vozlišče, vendar pa je to drugače opredeliti. 

Torej imamo nekaj bool da predstavlja ali besede dejansko obstaja na tej lokaciji, in nato imamo nekaj paleto here-- ali ne, To je kazalec niz 27 znakov. In to je, v tem primeru je to 27-- Prepričan sem, da ste vsi podobni, počakajte, obstaja 26 črk v abecedi. Zakaj imamo 27? 

Torej, odvisno način izvajati to, to je od pset da dovoljeno za opuščaj. Torej, to je, zakaj extra ena. Prav tako boste imeli v nekaterih primeri null terminator je kot eden od Znaki, da je to dovoljeno, in to je, kako preveriti, vidim, če je konec besedi. Če vas zanima, si oglejte Video Kevinova na study.cs50, kakor tudi poka Wikipedija nekaj dobrih virov tam. 

Vendar smo šli skozi le nekako o tem, kako lahko sodelujete prek poskusu če si dal enega. Tako da imamo super preprosto enega tukaj, da ima besede "kij" in "zoom" v njih. In kot smo videli tu gor, ta mali prostor tukaj predstavlja našo bool da pravi, ja, to je beseda. In potem je to naša nizi znakov, kajne? 

Tako smo šli skozi iskanje "bat" v tem poskusu. Torej, začeti na vrhu, kajne? In vemo, da b ustreza Drugi indeks, drugi element v tem polju, ker in b. Torej približno druga. 

In pravi, OK, kul, upoštevajte, da v Naslednja matrika, saj če se spomnimo, to ni, da je vsak od teh dejansko vsebuje element. Vsak od teh nizov vsebuje kazalec, kajne? To je pomembna razlika, da bi. 

Vem, da se to dogaja, da be-- poskusih so res težko priti na prvo, tako da tudi če je to drugič ali tretjič in je še vedno nekako od zdelo težko, Obljubim, da če greš uro Skratka spet jutri, da bomo verjetno lahko veliko bolj smiselno. Je potrebno veliko za prebaviti. Še vedno včasih sem podobno, čakaj, kaj je poskusiti? Kako naj uporabljam to? 

Tako smo b v tem primeru, ki je naš drugi indeks. Če bi imeli, recimo, c ali d ali katera koli druga črka, moramo načrtovati, da se nazaj na kazalo našega polja, ki ustreza. Torej bi vzamemo kot rchar in smo pravkar odštejte off, da ga map v 0 do 25. Vsi so dobri, kako smo map naše znakov? OK. 

Torej, gremo na drugo eno in mi vidim, ja, da ne bi nič. Mi lahko premaknete na to naslednjo paleto. Torej gremo na to naslednje matrike tukaj. 

In smo rekli, v redu, zdaj smo videti, če je tukaj. Je nična ali ne dejansko korak naprej? Torej dejansko premika naj v ta sklop. In smo rekli, v redu, t je naša zadnja črka. Torej gremo na t na indeks. In potem smo korak naprej zato, ker je še eden. In ta pravi, da v bistvu, ja, pa pravi, da je beseda here-- da če boste sledili tem Pot, ki ste prišli na besedo, kar vemo, je "bat". Ja? 

OBČINSTVO: Ali je standardna, da ima to kot indeks 0 in nato še neke vrste na 1 ali da imajo na koncu? 

SPEAKER 1: No. Torej, če se ozremo na naše Izjava tukaj, to je bool, tako da je sama element v vozlišču. Tako da to ni del niza. Cool. Torej, ko smo končali našo besedo in smo na tem polju, kaj želimo narediti je storiti, ček za to besedo. In v tem primeru bi se vrnil ja. 

Torej na to opombo, vemo, da je "živalski vrt" - vemo, saj ljudje, da je "zoo" beseda, kajne? Vendar poskusite tukaj bi pravijo, ne, to ni. In bi rekel, da zato, ker mi ga niso določena kot beseda tukaj. Čeprav smo lahko preide skozi ta sklop, Ta poskus bi rekel, da ne, zoo ni v slovarju saj imamo ne jo označeni kot taki. 

Torej en način, da to that-- oh, oprosti, tale. Torej, v tem primeru, "zoo" ni beseda, vendar je v našem poskusu. Toda v ta, da smo ga želeli uvesti besedo "kopel", kaj se zgodi je sledimo through-- b, a, t. Mi smo v tem polju, in gremo iskati h. 

V tem primeru, ko smo poglej kazalec na uri, to je obrnjena na NULL, OK? Torej, če je to izrecno kaže na drugi matriki, predpostavimo, da so vsi kazalci V tem polju se kaže na null. Torej, v tem primeru, h se kaže na nič, tako da ne moremo storiti ničesar, tako da bi bilo tudi vrniti false, "kopel" ni tukaj. Torej, zdaj smo dejansko bo šel skozi kako bomo dejansko rekli, da "zoo" je v našem poskusu. Kako vstaviti "živalski vrt", v našem poskusu? Torej, na enak način, da smo začeli z naš povezani seznam, začnemo v korenu. Če ste v dvomih, začnite pri koren od teh stvari. 

In bomo rekli, v redu, z. obstaja z, v tem, in to počne. Torej ste se gibljejo na vaš naslednji niz, v redu? In nato na naslednjo, smo rekli, v redu, ne o obstaja? To počne. To še enkrat. 

In tako na našem naslednjem enega, smo rekel, OK, "zoo" že tu obstaja. Vse, kar moramo storiti, je nastaviti ta enaka da velja, da je beseda tam. Če bi sledili vse do prej navedene točke to je beseda, tako da samo nastavljen je enak kot. Ja? 

OBČINSTVO: Torej ne, da pomeni, da je "ba" beseda tudi? 

SPEAKER 1: No. Torej, v tem primeru, "ba" bomo dobili tukaj, bi lahko rekli, je to beseda, in bi bilo še vedno ni. OK? Mmhmm? 

OBČINSTVO: Torej, ko si je beseda in rečeš da, potem je vsebuje iti m? 

SPEAKER 1: Torej, to mora storiti with-- ste nalaganju to. Rečeš "zoo" je beseda. Ko greš na check-- kot, da ste želeli povedati, pomeni "zoo" obstajajo v tem slovarju? Si le, da bo iskanje za "živalski vrt" nato pa preverite, če je beseda. Si ne bo premaknil do m, ker to ni tisto, kar iščete. 

Torej, če bi dejansko želeli dodati "kopel" v tem poskusu, mi bi naredil isto stvar kot smo to storili z "živalski vrt" razen da bomo videli, ko bomo poskusiti in priti do h, da ne obstaja. Torej si lahko zamislite, da je to težaven dodati novo vozlišče v povezani seznam, zato bi morali dodati še eno eden od teh nizi, kot tako. In potem, kaj mi je pravkar nastavili h element te matrike, ki kažejo na to. 

In potem, kaj bi želeli narediti tukaj? Dodajte je enaka true ker je beseda. Cool. Vem. Poskuša niso najbolj razburljivo. Verjemi mi, vem. 

Torej, ena stvar, za uresničitev s poskusih Rekel sem, oni so zelo učinkoviti. Tako smo videli prevzamejo tono prostora. Oni nekako zmedeno. Torej, zakaj bi si kdaj uporabiti to? Uporabljamo jih zato, ker oni neverjetno učinkovit. 

Torej, če ste že kdaj iskali do besede, ste le omejena z dolžino besede. Torej, če iščete Beseda, ki je dolga pet, ste le kdaj bodo morali da največ petih primerjavah, OK? Tako da si lahko v bistvu konstantna. Like vstavljanja in lookup so v bistvu konstantna čas. 

Torej, če lahko kdaj nekaj v stalnem času, da je tako dober, kot je dobil. Ne morete dobiti boljše od stalen čas za te stvari. Tako, da je ena izmed ogromne pluse poskuša. 

Vendar je veliko prostora. Tako da boste nekako morali odločiti, kaj je bolj pomembno za vas. In na današnjih računalnikih, Prostor, ki je lahko poskus traja Mogoče ne vpliva ste, da je veliko, ampak morda imate opravka z nečim da ima veliko, veliko več stvari, in poskus samo ni smiselno. Ja? 

OBČINSTVO: Počakajte, da imate 26 Črke v vsak posameznik? 

SPEAKER 1: mmhmm. Ja, imate 26. Imate nekaj je beseda dvojno podajo, nato pa imate 26 kazalcev v vsaki eno. In oni point-- 

OBČINSTVO: In vsak 26, pa imajo vsak 26? 

SPEAKER 1: Da. In zato, kot si lahko glej, se širi zelo hitro. Vse je v redu. Tako bomo dobili v drevesih, ki Počutim se, kot je lažje in bo verjetno biti lepo Oddih od poskusih se. Zato upajmo, da večina od vas Videl drevo prej. Ni všeč lepa tisti zunaj, ki sem Ne vem, če je kdo šli na prostem v zadnjem času. Šel sem pobiral jabolka ta vikend, in oh moj bog, bilo je lepo. Nisem vedel, listje mogoče videti, da je lepa. 

Torej je to samo drevo, kajne? To je samo nekaj vozlišč, in opozarja na kup drugih vozlišč. Kot vidite tukaj, je to nekakšna stalnica. Vozlišča, ki kaže, da vozlišča je nekako Bistvo številnih podatkovnih struktur. To je odvisno samo od tega, kako smo imajo jih opozarjajo na medsebojno in kako prečkanje skoznje in kako smo vstavite stvari, ki določa, njihove različne značilnosti. 

Torej samo nekaj terminologije, ki sem jih prej. Torej koren je vse, kar je v samem vrhu. to je, kjer smo se vedno začne. Lahko si o njej mislijo kot vodja tudi. Ampak na drevesih, smo nagnjeni k nanašajo na to kot root. 

Karkoli na spodnjem here-- na zelo, zelo bottom-- so menili listi. Torej gre skupaj z Celotna drevo stvar, kajne? Listi so na robovih drevo. 

In potem imamo tudi nekaj Pogoji govoriti o vozliščih v zvezi seboj. Tako da imamo starše, otroci, bratje in sestre. Torej v tem primeru 3 je matično 5, 6 in 7. Tako staršev, kar je en korak nad karkoli vas zanima sklicevanjem, tako da samo kot družinsko drevo. Upajmo, da je to vse malo bit bolj intuitiven kot poskusih. 

Bratje in sestre so vse, ki imajo isti nadrejeni, kajne? Oni so na istem nivoju tukaj. In potem, ko sem bil rekel, otroci so samo kar je en korak pod vozlišče v vprašanju, OK? Cool. Torej, binarno drevo. Lahko vsakdo nevarnost ugibati na enem od značilnosti binarnega drevesa? 

OBČINSTVO: Max dva lista. 

SPEAKER 1: Right. Torej max dveh listov. Torej, v tem enem poprej smo imeli tole da je imel tri, ampak v binarnem drevesu imate max dveh otrok na starša, kajne? Še en zanimivo lastnost. Ali kdo ve za to? Dvojiško drevo. 

Tako da bo binarno drevo ima vse na the-- ta ni sorted-- vendar v sortirano binarno drevo, vse, kar je na desni strani večja od staršev, in vse na levi je manj od staršev. In da je bil kviz Vprašanje prej, tako da dobro vedeti. Torej način opredeljuje, spet imamo eno vozlišče. To izgleda zelo podobno kot kaj? Dvakrat 

Publika: Povezan seznami 

SPEAKER 1: dvojna povezani seznam, kajne? Torej, če želimo zamenjati to s prejšnjo in naslednjo, to bi bilo dvojno povezani seznam. Toda v tem primeru smo dejansko imajo levo in desno in to je to. Drugače pa je popolnoma enak. Še vedno imamo element iščete, in imate le dve kazalci dogaja, da karkoli je naslednji. Ja, tako dvojiško iskalno drevo. Če opazimo, vse na tukaj je večja than-- ali takoj vse da tukaj je večja od vsega tu je manj kot. 

Torej, če bi preiskava skozi to, bi morali videti zelo blizu binarnega iskanja tukaj, kajne? Razen namesto gledanja na polovici matrike, smo samo gledaš na bodisi na levo strani ali na desni strani drevesa. Tako da dobi malo enostavnejši, mislim. 

Torej, če je vaš korenski NULL, Očitno je to samo false. In če je tam, očitno je res. Če je manj kot iščemo levo. Če je več, iščemo pravico. To je natanko tako kot binarno iskanje, samo drugačna struktura podatkov da smo s pomočjo. Namesto matrike, to je samo binarno drevo. 

OK, nizov. In tudi, da izgleda, kot da Morda imajo malo časa. Če bomo to storili, sem vesel, da gredo čez vse to še enkrat. OK, tako nizov. Ali kdo spomnite kaj stacks-- vse značilnosti dimnika? 

OK, tako da je večina od nas, mislim, jesti v jedilnico halls-- toliko, kot morda ne bomo želeli. Ampak seveda, si lahko zamislite skladovnice dobesedno le kot skladovnice pladnjev ali kup stvari. In kaj je pomembno zavedati, je, da je something-- značilnost da rečemo temu by-- je LIFO. Ali kdo ve, kaj to pomeni? Mmhmm? 

OBČINSTVO: zadnji noter, prvi ven. 

SPEAKER 1: Right, zadnji noter, prvi ven. Torej, če vemo, če bomo zlaganje stvari up, najlažje, da zgrabite off-- in morda edina stvar, ki jo lahko zgrabi off, če naš dimnik je velik enough-- je, da je zgornji del. Karkoli je tako dal na last-- kot vidimo tukaj, karkoli je potisnilo na najbolj recently-- je bo najprej stvar, ki jo pop off, OK? 

Torej, kaj imamo tukaj je drugo typedef struct. To je res samo všeč crash seveda v podatkovno strukturo, tako da je veliko vrže na vas. Vem. Torej še en struct. Bravo struktur. 

In v tem primeru, to je nekaj pointer na matriko, ki ima nekaj sposobnosti. Torej to pomeni našo skladovnico tukaj, kot naš dejanski matriki da je gospodarstvo naše elemente. In potem tukaj imamo nekaj velikosti. 

In ponavadi, ki jih želite obdržati tir, kako velik je vaš dimnik kajti to, kar se dogaja, da se omogoči vi storiti je, če veš, velikost, vam omogoča, da reči, OK, sem na zmogljivosti? Lahko dodam še kaj? In to vam pove tudi, kjer je vrh vaših žetonov je, tako da boste vedeli, kaj vas lahko dejansko vzlet. In to dejansko dogaja, da biti malo bolj jasno tukaj. 

Torej Pritisni, eno stvar, če vas bili kdaj izvajati potiskanje, kot sem pravkar rekel, tvoja Sveženj ima omejeno velikost, kajne? Naša paleta imela nekaj zmogljivosti. To je niz. To je fiksna velikost, zato moramo se prepričajte, da smo ne daje več v našo paleto, kot smo dejansko imajo prostor. 

Torej, če ste ustvarjanju potiskanje funkcija, prva stvar, kar morate storiti je reči, OK, imam prostor v mojem kupu? Ker če jaz ne, žal, Ne morem shraniti element. Če bi to storili, potem želite shraniti je na vrhu kupa, prav? 

In zato imamo spremljate naše velikosti. Če ne bomo spremljali naše velikosti, ne vemo, kje bi ga dal. Ne vemo, kako veliko stvari v naši matriki že. Tako kot očitno obstajajo načini da morda to lahko narediš. Lahko inicializacijo vse na NULL in nato preverite za najnovejšo NULL, vendar je veliko lažje, stvar je samo reči, OK, slediti velikosti. Kot sem vedel, da sem imel štiri elemente v mojem polju, zato naslednja stvar da smo se na, smo dogaja, da shranite na indeksu 4. In potem, seveda, to pomeni, da ste uspešno potisnil nekaj na vaših žetonov, ki jih želimo povečati velikost tako da boste vedeli, kje ste tako da lahko push več stvari naprej. 

Torej, če se trudimo, da pop nekaj off dimnika, kaj bi lahko prva stvar da želimo preveriti? Ste poskušali vzeti nekaj off vaših žetonov. Ali ste prepričani, da je nekaj v vašem kupu? No. Torej, kaj bi mi želeli preveriti? 

OBČINSTVO: [neslišno]. SPEAKER 1: Preverite, ali velikost? Velikost. Zato želimo, da preverite, če je naša velikost je večja od 0, OK? In če je, potem želimo zmanjšati naša velikost z 0 in se vrniti, da. Zakaj? 

V prvem smo potiskanje, smo ga potisnili na velikost in nato posodobljeno velikosti. V tem primeru smo pomanjšanja velikosti in nato vzlet, je skubljenje iz naše paleto. Zakaj bi mi to naredil? Torej, če imam eno stvar na mojem kupu, kaj bi bilo moje velikosti na tej točki? 1. 

In kjer je element 1 shranjeno? Na kaj indeks? OBČINSTVO: 0. SPEAKER 1: 0. Torej v tem primeru smo vedno morali sure-- namesto vračanja velikost minus 1, ker smo vemo, da je naš element bo shranjeno na 1. manj glede na naš velikost je ta samo skrbi zanj. To je nekoliko bolj eleganten način. In smo samo pojemanje Nostra velikosti in se nato vrne velikost. Mmhmm? 

OBČINSTVO: Mislim, da samo na splošno, zakaj bi ta struktura podatkov koristna? 

SPEAKER 1: To je odvisno od vaše kontekstu. Torej za nekatere teorije, če delate with-- OK, Naj vidim, če je koristno ena da je koristno, da več kot zunaj za CS. Z dimniki, kadarkoli boste potrebovali slediti nekaj, je nedavno dodano ko boste želeli uporabiti kup. 

In ne morem razmišljati o dobro Primer, ki prav zdaj. Ampak ko najnovejša stvar, ki je najbolj pomembno za vas, da je, ko kup se dogaja, da je koristen. Poskušam razmišljati, če tam je dobra za to. Če pomislim na dober primer v naslednjem 20 minut, bom zagotovo vam povem. 

Ampak na splošno, če je kaj, kot sem rekel večina, kjer najnovejša je najbolj pomembno, da je kjer je kup prihaja v igro. Ker so čakalne vrste so vrste nasprotno. In vsi mali psi. Ali ni to super, kajne? Počutim se, kot da bi moral samo še zajček video desno v sredini Oddelek za vas ker je to intenziven odsek. 

Tako čakalne vrste. V bistvu čakalna vrsta je kot črto. Vidva Prepričan sem, da uporaba tega vsak dan, tako kot v naši jedilnici. Zato moramo iti v in dobili naše pladnje, sem da boste morali čakati v vrsti Močan in dobili hrano. 

Torej razlika tukaj je, da je ta FIFO. Torej, če LIFO je bil nazadnje v prvi ven, FIFO je prvi noter, prvi ven. Torej, to je, če karkoli si dal na prvi je vaša najpomembnejša. Torej, če ste čakali v line-- lahko vam si, če si šel v pojdi novi iPhone in da je sveženj kadar Zadnja oseba v skladu najprej dobil, bi ljudje pobijali med seboj. 

Torej FIFO, da smo vsi zelo dobro poznamo z v resničnem svetu tu in vse to ima opraviti z dejansko nekako poustvariti to celotno linijo in čekanjem strukturo. Torej, ker se z dimnika, imamo potiskanje in pop. S čakalno vrsto, imamo enqueue in dequeue. Torej enqueue v bistvu pomeni, Povedano na hrbtu, in dequeue sredstva vzeti off od spredaj. Torej naša podatkovna struktura je malo bolj zapletena. Imamo še eno stvar za sledenje. 

Torej, brez glave, ta je točno kup, kajne? To je enako strukturo kot dimnika. Edina stvar drugačna zdaj smo imam glavo, ki je tisto, kar misliš, se dogaja, da spremljate? 

OBČINSTVO: prvi. 

SPEAKER 1: Right, Prva stvar, ki smo se v. Vodja naše vrste. Kdor je prvi na vrsti. Vse je v redu, tako da če bomo enqueue. Spet s katerokoli Te podatkovne strukture, saj imamo opravka z vrsto, moramo preveriti, če imamo prostor. 

To je nekako tako kot mi pove, fantje, če odprete datoteko, morate preveriti za nično. S katerimkoli izmed teh skladovnic in čakalne vrste, morate da vidim, če je prostor, ker smo ki se ukvarjajo z določeno velikostjo polja, kot smo videli here-- 0, 1 vse do 5. Torej, kaj bomo storili v tem primeru je prijava da vidim, če imamo še prostor. Naša velikost manjša od zmogljivosti? 

Če je tako, moramo jo shranite na rep in bomo posodobiti naše velikosti. Torej, kaj bi rep biti v tem primeru? Ni je izrecno napisano ven. Kako bi bilo shranjevanje? Kaj bi repa? 

Tako da je sprehod skozi ta primer. Torej, to je matrika velikosti 6, kajne? In imamo zdaj, naša velikost je 5. In ko smo ga v, gre da gredo v peto indeks, kajne? Tako shranite na repu. 

Drug način, da napišete rep bi samo biti naša paleta na indeksom velikosti, kajne? To je velikost 5. Naslednja stvar, ki se dogaja, da gredo v 5. Cool? OK. To je nekoliko bolj zapletena postane ko smo začeli zajebavam z glavo. Ja? 

OBČINSTVO: Ali to pomeni, da smo bi razglasila niz, ki je pet elementov dolgo in Nato smo dodali na njej? 

SPEAKER 1: No. Torej v tem primeru, to je skladovnica. To bi se razglasi kot polje velikosti 6. In v tem primeru smo samo še eno vesoljsko levo. 

OK, tako da ena stvar je v tem primeru, če je naša glava je na 0, Nato smo le lahko dodate na velikost. Vendar pa postane malo bolj zapleteno saj pravzaprav so nimajo drsnika za to, da jaz grem pripraviti eno, ker to ni tako enostavno, ko vas začetek znebi stvari. Torej, ker se z dimnika si le kdaj skrbeti, kaj velikost Ko ste dodali nekaj na, z vrsti boste morali narediti Prepričajte se, da je vaša glava obračuna, saj kul stvar o čakalnih vrst je, da če nisi v vlogi, lahko dejansko narediti, da se ovije okoli. 

OK, tako da ena thing-- oh, To je grozno kreda. Ena stvar, da razmisli je tako. Bomo pač pet. OK, tako da bomo pravijo, glava je tukaj. To pomeni 0, 1, 2, 3, 4. 

Glava je tam, in prosim, stvari v njih. In želimo dodati nekaj v, kajne? Tako stvar, da moramo vedo, da je glava vedno dogaja, da se premaknete na ta način in potem zanka nazaj okoli, OK? 

Tako da je ta čakalna vrsta je prostora, kajne? To je prostor, v samem začetku, nekako nasprotje tega. Torej, kaj moramo storiti, je, da smo moramo izračunati rep. Če veste, da je vaš glava ne premakne, rep je samo tvoja matrika na Indeks velikosti. 

Toda v resnici, če uporabljate čakalno vrsto, tvoja glava se posodablja. Torej, kaj morate storiti, je, dejansko izračunati rep. Torej, kaj moramo storiti, je ta formula Tukaj, kar jaz grem, da te Fantje pomislite, in potem bomo govorili o tem. Torej, to je zmogljivost. 

Torej, to bo dejansko vam način, da to storite. Ker v tem primeru, kaj? Naš vodja je na 1, naša velikost je 4. Če bomo mod, ki ga 5, dobimo 0, ki je, če bi se morali vhod je. 

Torej v naslednjem primeru, če bi to naredili, smo rekli, v redu, dajmo dequeue nekaj. Mi dequeue to. Mi ta element, kajne? 

In zdaj naša glava je obrnjena tukaj in želimo dodati v druge stvari. To je v bistvu nazaj naše linije, kajne? Čakalne vrste se lahko ovije okoli polja. To je ena od glavnih razlik. Stacks, si tega ne more storiti. 

S čakalnimi vrstami, lahko ker vse, kar zadevah je, da veš, kaj je bila nazadnje dodali. Ker je vse, kar se dogaja, da se doda v ta leftward smer, v tem primeru, nato pa ovijte okoli, lahko še naprej uvaja nove elemente na prednjem delu matrike ker to ni res prednja matrike več. Lahko si misliš o začetku Niz kot kje dejansko je tvoja glava. 

Torej, ta formula je, kako si izračunajte svoj rep. Ali je to smiselno? OK. OK, dequeue, nato pa vi imate 10 minut mi zaprosijo katerega koli vprašanja, ki pojasnjujejo hočeš, ker vem, da je noro. 

Vse je v redu, tako da v istem way-- Ne vem, če se vi opazili, vendar CS je vse o vzorcih. Stvari so precej Enako, le z drobnimi poteg. Torej isto stvar tukaj. Moramo preveriti, da vidim, če bomo dejansko imeti nekaj v naši vrsti, kajne? Reči, OK, je naša velikost je večja od 0? Cool. 

Če bomo to storili, potem gremo naši glavo, ki je tisto, kar sem dokazala tukaj. Mi posodobitev naše glave, da je eden več. In potem smo pojemanje naše Velikost in vrne element. 

Tam je veliko bolj konkreten koda study.cs50.net, in sem zelo priporočam dogaja skozi njo, če imate čas, tudi če je samo psevdo-kodo. In če hočete govoriti z da z mano ena na ena, prosim povej mi, vem. Jaz bi z veseljem. Podatkovne strukture, če vzamete CS 124, boste vemo, da podatkovne strukture dobili zelo zabavno in to je šele začetek. 

Zato vem, da je težko. To je OK. Borimo se. Sem še vedno. Torej, ne skrbite preveč o tem. 

Ampak to je v bistvu Vam nadaljne crash seveda v podatkovnih struktur. Vem, da je veliko. Ali obstaja kaj, da smo bi rad šel še enkrat? Karkoli želimo govoriti skozi? Ja? 

OBČINSTVO: Za ta primer, tako Nov rep je na 0 nad tem? SPEAKER 1: Da. OBČINSTVO: OK. Torej gre skozi, boš pa 1 plus 4 or-- 

SPEAKER 1: Torej ste rekli, ko želimo iti to ponovi? OBČINSTVO: Ja. Torej, če ste bili kipec out--, kjer so vam izračun rep od v tem? 

SPEAKER 1: Torej rep je in-- sem to spremenila. Tako da v tem primeru bi bilo to Niz smo gledaš, OK? Torej imamo stvari v 1, 2, 3 in 4. Torej imamo glava je enaka 1 pri ta točka, in naša velikost je enaka 4 Na tej točki, kajne? 

Vi vsi strinjamo, da je temu tako? Torej mi glavo plus velikost, ki nam daje 5, in potem bomo mod s 5. Smo dobili 0, kar nam pove, da je 0 kjer je naša rep, kjer imamo prostor. 

OBČINSTVO: Kaj je zgornja meja? 

SPEAKER 1: zmogljivost. Žal mi je. Tako, da je velikost vašega array. Ja? 

OBČINSTVO: [neslišno] pred vrnemo element? 

SPEAKER 1: Torej gremo glavo ali vrnitev trenutek? Torej, če gremo eno, pojemanje velikost? Počakaj. Definitivno sem pozabil drugo. Pozabi. Ni drugega formulo. Ja, bi si želeli, da se vrnete glava in nato premakniti nazaj. 

OBČINSTVO: OK, saj je na ta točka, je glava na 0, in potem se želite vrniti indeks 0 in nato glava 1? 

SPEAKER 1: Right. Mislim, da obstaja še en Formula nekako takole. Ne morem imeti na vrhu moje glave kot Ne želim, da bi vam napačnega. Ampak mislim, da je popolnoma veljavna recimo, OK, shranite to element-- karkoli element glave je is-- pojemanje vaš velikost, premaknite nad glavo, in povratek ne glede na ta element. To je povsem veljavna. OK. Počutim se, kot da to ni kot most-- niste dogaja, da hodi ven podobno, ja, vem poskuša. I got to vse. To je v redu. Obljubim. Ampak podatkovne strukture so nekaj, je potrebno veliko časa, da se privadite. Verjetno ena najtežje stvari, mislim, da je v teku. 

Torej je vsekakor potrebno ponavljanje in je videti at-- I ne vem, povezane sezname dokler sem preveč z njimi, na enak način, da nisem Res razumem kazalce dokler sem moral naučiti dvoje let in naredite svoje lastne psets z njim. To traja veliko ponovitvene in časa. In na koncu, da bo vrsta kliknite. 

Toda v tem času, če imate neke vrste razumevanja na visoki ravni, kar to storiti, njihove prednosti in cons--, ki je kaj res navadno poudarjajo, zlasti v intro tečaj. Všeč mi je, zakaj bi uporabili poskusite čez array? Všeč mi je, kakšni so pozitivni in negativov vsake od teh? 

In razumevanje kompromise med vsako od teh struktur je tisto, kar je zdaj veliko bolj pomembno. Tam lahko ena nora Vprašanje, ali dva, da je dogaja, da vas prosim, da izvaja potiskanje ali izvajajo pop ali enqueue in dequeue. Toda za večino del, ki ima višjo raven razumevanja in več o je intuitivno razumevanje bolj pomembna kot dejansko da bi mogli izvajati. 

To bi bilo res super, če vas vse lahko greš ven in pojdi izvajati poskusiti, vendar smo razumeli, da to ni nujno najbolj razumna stvar prav zdaj. Ampak jih lahko v vašem pset, če želite da, in potem boste dobili prakso, in potem morda boste Res razumem. Ja? 

OBČINSTVO: OK, tako da so tisti, ki smo mišljen za uporabo v pset? Ali moram uporabiti eno od njih? SPEAKER 1: Da. Torej imaš izbiro. Mislim, da v tem primeru, ne moremo govorimo o pset malo ker sem tekel skozi to. Torej v vašem pset, imate Izbira poskusih ali hash tabel. Nekateri ljudje bodo poskušali in uporabo cvet filtrov ampak tisti, tehnično ni pravilen. Zaradi njihove verjetnostnega narave, dajejo včasih napačen. Oni so kul pogled v, čeprav. Toplo priporočam iščejo pri njih vsaj. Vendar pa imate možnost izbire med hash tabele in poskusu. In to se dogaja, da je tam, kjer naložite v slovarju. 

In boste morali izbrati Vaše hash funkcija, boste morali izbrati, koliko žlice, ki jo imajo, in se bo spreminjala. Všeč mi je, če imate več vedra, Mogoče bo to teči hitreje. Morda pa ste zapravljaš Veliko prostora, da je tako, čeprav. Moraš ga pogruntal. Mmhmm? 

OBČINSTVO: Prej ste rekli, da je moremo uporabljati drugih hash funkcije, da mi ne bi bilo treba ustvariti funkcijo razpršitve? 

SPEAKER 1: Ja, prav. Torej dobesedno za vaš hash funkcijo, kot google "funkcija hash" in si za nekaj kul narave. Vi se ne pričakuje, da gradijo lastne zgoščevalne funkcije. Ljudje preživijo svoje tez o teh stvareh. 

Torej, ne skrbite o gradnji svoje. Našli eno na spletu, da začnete z. Nekatere od njih boste morali manipulirati malo Da bi se prepričali vrste povratnih ujemajo in malenkosti, tako da v začetku, Jaz bi priporočal uporabo nekaj zelo enostavno, da morda le hashes na prvo črko. In potem, ko imate to delo, vgrajen hladilnik funkcijo razpršitve. Mmhmm? 

OBČINSTVO: Bi poskusite biti ali učinkovite, vendar le težje, like-- 

SPEAKER 1: Torej, poskusite, mislim, je intuitivno težko izvajati vendar je zelo hiter. Vendar pa je več prostora. Again, lahko optimizirate, tako tistih, ki v različne načine in obstajajo načini to-- OBČINSTVO: Kako smo ocenjena na to? Ali matter-- 

SPEAKER 1: Torej ste sortirani običajen način. Boš razvrsti na design. Kakorkoli boste to storili, boste želeli prepričajte, da je tako eleganten kot je mogoče in tako učinkovita, kot je mogoče. Ampak, če se odločite poskusiti ali hašiš miza, dokler deluje, smo zadovoljni s tem. In če boste uporabili nekaj, kar hashes na prvo črko, da je v redu, kot morda podobno zasnovo-modrih. Mi smo tudi dosegli točka v tem semester-- Ne vem, če vas Fantje noticed-- če ste pset stopnje upada malo zaradi oblikovanja in drugih malenkosti, To je popolnoma v redu. To je že do točke, kjer se vaš programi postajajo vse bolj zapletena. Obstaja več krajih lahko izboljšati. 

Torej, to je povsem normalno. Saj ne, da ste tem slabše od vaše pset. To je samo bomo pa težje od tebe. Tako da vsi že na občutek. Pravkar sem se razvrstijo vse vaše psets. Vem, da vsakdo se počuti. 

Zato ne bodite zaskrbljeni zaradi tega. In če imate vprašanja o predhodna psets ali načinov, kako lahko izboljšajo, Trudim se in komentiraj specifična mesta, ampak včasih je prepozno in sem se naveličal. Ali obstajajo še kakšne druge stvari, o podatkovne strukture? Prepričan sem, da ste vi v resnici ne želim več govoriti o njih, ampak, če obstajajo, sem vesel, da iti nad njimi, kakor tudi karkoli iz predavanja ta preteklem teden ali prejšnji teden. 

Vem, prejšnji teden je bilo vse ocene, tako da smo lahko preskočijo nekaterih pregleda iz predavanja. Vsa druga vprašanja, mi lahko odgovorite? OK, v redu. No, fantje ven 15 minut prej. 

Upam, da je to semi-koristno vsaj, in jaz vam bomo videli fantje naslednji teden, ali četrtek uradnih ur. Ali obstaja zahteva za prigrizke za naslednji teden, to je stvar? Ker sem pozabil sladkarije danes. In sem prinesel sladkarije zadnji teden, vendar je bilo Columbus Day, tako da je bilo tako kot šest ljudi, ki so je imel štiri vrečke bonbonov zase. Jaz lahko prinese zvezdne še enkrat, če ti je všeč. Zvezdne? OK, zveni dobro. Imajo velik dan, fantje.