>> KEVIN SCHMID: Néha, amikor az épület a programot, érdemes kihasználni a
adatstruktúra néven a szótárban.
A szótár térképek gombok, melyek általában a húrok, értékek, ints,
karakter, a mutató néhány tárgyat, amit akarunk.
Olyan, mint a hagyományos szótárak hogy a térkép szavakat a definíciók.
>> Szótárak adja meg nekünk a képes az adatok tárolására
jár valami és keresse fel később.
Szóval hogyan lehet ténylegesen alkalmazni a szótár, mondjuk, a C kód, hogy tudjuk
használja valamelyik program?
Nos, van egy csomó módon, hogy sikerült végre egy szótárban.
>> Az egyik, hogy jönne egy tömböt, hogy mi dinamikusan újra méretű vagy mi jönne egy
láncolt lista, hash tábla vagy egy bináris fa.
De bármit is úgy döntünk, mi kell szem előtt tartva a hatékonyság és a
teljesítménye a végrehajtás.
Meg kell gondolni a használt algoritmus beszúrni, és felnéz tételeket
Adataink szerkezetét.
>> Most tegyük fel, hogy mi használni kívánt karakterláncokat kulcsokat.
Beszéljünk egy lehetőség, adatstruktúrát trie nevezzük.
Tehát itt egy vizuális ábrázolás A trie.
>> Ahogy a kép is mutatja, a trie egy fa adatstruktúra a
csomópontok kapcsolódnak össze.
Látjuk, hogy nincs egyértelműen gyökér csomópont néhány link kiterjedő
más csomópontok.
De mit jelent az egyes node áll?
Ha feltételezzük, hogy mi tárolására gombok csak alfabetikus karaktereket,
nem érdekel a nagybetűk, itt van egy meghatározása a csomópont,
elegendő.
>> Egy objektum, melynek típusa struktúra node két részből áll
hívott adatok és a gyermekek.
Már elhagyta az adatok egy részét, mint a comment ki kell cserélni egy összetevő
a nyilatkozatot struct csomópont építeni egy C program.
Az adatok egy része lehet egy csomópont Logikai érték, hogy jelezze
nem a csomópont képviseli a befejezése A szótár gombot, vagy lehet, hogy egy
string meghatározása egy szó szerepel a szótárban.
>> Majd egy mosolygó arc jelzi ha az adatok van jelen egy csomópont.
Van 26 eleme a gyerekek tömb, egy index
egy betű.
Meglátjuk a jelentősége Ennek hamarosan.
>> Menjünk egy közelebbi pillantást a gyökér csomópont a mi diagram, amelynek nincs adat
társított, ahogy azt a hiányában a mosolygó arc a
adatok részét.
A nyilak a kinyúló részei A gyerekek array képviselnek non-csomópont
mutatók más csomópontokhoz.
Például, a nyíl kinyúló A második elem a gyermekek
képviseli a B betű a szótárban kulcsot.
És a nagyobb diagramon névvel illetjük is a B.
>> Megjegyezzük, hogy az ábrán a nagyobb, amikor felhívni a mutatót egy másik csomópont, az
nem számít, ha a nyílhegy megfelel ennek a másik csomópont.
A minta szótár trie tartalmaz két szó, hogy és a zoom.
Sétáljunk egy példán keresztül a keresi fel adatokat a kulcsot.
>> Tegyük fel akartuk nézni a megfelelő értéket a kulcs fürdő.
Kezdjük a felnéz A gyökér csomópont.
Akkor tegye meg az első betű a mi kulcs, B, és megtalálni a megfelelő
észrevenni a gyerekek tömbben.
Figyeljük meg, hogy pontosan 26 foltok a tömb, egy-egy levelét
az ábécé.
És mi lesz a foltok képviselik az ábécé sorrendben.
>> Majd nézd meg a második index, akkor, indexe egy, B. Általában, ha azt
Van néhány betű C is lehet meghatározni a megfelelő helyen
A gyerekek tömbben a számítás, mint ez.
Mi lehetett volna használni a nagyobb gyerekek array, ha azt akartuk, hogy ajánlani felnéz a
kulcsok szélesebb körű karakterekből mint például az egész
ASCII karakterkészlet.
>> Ebben az esetben a mutató a gyermekeink array at
index egy nem null.
Tehát fogjuk folytatni kell a munkát fel a kulcsot fürdő.
Ha valaha is találkozott a null pointer a megfelelő helyszínen, a gyermekek
array, amíg áthaladt a csomópontok, akkor meg kell mondani, hogy mi
nem talált semmit a kulcsot.
>> Nos, mi lesz a második levél kulcsfontosságú, A, és folytassa a következő
mutatók egészen addig, amíg meg elérjük a végét a gombot.
Ha elérjük a végét, a kulcs nélküli üti semmilyen zsákutcák, null mutató,
mint a jelen esetben, akkor csak a kell ellenőrizni, még egy dolog.
Ez kulcsfontosságú valójában a szótárban?
>> Ha igen, akkor kell találni egy értéket, illetve a mosolygó arc ikon a diagram, ahol a
a szó véget ér.
Ha van valami tárolt az adatokat, akkor is vissza.
Például, a kulcs állatkert nincs a szótár, még akkor is lehetett volna
elérte a végén ez a kulcs, anélkül, hogy ütő egy null pointer, míg mi
halad végig a trie.
>> Ha megpróbáltuk felnéz a kulcsot fürdő, a a második az utolsó csomópont tömb index,
megfelel a H betű, akkor tartottak null mutató.
Tehát fürdő nem szerepel a szótárban.
És így a trie egyedülálló abban, hogy a kulcsokat soha nem explicit módon tárolja
az adatszerkezetet.
Szóval hogyan lehet beszúrni valamit egy trie?
>> Menjünk be a kulcsot állatkert a mi trie.
Ne feledje, hogy a mosolygó arc egy csomópont lehet levelezési kódot egy egyszerű
Logikai érték, amely jelzi, hogy állatkertben van a szótárban, vagy lehetett
felel meg több információt, hogy mi kívánja társítani a kulcs állatkert,
mint a meghatározása a szó, vagy valami más.
Bizonyos szempontból, a folyamat be valamit a trie hasonló
keres valamit a trie.
>> Kezdjük a gyökér csomópont ismét következő mutatókat megfelelő
A leveleket a gombot.
Szerencsére meg tudtuk követni mutatók egészen addig, amíg elértük
a végén a gombot.
Mivel az állatkert a prefix szó zoom, amely tagja a
szótár, nem kell, hogy osztják az új csomópontokat.
>> Mi lehet módosítani a csomópontot, hogy jelezze, hogy a útját karakter vezető
ez jelenti a kulcsot a szótár.
Most próbáljuk behelyezése kulcsot BATH a trie.
Kezdjük a gyökér csomópontot és kövesse mutatók újra.
De ebben a helyzetben, elérünk egy halott vége előtt képesek vagyunk, hogy a
vége a kulcs.
Most akkor kell kiosztani néhány új csomópontok kell hozzá egy új
node minden fennmaradó levél a gombot.
>> Ebben az esetben, már csak be kell kiosztani egy új csomópontot.
Akkor kell, hogy a H-index referencia az új csomópontot.
Ismét lehet módosítani a csomópont azt jelzi, hogy az út a karakter
ami azt jelenti kulcs a szótár.
Nézzük oka az aszimptotikus komplexitását eljárások ezen
két művelet.
>> Megjegyezzük, hogy mindkét esetben a számot lépések algoritmus kellett hozzá
arányos a számát betűk a kulcsszó.
Ez így van.
Ha azt szeretné, hogy néz ki egy szót a trie akkor csak meg kell halad végig
a betűk egyenként, amíg nem vagy eléri a végén a szó vagy
zsákutcába a trie.
>> És ha be szeretne szúrni egy kulcsot érték pár egy trie a
eljárás beszéltünk, a legrosszabb esetben lesz akkor kiosztása egy új csomópont
minden betű.
És tegyük fel, hogy a kiosztás állandó idő működését.
Tehát, ha azt feltételezzük, hogy a kulcs hossza által határolt fix konstans, mind
behelyezése és felnéz állandó üzemeltetését a trie.
>> Ha nem teszik ezt a feltételezést, hogy az a kulcs hosszát határolt fix
állandó, akkor behelyezése és felnéz, a legrosszabb esetben is lineáris a
a kulcs hossza.
Figyeljük meg, hogy a tételek száma a tárolt A trie nem befolyásolja a megjelenés fel
vagy behelyezésének időpontjával.
Ez csak érintette a a kulcs hossza.
>> Ezzel szemben, a bejegyzések hozzáadását, mondjuk, a hash tábla hajlamos arra, hogy
jövő felnéz lassabb.
Bár ez hangzik vonzó az első, azt kell szem előtt tartani, hogy a
kedvező aszimptotikus komplexitás nem a gyakorlatban azt jelenti, hogy az adatok
struktúra szükségszerűen feddhetetlen.
Azt is figyelembe kell venni, hogy az, hogy tárolja a szó a trie amire szükségünk van, a legrosszabb
esetben a csomópontok száma arányos hogy a hossza a szó maga.
>> Megpróbálja hajlanak arra, hogy a sok helyet.
Ez ellentétben a hash tábla, ahol csak szükség van egy új csomópont
tárolni néhány kulcs-érték párt.
Most ismét elméletben, nagy tér fogyasztás nem tűnik, mint egy nagy
foglalkoznak, különös tekintettel arra, hogy a modern számítógépek gigabájt és
gigabájt memória.
De kiderül, hogy még mindig aggódni a memória használat és
szervezet kedvéért teljesítmény, mivel a modern számítógépek
van mechanizmusok meglétét a Hood, hogy gyorsítsák fel memóriát.
>> De ezek a mechanizmusok működnek a legjobban, ha memória hozzáférések készülnek kompakt
régiók és területek.
És a csomópontok egy trie is laknak bárhol, hogy a halom.
De ezek a kompromisszumok hogy figyelembe kell venni.
>> Ne feledje, hogy, amikor kiválasztják egy adat struktúra egy bizonyos feladat, mi
meg kell gondolni, milyen műveleteket az adatstruktúra kell
támogatás és mennyi a teljesítménye e, az egyes
műveletek kérdésekben nekünk.
Ezek a műveletek még túlmutat csak
alapvető felnéz és beillesztés.
Tegyük fel, hogy volna végre egy kedves Az automatikus teljes funkcionalitás, nagy
mint a Google kereső nem.
Ez azt jelenti, vissza a kulcsokat, és potenciálisan értékek
egy adott előtagot.
>> A trie egyedülállóan hasznos ehhez a művelethez.
Ez egyszerűen halad végig A trie minden karakterét
előtag.
Csakúgy, mint egy felnézni működés, tudtuk követni mutatók
karakterenként.
Ezután, amikor megérkezik a végén a prefix, tudtuk halad végig a
fennmaradó részét az adatstruktúra mivel bármely, a gombok túl
Ezen a ponton van az előtag.
>> Ez is könnyű megszerezni ezt a hirdetést betűrendben, mivel a
elemeit a gyerekek tömb sorrendben betűrendben.
Így remélhetőleg akkor figyelembe adakozás próbál egy próbát.
Schmid Kevin vagyok, és ez a CS50.
>> Ah, ez a kezdet a csökkenés.
Sajnálom.
Bocsánat.
>> Strike négy.
Kint vagyok.
Bocsánat.
Elnézést, hogy a személy, aki kell szerkeszteni ezt megbolondul.
>> Bocsánat.
Bocsánat.
>> SPEAKER 1: Szép munka.
Ez nagyon jól sikerült.