Doug LLOYD: Torej, v CS50, smo iz veliko različnih podatkovnih struktur, prav? Smo videli nizi in povezana Seznami in hash tabele, in poskuša, skladi in vrste. Bomo naučili tudi malo o drevesih in kupe, ampak res vsi ti šele na koncu up pa variacije na temo. Res so ti nekako štiri osnovne zamisli da je vse ostalo lahko zavre navzdol. Nizi, povezani seznami, hash tabele, in poskuša. In kot sem rekel, ni so variacije na njih, vendar je to zelo veliko dogaja povzeti vse, kar bomo govorili približno v tem razredu v smislu C. Ampak, kako ti vse ukrep gor, kajne? Mi smo se pogovarjali o prednostih in slabostih vsakega v ločenih video posnetke na njih, ampak tam je veliko številk pridobivanje vrže okrog. Tam je veliko splošno misli pridobivanje vrže okrog. Poskusimo in utrditi je v samo enem mestu. Oglejmo pretehtati prednosti pred zaporniki, in menijo, ki je struktura podatkov je lahko zgodilo podatki struktura za določeno situacijo, ne glede na vrsto podatkov, ki ste shranjevanje. Saj ni nujno, da je vedno treba uporabiti super hitro insercijo, delecijo in iskanje za trie, če vas res ne skrbi, vstavljanje in brisanje preveč. Če potrebujete le hitro naključno dostop, morda niz je bolje. Torej, kaj je destilirati, da. Spregovorimo o vsakem od štirih glavne vrste podatkovnih struktur da smo se pogovarjali o tem, in Samo glej, ko bi jih bilo dobro, in če ne bi bilo tako dobro. Torej začnimo z nizi. Torej vstavitev, ki je nekako slabo. 

Vstavitev konec matrike je v redu, če gradimo paleto, kot gremo. Ampak, če bomo morali vstaviti elementi v sredini, pomislite na vstavljanje razvrščanje, tam je veliko spreminjajočih se prilega element tam. In tako, če bomo vstavite kjerkoli, ampak konec array, da to verjetno ni tako velika. 

Podobno, izbris, če smo brisanje od konca matrike, je verjetno tudi ni tako velik, če ne želimo pustiti prazne vrzeli, ki običajno ne bomo. Želimo, da odstranite element, in potem nekako bi bilo spet Topel. In tako brisanju elementov iz niz, tudi ni tako velika. 

Iskanje, čeprav je super. Imamo naključni dostop, stalen čas lookup. Pravkar smo rekli, sedem, in gremo za matrične premestitev sedem. Pravimo, 20, z pojdite na Niz premestitev 20. Nimamo za čez Ponovil. To je zelo dobro. 

Polja so tudi relativno enostavno rešiti. Vsakič, ko smo se pogovarjali o sortiranju algoritem, kot izbirnega vrste, Vstavitev vrste, mehurček razvrstite, združiti nekako smo vedno uporablja nize, da to storite, ker so nizi zelo enostavno sortiranje, relativno glede na podatkovne strukture smo videli doslej. 

Oni so tudi relativno majhna. Tam ni veliko dodatnega prostora. Pravkar ste v prahi natanko toliko kot ga potrebujete, da imajo svoje podatke, in to je precej, da. Torej, oni so precej majhna in učinkovito na ta način. Ampak ena negativna, čeprav, je, da so določeni v velikosti. Imamo točno izjavi, kako big želimo naša matrika biti, in smo dobili le en strel na njo. Mi ne more rasti in psihiater. 

Če bomo potrebovali, da raste ali skrči jo imamo morali razglasiti povsem novo paleto, kopiranje vseh elementov Prvi niz v drugega zaporedja. In če smo se uštel, da Čas, moramo to storiti še enkrat. Ni tako velika. Torej, nizi nam ne daje prožnost da ima spremenljivo število elementov. 

Z povezanega seznama, Vstavitev je zelo enostavno. Pravkar smo prečenje na sprednji strani. Izbris je tudi precej enostavno. Moramo najti elemente. To vključuje nekaj iskanja. 

Ampak, ko ste našli element iščete, vse, kar morate storiti je spremeniti kazalec, morda dve, če imate vezavni list-- dvakrat povezani seznam, rather-- in potem si lahko samo sprostite vozlišče. Nimate za premik vse okoli. Pravkar ste spremenili dveh kazalcev, tako da je precej hitro. 

Iskanje je slabo, čeprav, kajne? Da bi za nas, da bi našli element povezan seznamu ali enkrat ali dvakrat povezana, moramo linearna ga iščete. Moramo začeti na začetku in premaknite konec, ali začeti na koncu poti na začetku. Nimamo naključni dostop več. Torej, če smo početje veliko iskanja, morda vezavni seznam ni tako zelo dobro za nas. 

Oni so tudi v resnici težko razvrstiti, kajne? Edini način, da lahko Res razvrstiti povezanega seznama je, da ga rešiti, kot jo zgraditi. Ampak, če ste ga rešiti, kot ste zgraditi jo, nisi več kar hitro vstavljanje več. Nisi samo prečenjem stvari na sprednji strani. Moraš najti pravem mestu, da ga proda, in potem vaš vstavljanje postane skoraj tako slab kot vstavite v array. Torej, povezani seznami niso tako super za sortiranje podatkov. 

Oni so tudi zelo majhne, ​​velikost-pametno. Dvakrat povezani seznam nekoliko večja kot posamično povezanih seznamov, ki so nekoliko večje kot nizi, vendar to ni ogromno zapravili prostora. Torej, če je prostor na premijo, vendar ni res intenzivna premium, to je lahko prava pot. 

Hash tabele. Vstavljanje v hash tabelo je dokaj enostavna. To je dvostopenjski postopek. Najprej moramo teči naše podatke preko funkcija hash, da bi dobili kodo razpršitve, in potem vstavimo elementa v hash tabela na tej hash kode lokacije. 

Izbris, podobno povezani seznam, je enostavno, ko boste našli element. Moraš najprej najti, ampak potem ko ga izbrisati, morate samo za izmenjavo Nekaj ​​nasvetov, če uporabljate ločeno veriženje. Če uporabljate sondiranje, ali če niste uporablja verižni sploh V vašem hash tabele, Črtanje je pravzaprav zelo preprost. Vse, kar morate storiti, je razpršitev podatkov, nato pa pojdite na to lokacijo. In ob predpostavki, da ne imate trčenja, boste lahko zelo hitro izbrisati. 

Zdaj, lookup je, če stvari dobili malo bolj zapletena. To je v povprečju bolje kot povezanih seznamov. Če uporabljate verižni, imate še vedno povezani seznam, kar pomeni, da še vedno imajo Iskanje oškodovanje povezanega seznama. Ampak zato, ker ste ob vaš povezano seznam in ga razdelite čez 100 ali 1000 ali n elementi v vašem hash tabele, ste povezani seznami so vsi ena n velikosti. Oni so vsi bistveno manjši. Da ste n namesto povezane sezname enega povezanega seznama velikosti n. 

In tako je to v realnem svetu konstanta dejavnik, ki smo na splošno Ne govori o časovnih zahtevnosti ga, pa dejansko narediti razliko tukaj. Tako iskanje je še vedno linearna iskanje če uporabljate verižni, vendar je dolžina seznama iščete s pomočjo Zelo, zelo kratek v primerjavi. Še enkrat, če sortiranje je vaša cilj tukaj, razpršena tabela je verjetno ni prava pot. Samo uporabite array če sortiranje je zelo pomembno za vas. 

In lahko se spreminjajo velikosti. Težko je reči, ali je hash tabela je majhna ali velika, ker je res odvisno od kako velik je vaš hash tabela. Če ste šele tekoč, da bo shranjevanje pet elementov v vašem hash tabele, in imate razpršene tabele s 10.000 elementi v njej, ste verjetno izgubljamo veliko prostora. Kontrast vam pa lahko tudi imajo zelo kompaktnih hash tabele, vendar manjša vaš hash tabela dobi, daljša vsaka od teh povezanih seznamov bolnikih. In tako je res ni način, da se opredelijo ravno velikost hash tabele, ampak to je verjetno varno reči, da je v splošnem bo večja kot povezan Seznam shranjevanje enake podatke, vendar manjše od trie. 

In poskuša so četrti teh struktur da smo se pogovarjali o tem. Vstavljanje v Trie je zapleten. Tam je veliko dinamično dodeljevanje pomnilnika, zlasti na začetku, kot ste začeli graditi. Ampak to je konstanta čas. To je le človeški element tukaj, zaradi česar je težavno. Ob srečujejo null kazalec, malloc prostor, tja, morda malloc prostor od tam spet. Neke vrste ustrahovanja faktorjem kazalci v dinamično dodeljevanje pomnilnika je ovira za počistiti. Ampak, ko ste jo izbil, vstavljanje pravzaprav je precej preprost, in gotovo je konstantna čas. 

Izbris je enostavno. Vse kar morate storiti je, pluti navzdol Nekaj ​​kazalcev in prosti vozlišča, tako da je zelo dober. Iskanje je tudi precej hitro. To temelji le na dolžina vaših podatkov. Torej, če vse vaše podatke, je pet nizi znakov, na primer, ste shranjevanje pet nizi znakov v vašem Trie, je samo pet korakov do našli tisto, kar iščete. Pet je le konstanten faktor, tako še enkrat, vstavljanje, brisanje in iskanje Tukaj so vsi konstantni čas, učinkovito. 

Druga stvar je, da je vaša trie pravzaprav nekako že razporejene, kajne? V skladu s tem, kako smo vstavljanje elementi, ki ga bo pismo z dopisom od Ključ ali števka ključa, Značilno je, da vaš trie konča pa nekako razporejene kot jo gradijo. To ni res naredi Občutek, da razmišljajo o sortiranje na enak način razmišljamo o je z nizi ali povezanih seznamov, ali hash tabele. Toda v nekem smislu, vaša trie je razvrščen kot greš. 

Slaba stran je seveda, da je trie hitro postane velik. Iz vsake stični točki, boste morda have-- če vaš ključ je sestavljen iz številk, imate 10 drugih krajev, lahko greš, ki pomeni, da je vsako vozlišče vsebuje informacije o podatkih, ki jih želite shraniti v tistem vozlišču, plus 10 kazalcev. Ki na CS50 IDE, je 80 bajtov. Torej, to je najmanj 80 bajtov za vsako vozlišče, ki ga ustvarjajo, in da je niti ne računam podatkov. In če so vaši vozlišča črke namesto številk, Zdaj imate 26 kazalcev iz vsake lokacije. In 26-krat 8 je verjetno 200 bajte, ali nekaj takega. In imaš kapital in vam lowercase-- lahko vidite, kam grem s tem, kajne? Vaši vozlišča lahko dobite res velika, zato je trie sam na splošno, lahko zares veliko, preveč. Torej, če je prostor na visoko Premija na vašem sistemu, trie morda ni pravi način za iti, čeprav njegove druge ugodnosti pridejo v poštev. Sem Doug Lloyd. To je CS50.