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. Oprostite. Oprostite. 

Štrajk četiri. Ja sam vani. Oprostite. Oprostite. Oprostite. Žao mi je za izradu osobu koja mora urediti polude. 

Oprostite. Oprostite. Oprostite. Oprostite. 

ZVUČNIK 1: Bravo. To je jako dobro napravljena.