DOUG LLOYD: Takže vo CS50, sme prebrali veľa rôznych dátových štruktúr, v poriadku? Videli sme poľa, a je spojená zoznamy a hashovacie tabuľky, a snaží sa, komíny a fronty. Budeme tiež dozvedieť niečo o stromy a haldách, ale v skutočnosti to všetko len koniec up je variácia na tému. Tam naozaj sú títo druh štyroch základných myšlienok že všetko ostatné môže sa redukuje na. Pole, spojové zoznamy, hashovacie tabuľky, a snaží sa. A ako som povedal, že sú variácie na nich, ale to je dosť veľa ísť do zhrnúť všetko, čo budeme hovoriť o v tejto triede, pokiaľ ide o C. Ale ako to všetko opatrenia hore, nie? Hovorili sme o výhodách a nevýhodách každé v oddelených videa na nich, ale je tu veľa čísel dostať hodená okolo. Je tu veľa všeobecné myšlienky dostať hodená okolo. Skúsme a konsolidovať že do jediného miesta. Poďme zvážiť výhody proti sú nevýhody, a zvážiť čo štruktúra dát môže byť tá pravá dát štruktúra pre vašu konkrétnu situáciu, bez ohľadu na typ dát ste skladovania. Nemusíte nutne vždy nutné použite super rýchle vloženie, vymazanie, a vyhľadávanie z trie, ak naozaj sa nestarajú o vkladanie a mazanie Priveľa. Ak potrebujete len rýchlo náhodný prístup, možno pole je lepšie. Takže poďme páliť to. Poďme sa baviť o každej zo štyroch hlavné druhy dátových štruktúr že sme hovorili o, a jednoducho vidieť, kedy by mohol byť dobrý, a keď oni by mohli nebude tak dobrá. Takže začnime s poli. Takže vloženie, že to trochu zlé. 

Vložený na konci poľa je v poriadku, ak staviame celú radu, ako sme ísť. Ale ak budeme potrebovať vložiť prvky do stredu, Spomeňte si na vloženie triedenie, je tu veľa posúvanie, aby sa zmestili prvok tam. A tak, keď budeme vložiť nikde inde než na konci poľa, že to asi nie je tak veľký. 

Podobne, mazanie, ak sme mazanie od konca poľa, je asi tiež nie je tak skvelé, ak nechceme nechať prázdne medzery, ktoré zvyčajne nemáme. Chceme odstrániť prvok, a potom tak nejako, aby to znova pohodlný. A tak mazanie prvkov z pole, tiež nie je tak veľký. 

Vyhľadávania, aj keď, je skvelá. Máme náhodný prístup, konštantný čas vyhľadávania. Práve sme sa povedať, sedem, a pôjdeme do poľa premiestnenie sedem. My hovoríme 20, s Choď na array premiestnenie 20. Nemáme k iterovat cez. To je celkom dobrý. 

Polia sú tiež relatívne ľahko triediť. Zakaždým, keď sme hovorili o triedení algoritmus, ako je výber druhu, insertion sort, bublinkové radenie, zlúčiť triedenie, sme vždy poľa, ako to urobiť, pretože pole sú celkom jednoduché triedenie, vzhľadom k dátovej štruktúry sme doteraz videli. 

Sú to tiež pomerne malý. Tam nie je moc väčší priestor. Práve ste zrušil presne toľko, koľko ako budete potrebovať držať vaše dáta, a to je do značnej miery to. Takže sú to celkom malé a efektívne týmto spôsobom. Ale ďalšie nevýhodou, aj keď, je to, že sú stanovené v veľkosť. Musíme priznať, ako presne big chceme naše polia byť, a my len jeden pokus na to. Nemôžeme rast a zmenšiť ju. 

Ak potrebujeme pestovať alebo zmenšiť to, my je potrebné vyhlásiť úplne nový rad, skopírujte všetky prvkov Prvé pole do druhého poľa. A ak sa prepočítal, že čas, musíme to urobiť znovu. Nie je to tak veľký. Takže pole nedávajú nám flexibilitu mať variabilný počet prvkov. 

S Google zoznamu vloženie je celkom jednoduché. Jednoducho sme pripnúť na prednej strane. Vypustenie je tiež celkom jednoduché. Musíme nájsť prvky. Ktoré sa týkajú nejaké vyhľadávanie. 

Ale akonáhle ste našli element hľadáte, všetko, čo musíte urobiť vy Ak je zmeniť ukazovateľ, možno dva, ak máte prepojené list-- dvojnásobne spájať zoznam, rather-- a potom stačí uvoľniť uzol. Nemusíte k posunu všetko okolo. Tie stačí zmeniť dva ukazovatele, tak to je celkom rýchly. 

Vyhľadávanie je zlé, že? Aby nám nájsť prvok v Google zozname či už jednotlivo alebo dvakrát spojené, musíme lineárne hľadať to. Musíme začať od začiatku a presunúť na koniec, alebo začať na konci pohybu na začiatok. Nemáme náhodný prístup ešte. Takže ak Robíme Veľa vyhľadávania, možno prepojeného zoznam nie je až tak dobré pre nás. 

Sú tiež veľmi ťažké triediť, že jo? Jediný spôsob, ako môžete Naozaj triediť prepojeného zoznamu je triediť, ako ste si ju postaví. Ale ak si ho zoradiť ako vy postaviť to, že ste už Vďaka rýchle vkladanie ešte. Nie ste len pripínanie veci na prednej. Musíte nájsť správne miesto, aby to, a potom sa vaše vloženie stane sa len o tak zlé, ako vloženie do matice. Takže prepojené zoznamy nie sú tak veľký pre triedenie dát. 

Sú tiež celkom malý, veľkosť-múdry. Dvojnásobne mierne spojené zoznam väčšie ako jednotlivo previazané zoznamy, , Ktoré sú o niečo väčšie ako pole, ale nie je to obrovské množstvo nevyužité miesto. Takže ak priestor je za vysokú cenu, ale Nie je to naozaj intenzívne prémie, to môže byť tá správna cesta, ako ísť. 

Hash stoly. Vloženie do hash tabuľky je pomerne jednoduchá. Je to dvojstupňový proces. Najprv je potrebné spustiť naše dáta prostredníctvom funkcia hash získať hash kód, a potom vložíme prvok do hash tabuľky v tomto hash kód Umiestnenie. 

Vypustenie, podobne ako Google zoznamu je ľahké, akonáhle zistíte prvok. Musíte ju najprv nájsť, ale potom, keď ho odstrániť, stačí vymeniť pár ukazovateľov, ak používate samostatné reťazenie. Ak používate snímanie, alebo ak si nie ste za použitia reťazenie vôbec v hash tabuľke, vypustenie je vlastne rýchle. Všetko, čo musíte urobiť, je hash dát, a potom ísť na dané miesto. A za predpokladu, že nie máte nejaké kolízie, budete môcť veľmi rýchlo odstrániť. 

Teraz, vyhľadávanie je miesto, kde sa veci trochu zložitejšie. To je v priemere lepšie než spojových zoznamov. Ak používate zreťazenie, stále máte prepojeného zoznamu, čo znamená, že stále majú Hľadanie úkor prepojeného zoznamu. Ale pretože ste pri vašej spojenej Zoznam a to rozdelenie viac ako 100 alebo 1000 alebo n elementy vo vašom hash tabuľke, ste spojové zoznamy sú jedným nth veľkosti. Všetci sú podstatne menšie. Ste n spojené zoznamy namiesto jedného spojovaceho zoznamu veľkosti n. 

A tak to real-svet konštantný faktorom, ktorý sme sa všeobecne nehovorí o v časovej zložitosti to, robí v skutočnosti niečo zmeniť tu. Takže vyhľadávanie je stále lineárny pozrite sa, či používate zreťazenie, ale dĺžka zoznamu hľadáte prostredníctvom je veľmi, veľmi krátke porovnanie. Opäť platí, že ak je triedenie vašich cieľom tu, hash tabuľky asi nie je správna cesta. Stačí použiť pole, ak triedenie je pre vás naozaj dôležité. 

A môžu oscilujú veľkosti. Je ťažké povedať, či je hash tabuľka je malý alebo veľký, pretože to naozaj záleží na aký veľký je váš hash tabuľky je. Ak ste len bude uloženie päť prvkov vo vašom hash tabuľky, a máte hash tabuľku s 10.000 elementy v tom, ste pravdepodobne plytvanie veľa priestoru. Kontrast je tiež majú veľmi kompaktný hash tabuľky, ale menšie vaše hash tabuľky dostane, každej z týchto spojových zoznamov dlhšiu dostane. A tak tam naozaj žiadny spôsob, ako definovať presne veľkosť hash tabuľky, ale to je pravdepodobne bezpečné hovoriť, že je to všeobecne Bude väčší ako pripojený Zoznam ukladanie rovnaké dáta, ale menšie ako trie. 

A snaží sa o štvrtú z týchto štruktúr že sme hovorili o. Vkladanie do trie je zložitý. Je tu veľa dynamický alokácie pamäti, najmä na začiatku, ako ste začínajú stavať. Ale je to konštantná čas. Je to len ľudský element tu, že robí to zložitejšie. S stretnúť ukazovatele null, malloc priestor, tam, možno malloc priestor odtiaľ znovu. Druh zastrašovania faktora ukazovatele v dynamického prideľovanie pamäte je prekážka zmizne. Ale akonáhle ste ju prečítal, vkladanie vlastne príde celkom jednoduché, a to iste je konštantná čas. 

Mazanie je ľahké. Všetko, čo musíte urobiť, je pohybovať dole niekoľko ukazovateľov a voľného uzla, tak to je celkom dobré. Vyhľadávanie je tiež veľmi rýchly. Je to len na základe Dĺžka vašich dát. Takže ak všetky vaše dáta je päť reťazca znakov, Napríklad, že ste ukladanie päť reťazce znakov vo vašom trie, to trvá len päť krokov na nájsť to, čo hľadáte. Five je len konštantný faktor, tak Znova, vkladanie, mazanie a vyhľadávanie Tu sú všetky konštantné čas, efektívne. 

Ďalšia vec je, že vaše trie je vlastne druh už je zoradený, že jo? Na základe toho, ako sme vkladanie prvkov, tým, že ide písmeno listom z kľúč, alebo po jednotlivých čísliciach kľúče, typicky Vaša trie skončí ako druh radené, ako si ho postaviť. To nie je naozaj robí zmysel premýšľať o tom, triedenie Rovnakým spôsobom si myslíme, že o to s poli, alebo previazané zoznamy, alebo hashovacie tabuľky. Ale v istom zmysle, vaše Trie je radený as you go. 

Nevýhodou však je, že Trie rýchlo stáva obrovský. Z každého križovatke, môžete have-- ak váš kľúč sa skladá z číslic, máte 10 ďalších miesta, môžete ísť, čo Znamená to, že každý uzol obsahuje informácie o dátach, ktoré chcete uložiť v tomto uzle, plus 10 ukazovateľov. Čo, na CS50 IDE, je 80 bytov. Takže to je aspoň 80 bajtov pre každý uzol, ktorý vytvoríte, a to ani počítanie dáta. A ak vaše uzly listy miesto číslic, Teraz máte 26 ukazovatele z každého miesta. A 26 krát 8 je asi 200 bajtov, alebo niečo také. A máte kapitál a lowercase-- vám môže vidieť, kam idem s tým, že jo? Vaša uzly môže dostať naozaj veľký, a tak trie sám, celkovo môže naozaj veľká, taky. Takže ak priestor je za vysokú prémie na vašom systéme, Trie nemusí byť správny spôsob, ako ísť, aj keď jeho ďalšie výhody vstupujú do hry. Som Doug Lloyd. To je CS50.