DOUG LLOYD: Tehát CS50, már lefedett egy csomó más adatszerkezetek, ugye? Láttuk tömbök, és az ehhez kapcsolódó listák és hash táblák, és próbál, halom és a sorban állás. Majd azt is tanulni egy kicsit mintegy fák és halmok, de tényleg ezek mind csak a végén fel, hogy variációk egy témára. Valóban vannak ezek a fajta négy alapvető ötletek hogy minden mást is szűkülnek le. Tömbök, láncolt listák, hash táblák, és próbál. És mint mondtam, variációi rájuk, de ez elég sokat fog összefoglalni mindent meg fogunk beszélni mintegy ebben az osztályban szempontjából C. De hogyan ezek az összes intézkedés, ugye? Beszéltünk az érvek és ellenérvek Az egyes különálló videók rájuk, de van egy csomó számok egyre dobott körül. Van egy csomó általános gondolatok egyre dobott körül. Próbáljuk megszilárdítása azt csak egy helyen. Nézzük mérlegelni előnyeit ellen Az ellenérvek, és úgy vélik, mely adatok szerkezete Lehet, hogy a megfelelő adatokat struktúra az adott helyzetet, bármilyen fajta adatok te tárolására. Nem feltétlenül kell mindig Használja a szupergyors elvétel, és keresési egy Trie ha igazán Nem érdekel beszúrása, törlése túl sok. Ha szüksége van csak gyorsan véletlenszerű hozzáférést, talán egy tömb jobb. Úgyhogy distill ezt. Beszéljünk a négy fő típusú adatok szerkezetek hogy beszéltünk, és csak látni, amikor lehet, hogy jó, és amikor lehet, hogy nem olyan jó. Szóval kezdjük a tömbök. Szóval behelyezés, ez a fajta rossz. 

Insertion végén egy tömb rendben van, ha építünk egy tömb, ahogy haladunk. De ha kell beszúrni elemek középre, gondoljon vissza a behelyezés rendezés, van egy csomó Az áttéréssel illik egy olyan elem is van. És így ha fogunk beilleszteni sehol, de a végén egy tömb, ez talán nem olyan nagy. 

Hasonlóképpen, törlés, kivéve, ha mi vagyunk törlése végétől egy tömb, Feltehetőleg nem olyan nagy, ha mi nem akarjuk, hogy hagyja üresen hiányosságok, ami általában nem. Azt akarjuk, hogy távolítsa el az elemet, és akkor egyfajta teszik otthonos újra. És így törlését elemek tömb, nem is olyan nagy. 

Keresése, mégis, ez nagyszerű. Van véletlenszerű hozzáférés, konstans időben keresést. Mi csak annyit hét, és megyünk a tömb áthelyezés hét. Azt mondjuk 20, a go, hogy tömb áthelyezés 20. Nem kell iterációkhoz szerte. Ez elég jó. 

A tömbök is viszonylag könnyen rendezni. Minden alkalommal beszélgettünk szelektáló algoritmus, mint például a kiválasztás sort, beillesztés sort, buborékos rendezést, merge rendezés, mi mindig tömböket kell csinálni, mert tömbök elég könnyű Rendezés képest a adatstruktúrák láttunk eddig. 

Ők is viszonylag kicsi. Ott nem sok extra helyet. Te csak félre pontosan annyi ahogy kell tartani az adatokat, és ez nagyjából azt. Tehát ők nagyon kicsi és hatékony az említett módon. De egy másik hátránya azonban, az, hogy ezek fix méretű. Van, hogy állapítsa meg, hogy pontosan hogyan big azt akarjuk tömb lenni, és mi csak kap egy lövés is. Nem tudunk növekedni és csökken ez. 

Ha kell, hogy növekszik vagy csökken, mi kell bejelenteni egy teljesen új tömb, másolja az összes elem a első tömb a második tömb. És ha elszámította magát, hogy idő, meg kell csinálni újra. Nem olyan nagy. Tehát tömbök nem ad számunkra a rugalmasságot, hogy változó számú elemekkel. 

A láncolt lista, behelyezés elég könnyű. Mi csak a host-ra az első. Törlés is nagyon egyszerű. Meg kell találnunk az elemeket. Mely magában némi keresgélés. 

De ha megtalálta az elem keres, csak annyit kell tennie, a változás egy mutató, talán két ha Csatolt list-- kétszeresen láncolt lista, rather-- és akkor is csak kiszabadítani a csomópontot. Nem kell váltani mindent körül. Te csak megváltoztatni a két mutató, úgy, hogy elég gyors. 

Keresési van rossz, ugye? Annak érdekében, hogy megtaláljuk a eleme egy láncolt lista, akár magukban, vagy kétszeresen kötött, van, hogy lineáris keresés rá. Meg kell kezdeni az elején és mozgatni a végén, vagy végén kezdődik mozgásban az elején. Nincs véletlen hozzáférésű többé. Tehát, ha csinálunk egy Sok keresés, talán A csatolt lista nem annyira jó nekünk. 

Ők is nagyon nehéz rendezni, ugye? Az egyetlen mód, akkor Tényleg rendezni egy láncolt lista az, hogy rendezni úgy, mint a kivitelezést. De ha rendezni úgy, mint kivitelezést, te már nem hogy gyors betoldások többé. Te nem csak tacking dolgokat rá az első. Meg kell találni a megfelelő helyre tedd, majd a beszúrás válik majdnem olyan rossz mint behelyezése egy tömbbe. Így kapcsolódik listák nem olyan nagy válogatás adatok. 

Ők is elég kicsi, méret-bölcs. Kétszeresen láncolt lista enyhén nagyobb, mint külön-külön láncolt listák, amelyek kissé nagyobb mint tömbök, de ez nem rengeteg elvesztegetett hely. Tehát ha a hely egy prémium, de Nem egy igazán erős prémium, ez lehet a helyes út. 

Hash táblák. Beszúrás hasító táblázat meglehetősen egyszerű. Ez egy kétlépcsős folyamat. Először is meg kell futtatni adataink segítségével a hash függvény, hogy egy hash kódot, majd betesszük az elem az hash tábla, hogy hash kódot helyét. 

Törlés, hasonló láncolt lista, könnyű, ha megtaláljuk a elemet. Meg kell találni azt az első, de aztán amikor törli azt, akkor csak meg kell cserélni Pár mutatók, ha használja külön láncolás. Ha használja szondázás, vagy ha nem segítségével láncolt egyáltalán a hash tábla, törlés valójában nagyon egyszerű. Mindössze annyit kell tennie, hogy a hash adatokat, és akkor megy arra a helyre. És feltételezve, hogy nem bármilyen ütközések, Ön képes lesz arra, hogy törölje nagyon gyorsan. 

Most, keresési van, ahol a dolgok egy kicsit bonyolultabb. Ez jobb az átlagos mint láncolt listák. Ha használja láncolás, még mindig van egy láncolt lista, ami azt jelenti, még a keresés kárára egy láncolt lista. Hanem azért, mert ön tölti kapcsolódik listát, és ketté ez több mint 100 vagy 1000 vagy n eleme a hash tábla, akkor láncolt listák mindnyájan egy n-edik méretét. Mind lényegesen kisebb. Még n láncolt listák helyett Egy láncolt lista n méretű. 

És így ez a valós állandó tényező, amit általában Nem beszélnek a futási ideje, hogy valójában csinál egy különbség van. Tehát keresési van még lineáris keresés használata esetén láncolás, de a hossza a lista Ön keres keresztül Nagyon, nagyon rövid képest. Ismét, ha válogatás az Ön cél itt, hash tábla valószínűleg nem a helyes út. Csak használ egy tömböt, ha válogatás nagyon fontos neked. 

És akkor végig nem járják a mérete. Nehéz megmondani, hogy a hash tábla kicsi vagy nagy, mert valójában attól függ, milyen nagy a hash tábla. Ha csak lesz tárolására öt elem a hash tábla, és van egy hash tábla 10.000 elemek is, akkor valószínűleg pazarlás sok helyet. Kontraszt, hogy akkor is nagyon kompakt hash táblák, de a kisebb a hash tábla lesz, Hosszabb minden egyes ilyen láncolt listák jelentkeznek. És így már tényleg nem lehet meghatározni Pontosan akkora, mint egy hash tábla, de ez valószínűleg biztonságos mondani, hogy az általánosan nagyobb lesz, mint a kapcsolt listán tárolja ugyanazokat az adatokat, de kisebb, mint egy Trie. 

És megpróbálja a negyedik E struktúrák hogy mi már beszélünk. Behe- egy Trie összetett. Van egy csomó dinamikus memóriafoglalási, főleg az elején, mint kezded építeni. De ez az állandó idő. Ez csak az emberi tényező itt teszi, hogy trükkös. Miután a találkozás null pointer, malloc helyet, ott, esetleg malloc tér onnan újra. Az a fajta megfélemlítés tényezője mutatókat memória dinamikus az akadályt, hogy egyértelmű. De ha egyszer már tisztázta, beillesztés valóban jön nagyon egyszerű, és ez minden bizonnyal nem változik az időben. 

Törlés könnyű. Mindössze annyit kell tennie, hogy navigálni le Pár mutatók és ingyenes a csomópont, szóval ez elég jó. Keresés is elég gyors. Ez csak alapul a hossza az adatokat. Tehát, ha az összes adat van Öt karakterláncok, Például te tárolására öt karaktersorainak a Trie, csak úgy öt lépésben megtalálja, amit keres. Öt mindössze egy állandó tényezőt, így ismét, inszerciójával, deléciójával, és keresési Itt megtalálja az összes állandó időben, hatékonyan. 

A másik dolog az, hogy a Trie van valójában milyen már válogatni, ugye? Azáltal, hogy hogyan vagyunk behelyezése elemek, megy levélre a gombot, vagy számjegyenként a legfontosabb, Jellemzően a Trie végül is fajta válogatni, mint építeni. Ez nem igazán tesz értelme gondolkodni válogatás ugyanúgy gondolkodunk azt tömbök, vagy kapcsolt listák, vagy hash táblák. De bizonyos értelemben, a Trie van rendezve, ahogy megy. 

A hátránya, természetesen az, hogy Egy Trie gyorsan válik hatalmas. Minden csatlakozási pontja, lehet, have-- ha a kulcs áll számjegy, Ön 10 egyéb helyen érhetők el, amelyek azt jelenti, hogy minden csomópont információkat tartalmaz a kívánt adatokat tárolni abban csomópontot, plusz 10 mutató. Melyik, a CS50 IDE, 80 bájt. Tehát legalább 80 byte minden csomópont hogy hozzon létre, és ez nem is számít adatokat. És ha a csomópontok betűk helyett számok, most már 26 mutató minden helyen. És 26-szer 8 valószínűleg 200 bájt, vagy valami ilyesmi. És van fővárosban és lowercase-- lehet lásd, hova megyek ezzel, nem igaz? Az Ön csomópontok tud igazán nagy, és így a Trie Maga összességében is igazán nagy, túl. Tehát, ha kevés a hely magas prémium a rendszer, Egy Trie lehet, hogy nem a helyes út megy, annak ellenére, hogy más előnyök jöhet számításba. Én Doug Lloyd. Ez CS50.