[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. 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]