>> KEVIN Schmid: Ibland, när man bygger en program, kanske du vill använda en
datastruktur som kallas en ordbok.
En ordbok kartor nycklar, som är oftast strängar, till värden, Ints,
tecken, en pekare till något objekt, vad vi vill.
Det är precis som vanliga ordböcker att kart ord genom definitioner.
>> Ordböcker ger oss förmåga att lagra information
förknippas med något och slå upp det senare.
Så hur gör vi faktiskt genomför en dictionary i, säg, C-kod som vi kan
användning i någon av våra program?
Nåväl, det finns många sätt att vi skulle kunna genomföra en ordbok.
>> För en, kan vi använda en array som vi dynamiskt ändra storlek eller vi skulle kunna använda en
länkad lista, hashtabell eller ett binärt träd.
Men vad vi än väljer, bör vi vara uppmärksam på effektivitet och
utförandet av implementeringen.
Vi borde tänka på den algoritm som används att sätta in och leta upp poster i
vår datastruktur.
>> För nu, låt oss anta att vi vill använda strängar som nycklar.
Låt oss tala om en möjlighet, en datastruktur som kallas en trie.
Så här är en visuell representation av en trie.
>> Som bilden antyder, en trie är en träddatastruktur med
noder kopplas samman.
Vi ser att det finns helt klart en rot nod med några länkar som sträcker sig till
andra noder.
Men vad varje nod består av?
Om vi ​​antar att vi lagrar nycklar med endast alfabetiska tecken, och
Vi bryr oss inte om kapitalisering, Här är en definition av en nod som
tillräcklig.
>> Ett objekt vars typ är struct nod har två delar
kallas data och barn.
Vi har lämnat uppgifterna ingår som en kommentar för att ersättas av en komponent
deklaration när struct nod är införlivas i ett C-program.
Datadelen hos en nod kan vara en Booleskt värde som anger om
inte den nod representerar slutför av en ordbok nyckel eller det kan vara en
sträng som representerar definitionen av ett ord i ordlistan.
>> Vi kommer att använda en smiley för att ange när data är närvarande i en nod.
Det finns 26 element i vår barn array, ett index
per bokstav.
Vi får se vilken betydelse av detta kort.
>> Låt oss få en närmare titt på rotnoden i vårt diagram, som saknar uppgifter
samband med det, vilket framgår av den avsaknad av smiley i
datadel.
De pilar som sträcker sig från de delar som barnen array representerar icke-nod
pekare till andra noder.
Exempelvis pilen som sträcker sig från den andra delen av barn
representerar bokstaven B i en ordbok nyckel.
Och i den större schema vi märka den med ett B.
>> Notera att i den större diagrammet, när vi dra en pekare till en annan nod, det
spelar ingen roll var pilspetsen uppfyller denna andra nod.
Vår provet ordboks trie innehåller två ord, det och zooma.
Låt oss gå igenom ett exempel på leta upp uppgifter för en nyckel.
>> Antag att vi ville slå upp Motsvarande värde för nyckeln badet.
Vi börjar vår blick upp vid rotnoden.
Sen tar vi den första bokstaven i vår nyckel, B, och hittar motsvarande
plats i våra barn array.
Lägg märke till att det är exakt 26 platser i arrayen, en för varje bokstav i
alfabetet.
Och vi kommer att ha fläckarna representerar bokstäverna i alfabetet i ordning.
>> Vi tittar på det andra indexet sedan, index en, för B. I allmänhet, om vi
har någon bokstav C vi skulle kunna fastställa den motsvarande plats
i barn array med en beräkning som denna.
Vi kunde ha använt ett större barn matris om vi ville erbjuda titta upp på
nycklar med ett bredare utbud av karaktärer, såsom hela
ASCII-teckenuppsättning.
>> I detta fall pekaren i våra barn array på
index man inte är null.
Så vi ska fortsätta titta upp nyckeln badet.
Om vi ​​någonsin stött på en nollpekare på rätt plats i barnen
matris medan vi korsas noderna, då vi måste säga att vi
kunde inte hitta något för den tangenten.
>> Nu tar vi den andra bokstaven i vår nyckel, A, och fortsätter efter
pekare på detta sätt tills vi når slutet av vår nyckel.
Om vi ​​kommer till slutet av nyckeln utan träffa några återvändsgränder, null pekare,
vilket är fallet här, då bara vi måste kolla en sak.
Är det nyckeln faktiskt i ordlistan?
>> Om så är fallet, skulle vi finna ett värde, väl en smiley-ikonen i vårt diagram där
ordet slutar.
Om det är något annat som lagras med data, då kan vi lämna tillbaka den.
Till exempel, är nyckeln zoo inte i ordbok, även om vi kunde ha
nått slutet av denna nyckel utan att någonsin slå en null-pekare, medan vi
iterera igenom trie.
>> Om vi ​​försökte leta upp nyckeln bad, näst sista nods fältindex,
motsvarar bokstaven H, skulle har haft en null-pekare.
Så bad är inte i ordlistan.
Och så en trie är unik i det att knapparna är aldrig explicit lagrad i
datastrukturen.
Så hur ska vi sätta in något in i en trie?
>> Låt oss sätta i nyckeln zoo i vår trie.
Kom ihåg att en smiley på en nod skulle motsvara i koden till ett enkelt
Booleskt värde som tyder på att zoo är i ordboken eller det kan
motsvara mer information som vi vill associera med nyckel zoo,
liksom definitionen av ord eller något annat.
På sätt och vis, att processen för in något i ett trie liknar
tittar upp något i ett trie.
>> Vi börjar med rotnoden igen, Följande tips motsvarande
bokstäverna i vår nyckel.
Lyckligtvis kunde vi följa pekare ända tills vi nådde
slutet av nyckeln.
Eftersom djurparken är ett prefix till ordet zoom, vilket är en medlem av den
ordbok, behöver vi inte fördela några nya noder.
>> Vi kan modifiera noden för att indikera att banan av tecken som leder till
det utgör en nyckel i vår ordlista.
Nu ska vi försöka sätta in nyckel BAD i trie.
Vi börjar på rotnoden och följ pekare igen.
Men i den här situationen, slog vi en död slutar innan vi kan komma till
änden av nyckeln.
Nu kommer vi att behöva avsätta en del nya kontaktpunkter måste tilldela en ny
nod för varje återstående skrivelse av vår nyckel.
>> I det här fallet behöver vi bara att tilldela en ny nod.
Då kommer vi att behöva göra H-index referera till den nya noden.
Återigen kan vi modifiera den nod till indikera att banan av tecken
som leder till den representerar en nyckel i vår ordlista.
Låt oss resonera om asymptotiska komplexiteten i våra rutiner för dessa
två operationer.
>> Vi märker att i båda fallen att antalet för steg vår algoritm tog var
proportionell mot antalet av bokstäver i sökordet.
Det stämmer.
När du vill slå upp ett ord i en trie du behöver bara iterera genom
bokstäverna en efter en tills du antingen når slutet av ordet eller
träffa en återvändsgränd i trie.
>> Och när du vill lägga in en nyckel värde-par till ett trie med hjälp av
procedur som vi diskuterade, det värsta fallet kommer att få dig att tilldela en ny nod
för varje bokstav.
Och vi antar att fördelningen är en konstant tids operation.
Så om vi antar att nyckellängden är avgränsas av en fast konstant, både
insättning och leta upp är konstanta tidsverksamhet för en trie.
>> Om vi ​​inte göra detta antagande att nyckellängden är begränsad av ett fast
konstant, sedan införandet och titta upp, i värsta fall, är linjär i
längden på nyckeln.
Observera att antalet objekt som lagras i trie inte påverkar utseendet upp
eller inser tid.
Det har bara påverkats av den längden på nyckeln.
>> Däremot att lägga till poster i, säg, en hashtabell tenderar att göra
framtiden ser upp långsammare.
Även om detta kanske låter lockande i början, Vi bör hålla i minnet att en
gynnsamma asymptotisk komplexitet inte innebär att i praktiken uppgifter
strukturen är nödvändigtvis klanderfri.
Vi måste också tänka på att lagra en ord i ett trie vi behöver, i värsta
fall ett antal noder i proportion till längden av själva ordet.
>> Försöker tenderar att använda en hel del utrymme.
Det är i motsats till en hash-tabell, där vi behöver bara en ny nod till
lagra vissa nyckelvärde paret.
Nu, återigen i teorin, stort utrymme konsumtion verkar inte som en stor
hantera, speciellt med tanke på att modern datorer har gigabyte och
gigabyte minne.
Men det visar sig att vi fortfarande har att oroa sig för minnesanvändning och
organisation för den skull prestanda, eftersom moderna datorer
ha mekanismer enligt huva för att snabba upp minnesåtkomst.
>> Men dessa mekanismer fungerar bäst när minnesaccesserna är gjorda i kompakt
regioner eller områden.
Och noderna i ett trie kunde uppe någonstans i högen.
Men dessa är avvägningar att vi måste överväga.
>> Kom ihåg att när du väljer en data struktur för en viss uppgift, vi
bör tänka på vad slags operationer datastrukturen behöver
stöd och hur mycket prestandan av var och en av dem
verksamhet är viktigt för oss.
Dessa verksamheter kan till och med sträcker sig längre än bara
grundläggande utseende upp och insättning.
Antag att vi ville genomföra en slags av automatisk komplettering funktionalitet, mycket
som Googles sökmotor fungerar.
Det vill säga, tillbaka alla nycklar och potentiellt värden som
har ett givet prefix.
>> En trie är unikt användbar för denna operation.
Det är enkelt att iterera igenom den trie för varje karaktär
prefixet.
Precis som en slå upp operation Vi kunde följa pekare
tecken för tecken.
Sedan, när vi kommer till slutet av prefix, kunde vi iterera genom
återstående del av datastrukturen sedan någon av knapparna bortom
denna punkt har prefixet.
>> Det är också lätt att få den här informationen i alfabetisk ordning sedan
delar av barn arrayen är ordnade alfabetiskt.
Så förhoppningsvis kommer du att tänka på givandet försöker ett försök.
Jag är Kevin Schmid, och detta är CS50.
>> Ah, det här är början av nedgången.
Jag är ledsen.
Ursäkta.
>> Strike fyra.
Jag är ute.
Ursäkta.
Ledsen för att den som måste redigera bli galen.
>> Ursäkta.
Ursäkta.
>> SPEAKER 1: Bra gjort.
Det var riktigt bra gjort.