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. Më vjen keq. Më vjen keq. Më vjen keq. 

Grevë katër. Unë jam jashtë. Më vjen keq. Më vjen keq. 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. Më vjen keq. Më vjen keq. 

Gjuha 1: Të lumtë. Kjo është bërë me të vërtetë mirë.