>> KEVIN Schmid: Ndonjëherë, kur ndërtimin e një program, ju mund të dëshironi të shfrytëzojnë një
Struktura e të dhënave e njohur si një fjalor.
Një fjalor harta çelësat, të cilat janë zakonisht vargjet, të vlerave, Ints,
chars, një tregues për një objekt, çdo gjë që ne duam.
Është vetëm si fjalorët e zakonshëm Fjalët që Harta përmes përkufizimeve.
>> Fjalorë na japin me Aftësia për të ruajtur informacione
lidhur me diçka dhe të shikojnë atë më vonë.
Deri sa nuk kemi edhe të implementojë një fjalor në, të themi, kodi C se ne mund
përdorim në një nga programet?
E pra, ka shumë mënyra që ne mund të zbatojë një fjalor.
>> Për një, ne mund të përdorim një rrjet që ne dinamike ri-madhësi ose ne mund të përdorë
lista e lidhur, me tabelë hash ose një pemë binare.
Por çdo gjë që ne kemi zgjedhur, ne duhet të jemi të ndërgjegjshëm e efikasitetit dhe
Ecuria e zbatimit.
Ne duhet të mendojmë për algorithm përdorur për të futur dhe të kërkoni në artikuj
struktura jonë e të dhënave.
>> Tani për tani, le të supozojmë se ne dëshironi të përdorni vargjet si çelësat.
Le të flasim për një mundësi, një strukturë e të dhënave të quajtur një Trie.
Kështu që këtu është një përfaqësim vizuale e një Trie.
>> Si foto sugjeron, një Trie është një strukturë e të dhënave pemë me
nyje lidhur së bashku.
Ne e shohim se ka në mënyrë të qartë një rrënjë nyjen me disa lidhje të shtrirë në
nyjet e tjera.
Por ajo që e bën çdo nyje të përbëhet nga?
Në qoftë se ne supozojmë se ne jemi ruajtjen çelësat me vetëm karaktere alfabetik, dhe
ne nuk e kujdesit për kapitalizimin, këtu është një përkufizim i një nyje që
do të mjaftojë.
>> Një objekt lloji i të cilit është struct nyje ka dy pjesë
e quajti të dhëna dhe fëmijët.
Ne e kemi lënë pjesën e të dhënave si një koment për t'u zëvendësuar me një komponent
Deklarata kur nyje struct është inkorporuar në një program C.
Pjesa dhënat e një nyje mund të jetë një Vlera boolean për të treguar nëse janë ose
nuk nyja përfaqëson përfundimin të një kyç fjalor ose ajo mund të jetë një
string përfaqëson përkufizimin nga një fjalë në fjalor.
>> Ne do të përdorim një fytyrë smiley për të treguar dhëna është i pranishëm në një nyje.
Ka 26 elemente në tonë Fëmijët e array, e indeksi
per karakter alfabetik.
Ne do të shohim rëndësinë e kjo së shpejti.
>> Le të marrë një vështrim më të afërt e nyjeve rrënjë në diagramin tonë, e cila nuk ka të dhëna të
lidhur me të, siç tregohet nga mungesa e fytyrë smiley në
pjesë e të dhënave.
Shigjetat zgjeruar nga pjesët e array fëmijët përfaqësojnë jo nyje
pointers në nyjet e tjera.
Për shembull, shigjeta zgjeruar nga elementi i dytë i fëmijëve
përfaqëson shkronjën B në një kyç të fjalorit.
Dhe në diagramin më të madhe ne e shënojnë atë me një B.
>> Vini re se në diagramin më të madhe, kur ne të nxjerrë një tregues për një tjetër nyje, ajo
nuk ka rëndësi se ku Arrowhead plotëson këtë nyje të tjera.
Mostra fjalor ynë Trie përmban dy fjalë, që dhe zoom.
Le të ecin nëpër një shembull të kërkoni deri të dhënat për një kyç.
>> Supozoni se ne të kërkuar për të parë deri vlerën përkatëse për dush kryesore.
Ne do të fillojnë shikoni tonë deri në nyjen rrënjë.
Pastaj ne do të marrin shkronjën e parë të tonë kyç, B, dhe gjeni përkatës
vend në rrjet fëmijët tonë.
Vini re se ka pikërisht 26 pika të në rrjet, një për çdo letër e
alfabetin.
Dhe ne do të kemi njollat ​​përfaqësojnë shkronjat e alfabetit në mënyrë.
>> Ne do të shikojmë në indeksin e dytë më pas, Indeksi një, për B. Në përgjithësi, në qoftë se ne
kanë disa alfabetike karakter C ne mund të përcaktojë vendin përkatës
në rrjet fëmijëve duke përdorur një llogaritje si kjo.
Ne mund të ketë përdorur një fëmijë më të mëdha array nëse kemi dashur të ofrojmë kërkoni të
çelësat me një gamë më të gjerë të karaktereve, të tilla si tërë popullatën
Karakterin ASCII vendosur.
>> Në këtë rast, akrep në grup të fëmijëve tonë në
indeksi nuk është i pavlefshëm.
Pra, ne do të vazhdojmë në kërkim up dush kyç.
Nëse ne hasur ndonjëherë një tregues null në vendin e duhur në fëmijët
array ndërsa ne përshkuar nyjet, atëherë ne do të duhet të them se ne
nuk mund të gjeni ndonjë gjë për atë çelës.
>> Tani, ne do të marrin letrën e dytë të çelësi jonë, A, dhe të vazhdojë në vijim
pointers në këtë mënyrë deri ne arritur në fund të kyç tonë.
Nëse do të arrijë në fund të kyçe pa goditur ndonjë përfundon vdekur, pointers null,
siç është rasti këtu, atëherë ne vetëm duhet të kontrolloni edhe një gjë.
A është ky kyç në të vërtetë në fjalor?
>> Nëse është kështu, ne duhet të gjejmë një vlerë, edhe një icon smiley fytyra në diagramin tonë ku
fjala përfundon.
Nëse ka diçka tjetër ruajtur me të dhënat, atëherë ne mund të kthejë atë.
Për shembull, kopshtin zoologjik çelësi nuk është në fjalor, edhe pse ne mund të kemi
arritur në fund të këtij kyç pa ndonjëherë goditur një tregues zero, ndërsa ne
iterate nëpërmjet Trie.
>> Nëse ne u përpoq të kërkoni dush kyç, dytë të indeksit array nyje të kaluar,
korrespondon letrës H, do kanë mbajtur një tregues null.
Pra dush nuk është në fjalor.
Dhe kështu një Trie është unik në atë që çelësat nuk janë të ruajtura në mënyrë të qartë në
Struktura e të dhënave.
Deri sa nuk kemi futur diçka në një Trie?
>> Le të futur çelësin kopsht zoologjik në Trie tonë.
Mos harroni se një fytyrë smiley në një nyje mund të korrespondojnë me kodin për një të thjeshtë
Vlera boolean për të treguar atë kopsht zoologjik është në fjalor, ose ajo mund të
korrespondojnë me më shumë informacion se ne dëshirojnë që të lidhen me kopshtin zoologjik kyç,
si percaktimin e fjalë apo diçka tjetër.
Në disa mënyra, procesi për të futur diçka në një Trie është e ngjashme me
duke kërkuar deri diçka në një Trie.
>> Ne do të fillojë me nyjen rrënjë përsëri, pointers mëposhtme korrespondon
shkronjat e kyç tonë.
Për fat të mirë, ne ishim në gjendje për të ndjekur pointers gjithë rrugës, derisa arritëm në
fundi i kyç.
Që kopsht zoologjik është një prefiks të fjalës zoom, e cila është anëtare e
fjalor, ne nuk kemi nevojë të ndajë çdo nyje të reja.
>> Ne mund të ndryshojë nyje për të treguar se rruga e personazheve kryesorë të
ajo përfaqëson një kyç në fjalorin tonë.
Tani, le të përpiqemi futur BATH kyç në Trie.
Ne do të fillojë në nyjen rrënjë dhe ndiqni pointers përsëri.
Por në këtë situatë, ne goditi një vdekurit të përfundojë para se ne jemi në gjendje për të marrë të
fundi i kyç.
Tani, ne do të duhet të ndajë disa të reja nyjet do të duhet të ndajë një të re
nyje për çdo mbetur Letra e kyç tonë.
>> Në këtë rast, ne vetëm duhet për të caktuar një nyje të re.
Pastaj ne do të duhet për të bërë indeksin H referencë këtë nyje të re.
Edhe një herë, ne mund të modifikoj nyje të tregojnë se rruga e karaktereve
duke çuar në atë përfaqëson një kyç në fjalorin tonë.
Le të arsyetojë rreth asymptotic Kompleksiteti i procedurave tona për këto
dy operacione.
>> Ne vërejmë se në të dy rastet numri e hapa algorithm tonë mori ishte
në proporcion me numrin e shkronjat me fjalen.
Kjo është e drejtë.
Kur ju dëshironi të kërkoni një fjalë në një Trie ju vetëm duhet të iterate përmes
shkronjat një nga një derisa ju ose arrijë në fund të fjalës ose
goditi një fund të vdekur në Trie.
>> Dhe kur ju dëshironi për të futur një kyç vlerë çift në një Trie duke përdorur
Procedura e kemi diskutuar, rastin më të keq do të keni caktimin e një nyje të re
për çdo letër.
Dhe ne do të supozojmë se ndarjen është një operacion konstante kohë.
Pra, në qoftë se ne supozojmë se gjatësia kryesore është kufizohet nga një konstante të caktuar, të dy
futje dhe të kërkoni janë konstante operacionet kohore për një Trie.
>> Nëse ne nuk do të bëjë këtë supozim që Gjatësia kyç kufizohet nga një fiks
konstante, atëherë futje dhe të kërkoni, në rastin keq, janë lineare në
gjatësia e çelësit.
Vini re se numri i artikujve ruajtur në Trie nuk ndikon në sy deri
ose kohë futje.
Është e ndikuar vetëm nga gjatësia e çelësit.
>> Në të kundërt, duke shtuar shënimet në, të themi, një tabelë hash ka tendencë për të bërë
ardhmja kërkoni ngadalshme.
Derisa kjo mund të tingëllojë si tërheqës në fillim, ne duhet të mbani në mend se një
Kompleksiteti i favorshëm asymptotic nuk do të thotë se në praktikë të dhënave
Struktura është domosdoshmërisht pa gabim.
Ne duhet të marrë në konsideratë se për të ruajtur një fjalë në një Trie ne kemi nevojë, në më të keq
rast, një numër i nyjeve proporcional me gjatësinë e vet fjale.
>> Mundohet kanë tendencë për të përdorur një shumë hapësirë.
Kjo është në kontrast me një tabelë hash, ku ne duhet vetëm një nyje të re në
të ruajtur disa palë vlerë kyç.
Tani, përsëri në teori, hapësirë ​​të madhe Konsumi nuk duket si një i madh
merren, sidomos duke pasur parasysh se moderne kompjuterët kanë gigabajt dhe
gigabajt të memories.
Por kjo rezulton se ne ende kemi të shqetësohen për përdorimin e kujtesës dhe
Organizata për hir të performancës, pasi që e kompjuterëve modern
kanë mekanizma në vend nën individualitet për të përshpejtuar qasjen e kujtesës.
>> Por këto mekanizma të punojnë më mirë kur accesses kujtesës janë bërë në kompakt
regjionet apo zonat.
Dhe nyjet e një Trie mund të banojnë kudo në atë grumbull.
Por këto janë tregtisë të humbura se ne duhet të marrin në konsideratë.
>> Mos harroni se, kur zgjedh një të dhënave Struktura për një detyrë të caktuar, ne
duhet të mendoni se çka llojet e operacionet struktura e të dhënave duhet të
mbështetje dhe sa performanca e secilit prej atyre
Operacionet çështje për ne.
Këto operacione mund edhe të shtrihen përtej vetëm
themelore look up dhe futje.
Supozoni se ne të kërkuar për të zbatuar një lloj i funksionalitetit auto-plotë, shumë më
si Google search engine bën.
Kjo është, të kthehen të gjitha çelësat dhe të potencialisht vlerat të cilat
kanë një prefiksin e dhënë.
>> Një Trie është unike dobishme për këtë operacion.
Është e hapur për iterate përmes Trie për çdo karakter të
prefix.
Ashtu si një look up operacion, ne mund të ndjekim pointers
karakter nga karakteri.
Pastaj, kur të arrijmë në fund të prefix, ne mund të iterate përmes
pjesa e mbetur e strukturës së të dhënave që ndonjë nga çelësat përtej
kjo pikë kanë prefiksin.
>> Është gjithashtu e lehtë për të marrë këtë listë në rend alfabetik që prej
Elementet e vektorit fëmijëve janë urdhëruar alfabetikisht.
Kështu që shpresojmë se ju do të marrin në konsideratë Dhënia përpiqet një provoni.
Unë jam Kevin Schmid, dhe kjo është CS50.
>> Ah, ky është fillimi e rënies.
Më vjen keq.
>> Grevë katër.
Unë jam jashtë.
Më vjen keq.
Na vjen keq për të bërë personi i cili ka për të redaktuar këtë çmendem.
>> Më vjen keq.
Më vjen keq.
>> Gjuha 1: Të lumtë.
Kjo është bërë me të vërtetë mirë.