DOUG LLOYD: Takže ve CS50, jsme probrali mnoho různých datových struktur, v pořádku? Viděli jsme pole, a je spojena seznamy a hashovací tabulky, a snaží se, komíny a fronty. Budeme také dozvědět něco o stromy a haldách, ale ve skutečnosti to vše jen konec up je variace na téma. Tam opravdu jsou tito druh čtyř základních myšlenek že vše ostatní může se redukuje na. Pole, spojové seznamy, hashovací tabulky, a snaží se. A jak jsem řekl, že jsou variace na nich, ale to je dost hodně jít do shrnout všechno, co budeme mluvit o v této třídě, pokud jde o C. Ale jak to všechno opatření nahoru, ne? Mluvili jsme o výhodách a nevýhodách každé v oddělených videa na nich, ale je tu spousta čísel dostat hozen kolem. Je tu spousta obecné myšlenky dostat hozen kolem. Zkusme a konsolidovat že do jediného místa. Pojďme zvážit výhody proti jsou nevýhody, a zvážit což struktura dat může být ta pravá dat struktura pro vaši konkrétní situaci, bez ohledu na typ dat jste skladování. Nemusíte nutně vždy nutné použijte super rychlé vložení, vymazání, a vyhledávání z trie, pokud opravdu se nestarají o vkládání a mazání moc. Pokud potřebujete jen rychle náhodný přístup, možná pole je lepší. Takže pojďme pálit to. Pojďme se bavit o každé ze čtyř hlavní druhy datových struktur že jsme mluvili o, a prostě vidět, kdy by mohl být dobrý, a když oni by mohli nebude tak dobrá. Takže začněme s poli. Takže vložení, že to trochu špatné. 

Vložený na konci pole je v pořádku, pokud stavíme celou řadu, jak jsme jít. Ale pokud budeme potřebovat vložit prvky do středu, Vzpomeňte si na vložení třídění, je tu spousta posouvání, aby se vešly prvek tam. A tak, když budeme vložit nikde jinde než na konci pole, že to asi není tak velký. 

Podobně, mazání, pokud jsme mazání od konce pole, je asi také není tak skvělé, pokud nechceme nechat prázdné mezery, které obvykle nemáme. Chceme odstranit prvek, a pak tak nějak, aby to znovu pohodlný. A tak mazání prvků z pole, také není tak velký. 

Vyhledávání, i když, je skvělá. Máme náhodný přístup, konstantní čas vyhledávání. Právě jsme se říci, sedm, a půjdeme do pole přemístění sedm. My říkáme 20, s Jdi na array přemístění 20. Nemáme k iterovat přes. To je docela dobrý. 

Pole jsou také relativně snadno třídit. Pokaždé, když jsme mluvili o třídění algoritmus, jako je výběr druhu, insertion sort, bublinkové řazení, sloučit třídění, jsme vždycky pole, jak to udělat, protože pole jsou docela snadné třídění, vzhledem k datové struktury jsme dosud viděli. 

Jsou to také poměrně malý. Tam není moc větší prostor. Právě jste zrušil přesně tolik, kolik jak budete potřebovat držet vaše data, a to je do značné míry to. Takže jsou to docela malé a efektivní tímto způsobem. Ale další nevýhodou, i když, je to, že jsou stanoveny v velikost. Musíme přiznat, jak přesně big chceme naše pole být, a my jen jeden pokus na to. Nemůžeme růst a zmenšit ji. 

Pokud potřebujeme pěstovat nebo zmenšit to, my je třeba vyhlásit zcela novou řadu, zkopírujte všechny prvků První pole do druhého pole. A pokud se přepočítal, že čas, musíme to udělat znovu. Moc dobře ne. Takže pole nedávají nám flexibilitu mít variabilní počet prvků. 

S Google seznamu vložení je docela snadné. Prostě jsme připnout na přední straně. Vypuštění je také docela snadné. Musíme najít prvky. Které se týkají nějaké vyhledávání. 

Ale jakmile jste našli element hledáte, vše, co musíte udělat vy Je-li změnit ukazatel, možná dva, pokud máte propojené list-- dvojnásobně spojový seznam, rather-- a pak stačí uvolnit uzel. Nemusíte k posunu všechno kolem. Ty stačí změnit dva ukazatele, tak to je docela rychlý. 

Vyhledávání je špatné, že? Aby nám najít prvek v Google seznamu ať už jednotlivě nebo dvakrát spojeny, musíme lineární hledat to. Musíme začít od začátku a přesunout na konec, nebo začít na konci pohybu na začátek. Nemáme náhodný přístup ještě. Takže pokud Děláme Hodně vyhledávání, možná propojeného seznam není až tak dobré pro nás. 

Jsou také velmi obtížné třídit, že jo? Jediný způsob, jak můžete Opravdu třídit propojeného seznamu je třídit, jak jste si ji postaví. Ale pokud si ho seřadit jak vy postavit to, že jste již Díky rychlé vkládání ještě. Nejste jen připínání věci na přední. Musíte najít správné místo, aby to, a pak se vaše vložení stane se jen o tak špatné, jako vložení do matice. Takže propojené seznamy nejsou tak velký pro třídění dat. 

Jsou také docela malý, velikost-moudrý. Dvojnásob mírně spojeno seznam větší než jednotlivě provázané seznamy, , které jsou o něco větší než pole, ale není to obrovské množství nevyužité místo. Takže pokud prostor je za vysokou cenu, ale Není to opravdu intenzivní prémie, to může být ta správná cesta, jak jít. 

Hash stoly. Vložení do hash tabulky je poměrně jednoduchá. Je to dvoustupňový proces. Nejprve je potřeba spustit naše data prostřednictvím funkce hash získat hash kód, a pak vložíme prvek do hash tabulky v tomto hash kód Umístění. 

Vypuštění, podobně jako Google seznamu je snadné, jakmile zjistíte prvek. Musíte ji nejprve najít, ale pak, když jej odstranit, stačí vyměnit pár ukazatelů, pokud používáte samostatné řetězení. Pokud používáte snímání, nebo pokud si nejste za použití řetězení vůbec v hash tabulce, vypuštění je vlastně rychlé. Vše, co musíte udělat, je hash dat, a pak jít na dané místo. A za předpokladu, že ne máte nějaké kolize, budete moci velmi rychle odstranit. 

Nyní, vyhledávání je místo, kde se věci trochu složitější. To je v průměru lepší než spojových seznamů. Pokud používáte zřetězení, stále máte propojeného seznamu, což znamená, že stále mají Hledání úkor propojeného seznamu. Ale protože jste při vaší spojené Seznam a to rozdělení více než 100 nebo 1000 nebo n elementy ve vašem hash tabulce, jste spojové seznamy jsou jedním nth velikosti. Všichni jsou podstatně menší. Jste n spojeny seznamy namísto jednoho spojového seznamu velikosti n. 

A tak to real-svět konstantní faktorem, který jsme se obecně nemluví o v časové složitosti to, dělá ve skutečnosti něco změnit zde. Takže vyhledávání je stále lineární podívejte se, zda používáte zřetězení, ale délka seznamu hledáte prostřednictvím je velmi, velmi krátké srovnání. Opět platí, že pokud je třídění vašich cílem zde, hash tabulky asi není správná cesta. Stačí použít pole, pokud třídění je pro vás opravdu důležité. 

A mohou oscilují velikosti. Je těžké říci, zda je hash tabulka je malý nebo velký, protože to opravdu záleží na jak velký je váš hash tabulky je. Pokud jste jen bude uložení pět prvků ve vašem hash tabulky, a máte hash tabulku s 10.000 elementy v tom, jste pravděpodobně plýtvání hodně prostoru. Kontrast je také mají velmi kompaktní hash tabulky, ale menší vaše hash tabulky dostane, každé z těchto spojových seznamů delší dostane. A tak tam opravdu žádný způsob, jak definovat přesně velikost hash tabulky, ale to je pravděpodobně bezpečné říkat, že je to obecně Bude větší, než spojený Seznam ukládání stejná data, ale menší než trie. 

A snaží se o čtvrtou z těchto struktur že jsme mluvili o. Vkládání do trie je složitý. Je tu hodně dynamický alokace paměti, zvláště na začátku, jak jste začínají stavět. Ale je to konstantní čas. Je to jen lidský element tady, že dělá to složitější. S setkat ukazatele null, malloc prostor, tam, možná malloc prostor odtamtud znovu. Druh zastrašování faktoru ukazatele v dynamického přidělování paměti je překážka zmizí. Ale jakmile jste ji přečetl, vkládání vlastně přijde docela jednoduché, a to jistě je konstantní čas. 

Mazání je snadné. Vše, co musíte udělat, je pohybovat dolů několik ukazatelů a volného uzlu, tak to je docela dobré. Vyhledávání je také velmi rychlý. Je to jen na základě Délka vašich dat. Takže pokud všechna vaše data je pět řetězce znaků, Například, že jste ukládání pět řetězce znaků ve vašem trie, to trvá jen pět kroků na najít to, co hledáte. Five je jen konstantní faktor, tak Znovu, vkládání, mazání a vyhledávání Zde jsou všechny konstantní čas, efektivně. 

Další věc je, že vaše trie je vlastně druh již řazeno, že jo? Na základě toho, jak jsme vkládání prvků, tím, že jde písmeno dopisem z klíč, nebo po jednotlivých číslicích klíče, typicky Vaše trie skončí jako druh řazeny, jak si ho postavit. To není opravdu dělá smysl přemýšlet o tom, třídění Stejným způsobem si myslíme, že o to s poli, nebo provázané seznamy, nebo hashovací tabulky. Ale v jistém smyslu, vaše Trie je řazen as you go. 

Nevýhodou ovšem je, že Trie rychle stává obrovský. Z každého křižovatce, můžete have-- pokud váš klíč se skládá z číslic, máte 10 dalších místa, můžete jít, což Znamená to, že každý uzel obsahuje informace o datech, které chcete uložit v tomto uzlu, plus 10 ukazatelů. Což, na CS50 IDE, je 80 bytů. Takže to je alespoň 80 bajtů pro každý uzel, který vytvoříte, a to ani počítání data. A pokud vaše uzly dopisy místo číslic, Nyní máte 26 ukazatele z každého místa. A 26 krát 8 je asi 200 bajtů, nebo něco takového. A máte kapitál a lowercase-- vám může vidět, kam jdu s tím, že jo? Vaše uzly může dostat opravdu velký, a tak trie sám, celkově může opravdu velká, taky. Takže pokud prostor je za vysokou prémie na vašem systému, Trie nemusí být správný způsob, jak jít, i když jeho další výhody vstupují do hry. Jsem Doug Lloyd. To je CS50.