DOUG LLOYD: Nii CS50, oleme kaetud palju erinevaid andmestruktuurid õige? Me oleme näinud massiivid ning seotud nimekirjad ja hash tabeleid, ja proovib, korstnad ja järjekorrad. Me ka õppida veidi umbes puud ja hunnikutes, kuid tõesti neid kõiki lihtsalt lõpuks up on variatsioone teema. Seal tõesti on need Selline neli põhiideed et kõik muu võib taanduvad. Massiivid, ahelloendid, hash tabeleid ja proovib. Ja nagu ma ütlesin, On erinevusi nende, aga see on päris palju läheb kokku kõik me kavatseme rääkida umbes selles klassis poolest C. Aga kuidas need kõik küündima, eks? Me rääkisime plusse ja miinuseid Iga eraldi videos neile, kuid seal on palju numbreid saada visatakse ümber. Seal on palju üldist mõtteid saada visatakse ümber. Proovime ja tugevdada see vaid üks koht. Olgem kaaluda plusse vastu miinuseid, ja kaaluda mis andmestruktuur võiks olla õigus andmeid struktuuri oma konkreetsele olukorrale, olenemata sellest, millist andmete olete ladustamiseks. Sa ei pruugi alati vaja kasutada super kiire lisamise, kustutamise ja lookup on Prefiksipuu kui sa tõesti ei hooli lisada ja kustutada liiga palju. Kui teil on vaja lihtsalt kiiresti juhuslik juurdepääsu, võibolla hulga parem. Nii oletame ajama seda. Räägime iga nelja suuremate liiki andmestruktuuride et me rääkisime, ja lihtsalt näha, kui nad võiksid olla hea, ja kui nad ei pruugi olla nii hea. Nii alustame massiivid. Nii sisestamise, et on selline halb. 

Insertion lõpus massiivi on OK, Kui me ehitame massiivi läheme. Aga kui meil on vaja sisestada elemendid keskele, arvan, et tagasi sisestamise sorteerida, seal on palju minnes sobib element olemas. Ja kui me läheme sisestada kõikjal, kuid lõpuks massiiv, et ilmselt ei ole nii suur. 

Samuti kustutamist, kui me oleme kustutada lõpust massiivi, on ilmselt ka mitte nii suur kui me ei taha lahkuda tühjade lüngad, mis tavaliselt me ​​seda ei tee. Me tahame, et eemaldada element, ja siis omamoodi teha kallistama uuesti. Ja nii kustutamine elemendid massiivi, ka mitte nii suur. 

Otsing, kuigi on suur. Meil on muutmälu, konstantse ajaga otsing. Me lihtsalt öelda, seitse, ja me läheme kuni massiivi ümberpaigutamine seitse. Me ütleme, 20, koos Mine massiivi ümberpaigutamine 20. Me ei pea korrata üle. See on päris hea. 

Massiivid on ka suhteliselt lihtne sorteerida. Iga kord, kui me rääkisime sorteerimine algoritm, nagu valimise omamoodi, sisestamise sorteerida, mull sorteerida, ühendada Sorteeri me alati kasutada massiive seda teha, sest massiivid on päris lihtne sorteerida, võrreldes andmestruktuuride oleme näinud siiani. 

Nad on ka suhteliselt väike. Seal ei ole palju lisaruumi. Sa lihtsalt kõrvale täpselt nii palju kui teil on vaja hoida oma andmeid, ja see on päris palju see. Nii nad on üsna väike ja tõhus nii. Aga teine ​​negatiivne külg, kuigi on see, et nad on fikseeritud suurus. Meil on kuulutada, kuidas täpselt big me tahame, et meie massiivi olla, ja et me saame ainult üks lask seda. Me ei saa kasvada ja kahaneb see. 

Kui meil on vaja kasvada või väheneda, siis me vaja kuulutada täiesti uue massiivi, kopeerida kõik elemendid Esimene massiivi teine ​​rida. Ja kui me valesti, et aega, me peame seda uuesti teha. Ei ole nii suur. Nii massiivid ei anna meile paindlikkuse omada muutuva arvu elemente. 

Mis ahelloend, sisestamise on üsna lihtne. Me lihtsalt pühitakse peale ees. Kustutamine on ka üsna lihtne. Me peame leidma elemente. See kaasata mõned otsivad. 

Aga kui olete leidnud element otsite, kõik mida sa pead tegema on muuta kursorit, võib-olla kaks, kui teil on lingitud list-- kahekordselt seotud nimekirja, rather-- ja siis saate lihtsalt vaba sõlme. Sa ei pea minema kõike enda ümber. Sa lihtsalt muuta kahe suunanäitajaks, nii see on päris kiire. 

Otsing on halb küll, eks? Et saaksime leida element ahelloend, kas eraldi või kahekordselt seotud, meil lineaarne otsida seda. Me peame hakkama alguses ja liigutage end, või alustada lõpus liikuda algusesse. Meil ei ole random access enam. Nii et kui me teeme palju otsinguid, võib-olla ahelloend ei ole päris nii hea. 

Nad on ka väga raske sorteerida, eks? Ainult nii saab tõesti sorteeri ahelloend on sortida kui ehitada see. Aga kui sa sorteeri seda nagu ehitada see, et sa oled enam teha kiireid vahelekirjutuste enam. Sa mitte ainult laveerimine asju peale ees. Sa pead leidma õigesse kohta panna, ja siis oma sisestamist muutub peaaegu sama halb sisestades massiivi. Nii ahelloendid ei ole nii suur sorteerimine andmeid. 

Nad on ka üsna väike, suurus tark. Kahekordselt seotud nimekirja veidi suurem kui üksikult ahelloendid, mis on veidi suuremad kui massiivid, kuid see ei ole tohutult raisatud ruumi. Nii et kui ruumi on lisatasu, kuid ei ole tõesti tihe premium, see võib olla õige tee. 

Räsitabeli. Sisestamist hash tabelis on üsna lihtne. See on kaheastmeline protsess. Esiteks peame kulgema meie kaudu andmeid räsi funktsiooni saada räsikoodiga, ja siis me lisada element sisse hash tabelit, et räsikoodiga asukohta. 

Kustutamine, sarnaselt seotud nimekirja, on lihtne, kui leiad element. Sa pead leidma kõigepealt, aga siis, kui sa seda kustutada, sa lihtsalt vaja vahetada paar suunanäitajaks, kui te kasutate eraldi ühendamine. Kui te kasutate katsetamine, või kui sa ei ole kasutades aheldamine üldse Teie hash tabelit, kustutamise on tegelikult väga lihtne. Kõik, mida pead tegema, on hash andmed ja siis minge selles kohas. Ja eeldades, et sa seda ei tee mingeid kokkupõrkeid, Teil on võimalik kustutada väga kiiresti. 

Nüüd, lookup on, kus asjad natuke keerulisem. See on keskmiselt paremad kui ahelloendid. Kui te kasutate ühendamine, sul on veel seotud nimekirja, mis tähendab, sul on veel Otsing kahjustamises ahelloend. Aga kuna te võtate oma seotud nimekirja ja jagades selle üle 100 või 1000 või n elementi oma hash tabelit, sa oled ahelloendid on kõik üks nda suurus. Nad kõik on oluliselt väiksem. Olete n ahelloendid asemel Ühe seotud nimekiri suuruse n. 

Ja nii see reaalse maailma pidev tegur, mis meil üldiselt ei räägi ajas keerukus, see ei tegelikult midagi muuta siin. Nii lookup on ikka lineaarne otsida, kui te kasutate ühendamine, kuid pikkus nimekirja sa läbi otsida on väga lühike võrreldes. Jällegi, kui sorteerimine on teie eesmärk siin hash tabeli Ilmselt ei ole õige tee. Lihtsalt kasutada massiivi kui sortimine On väga oluline, et teil. 

Ja nad saavad kulgema varieeruvad suurusest. On raske öelda, kas hash tabelis on väike või suur, sest see tõesti sõltub kui suur on teie hash tabelis on. Kui oled ainus kavatse salvestamiseks viis elementi oma hash tabelit, ja teil on hash tabelis 10000 elementide seda, oled ilmselt raiskab palju ruumi. Kontrast, võid ka on väga kompaktne hash tabeleid, kuid väiksematel oma hash tabelit saab, Pikemas iga nimetatud ahelloendid saab. Ja nii seal on tõesti kuidagi määratleda täpselt sama suur hash tabelit, aga see on ilmselt ohutu öelda, et see on üldiselt saab olema suurem kui seotud nimekirja salvestamiseks samu andmeid, kuid väiksem kui Prefiksipuu. 

Ja üritab on neljas Nende struktuuride et me oleme rääkinud. Sisestamine sisse Prefiksipuu on keeruline. Seal on palju dünaamilisem mälu eraldamise, eriti alguses, kui sa oled hakanud ehitama. Aga see on pidev aega. See on ainult inimese element siin, mis muudab ta keeruline. Võttes silmitsi nullviida, malloc ruumi, sinna minna, võib-olla malloc ruumi sealt uuesti. Omamoodi hirmutamise tegur viiteid dünaamiline mälu eraldamise on takistuseks selge. Aga kui olete läbinud seda, sisestamise tegelikult on üsna lihtne, ja see on kindlasti pidevat aega. 

Kustutamine on lihtne. Kõik, mida pead tegema, on liikuda alla Paar viiteid ja vaba sõlme, nii, et on päris hea. Otsing on ka päris kiire. See on ainus, mis põhineb pikkus oma andmeid. Nii et kui kõik andmed on viie tähemärke, Näiteks, sa hoidmiseks viis tähemärgistringides oma Prefiksipuu, see võtab vaid viis sammu leida, mida te otsite. Viis on lihtsalt konstandiks, nii jälle lisamise, kustutamise ja otsimise siin on kõik pidevas ajal tõhusalt. 

Teine asi on see, et teie Prefiksipuu on tegelikult omamoodi juba sorteeritud, eks? Tänu kuidas me sisestades elemente, minnes kirja kirja teel klahvi või numbrite kaupa võti, Tavaliselt oma Prefiksipuu jõuab on Selline järjestatud nagu te ehitada seda. See ei ole tegelikult teeb mõtet mõelda sorteerimine samamoodi mõtleme see massiivid või ahelloendid, või hash tabeleid. Kuid mõnes mõttes oma Prefiksipuu on järjestatud lähete. 

Puuduseks on muidugi see, et Prefiksipuu kiiresti muutub tohutu. Igast ristmikul punkti, võite have-- kui oma võti seisneb numbrit, teil on 10 muud kohti võid minna, mis tähendab, et iga sõlme sisaldab teavet umbes andmed, mida soovite salvestada sel sõlme, pluss 10 suunanäitajaks. Mille kohta on CS50 IDE, on 80 baiti. Nii et see on vähemalt 80 baiti Iga sõlme, et te luua, ja see pole isegi lugedes andmeid. Ja kui teie sõlmed Tähtede asemel numbrit, nüüd on 26 suunanäitajaks igast asukohast. Ja 26 korda 8 on ilmselt 200 baiti, või midagi sellist. Ja sul on kapitali ja lowercase-- võite näha, kus ma lähen seda, eks? Sinu sõlmed saavad tõesti suur, ja nii Prefiksipuu ise üldiselt ei saada tõesti suur, liiga. Nii et kui ruumi on kõrge premium oma süsteemis, Prefiksipuu ei pruugi olla õige tee minna, kuigi tema muid hüvesid tulevad mängu. Ma olen Doug Lloyd. See on CS50.