[Predvajanje glasbe]
>> DAVID Malan: To je CS50.
In to je hkrati začetek in end-- kot literally-- skoraj konec
od šestih tedna.
>> Mislil sem, da sem deliti malo zabavno dejstvo.
To sem potegnil iz Nabor podatkov za preteklo semester.
Morda se boste spomnili, da vas prosimo za vsak set oblika p, če ste gledal na spletu
ali če ste se udeležili osebno.
In tukaj je podatek.
Torej, danes je zelo predvidljiv.
Vendar smo želeli, da bi porabili malo časa s tabo vseeno.
Bi kdo rad Domnevamo, zakaj je to Graf je tako jaggy, gor dol, gor dol,
tako dosledno?
Kaj vsak od vrhov in korita predstavljajo?
>> OBČINSTVO: [neslišno]
DAVID Malan: Indeed.
In bolj zabavno, bog ne daj, imamo eno predavanje v petek
na začetku semestra, da je tisto, kar vidimo, se zgodi.
Torej, danes, vzamemo v malo Več o podatkovnih struktur.
In da bi vam bolj trdna duševno model za težave ob petih,
ki je zdaj ven.
Pravopisne napake, si bomo pri čemer vam izroči besedilno datoteko nekaj 100.000
plus angleške besede, in boste imeli
da ugotovimo, kako spretno jih naložite v spomin, v RAM, z uporabo nekaterih podatkov
Struktura po vaši izbiri.
>> Zdaj ena taka struktura podatkov lahko bo, vendar verjetno ne bi smelo biti,
precej poenostavljeno povezani seznam, ki smo jo uvedli zadnji čas.
In povezani seznam imeli vsaj eno prednost pred matrike.
Kaj je še ena prednost povezani seznam verjetno?
>> OBČINSTVO: Insertion.
>> DAVID Malan: Insertion.
Kaj misliš s tem?
>> OBČINSTVO: Anywhere skupaj seznam [neslišno].
>> DAVID Malan: Dobro.
Tako da lahko vstavite element kadar je to želiš v sredini seznama
ne da bi shuffle ničesar, ki smo sklenili, v našem razvrščanje
razprave, ni nujno dobra stvar,
ker je potreben čas za dejansko premikanje vseh teh ljudeh levo ali desno.
In tako s povezani seznam, lahko Samo razporediti s funkcije malloc, novo vozlišče,
in nato posodobite par pointers-- dva, tri operacije max--
in smo sposobni razparal nekoga v kjerkoli v seznamu.
>> Kaj je koristno o povezanem seznamu?
Ja?
>> OBČINSTVO: [neslišno]
DAVID Malan: Popolna.
Popolna.
To je res dinamična.
In da ne boš storila, vnaprej, do neke fiksne velikosti
kos pomnilnika, kot si ti bi morali da z matriko, pozitivni katerega
je, da lahko dodeli vozlišč le na Povpraševanje tem uporabljajo samo toliko prostora
kot ga dejansko potrebujete.
V nasprotju s paleto, boste morda nenamerno dodeli premalo.
In potem je le, da bo da so bolečine v vratu
prerazporediti novo večjo paleto, kopiranje vse, kar je več, osvobodi starega niz,
in nato premaknite o vašem podjetju.
Ali še huje, lahko dodeli pot več pomnilnika, kot ga dejansko potrebujejo,
in tako boste imeli zelo redko poseljenih matriko, tako rekoč.
>> Tako povezani seznam vam to Prednosti dinamičnosti in fleksibilnosti
z vstavki in izbrisi.
Ampak zagotovo mora biti cena.
Pravzaprav je eden od tem raziskati kvizu ničelno
je nekaj kompromise smo videli doslej.
Torej, kaj je plačana cena ali Slabost povezanega seznama?
Ja.
>> OBČINSTVO: Ne bralno.
>> DAVID Malan: Ne bralno.
Ampak koga briga?
Bralno ne zveni prepričljivi.
>> OBČINSTVO: [neslišno]
DAVID Malan: Točno tako.
Če želite imeti nekatere algorithm--
in mi dejansko predlagala dvojiško iskalno zlasti kar
je tista, ki smo jih uporablja precej bit-- Če nimate naključno dostopa,
ne morete storiti, da preprosto aritmetiko iskanja kot srednji element
in skakanje pravica do njih.
Boste namesto tega morali začeti na prvi element in linearno iskanje z leve
na desno, če želite, da bi našli srednji ali kateri koli drug element.
>> OBČINSTVO: Verjetno traja več pomnilnika.
>> DAVID Malan: zavzame več pomnilnika.
Kje je ta dodatna stalo prihajajo iz spomina?
>> OBČINSTVO: [neslišno]
DAVID Malan: Točno tako.
V tem primeru je tukaj, imeli smo povezani seznam za cela števila,
in vendar smo podvojili količina pomnilnika
moramo jih tudi shranjevanje teh nasvetov.
Zdaj manj velik posel kot vaše konstruktov dobili večje
in ste shranjevanje ni več, vendar morda študent ali kakšen drug predmet.
Vendar točka vsekakor ostaja.
In tako število operacij na povezanih seznamih so bili imenovani
so bili veliki O iz n-- linearno.
Stvari, kot pri vstavljanju ali iskanju ali izbris v primeru element
se je zgodilo, da je na samem koncu seznam, ali je to urejeno ali ne.
>> Včasih boste morda dobili srečo in tako spodnja meja za te operacije
lahko tudi stalen čas, če ste Vedno je videti na prvi element,
na primer.
Ampak na koncu, smo obljubili doseči sveti gral
podatkovnih struktur, ali nekateri njihovi približevanje,
s pomočjo konstantne časa.
Lahko najdemo elemente ali dodati elemente ali odstranite elemente iz seznama?
Bomo videli zelo kmalu.
In se izkaže, da je eden mehanizmov, da smo
dogaja, da začnete uporabljati danes, letna poraba v p nastavite pet,
je pravzaprav precej pozna.
Na primer, če je ta kup izpitnih knjig, od katerih je vsak
ima študent je prvi Ime in priimek na njej,
in sem jih pobral od na koncu izpit,
in oni so vse precej veliko v naključnem zaporedju,
in želimo, da gredo o sortiranje te izpite, tako da enkrat sortirani
to je samo veliko lažje in hitreje, da jih izroči nazaj
študentom po abecedi.
Kaj bi vaši instinkti biti za kup izpitov, kot je ta?
>> No, če ste kot jaz, boste lahko vidimo, da je ta m,
tako da bom nekako dal to v, Če je to moja miza ali moje nadstropje, kjer
Jaz širi stvari out-- ali moja matrika really--
Jaz bi dal vse Ms tam.
Oh.
Tukaj je A. Torej bom morda dal As tukaj.
Oh.
Tu je še en A. Grem bi dal, da je tukaj.
Tukaj je Z. Tukaj je še ena M. In tako Jaz bi začeli delati kupe, kot je ta.
In potem pa sem šel kasneje in nekako zelo nitpicky-ly sortiranje
posamezni piloti.
Ampak dejstvo je, jaz bi bil videti na vhodu, da sem roko
in želim narediti nekaj izračuna Odločitev temelji na tem vhodu.
Če se začne z, ga dal tja.
Če se začne z Z, ga položite čez tam, in vse vmes.
>> Torej, to je tehnika, ki je splošno znana kot hashing-- H-A-S-H--
ki na splošno pomeni, da se kot vnos in uporabo te vhod za izračun
vrednost, navadno številka, in da Številka je indeks v skladiščenju
posoda, kot matrike.
Torej, z drugimi besedami, morda imam hash funkcijo, kot jaz v moji glavi,
da vidim, če nekdo Ime, ki se začne z A,
Grem na zemljevid, ki nič v glavi.
In če vidim nekoga z Z, sem gre za preslikavo, ki do 25. v moji glavi
, nato pa, da je v zadnja najbolj kup.
>> Zdaj, če pomislite ne moji možgani ampak programa C, kakšne številke lahko
zanesete na to, da se doseže enak rezultat?
Z drugimi besedami, če vas imel ASCII znakov A,
kako določiti kaj bucket, da ga v?
Verjetno ne želite, da ga dal v vedro 65, ki
bi bilo tako kot tam brez pravega razloga.
Kje hočeš, da dajo glede na njegovo ASCII vrednost?
Kam želite narediti svoje ASCII vrednost, da bi prišli do pametnejše vedro
da bi ga v?
>> OBČINSTVO: Minus A.
>> DAVID Malan: Ja.
Torej minus ali minus natančneje 65, če je to
kapital A. Or 98, če to je z malimi tiskanimi črkami.
In tako, da bi nam omogočilo, da zelo enostavno in zelo aritmetično,
dal nekaj v vedro, kot je ta.
Tako se izkaže, smo pravzaprav storili to pa tudi s kvizi.
>> Tako da boste morda spomni boste obkrožili vaš naziv asistent na pokrovu.
In organizirane so bile imena TF je v teh stolpcih, po abecedi,
No, verjeli ali ne, ko vse 80 plus nas
skupaj dobili drugo noč razredu, Zadnji korak v našem procesu ocenjevanja
je za razpršitev kvize v big prostor nadstropju na [neslišno]
in določiti kvizi vsakogar out natanko zaporedju TF-ih
Imena na pokrovu, ker potem je veliko lažje za nas
iskanje skozi to z uporabo linearne iskanje ali neke vrste spretnost
za TF, da bi našli njegovo ali kvizi svojimi učenci.
>> Tako da je ta ideja hašiš da boste videli, je
zelo močni, je pravzaprav zelo vsakdanja in zelo intuitiven,
podobno kot morda razdeliti in vladaj je v ničelni tednu.
Sem hitro naprej na hackathon Pred nekaj leti.
To je bil Zamyla in par druge voščilnice osebje študentje
kot so se v.
In smo imeli cel kup pregibanje mize tam z imenskimi oznakami.
In smo organizirali imenske oznake s podobno As tamle
in Zs tam.
In tako eden od TF zelo spretno to napisal kot navodili
za ta dan.
In v 12. tednu semestra tega Vse je logično in vsakogar
vedel, kaj naj naredim.
Ampak kadarkoli ste prioritetnem vrstnem redu na enak način,
ste izvedbenih Isti pojem hash.
Torej, kaj je to malo formalizirati.
Tukaj je matrika.
To je opozoriti, da je malo širok samo prikazujejo, vizualno,
da bi mi dal strune v kaj takega.
In ta matrika je očitno velikost 26 skupaj.
In je stvar imenovano miza samovoljno.
Toda to je šele umetniška interpretacija kaj bi hash tabela.
>> Tako razpršena tabela sedaj se dogaja, da biti višja raven podatkovna struktura.
Ob koncu dneva bomo kmalu videli, da vas
lahko izvaja razpršene tabele, ki je podobno kot prijava v skladu
na hackathon podobno kot to tabela se uporablja za razvrščanje izpit knjige.
Ampak hash tabela nekako tako visoki ravni
Koncept, ki bi lahko uporabite niz pod kapuco za njeno izvajanje,
ali bi to lahko uporabite seznam dolžine ali celo morda nekatere druge podatkovne strukture.
In sedaj, ko je theme-- jemanje nekatere od teh osnovnih sestavin
kot array in te stavbe blokirajo sedaj seznama dolžine
in videli, kaj lahko gradimo poleg tistih, kot sestavino
v receptu, ki vse bolj in bolj zanimive in uporabne končni rezultati.
>> Torej s hash tabelo lahko bi ga izvajati
v spomin na slikovno, kot je ta, vendar kako bi bilo dejansko treba kodirati up?
No, morda kot preprosto je to.
Če zmogljivost v vseh kape, je le nekatere constant-- primer 26,
26 črk alphabet-- Jaz bi poklical svojega spremenljivo mizo,
in lahko trdim, da bom dal char zvezde tam, ali vrvice.
Torej, to je tako enostavno, kot je ta, če želijo izvajati razpršene tabele.
In vendar, je to res samo matrika.
Ampak še enkrat, hash Miza je zdaj tisto, kar bomo
pokličite abstraktni podatkovni tip, ki je pravkar nekakšen konceptualni plastenja na vrhu
nečesa bolj preprostega Zdaj je všeč array.
>> Zdaj, kako bomo šli o reševanju težav?
No, prej sem imel razkošje imajo dovolj prostora tabel tukaj
tako da sem lahko dal kvizi kjerkoli sem hotel.
Tako kot bi šel tu.
Zs bi šel tukaj.
Jst bi šel tukaj.
In potem sem imela nekaj dodatnega prostora.
Ampak to je malo goljufija pravice zdaj, ker te tabele, če je res
pomislil kot matrika, je le bo neke fiksne velikosti.
>> Tako tehnično, če potegnem do drugega študenta kviz
in glej, oh, ta oseba je ime se začne z A preveč,
Nekako želim, da ga ni.
Toda takoj, ko sem ga dal tja, če ta tabela dejansko predstavlja niz,
Grem k nujnim ali clobbering Kdor tega študenta kviz.
Kajne?
Če je to matrika, lahko le ena stvar gredo v vsakem od teh celic ali elementov.
In tako sem nekako imajo pa izberete.
>> Zdaj prej sem nekako prevarala in je to storil ali I
Samo nekako zloži jim druga nad drugo.
Ampak to se ne bo letenje v kodi.
Torej, če bi jaz dal Drugi študent, čigar ime
je, če je vse, kar sem imel, je to na voljo prostor tabel?
In sem uporabila tri reže in jo izgleda, da je samo nekaj drugih.
Kaj lahko naredim?
OBČINSTVO: [neslišno]
DAVID Malan: Ja.
Mogoče pa jo kar naprej preprosta.
Kajne?
To ne spada tja, kamor želim, da ga proda.
Torej bom dal tehnično, če bi šel B.
Zdaj, seveda, sem začel da sem slikal v kotu.
Če dobim za študenta čigar ime je pravzaprav B,
Zdaj B se bo preselila malo naprej, saj se lahko zgodi, ja,
če je to B, sedaj pa mora iti tukaj.
>> In zato je to zelo hitro lahko postane problematično,
ampak to je tehnika, ki dejansko se omenja kot linearna sondiranje,
pri čemer si razmisli vaš matrika biti vzdolž linije.
In si nekako sondo ali pregledati vsak element, ki je na voljo
išče razpoložljivih kraju samem.
In takoj, ko boste ugotovili, eno, jo spusti noter.
>> Zdaj, pri čemer je cena zdaj plača za to je, kaj?
Imamo določeno velikost polja, in ko sem vstavil imen
v njej, vsaj na začetku, kaj je čas vstavitve teče
za dajanje študente " kvizi v pravih vedra?
Big O česa?
>> OBČINSTVO: n.
DAVID Malan: Slišal sem veliko O n.
Ni res.
Vendar bomo draži narazen zakaj vsak trenutek.
Kaj bi lahko bilo?
>> OBČINSTVO: [neslišno]
DAVID Malan: In povej mi to naredil vizualno.
Predvidevam, da je to pismo S.
>> OBČINSTVO: To je ena.
DAVID Malan: To je ena.
Kajne?
To je matrika, ki pomeni, da moramo imeti izbirni dostop.
In če razmišljamo o tem kot nič, in to kot 25.,
in se zavedamo, da je oh, tu je moj input S,
Jaz vsekakor lahko pretvorite S, ASCII znak,
k ustreznim številom med nič in 25
in nato takoj ga, kamor spada.
>> Seveda, takoj ko dobim Druga oseba, ki je ime ali B ali C
na koncu, če sem uporabil Linearni sondiranje kot moja rešitev,
čas teče Vključitev v najslabšem primeru
se dejansko dogaja, da prenesejo v kaj?
In sem jo slišal tukaj pravilno že na začetku.
OBČINSTVO: [neslišno]
DAVID Malan: Torej je n res enkrat imate dovolj velik nabor podatkov.
Torej, na eni strani, če Vaše array je dovolj velika
in vaši podatki so redki dovolj, dobili to lepo konstantno čas.
Toda takoj, ko začnete dobili več in več elementov,
in samo statistično dobiš več ljudi s črko
Njihovo ime ali črka B, bi to lahko
prenesejo v nekaj bolj linearno.
Torej ni čisto popoln.
Tako da smo lahko še boljši?
>> No, kaj je bilo naše Rešitev prej, ko mi
želijo imeti več dinamike kot nekaj podobnega array dovoljeno?
OBČINSTVO: [neslišno]
DAVID Malan: Kaj smo uvedli?
Ja.
Tako povezani seznam.
No, da vidimo, kaj povezano Seznam lahko storite za nas, namesto.
No, naj vam predlagam, da sestaviti sliko, kot sledi.
Zdaj je ta drugačna Slike od primer
iz drugačnega besedila, dejansko, da dejansko uporabo paleto velikosti 31.
In ta avtor preprosto odločil, da hash strune
ne temelji na imena zadevne osebe, ampak na podlagi njihovih Birthdates.
Ne glede na mesec, so pogruntal če ste rojeni v prvi v mesecu
ali 31. v mesecu, avtor bo hash, ki temelji na tej vrednosti,
tako da se širijo imena ven nekaj več kot le 26 madeži lahko dovoli.
In morda je malo bolj izenačena kot se dogaja pri abecednih črk,
ker seveda tam je verjetno več ljudi na svetu z imeni
da začetek s kot gotovo nekatere druge črke abecede.
Mogoče je to malo bolj enoten, ob predpostavki,
enakomerna porazdelitev dojenčkov po enem mesecu.
>> Ampak, seveda, to je še vedno nepopolna.
Kajne?
Imava trčenja.
Več ljudi v to struktura podatkov so še vedno
ob isti datum rojstva vsaj ste ne glede na mesec.
Toda kaj je avtor naredil?
No, izgleda, da imamo niz na levi strani poteka navpično,
ampak to je samo umetniška interpretacija.
Ni važno v katero smer vas pripravi niz, je še vedno niz.
Kaj je ta niz na videz?
>> OBČINSTVO: Povezan seznam.
>> DAVID Malan: Ja.
Izgleda, da je array povezani seznam.
Torej še enkrat, da to točko vrste uporabe te podatkovne strukture zdaj
kot sestavine za več zanimive rešitve,
lahko popolnoma sprejeti temeljna, kot array,
in nato vzemite nekaj več Zanimivo kot povezan seznam
in jih tudi združite v še bolj zanimivo strukturo podatkov.
In res, tudi to bi se imenuje razpršene tabele,
pri čemer je matrika Res hash tabela,
ampak da hash tabela ima verige, tako rekoč,
ki lahko raste ali skrči na podlagi število elementov, ki jo želite vstaviti.
>> Zdaj, v skladu s tem, kar je čas teče zdaj?
Če želim vstaviti nekoga čigar rojstni dan je 31. oktober
kje je on ali ona iti?
Vse je v redu.
Na samem dnu, kjer piše 31.
In to je odlično.
To je bil čas konstantna.
Toda kaj, če bomo našli nekoga drugega čigar rojstni dan je, da vidimo,
Oktober, november 31. december?
Kjer je on ali ona bo šel?
Ista stvar.
Drugi korak, čeprav.
To je stalnica, čeprav je ni bilo?
Vse je v redu.
Trenutno je.
Ampak v splošnem primeru, več ljudi, ki smo jih prišteli,
probabilistically, greva da bi dobili več in več trkov.
>> Zdaj je to malo bolje, ker je tehnično
Zdaj moje verige lahko v najslabši primer, kako dolgo?
Če sem v to bolj vstavite n ljudi prefinjena struktura podatkov, n ljudje,
v najslabšem primeru, da se dogaja, da je n.
Zakaj?
>> OBČINSTVO: Ker če bi vsi ima isti rojstni dan,
oni bo ena vrstica.
DAVID Malan: Popolna.
Morda bi bilo malo izmišljene, ampak res v najslabšem primeru,
če imajo vsi isti rojstni dan, glede na vložke ki jih imate,
boste imeli množično dolgo verigo.
In tako, da to lahko tudi pokličete hash tabele, ampak res je
le ogromen povezani seznam z cel kup zapravljenega prostora.
Ampak na splošno, če predpostavimo, da najmanj so rojstni dnevi uniform--
in verjetno ni.
Delam, da je gor.
Ampak, če predpostavimo, za sake razprave
da so, potem v teoriji, če to je navpična reprezentacija
array, tudi potem pa upajmo, da ste bo dobil verige, ki so, veste,
približno enake dolžine, kjer je vsak izmed to predstavlja dan v mesecu.
>> Zdaj, če je 31 dni v mesecu, to pomeni, da mi teče čas res
je velik O n nad 31, ki počuti bolje kot ravne.
Toda kaj je bil eden od naših Obveznosti nekaj tednov
nazaj, kadar je šlo za izražanje čas delovanja algoritma?
Samo poglej samo na visoko naročila mandata.
Kajne?
31 je vsekakor koristno.
Ampak to je še vedno velik O n.
Toda eden od teme za problem določiti pet
se bo na priznavajo, da je nujno,
asimptotično, teoretično ta struktura podatkov
Ni boljšega kot samo en ogromen povezani seznam.
In res, v najslabšem primeru, to razpršene tabele lahko prenesejo v to.
>> Ampak v resničnem svetu, pri nas ljudje lastni Macov ali osebnih računalnikov ali karkoli
in se izvajajo v realnem svetu programska oprema na resničnem svetovnem podatkov
algoritem, ki se boste raje?
Tisti, ki bo končnim korakov ali tista, ki traja n deljeno s 31 korakov
da bi našli nekaj podatek ali poiskati nekaj informacij?
Mislim, absolutno 31 znamk Razlika v resničnem svetu.
To je 31-krat hitreje.
In smo ljudje zagotovo dogaja, da cenim.
>> Torej zavedaš dihotomijo tam med dejansko
Govorimo o stvareh teoretično in asimptotično ki vsekakor
ima vrednost, kot smo videli, ampak v resničnem svetu,
Če vam je mar samo izdelavo človek srečen za splošne vhode,
morda dobro, da želite sprejeti Dejstvo, da je to ja linearna,
ampak to je 31-krat hitreje kot linearna lahko.
In še bolje, da nimamo samo zato, da narediti nekaj samovoljno kot rojstnim dnem,
bomo lahko porabili malo več časa in spretnost
in razmišljati o tem, kaj lahko storimo, osebno ime in morda osebe
njihov datum rojstva združiti tiste, sestavine, da ugotovimo, kaj
da je resnično več enotna in manj jaggy,
tako rekoč od te slike Trenutno kaže, da bi bilo.
Kako bi lahko to izvedli v kodo?
No, naj vam predlagam, da samo sposoditi nekaj sintakse, ki smo jih
uporablja nekajkrat doslej.
In bom za opredelitev vozlišče, ki je ponovno
je generični izraz za samo nekateri Posoda za nekaj podatkov strukturo.
Jaz bom predlagal, da Niz se dogaja tam notri.
Ampak bomo začeli jemati tistih, ki usposabljanje kolesa off zdaj.
>> Nič več CS50 knjižnica res, če hočeš
da jo uporabite za vaše finale Projekt, ki je v redu,
zdaj pa bomo potegnite nazaj zavese in reči, da je samo char zvezda.
Torej besede tam se bo ime osebe v vprašanju.
In zdaj imam povezavo tukaj na naslednje vozlišče
da le-ti predstavljajo vsaka od vozlišč
v verigi, potencialno iz povezanega seznama.
>> In zdaj kako Izjavljam sam hash tabela?
Kako razglasi celotno strukturo?
No, res, tako kot sem se kazalec na samo prvi element seznama
Pred podobno lahko rečem Potrebujem samo kup kazalci
za izvajanje te celo razpršene tabele.
Bom imela niz imenovana miza za hash tabele.
To se dogaja, da so velikosti zmogljivosti.
To je, koliko elementov lahko fit v njem.
In vsak od teh elementov v to Niz se bo vozlišče zvezda.
Zakaj?
No, na tej sliki, kar sem izvajanje razpršene tabele kot
dejansko je v začetku le ta niz, da smo pripravljeni navpično,
vsak od katerih kvadratov predstavlja kazalec.
Da tisti, ki imajo poševnico preko njih so samo null.
In tisti, ki imajo puščice, ki gredo v desno
so dejanski kazalci na dejanske vozlišč, ergo začetek povezanega seznama.
>> Torej, tukaj je torej, kako bi lahko izvajati razpršene tabele, ki
izvaja ločeno veriženja.
Sedaj lahko storimo bolje?
Vredu sem obljubil zadnjič, da bomo lahko dosegli konstantno časa.
In sem nekako vam je dal stalen čas tukaj,
potem pa ni povedal res konstanten čas, ker je še vedno
odvisno od vsote število elementov
ste vnesla podatkovna struktura.
Recimo, bomo to storili.
Dovolite mi, da se vrnete na zaslon tukaj.
Dovolite mi, da je tudi ta projekt sem gor, jasno, zaslon, in domnevam, da sem to naredil.
Recimo, da sem si želel, da vstavite ime Daven leta v mojo strukturo podatkov.
>> Torej, želim vstaviti niz Daven v strukturo podatkov.
Kaj pa, če ne uporabljam hash tabelo, vendar sem uporabo
nekaj, kar je več dreves, kot so kot družinsko drevo, kjer
imate nekaj korenine v top in nato vozlišča in liste
da gredo navzdol in navzven.
Domnevam torej, da sem želite vstaviti Daven je
v tisto, kar je trenutno prazen seznam.
Bom naredil naslednje: Jaz sem tekoč ustvariti vozlišče v tej družini
drevo, podobno strukturo podatkov, ki izgleda malo takole, od katerih je vsak
pravokotniki je, recimo, za zdaj 26 elementov v njem.
In vsaka od celic V tem polju se dogaja
da predstavlja črko abecede.
>> Natančneje, bom za zdravljenje to je, potem B, potem C, potem D,
tale tukaj.
Torej, to se dogaja, da učinkovito predstavljajo črko D.
Ampak, da vstavite vse Daven je ime moram storiti malo več.
Tako da sem prvič dogaja, da hash, če se tako izrazim.
Grem pogledati prvo črko v Daven je, kar je očitno D,
in bom za dodelitev vozlišče, ki izgleda
kot this-- velik pravokotnik velik dovolj, da se prilega popolno abecedo.
>> Zdaj je D storil.
Sedaj A. D-V-E-N je avt.
Torej, zdaj, kaj bom storiti, je to.
Takoj, ko sem začel obvestilo D ni kazalec tam.
To je smeti vrednosti v trenutku, ali mi lahko inicializacijo NULL.
Ampak naj nadaljujem z Ta ideja o izgradnji drevo.
Dovolite mi, da dodeli še enega od teh vozlišča, ki ima 26 elementov v njem.
>> In veste kaj?
Če je to le vozlišče v pomnilniku, da Ustvaril sem s funkcije malloc z uporabo struct
kot bomo kmalu videli, Bom naredil this--
Bom potegniti puščico iz stvar, ki jo zastopa D navzdol
s to novo vozlišče.
In zdaj, prvi naslednji črka v imenu Daven je,
V- D-A-V- bom, da gredo naprej in sestaviti novo vozlišče, kot je ta,
pri čemer so elementi V tukaj, ki bomo pripraviti za instance-- Ops.
Ne bomo pripraviti tam.
To se dogaja, da gredo tukaj.
>> Potem bomo menijo, da je V.
In potem tukaj si bomo indeksa navzdol iz V. v tisto, kar menimo, da je E.
In potem od tu si bomo iti na eno od teh vozlišč tukaj.
In zdaj imamo vprašanje odgovoriti.
Moram nekako kažejo, da smo na koncu niza Daven.
Tako da sem lahko samo pustite null.
>> Toda kaj, če imamo Daven je polno ime tudi, kar
je, kot že rečeno, Davenport?
Pa kaj, če je Daven dejansko podniz,
predpona precej daljše vrvi?
Ne moremo samo trajno reči nič ne dogaja
iti tja, ker smo lahko Nikoli ne vstavite besedo tako, kot je Davenport
V to podatkovno strukturo
>> Torej, kaj lahko storimo namesto tega je zdravljenje vsakega od teh elementov
kot morda ima dva elementi znotraj njih.
Eden od njih je kazalec, res, kot sem že počel.
Torej je vsako od teh polj ni le ena celica.
Toda kaj, če top one-- dno eden je
bo nična, ker ni Davenport samo še.
Kaj pa, če top ena je nekaj posebnega vrednost?
In to se dogaja, da se malo trdi, da je ta velikost pripraviti.
Recimo, da je samo kljukica.
Preverite.
D--V-E-N je niz v tej strukturi podatkov.
>> Medtem, če bi imel več prostora Tukaj lahko storim P-O-R-T,
in lahko sem dal ček v vozlišču ki ima črko T na samem koncu.
Torej, to je množično kompleks je videti strukturo podatkov.
In moj rokopis gotovo ne pomaga.
Ampak, če sem hotel nekaj vstavili drugega, razmisliti, kaj bi naredili.
Če bi želeli postaviti Davida in, sva po isti logiki, D-A-V,
zdaj pa naj opozorim na naslednjo element ne iz E, ampak od I do D.
Tako se dogaja, da je več vozlišča v drevesu.
Bomo imeli klic funkcije malloc več.
Ampak jaz ne želim, da bi popolna zmešnjava te slike.
Tako da je namesto pogled na eno ki je bila predhodno že oblikovano
kot je ta z ne dot, dot, pike, ampak le skrajšano nizi.
Toda vsaka od vozlišč v tem drevesu tukaj
predstavlja enako thing-- Niz Ray velikosti 26.
>> Ali če hočemo biti res čisto zdaj, kaj
če ime nekoga, kot je opuščaj, kaj je
predpostavimo, da dejansko ima vsako vozlišče kot 27 indeksov v njej, ne le 26.
Torej to sedaj se bo podatkov struktura se imenuje trie-- T-R-I-E.
Trie, ki je menda zgodovinsko pameten ime za drevo
ki je optimizirana za Preiskovalna, kar seveda
je pira z I-E, tako da je Trie.
Ampak to je zgodovina Trie.
>> Torej Trie je to drevo kot podatki Struktura kot družinsko drevo
da na koncu obnaša tako.
In tukaj je samo en primer cel kup imen drugih ljudi.
Vendar pa je vprašanje zdaj pri roki, je tisto, kar imajo
smo pridobili z uvedbo verjetno več zapletena struktura podatkov, in eno,
odkrito, ki uporablja veliko pomnilnika.
>> Ker je, čeprav, v tem trenutku sem samo
uporabo D-jev, kazalec in In V Es in Ns,
Jaz zapravljam pekel od veliko pomnilnika.
Ampak, kje sem preživela en vir, Jaz ponavadi ne pridobijo nazaj drugo.
Torej, če sem porabi več prostora, kar je verjetno upanje?
Da sem porabi manj kaj?
OBČINSTVO: Manj časa.
DAVID Malan: Čas.
Zdaj, zakaj naj bi to bilo?
No, kaj je vstavljanje čas, v smislu velikih O sedaj,
imena, kot Daven ali Davenport ali David?
No, bil Daven pet korakov.
Davenport bi devet korakov, tako da bi bilo nekaj več korakov.
David bi pet korakov, kot tudi.
Torej, to so konkretni številke, ampak zagotovo obstaja
zgornja meja na Dolžina ime nekoga.
In res, v problemu kompleti petih specifikacije,
bomo predlagali da je to nekaj
da je 40-nekaj-ak znakov.
>> Realno, nihče nima neskončno dolgo ime,
kar pomeni, da dolžina ime ali dolžina niza smo morda
imajo gotovo stanje struktura je verjetno kaj?
To je konstantna.
Kajne?
To je lahko velik konstanten kot 40-nekaj, vendar je konstantna.
In to nima nobene odvisnosti od koliko druga imena, ki so v tej strukturi podatkov.
Z drugimi besedami, če I želel zdaj vstavite
Colton ali Gabriel ali Rob ali Zamyla ali Alison ali Belinda ali katera koli druga imena
od zaposlenih v teh podatkov struktura, je čas teče
vstavljanje druga imena bo sploh vplivala
s tem, kako veliko drugih elementov, so v strukturi podatkov že?
To ni.
Kajne?
Ker smo učinkovito uporabo Ta večplastna hash tabele.
In čas teče katerokoli od teh operacij
ni odvisna od števila elemente, ki so v strukturi podatkov
ali da se sčasoma gredo da so v strukturi podatkov,
ampak na dolžino, kar posebej?
>> Niz čemer vstavljena, ki ne bi
ta konstanta asimptotično time-- big O enega.
In odkrito povedano, samo v realnem svetu, to
pomeni vstavljanje ime Daven je potrebno kot pet korakov oziroma Davenport devetih
koraki, ali David pet korakov.
To je precej darn majhne tekaške krat.
In res, da je zelo dobra stvar, še posebej, če
to ni odvisna od celotne število elementov v tam.
Torej, kako bi lahko izvajanje tega vrsta strukture v kodo?
To je malo več kompleksna, vendar še vedno je
samo uporaba osnovni gradniki.
Grem na novo opredeliti nam vozlišče, kot sledi:
bool imenuje word-- in to lahko imenujemo ničesar.
Vendar bool predstavlja kaj sem narisal kot kljukico.
Da.
To je konec niza v tej strukturi podatkov.
>> In, seveda, vozlišče zvezda tam se nanaša na otroke.
In, seveda, tako kot družinsko drevo, si
bi upošteval vozlišča ki so viseli
dna nekaterih staršev element, da so otroci.
In tako se dogaja, da otroci je množica 27., 27. ena
le da za vejico.
Mi bomo za razvrščanje posebnega primera tega.
Tako da lahko imajo nekatere Imena z opuščaj.
Mogoče celo vezaj smeli tja, vendar boste
glej str nizu 5 smo samo za nego o pismih in opuščaj.
>> In potem kako si predstavljajo sama podatki struktura?
Kako si predstavljajo korenine te Trie, tako rekoč?
No, tako kot s povezano seznamu, potrebujejo kazalec na prvi element.
Z Trie morate samo eno kazalec na koren tega Trie.
In od tam lahko izbrskali svojo pot navzdol globlje in globlje
za vsako drugo vozlišče v strukturi.
Tako enostavno s to pločevinko zastopamo to struct.
>> Zdaj Meanwhile-- Oh, vprašanje.
>> OBČINSTVO: Kaj je bool beseda?
>> DAVID Malan: Bool beseda Samo ta inkarnacija C
tega, kar sem opisal v to polje tukaj, ko
Sem začel razdelitvijo vsakega od Elementi Array je v dveh kosih.
Ena je kazalec na naslednje vozlišče.
Druga mora biti nekaj podobnega potrditveno polje
reči da, tam je Beseda Daven da se tu konča,
zato, ker ne želimo, v trenutku, Dave.
>> Čeprav Dave se bo legitimna beseda, on ni v Trie
še ni.
In D ni beseda.
In D-ni beseda ali ime.
Torej kljukico kaže samo enkrat vas
hit to vozlišče Predhodna pot znakov
pravzaprav niz, ki ste vstavili.
Tako, da je vse bool tam je delal za nas.
>> Katera koli druga vprašanja o poskusih?
Ja.
>> OBČINSTVO: Kaj je prekrivanja?
Kaj pa, če imate Dave in Daven?
DAVID Malan: Popolna.
Kaj pa, če imate Dave in Daven?
Torej, če bomo vstavite, pravijo vzdevek za David-- Dave-- D-A-V-E?
To je pravzaprav zelo preprost.
Tako da smo samo bo trajalo štiri korake.
D--V-E. In kaj moram storiti, ko sem udaril, da je četrto vozlišče?
Le, da bo preveriti.
Mi smo že na dobri poti.
Končano.
Štirje koraki.
Constant čas asimptotično.
In zdaj smo navedli, da sta Dave in Daven so strune v strukturi.
Torej ni problem.
In opazil, kako prisotnost od Daven ni uspelo
vzeti več časa ali manj Čas za Dave in obratno.
>> Torej, kaj še lahko zdaj naredim?
Mi smo uporabili to metaforo, preden podstavkov predstavlja nekaj.
Vendar se izkaže, da skladovnica pladnjev je pravzaprav
demonstrativen druge abstraktne podatkov type-- višjo raven podatkovno strukturo
da na koncu je dan samo kot niz ali povezani seznam
ali kaj bolj preprostega.
Ampak to je bolj zanimivo konceptualna zasnova.
Kup, tako kot ti pladnji tukaj v Mather,
se na splošno imenuje Samo that-- kup.
>> In v tej vrsti podatkovne strukture imate dve operations--
imate eno imenovano push dodal nekaj na sklad,
kot dajanje drug pladenj nazaj na vrhu kupa.
In potem pop, kar pomeni, da vam sprejeti na najvišji pladnja off.
Toda kaj je ključnega pomena pa je, da sveženj da je dobil to nenavadno lastnost.
Kot jedilnici osebje so preurejanjem pladnje za naslednji obrok,
kaj se dogaja, da se Res o tem, kako študenti
interakcijo s tem strukturo podatkov?
OBČINSTVO: Ti boš pop en off.
DAVID Malan: Ti boš pop One, upajmo vrh.
V nasprotnem primeru je le nekako neumno iti vse do dna.
Kajne?
Podatkovna struktura v resnici ne dovoli ste, da zgrabite spodnji pladenj vsaj
enostavno.
Torej je to zanimalo nepremičnina na kupu
da je zadnja točka je v bo prvi ven.
In računalniški znanstveniki pokličite to LIFO-- zadnji noter, prvi ven.
In dejansko ima zanimive aplikacije.
To ni nujno tako očitno kot nekateri drugi, vendar pa lahko dejansko koristno,
in lahko, seveda, je treba izvesti v nekaj različnih načinov.
>> Torej eno, in dejansko, naj me ne, da se potopite v to.
Naredimo to namesto tega.
Oglejmo si eno, ki je skoraj Ista ideja, ampak je malo bolj pošteno.
Kajne?
Če ste eden od teh ventilatorjev dečke ali dekleta, ki resnično všeč Apple izdelkov
in si se zbudil ob 03:00 line up na neki trgovini
da bi dobili najnovejše iPhone, boste Morda so v čakalni vrsti takole.
>> Zdaj je čakalna vrsta zelo namerno imenom.
To je črta, ker tam nekateri pravičnost do njega.
Kajne?
To bi nekako zanič, če ste dobil je prvi na Apple Store
ampak ste dejansko spodnjih pladenj, ker zaposleni Apple potem
pop zadnjo osebo, ki dejansko dobil v vrsti.
Torej dimnikov in čakalne vrste, čeprav funkcionalno oni nekako v same--
to je samo ta zbirka sredstev, ki je
dogaja, da rastejo in shrink-- tam je ta vidik pravičnosti z njim,
vsaj v resničnem svetu, kjer se izvajajo dejavnosti vadite
se bistveno razlikujejo.
Stack-- čakalne vrste rather-- je dejal, da imajo
dve operaciji: n čakalne vrste in d čakalne vrste.
Ali pa jih lahko pokličete poljubno število stvari.
Ampak si samo želim, da zajame Ideja, da je eden dodajanje
in ena je na koncu odšteje.
>> Zdaj pod pokrovom, tako da se bo sveženj in čakalne vrste bi bilo mogoče izvesti, kako?
Mi ne bo šel v kodeksu Zato, ker višji nivo
Ideja je nekako bolj očitna.
Mislim, kaj so ljudje naredili?
Če sem prva oseba na Apple Shranjevanje in to je vhodna vrata,
veš, da bom stati tukaj.
In naslednjo osebo je dogaja, da stojim tu.
Torej, kaj je struktura podatkov sama daje v čakalno vrsto?
>> OBČINSTVO: čakalne vrste.
DAVID Malan: No, čakalne vrste.
Prepričan.
Kaj še?
>> OBČINSTVO: povezani seznam.
>> DAVID Malan: povezana seznam, ki ga lahko izvajajo.
In povezani seznam je lepo, ker potem Zraste lahko poljubno dolgo, v nasprotju
da imajo neko določeno število ljudi v trgovini.
Ampak mogoče določeno število krajev, je legitimno.
Ker, če imajo le kot 20 Telefoni iPhone na prvi dan, morda
potrebujejo le niz velikosti 20, ki bi predstavljal čakalno vrsto, ki
je samo reči, zdaj, ko smo začeli govoriti o temi problemi na višji ravni,
ga lahko izvajajo v vsakem številne načine.
In tam je verjetno le, da bo biti kompromis v času in prostoru
ali pa samo v svoji kompleksnosti kode.
>> Kaj pa kupu?
No, kup, smo videli tudi lahko samo ti pladnji.
In ti bi to matrika izvajati.
Ampak na neki točki, če boste uporabili matriko, kaj se bo zgodilo s pladnji
skušaš dati dol?
Vse je v redu.
Boš samo mogli iti tako visoko.
In mislim, da v Mather oni dejansko potisnjeni v tej odprtini.
Torej, res, to je skoraj kot Mather uporablja
niz fiksne velikosti, saj lahko le
fit toliko pladnjev v tej odprtini stena spodaj kolena ljudi.
In tako, da bi bilo dejal, da je matrika,
vendar bi vsekakor izvajati, da bolj splošno s povezani seznam.
>> No, kaj pa drugega strukturo podatkov?
Dovolite mi, dvigni eno drugo vizualno tukaj.
Nekaj ​​podobnega, kako o tem enem tukaj?
Zato bi bilo koristno, da se ne nekaj tako fancy kot Trie, ki
Videli smo imeli te zelo široke vozlišč, od katerih je vsak v matriki?
Toda kaj, če delamo nekaj več enostavno, kot stara šola družinsko drevo,
vsak od katerih vozlišča tukaj je samo shranjevanje številke.
Namesto imena ali potomca je samo shranjevanje številko, kot je ta.
>> No, žargon, ki jih uporabljamo v podatkovne strukture je tako poskuša
in drevesa, kjer je, še enkrat, je Trie Samo tisti, katerega vozlišča so nizi
je še vedno tisto, kar bi lahko uporabljati od osnovne šole
Ko ste naredili družino tree-- listi in korenina
drevesa in otroke starši in njihovi bratje in sestre.
In morda smo izvajati drevo, na primer, kot je enostavno kot to.
Drevo, če slednja kot vozlišče, enega ti krogi, ki ima številko,
to ne dogaja, da imajo en kazalec, ampak dva.
In takoj, ko boste dodali Drugi kazalec, ki jih
dejansko lahko sedaj narediti neke iz dvodimenzionalnega podatkov
strukture v spominu.
Podobno kot dvodimenzionalna matrika, lahko
imajo vrste iz dvodimenzionalne povezani seznam, ampak tisti,
da sledijo vzorcu kjer obstaja nobenega cikla.
To je resnično drevo z enim stari način tu in potem
nekateri starši in otroci ter vnuki in pravnuki.
in tako naprej.
>> Ampak kaj je res lepo o tem preveč, Samo, da vas draži z nekaj kode,
Odpoklic rekurzija iz Nekaj ​​časa nazaj, pri čemer
napišete funkcijo, ki se kliče.
To je lepa priložnost izvesti nekaj
kot rekurzija, ker da je to.
>> To je drevo.
In sem bil malo anal s tem, kako Sem dal cela na cesto.
Toliko, da ima posebna name-- binarno iskalno drevo.
Zdaj smo slišali binarno iskanje, vendar lahko
delo nazaj od imena ta stvar je?
Kaj je vzorec, kako sem vstavljena cela števila v to drevo?
To ni arbitrarna.
Tukaj je nekaj za vzorec.
Ja.
>> OBČINSTVO: Manjše tisti na levi.
>> DAVID Malan: Ja.
Manjši pa so na levi strani.
Večje pa so na desni strani.
Tako, da je resnična trditev matična je večji od njene kazenski otroka,
vendar manj kot njeni desni otroka.
In to samo še rekurzivna definicija verbalno
saj se lahko uporablja, da Ista logika, da vsako vozlišče
in ima samo dna ven, baza primeru, če vas
bo, ko ste zadeli enega izmed listi, tako rekoč,
kjer je dopust še bolj brez otrok.
>> Zdaj, kako bi našli številko 44?
Ti bi začeli pri korenu in reči, hm.
55 ni 44 Torej, ne želim iti desno, ali pa bi rad šel levo?
No, očitno želite iti levo.
In zato je tako kot telefon Knjiga primer v binarnem iskanju
bolj na splošno.
Vendar smo ga izvajajo Zdaj malo bolj dinamično
kot niz lahko dovoli.
In v resnici, če želite videti na kodo, na prvi pogled seveda.
Izgleda, da je cel kup linij.
Ampak to je čudovito preprost.
Če želite izvesti funkcijo imenuje iskanje katerih namen v življenju
je za iskanje vrednosti kot je n, celo število,
in ste opravili v enem pointer-- kazalec na vozlišče korenin,
ne, tega drevesa, iz katerih lahko dostopate do vsega drugega,
opazili, kako preprosteje lahko izvajajo logiko.
Če drevo je nična, Očitno je ni.
Naj samo vrne false.
Kajne?
Če ste ga ročno nič, tam ni ničesar.
>> Drugega, če je n manj kot Drevo arrow n-- zdaj arrow n,
spomnim smo uvedli super kratko drugi dan,
in to samo pomeni, da de-sklic kazalec in poglejte polja, imenovano n.
Torej to pomeni, da gredo tja in poglej na področju imenovanem n.
Torej, če je n vrednost si dal, je manj od vrednosti v celo število dreves,
Kam želite iti?
Na levi.
>> Torej opazil rekurzijo.
Jaz returning-- ni res.
Ni napačna.
Jaz sem se vračajo, ne glede na odgovor je s pozivom k sebi, mimo
spet n, ki je odveč, ampak kaj je sedaj nekoliko drugačna?
Kako bom kar problem manjši?
Jaz sem, ki poteka v kot drugi argument, ne koren drevesa,
ampak levo otrok v tem primeru.
Tako da sem poteka v levem otroka.
>> Medtem, če je n večji od node sem trenutno iščejo,
Iščem desno stran.
Else, če drevo ni nič, in Če element ni na levi
in to ne na desno, kaj je čudovito tako?
Mi smo dejansko našli vozlišče v vprašanje, zato se vrnemo true.
>> Torej smo pravkar opraskan površine zdaj nekatere od teh podatkovnih struktur.
V problem določiti pet jih boste raziskovanje teh še nadalje,
in boš dal vaš design odločitev o tem, kako iti o tem.
Kaj bi rad za sklepanje o je le drugi teaser 30
kaj čaka naslednji teden in dlje.
>> Kot smo begin-- srečo boste morda think-- naš prehod počasi
iz sveta C in nižje Podrobnosti o izvajanju ravni,
v svetu, v katerem bomo lahko za samoumevno, da ima nekdo končno
izvajajo te podatke strukture za nas,
in bomo začeli razumeti realnem svetu pomenijo izvajanja
spletne programe in spletne strani bolj splošno
in tudi zelo varščina posledice, ki smo jih le
začeli praska površino.
Tukaj je, kaj nas čaka v dneh, ki prihajajo.
>> [VIDEO PREDVAJANJE]
>> -On Je prišel s sporočilom, s protokolom vse sam.
Prišel je na svet krut požarni zidovi, usmerjevalniki, neskrbni
in nevarnosti hujše od smrti.
Je hitro.
On je močan.
On je TCP / IP, in on je dobil svoj naslov.
"Warriors mreže."
[END VIDEO PREDVAJANJE]
DAVID Malan: Prihaja naslednji teden.
Vam bomo videli potem.
[VIDEO PREDVAJANJE]
In zdaj, "Deep Thoughts" z Daven Farnham.
David B. vedno začne predavanja, "V redu."
Zakaj pa ne, "Tukaj je rešitev za ta teden problemskega sklopa "
ali "Mi smo kar vsi vi?"
[Smeh]
[END VIDEO PREDVAJANJE]