[Música tocando]
COLUNA 1: Tudo bem.
Todos bem-vindos de volta à seção.
Espero que todos estão com sucesso recuperado de seu quiz
desde a semana passada.
Eu sei que é um pouco louco, às vezes.
Como eu estava dizendo antes, se você estiver dentro do desvio padrão,
realmente não se preocupe com isso, especialmente para uma secção menos confortável.
Isso é sobre onde você deveria estar.
>> Se você fez grande, então incrível.
Kudos para você.
E se você sentir que você precisa um pouco mais de ajuda, por favor
sinta-se livre para chegar para fora a qualquer um dos FT.
Estamos todos aqui para ajudar.
>> É por isso que nós ensinamos.
É por isso que eu estou aqui toda segunda-feira para você rapazes e no escritório horas às quintas-feiras.
Então, por favor, sinta-se livre para me deixar saber se você está preocupado com nada
ou se há alguma coisa sobre o quiz que você realmente gostaria de abordar.
>> Assim, a agenda para hoje é tudo sobre estruturas de dados.
Algumas delas são apenas vai ser apenas para que você obtenha familiarizados com estes.
Você não pode sempre implementar los nesta classe.
Alguns deles você vai, como para o seu pset ortográfico.
>> Você vai ter a sua escolha entre tabelas hash e tentativas.
Então, nós vamos, sem dúvida vamos sobre aqueles.
Vai ser definitivamente mais do tipo uma secção de alto nível hoje, no entanto,
porque há um monte deles, e se fomos para os detalhes de implementação
em todas elas, não teríamos mesmo passar por listas ligadas
e talvez um pouco de tabelas de hash.
>> Então, tenha paciência comigo.
Nós não estamos indo fazer tanto de codificação desta vez.
Se você tiver quaisquer perguntas sobre o assunto ou você quer ver implementado
ou experimentar por si próprio, Eu recomendo definitivamente
indo study.cs50.net, que tem exemplos de todos estes.
Ele vai ter meus PowerPoints com as notas que nós
tendem a usar, bem como alguma programação exercícios, especialmente para as coisas
como listas ligadas e binário árvores pilhas e sugestões.
Tão pouco mais alto nível, que Pode ser bom para vocês.
>> Então, com isso, vamos começar.
E também, quizzes sim--.
Acho que a maioria de vocês que estão em minha seção tem seus questionários,
mas ninguém entra ou algum motivo você não, eles estão aqui na frente.
>> Assim listas ligadas.
Eu sei que este tipo de vai para trás antes de seu quiz.
Essa foi a semana antes que aprendemos sobre isso.
Mas, neste caso, nós vamos ir um pouco mais em profundidade.
>> Então, por que poderíamos escolher um lista ligada através de uma matriz?
O que os distingue?
Sim?
>> AUDIÊNCIA: Você pode expandir um ligado listar contra tamanho fixo de um array.
COLUNA 1: Certo.
Uma matriz tem tamanho fixo enquanto que uma lista ligada tem um tamanho variável.
Então, se nós não sabemos como tanto que queremos armazenar,
uma lista ligada nos dá uma grande maneira de fazer isso porque nós podemos apenas
adicionar em outro nó e adicionar outro nó e adicionar em outro nó.
Mas o que poderia ser um trade-off?
Alguém se lembra do trade-off entre matrizes e listas ligadas?
Mmhmm?
>> AUDIÊNCIA: Você tem que percorrer todo o caminho
através da lista ligada encontrar um elemento em uma lista.
Em uma matriz, você pode apenas encontrar um elemento.
>> COLUNA 1: Certo.
Assim, com arrays--
>> AUDIÊNCIA: [inaudível].
>> COLUNA 1: Com matrizes, temos o que é chamado de acesso aleatório.
Significa que, se queremos o que é já o quinto ponto de uma lista
ou o quinto ponto da nossa array, podemos apenas agarrá-lo.
Se é uma lista ligada, temos para percorrer, certo?
Então acessar um elemento em uma matriz é constante de tempo,
enquanto que com uma lista ligada que seria provavelmente será o tempo linear, porque talvez
nosso elemento é todo o caminho no final.
Temos que procurar através de tudo.
Assim, com todos estes dados estruturas que vamos
gastar um pouco mais de tempo em diante, quais são os pontos positivos e negativos.
Quando poderia queremos usar um sobre o outro?
E esse é o tipo de grande coisa para levar.
>> Portanto, temos aqui a definição de um nó.
É como um elemento nossa lista ligada, certo?
Então, estamos todos familiarizados com as nossas estruturas typedef,
que fomos na avaliação da última vez.
Era basicamente apenas criar outro tipo de dados que poderíamos usar.
>> E, neste caso, é um nó que irá realizar algum inteiro em.
E então o que é a segunda parte aqui?
Qualquer um?
>> AUDIÊNCIA: [inaudível].
>> COLUNA 1: Sim.
É um ponteiro para o próximo nó.
Portanto, este deve realmente estar aqui em cima.
Este é um tipo de ponteiro nó para a próxima coisa.
E isso é o que eles engloba o nosso nó.
Legal.
>> Tudo bem, então com a pesquisa, como estávamos apenas dizendo antes da mão, se você estiver
vai pesquisar, você tem que realmente fazer uma iteração
através de sua lista ligada.
Então, se nós estamos olhando para o número 9, que iria começar na nossa cabeça
e que nos aponta para o início da nossa lista ligada, certo?
E nós dizemos: OK, faz isso nó conter o número 9?
Não?
>> Tudo bem, vá para a próxima.
Siga-o.
Será que ela contém o número 9?
Não.
Siga o próximo.
>> Então nós temos que realmente iteração através da nossa lista ligada.
Não podemos simplesmente ir diretamente para onde 9 é.
E se vocês realmente querem ver alguns pseudo-código lá em cima.
Temos alguma função de pesquisa aqui que leva em-- o que é preciso em?
O que você acha?
Uma tão fácil.
O que é isso?
AUDIÊNCIA: [inaudível].
COLUNA 1: O número que estamos procurando.
Certo?
E o que seria isso corresponde a?
É um ponteiro para?
>> AUDIÊNCIA: um nó.
>> COLUNA 1: Um nó à lista que nós estamos olhando, certo?
Portanto, temos alguns nós são ponteiro aqui.
Este é um ponto que vai realmente iterar nossa lista.
Nós configurá-lo igual a listar porque isso é apenas
fixando-a igual ao início da nossa lista ligada.
>> E enquanto não é NULL, enquanto ainda temos coisas em nossa lista,
verificar para ver se esse nó tem o número que estamos procurando.
Retorna verdadeiro.
Caso contrário, atualizá-lo, certo?
>> Se for NULL, saímos nossa while e retornar falso
porque isso significa que não tê-lo encontrado.
Será que todo mundo começa como isso funciona?
Está bem.
>> Assim, com a inserção, você ter três formas diferentes.
Você pode preceder, você pode acrescentar e você pode inserir em sortidas.
Neste caso, estamos vai fazer um preceder.
Alguém sabe como aqueles três casos pode ser diferente?
>> Então preceder significa que você colocar ele na frente da sua lista.
Então, isso significa que não importa que o nó é, não importa
qual é o valor, você vai para colocá-lo aqui na frente, OK?
Vai ser o primeiro elemento em sua lista.
>> Se você anexá-lo, ele vai para ir para a parte de trás de sua lista.
E inserir em variados significa que você está vai colocar realmente no lugar
onde ele mantém sua lista ligada ordenada.
Mais uma vez, como você usa os e quando você usa
eles irão variar de acordo com o seu caso.
Se ele não precisa ser classificado, anteposta tende
ser o que a maioria das pessoas usar, porque você não faz
tem que passar por toda a lista para encontrar o fim de adicioná-lo, certo?
Você pode simplesmente colocá-lo em direito.
>> Então, vamos passar por um inserção 1 agora.
Então, uma coisa que eu vou recomendo neste pset
é chamar as coisas, como sempre.
É muito importante que você atualize os ponteiros na ordem correta
porque se você atualizá-los um pouco fora de ordem,
você vai acabar perda de partes da sua lista.
>> Assim, por exemplo, neste caso, estamos contando a cabeça para apenas um ponto a 1.
Se nós apenas fazer isso sem salvar este 1,
nós não temos nenhuma idéia do que 1 deve apontar para agora
porque nós perdemos o a cabeça apontada.
Então, uma coisa para lembrar quando você está fazendo um preceder
é salvar o que o cabeça pontos para o primeiro,
Depois, atribua-o e atualize o que o seu novo nó deve apontar para.
Neste caso, esta é uma maneira de fazê-lo.
>> Então, se tivéssemos feito isso dessa maneira onde nós apenas transferido cabeça,
perdemos basicamente nossa lista inteira, certo?
Uma maneira de fazer isso é ter um ponto de seguinte, e depois ter ponto cabeça para 1.
Ou você pode fazer como o tipo de armazenamento temporário, de que falei.
>> Mas a reatribuição seu ponteiros na ordem correta
vai ser muito, muito importante para este pset.
Caso contrário, você vai ter um hash mesa ou uma tentativa que só vai ser
apenas uma parte das palavras que você quer e então you're-- mmhmm?
AUDIÊNCIA: Qual foi o temporário coisa de armazenamento que você estava falando?
COLUNA 1: O armazenamento temporário.
Então, basicamente, outra maneira que você poderia fazer isso
é armazenar o chefe de alguma coisa, como armazená-lo na variável temporária.
Atribuí-la a um e em seguida, atualizar 1 ao ponto
para qualquer cabeça usado para apontar para.
Desta forma é obviamente mais elegante, porque você
Não é necessário um valor temporário, mas apenas oferecer uma outra maneira de fazê-lo.
E nós realmente temos um código para esta.
Assim, para lista ligada, nós realmente tem algum código.
Então insira aqui, este é antecedendo.
Portanto, este entra nele na cabeça.
>> Então a primeira coisa, você precisa criar seu novo nó, é claro,
e verificar se há NULL.
Sempre bom.
E então você precisa para atribuir os valores.
Sempre que você cria um novo nó, você Não sei o que ele está apontando para o próximo,
assim que você quer inicializar para NULL.
Se ele acabar apontando para algo outra coisa, ele é transferido e está tudo bem.
Se é a primeira coisa na lista, ele precisa
para apontar para NULL porque isso é o fim da lista.
>> Então para inseri-lo, vemos aqui nós está atribuindo o próximo valor do nosso nó
para ser o cabeça, que é o que nós tivemos aqui.
Isso é o que nós fizemos.
E então nós estamos atribuindo cabeça para ponto ao nosso novo nó, porque lembre-se,
é algum novo ponteiro para um nó, e isso é exatamente o que é cabeça.
É exatamente por isso que tem esse assessor seta.
Legal?
Mmhmm?
>> AUDIÊNCIA: Será que temos que inicializar novo ao lado de NULL em primeiro lugar,
ou podemos simplesmente inicializá-lo de cabeça?
>> COLUNA 1: New próxima precisa de ser NULL para iniciar
porque você não sabe onde vai ser.
Além disso, esta é uma espécie de Assim como um paradigma.
Você defini-lo igual a NULL apenas para fazer Certifique-se de que todas as bases estão cobertas
antes de fazer qualquer mudança de modo que você está sempre garantido que ele vai
estar apontando para um valor específico contra como um valor de lixo.
Porque, sim, nós atribuímos novo ao lado automaticamente,
mas é mais como um boas práticas para inicializar
dessa forma e depois transferir.
>> OK, então duplamente ligada listas agora.
O que nós pensamos?
O que há de diferente com duplamente ligada listas?
>> Assim, em nossas listas ligadas, podemos apenas mover em uma direção, certo?
Nós só temos a seguir.
Nós só podemos ir para a frente.
>> Com uma lista duplamente ligada, também podemos andar para trás.
Portanto, temos não só a número que deseja armazenar,
temos onde ele aponta para o próximo e onde veio.
Então, isso permite alguns melhores travessia.
>> Então nós duplamente vinculadas, muito semelhante, certo?
A única diferença é que agora têm um lado e uma anterior.
É a única diferença.
>> Então, se fôssemos para preceder ou append-- nós não têm qualquer código para esta aqui--se
mas se você fosse para tentar inseri-lo, o importante
é que você precisa fazer Certifique-se que você está atribuindo
tanto o anterior e seu próximo ponteiro corretamente.
Portanto, neste caso, você faria não só inicializar seguinte,
você inicializa anterior.
Se estamos no topo da lista, nós não só fazer a cabeça igual novo,
mas deve ser a nossa nova anterior apontar para a cabeça, certo?
>> Essa é a única diferença.
E se você quiser mais prática com estes com listas ligadas, com a inserção,
com a exclusão, com a inserção em uma lista variada,
confira study.cs50.net.
Há um monte de grandes exercícios.
Eu recomendo-los.
Eu gostaria que tivéssemos tempo para passar por eles mas há um monte de estruturas de dados
para passar.
>> OK, então tabelas de hash.
Este é provavelmente o mais pouco útil para o seu pset
aqui, porque você vai ser implementação de um destes, ou uma tentativa.
Eu realmente gosto de tabelas de hash.
Eles são muito legal.
>> Então, basicamente, o que acontece é uma tabela hash
é quando nós realmente precisamos speedy inserção, exclusão e pesquisa.
Essas são as coisas que estamos priorizar em uma tabela hash.
Eles podem ficar muito grande, mas, como veremos, com tentativas,
há coisas que são muito maiores.
>> Mas, basicamente, todo um hash tabela é uma função hash
que lhe diz que balde para colocar cada de seus dados, cada um de seus elementos em.
Uma maneira simples de pensar em uma tabela hash é que não é apenas baldes de coisas,
certo?
Então, quando você está classificando as coisas por como a primeira letra do seu nome,
que é como uma espécie de tabela de hash.
>> Então, se eu fosse vocês grupo é em grupos de quem quer que seu nome começa
com um aqui, ou quem quer que o aniversário é em janeiro, fevereiro, março,
seja qual for, que é eficaz criação de uma tabela hash.
É só criar baldes que você classificar os elementos em
para que você possa encontrá-los mais fácil.
Assim, desta forma, quando eu preciso para encontrar um de vocês,
Eu não tenho que procurar através de cada um de seus nomes.
Eu posso ser como, oh, eu sei que Aniversário de Danielle é em--
AUDIÊNCIA: --April.
COLUNA 1: abril.
Então eu olho na minha abril balde, e com alguma sorte,
ela vai ser a única pessoa lá dentro, e meu tempo era constante nesse sentido,
enquanto que, se eu tenho que olhar através de um grupo inteiro de pessoas,
que vai levar muito mais tempo.
Então, tabelas hash são realmente apenas baldes.
Uma maneira fácil de pensar deles.
>> Então, uma coisa muito importante sobre uma tabela hash é uma função hash.
Então, as coisas que eu acabei de falar sobre, como sua primeira letra de seu nome
ou o seu mês de aniversário, estas são idéias que
realmente se correlacionam com uma função hash.
É apenas uma maneira de decidir qual balde você está elemento entra, OK?
Portanto, para este pset, você pode olhar para cima praticamente qualquer função hash que deseja.
>> Não tem que ser o seu próprio.
Há alguns realmente fresco para fora há que fazer todos os tipos de matemática maluca.
E se você quiser fazer o seu corretor ortográfico super rápido,
Eu definitivamente olhar para um desses.
>> Mas há também o são mais simples, como a computação
a soma das palavras, como cada letra tem um número.
Calcular a soma.
Que determina o balde.
Eles também têm as mais fáceis que são apenas como toda a de um aqui,
todo o B está aqui.
Qualquer um desses.
>> Basicamente, ele apenas diz-lhe que índice da matriz seu elemento deve ir para.
Basta decidir o bucket-- é tudo uma função hash é.
Portanto, temos aqui um exemplo que é apenas a primeira letra da string
que eu estava falando.
>> Então você tem algum hash que é apenas o primeira letra da frase, menos um,
que lhe dará alguns número entre 0 e 25.
E o que você quer fazer é certifique-se de que isso representa
o tamanho de seu hash de mesa-- quantos baldes existem.
Com muitos destes funções de hash, eles são
vai ser o retorno de valores que pode estar muito acima do número de depósitos
que você realmente tem em sua tabela de hash,
então você precisa fazer Certifique-se e mod por aqueles.
Caso contrário, ele vai dizer, oh, ele deve estar em balde 5000
mas você só tem 30 baldes em sua tabela hash.
E, claro, todos nós sabemos que é vai resultar em alguns erros de loucos.
Então certifique-se de mod pelo tamanho da tabela hash.
Legal.
Assim colisões.
Estão todos bem até agora?
Mmhmm?
>> AUDIÊNCIA: Por que ele retornar um valor tão grande?
>> COLUNA 1: Dependendo do algoritmo que a sua função de hash usa.
Alguns deles irão fazer multiplicação louco.
E é tudo sobre a obtenção de uma distribuição uniforme,
para que eles realmente fazer alguma coisas malucas às vezes.
Isso é tudo.
Algo mais?
Está bem.
>> Assim colisões.
Basicamente, como eu disse anteriormente, na melhor das hipóteses,
qualquer balde eu olhar é vai ter uma coisa,
então eu não tenho que olhar para tudo, certo?
Eu nem sei que ele está lá ou é Não, e isso é o que realmente queremos.
Mas se temos dezenas de milhares de Os pontos de dados e inferior a esse número
de baldes, nós vamos ter colisões onde eventualmente algo
vai ter que acabar em um balde que já tem um elemento.
>> Então a questão é, o que que vamos fazer nesse caso?
O que vamos fazer?
Já temos alguma coisa lá?
Será que simplesmente jogá-lo fora?
>> Não.
Temos que manter os dois.
Assim, a maneira que nós normalmente fazer isso é o quê?
Qual é a estrutura de dados que acabamos de falar?
AUDIÊNCIA: lista encadeada.
COLUNA 1: Uma lista ligada.
Então, agora, em vez de cada um destes baldes ter apenas um elemento,
que vai conter uma lista ligada de os elementos que foram hash dentro dele.
OK, que todos tipo de tirou essa idéia?
Porque nós não poderíamos ter um array porque não sabemos quantas coisas
vão estar lá.
Uma lista ligada nos permite ter apenas o número exato que
são misturados em que balde, né?
>> Então linear de sondagem é basicamente este idea--
é uma maneira de lidar com a colisão.
O que você pode fazer é se, neste caso, baga foi hash em um
e já temos algo lá, você só
continue indo para baixo até você encontrar um slot vazio.
Essa é uma maneira de lidar com isso.
A outra maneira de lidar é com o que acabamos de
called-- o ligado lista é chamado encadeamento.
>> Então, essa idéia funciona se sua tabela hash que você pensa
é muito maior do que seu conjunto de dados ou se você
quero tentar minimizar o encadeamento até que seja absolutamente necessário.
Então, uma coisa é linear sondagem, obviamente, significa
que a sua função de hash não é tão útil
porque você vai acabar usando sua função de hash, ficando a um ponto,
você linear sondar até algum lugar que está disponível.
Mas agora, naturalmente, nada outra coisa que acaba por lá,
você vai ter que pesquisar ainda mais para baixo.
>> E há muito mais despesa de busca que
vai para a introdução de um elemento em sua tabela hash agora, certo?
E agora quando você vai tentar encontrar baga de novo, você vai botar ele,
e ele vai dizer: oh, olha no balde 1,
e não vai ser no balde 1, então você está
vai ter que atravessar através do restante destes.
Então, às vezes é útil, mas na maior parte dos casos,
vamos dizer que encadeamento é o que você quer fazer.
>> Então nós conversamos sobre isso antes.
Eu tenho um pouco à frente de mim.
Mas o encadeamento é, basicamente, que cada balde em sua tabela hash
é apenas uma lista ligada.
>> Assim, uma outra forma, ou mais técnico forma, pensar em uma tabela hash
é que não é apenas uma matriz de listas ligadas, que
quando você está escrevendo seu dicionário e você está tentando carregá-lo,
pensando nisso como uma matriz de listas ligadas
fará com que seja muito mais fácil para que você possa inicializar.
>> AUDIÊNCIA: Então tabela hash tem um tamanho pré-determinado,
como um [inaudível] de baldes?
>> COLUNA 1: Certo.
Por isso, tem um número definido de baldes que você determine--
que vocês devem sinta-se livre para brincar.
Pode ser muito legal para ver o que acontece
como você mudar o seu número de caçambas.
Mas sim, ele tem um definir o número de baldes.
O que lhe permite encaixar como muitos elementos que você precisa
é este encadeamento separado onde você ligaram listas em cada balde.
Isso significa que sua tabela hash será exatamente o tamanho
que você precisa que ele seja, certo?
Esse é o ponto de listas ligadas.
Legal.
>> Por isso, todos OK lá?
Tudo certo.
Ah.
O que aconteceu?
Realmente agora.
Acho que alguém está me matando.
>> OK, vamos entrar em tentativas, que são um pouco louco.
Eu gosto de tabelas de hash.
Eu acho que eles são muito legal.
Tries são legais também.
>> Então, alguém se lembra o que é uma tentativa?
Você deveria ter ido mais brevemente na palestra?
Você se lembra do tipo de como ele funciona?
AUDIÊNCIA: Eu só estou balançando que se passar por isso.
COLUNA 1: Nós não passar por isso.
OK, nós realmente estamos indo para ir sobre ele agora é o que estamos dizendo.
>> AUDIÊNCIA: Isso é para uma árvore de recuperação.
>> COLUNA 1: Sim.
É uma árvore de recuperação.
Impressionante.
Então, uma coisa a notar aqui é que nós está olhando para caracteres individuais
aqui, certo?
>> Portanto, antes com a nossa função de hash, que estavam olhando para as palavras como um todo,
e agora estamos procurando mais para os personagens, certo?
Portanto, temos Maxwell aqui e Mendel.
Então, basicamente, um try-- uma maneira de pensar sobre isso é que todos os níveis aqui
é uma matriz de letras.
Portanto, este é o nó raiz aqui, certo?
Isso tem todos os personagens do alfabeto para o início de cada palavra.
>> E o que você quer fazer é digamos, OK, nós temos alguma palavra M.
Nós vamos olhar para Maxwell, de modo vamos para M. e M aponta para um inteiro
uma outra matriz onde cada palavra, enquanto houver
é uma palavra que tem um como a segunda carta,
enquanto há uma palavra que tem B como a segunda carta,
ele terá um ponteiro indo a alguma próxima matriz.
>> Provavelmente não há uma palavra que MP alguma coisa,
Assim, com a posição P no presente array, que seria apenas NULL.
Ele diria: OK, não há nenhuma palavra que M seguido por um P, OK?
Então, se nós pensamos sobre isso, cada uma dessas coisas menores
é realmente um destes grandes conjuntos de A a Z.
Então, o que pode ser uma das coisas que é uma espécie de desvantagem de uma tentativa?
>> AUDIÊNCIA: Uma grande quantidade de memória.
>> COLUNA 1: É uma tonelada de memória, certo?
Cada um desses blocos aqui representa 26 espaços, 26 matriz elemento.
Então tenta ficar incrivelmente pesada espaço.
>> Mas eles são muito rápidos.
Então, incrivelmente rápido, mas realmente espaço ineficiente.
Meio que tem que descobrir qual deles você quer.
Estes são muito legal para o seu pset, mas eles ocupam muita memória,
para que o comércio off.
Sim?
>> AUDIÊNCIA: Seria possível para configurar uma tentativa e, em seguida,
uma vez que você tem todo o dados em que você need--
Eu não sei se isso faria sentido.
Eu estava me livrar de todo o Caracteres nulos, mas, em seguida,
você não seria capaz de indexar eles--
>> COLUNA 1: Você ainda precisa deles.
>> AUDIÊNCIA: - da mesma forma a cada vez.
COLUNA 1: Sim.
Você precisa dos caracteres nulos para deixar Você sabe se não há uma palavra lá.
Ben se você tem algo que você quer?
Está bem.
Tudo bem, então vamos para ir um pouco mais
no detalhe técnico atrás a tentar trabalhar com um exemplo.
>> OK, então isso é a mesma coisa.
Considerando que, em uma lista ligada, a nossa principal tipo de-- qual é a palavra que eu quero? -
como a construção de bloco era um nó.
Em uma tentativa, nós também temos um nó, mas é definido de forma diferente.
>> Portanto, temos alguns que bool representa, na verdade, se uma palavra
existe neste local, e em seguida, temos alguma variedade aqui-- ou melhor,
este é um ponteiro para uma matriz de 27 caracteres.
E isto é para, no presente caso, este 27-- Tenho certeza que todos vocês são como, espera,
há 26 letras no alfabeto.
Por que temos 27?
>> Assim, dependendo do forma de implementar esta,
isto é de um pset que permitiu apóstrofos.
É por isso que o extra.
Você também terá em algum casos o terminador nulo
está incluída como um dos caracteres que é permitido ser,
e é assim que eles verificam a ver se é o final da palavra.
Se você estiver interessado, confira Vídeo de Kevin em study.cs50,
bem como a Wikipedia tem alguns bons recursos lá.
>> Mas vamos passar por apenas uma espécie de como você pode trabalhar através de uma tentativa
se você está dado um.
Portanto, temos um super simples aqui que Tem as palavras "bat" e "zoom" neles.
E como podemos ver aqui em cima, este pequeno espaço aqui
representa a nossa bool que diz, sim, esta é uma palavra.
E então isso tem a nossa arrays de caracteres, certo?
>> Então, nós estamos indo para percorrer encontrar "morcego" nessa tentativa.
Então comece no topo, certo?
E nós sabemos que b corresponde a o segundo índice, o segundo elemento
Nesta matriz, porque a e b.
Assim, cerca de um segundo.
>> E diz, OK, legal, segue que em a próxima matriz, porque se nos lembrarmos,
não é que cada um destes na verdade, contém o elemento.
Cada uma destas matrizes contém um ponteiro, certo?
É uma distinção importante a fazer.
>> Eu sei que isso vai ser-- tentativas são realmente difícil de obter no primeiro tempo,
por isso mesmo que este é o segunda ou terceira vez
e ainda é o tipo de parecer difícil,
Eu prometo que se você vai assistir o amanhã curto novamente,
ele provavelmente vai fazer muito mais sentido.
Demora muito para digerir.
Eu às vezes ainda sou como, espere, o que é uma tentativa?
Como eu uso isso?
>> Então temos b neste caso, que é o nosso segundo índice.
Se tivéssemos, por exemplo, c ou d ou qualquer outra carta,
precisamos mapear que volta ao índice da nossa matriz que que corresponde a.
Então, nós tomaríamos como rchar e nós apenas subtrair fora de um para mapeá-lo em 0-25.
Todo mundo bom como nós mapear os nossos personagens?
Está bem.
>> Então vamos para o segundo e nós ver que, sim, ele não é NULL.
Podemos passar para o próximo matriz.
Então vamos para o próximo conjunto aqui.
>> E nós dizemos: OK, agora nós precisa ver se um está aqui.
É um nulo ou não é realmente seguir em frente?
Assim, na verdade, um move encaminhar nesta matriz.
E nós dizemos: OK, t é a nossa última carta.
Então vamos para o t no índice.
E, então, avançar porque não há outro.
E isso se diz, basicamente, que, sim, ele diz que não é uma palavra aqui-
que, se você seguir este caminho, você chegou
em uma palavra, que sabemos que é "bat".
Sim?
>> AUDIÊNCIA: É normal ter que como índice 0 e, em seguida, ter uma espécie em 1
ou para ter no final?
>> COLUNA 1: Não.
Portanto, se olharmos para o nosso declaração aqui, é um bool,
por isso é seu próprio elemento em seu nó.
Portanto, não é parte da matriz.
Legal.
Então, quando nós terminamos a nossa palavra e estamos nesta matriz, o que nós queremos fazer
é fazer uma verificação para isso é uma palavra.
E, neste caso, ele voltaria sim.
>> Então, nessa nota, sabemos que "zoo" - sabemos como os seres humanos que "zoo" é uma palavra,
certo?
Mas se tentar aqui seria dizer, não, não é.
E diria que porque nós não designou-o como uma palavra aqui.
Mesmo que podem atravessar através do presente matriz,
esta tentativa diria que não, zoológico não está em seu dicionário
porque não temos designado como tal.
>> Assim, uma maneira de fazer isso-- Ah, desculpe, este.
Portanto, neste caso, "zoo" não é uma palavra, mas é em nossa tentativa.
Mas neste, dizer que quer que ele introduzir a palavra "banho", o que acontece
é seguirmos through-- b, um t.
Estamos nessa matriz, e vamos para procurar h.
>> Neste caso, quando olhar para o ponteiro no h,
ele está apontando para NULL, OK?
Então, a menos que seja explicitamente apontando para uma outra matriz,
você assumir que todos os ponteiros nesta matriz estão apontando para null.
Portanto, neste caso, h está apontando como nulo por isso não podemos fazer nada,
por isso seria também retornar falsa, "banho" não é aqui.
Portanto, agora estamos realmente vai passar por
como é que nós realmente dizer que "zoo" é em nossa tentativa.
Como é que vamos inserir "zoo" em nossa tentativa?
Assim, da mesma maneira que começou com o nossa lista ligada, começamos na raiz.
Quando estiver em dúvida, comece a raiz destas coisas.
>> E vamos dizer, OK, z.
z existe neste, e ele faz.
Então você está se movendo para sua próxima matriz, OK?
E então no próximo, podemos dizer, OK, se o existir?
Ele faz.
Este novo.
>> E assim, em nosso próximo, temos dito, OK, "zoo" já existe aqui.
Tudo o que precisamos fazer é definir este igual a verdade, que não é uma palavra lá.
Se você tivesse seguido tudo até antes desse ponto,
é uma palavra, por isso só configurá-lo igual a tal.
Sim?
>> AUDIÊNCIA: Então faz isso significa que "ba" é uma palavra também?
>> COLUNA 1: Não.
Portanto, neste caso, "ba" obteríamos aqui, diríamos que é uma palavra,
e ele ainda seria não.
Ok?
Mmhmm?
>> AUDIÊNCIA: Então, quando você é um palavra e você diz que sim, então ele
conterá a ir para m?
>> COLUNA 1: Então, isso tem a ver com-- você está carregando isso em.
Você diz "zoo" é uma palavra.
Quando você vai a check-- como, digamos que você quer dizer,
significa "jardim zoológico" existe neste dicionário?
Você só vai procurar "zoo" e, em seguida, verificar para ver se é uma palavra.
Você nunca vai se mover através de m porque isso não é
o que você está procurando.
>> Então, se nós realmente queria adicionar "banho" nesta tentativa,
faríamos a mesma coisa como fizemos com "zoo"
exceto veríamos que quando nós tentar chegar a hora, ele não existe.
Então você pode pensar nisso como uma tentativa para adicionar um novo nó em uma lista ligada,
de modo que seria necessário para adicionar outro uma dessas matrizes, assim.
E então o que fazemos é apenas definir o h elemento dessa matriz apontando para isso.
>> E então, o que gostaria de fazer aqui?
Adicioná-lo igual a true porque é uma palavra.
Legal.
Eu sei.
Tenta não são o mais emocionante.
Confie em mim, eu sei.
>> Então, uma coisa a perceber com tentativas, Eu disse, eles são muito eficientes.
Então, nós vimos eles levar até uma tonelada de espaço.
Eles são o tipo de confundir.
Então, por que nós nunca usá-los?
Usamos estes porque eles são incrivelmente eficiente.
>> Então, se você está sempre à procura uma palavra, só são
delimitada pelo comprimento da palavra.
Então, se você está procurando um palavra que tem um comprimento de cinco,
você está sempre apenas vai ter que fazer, no máximo, cinco comparações, OK?
Assim, torna-se, basicamente, uma constante.
Como a inserção e pesquisa são basicamente constante de tempo.
>> Então, se você pode nunca chegar algo em tempo constante,
que é tão bom quanto ele ganha.
Você não pode ficar melhor do que constante de tempo para essas coisas.
Assim que é um dos enormes vantagens de tentativas.
>> Mas é muito espaço.
Então você meio que tem que decidir o que é mais importante para você.
E em computadores de hoje, o espaço que uma tentativa pode levar até
talvez não afecta que muito, mas talvez
você está lidando com algo que tem muito, muito mais coisas,
e uma tentativa só não é razoável.
Sim?
>> AUDIÊNCIA: Aguarde, então você tem 26 letras em cada um?
>> COLUNA 1: Mmhmm.
Sim, você tem 26.
Você tem alguma é marcador de texto e, em seguida, você tem 26 indicadores em cada um.
E eles estão ponto--
>> AUDIÊNCIA: E a cada 26 anos, que cada um deles tem 26?
>> COLUNA 1: Sim.
E é por isso que, como você pode ver, ele se expande rapidamente.
Tudo certo.
Então, nós estamos indo para entrar em árvores, o que Eu sinto que é mais fácil e, provavelmente,
ser um pouco agradável indulto a partir de tentativas lá.
Portanto, esperamos que a maioria de vocês vi uma árvore antes.
Não como o bastante os de fora, que eu
Não sei se alguém foi ao ar recentemente.
Fui colheita da maçã neste fim de semana, e oh meu Deus, ele era lindo.
Eu não sabia que as folhas poderia parecer que bonita.
>> Portanto, esta é apenas uma árvore, certo?
É só algum nó, e aponta para um monte de outros nós.
Como você pode ver aqui, este é tipo de um tema recorrente.
Nodes apontando para nós é uma espécie de a essência de muitas estruturas de dados.
Depende apenas de como nós tê-los uns aos outros para apontar
e como nós percorremos através deles e como nós
inserir coisas que determina as suas diferentes características.
>> Então, basta um pouco de terminologia, que eu usei antes.
Então raiz é o que está no topo.
É onde nós sempre começar.
Você pode pensar nisso como a cabeça também.
Mas, para as árvores, que tendem a se referem a ele como a raiz.
>> Qualquer coisa no fundo aqui-- no muito, muito bottom--
folhas são consideradas.
Por isso, vai junto com o coisa árvore inteira, certo?
As folhas são nas bordas da sua árvore.
>> E depois temos também um par de termos de falar sobre nós em relação
uns com os outros.
Portanto, temos pai, filhos e irmãos.
Portanto, neste caso, é o 3 -mãe de 5, 6, e 7.
Então, o pai é o que está um passo acima de tudo o que você está
referindo-se, por isso só como uma árvore genealógica.
Felizmente, isso é tudo um pouco pouco mais intuitivo do que as tentativas.
>> Os irmãos são os que têm o mesmo pai, certo?
Eles estão no mesmo nível aqui.
E então, como eu estava dizendo que os filhos são apenas
tudo o que é um degrau abaixo o nó em questão, OK?
Legal.
Assim, uma árvore binária.
Alguém pode arriscar um palpite em um dos as características da árvore binária?
>> AUDIÊNCIA: Max duas folhas.
>> COLUNA 1: Certo.
Assim máximo de duas folhas.
Assim, em um presente antes, tivemos um presente que tinha três, mas de uma árvore binária,
você tem um máximo de dois crianças por pais, certo?
Há um outro característica interessante.
Alguém sabe isso?
Árvore binária.
>> Assim, uma árvore binária terá tudo em as-- este não é sorted--
mas de uma árvore binária classificados, tudo à direita
é maior do que a mãe, e tudo à esquerda
é menor do que a mãe.
E isso tem sido um quiz pergunta antes, então é bom saber.
Então, a forma como definimos isso, novamente, temos um outro nó.
Este é muito parecido com o que?
Duplamente
>> Audiência: Linked listas
>> COLUNA 1: Uma lista ligada dupla, certo?
Então, se substituirmos este com anterior e seguinte,
esta seria uma lista duplamente ligada.
Mas, neste caso, nós realmente ter esquerda e direita e é isso.
Caso contrário, é exatamente o mesmo.
Ainda temos o elemento você está procurando,
e você só tem dois ponteiros indo para o que vem a seguir.
Sim, então árvore binária de busca.
Se notarmos, tudo no aqui é maior than--
ou tudo imediatamente para a direita aqui
é maior do que, tudo aqui é inferior a.
>> Então, se fôssemos pesquisar, ele deve olhar muito próximo de busca binária
aqui, certo?
Exceto em vez de olhar na metade da matriz,
estamos apenas olhando para a esquerda ou lado ou do lado direito da árvore.
Então, ele fica um pouco mais simples, eu acho.
>> Portanto, se sua raiz é NULL, obviamente, é simplesmente falso.
E se ele está lá, obviamente, é verdade.
Se for menor do que, buscamos a esquerda.
Se for maior do que, buscamos a direita.
É exatamente como busca binária, apenas uma estrutura de dados diferente
que estamos usando.
Em vez de uma matriz, é apenas uma árvore binária.
>> OK, pilhas.
E também, parece que pode ter um pouco de tempo.
Se fizermos isso, estou feliz de ir sobre nada disso de novo.
OK, então empilha.
Alguém se lembra o que stacks-- quaisquer características de uma pilha?
>> OK, assim que a maioria de nós, eu acho, comer no jantar halls--
tanto quanto nós pode não gostar de.
Mas, obviamente, você pode pensar em uma pilha literalmente apenas como uma pilha de bandejas
ou uma pilha de coisas.
E o que é importante para perceber é que é
something-- a característica que podemos chamá-lo por-- é LIFO.
Alguém sabe o que isso significa?
Mmhmm?
>> AUDIÊNCIA: último a entrar, primeiro a sair.
>> COLUNA 1: Direito, último a entrar, primeiro a sair.
Então, se nós sabemos, se vamos empilhar as coisas se, a coisa mais fácil de agarrar off--
e talvez a única coisa que pode pegar off, se a nossa pilha é grande enough--
é aquele elemento superior.
Então o que foi colocado em last-- como vemos aqui,
tudo o que foi empurrado na maioria recently-- é
vai ser o primeiro coisa que nós pop off, OK?
>> Então o que temos aqui é outra struct typedef.
Isto é realmente apenas como um Bater Curso de estrutura de dados,
por isso há muito jogado em vocês.
Eu sei.
Então, mais uma struct.
Yay para estruturas.
>> E, neste caso, é um ponteiro para uma matriz que tem alguma capacidade.
Então, isso representa a nossa pilha aqui, como nossa matriz real
que está segurando os nossos elementos.
E então aqui temos alguns tamanho.
>> E geralmente, você quer manter pista de quão grande é a tua stack
porque o que vai permitir você precisa fazer é se você sabe o tamanho,
ele permite que você diz, OK, eu sou a capacidade?
Posso adicionar mais alguma coisa?
E também lhe diz onde a parte superior do seu stack
É assim que você sabe o que você pode realmente decolar.
E isso realmente vai ser um pouco mais claro.
>> Assim, por impulso, uma coisa, se você nunca foram para implementar impulso,
como eu estava dizendo, o seu pilha tem um tamanho limitado, certo?
Nossa matriz tinha alguma capacidade.
É uma matriz.
É um tamanho fixo, por isso precisamos certifique-se de que não estamos colocando mais
em nossa matriz do que nós realmente tem espaço para.
>> Então, quando você está criando um impulso função, a primeira coisa que você faz é dizer, OK,
eu tenho espaço na minha pilha?
Porque se eu não fizer isso, desculpe, Eu não posso guardar o seu elemento.
Se eu fizer isso, então você deseja armazenar -lo no topo da pilha, à direita?
>> E é por isso que temos manter o controle do nosso tamanho.
Se não manter o controle de nosso tamanho, não sabemos onde colocá-lo.
Nós não sabemos quantas coisas estão em nossa matriz já.
Como, obviamente, existem maneiras que talvez você poderia fazê-lo.
Você pode inicializar tudo para NULL e, em seguida, verifique o mais recente NULL,
mas uma coisa muito mais fácil é apenas quer dizer, OK, manter o controle de tamanho.
Como eu sei que eu tenho quatro elementos na minha matriz, então a próxima coisa
que colocar, nós somos indo para armazenar no índice 4.
E então, é claro, isto significa que você empurrou algo com sucesso
em seu stack, você quer aumentar o tamanho
para que você saiba onde você está para que você pode empurrar mais coisas sobre.
>> Então, se estamos tentando pop algo fora da pilha,
o que poderia ser a primeira coisa que deseja verificar?
Você está tentando tomar algo fora de sua pilha.
Tem certeza de que há algo em sua pilha?
Não.
Então, o que podemos querer verificar?
>> AUDIÊNCIA: [inaudível].
COLUNA 1: Verifique o tamanho?
Tamanho.
Por isso, queremos verificar se nosso tamanho é maior que 0, OK?
E se é, então nós queremos diminuir nosso tamanho por 0 e retornar isso.
Por quê?
>> No primeiro fomos empurrando, nós empurrou
sobre o tamanho eo tamanho atualizado.
Neste caso, estamos diminuindo o tamanho e depois tirá-lo, arrancando-o
da nossa matriz.
Por que fazemos isso?
Então, se eu tenho uma coisa na minha pilha, qual seria o meu tamanho em que ponto?
1.
>> E onde está armazenado o elemento 1?
Em que índice?
AUDIÊNCIA: 0.
COLUNA 1: 0.
Portanto, neste caso, nós sempre precisa fazer sure--
em vez de retornar tamanho menos 1, porque nós
saber que o nosso elemento é vai ser armazenado a uma menor
seja qual for o nosso tamanho é, este só cuida dele.
É uma maneira um pouco mais elegante.
E nós só diminuir nossa tamanho e, em seguida, retornar tamanho.
Mmhmm?
>> AUDIÊNCIA: Eu acho que só em geral, por que essa estrutura de dados
ser benéfico?
>> COLUNA 1: Depende do seu contexto.
Assim, para algumas das teorias, se você está trabalhando com-- OK,
deixe-me ver se há um benéfico que é benéfico para mais de fora
de CS.
Com pilhas, a qualquer hora que você precisa manter o controle de algo que
é o adicionado mais recentemente é quando você vai querer usar uma pilha.
>> E eu não posso pensar em uma boa exemplo do que agora.
Mas sempre que a mais recente coisa é mais importante para você,
que é quando uma pilha vai ser útil.
Eu estou tentando pensar se há uma boa para isso.
Se eu pensar em um bom exemplo na próxima 20 minutos, com certeza vou te dizer.
>> Mas no geral, se há alguma coisa, como eu disse a maioria, onde mais recente
é o mais importante, que é onde uma pilha entra em jogo.
Considerando as filas são uma espécie de oposto.
E todos os cães pequenos.
Não é esta a grande, certo?
Eu sinto que eu deveria só tem um vídeo coelho
à direita no meio de seção para vocês
porque este é um corte intenso.
>> Então uma fila.
Basicamente, uma fila é como uma linha.
Vocês Tenho certeza de que uso isso todos os dias, assim como em nossas salas de jantar.
Então, nós temos que ir em e chegar em nossas bandejas, eu sou
se você tem que esperar na fila para roubar ou obter seu alimento.
>> Assim, a diferença aqui é que este é o FIFO.
Então, se LIFO foi o último a entrar, primeiro fora, FIFO é o primeiro a entrar, primeiro fora.
Portanto, este é o lugar onde tudo o que você colocar em primeiro lugar é a sua mais importante.
Então, se você estava esperando em um linha-- pode você
imagine se você fosse a ir buscar o novo iPhone
e era uma pilha em que a última pessoa da fila chegou primeiro,
as pessoas iriam matar um ao outro.
>> Então FIFO, estamos todos muito familiarizados com no mundo real aqui,
e tudo isso tem a ver com a verdade tipo de recriar esta linha inteira
e filas estrutura.
Assim, enquanto que com a pilha, temos push e pop.
Com uma fila, temos enfileiramento e retirar da fila.
Então enfileiramento significa, basicamente, colocá-lo na parte de trás,
e meios dequeue tomar fora a partir da frente.
Portanto, a nossa estrutura de dados é um pouco mais complicado.
Temos uma segunda coisa a acompanhar.
>> Assim, sem a cabeça, esta é exatamente uma pilha, certo?
Esta é a mesma estrutura que uma pilha.
A única coisa diferente agora é que tem essa cabeça, que o que você pensa
vai acompanhar?
>> AUDIÊNCIA: O primeiro.
>> COLUNA 1: Direito, o primeira coisa que colocamos no.
O chefe da nossa fila.
Quem é o primeiro da fila.
Tudo bem, então se fizermos enfileiramento.
Mais uma vez, com qualquer de estas estruturas de dados,
uma vez que estamos lidando com um array, precisamos verificar se temos espaço.
>> Este é tipo de como me dizendo vocês, se você abrir um arquivo,
você precisa verificar para null.
Com qualquer destas pilhas e as filas, você precisa
para ver se há espaço porque estamos lidar com uma matriz de tamanho fixo,
como vemos aqui-- 0, 1 tudo até 5.
Então o que fazer nesse caso é de seleção para ver se ainda temos espaço.
É o nosso tamanho inferior a capacidade?
>> Se assim for, é preciso armazená-lo em a cauda e nós atualizamos nosso tamanho.
Então, o que pode ser a cauda neste caso?
Não está explicitamente escrito para fora.
Como podemos armazená-lo?
Qual seria a cauda ser?
>> Então, vamos caminhar por este exemplo.
Portanto, esta é uma matriz de tamanho 6, certo?
E temos agora, nosso tamanho é 5.
E quando nós colocá-lo em, ele vai ir para o quinto índice, certo?
Assim armazenar pelo cauda.
>> Outra maneira de escrever cauda seria apenas ser a nossa matriz no índice de tamanho, certo?
Isto é de tamanho 5.
A próxima coisa que vai entrar em cinco.
Legal?
Está bem.
Ele fica um pouco mais complicado quando começamos a mexer com a cabeça.
Sim?
>> AUDIÊNCIA: Isso significa que nós teria declarado uma matriz que
era de cinco elementos de comprimento e então nós estamos adicionando para ele?
>> COLUNA 1: Não.
Portanto, neste caso, esta é uma pilha.
Este seria declarada como uma matriz de tamanho 6.
E, neste caso, nós só tem um espaço à esquerda.
>> OK, então uma coisa é neste caso, se a nossa cabeça está em 0,
então nós apenas pode adicioná-lo em tamanho.
Mas fica um pouco mais complicado porque, na verdade, eles
não tem um slide para isso, então eu vou
desenhar um porque não é tão simples, uma vez que
começar a se livrar das coisas.
Assim, enquanto que com uma pilha você só tem
se preocupar com o que o tamanho é quando você está adicionando algo sobre,
com uma fila que você também precisa fazer Certifique-se que sua cabeça está contabilizado,
porque uma coisa legal sobre filas é que se você não estiver com sua capacidade,
você pode realmente fazer isso enrole.
>> OK, então um coisa-- oh, isso é terrível giz.
Uma coisa a considerar é o caso.
Nós vamos apenas fazer cinco.
OK, então nós estamos indo para dizem que a cabeça está aqui.
Este é 0, 1, 2, 3, 4.
>> A cabeça está lá, e por favor, tem coisas em si.
E queremos acrescentar algo, certo?
Então, a única coisa que precisamos sabe é que a cabeça é sempre
vai se mover desta maneira e em seguida, volta ao início volta, OK?
>> Portanto, esta fila tem espaço, certo?
Ele tem espaço no início, tipo da frente deste.
Então o que precisamos fazer é nós precisa para calcular a cauda.
Se você sabe que seu cabeça não mudou, cauda
é apenas a sua matriz no o índice do tamanho.
>> Mas, na realidade, se você estiver usando uma fila, sua cabeça provavelmente está sendo atualizado.
Então o que você precisa fazer é na verdade calcular a cauda.
Então, o que fazemos é esta fórmula aqui, que eu vou deixar você
vocês pensam sobre e então vamos falar sobre isso.
Portanto, esta é a capacidade.
>> Então, isso vai realmente dar-lhe uma maneira de fazê-lo.
Porque neste caso, o quê?
Nossa cabeça está em 1, nosso tamanho é 4.
Se nós mod que por 5, obtemos 0, que é onde deve introduzir-lo.
>> Então, em seguida, no caso seguinte, se tivéssemos que fazer isso,
podemos dizer, OK, vamos desenfileirá algo.
Nós desenfileirá isso.
Tomamos a este elemento, certo?
>> E agora a nossa cabeça está apontando aqui, e queremos adicionar em outra coisa.
Este é basicamente o de trás da nossa linha, certo?
As filas podem envolver em torno da matriz.
Essa é uma das principais diferenças.
Pilhas, você não pode fazer isso.
>> Com filas, você pode porque tudo o que importa
é que você sabe o que foi adicionado mais recentemente.
Uma vez que tudo vai ser adicionado em neste sentido para a esquerda, no caso em apreço,
e em seguida, enrole ao redor, você pode continuar colocando em novos elementos
na parte da frente da matriz porque não é realmente
a frente da matriz mais.
Você pode pensar no início do matriz como em sua cabeça realmente é.
>> Portanto, esta fórmula é como você calcular a sua cauda.
Será que isso faz sentido?
Está bem.
OK, dequeue, e em seguida Vocês têm 10 minutos
para me perguntar qualquer perguntas de esclarecimento você quer, porque eu sei que é loucura.
>> Tudo bem, então no mesmo maneira-- Eu não sei se vocês notaram,
mas CS é tudo sobre padrões.
As coisas são muito bonito o mesmo, apenas com pequenos ajustes.
Então mesma coisa aqui.
Precisamos verificar para ver se realmente têm algo em nossa fila, certo?
Dizer, OK, é o nosso tamanho maior que 0?
Legal.
>> Se o fizermos, então nós nos movemos nossa cabeça, que é o que eu acabei demonstrado aqui.
Nós atualizamos a nossa cabeça para ser mais um.
E depois que nós diminuiremos nossa tamanho e retornar o elemento.
>> Há muito mais concreto código em study.cs50.net,
e eu recomendo ir por isso, se você tiver tempo,
mesmo que seja apenas um pseudo-código.
E se vocês querem falar através que comigo um a um, por favor, me deixe
sei.
Eu ficaria feliz em.
As estruturas de dados, se você tomar CS 124, você vai
sabemos que as estruturas de dados ficar muito diversão e este é apenas o começo.
>> Então, eu sei que é difícil.
Está certo.
Nós lutamos.
Eu continuo a fazer.
Então não se preocupe muito com isso.
>> Mas isso é basicamente o seu Crash Course em estruturas de dados.
Eu sei que é muito.
Existe alguma coisa que nós gostaria de ir de novo?
Qualquer coisa que quero falar através?
Sim?
>> AUDIÊNCIA: Para esse exemplo, de modo a cauda nova é a 0 sobre isso?
COLUNA 1: Sim.
AUDIÊNCIA: OK.
Então passando, você teria um mais 4 ou-
>> COLUNA 1: Então você estava dizendo, quando queremos ir fazer isso de novo?
AUDIÊNCIA: Yeah.
Então, se você estava imaginando out-- onde estão você calcular a cauda da nisso?
>> COLUNA 1: Então a cauda foi em-- eu mudei isso.
Assim, neste exemplo aqui, esta foi a matriz que estamos olhando, OK?
Portanto, temos coisas em 1, 2, 3 e 4.
Portanto, temos a nossa cabeça é igual a 1 no Neste ponto, o tamanho e a é igual a 4
neste ponto, certo?
>> Vocês todos concordam que é o caso?
Então nós fazemos a cabeça mais o tamanho, o que nos dá 5, e então nós mod por 5.
Recebemos 0, o que nos diz que 0 é onde está a nossa cauda, ​​onde temos espaço.
>> AUDIÊNCIA: O que é um cap?
>> COLUNA 1: A capacidade.
Desculpe.
Então esse é o tamanho de sua matriz.
Sim?
>> AUDIÊNCIA: [inaudível] antes retornamos o elemento?
>> COLUNA 1: Então, passamos a ir ou voltar do momento?
Então, se nós nos movemos um, diminuir o tamanho?
Aguente.
Eu definitivamente esqueceu o outro.
Não importa.
Não há outra fórmula.
Sim, você gostaria de voltar a cabeça e, em seguida, movê-lo de volta.
>> AUDIÊNCIA: OK, porque neste ponto, a cabeça estava em 0,
e depois quiser retornar índice 0 e, em seguida, fazer a cabeça 1?
>> COLUNA 1: Certo.
Eu acho que há outro tipo fórmula de como este.
Eu não tenho isso no topo da minha cabeça como Eu não quero dar-lhe a pessoa errada.
Mas eu acho que é perfeitamente válida para digamos, OK, guarde esta element-- o que quer
elemento de cabeça é-- diminuir sua tamanho, mover a cabeça mais, e retorno
o que quer que esse elemento é.
Isso é perfeitamente válido.
Está bem.
Eu sinto que isso não é como o most-- você não está
vai sair daqui como, sim, eu sei tentativas.
Eu tenho tudo.
Isso está ok.
Eu prometo.
Mas estruturas de dados que são algo é preciso muito tempo para se acostumar.
Provavelmente uma das mais difíceis coisas, eu acho que, no curso.
>> Por isso, definitivamente leva repetição e olhando at-- I
realmente não sei listas ligadas até que eu fiz demais com eles,
da mesma forma que eu não fiz realmente entender ponteiros
até que eu tive que ensiná-lo para dois anos e faço meus próprios Série de Exercícios com ele.
Ele tem um monte de reiteração e do tempo.
E, eventualmente, ele vai tipo de clique.
>> Mas, enquanto isso, se você tem o tipo de um elevado nível de compreensão que
estes fazem, seus prós e que é o que cons--
nós realmente tendem a enfatizar, especialmente no curso de introdução.
Como, por que usaria uma tentativa através de uma matriz?
Como, quais são os aspectos positivos e negativos de cada um deles?
>> E entender os trade-offs entre cada uma destas estruturas
é o que é muito mais importante agora.
Não pode ser um louco ou duas perguntas que é
vai pedir-lhe para implementar impulso ou implementar pop ou enfileiramento e retirar da fila.
Mas, na maior parte, tendo essa maior nível de compreensão e mais
de uma compreensão intuitiva é mais importante do que realmente
ser capaz de implementá-lo.
>> Seria realmente maravilhoso se todos vocês podia sair e ir para implementar uma tentativa,
mas entendemos que não é necessariamente a coisa mais razoável agora.
Mas você pode em seu pset, se você quiser para, em seguida, você vai começar a prática,
e, em seguida, talvez você realmente entendê-la.
Sim?
>> AUDIÊNCIA: OK, então quais são que pretendia usar no pset?
Preciso usar um deles?
COLUNA 1: Sim.
Então você tem a sua escolha.
Eu acho que, neste caso, podemos falar sobre o pset um pouco
porque eu corri através destes.
Assim, no seu pset, você tem o seu escolha de tentativas ou tabelas de hash.
Algumas pessoas vão tentar e usar filtros de Bloom,
mas aqueles que tecnicamente não estão corretas.
Devido à sua natureza probabilística, eles dão falsos positivos, às vezes.
São olhar frio em, no entanto.
Recomendo olhar para eles, pelo menos.
Mas você tem a sua escolha entre uma tabela hash e uma tentativa.
E isso vai ser onde você carrega em seu dicionário.
>> E você terá que escolher sua função de hash,
você precisa escolher quantos baldes você tem, e vai variar.
Como se você tiver mais baldes, talvez ele vai correr mais rápido.
Mas talvez você está desperdiçando um muito espaço dessa forma, no entanto.
Você tem que descobrir isso.
Mmhmm?
>> AUDIÊNCIA: Você disse antes que podemos usar outras funções de hash,
que não temos a criar uma função hash?
>> COLUNA 1: Sim, certo.
Então, literalmente, para a sua função de hash, como o google "função hash"
e olhar para alguns dos mais interessantes.
Você não está prevista a construção suas próprias funções de hash.
As pessoas gastam o seu teses sobre essas coisas.
>> Então não se preocupe sobre a construção de seu próprio país.
Encontrar uma linha para começar.
Alguns deles você tem que manipular um pouco
para garantir que os tipos de retorno igualar-se e outros enfeites, assim, no início,
Eu recomendaria usar algo realmente fácil que talvez apenas
hashes na primeira letra.
E, em seguida, uma vez que você tem que trabalhar, incorporando uma função hash mais frio.
Mmhmm?
>> AUDIÊNCIA: Será que um tente ser ou eficiente, mas apenas mais difícil, como--
>> COLUNA 1: Então uma chance, eu acho, é intuitivamente difícil de implementar
mas é muito rápido.
No entanto, ocupa mais espaço.
Novamente, você pode otimizar tanto dos que estão no diferentes maneiras e existem maneiras a--
AUDIÊNCIA: Como estamos classificados sobre isso?
Será que matter--
>> COLUNA 1: Então você está classificado como normal.
Você vai ser graduada em design.
Independentemente da forma como você faz, você quer ter certeza que é tão elegante como ela pode ser
e tão eficiente quanto possível.
Mas se você escolher uma tentativa ou de hash mesa, contanto que ele funciona,
estamos felizes com isso.
E se você usar algo que hashes na primeira letra, isso é bom,
como talvez como design-wise.
Também estamos atingindo o ponto neste semester--
Eu não sei se você caras noticed-- se você estiver
graus PSet diminuir um pouco por causa do design e outros enfeites,
isso é perfeitamente normal.
Está ficando a um ponto onde sua programas estão ficando cada vez mais complicado.
Há mais lugares você pode melhorar.
>> Por isso é perfeitamente normal.
Não é que você está fazendo pior em seu pset.
É só que estamos sendo mais difícil para você agora.
Então, todo mundo está sentindo isso.
Eu só graduada todas as suas Série de Exercícios.
Eu sei que todo mundo está sentindo isso.
>> Portanto, não se preocupar com isso.
E se você tiver quaisquer dúvidas Série de Exercícios anteriores ou maneiras que você pode melhorar,
Eu tento e comentar o específico lugares, mas às vezes é tarde
e eu fico cansado.
Existem outras coisas sobre estruturas de dados?
Tenho certeza de que vocês realmente não quero falar mais deles,
mas se houver, eu estou feliz de passar por cima deles, assim como qualquer coisa
de palestra passado semana ou na semana passada.
>> Eu sei que na semana passada foi toda a revisão, de modo podemos ter pulado alguma revisão
da palestra.
Todas as outras perguntas eu posso responder?
OK, tudo bem.
Bem, vocês sair 15 minutos mais cedo.
>> Espero que este era semi-útil, pelo menos, e eu vou ver vocês na próxima semana,
ou o horário de expediente quinta-feira.
Há pedidos de lanches para a próxima semana, que é a coisa?
Porque eu esqueci de doces hoje.
E eu trouxe doces última semana, mas era Dia de Colombo,
então não eram como seis pessoas que tinha quatro sacos de doces para si.
Eu posso trazer Starbursts novamente se quiser.
Starbursts?
OK, parece bom.
Tenha um ótimo dia, pessoal.