DOUG Lloyd: Pra, në CS50, ne kemi mbuluar një shumë prej strukturave të ndryshme të të dhënave, e drejtë? Ne e kemi parë vargjeve, dhe të lidhura Listat, dhe tavolina hash, dhe përpiqet, oxhaqet dhe radhët e gjata. Ne gjithashtu do të mësojnë pak për pemë dhe grumbujt, por me të vërtetë të gjitha këto vetëm në fund duke qenë variacione mbi një temë. Ka të vërtetë janë këto lloj i katër ideve themelore se çdo gjë tjetër mund të valoj poshtë për të. Vargjeve, listat lidhura, tavolina hash, dhe të përpiqet. Dhe si i tha, nuk ka dallime në to, por kjo është shumë e shumë do të përmbledhë çdo gjë që ne jemi duke shkuar për të folur lidhje në këtë klasë në drejtim të C. Por si do të gjitha këto masa e lart, e drejtë? Ne kemi biseduar për të mirat dhe të këqijat e secilit në të veçanta video mbi ta, por ka një shumë të numrave duke u hedhur rreth. Nuk është një shumë e përgjithshme Mendimet e duke u hedhur rreth. Le të përpiqen dhe të konsolidojë kjo në vetëm një vend. Le të peshojnë të mirat kundër të këqijat, dhe të marrë parasysh që Struktura e të dhënave mund të jetë e drejtë e të dhënave Struktura për gjendjen tuaj të veçantë, çfarëdo lloji i të dhënave që ju jeni ruajtjen. Ju nuk domosdoshmërisht gjithmonë duhet të përdorni futje super të shpejtë, fshirjen, dhe lookup i një Trie nëse jeni të vërtetë nuk kujdesen për të futur dhe fshirjes shume. Nëse keni nevojë vetëm të shpejt të rastit qasje, ndoshta një grup është më e mirë. Pra, le të gjej atë. Le të flasim për secilin nga katër lloje kryesore të strukturave të të dhënave që ne kemi biseduar rreth, dhe vetëm shikoni kur ata mund të jenë të mira, dhe kur ata nuk mund të jetë aq i mirë. Pra, le të fillojë me vargjeve. Kështu futje, kjo është lloj i keq. 

Futje në fund të një grup është në rregull, në qoftë se ne jemi duke ndërtuar një grup si të shkojmë. Por në qoftë se ne kemi nevojë për të futur Elementet në mes, mendoj se mbrapa në futje lloj, nuk është një shumë e zhvendosur të përshtaten një element në atje. Dhe kështu që në qoftë se ne jemi duke shkuar për të futur kudo por fundi i një grup, që ndoshta nuk është aq e madhe. 

Në mënyrë të ngjashme, fshirje, nëse ne jemi fshirjes nga fundi i një grup, është ndoshta edhe jo aq e madhe nëse ne nuk duam të lënë boshllëqe bosh, të cilat zakonisht ne nuk bëjmë. Ne duam për të hequr një element, dhe pastaj lloj i bëjnë të rehatshëm përsëri. Dhe kështu fshirjes elemente nga një grup, edhe jo aq e madhe. 

Lookup, megjithatë, është e madhe. Ne kemi qasje të rastit, lookup kohë konstante. Ne vetëm themi shtatë, dhe ne do të shkojmë të zhvendosjes array shtatë. Ne themi 20, me lëvizje të array zhvendosjes 20. Ne nuk duhet të iterate nëpër. Kjo është shumë e mirë. 

Vargjeve janë gjithashtu relativisht e lehtë për të zgjidhur. Çdo herë kemi biseduar për një klasifikim algorithm, të tilla si lloj përzgjedhjes, lloj futje, flluskë lloj, shkrihen lloj, ne gjithmonë e përdorur vargjeve për të bërë atë, sepse vargjeve janë goxha të lehtë për të lloj, relative te strukturave dhënave ne kemi parë deri tani. 

Ata janë gjithashtu relativisht i vogël. Nuk është një shumë hapësirë ​​shtesë. Ju vetëm të lënë mënjanë saktësisht sa më shumë si ju duhet të mbani të dhënat tuaja, dhe kjo është shumë e shumë ajo. Pra, ata janë mjaft të vogla dhe efikas në këtë mënyrë. Por një tjetër downside, edhe pse, është se ata janë të fiksuara në madhësi. Ne duhet të deklarojnë me saktësi se si i madh ne duam koleksion jonë të jetë, dhe ne vetëm të marrë një e shtënë në të. Ne nuk mund të rritet dhe tkurret atë. 

Në qoftë se ne kemi nevojë të rritet ose tkurret atë, ne duhet të deklarojë një grup krejtësisht të re, kopje të të gjitha elementet e array e parë në grup të dytë. Dhe në qoftë se ne llogariti keq se kohë, ne duhet të bëjmë atë përsëri. Jo aq e madhe. Pra vargjeve nuk na jep fleksibilitetin që të ketë një numër të ndryshueshme të elementeve. 

Me një listë të lidhura, futje është shumë e lehtë. Ne vetëm litar mbi pjesën e përparme. Fshirje është gjithashtu shumë e lehtë. Ne duhet të gjejmë elementet. Që përfshijnë disa kërkim. 

Por një herë ju keni gjetur elementin ju jeni duke kërkuar për të, të gjithë ju duhet të bëni është të ndryshojë një akrep, ndoshta dy në qoftë se ju keni një i lidhur list-- një dyfish listë e lidhur, rather-- dhe atëherë ju vetëm mund të lirë nyjen. Ju nuk duhet të zhvendoset çdo gjë përreth. Ju vetëm të ndryshojë dy pointers, kështu që është mjaft i shpejtë. 

Lookup është e keqe edhe pse, e drejtë? Në mënyrë që ne për të gjetur një element në një listë të lidhura, qoftë në formë individuale apo dyfish i lidhur, ne duhet ta lineare të kërkuar atë. Ne duhet të fillojë në fillim dhe lëvizur fund, ose të fillojnë në lëvizje fund në fillim. Ne nuk kemi qasje të rastit më. Pra, nëse ne jemi duke bërë një Shumë kërkim, ndoshta një listë e lidhur nuk është krejt në mënyrë të mirë për ne. 

Ata janë gjithashtu të vërtetë e vështirë për të zgjidhur, e drejtë? E vetmja mënyrë që ju mund të të vërtetë të zgjidhur një listë e lidhur është për të zgjidhur atë si ju të ndërtuar atë. Por nëse ju zgjidhur atë si ju ndërtuar atë, ju nuk jeni duke e bërë insertions shpejtë më. Ju nuk jeni vetëm tacking gjëra onto përpara. Ju keni për të gjetur të vendin e duhur për ta vënë atë, dhe pastaj futje tuaj bëhet vetëm për aq e keqe si futur në një grup. Pra, listat e lidhura nuk janë aq e madhe për klasifikim të dhënave. 

Ata janë gjithashtu mjaft të vogla, madhësia e-mençur. Dyfish i lidhur listën pak më të mëdha se listat e lidhura në formë individuale, të cilat janë pak më të madhe se vargjeve, por kjo nuk është një sasi të madhe të hapësirës tretur. Pra, nëse hapësira është shumë i kërkuar, por jo një premium të vërtetë intensive, kjo mund të jetë mënyra e drejtë për të shkuar. 

Tavolina hash. Futje në një tabelë hash është mjaft i hapur. Është një proces me dy faza. Së pari ne kemi nevojë për të drejtuar të dhënat tona përmes një funksion hash për të marrë një kod të hash, dhe pastaj ne të futur elementin NË Tabela hash në atë lokacion kodin hash. 

Fshirje, të ngjashme me listë të lidhura, është e lehtë sapo ju të gjeni elementin. Ju keni për të gjetur atë më parë, por pastaj kur ju fshini atë, ju vetëm duhet për të shkëmbyer një çift i pointers, në qoftë se ju jeni duke përdorur chaining veçantë. Nëse jeni duke përdorur probing, ose në qoftë se ju nuk jeni duke përdorur chaining në të gjitha në tryezën tuaj hash, fshirje është në fakt të vërtetë e lehtë. Të gjithë ju duhet të bëni është të hash të dhënave, dhe pastaj të shkoni në atë vend. Dhe duke supozuar që ju nuk e bëni keni ndonjë goditjet, ju do të jetë në gjendje për të fshirë shumë shpejt. 

Tani, lookup është ajo që gjërat merrni pak më e komplikuar. Është mesatarisht më të mirë se listat e lidhura. Nëse jeni duke përdorur chaining, ju ende keni një listë e lidhur, që do të thotë ju ende keni Kërkimi dëm një listë e lidhur. Por për shkak se ju jeni duke marrë lidhur tuaj Lista e ndarë atë mbi 100 apo 1000 ose n elemente në tryezën tuaj hash, ju jeni Listat e lidhura janë të gjithë një n-madhësia. Ata janë të gjithë në thelb më të vogla. Ju keni lidhur n listat vend e një listë të lidhura me madhësi n. 

Dhe kështu kjo botës reale konstante faktor, që ne në përgjithësi mos flasim për në kompleksitetin kohë, ka të vërtetë të bëjë një ndryshim këtu. Pra lookup është ende lineare kërko në qoftë se ju jeni duke përdorur chaining, por gjatësia e listës ju jeni në kërkim përmes është shumë, shumë e shkurtër nga krahasimi. Përsëri, në qoftë se zgjidhja është tuaj Qëllimi këtu, tabela hash-së ndoshta nuk është mënyra e drejtë për të shkuar. Vetëm të përdorni një rrjet nëse sorting është me të vërtetë e rëndësishme për ju. 

Dhe ata mund të drejtuar gamë e madhësisë. Është e vështirë të thuhet nëse një tabelë hash është i vogël apo i madh, sepse me të vërtetë varet nga sa i madh tabelë hash juaj është. Nëse ju jeni vetëm do të jetë ruajtjen pesë elemente në tryezën tuaj hash, dhe ju keni një tabelë hash me 10.000 elementëve në të, ndoshta ju jeni të humbur një shumë hapësirë. Kontrasti qenë ju gjithashtu mund të kanë tavolina shumë kompakt hash, por më të vogla tryezë juaj hash merr, Sa më gjatë që secili prej këtyre listave të lidhura merr. Dhe kështu që nuk ka të vërtetë nuk ka mënyrë për të përcaktuar pikërisht madhësia e një tabelë hash, por kjo është ndoshta i sigurt për të thënë se është në përgjithësi do të jetë më e madhe se një i lidhur Lista ruajtjen të njëjtat të dhëna, por më i vogël se një Trie. 

Dhe mundohet janë katërt e ketyre strukturave që ne kemi qenë duke folur rreth. Futur në një Trie është komplekse. Nuk është një shumë e dinamik kujtese, veçanërisht në fillim, si ju jeni duke filluar për të ndërtuar. Por është koha konstante. Është vetëm element njerëzor këtu që e bën të ndërlikuar. Duke pasur të ndeshen treguesin null, malloc hapësirë, shko atje, hapësirë ​​ndoshta malloc nga atje përsëri. Lloj i faktorit frikësimit të pointers në shpërndarjen e kujtesës dinamike është pengesë për të pastruar. Por një herë ju keni pastruar atë, futje në fakt vjen mjaft e thjeshtë, dhe kjo sigurisht është koha konstante. 

Fshirje është e lehtë. Të gjithë ju duhet të bëni është të lundruar poshtë një çift ​​i pointers dhe pa nyje, kështu që kjo është shumë e mirë. Lookup është gjithashtu mjaft i shpejtë. Është e bazuar vetëm në gjatësia e të dhënave tuaja. Pra, nëse të gjitha të dhënat tuaja është pesë vargjet karakter, për shembull, ju jeni ruajtjen pesë strings karakter në Trie tuaj, ajo merr vetëm pesë hapa për të gjeni atë që ju po kërkoni. Pesë është vetëm një faktor konstant, kështu që përsëri, futje, fshirje, dhe lookup këtu janë të gjithë kohë konstante, në mënyrë efektive. 

Një tjetër gjë është se Trie juaj është në fakt renditura lloj tashmë, e drejtë? Duke u mbështetur në sa ne jemi Elementet e futni duke shkuar letrën me letër e kyç, ose shifra me shifra të çelësit, në mënyrë tipike, Trie juaj përfundon duke u lloj i të renditura si ju të ndërtuar atë. Ajo nuk ka të vërtetë e bën kuptim për të menduar për klasifikim në të njëjtën mënyrë që ne mendojmë për ajo me vargjeve, ose listat e lidhura, ose tabelat hash. Por, në një kuptim, tuaj Trie është renditur si ju shkoni. 

Dobësitë, natyrisht, është se një Trie shpejt të bëhet i madh. Nga çdo pikë kryqëzim, ju mund të have-- nëse çelësi yt përbëhet nga shifra, ju keni 10 Tjetër vende ju mund të shkoni, që do të thotë se çdo nyje përmban informacion për të dhënat që ju doni të ruajtur në atë nyje, plus 10 pointers. I cili, në CS50 IDE, është 80 bytes. Pra, kjo është të paktën 80 bytes për çdo nyje që keni krijuar, dhe kjo nuk është edhe numëruar të dhënat. Dhe nëse nyjet tuaja janë letra në vend të shifrave, tani ju keni 26 pointers nga çdo vend. Dhe 26 herë 8 është ndoshta 200 bytes, ose diçka të tillë. Dhe ju keni kapital dhe ju mund të lowercase-- shihni se ku unë jam duke shkuar me këtë, apo jo? Nyjet e juaj mund të merrni të vërtetë i madh, dhe kështu Trie vetë, në përgjithësi, mund të merrni të vërtetë e madhe, too. Pra, nëse hapësira është në një të lartë premium në sistemin tuaj, një Trie mund të mos jetë mënyra e drejtë për shko, edhe pse përfitimet e saj të tjera të hyjë në lojë. Unë jam Doug Lloyd. Kjo është CS50.