>> KEVIN SCHMID: Dažreiz, kad ēka programmu, jūs varētu vēlēties, lai izmantotu
datu struktūra pazīstams kā vārdnīcu.
Vārdnīca kartes taustiņi, kas ir parasti stīgas, vērtībām, Ints,
simboli, rādītāju uz kādu objektu, ko mēs gribam.
Tas ir tāpat kā parastās vārdnīcās ka karšu vārdi caur definīcijām.
>> Vārdnīcas sniedz mums spēja saglabāt informāciju
saistīta ar kaut ko un meklēt to vēlāk.
Tātad, kā mēs faktiski īstenot vārdnīca, teiksim, C kodu, ka mēs varam
izmantošanai vienā no mūsu programmu?
Nu, tur ir vairāki veidi, ka mēs varētu īstenot vārdnīcu.
>> Attiecībā uz vienu, mēs varētu izmantot masīvu, ka mēs dinamiski mainīt lielumu vai mēs varētu izmantot
saistīts saraksts, hash tabulu vai bināro koku.
Bet neatkarīgi mēs izvēlamies, mums vajadzētu jāsargājas no efektivitātes un
izpildi īstenošanas.
Mums vajadzētu domāt par algoritma ievietot un meklēt priekšmetus
Mūsu datu struktūra.
>> Tagad, pieņemsim, ka mēs vēlaties izmantot stīgas, atslēgas.
Parunāsim par vienu iespēju, datu struktūra, ko sauc par Trie.
Tātad, šeit ir vizuāls attēlojums no Trie.
>> Kā liekas, Trie ir koks datu struktūra ar
mezglu saistīti kopā.
Mēs redzam, ka tur ir skaidri saknes mezgls ar dažas saites attiecina uz
citiem mezgliem.
Bet ko katrs mezgls sastāv?
Ja mēs pieņemam, ka mēs esam atslēgu glabāšanas ar tikai alfabēta burtiem, un
mums nerūp kapitalizācijas, šeit ir definīciju mezglu, kas
pietiks.
>> Objekts, kura tips ir struct mezgls ir divas daļas
aicināja datus un bērnus.
Mēs esam atstājuši datu daļa, kas komentāru aizstāt ar sastāvdaļu
deklarācijā, ja struktūrai mezgls ir iekļauts C programmu.
Datu daļa mezglā var būt Būla vērtība, kas norāda, vai
nav mezglu pārstāv pabeigšanu vārdnīcas atslēgu vai tas varētu būt
string pārstāv definīciju ar vārdu vārdnīcā.
>> Mēs izmantot smaidiņam norādītu kad dati ir klāt mezglā.
Ir 26 elementi mūsu bērni masīvs, viens indekss
katru alfabēta burtu.
Redzēsim nozīmi tas drīz.
>> Būsim tuvāk apskatīt saknes mezgla mūsu diagramma, kas nav datu
saistīta ar to, kā norāda neesamība smaidošās sejas
datu daļu.
Bultas, kas stiepjas no daļām bērni masīvu veido ne-mezglu
norādes uz citiem mezgliem.
Piemēram, arrow stiepjas no otrais elements bērniem
apzīmē burtu B vārdnīcā atslēgu.
Un lielākā diagrammā mēs marķēt ar B.
>> Jāņem vērā, ka lielākās diagramma, kad mēs izdarīt rādītāju uz citu mezglu, tas
nav svarīgi, kur bultas gals atbilst šo citu mezglu.
Mūsu izlases vārdnīca trie satur divi vārdi, kas un zoom.
Apskatīsim piemēru looking up datus par atslēgu.
>> Pieņemsim, ka mēs vēlējāmies, lai meklētu atbilstošo vērtību galveno vannā.
Mēs sāksim savu izskatu augšu saknes mezglā.
Tad mēs ņemšu pirmo burtu mūsu atslēgu, B, un atrast atbilstošo
vietas mūsu bērniem masīvā.
Ievērojiet, ka ir tieši 26 punkti masīvā, pa vienai katrā no vēstules
alfabēts.
Un mums būs plankumi pārstāv burtus alfabēta kārtībā.
>> Mēs apskatīt otrajā indeksu, tad, indekss vienu, lai B. Kopumā, ja mēs
ir dažas alfabēta burtu C mēs varētu noteikt atbilstošo vietu
ar bērnu masīvā, izmantojot aprēķinu, kā šis.
Mēs būtu varējuši izmantot lielāku bērnu masīvs, ja mēs vēlējāmies piedāvāt Look veido
taustiņi ar plašāku rakstzīmes, , piemēram, visu
ASCII rakstzīmju kopu.
>> Šajā gadījumā rādītājs mūsu bērniem masīvā pie
indekss viens nav null.
Tāpēc mēs joprojām meklējam up galveno vannā.
Ja mēs kādreiz radušās null rādītāju pie pareizas vietas bērniem
masīvs kamēr mēs šķērso mezglus, Tad mums būs teikt, ka mēs
nevarēju atrast neko par šo taustiņu.
>> Tagad mēs ņemšu otro vēstuli Mūsu galvenais, un arī turpmāk pēc
norādes šādā veidā, kamēr mēs beigs mūsu atslēgu.
Ja beigs atslēgu bez hitting strupceļus, null norādes,
kā tas ir šajā gadījumā, tad mēs tikai ir jāpārbauda vēl viena lieta.
Tas ir galvenais, kas faktiski vārdnīcā?
>> Ja tā, tad mums vajadzētu atrast vērtību, labi smiley sejas ikona mūsu diagrammā, kur
vārds beidzas.
Ja ir kaut kas cits uzglabā ar datus, tad mēs varam to atpakaļ.
Tā, piemēram, galvenais zoo nav vārdnīca, lai gan mēs varētu būt
sasnieguši šīs atslēgu, nekad hitting null rādītāju, kamēr mēs
atkārtot, izmantojot Trie.
>> Ja mēs mēģinājām meklēt atslēgas vanna, Otrais pagājušā mezglu masīva indeksu,
atbilst burtu H, būtu ir notika null rādītāju.
Tātad, vanna nav vārdnīcā.
Un tā trie ir unikāla ar to, ka atslēgas nekad nav skaidri glabāti
datu struktūra.
Tātad, kā mēs ievietot kaut ko uz Trie?
>> Pieņemsim ievietojiet atslēgu zoo mūsu Trie.
Atcerieties, ka smiley sejas pie mezglā varētu atbilst kodā uz vienkāršu
Būla vērtība, kas norāda, ka zoo ir vārdnīcā vai tas varētu
atbilst vairāk informācijas, ka mēs vēlas saistīt ar galveno zoo,
piemēram, definīciju vārds vai kaut kas cits.
Dažos veidos, process, lai ievietotu kaut uz Trie ir līdzīgs
looking up kaut kādā Trie.
>> Mēs sāksim ar to saknes mezgla atkal, Šādas norādes atbilst
vēstules no mūsu galvenajiem.
Par laimi, mēs varējām sekot norādes visu ceļu, līdz nonācām
gals atslēgu.
Tā zoo ir priedēklis vārda zoom, kas ir dalībniece
vārdnīca, mums nav nepieciešams piešķirt jaunus mezgliem.
>> Mēs varam mainīt mezglu, lai norādītu, ka ceļš rakstzīmju rezultātā
tas ir galvenais mūsu vārdnīcā.
Tagad pamēģināsim ievietojot Galvenais PIRTS uz Trie.
Mēs sāksim saknes mezgla un izpildiet norādes vēlreiz.
Bet šajā situācijā, mēs hit miris beigties pirms mēs esam spējīgi nokļūt
gals atslēgu.
Tagad mums būs nepieciešams piešķirt kādu jaunu mezgli būs nepieciešams piešķirt vienu jaunu
mezglu par katru atlikušo vēstule no mūsu atslēgas.
>> Šajā gadījumā, mums ir nepieciešams piešķirt vienu jaunu mezglu.
Tad mums būs nepieciešams, lai H indeksu atsauce šo jauno mezglu.
Atkal, mēs varam mainīt mezglu norāda, ka ceļš rakstzīmju
noved pie tā ir Galvenais mūsu vārdnīcā.
Pieņemsim spriest par asimptotiskais sarežģītība mūsu procedūru šos
divas operācijas.
>> Mēs paziņojuma, kas abos gadījumos numurs Pakāpienu mūsu algoritms bija bija
proporcionāls skaita burti atslēgvārdu.
Tas ir labi.
Ja vēlaties, lai uzmeklēt vārdu trie jums ir nepieciešams atkārtot, izmantojot
burti pa vienam, līdz jūs vai nu beigs vārdu vai
hit strupceļā ar Trie.
>> Un, ja jūs vēlaties, lai ievietotu atslēgu vērtība pāri par Trie, izmantojot
procedūru mēs apspriedām, sliktākajā gadījumā būs jums piešķirot jaunu mezglu
katram burtam.
Un mēs pieņemam, ka sadalei ir nemainīgs laika darbību.
Tātad, ja mēs pieņemam, ka atslēgas garums ir ko ierobežo noteiktu konstanti, gan
ievietošanas un meklēt ir konstants laika operācijas ir Trie.
>> Ja mums nav šo pieņēmumu, ka atslēgas garumu ierobežo fiksētu
nemainīgs, tad ievietošanas un meklēt, sliktākajā gadījumā, ir lineāra
atslēgas garums.
Ievērojiet, ka vienību skaits ir saglabāti kas Trie neietekmē izskatu up
vai ievietošanas laika.
Tas ir tikai ietekmē atslēgas garums.
>> Turpretī, pievienojot ierakstus, teiksim, hash tabulu mēdz darīt
Nākotne izskatās lēnāk.
Lai gan tas var likties pievilcīgs sākumā, mums ir jāpatur prātā, ka
labvēlīgs asimptotiskās sarežģītība nav nozīmē, ka praksē datu
struktūra ir obligāti nevainojama.
Mums jāņem vērā, ka, lai saglabātu vārds ir Trie mums ir nepieciešams, jo sliktākajā
gadījumā, vairāki mezglu proporcionāls ar garumu vārda together.
>> Mēģina mēdz izmantot daudz vietas.
Tas ir pretstatā hash tabulu, kur mums ir nepieciešama tikai viena jauna mezgla uz
uzglabāt dažas galvenās vērtības pāri.
Tagad atkal teorētiski, liela telpa patēriņš nav šķist liels
risinātu, it īpaši ņemot vērā, ka mūsdienu datori ir gigabaitiem, un
gigabaitu atmiņu.
Bet izrādās, ka mums vēl ir jāuztraucas par atmiņas izmantošanu un
organizācijas dēļ sniegumu, jo mūsdienu datoriem
ir mehānismi, ar kapuce paātrināt atmiņas piekļuvi.
>> Taču šie mehānismi darbojas vislabāk, kad atmiņas Pieejas tiek veikti kompakts
reģioniem vai teritorijām.
Un mezglus, kuru Trie varētu uzturēties jebkur šajā kaudzē.
Bet tie ir kompromisi ka mums ir jāapsver.
>> Atcerieties, ka, izvēloties datu struktūra, lai noteiktu uzdevumu, mēs
vajadzētu domāt par to, kāda veida darbības datu struktūra ir
atbalstu un cik daudz sniegumu katra no tām
Operācijas ar jautājumiem pie mums.
Šīs operācijas var pat pārsniedz tikai
pamata uzmeklēt un ievietošanas.
Pieņemsim, ka mēs vēlējāmies īstenot veida auto-pilnīgs funkcionalitāti, daudz
piemēram, Google meklēšanas dzinējs nav.
Tas ir, atpakaļ visas atslēgas un potenciāli vērtības, kas
ir dota prefiksu.
>> Trie ir unikāli noderīgs Lai veiktu šo darbību.
Tas ir vienkārši atkārtot, izmantojot trie katra raksturu
prefiksu.
Tāpat kā uzmeklēt darbību, mēs varētu sekot norādes
raksturu pēc rakstura.
Pēc tam, kad mēs nonāktu beigās priedēklis, mēs varētu atkārtot, izmantojot
atlikušo daļu datu struktūru jo jebkuru no taustiņiem aiz
Šis punkts ir prefiksu.
>> Tas ir arī viegli iegūt šo ierakstu alfabētiskā secībā, jo
elementi bērnu masīva ir pasūtīts pēc alfabēta.
Tāpēc cerams, jūs uzskatāt pasniegšanas mēģina mēģināt.
Es esmu Kevin Schmid, un tas ir CS50.
>> Ah, tas ir sākums krituma.
Piedod.
Piedodiet.
>> Strike četri.
Es esmu ārā.
Piedodiet.
Atvainojos par to personu, kas ir, lai rediģētu to go crazy.
>> Piedodiet.
Piedodiet.
>> SPEAKER 1: Labi darīts.
Tas bija ļoti labi darīts.