>> KEVIN SCHMID: Às vezes, quando a construção de um programa, você pode querer utilizar um
estrutura de dados conhecida como um dicionário.
Um dicionário chaves mapas, que são geralmente cordas, com os valores, ints,
caracteres, um ponteiro para algum objeto, o que quisermos.
É como dicionários comuns que mapa palavras através de definições.
>> Dicionários nos fornecer o capacidade de armazenar informações
associado a algo e procurá-lo mais tarde.
Então, como é que vamos realmente implementar um dicionário, digamos, em código C que pudermos
usar em um de nossos programas?
Bem, há uma série de maneiras que poderíamos implementar um dicionário.
>> Por um lado, nós poderíamos usar uma matriz que dinamicamente re-size ou nós poderíamos usar um
lista ligada, tabela hash ou uma árvore binária.
Mas o que quer que nós escolhemos, devemos estar consciente da eficiência e da
desempenho da implementação.
Devemos pensar sobre o algoritmo usado para inserir e procurar os itens em
a estrutura de dados.
>> Por enquanto, vamos supor que nós quer usar strings como chaves.
Vamos falar sobre uma possibilidade, uma estrutura de dados chamada de trie.
Então aqui está uma representação visual de um trie.
>> Como a imagem sugere, um trie é uma estrutura de dados em árvore com
nós ligados.
Vemos que há claramente uma raiz nó com alguns links que se estende até
outros nós.
Mas o que é que cada nó consiste?
Se assumirmos que estamos armazenar chaves com apenas caracteres alfabéticos, e
que não se preocupam com a capitalização, aqui está uma definição de um nó que
será suficiente.
>> Um objeto cujo tipo é struct nó tem duas peças
chamada de dados e crianças.
Nós deixamos a parte de dados como um comentário para ser substituído por um componente
declaração quando nó struct é incorporados em um programa C.
A parte de dados de um nó pode ser um Valor booleano para indicar se
não representa o nó a conclusão de uma chave de dicionário ou pode ser uma
string representando a definição de uma palavra no dicionário.
>> Vamos usar um rosto sorridente para indicar quando os dados estão presentes em um nó.
Há 26 elementos em nosso variedade crianças, um índice
por caractere alfabético.
Vamos ver o significado deste breve.
>> Vamos olhar mais de perto do nó raiz no nosso diagrama, que não tem dados
associada com ele, tal como indicado pela ausência do rosto sorridente no
porção de dados.
As setas que se estendem a partir das partes de os filhos de matriz representam não-nó
ponteiros para outros nós.
Por exemplo, a seta que se estende a partir de o segundo elemento de crianças
representa a letra B em uma chave de dicionário.
E no diagrama maior que rotulá-la com um B.
>> Note que, no diagrama de maior, quando desenhar um ponteiro para outro nó, ele
Não importa onde a ponta da seta cumpre que outro nó.
Nosso dicionário amostra contém trie duas palavras, que e zoom.
Vamos examinar um exemplo de olhando para cima de dados para uma chave.
>> Suponha que queria procurar o valor correspondente para o banho de chave.
Vamos começar o nosso olhar para cima no nó de raiz.
Então nós vamos ter a primeira letra do nosso chave, B, e encontrar o correspondente
detectar, em nossa disposição filhos.
Observe que há exatamente 26 pontos na matriz, um para cada letra
o alfabeto.
E nós vamos ter os pontos representam o letras do alfabeto em ordem.
>> Nós vamos olhar para o segundo índice, em seguida, índice de um, para B. Em geral, se
tem algum character C nós poderia determinar o ponto correspondente
na matriz crianças usando um cálculo assim.
Poderíamos ter usado um crianças maiores array se queríamos oferecer olhar-se de
teclas com uma ampla gama de caracteres, , tais como o todo
Conjunto de caracteres ASCII.
>> Neste caso, o ponteiro na nossa gama crianças em
índice não é nulo.
Então, vamos continuar procurando o banho de chave.
Se alguma vez encontrou um ponteiro nulo no local apropriado nas crianças
array enquanto atravessamos os nós, então nós vamos ter que dizer que nós
não poderia encontrar qualquer coisa para essa chave.
>> Agora, vamos dar a segunda letra nossa chave, A, e continuar seguindo
ponteiros, desta forma até que nós chegar ao fim da nossa chave.
Se chegar ao final da chave sem bater nos becos sem saída, os ponteiros nulos,
como é o caso aqui, então nós só tem que verificar mais uma coisa.
É esta chave realmente no dicionário?
>> Se assim for, devemos encontrar um valor, bem a ícone do smiley face em nosso diagrama onde
a palavra termina.
Se há algo mais armazenado com os dados, então podemos devolvê-lo.
Por exemplo, o jardim zoológico de chave não está no dicionário, mesmo que pudéssemos ter
atingido o fim desta chave sem nunca bater um ponteiro nulo, enquanto nós
percorrer a trie.
>> Se tentei olhar para o banho de chave, o segundo para índice da matriz do último nó,
correspondente à letra H, que realizaram um ponteiro nulo.
Então banho não está no dicionário.
E assim um trie é único em que as chaves nunca são explicitamente armazenada em
a estrutura de dados.
Então, como vamos inserir algo numa trie?
>> Vamos inserir a chave zoológico em nossa trie.
Lembre-se que um rosto sorridente em um nó poderia corresponder em código para um simples
Valor booleano para indicar que zoo está no dicionário ou poderia
correspondem a mais informações que nós deseja associar com o zoológico chave,
como a definição do palavra ou outra coisa.
De certa forma, o processo para inserir algo em um trie é semelhante ao
procurando algo em uma trie.
>> Vamos começar com o nó raiz de novo, seguintes ponteiros correspondentes a
as letras da nossa chave.
Felizmente, fomos capazes de seguir ponteiros todo o caminho até chegarmos
a extremidade da chave.
Desde zoológico é um prefixo da palavra zoom, que é um membro da
dicionário, não precisa alocar quaisquer novos nós.
>> Nós podemos modificar o nó para indicar que o caminho de caracteres que conduzem a
ela representa uma chave no nosso dicionário.
Agora, vamos tentar inserir o BANHO chave na trie.
Vamos começar no nó raiz e siga os ponteiros novamente.
Mas nesta situação, nós batemos um morto acabar antes somos capazes de chegar ao
extremidade da chave.
Agora, vamos ter de alocar algum novo nós terá de atribuir uma nova
nó para cada restante carta de nossa chave.
>> Neste caso, só precisamos para alocar um novo nó.
Então nós vamos ter que fazer o índice H referência a este novo nó.
Mais uma vez, podemos modificar o nó indicar que o caminho de caracteres
levando a que ele representa um chave no nosso dicionário.
Vamos raciocinar sobre o assintótica complexidade dos nossos procedimentos para estes
duas operações.
>> Notamos que em ambos os casos, o número de passos de nosso algoritmo tomou foi
proporcional ao número de letras da palavra-chave.
Isso mesmo.
Quando você quiser procurar uma palavra num trie você só precisa para percorrer
as letras uma a uma até que você quer alcançar o fim da palavra ou
atingido um beco sem saída no trie.
>> E quando você deseja inserir uma chave par de valores em uma trie usando o
procedimento discutimos, o pior caso terá que alocar um novo nó
para cada letra.
E vamos supor que a alocação é uma operação de tempo constante.
Assim, se assumirmos que o comprimento da chave é delimitada por uma constante fixa, tanto
inserção e olhar para cima são constantes operações de tempo para uma trie.
>> Se não fizermos esta suposição de que o comprimento da chave é delimitada por um fixo
constante, em seguida, inserção e olhar para cima, no pior dos casos, são lineares no
comprimento da chave.
Note-se que o número de itens armazenados no trie não afeta o olhar para cima
ou o tempo de inserção.
É só impactado pela comprimento da chave.
>> Em contraste, a adição de entradas para, por exemplo, uma tabela hash tende a fazer
futuro olhar para cima mais lento.
Embora isso possa parecer atraente à primeira vista, devemos ter em mente que um
complexidade assintótica favorável não significa que, na prática os dados
estrutura é necessariamente irrepreensível.
Devemos considerar também que para armazenar um palavra em uma trie que precisamos, no pior
caso, um número de nós proporcional para o comprimento da própria palavra.
>> Tries tendem a usar um monte de espaço.
Isso está em contraste com uma tabela hash, em que só precisa de um novo nó a
armazenar algumas par de valores chave.
Agora, de novo, em teoria, o espaço grande consumo não parece ser um grande
lidar, especialmente tendo em conta que a moderna computadores têm gigabytes e
gigabytes de memória.
Mas acontece que ainda temos se preocupar com o uso de memória e
organização em prol da desempenho, uma vez que os computadores modernos
ter mecanismos em vigor sob o capa para acelerar o acesso à memória.
>> Mas esses mecanismos funcionam melhor quando acessos à memória são feitos em compacto
regiões ou zonas.
E os nós de um trie pode residir em qualquer lugar que heap.
Mas estes são os trade-offs que devemos considerar.
>> Lembre-se que, ao escolher um data estrutura para uma determinada tarefa, nós
deve pensar em que tipo de operações a estrutura de dados precisa
suporte e quanto ao desempenho de cada um daqueles
assuntos operações para nós.
Estas operações podem até vão além de simples
Olhe para cima e inserção básico.
Suponha que queria implementar uma espécie de funcionalidade de auto-completar, muito
como motor de busca Google faz.
Ou seja, retornar todas as chaves e valores que potencialmente
ter um determinado prefixo.
>> Uma trie é exclusivamente útil para esta operação.
É simples para percorrer o trie para cada personagem de
o prefixo.
Assim como um olhar para a operação, poderíamos seguir ponteiros
caractere por caractere.
Em seguida, quando chegar ao fim do prefixo, poderíamos percorrer a
parte restante da estrutura de dados desde que qualquer uma das teclas além
Neste ponto temos o prefixo.
>> É também fácil de obter este anúncio em ordem alfabética desde o
elementos da matriz crianças são ordenados por ordem alfabética.
Portanto, esperamos que você vai considerar doação tenta uma tentativa.
Eu sou Kevin Schmid, e este é CS50.
>> Ah, isso é o começo do declínio.
Sinto muito.
Desculpe.
>> Greve de quatro.
Eu estou fora.
Desculpe.
Desculpem-me por fazer a pessoa que tem para editar este enlouquecer.
>> Desculpe.
Desculpe.
>> COLUNA 1: Bem feito.
Isso foi muito bem feito.