>> KEVIN Schmid: Stundum, þegar byggja á program, þú might vilja til að nýta tölvutækni
gögn uppbygging þekktur eins og orðabók.
A orðabók kort takkana, sem er venjulega strengi, gildum, ints,
stafir, bendi á einhverjum hlut, hvað sem við viljum.
Það er bara eins og venjulegur orðabækur göngulag orð gegnum skilgreiningar.
>> Orðabækur veita okkur með getu til að geyma upplýsingar
tengist eitthvað og lítur hann upp síðar.
Svo hvernig við innleiða í raun orðabók í, segjum, C kóða sem við getum
nota í einu af áætlunum okkar?
Jæja, there ert a einhver fjöldi af lifnaðarhættir sem við gátum innleiða orðabók.
>> Fyrir einn, gætum við notað array sem við virk aftur stærð eða við gætum nota
tengda listanum, kjötkássa borð eða tvöfaldur tré.
En hvað sem við veljum, ættum við að hafa í huga að skilvirkni og
árangur af framkvæmd.
Við ættum að hugsa um reiknirit notað til að setja inn og líta upp atriði í
gögn uppbygging okkar.
>> Fyrir nú, við skulum gera ráð fyrir að við vilt nota strengi eins og lyklar.
Við skulum tala um einn möguleika, gögn uppbygging kallast trie.
Svo hér er myndræn af trie.
>> Eins og myndin gefur til kynna, trie er tré gögn uppbygging með
hnúður tengd saman.
Við sjáum að það er greinilega rót hnút með nokkrir tenglar sem nær til
aðrar hnúður.
En hvað þýðir hver hnútur samanstanda af?
Ef við gerum ráð fyrir að við erum að geyma lykla með aðeins stafrófsröð stafir, og
við gerum ekki sama um fjármögnun, hér er skilgreining á hnút sem
mun nægja.
>> Hlutinn sem gerð er struct hnútur í tvo hluta
kallaði gögn og börn.
Við höfum vinstri gögnin hluti sem athugasemd til að skipta með íhlut
yfirlýsing þegar strúktúr hnútur er tekin upp í C forrit.
Gögnin hluti af hnút gæti verið Boolean gildi til kynna hvort eða
ekki hnúturinn táknar endalok á orðabók takkann eða það gæti verið
band alþingismaður skilgreiningu á orði í orðabókina.
>> Við munum nota broskalla andlit til að sýna þegar gögnum er til staðar í hnút.
Það eru 26 þættir í okkar börn array, eina vísitölu
á bókstaf.
Við munum sjá mikilvægi þetta fljótlega.
>> Við skulum fá að líta nánar á rót hnút Á skýringamynd okkar, sem hefur engin gögn
tengslum við hana, eins og sýnt er með Vöntun á broskalla andlit í
gögn hluti.
Örvarnar nær frá hlutum börnin array tákna non-hnút
ábendingum til annarra hnúta.
Til dæmis, sem örin nær frá seinni þáttur barna
táknar stafinn B í orðabók takkann.
Og í stærri myndinni við merki það með B.
>> Bent er á að í stærri skýringarmynd, þegar við draga bendi á annan hnút, það
skiptir ekki máli hvar Arrowhead uppfyllir þessi annar hnút.
Sýnishorn orðabók okkar trie inniheldur tvö orð, sem og zoom.
Skulum ganga í gegnum dæmi um leita upp gögn fyrir takka.
>> Segjum að við vildum að líta upp samsvarandi gildi fyrir helstu baði.
Við munum byrja útlit okkar upp í rót hnút.
Þá munum við taka fyrsta stafinn af okkar lykill, B, og finna samsvarandi
blettur í börnum fylking okkar.
Takið eftir að það eru nákvæmlega 26 staði í fylkinu, einn fyrir hvern bókstaf
stafrófið.
Og við munum hafa blettina tákna bókstafir í röð.
>> Við munum líta á annan vísitölu þá, Vísitala einn, fyrir B. almennt, ef við
hafa sumir bókstaf C vér gæti ákvarða samsvarandi stað
í börnin fylki með útreikningum eins og þetta.
Við gætum hafa notað stærri börn array ef við vildum að bjóða Horfðu upp af
lykla með fjölbreyttari stöfum, svo sem eins og á öllu
ASCII stafasett.
>> Í þessu tilviki er bendi hjá börnum fylking okkar á
Vísitala einn er ekki núll.
Þannig að við munum halda áfram að leita upp helstu baði.
Ef við lendum alltaf núll músina á réttum stað í börnum
array meðan við liggur hnúður, þá munum við þurfa að segja að við
gat ekki fundið neitt fyrir þessi lykill.
>> Nú munum við taka annað bréf um lykill okkar, A, og halda áfram að fylgjast
ábendingum á þennan hátt þar til við ná sambandi við lok lykill okkar.
Ef við náum að enda takkann án hitting allir blindgötur, null ábendingum,
eins og raunin er hér, þá erum við aðeins að athuga eitt í viðbót.
Er þetta lykillinn raun í orðabókinni?
>> Ef svo er, ættum við að finna gildi, vel a broskalla andlit táknið í myndinni okkar þar
orðið endar.
Ef það er eitthvað annað geymd með gögn, þá getum við farið með hana.
Til dæmis, lykillinn Zoo er ekki í orðabók, jafnvel þótt við gætum haft
náð í lok þessa takka án þess nokkurn tíma hitting núll músina, meðan við
iterate gegnum trie.
>> Ef við reyndum að líta upp takkann bað, að sekúndu til array vísitölu síðasta hnúturinn er,
sem svarar til stafnum H, myndi hafa haldið núll músina.
Svo er bað ekki í orðabókinni.
Og svo er trie einstakt í að takkarnir eru aldrei beinlínis geymdar í
gagnagrindina.
Svo hvernig gera við setja eitthvað í trie?
>> Skulum setja lykilinn dýragarðinum í trie okkar.
Mundu að broskalla andlit í hnút gæti svara í kóða til einfalt
Boolean gildi sem benda til að dýragarðinum er í orðabókinni eða það gæti
samsvara frekari upplýsingar sem við vilt tengja við takkann dýragarðinum,
eins skilgreiningu á orð eða eitthvað annað.
Að sumu leyti, the aðferð að setja eitthvað í trie er svipað
leita upp eitthvað í trie.
>> Við munum byrja með rót hnút aftur, Eftirfarandi ábendingum sem svarar til
bréfum lykill okkar.
Til allrar hamingju, við varúlfur fær til að fylgja ábendingum alla leið þangað til við höfum náð
enda takkann.
Þar dýragarðinum er forskeyti á orðinu zoom, sem er aðili að
orðabók, þurfum við ekki að úthluta öllum nýjum hnúður.
>> Við getum breytt hnút til kynna að leið af stöfum sem leiðir til
það táknar lykil í orðabók okkar.
Nú, við skulum reyna að setja á lykill BATH í trie.
Við munum byrja á rót hnút og fylgja ábendingum aftur.
En í þessu ástandi, högg við dauður enda áður en við erum fær um að fá að
endir af helstu.
Nú munum við þurfa að úthluta nokkrar nýjar hnúður verður að úthluta einum nýjum
hnút fyrir hvern eftir bréf af takkanum okkar.
>> Í þessu tilfelli þarf við bara að úthluta einum nýjum hnút.
Þá munum við þurfa að gera H vísitölu tilvísun nýja hnút.
Enn og aftur, getum við breytt hnút til benda til þess að slóð af stöfum
sem leiðir til þess að það táknar Lykillinn í orðabók okkar.
Skulum ástæðu um asymptotic flókið ferli okkar fyrir þessi
tvær aðgerðir.
>> Við eftir því að í báðum tilfellum númer af skrefum reiknirit okkar tók var
í réttu hlutfalli við fjölda bréf í leitarorði.
Það er rétt.
Þegar þú vilt líta upp orði í trie þú þarft bara að iterate gegnum
bókstafirnir einn við einn þangað til þú annað hvort ná í lok orðsins eða
högg dauður endi í trie.
>> Og þegar þú vilt setja á takka gildi par í trie nota
málsmeðferð og við ræddum, versta tilfelli verður þú að úthluta nýja hnút
fyrir hvern staf.
Og við munum gera ráð fyrir að úthlutun er stöðug tími aðgerð.
Þannig að ef við gerum ráð fyrir að lykillinn lengd er afmarkast af föstu stöðug, bæði
innsetningu og líta upp eru stöðug tími starfsemi fyrir trie.
>> Ef við gerum þetta ekki ráð fyrir að lykillinn lengd afmarkast af föstum
fasti, þá er sett í og ​​líta upp, í versta tilfelli, eru línuleg á
lengd lykilsins.
Takið eftir því að fjöldi liða sem eru geymdar í trie hefur ekki áhrif á útlit upp
eða innsetning tími.
Það er aðeins fyrir áhrifum af lengd lykilsins.
>> Hins vegar að bæta færslum að segja, tæti borð tilhneigingu til að gera
Framtíðin lítur upp hægar.
Þó að þetta hljómi aðlaðandi í fyrstu, við ættum að hafa í huga að
hagstæð asymptotic flókið ekki meina að í reynd gögn
uppbygging er endilega handan háðungar.
Við verðum einnig að huga að til að geyma orð í trie við þurfum, í versta
raunin, a tala af hnúður í réttu hlutfalli til að lengd í orðið.
>> Reynir tilhneigingu til að nota mikið pláss.
Það er í mótsögn við kjötkássa borð, þar sem við þurfum aðeins eitt nýtt hnút að
geyma ýmsar lykill gildi par.
Nú, aftur í orði, stór rúm neysla virðist ekki eins stór
takast, sérstaklega í ljósi þess að nútíma tölvur hafa gígabæta og
gígabæta minni.
En það kemur í ljós að við höfum enn að hafa áhyggjur af minni notkun og
skipulag fyrir sakir flutningur, þar nútíma tölvur
hafa kerfi í stað undir hetta til að flýta minni aðgangur.
>> En þessar aðferðir virka best þegar minni aðgangur eru gerðar í samningur
svæði eða svæði.
Og hnútar af trie gæti búa hvar sem er í þeirri hrúga.
En þetta eru trade-offs að við verðum að íhuga.
>> Mundu að þegar þeir velja sér gögn uppbygging fyrir tiltekið verkefni, við
ætti að hugsa um hvers konar Rekstur gagnagrindina þarf að
stuðning og hversu mikið árangur í hverjum þessara
starfsemi mál til okkar.
Þessar aðgerðir geta jafnvel ná út bara
undirstöðu líta upp og innsetning.
Segjum að við vildum að innleiða eins konar farartæki-heill virkni, mikið
eins og Google leitarvél er.
Það er aftur alla takkana og hugsanlega gildi sem
hafa gefið forskeyti.
>> A trie er einstaklega gagnlegt við þessa aðgerð.
Það er einfalt að iterate gegnum á trie fyrir hvern staf af
forskeyti.
Rétt eins og að líta upp rekstri, við gátum fylgst ábendingum
eðli með staf.
Þá, þegar við komum í lok á forskeyti, gætum við iterate gegnum
sem eftir er hluti af gagnagrindina þar einhverju takka utan
þetta lið hafa forskeyti.
>> Það er líka auðvelt að fá þessa skráningu í stafrófsröð frá því að
þættir af börnum array eru pöntuð í stafrófsröð.
Svo vonandi að þú munt íhuga giving reynir a reyna.
Ég er Kevin Schmid, og þetta er CS50.
>> Ah, þetta er upphaf í hnignun.
Fyrirgefðu.
Sorry.
>> Slá fjögur.
Ég er út.
Sorry.
Því miður fyrir að gera við mann sem þarf að breyta þetta fara brjálaður.
>> Sorry.
Sorry.
>> Ræðumaður 1: Vel gert.
Það var mjög vel gert.