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. Sorry. Sorry. 

Slá fjögur. Ég er út. Sorry. Sorry. Sorry. Því miður fyrir að gera við mann sem þarf að breyta þetta fara brjálaður. 

Sorry. Sorry. Sorry. Sorry. 

Ræðumaður 1: Vel gert. Það var mjög vel gert.