KEVIN SCHMID: Kartais, kai pastatas programa, galite naudoti duomenų struktūra vadinama žodyną. Žodynas žemėlapiai raktai, kurie yra paprastai stygos, vertybėms, ints, simbolių, rodyklė į tam tikrą objektą, ką norime. Tai tiesiog kaip paprasti žodynai kad žemėlapis žodžiai per apibrėžimus. 

Žodynai pateikti Galimybė saugoti informaciją susijęs su kažkuo ir surasti jį vėliau. Taigi, kaip mes iš tikrųjų įgyvendinti žodynas, tarkim, C kodas, kad mes galime naudoti vieną iš mūsų programų? Na, yra daug būdų, kad galėtume įgyvendinti žodyną. 

Už vieną, mes galime naudoti masyvą, kad mes dinamiškai naujo dydžio ar mes galime naudoti susijęs sąrašas, maišos lentelė arba dvejetainis medis. Bet ką mes pasirinkti, turėtume prisimindama efektyvumo ir vykdymą, įgyvendinti. Turėtume galvoti apie algoritmas įterpti ir ieškoti elementus į mūsų duomenų struktūra. 

Nes dabar, tarkime, kad mes norite naudoti eilutes kaip raktus. Pakalbėkime apie viena galimybė, duomenų struktūra vadinama TRIE. Taigi čia yra vaizdinis iš TRIE. 

Kaip paveikslas rodo, A TRIE yra medžio duomenų struktūra, mazgai sujungti. Mes matome, kad yra aiškiai šaknis mazgas su kai kurios nuorodos išplečiantis kiti mazgai. Bet ką kiekvienas mazgas sudaro? Jei mes manome, kad mes saugoti raktus su tik raides ir mes nerūpi kapitalizacija, čia iš mazgo, apibrėžimas pakaks. 

Daiktas, kurio tipas yra struct mazgas susideda iš dviejų dalių vadinamas duomenis ir vaikus. Mes palikome duomenų dalį kaip komentarą bus pakeistas komponento deklaracija kai struct mazgas įtraukti į C programa. Duomenų dalis mazgas gali būti Būlio vertė nurodoma, ar ne mazgas reiškia užbaigimą iš žodyno rakto arba ji gali būti ženklų atstovams apibrėžimą žodžio žodyne. 

Mes naudosime smiley veido nurodyti kai duomenys yra pateikti mazgas. Yra 26 elementų mūsų vaikai masyvas, vienas puslapis už raidė. Pamatysime reikšmę tai greitai. 

Leiskite gauti arčiau šaknų mazgas mūsų diagramą, kurioje nėra duomenų susijęs su juo, kaip nurodyta nebuvimas smiley veido duomenų dalis. Rodyklės nusidriekę iš dalių vaikai masyvo atstovauti ne-mazgas rodykles į kitus mazgus. Pavyzdžiui, rodyklė tęsiasi nuo Antrasis elementas vaikams atstovauja raidę B žodyne klavišą. Ir didesnių schema mes ženklina ją su B 

Atkreipkite dėmesį, kad didesnių schema, kai mes atkreipti žymeklį į kitą mazgą, jis Nesvarbu, kur Antgaliai atitinka tą kitą mazgą. Mūsų pavyzdys žodynas trie yra du žodžiai, kad ir priartinimas. Leiskite eiti per pavyzdys žiūrint duomenis rakto. 

Tarkime, mes norime ieškoti atitinkančią vertę raktų vonia. Mes pradėsime mūsų ieškoti šakninio mazgo. Tada mes priimsime pirmąją raidę mūsų raktas, B ir rasti atitinkamas vietoje mūsų vaikų masyvo. Atkreipkite dėmesį, kad yra lygiai 26 taškus masyve, po vieną kiekvienam laiške abėcėlė. Ir mes turime dėmės atstovauti abėcėlės raidžių tvarka. 

Mes pažvelgti į antrąjį indeksą tada, vienas puslapis, skirtas B. Apskritai, jei mes turėti tam tikrą raidė C mes galėtų nustatyti atitinkamą vietą į vaikų masyvas naudojant kaip tai apskaičiuoti. Galėjome naudojo didesnius vaikus masyvas jei norime pasiūlyti pažvelgti į raktai su įvairesnių simbolių, pavyzdžiui, visą ASCII simbolių rinkinys. 

Tokiu atveju, žymeklis mūsų vaikų masyvo vienas puslapis nėra lygus nuliui. Taigi mes ir toliau ieškome iki rakto pirtis. Jeigu mes kada nors susidūrė null rodyklė tinkamu vietoje vaikais masyvas, o mes vedama mazgus, tada mes turime pasakyti, kad mes negalėjo rasti nieko už tą raktą. 

Dabar, mes priimsime antrą raidę mūsų pagrindinis, ir toliau taip rodykles Tokiu būdu, kol mes pasiekti, kad mūsų raktas pabaigos. Jei mes pasiekti rakto galą be hitting bet aklavietes, null patarimų, kaip yra šiuo atveju, tada mes tik turi patikrinti dar vieną dalyką. Ar tai raktas tikrųjų žodyne? 

Jei taip, mes turime rasti vertę, taip pat smiley veido piktograma mūsų diagramą, kurioje žodis baigiasi. Jei yra kažkas saugomi duomenys, tada mes galime jį grąžinti. Pavyzdžiui, pagrindinis zoologijos nėra žodynas, nors galėtume turėti pasiekė šio rakto galą niekada pradeda null rodyklę, o mes pakartoti per TRIE. 

Jei mes bandėme ieškoti rakto pirtis, antrasis praėjusių mazgas masyvo indeksas, atitinkanti raidė H, būtų surengė null rodyklę. Taigi pirtis nėra žodyne. Ir taip trie yra unikali tuo, kad raktus niekada aiškiai saugomi duomenų struktūra. Taigi, kaip mes įterpti kažką į TRIE? 

Leiskite įdėti raktą Zoo į mūsų TRIE. Atminkite, kad smiley veido ne mazgas gali atitikti kodą į paprastas Būlio vertė rodo, kad zoologijos sode yra žodyne arba ji gali atitinka daugiau informacijos, kad mums norite susieti su pagrindine zoologijos sode, kaip ir apibrėžiant žodis ar kažkas. Tam tikrais būdais, procesas įterpti kažkas į TRIE yra panašus į žiūrint ką nors per TRIE. 

Pradėsime nuo šaknų mazgas vėl, Šie patarimų, atitinkantis Mūsų raktas raidės. Laimei, mums pavyko laikytis patarimų visą kelią, kol pasiekė rakto galas. Kadangi zoologijos sodas yra žodžio priešdėlis priartinimas, kuris yra narys žodyną, mes nereikia skirti jokių naujų mazgų. 

Mes gali keisti mazgas rodo, kad simbolių pirmaujančių į kelias ji yra mūsų žodyne klavišą. Dabar pabandykime įterpiant raktas PIRTIS į TRIE. Pradėsime nuo šakninio mazgo ir vėl vykdykite nurodymus. Bet šioje situacijoje, mes paspauskite miręs pabaigą, kol mes galėsime gauti pabaigos klavišą. Dabar, mes turime skirti keletą naujų mazgai turės skirti vienas naujas mazgas kiekvienas likęs laiškas mūsų raktą. 

Tokiu atveju, mes tiesiog reikia skirti vieną naują mazgą. Tada mes turime padaryti H puslapis nuoroda šią naują mazgas. Dar kartą, mes galime pakeisti mazgas rodo, kad simbolių kelias todėl jai atstovauja raktas į mūsų žodyną. Leiskite samprotauti apie asimptotinis sudėtingumas mūsų procedūras jie dvi operacijos. 

Pastebime, kad abiem atvejais skaičius iš žingsnius mūsų algoritmas paėmė buvo proporcingas skaičius raidės raktinį žodį. Tai tiesa. Jei norite ieškoti žodį trie tereikia pakartoti per raidės po vieną, kol jums arba pasiekti žodžio pabaigoje arba pasiekė aklavietę į TRIE. 

Ir kai jūs norite įterpti mygtuką vertė pora į TRIE naudojant procedūra aptarėme, blogiausiu atveju bus jums skiriant naują mazgas už kiekvieną laišką. Ir mes manyti, kad paskirstymas yra pastovus laikas operacija. Taigi, jei mes manome, kad rakto ilgis yra apriboti nustatytą konstantą, tiek intarpas ir ieškoti yra pastovus laiko operacijose TRIE. 

Jei mes ne pateikti šią prielaidą, kad rakto ilgis yra apribota fiksuoto pastovus, tada įkišimo ir ieškoti, blogiausiu atveju yra tiesinis ilgis klavišą. Atkreipkite dėmesį, kad laikyti daiktų skaičius į TRIE neturi įtakos ieškoti ar įterpimo laikas. Tai įtakos tik ilgis klavišą. 

Priešingai, pridedant įrašus, tarkim, maišos lentelė yra linkęs padaryti ateitis ieškoti lėčiau. Nors tai gali atrodyti patrauklus, pirmiausia, turėtume nepamiršti, kad palankus asimptotinis sudėtingumas nėra reiškia, kad praktikoje duomenis struktūra yra neišvengiamai nepriekaištingas. Mes taip pat turime manyti, kad laikyti žodis į TRIE turime, blogiausiu atveju, mazgų skaičius proporcingas su žodžiu pati ilgio. 

Tries linkę naudoti daug vietos. Štai priešingai maišos lentelės kur mes tik reikia vieną naują mazgą laikyti kai kurių pagrindinių vertės porą. Dabar vėl teoriškai, didelė erdvė vartojimas neatrodo kaip didelė spręsti, ypač turint omenyje, kad modernios kompiuteriai turi gigabaitų ir gigabaitų atminties. Tačiau paaiškėja, kad mes vis dar turime nerimauti atminties ir organizacija vardan efektyvumą, nes šiuolaikiniai kompiuteriai turėti mechanizmus, pagal dangtis pagreitinti atminties galimybes. 

Tačiau šie mechanizmai veikia geriausiai, kai atminties užklausų gaminami kompaktiškas regionuose ar teritorijose. Ir tam TRIE mazgus gali gyventi bet tos krūvos. Tačiau tai yra kompromisai kad mes turime apsvarstyti. 

Atminkite, kad, renkantis duomenis struktūrą tam tikrą užduotį, mes reikia galvoti apie tai, kas rūšių operacijos duomenų struktūra turi parama ir kiek veiklos vienas iš tų, operacijos yra svarbi mums. Šios operacijos gali net peržengia tiesiog Pagrindinė ieškoti ir įterpimas. Tarkime, mes norime įgyvendinti natūra auto-pilnas funkcionalumas, daug kaip "Google" paieškos sistema veikia. Tai yra, grąžinti visus raktus ir potencialiai vertybės turėti tam tikrą priedėlį. 

Trie vienareikšmiškai naudinga šiai operacijai. Tai paprasta pakartoti per kiekvieno charakterio trie prefiksas. Tiesiog kaip ieškoti operacijos galėtume sekti nurodymus požymis pobūdžio. Tada, kai mes atvykti į pabaigos priešdėlis, galime pakartoti per Likusi duomenų struktūros nes bet raktus po šis punktas turi priešdėlį. 

Tai taip pat lengva gauti šį įrašą abėcėlės tvarka nuo elementai vaikų masyvo yra rikiuojami pagal abėcėlę. Taigi tikiuosi jums apsvarstyti davimas bando pabandyti. Aš Kevin Schmid, ir tai yra CS50. 

Ak, tai pradžia iš nuosmukio. Aš atsiprašau. Atsiprašau. Atsiprašau. Atsiprašau. 

Strike keturis. Aš iš. Atsiprašau. Atsiprašau. Atsiprašau. Atsiprašome už tai, kad asmuo, kuris turi redaguoti šį išprotėti. 

Atsiprašau. Atsiprašau. Atsiprašau. Atsiprašau. 

GARSIAKALBIS 1: Well done. Tai buvo tikrai gerai padaryta.