KEVIN SCHMID: De vegades, quan la construcció d'una programa, és possible que vulgueu utilitzar un estructura de dades coneguda com un diccionari. A Mapes Diccionari tecles, que són generalment cordes, als valors, enters, caràcters, un punter a un objecte, el que vulguem. És igual que els diccionaris normals Aquest mapa paraules a través de les definicions. 

Diccionaris ens donen la capacitat d'emmagatzemar informació associat amb alguna cosa i buscar més tard. Així que com podem posar en pràctica un Diccionari en, per exemple, el codi C que podem utilitzar en un dels nostres programes? Bé, hi ha un munt de maneres en què podríem implementar un diccionari. 

D'una banda, podríem utilitzar una matriu que dinàmicament canviar la mida o podríem utilitzar un llista enllaçada, taula hash o un arbre binari. Però qualsevol cosa que triem, hem tenir en compte l'eficiència i el rendiment de l'aplicació. Hem de pensar en l'algoritme utilitzat per inserir i cercar elements en la nostra estructura de dades. 

Per ara, anem a suposar que vulgueu utilitzar cadenes com a claus. Anem a parlar d'una de les possibilitats, una estructura de dades anomenada trie. Així que aquí hi ha una representació visual d'un trie. 

A mesura que la imatge suggereix un trie és una estructura de dades en arbre amb nodes enllaçats. Veiem que hi ha clarament una arrel node amb alguns enllaços que s'estén a altres nodes. Però què significa cada node consisteix? Si assumim que estem emmagatzemant claus amb només caràcters alfabètics i no ens preocupem per capitalització, he aquí una definició d'un node que serà suficient. 

Un objecte el tipus és struct node té dues parts trucada de dades i els nens. Hem deixat la part de dades com un comentari per ser substituït per un component declaració al node d'estructura és incorporat en un programa en C. La part de dades d'un node pot ser un Valor booleà per indicar si no el node representa la finalització d'una clau de diccionari o podria ser un cadena que representa la definició d'una paraula al diccionari. 

Farem servir una cara somrient per indicar quan les dades està present en un node. Hi ha 26 elements en el nostre array nens, un índex per caràcter alfabètic. Veurem el significat d'aquest aviat. 

Anem a prendre una mirada més propera del node arrel en el nostre diagrama, que no disposa de dades associat amb ell, com s'indica per la absència de la cara somrient al porció de dades. Les fletxes que s'estenen des de les parts de els fills de la matriu representen lliure de nodes punters a altres nodes. Per exemple, la fletxa que s'estén des el segon element de nens representa la lletra B en clau d'un diccionari. I en el diagrama més gran el etiquetem amb una B. 

Tingueu en compte que en el diagrama més gran, quan dibuixar un punter a un altre node, no importa on la punta de fletxa compleix que un altre node. El nostre trie diccionari mostra conté dues paraules, això i zoom. Anem a veure un exemple de la recerca de dades per a una clau. 

Suposem que volem cercar el valor corresponent per al bany clau. Començarem la nostra mirada cap amunt en el node arrel. Llavors anem a prendre la primera lletra de la nostra clau, B, i trobar els corresponents detectar en la nostra sèrie els nens. Observeu que hi ha exactament 26 punts en la matriu, un per cada lletra de l'alfabet. I tindrem els punts representen la lletres de l'alfabet en ordre. 

Mirarem el segon índex de llavors, índex d'un, per a B. En general, si ens tenir algun caràcter alfabètic C que podria determinar el lloc corresponent en la matriu dels nens utilitzant un càlcul com aquest. Podríem haver utilitzat nens més grans matriu si volíem oferir mirada d' tecles amb una gamma més àmplia de caràcters, com la totalitat Conjunt de caràcters ASCII. 

En aquest cas, el punter en la nostra sèrie els nens a índex no és nul. Així que seguirem buscant el bany de la clau. Si alguna vegada ens trobem amb un punter nul en el lloc adequat en els nens array mentre travessem els nodes, llavors haurem de dir que No hem pogut trobar res per aquesta tecla. 

Ara, anem a prendre la segona lletra de l' la clau, A, i continuar seguint punters d'aquesta manera fins que arribar al final de la clau. Si arribem a la final de la clau sense colpejar cap carrerons sense sortida, punters nuls, com és el cas aquí, llavors només ha de comprovar una cosa més. És això realment clau en el diccionari? 

Si és així, cal trobar un valor, o bé un icona de cara somrient al nostre diagrama on la paraula acaba. Si hi ha alguna cosa més emmagatzemat amb les dades, llavors podem tornar-lo. Per exemple, el zoològic clau no està en el diccionari, tot i que podríem tenir arribat al final d'aquesta tecla sense colpejar a un punter nul, mentre que recórrer el trie. 

Si tractem de buscar el bany de tecla, el segon per l'índex de matriu de l'últim node, corresponent a la lletra H, es han celebrat un punter nul. Així bany no és al diccionari. I així un trie és únic en què les tecles mai s'emmagatzemen de manera explícita en l'estructura de dades. Llavors, com inserim alguna cosa en un trie? 

Anem a inserir la clau zoològic a la nostra trienni. Recordi que una cara somrient en un node podria correspondre en el codi a un simple Valor booleà per indicar que el zoològic és al diccionari o podria corresponen a més informació que ens desitgi associar amb el zoo clau, com la definició de la paraula o alguna altra cosa. En certa manera, el procés per inserir alguna cosa en un trie és similar a buscar alguna cosa en un trie. 

Anem a començar amb el node arrel de nou, següents indicadors corresponents a les cartes de la clau. Per sort, hem estat capaços de seguir punters tot el camí fins que arribem a l'extrem de la clau. Des del zoològic és un prefix de la paraula de zoom, que és un membre de la diccionari, que no cal assignar els nous nodes. 

Podem modificar el node per indicar que el camí de caràcters que condueixen a representa una tecla al diccionari. Ara, anem a tractar d'inserir el BANY clau al trienni. Començarem en el node arrel i seguir els punters de nou. Però en aquesta situació, arribem a un mort acabar abans que som capaços d'arribar a la extrem de la clau. Ara, haurem d'assignar un nou nodes hauran de assignar una nova node per a cada restant carta de la clau. 

En aquest cas, només tenim assignar un node nou. Llavors haurem de fer que l'índex H fer referència a aquest nou node. Un cop més, podem modificar el node a indicar que la ruta d'accés de caràcters donant lloc al fet que representa un clau en el nostre diccionari. Anem a raonar sobre la asimptòtica complexitat dels nostres procediments per a aquests dues operacions. 

Ens adonem que en els dos casos el nombre dels passos del nostre algorisme es va prendre proporcional al nombre de lletres a la paraula clau. Això és correcte. Quan es vol buscar una paraula en una trie només ha de recórrer les lletres una per una fins que ja sigui arribar al final de la paraula o un carreró sense sortida al trienni. 

I quan es vol introduir una clau parell en un trie valor utilitzant el procediment ja vam comentar, el pitjor dels casos haurà d'assignar un nou node per a cada lletra. I anem a suposar que l'assignació és una operació constant de temps. Així que si suposem que la longitud de la clau és delimitada per una constant fixa, tant inserció i mirar cap amunt són constants operacions de temps per a un trie. 

Si no fem aquesta suposició que la longitud de la clau està limitada per una fix constant, llavors la inserció i mirar cap amunt, en el pitjor dels casos, són lineals en el longitud de la clau. Noti que el nombre d'elements emmagatzemats al trie no afecta la mirada fins o el temps d'inserció. Només ha afectat per la longitud de la clau. 

Per contra, l'addició d'entrades a, diguem, una taula hash tendeix a fer futur mirar cap amunt més lent. Si bé això pot semblar atractiu al principi, hem de tenir en compte que un complexitat asimptòtica favorables no significa que en la pràctica les dades estructura és necessàriament irreprotxable. També cal considerar que per emmagatzemar un paraula en un trie que necessitem, en el pitjor dels casos cas, un nombre de nodes proporcional de la longitud de la paraula en si mateixa. 

Tries tendeixen a utilitzar una gran quantitat d'espai. Això està en contrast amb una taula hash, on només necessitem un de nou node a emmagatzemar algun parell de valors clau. Ara, de nou, en teoria, gran espai el consum no sembla ser un gran fer front, sobretot tenint en compte que modern ordinadors tenen gigabytes i gigabytes de memòria. Però resulta que encara tenim de preocupar per l'ús de memòria i organització pel bé de rendiment, ja que les computadores modernes disposar de mecanismes en el marc del campana per accelerar l'accés de memòria. 

No obstant això, aquests mecanismes funcionen millor quan accessos de memòria es fan en compacte regions o zones. I els nodes d'un trie podrien residir en qualsevol lloc d'aquest munt. Però aquestes són les compensacions que hem de considerar. 

Recordeu que, en triar una dada estructura per a una determinada tasca, ha de pensar en quin tipus de operacions de l'estructura de dades ha de el suport i la quantitat de les prestacions de cada un dels matèria d'operacions a nosaltres. Aquestes operacions poden fins i tot estendre més enllà de simplement bàsica mirada i la inserció. Suposem que volem implementar un tipus de la funcionalitat d'autocompletar, i molt com a motor de cerca de Google fa. És a dir, tornar totes les claus i valors que potencialment tenir un prefix donat. 

Un trie és únicament útil per a aquesta operació. És senzill per recórrer trie per a cada caràcter de el prefix. Igual que una operació de mirar cap amunt, podríem seguir punters caràcter per caràcter. Després, quan vam arribar a la final de l' prefix, podríem recórrer la porció restant de l'estructura de dades des de qualsevol de les tecles més enllà aquest punt té el prefix. 

També és fàcil obtenir aquest anunci en ordre alfabètic des de la elements de la matriu nens s'ordenen alfabèticament. Així que espero que vostè consideri donar intentar l'intent. Sóc Kevin Schmid, i això és CS50. 

Ah, aquest és el començament de la disminució. Ho sento. Ho sento. Ho sento. Ho sento. 

Vaga de quatre. Estic fora. Ho sento. Ho sento. Ho sento. Ho sento per fer la persona que ha d'editar aquest es torni boig. 

Ho sento. Ho sento. Ho sento. Ho sento. 

ALTAVEU 1: Ben fet. Això estava molt ben fet.