DOUG LLOYD: Então, em CS50, nós cobrimos um grande número de diferentes estruturas de dados, certo? Nós vimos arrays, e ligados listas e tabelas de hash, e tenta, pilhas e filas. Também vamos aprender um pouco sobre árvores e montes, mas realmente todos estes acabar sendo variações sobre um tema. Há realmente estes tipo de quatro idéias básicas que tudo o resto pode ferver para baixo. Arrays, listas ligadas, tabelas de hash, e tenta. E como eu disse, há são variações sobre eles, mas isso é muito muito indo para resumir tudo o que vai falar Sobre nesta classe em termos de C. Mas como estes todos medida, certo? Nós conversamos sobre os prós e contras de cada um em vídeos separados sobre eles, mas há um monte de números sendo jogado em torno. Há um monte de geral pensamentos ser jogado ao redor. Vamos tentar e consolidar -lo em apenas um lugar. Vamos pesar os prós contra os contras, e considere qual a estrutura de dados pode ser a dados direita estrutura para sua situação particular, qualquer tipo de dados que você está armazenando. Você não necessariamente precisa sempre usar o super rápida inserção, eliminação, e pesquisa de uma trie se você realmente não se preocupam com inserir e excluir demais. Se você precisa apenas rapidamente aleatória acesso, talvez uma matriz é melhor. Então, vamos destilar isso. Vamos falar sobre cada um dos quatro principais tipos de estruturas de dados que nós já conversamos sobre, e basta ver quando eles pode ser bom, e quando eles podem não ser tão bom. Então vamos começar com matrizes. Então inserção, que é tipo de ruim. 

A inserção na extremidade de uma matriz é OK, se nós estamos construindo uma matriz como vamos nós. Mas se nós precisarmos inserir elementos no meio, acho que volta para inserção tipo, há muito de deslocamento para ajustar um elemento em lá. E por isso, se nós estamos indo para inserir qualquer lugar, mas no final de uma matriz, que provavelmente não é tão grande. 

Da mesma forma, a exclusão, a menos que sejamos exclusão a partir da extremidade de uma matriz, é, provavelmente, também não tão grande se nós não queremos deixar lacunas vazias, que normalmente nós não. Queremos remover um elemento, e em seguida, tipo de torná-lo confortável novamente. E assim a exclusão de elementos uma matriz, também não tão grande. 

Lookup, porém, é grande. Temos de acesso aleatório, pesquisa de tempo constante. Nós apenas dizer sete, e nós vamos a matriz deslocalização sete. Dizemos 20, com a go matriz deslocalização 20. Não temos para percorrer transversalmente. Isso é muito bom. 

Arrays também são relativamente fáceis de classificar. Cada vez que falamos sobre uma triagem algoritmo, tais como seleção de tipo, tipo de inserção, bubble sort, merge tipo, nós sempre utilizado matrizes para fazê-lo, porque as matrizes são bastante fáceis de tipo, em relação às estruturas de dados temos visto até agora. 

Eles também são relativamente pequeno. Não há um monte de espaço extra. Você só anular exatamente tanto como você precisa para armazenar seus dados, e isso é muito bonito isso. Então eles são muito pequenos e eficiente desta maneira. Mas uma outra desvantagem, no entanto, é que eles são de tamanho fixo. Temos de declarar exatamente como grande queremos que a nossa matriz para ser, e nós só temos uma chance. Nós não podemos crescer e reduzi-lo. 

Se precisamos crescer ou encolher-lo, nós precisa declarar uma matriz inteiramente novo, copiar todos os elementos do primeira matriz para a segunda matriz. E se calculou mal que tempo, temos de fazê-lo novamente. Não é tão boa. Então matrizes não nos dão a flexibilidade ter número variável de elementos. 

Com uma lista ligada, inserção é muito fácil. Nós apenas alinhavar para a frente. Eliminação também é muito fácil. Temos que encontrar os elementos. Que envolvem alguma pesquisa. 

Mas uma vez que você tenha encontrado o elemento você está procurando, tudo que você precisa fazer é alterar um ponteiro, possivelmente dois, se você tem uma ligada lista-- um duplamente lista ligada, rather-- e então você pode apenas liberar o nó. Você não tem que mudar tudo ao seu redor. Você acabou de mudar dois ponteiros, de modo que é muito rápido. 

Lookup é ruim, certo? A fim para nós encontrar um elemento em uma lista ligada, isoladamente ou duplamente ligado, temos a linear busca-lo. Temos que começar no início e mova o fim, ou começar no final do movimento para o início. Não temos acesso aleatório mais. Então, se estamos fazendo um muita pesquisa, talvez uma lista ligada não é tão bom para nós. 

Eles também são realmente difícil de resolver, certo? A única maneira que você puder realmente classificar uma lista ligada é para classificá-lo como você construí-lo. Mas se você classificá-lo como você construí-lo, você não é mais fazendo inserções rápidas anymore. Você não está apenas alinhavando as coisas para a frente. Você tem que encontrar o ponto certo para colocá-lo, e, em seguida, a sua inserção torna-se quase tão ruim como a inserção em uma matriz. Então listas ligadas não são tão grande para classificar os dados. 

Eles também são bastante pequeno, tamanho-wise. Duplamente lista ligada ligeiramente maior do que isoladamente listas ligadas, que são ligeiramente maiores de matrizes, mas não é uma enorme quantidade de espaço desperdiçado. Portanto, se o espaço é um prêmio, mas não um prêmio muito intenso, este pode ser o caminho certo a seguir. 

As tabelas de hash. Inserção em uma tabela hash é bastante simples. É um processo de duas etapas. Primeiro, precisamos executar nossas informações através uma função hash para obter um código de hash, e, depois, insira o elemento para o tabela hash naquele local do código hash. 

Eliminação, semelhante a lista ligada, é fácil uma vez que você encontrar o elemento. Você tem que encontrá-lo primeiro, mas, em seguida, quando você excluí-lo, você só precisa trocar um par de ponteiros, se você estiver usando o encadeamento separado. Se você estiver usando sondagem, ou se você não estiver usando encadeamento em tudo em sua tabela de hash, eliminação é realmente muito fácil. Tudo que você precisa fazer é botar o dados, e em seguida, ir para esse local. E supondo que você não fazer tem nenhum colisões, você vai ser capaz de apagar muito rapidamente. 

Agora, a pesquisa é onde as coisas ficar um pouco mais complicado. Está na melhor média de listas ligadas. Se você estiver usando o encadeamento, você ainda tem uma lista ligada, o que significa que você ainda tem a Pesquisa detrimento uma lista ligada. Mas porque você está tomando seu ligada lista e dividi-lo mais de 100 ou 1000 ou n elementos em sua tabela de hash, você é listas ligadas são todos um enésimo o tamanho. Eles são todos substancialmente menor. Você listas n ligada ao invés de uma lista ligada de tamanho n. 

E assim, este mundo real constante fator, que geralmente não falar sobre a complexidade em tempo, faz realmente fazer a diferença aqui. Assim pesquisa ainda é linear procurar se você estiver usando o encadeamento, mas o comprimento da lista Você está vendo a é muito, muito curto, por comparação. Novamente, se a classificação é a sua objetivo aqui, hash de tabela de provavelmente não é o caminho certo a seguir. Basta usar uma matriz se classificar é realmente importante para você. 

E eles podem executar a gama de tamanho. É difícil dizer se uma tabela hash é pequeno ou grande, porque ele realmente depende de como grande sua tabela hash é. Se você está indo só para estar armazenando cinco elementos em sua tabela hash, e você tem uma tabela hash com 10.000 elementos nele, provavelmente você está desperdiçando uma grande quantidade de espaço. Contraste sendo você também pode tem tabelas de hash muito compactas, mas o menor sua tabela hash fica, quanto mais cada uma dessas listas ligadas recebe. E assim não há realmente nenhuma maneira de definir exactamente o tamanho de uma tabela hash, mas é provavelmente seguro dizer que é geralmente vai ser maior do que um ligado lista armazenar os mesmos dados, mas menor do que um trie. 

E tentativas são a quarta destas estruturas que temos vindo a falar. A inserção numa trie é complexo. Há um monte de dinâmica alocação de memória, especialmente no início, como você está começando a construir. Mas é tempo constante. É apenas o elemento humano aqui que faz com que seja complicado. Ter de encontrar ponteiro nulo, malloc espaço, ir lá, o espaço possivelmente malloc a partir daí de novo. O tipo de fator de intimidação de ponteiros em alocação dinâmica de memória é o obstáculo para limpar. Mas uma vez que você limpou-o, inserção na verdade vem bastante simples, e é certamente tempo constante. 

A exclusão é fácil. Tudo que você precisa fazer é navegar para baixo a par de ponteiros e livre o nó, de modo que é muito bom. Lookup também é bastante rápido. É só com base na comprimento de seus dados. Portanto, se todos os seus dados é cinco cadeias de caracteres, por exemplo, você está armazenando cinco cadeias de caracteres em seu trie, ele só tem cinco passos para encontrar o que você está procurando. Cinco é apenas um fator constante, por isso, novamente, inserção, exclusão e pesquisa aqui estão todos os tempos constante, de forma eficaz. 

Outra coisa é que seu trie é na verdade, meio que já classificadas, certo? Em virtude de como estamos elementos Inserir, indo letra por letra do chave, ou dígito por dígito da chave, normalmente, o trie acaba sendo tipo de classificadas como você construí-lo. Realmente não faz sentido pensar em classificação da mesma forma que pensamos sobre com matrizes ou listas ligadas, ou tabelas de hash. Mas, em certo sentido, o seu trie é classificada como você vai. 

A desvantagem, claro, é que um trie rapidamente torna-se enorme. De todos os pontos de junção, você pode have-- se sua chave é composta de dígitos, você tem 10 outros lugares que você pode ir, o que significa que cada nó contém informações sobre os dados que você deseja armazenar no nó que, além de 10 ponteiros. Que, em CS50 IDE, é de 80 bytes. Então, é, pelo menos, 80 bytes para cada nó que você criar, e isso não é mesmo contando dados. E se os seus nodos são letras em vez de dígitos, agora você tem 26 ponteiros de todos os locais. E 26 vezes 8 é provavelmente 200 bytes, ou algo parecido. E você tem o capital e você pode lowercase-- ver onde eu estou indo com isso, certo? Seus nós pode ficar muito grande, e assim a trie -se, em geral, pode ficar realmente grande, demasiado. Portanto, se o espaço é alta prêmio em seu sistema, um trie pode não ser o caminho certo para ir, apesar de seus outros benefícios entre no jogo. Eu sou Doug Lloyd. Este é CS50.