>> KEVIN SCHMID: Ponekad, kada je zgrada Program, možda želite koristiti
struktura podataka poznat kao rječniku.
A rječnik zemljovidi tipke, koje su obično žice, za vrijednostima, Ints,
znakova, kazaljka na nekom objektu, što god želimo.
To je baš kao i obične rječnika Ta je karta riječi kroz definicije.
>> Rječnici daju nam Sposobnost za pohranu podataka
povezana s nečim i gledati ga kasnije.
Pa kako smo zapravo provesti rječnik u, recimo, C kod koje možemo
koristiti u jednom od naših programa?
Pa, postoji mnogo načina na koje bismo mogli provesti rječnika.
>> Za jednu, da bismo mogli koristiti niz koji smo dinamički re-size ili bismo mogli koristiti
povezani popis, hash tablicu ili binarno stablo.
No, što god odlučite, trebali bismo voditi računa o učinkovitosti i
izvedba provedbu.
Trebamo razmišljati o algoritmu koristi umetnuti i gledati stvari u
Naša struktura podataka.
>> Za sada, neka Pretpostavimo da smo želite koristiti nizove kao tipke.
Pričajmo o jednom mogućnošću, struktura podataka naziva trie.
Dakle, ovdje je vizualni prikaz od trie.
>> Kako slika govori, trie je stablo struktura podataka s
čvorovi povezani.
Vidimo da postoji jasno korijena čvor s neke poveznice proteže do
ostali čvorovi.
No, ono što se svaki čvor sastoji?
Ako pretpostavimo da smo pohranu ključeva sa samo od slova, a
ne brinu o kapitalizaciji, evo definicija čvor koji
će biti dosta.
>> Objekt čija je tip struct čvor ima dva dijela
zove podatke i djecu.
Ostavili smo dio podataka kao komentar biti zamijenjen komponente
Izjava kad struct čvor uključene u C programu.
Dio podataka od čvora može biti Boolean vrijednost naznačiti je li ili
Ne čvor predstavlja završetak riječnika ključem ili bi to moglo biti
string predstavlja definiciju od riječi u rječniku.
>> Mi ćemo koristiti smješko za označavanje Kada se podaci prisutan u čvor.
Postoji 26 elementi u našem djeca polje, jedan index
po abecedi.
Vidjet ćemo značaj to uskoro.
>> Uzmimo bliži pogled korijenskog čvora u našem dijagramu, koja nema podataka
povezane s njim, na što ukazuje Izostanak smješko u
predio za podatke.
Strelice koje se protežu od dijela djeca Polje predstavljaju ne-čvor
upućivanje na druge čvorove.
Na primjer, koji se proteže od strelica Drugi element djece
predstavlja slovo B u rječniku ključu.
I u većoj slici smo ga označiti s B.
>> Imajte na umu da se u većoj slici, kad smo povući pokazivač na drugi čvor, to
Nije važno gdje strijele zadovoljava taj drugi čvor.
Naš uzorak rječnik trie sadrži dvije riječi, da je i zoom.
Idemo prošetati kroz primjer uvidom u podatke za neku tipku.
>> Pretpostavimo da smo htjeli pogledati odgovara vrijednosti za ključ kupku.
Počet ćemo naš pogled prema gore na root čvor.
Onda ćemo uzeti prvo slovo od naših Ključ, B, i pronaći odgovarajuća
uočiti u našu djecu niz.
Uočite da postoje točno 26 mjesta u nizu, jedan za svako slovo
abeceda.
I mi ćemo imati spotova predstavljaju slova abecede u redu.
>> Mi ćemo gledati na drugom indeksa tada, index je jedan, za B. U principu, ako smo
imaju neke slovo abecede C mi može odrediti odgovarajuće mjesto
u djece niz pomoću Izračun ovako.
Dobro bi nam veće djece Niz ako smo htjeli ponuditi Potraži
tipke sa širim rasponom likova, kao cjelokupnog
ASCII skup znakova.
>> U tom slučaju, pokazivač u našu djecu niz na
index netko nije null.
Tako ćemo i dalje u potrazi do ključnog kupki.
Ako smo ikada naišli na null pokazivač na odgovarajuće mjesto u djece
Niz dok smo prelazili preko čvorova, onda ćemo morati reći da smo
nije mogao pronaći ništa za taj ključ.
>> Sada, mi ćemo poduzeti drugi pismo naš ključ, i nastavite slijediti
upućuje se na taj način sve dok ne do kraja našeg ključu.
Ako ćemo do kraja ključ bez udarca bilo slijepe ulice, null naputke,
kao što je ovdje slučaj, onda smo samo Moram provjeriti još jednu stvar.
Je li to ključ zapravo u rječniku?
>> Ako je tako, trebali bismo se naći vrijednost, te smiley ikona lice u našoj shemi gdje
Riječ završava.
Ako postoji nešto drugo spremaju s podatke, a zatim ga možemo vratiti.
Primjerice, ključ zoo nije rječnik, iako smo mogli imati
došli do kraja ovog ključa bez ikada udarajući null pointer, dok smo
ponoviti kroz trie.
>> Ako smo pokušali potražiti ključnu kupku, predzadnji čvora indeksa polja,
odgovara slova H, bi održali su null pokazivač.
Dakle kupka je nema u rječniku.
I tako trie je jedinstvena po tome što ključeva se nikada nije izričito pohranjene u
Struktura podataka.
Pa kako ćemo umetnuti nešto u trie?
>> Idemo umetnite ključ Zoološki vrt u naš trie.
Ne zaboravite da je smješko na čvoru može odgovarati u kodu za jednostavne
Boolean vrijednost naznačiti da zoološki vrt je u rječniku ili je mogao
odgovaraju dodatne informacije koje smo žele povezati s ključnim zoološkom vrtu,
kao definicija Riječ ili nešto drugo.
Na neki način, postupak za umetanje nešto u trie je sličan
gleda se nešto u trie.
>> Počet ćemo s root čvor opet, Sljedeće naputke odgovara
slova od naših ključnih.
Srećom, bili smo u mogućnosti pratiti naputke sve dok nismo stigli do
kraj ključa.
Budući da je zoološki vrt je prefiks riječi zoom, koji je član
rječnik, mi ne trebaju izdvojiti neke nove čvorove.
>> Možemo mijenjati čvor ukazuje da Put od likova koji vode do
predstavlja ključ u našem rječniku.
Sada, pokušajmo umetanja Ključ KUPKA u trie.
Počet ćemo na root čvor i opet slijediti naputke.
No, u ovoj situaciji, udario mi mrtav završiti prije nego što smo mogli dobiti
kraj ključa.
Sada ćemo morati izdvojiti neke nove čvorovi će trebati izdvojiti jedan novi
čvor za svaki preostali Pismo našeg ključa.
>> U ovom slučaju, samo trebamo izdvojiti jedan novi čvor.
Onda ćemo morati napraviti indeks H Ovaj se novi čvor.
Još jednom, možemo mijenjati čvor na pokazuju da je put od likova
što je dovelo do njega predstavlja Ključ u našem rječniku.
Neka je razlog zbog asymptotic složenost naših postupaka za njih
dvije operacije.
>> Primjećujemo da je u oba slučaja broj koraka naš algoritam uzeo je
proporcionalna broju slova u ključnoj riječi.
To je točno.
Kada želite potražiti riječi u trie trebate samo ponoviti kroz
slova jedan po jedan sve dok ili ne do kraja riječi ili
pogodak ćorsokak u trie.
>> A kad želite umetnuti ključ Vrijednost par u trie pomoću
Postupak smo razgovarali, u najgorem slučaju imat ćete dodjele novi čvor
za svako slovo.
A mi ćemo pretpostaviti da raspodjelu je konstantna vrijeme operacije.
Dakle, ako pretpostavimo da je duljina ključa omeđen fiksnom konstanta, kako
umetanje i pogledati konstantne Vrijeme radnje za trie.
>> Ako mi ne bi tu pretpostavku da Dužina ključa je omeđen fiksna
konstantna, a zatim umetanje i pogledati, u najgorem slučaju, su linearna u
Duljina ključa.
Uočite da je broj predmeta pohranjena u trie ne utječe na pogled prema gore
ili umetanje vrijeme.
To je samo utjecali Duljina ključa.
>> Za razliku od toga, dodao unose se, recimo, hash tablica ima tendenciju da se
Budućnost pogledati sporije.
Iako ovo može zvučati privlačno na prvi pogled, treba imati na umu da
povoljni asimptotičnu složenost ne znači da je u praksi podataka
Struktura je nužno besprijekorno.
Također, moramo uzeti u obzir da je za pohranu Riječ u trie trebamo, u najgorem
slučaju, broj čvorova proporcionalna duljini same riječi.
>> Pokušava imaju tendenciju da koriste puno prostora.
To je u suprotnosti s hash tablici, gdje smo samo jedan novi čvor na
pohraniti neke ključne vrijednosti par.
Sada, ponovno je u teoriji, veliki prostor Potrošnja ne čini kao veliki
nositi, pogotovo s obzirom da je moderni računala imaju gigabajta i
gigabajta memorije.
No, ispostavilo se da još uvijek imamo brinuti o korištenju memorije i
Organizacija za dobrobit performanse, jer suvremeni računala
imaju mehanizme pod Sjenilo za ubrzanje pristupa memorije.
>> No, ti mehanizmi rade najbolje kada memorije pristupi su izrađene u kompaktni
regije ili područja.
A čvorovi trie mogao nalaziti bilo gdje u toj gomili.
No, to su kompromisi koje moramo uzeti u obzir.
>> Zapamtite da, pri odabiru podatke Struktura za određeni zadatak, mi
trebali razmišljati o tome što vrste Operacije struktura podataka treba
Podrška i koliko performanse svakog od tih
operacije je stalo do nas.
Ove operacije može čak proširiti dalje od pukog
Osnovni izgled i umetanje.
Pretpostavimo da smo htjeli provesti neku vrstu auto-kompletna funkcionalnost, mnogo
kao što je Google tražilica radi.
To jest, vratiti sve tipke i potencijalno vrijednosti koje
imaju određeni prefiks.
>> Trie je jedinstveno korisne Za ovaj postupak.
To je jednostavan za ponoviti kroz trie za svaki karakter
prefiks.
Baš kao i pogled do operacije, možemo pratiti naputke
slovo po slovo.
Zatim, kada dolazimo do kraja prefiks, mogli bismo ponoviti kroz
Preostali dio strukture podataka budući da je svaka od ključeva izvan
ova točka ima prefiks.
>> To je također lako dobiti ovaj oglas abecednim redom od
dijelovi dje niz su poredani po abecedi.
Dakle, nadamo se da ćete uzeti u obzir Davanje pokušava probati.
Ja sam Kevin Schmid, a to je CS50.
>> Ah, ovo je početak od pada.
Žao mi je.
Oprostite.
>> Štrajk četiri.
Ja sam vani.
Oprostite.
Žao mi je za izradu osobu koja mora urediti polude.
>> Oprostite.
Oprostite.
>> ZVUČNIK 1: Bravo.
To je jako dobro napravljena.