KEVIN Schmid: Ás veces, cando a construción dun programa, pode querer usar un estrutura de datos coñecida como un dicionario. Un dicionario claves mapas, que son xeralmente cordas, cos valores, Ints, caracteres, un punteiro para un obxecto, o que queiramos. É como dicionarios comúns Que mapa palabras través de axustes. 

Dicionarios nos ofrecer o capacidade de almacenar información asociado a algo e procura-lo máis tarde. Entón, como é que imos realmente implementar un dicionario, por exemplo, en código C que pudermos usar en un dos nosos programas? Así, hai unha serie de formas que poderiamos aplicar un dicionario. 

Por unha banda, poderíamos utilizar unha matriz que dinámica re-size ou poderiamos usar un lista ligada, táboa hash ou unha árbore binaria. Pero o que quere que nós escoller, hai que ser consciente da eficiencia e da desempeño da implementación. Debemos pensar sobre o algoritmo usado para introducir e buscar os elementos en a estrutura de datos. 

Por agora, imos supor que nós quere usar cadeas como claves. Imos falar sobre unha posibilidade, unha estrutura de datos chamada de trie. Entón aquí está unha representación visual dun trie. 

Como a imaxe suxire, un trie é unha estrutura de datos en árbore con nós conectados. Vemos que hai claramente unha raíz nó con algúns enlaces que se estende ata outros nós. Pero o que é que cada nodo consiste? Se asumimos que estamos almacenar claves con só caracteres alfabéticos, e que non se preocupan a capitalización, aquí está unha definición dun nó que será suficiente. 

Un obxecto cuxo tipo é struct nó ten dúas pezas chamada de datos e nenos. Nós deixamos a parte de datos como un comentario para ser substituído por un compoñente declaración cando nodo struct é incorporados nun programa C. A parte de datos dun nodo pode ser un Valor booleano para indicar se non representa o no a conclusión dunha chave de dicionario ou pode ser unha cadea que representa a definición dunha palabra no dicionario. 

Imos usar un rostro sorridente para indicar cando os datos están presentes nun nodo. Hai 26 elementos na nosa variedade nenos, un índice por carácter alfabético. Imos ver o significado deste breve. 

Imos mirar máis de preto do nodo raíz no noso diagrama, que non ten datos asociada con el, tal como indica a ausencia do rostro sorridente no porción de datos. As frechas que se estenden a partir das partes de os fillos de matriz representan non nodo punteiros para outros nós. Por exemplo, a frecha que se estende desde o o segundo elemento de nenos representa a letra B nunha chave de dicionario. E no diagrama maior que rótulo-la cun B. 

Teña en conta que, no diagrama de máis, cando deseñar un punteiro a outro no, el Non importa onde a punta da frecha cumpre que outro nodo. O noso dicionario mostra contén trie dúas palabras, que e zoom. Imos examinar un exemplo de mirando cara arriba de datos para unha chave. 

Supoña que quería buscar o valor correspondente ao baño de clave. Imos comezar a nosa mirada cara arriba no nodo raíz. Entón nós imos ter a primeira letra do noso clave, B, e atopar o correspondente detectar, na nosa disposición fillos. Teña en conta que hai exactamente 26 puntos na matriz, un para cada letra o alfabeto. E nós imos ter os puntos representan o letras do alfabeto en orde. 

Nós imos ollar para a segunda índice, logo índice de un, para B. En xeral, se Ten algún character C nós podería determinar o punto correspondente na matriz nenos a usar un cálculo así. Poderiamos usar un nenos maiores array se queriamos ofrecer ollar-se de teclas con unha ampla gama de caracteres, , Como o todo Conxunto de caracteres ASCII. 

Neste caso, o punteiro na nosa gama nenos en índice non é nulo. Entón, imos continuar a buscar o baño de clave. Se algunha vez atopou un punteiro nulo no lugar axeitado nos nenos array mentres atravesamos os nós, entón nós imos ter que dicir que nós non podería atopar calquera cousa a esta chave. 

Agora, imos dar a segunda letra nosa clave, A, e continuar seguindo punteiros, deste xeito ata que nós chegar ao final da nosa clave. Se chegar ao final da clave sen bater nos becos sen saída, os punteiros nulos, como é o caso aquí, entón nós só Ten que comprobar unha cousa. É esta chave realmente no dicionario? 

Se é así, hai que atopar un valor, ben a icona do Smiley cara na nosa diagrama onde a palabra remata. Se hai algo máis almacenado con os datos, entón podemos devolve-lo. Por exemplo, o xardín zoolóxico de chave non está no dicionario, aínda que puidésemos ter acadar o fin desta chave sen nunca bater un punteiro nulo, mentres nós percorrer a trie. 

Se tente ollar para o baño de clave, o segundo para índice de matriz do último nodo, correspondente á letra H, que realizaron un punteiro nulo. Entón baño non está no dicionario. E así un trie é único en que as claves nunca son explicitamente almacenada en a estrutura de datos. Entón, como imos introducir algo nunha trie? 

Imos introducir a clave zoolóxico na nosa trie. Lembre que un rostro sorridente nun nodo podería corresponder en código para un simple Valor booleano para indicar que zoo está no dicionario ou podería corresponden a máis información que nós quere asociar co zoolóxico clave, como a definición do palabra ou outra cousa. De certa forma, o proceso para introducir algo nun trie é semellante ao buscando algo nunha trie. 

Imos comezar co nó raíz de novo, seguintes punteiros correspondentes a as letras da nosa clave. Por sorte, fomos capaces de seguir punteiros todo o camiño ata chegar o extremo da chave. Desde zoolóxico é un prefixo da palabra zoom, que é membro da dicionario, non reservar os novos nós. 

Podemos modificar o nó para indicar que o camiño de caracteres que conducen a Representa unha clave no noso dicionario. Agora imos tratar de introducir o BAÑO clave na trie. Imos comezar o nodo raíz e siga os punteiros novo. Pero nesta situación, se loita un morto acabar antes somos capaces de chegar ao extremo da chave. Agora, imos ter que reservar algún novo nós terá que asignar un novo nó a cada resto carta de nosa clave. 

Neste caso, só necesitamos para reservar un novo nodo. Entón nós imos ter que facer o índice H referencia a este novo nodo. Unha vez máis, podemos modificar o no indicar que o camiño de caracteres levando a que representa un clave no noso dicionario. Imos razoar sobre o asintótica complexidade dos nosos procedementos para estes dúas operacións. 

Notamos que en ambos os casos, o número de pasos do noso algoritmo tomou foi proporcional ao número de letras da palabra clave. Iso mesmo. Cando se quere buscar unha palabra nun trie só precisa para percorrer as letras unha a unha ata que quere acadar o fin da palabra ou acadar unha rúa sen saída no trie. 

E cando quere inserir unha chave par de valores nunha trie mediante o procedemento discutir, o peor caso terá que asignar un novo nodo para cada letra. E imos supor que a distribución é unha operación de tempo constante. Así, se asumirmos que a lonxitude da clave é delimitada por unha constante fixa, tanto inserción e mirar para arriba son constantes operacións de tempo para unha trie. 

Se non facemos esta suposición de que a lonxitude da clave é delimitada por un fixo constante, logo inserción e mirar para arriba, no peor dos casos, son lineais no lonxitude da clave. Nótese que o número de elementos gardados no trie non afecta a mirada cara arriba ou o tempo de inserción. É só impactado pola lonxitude da clave. 

En contraste, a adición de entradas para, por exemplo, unha táboa hash tende a facer futuro mirar para arriba máis lento. Aínda que isto poida parecer atractivo a primeira vista, temos que ter presente que un complexidade asintótica favorable non significa que, na práctica os datos estrutura é necesariamente irrepreensível. Debemos considerar tamén que para almacenar un palabra nunha trie que necesitamos, no peor caso, un número de nós proporcional ao longo da propia palabra. 

Tries tenden a usar unha morea de espazo. Isto está en contraste cunha táboa hash, en que só precisa dun novo nodo a gardar algunhas par de valores clave. Agora, de novo, en teoría, o espazo grande consumo non parece ser un gran tratar, sobre todo tendo en conta que a moderna ordenadores teñen gigabytes e gigabytes de memoria. Pero resulta que aínda temos preocuparse co uso de memoria e organización en prol da rendemento, xa que os computadores modernos ter mecanismos vixente baixo o portada para acelerar o acceso á memoria. 

Pero estes mecanismos funcionan mellor cando accesos á memoria están feitos en compacto rexións ou zonas. E os nós de un trie pode residir en calquera lugar que heap. Pero estes son os trade-offs que debemos considerar. 

Lembre que, ao elixir un data estrutura para unha determinada tarefa, nós que pensar en que tipo de operacións a estrutura de datos ten soporte e en canto ao rendemento de cada un destes asuntos operacións para nós. Estas operacións poden ata van máis alá de simples Mire cara arriba e inserción básico. Supoña que quería implantar unha especie de función de auto-completar, moi como buscador Google fai. É dicir, voltar todas as claves e valores que potencialmente ter un determinado prefixo. 

Unha trie é exclusivamente útil para esta operación. É sinxelo para percorrer o trie para cada personaxe de prefixo. Así como un ollar para a operación, poderiamos seguir punteiros carácter por carácter. A continuación, cando chegar ao final do prefixo, poderiamos percorrer a parte restante da estrutura de datos sempre que calquera das teclas aló Neste punto temos o prefixo. 

É tamén fácil de obter este anuncio en orde alfabética desde o elementos da matriz nenos ordenar por orde alfabética. Polo tanto, esperamos que vai considerar doazón intenta un intento. Eu son Kevin Schmid, e este é CS50. 

Ah, iso é o comezo do descenso. Sinto moito. Sentímolo. Sentímolo. Sentímolo. 

Folga de catro. Eu estou fóra. Sentímolo. Sentímolo. Sentímolo. Desculpem-me por facer a persoa que ten para editar este tolear. 

Sentímolo. Sentímolo. Sentímolo. Sentímolo. 

COLUMNA 1: Ben feito. Iso foi moi ben feito.