COLUNA 1: Tudo bem, então este é CS50 Este é o fim de semana cinco. E lembrar que da última vez que comecei a olhar para os dados mais chique estruturas que passaram a resolver problemas, que começaram a introduzir novos problemas, mas a chave para este Era o tipo de rosqueamento que nós começou a fazer a partir de nó a nó. Então, isso, claro, é uma lista vinculada isoladamente. E por vinculada isoladamente, Quer dizer, há apenas um enrosque entre cada um desses nós. Acontece que você pode fazer mais chique coisas como listas duplamente ligadas em que você tem uma seta indo em ambas as direções, o que pode ajudar com determinadas eficiências. Mas isso resolveu o problema? O problema é que isto resolve? Por que nós nos importamos na segunda-feira? Por que, em teoria, se nós nos importamos na segunda-feira? O que isso faz? 

AUDIÊNCIA: Nós podemos redimensioná-lo dinamicamente. 

COLUNA 1: OK, então nós podemos redimensioná-lo dinamicamente. Bem feito tanto de você. Assim, você pode redimensionar dinamicamente este estrutura de dados, enquanto que uma matriz, recall, você tem que saber um priori quanto espaço você quer e se você precisar de um pouco mais espaço, você é tipo de fora da sorte. Você tem que criar uma matriz totalmente novo. Você tem que mover todos os seus dados de um para o outro, eventualmente, liberar o array antigo se você puder, e depois prosseguir. Que só se sente muito caro e muito ineficiente, e na verdade ele pode ser. Mas isso não é tudo de bom. Nós pagamos um preço, o que era uma dos preços mais óbvios nós pagar usando uma lista ligada? 

AUDIÊNCIA: Nós temos que usar espaço duplo para cada um. COLUNA 1: Sim, por isso precisamos pelo menos duas vezes mais espaço. Na verdade, eu percebi isso de imagem até mesmo um pouco enganador, porque no IDE CS50 em um monte de moderno computadores, um ponteiro ou um endereço não é, de facto, quatro bytes. É muito frequentemente estes dias oito bytes, os quais significa que a parte inferior mais retângulos lá em realidade são uma espécie de duas vezes mais grande como o que eu desenhei, o que significa que você está usando três vezes mais tanto espaço quanto poderíamos ter outra forma. Agora, ao mesmo tempo, estamos ainda falando bytes, certo? Nós não estamos necessariamente falando megabytes ou gigabytes, a menos que essas estruturas de dados ficar grande. 

E por isso hoje nós começamos a considerar como podemos explorar dados de forma mais eficiente se em fato de os dados se torna maior. Mas vamos tentar canonizar as primeiras operações que você pode fazer sobre estes tipos de estruturas de dados. Então, algo como um ligado lista suporta geralmente Operações como excluir, inserir e pesquisar. E o que quero dizer com isso? Isso só significa que, geralmente, se as pessoas estão usando lista encadeada, eles ou alguém tem implementado funções como DELETE, INSERT, e busca, assim você pode realmente fazer alguma coisa útil com a estrutura de dados. Então, vamos dar uma olhada rápida em como podemos implementar algum código para uma lista ligada como se segue. 

Portanto, este é apenas algum código C, nem mesmo um programa completo que eu realmente rapidamente empolada. Não é on-line na distribuição de código, pois não irão correr. Mas note Acabei com um comentário disse, dot dot dot, há algo lá, dot dot dot, alguma coisa lá. E vamos apenas olhar para que as peças são suculentos. Assim, na linha três, Recordamos que este é agora propusemos declarando um nó último tempo, um desses objetos retangulares. Ele tem um int que vamos chamá-N, mas poderíamos chamá-lo de qualquer coisa, e, em seguida, uma estrela nó struct chamada seguinte. E só para ficar claro, que segundo linha, em linha seis, o que é isso? O que ele está fazendo por nós? Porque certamente parece mais críptica do que nossas variáveis ​​habituais. 

AUDIÊNCIA: Torna-se passar um. 

COLUNA 1: Ele faz mover-se mais de um. E para ser mais preciso, ele irá armazenar o endereço do nó que está destinado a ser semanticamente próximo a ele, certo? Por isso, não vai necessariamente mover qualquer coisa. Ele só vai armazenar um valor, que é vai ser o endereço de algum outro nó, e é por isso que nós dissemos struct estrela nó, a estrela denotando um ponteiro ou um endereço. OK, então agora se você assumir que temos N esta disponível para nós, e vamos supor que alguém tem inserido um monte de números inteiros em uma lista ligada. E essa lista ligada é apontada por algum ponto um chamado de lista de variáveis ​​que é passou aqui como um parâmetro, como faço para ir sobre a linha 14 execução de pesquisa? Em outras palavras, se eu estou implementando função cujo propósito na vida é tomar um int e, em seguida, o começando de uma lista ligada, que é um apontador para a lista encadeada. Como primeiro, que eu acho que David foi o nosso voluntário na segunda-feira, ele estava apontando para toda ligada a lista, é como se nós estamos passando David em como nosso argumento aqui. Como é que vamos atravessar esta lista? Bem, acontece que, apesar de ponteiros são relativamente novo para nós agora, nós podemos fazer isso relativamente diretamente. 

Eu estou indo para ir em frente e declarar uma variável temporária que por convenção é só ir a ser chamado de ponteiro, ou PTR, mas você poderia chamá-lo de qualquer coisa que você quiser. E eu estou indo para inicializar -lo para o início da lista. Assim, você pode tipo de pensar neste como o professor me no outro dia, tipo de apontando para alguém entre nossos seres humanos como voluntários. Então, eu sou uma variável temporária que é apenas apontando para a mesma coisa que a nossa coincidentemente chamado voluntário David também estava apontando. Agora, enquanto ponteiro é não nulo, porque recordação que nulo é um valor especial sentinela o demarca o fim da lista, assim, enquanto eu não estou apontando para a terra como a nossa última voluntário era, vamos em frente e faça o seguinte. Se pointer-- e agora eu meio que quero para fazer o que fizemos com o aluno structure-- se ponteiro ponto próximo equals-- vez, se é igual a N ponteiro ponto é igual à variável n, a argumento que tem sido transmitido, então eu quero ir em frente e dizer return true. Eu encontrei o número N dentro de um dos nós da minha lista ligada. Mas o ponto deixa funciona neste contexto, porque ponteiro, PTR, é na verdade, um ponteiro, um endereço, nós realmente podemos maravilhosamente Finalmente usar um pedaço de sintaxe esse tipo de marcas senso intuitivo e, na verdade, usar uma flecha aqui, o que significa ir de esse endereço para o número inteiro lá dentro. Portanto, é muito semelhante em espírito para o operador ponto, mas porque ponteiro não é um ponteiro e não uma struct em si real, nós apenas usar a seta. 

Portanto, se o nó atual que eu, o variável temporária, estou apontando para não é N, o que eu quero fazer? Bem, com os meus voluntários humanos que tivemos aqui no outro dia, se o meu primeiro ser humano não é o que eu quer, e talvez o segundo humano não é o que eu quero, eo terceiro, I precisa para se manter fisicamente em movimento. Como como faço para percorrer uma lista? Quando tivemos um array você, apenas fiz como eu plus plus. Mas, neste caso, basta fazer ponteiro, fica, ponteiro, em seguida. Em outras palavras, o campo seguinte é como todas as mãos esquerda que os nossos voluntários humanos na segunda-feira estavam usando para apontar para algum outro nó. Aqueles eram seus vizinhos próximos. 

Então, se eu quiser passar por esta lista, Eu não posso simplesmente fazer eu plus plus mais, Eu tenho que dizer, em vez I, ponteiro, vai para igualar qualquer que seja o campo seguinte é, O próximo campo, o campo seguinte é, seguindo todas essas mãos esquerdas que tivemos no palco apontador para alguns valores subsequentes. E se eu passar Toda essa iteração, e, finalmente, eu bati nulo não ter N encontrado ainda, eu só retornar falso. Então, novamente, tudo o que estamos fazendo aqui, de acordo com a imagem de um momento atrás, está começando por apontar para a início da lista presumivelmente. E então eu vá, é o valor Eu estou procurando igual a nove? Se assim for, volto verdade e eu sou feito. Se não, eu atualizo minha mão, Ponteiro AKA, para apontar a localização da próxima seta e, em seguida, a localização próxima da seta, e no próximo. Eu estou simplesmente andando através desta matriz. 

Então, novamente, quem se importa? Como o que é este um ingrediente para? Bem, lembre-se que nós introduzimos a noção de uma pilha, que é um tipo abstrato de dados na medida em que é não é uma coisa C, não é uma coisa CS50, é uma idéia abstrata, essa idéia de empilhamento coisas em cima da outra que pode ser implementado em cachos de maneiras diferentes. E uma maneira que propusemos foi com uma matriz, ou com uma lista ligada. E verifica-se que canonicamente, uma pilha suporta, pelo menos, duas operações. E as palavras de zumbido são empurrão, para empurrar algo para a pilha, como uma nova bandeja no sala de jantar, ou pop, o que significa que para remover o mais alto bandeja da pilha no jantar hall, e então talvez alguns bem como outras operações. Então, como podemos definir a estrutura que agora estamos chamando uma pilha? 

Bem, nós temos todo o requisite sintaxe à nossa disposição em C. Eu digo, me dê uma definição de tipo de uma estrutura dentro de uma pilha, Eu vou dizer é um array, de um todo monte de números e, em seguida tamanho. Portanto, em outras palavras, se eu quiser para implementar isso no código, Deixa-me ir apenas uma espécie de desenhar o que se diz. Portanto, este está dizendo, me dê um estrutura que tem uma matriz, e eu não sei o que é capacidade, é aparentemente alguma constante que eu tenho definido em outro lugar, e isso é bom. Mas suponho que é apenas um, dois, três, quatro, cinco. Assim, a capacidade é de 5. Este elemento dentro da minha estrutura serão chamados números. E então eu preciso de um outra variável aparentemente chamado tamanho que inicialmente eu vou estipular é inicializado para zero. Se não há nada em a pilha, o tamanho é zero, e seus valores de lixo em números. Eu não tenho idéia o que está lá ainda. 

Então, se eu quero empurrar algo na pilha, suponha que eu chamo de impulso função, e Eu digo empurrar 50, como o número 50, onde proporia Eu desenhá-lo nessa matriz? Há cinco diferentes respostas possíveis. Onde você quer empurrar o número 50? Se o objetivo aqui, mais uma vez, chamar a empurrão função, passa um argumento de 50, onde posso colocá-lo? Cinco possible-- 20% de chance de adivinhar corretamente. Sim? 

AUDIÊNCIA: Extrema-direita. 

COLUNA 1: Extrema-direita. Existe agora uma chance de 25% de adivinhar corretamente. De modo que seria realmente bom. Por convenção, eu vou dizer com uma matriz, que seria geralmente começar à esquerda, mas poderíamos certamente começa pela direita. Então, o spoiler aqui seria eu sou provavelmente, vai para desenhá-lo à esquerda, assim como em uma matriz normal, onde Eu começo a ir à esquerda para a direita. Mas se você pode virar a aritmética, tudo bem. Não é apenas convencional. OK, eu preciso fazer uma mais mudanças embora. Agora que eu empurrei algo para a pilha, o que está próximo? 

Tudo bem, eu tenho que aumentar o tamanho. Então deixe-me ir em frente e apenas actualizar esta, que era igual a zero. E, em vez agora, eu vou para colocar no valor de um. E agora suponho que eu empurre outro número na pilha, como 51. Bem, eu tenho que fazer mais uma mudança, que é até o tamanho dois. E então suponho que eu empurrar mais uma número na pilha como 61, agora eu preciso atualizar o tamanho mais uma tempo, e obter o valor 3 como o tamanho. E agora suponho que eu chamo pop. Agora pop, por convenção, Não é preciso um argumento. Com uma pilha, o conjunto ponto da metáfora bandeja é que você não tem poder discricionário para ir buscar a bandeja, tudo que você pode fazer é pop o mais alto de uma pilha, apenas porque. Isso é o que esta estrutura de dados faz. 

Então, por que a lógica se eu dizer pop, o que sai? Então, 61. Então, o que realmente é o computador vai fazer na memória? O que o meu código tem que fazer? O que proporia nós mudamos na tela? O que deve mudar? Desculpa? Por isso, se livrar de 61. Então eu definitivamente posso fazer isso. E eu posso me livrar de 61. E então o que os outros mudança precisa acontecer? Tamanho, provavelmente, tem que voltar para dois. E assim tudo bem. Mas espere um minuto, tamanho um momento atrás tinha três anos. Vamos apenas fazer uma verificação de sanidade rápida. Como é que nós sabemos que nós queria se livrar de 61? Porque nós estamos estalando. E então eu tenho esta segunda tamanho da propriedade. 

Espere um minuto, estou pensando de volta para a segunda semana quando começamos a falar sobre arrays, onde este foi local de zero, este foi um local, este foi localização dois, este é o local de três, quatro, parece que o relação entre o tamanho e o elemento que eu quero remover a partir da matriz parece ser apenas o que? Tamanho menos um. E foi assim que, como seres humanos sabemos que 61 vem em primeiro lugar. Como está o computador vai saber? Quando seu código, onde você provavelmente quer fazer o tamanho menos um, Assim, três menos um é dois, e que significa que querem se livrar de 61. E então podemos realmente atualizar o tamanho de modo que o tamanho agora vai desde três a apenas dois. E só para ser pedante, eu vou a propor que eu sou feito, certo? Você proposto intuitivamente corretamente eu deveria livrar-se de 61. Mas não tem que tipo de tipo de livrado de 61? Eu efetivamente esquecido que é realmente lá. E acho que volta para PSet4, se você leu o artigo sobre forense, o PDF que tínhamos vocês ler, ou você vai ler esta semana para PSet4. Lembre-se que este é realmente pertinente para toda a idéia de computação forense. O que um computador faz é geralmente ele simplesmente se esquece de onde algo é, mas não ir e como tentar riscá-lo fora ou substituição esses bits com zeros e uns ou algum outro padrão aleatório a menos que você mesmo fazê-lo deliberadamente. Assim, a sua intuição estava bem, vamos nos livrar de 61. Mas, na realidade, não tem que se preocupar. Nós só precisamos esquecer que ele está lá mudando nosso tamanho. 

Agora há um problema com esta pilha. Se eu continuar empurrando as coisas para a pilha, o que é obviamente, vai acontecer em apenas alguns momentos do tempo? Nós vamos ficar sem espaço. E o que vamos fazer? Estamos tipo de rosca. Esta implementação não deixa nos redimensionar a matriz, porque usar esta sintaxe, se você acho que volta para duas semanas, uma vez que você declarou o tamanho de uma matriz, nós não vimos ainda um mecanismo onde você pode alterar o tamanho da matriz. E, de fato C não tem esse recurso. Se você diz que me dar cinco Nths, chamá-los de números, isso é tudo o que você está indo para obtê-lo. Então, o que fazemos agora como de segunda-feira, tem a capacidade de expressar uma solução porém, só precisamos ajustar a definição da nossa pilha a não ser alguns matriz codificados, mas apenas para armazenar um endereço. 

Agora, por que é isso? Agora só temos de estar confortável com o fato de que quando o meu programa é executado, Eu estou indo para presumivelmente tem que perguntar o ser humano, quantos números que você deseja armazenar? Assim, a entrada tem que vir de algum lugar. Mas uma vez eu sei que número, então eu posso apenas usar o que funciona para dar me um pedaço de memória? Eu posso usar malloc. E eu posso dizer qualquer número de bytes Eu quero voltar para estes Nths. E tudo o que tenho para armazenar os números variável aqui dentro deste struct deve ser o que? O que realmente vai para o números nesse cenário? É, um ponteiro para o primeiro byte desse pedaço de memória, ou mais especificamente, o endereço do primeiro desses bytes. Não importa se é um bytes ou um bilhão de bytes, Eu só precisa se preocupar com o primeiro. Porque o que malloc e garantias minhas garantias do sistema operacional, é que o pedaço de memória I obter, ele vai ser contíguos. Não vai ser lacunas. Então, se eu pedi para 50 ou bytes 1.000 bytes, eles estão todos indo para ser back to back to back. E desde que eu me lembro como grande, como Eu pedi muito, tudo o que precisa de saber é o primeiro tal endereço. 

Portanto, agora temos a capacidade de código. Embora, isso vai nos levar mais tempo para escrever isto, poderíamos agora realocar que a memória por apenas armazenar um endereço diferente lá se queremos uma maior ou mesmo um pedaço menor de memória. Então aqui para encontrar um compromisso. Agora temos dinamismo. Nós ainda temos contiguidade estou afirmando. Porque malloc nos dará um pedaço contíguo de memória. Mas isso vai ser uma dor no o pescoço para nós, o programador, para realmente codificar. É apenas mais trabalho. Precisamos de código semelhante ao que eu era batendo para fora apenas um momento atrás. Muito factível, mas adiciona complexidade. E assim desenvolvedor tempo, programador o tempo é ainda um outro recurso para que pudéssemos precisa gastar algum tempo para obter novos recursos. E depois, claro, há uma fila. Nós não vamos entrar nesse um em muito detalhe. Mas é muito semelhante em espírito. Eu poderia implementar uma fila, e suas operações correspondentes, enqueue ou dequeue, como adicionar ou remover, é apenas uma maneira de dizê-lo mais chique, enfileiramento ou desenfileirar, como se segue. Eu só posso me dar um struct que novamente tem matriz de um número, que de novo tem um tamanho, Mas por que eu preciso agora para manter o controle da frente de uma fila? Eu não preciso saber a frente da minha stack. Bem, se eu novamente para uma queue-- vamos duro codificá-lo como tendo como cinco inteiros em aqui potencialmente. Portanto, este é zero, um, dois, três, quatro. Este vai ser números chamados novamente. E isso vai ser chamado de tamanho. 

Por que não é suficiente ter apenas o tamanho? Bem, vamos empurrar os mesmos números por diante. Então eu pushed-- I enfileirado, ou empurrado. Agora eu vou enfileirar 50, e, em seguida, 51, e depois 61, e Dot Dot Dot. Então, isso é enqueue. I enfileirados 50, depois 51, depois 61. E isso parece idêntico para uma pilha até agora, só que eu preciso fazer uma mudança. Eu preciso atualizar esse tamanho, então eu ir de zero a um de dois a três agora. Como faço para retirar da fila? O que acontece com dequeue? Quem deve sair esta lista primeiro se é a linha na loja da Apple? Então, 50. Então é meio complicado desta vez. Considerando última vez que ele foi super fácil simplesmente fazer o tamanho menos um, Eu chegar ao final da minha matriz efetivamente onde os números são, ele remove 61. Mas eu não quero remover 61. Eu quero ter 50 anos, que estava lá na 5:00 para a linha para o novo iPhone ou outros enfeites. E assim se livrar de 50, I não pode simplesmente fazer isso, certo? Eu posso atravessar a 50. Mas nós apenas disse que não tem que ser tão anal como a riscar ou ocultar os dados. Nós podemos simplesmente esquecer onde está. 

Mas se eu mudar o meu tamanho agora dois, é esta informação suficiente para saber o que está acontecendo na minha fila? Na verdade, não. Tal como o meu tamanho é dois, mas onde é que a fila de começar, especialmente se eu ainda tenho esses mesmos números na memória. 50, 51, 61. Então, eu preciso lembrar Agora, onde a frente é. E assim como eu propus-se lá, nós vamos ter chamado apenas Frente Nth, cuja inicial valor deve ter sido o que? Zero, apenas o começo da lista. Mas agora, além de decrementing o tamanho, nós apenas incrementar a frente. Ora aqui está um outro problema. Então, quando eu continuo indo. Suponhamos que este é o número de como 121, 124, e, em seguida, caramba, Estou fora do espaço. Mas espere um minuto, eu não sou. Então, neste ponto da história, suponhamos que o tamanho é um, dois, três, quatro, de modo que o supor tamanho é quatro, a frente é um, de modo 51 é a parte da frente. Eu quero colocar outro número aqui, mas, caramba, eu estou fora do espaço. Mas eu não sou realmente, certo? Onde eu poderia colocar algum valor adicional, como 171? Sim, eu poderia apenas uma espécie de voltar para lá, certo? E, em seguida, atravessar a 50, ou apenas substituí-lo com 171. E se você está se perguntando por nossos números ficou tão aleatório, estes são normalmente tomadas computador cursos de ciências em Harvard após CS50. Mas isso foi uma boa otimização, porque agora eu não estou desperdiçando espaço. Eu ainda tenho que lembrar quão grande essa coisa é total. É cinco totais. Porque eu não quero começar a substituir 51. Então agora eu ainda estou sem espaço, de modo que o mesmo problema de antes. Mas você pode ver como agora em seu código, você provavelmente tem que escrever um pouco mais complexidade para que isso aconteça. E, de fato, o operador em C provavelmente permite você magicamente fazer isso a circularidade? Sim, o operador módulo, o sinal de porcentagem. Então, o que é legal sobre uma fila, embora nós manter matrizes desenho como essas linhas retas como, se você tipo de pensar sobre isso como encurvamento em torno de como um círculo, em seguida, basta intuitivamente que tipo de obras mentalmente Eu acho que um pouco mais limpa. Você ainda teria que implementar que modelo mental no código. Então, não é difícil, em última análise, para implementar, mas ainda perder o size-- vez, o capacidade de redimensionar, a menos que façamos isso. 

Temos de livrar-se da matriz, nós substituí-lo por um único ponteiro, e, em seguida, em algum lugar no meu código que eu tenho a chamar o que funcionar para realmente criar a matriz de números chamados? Malloc, ou alguma semelhante função, exatamente. Quaisquer perguntas sobre pilhas ou filas. Sim? Boa pergunta. Qual módulo você usaria aqui. Assim, em geral, quando se utiliza mod, você faria isso com o tamanho do estrutura inteira de dados. Então, algo como cinco ou capacidade, se é constante, está provavelmente envolvido. Mas apenas fazendo modulo cinco provavelmente não é suficiente, porque nós precisamos saber é que nós envolver em torno de aqui ou aqui ou aqui. Então você provavelmente está também vai querer envolver o tamanho da coisa, ou a variável frente também. Então é só isso relativamente expressão aritmética simples, mas módulo seria o ingrediente chave. 

Então, curta-metragem se você quiser. Uma animação que alguns povos em outra universidade juntos que nós temos adaptado para esta discussão. Trata-se de aprender a Jack fatos sobre filas e estatísticas. 

FILME: Era uma vez, havia um cara chamado Jack. Quando ele veio para fazer amigos, Jack não tem um talento especial. Então Jack foi conversar com o mais cara popular que ele conhecia. Ele foi para Lou e perguntou: O que eu faço? Lou viu que seu amigo foi muito angustiado. Bem, ele começou, apenas olha como você está vestida. Você não tem nenhuma roupa com um olhar diferente? Sim, disse Jack. Eu com certeza faço. Venha à minha casa e Eu vou mostrar a você. Então, eles foram para Jack. Jack e Lou mostrou a caixa onde guardava todas as suas camisas, e as calças e as meias. Lou disse, eu vejo que você tem todas as suas roupas em uma pilha. Por que você não usar algum outros de vez em quando? 

Jack disse, bem, quando eu remover roupas e meias, Eu lavá-los e colocá- -los na caixa. Em seguida, vem o próximo manhã, e se eu pulo. Eu ir para a caixa e obter minhas roupas fora do topo. Lou percebeu rapidamente O problema com Jack. Ele manteve roupas, CDs, e livros na pilha. Quando chegou para algo para ler ou para vestir, ele escolheria o topo livro ou roupa interior. Então, quando ele foi feito, ele iria colocá-lo de volta. Voltar seria ir, no topo da pilha. Eu sei a solução, disse um alto triunfante. Você precisa aprender a começar a usar uma fila. Lou pegou roupas de Jack e pendurou-os no armário. E quando ele tinha esvaziado a caixa, ele simplesmente jogou-a. 

Então ele disse, agora Jack, no final de o dia, colocar suas roupas no lado esquerdo quando você colocá-los fora. Então, amanhã de manhã quando você ver a luz do sol, pegar suas roupas à direita, a partir da extremidade da linha. Você não vê? disse Lou. Ele vai ser tão bom. Você vai usar tudo uma vez antes de usar algo duas vezes. E com tudo em filas em seu armário e prateleira, Jack começou a se sentir muito seguro de si. Tudo graças a Lou e sua maravilhosa fila. COLUNA 1: Tudo bem, é adorável. Então, o que foi realmente acontecendo por baixo do capuz agora? Que temos ponteiros, que temos malloc, que temos a capacidade de criar pedaços de memória para nós mesmos dinamicamente. Portanto, esta é uma imagem que vislumbrada apenas no outro dia. Nós realmente não habitará sobre ele, mas esta imagem tem sido acontecendo por baixo o capô há semanas. E assim isso representa, apenas um retângulo que temos desenhado, a memória do seu computador. E talvez o seu computador, ou CS50 ID, tem um gigabyte de memória RAM ou ou dois gigabytes ou quatro. Realmente não importa. Seu sistema operacional Windows ou Mac OS ou Linux, essencialmente permite que o programa a pensar que ele tem acesso para a totalidade do a memória do seu computador, mesmo que você pode estar executando vários programas ao mesmo tempo. Então, na realidade, que realmente não funciona. Mas é tipo de uma ilusão dado a todos os seus programas. Então se você tivesse dois gigas de RAM, este É assim que o computador pode pensar nisso. 

Agora coincidentemente, um deles coisas, um desses segmentos de memória, é chamado uma pilha. E, de fato qualquer momento até agora em escrever código que você tem chamado a função, por exemplo principal. Lembre-se que a qualquer momento eu tenho memória tirada do computador, Eu sempre desenhar tipo de metade de um retângulo aqui e não se incomode de falar sobre o que está acima. Porque quando principal é chamado, eu reivindico que você começa este pedaço de memória que vai para baixo aqui. E se uma função principal chamada como swap, bem troca vai aqui. E ao que parece, isso é onde ele está terminando. Em algo chamado uma pilha dentro da memória do seu computador. Agora, no final do dia, este é apenas aborda. É como byte zero, byte um, byte 2 bilhões. Mas se você pensar sobre isso como este objecto rectangular, tudo o que estamos fazendo a cada vez que chamar uma função é estratificação uma nova fatia de memória. Estamos dando essa função uma fatia da sua própria memória para trabalhar. 

E lembro agora que isso é importante. Porque se nós temos algo como troca e duas variáveis ​​locais como A e B e podemos mudar esses valores a partir de um e dois para dois e um, lembre- que quando retorna permuta, é como se essa fatia de memória é apenas ido. Na realidade, ainda é há forense. E algo ainda está realmente lá. Mas conceitualmente, é como embora é completamente desaparecido. E assim principal não sabe qualquer um dos trabalhos que foi feito nessa função swap, a menos que seja realmente passou naqueles argumentos de ponteiro ou por referência. Agora, a solução fundamental para esse problema com permuta está passando por coisas no endereço. Mas ao que parece, também, o que é vem acontecendo acima que parte do retângulo de todo esse tempo é Ainda há mais memória lá em cima. E quando você dinamicamente alocar a memória, se é dentro de GetString, que temos vindo a fazer para você no CS50 biblioteca, ou se vocês chamar malloc e pedir o sistema operacional para um pedaço de memória, ele não vem da pilha. Ele vem de outro lugar na memória do seu computador que é chamado de heap. E isso não é diferente. É a mesma RAM. É a mesma memória. É apenas a memória RAM que está acima lá em vez de descer aqui. 

E então o que é que isso significa? Bem, se o computador tiver uma quantidade finita de memória ea pilha está crescendo, então para falar, ea pilha, de acordo para esta seta, está crescendo para baixo. Em outras palavras, cada vez que você chamar malloc, você está sendo dada uma fatia de memória a partir de cima, em seguida, talvez um pouco mais baixo, então um pouco inferior, cada vez que você chamar malloc, a pilha, é o uso, é uma espécie de crescimento, crescendo cada vez mais perto para o que? A pilha. Então, isso parece ser uma boa idéia? Quero dizer, onde não é muito claro o que mais você pode fazer se você só tem uma quantidade finita de memória. Mas este é certamente ruim. Essas duas setas estão em um Crash Course um pelo outro. 

E verifica-se que cara mau, pessoas que são particularmente bons com a programação, e tentando invadir computadores, pode explorar essa realidade. Na verdade, vamos considerar um pequeno trecho. Portanto, este é um exemplo que você pode ler com mais detalhes na Wikipedia. Nós vamos apontá-lo no artigo se curioso. Mas há um ataque geral conhecido como buffer overflow que tem existido durante o tempo que os seres humanos ter tido a capacidade de manipular a memória do computador, especialmente em C. Portanto, este é um programa muito arbitrária, mas vamos lê-lo de baixo para cima. Principal em ARGC carvão estrela argv. Portanto, é um programa que tira argumentos de linha de comando. E tudo principal é que, aparentemente, é chamada uma função, chamá-lo de F pela simplicidade. E ele passa em quê? ArGV de um. Então, ele passa para o que quer que F a palavra é que o usuário digitou no prompt após a nome do programa em tudo. Tanto como César ou Vigenere, que você pode se lembrar fazendo com argv. 

Então, o que é F? F leva em uma string como seu único argumento, AKA uma estrela char, mesmo coisa, como uma string. E ele é chamado arbitrariamente bar no presente exemplo. E depois de char c 12, apenas em termos leigos, o que é char c suporte de 12 fazendo por nós? O que ele faz? A alocação de memória, especificamente 12 bytes para 12 caracteres. Exatamente. E então a última linha, mexa e cópia, você provavelmente não vi. Esta é uma cópia cadeia função cujo propósito na vida é copiar seu segundo argumento em seu primeiro argumento, mas apenas até um certo número de bytes. Assim, o terceiro argumento diz, quantos bytes você deve copiar? O comprimento da barra, tudo o que o usuário digitou. E os conteúdos de Bar, essa seqüência, são copiada para a memória apontada para a C. 

Então, isso parece meio idiota, e é. É um exemplo artificial, mas é representante de uma classe de vectores de ataque, uma forma de atacar um programa. Tudo está bem e bom se o usuário tipos em uma palavra que é 11 caracteres ou menos, mais a barra invertida zero. E se o usuário digita em mais de 11 ou 12 ou 20 ou 50 caracteres? O que é este programa vai fazer? Falha potencialmente seg. Vai para copiar cegamente tudo no bar-se ao seu comprimento, que é literalmente tudo no bar, para o endereço apontado pelo C. Mas C só preventivamente dada como 12 bytes. Mas não há nenhuma verificação adicional. Não há nenhum caso as condições. Não há nenhuma verificação de erros aqui. 

E então o que este programa é vai fazer é apenas cega copiar uma coisa à outra. E assim se desenhar esse como uma imagem, é aqui apenas uma pequena parte do espaço de memória. Então, observe na parte inferior, nós têm o bar variável local. Então, esse ponteiro que vai store-- vez que o argumento local que é indo para armazenar a barra de string. Em seguida, observe apenas acima dela numa pilha, porque cada vez que você perguntar para memória na pilha, ele vai um pouco acima, pictorially, aviso de que temos 12 bytes lá. A de cima esquerda é zero e suporte C o certo é inferior C suporte 11. Isso é apenas a forma como os computadores indo para colocá-lo fora. Então, só intuitivamente, se bar tem mais de 12 caracteres no total, incluindo a barra invertida zero, onde está o 12 ou o suporte de C 12 indo para ir? Ou melhor, onde é o 12º personagem ou o personagem 13th, o personagem vai centésimo para acabar na foto? Acima ou abaixo? 

Certo, porque embora a própria pilha cresce para cima, uma vez que você colocar as coisas em ele, por razões de concepção, coloca a memória de cima para baixo. Então, se você tem mais de 12 bytes, você vai começar a substituir bar. Agora que é um erro, mas é não é realmente um grande negócio. Mas é um grande negócio, porque há mais coisas acontecendo na memória. Então aqui está como nós pudemos colocar Olá, para ser claro. Se eu digitei Olá no prompt. Barra invertida zero, H-E-L-L-O, acaba por dentro esses 12 bytes, e estamos super seguro. Tudo está bem. Mas se eu digitar algo mais longo, que é potencialmente vai rastejar para o espaço bar. Mas, pior ainda, verifica-se fora todo esse tempo, embora nós nunca conversamos sobre que, a pilha é usada para outras coisas. Não são apenas as variáveis ​​locais. 

C é uma linguagem de nível muito baixo. E que tipo de segredo utiliza também a pilha para recordar quando um função é chamada, o que é o endereço da função anterior, assim que pode saltar de volta para essa função. Então, quando as chamadas principais trocar, entre as coisas empurrado para a pilha não são apenas troca variáveis ​​locais, ou seus argumentos, também empurrou secretamente para a pilha como representado pela fatia vermelho aqui, é o endereço do principal fisicamente na memória do seu computador, de modo que quando é feito de permuta, o computador sabe que eu preciso para voltar ao principal e terminar de executar a função principal. Então, isso é perigoso agora, porque se o usuário digita bem mais do que Olá, de tal modo que a entrada do usuário clobbers ou substitui essa seção vermelho, logicamente, se do computador só vai assumir cegamente em que os bytes que são fatia vermelho o endereço para o qual ele deve retornar, e se o adversário é inteligente o suficiente ou sorte o suficiente para colocar uma seqüência de bytes há que se parece com um endereço, mas é o endereço de código que ele ou ela quer o computador para executar em vez de principal? 

Em outras palavras, se o que o usuário está digitando no prompt, não é apenas algo como inócuo Olá, mas na verdade é um código que é equivalente apagar todos os arquivos desse usuário? Ou enviar e-mail a senha para mim? Ou começar a registrar sua teclas digitadas, certo? Há um caminho, vamos estipular hoje, que eles poderiam escrever não apenas Olá mundo ou seu nome, que podiam essencialmente passar em código, e zeros aqueles, que o computador erros de código e um endereço. Assim, embora um pouco abstrata, se o usuário digita o código contraditório suficiente que vamos generalizar aqui como A. Uma é o ataque ou adversários. Então, só coisas ruins. Nós não nos importamos sobre a números ou os zeros ou aqueles hoje, de tal forma que você acaba sobrescrevendo essa seção vermelho, notar que seqüência de bytes. O 835 C de zero oito zero. E agora, como artigo de Wikipedia aqui propôs, se você realmente começar agora rotular os bytes em seu computador de memória, o que o artigo é Wikipedia propondo é que, o que se o endereço de que byte superior esquerdo é de 80 C 0 3508. 

Em outras palavras, se o cara é ruim inteligente o suficiente com o seu código para realmente colocar um número aqui que corresponde ao endereço do código ele ou ela injectado no computador, você pode enganar o computador a fazer qualquer coisa. A remoção de arquivos, e-mail coisas, farejando o seu tráfego, literalmente qualquer coisa poderia ser injectado no computador. E assim por um estouro de buffer ataque em seu núcleo é apenas um estúpido, estúpido imperiosa de uma matriz que não têm seus limites marcada. E é isso que é super perigoso e ao mesmo tempo poderoso super em C é que nós realmente têm acesso a qualquer lugar da memória. Cabe a nós, os programadores, que escrevem o código original para verificar o comprimento danado de qualquer matrizes que nós estamos manipulando. Então, para ser claro, o que é a correção? Se reverter para esta código, eu não deveria apenas alterar o comprimento da barra, o que mais eu deveria estar verificando? O que mais eu deveria estar fazendo para evitar este ataque inteiramente? Eu não quero dizer apenas cega que você deve copiar como muitos bytes como é o comprimento da barra. Eu quero dizer, como copiar muitos bytes como estão em bar até o alocado memória, ou 12 no máximo. Então eu preciso de algum tipo de condição if que faz verificar o comprimento da barra, mas se for superior a 12, nós código apenas difícil 12 como a distância máxima possível. Caso contrário, o chamado tampão ataque de estouro pode acontecer. Na parte inferior das referidas lâminas, Se você está curioso para ler mais é o artigo original real se você gostaria de dar uma olhada. 

Mas agora, entre os preços pago aqui foi ineficiências. Então isso foi um rápido olhar baixo nível em que podem surgir problemas agora que nós têm acesso a memória do computador. Mas um outro problema que já tropeçou nesta segunda-feira era apenas a ineficiência de uma lista ligada. Estamos de volta ao tempo linear. Nós já não temos uma matriz contígua. Não temos acesso aleatório. Nós não podemos usar a notação de colchete. Nós, literalmente, tem que usar um loop while como a que eu escrevi há pouco. Mas na segunda-feira, que alegou que pudermos rastejar de volta para o reino da eficiência alcançar algo que é logarítmica talvez, ou melhor ainda, talvez até mesmo algo que é o chamado tempo constante. Então, como podemos fazer isso usando estes novos ferramentas, esses endereços, esses ponteiros, e enfiar coisas da nossa própria? Bem, suponha que aqui, estes são um bando de números que queremos armazenar em um estrutura de dados de forma eficiente e de busca. Podemos absolutamente rebobinar a semana dois, jogá-los em uma matriz, e pesquisá-los usando pesquisa binária. Dividir e conquistar. E, de fato você escreveu busca binária em PSET3, onde você implementou o programa find. Mas você sabe o quê. Há uma espécie de mais maneira inteligente de fazer isso. É um pouco mais sofisticado e talvez permite-nos ver porque binário busca é muito mais rápido. Primeiro, vamos introduzir a noção de uma árvore. Que, embora em realidade tipo de árvores crescer como este, no mundo de computador ciência que tipo de crescer para baixo como uma árvore de família, onde você tem seus avós ou bisavós ou outros enfeites no topo, o patriarca e a matriarca da família, apenas um chamada raiz, nó, abaixo que são as suas crianças, abaixo da qual estão os seus filhos, ou seus descendentes em geral. E qualquer um que pendura fora a parte inferior da família árvore, além de ser a caçula da família, também pode ser apenas genericamente chamado as folhas da árvore. 

Portanto, este é apenas um bando de palavras e definições para algo chamado de uma árvore no computador ciência, bem como uma árvore genealógica. Mas há encarnações mais extravagantes de árvores, uma das quais é chamada uma árvore de busca binária. E você pode tipo de provocação além o que essa coisa faz. Bem, é binário em que sentido? Onde é que o binário vem daqui? Desculpa? Não é tanto um ou. É mais que cada um de nós não tem mais de dois filhos, como podemos ver aqui. Em geral, um e tree-- seus pais e avós pode ter tantos filhos ou netos como eles realmente querem, e assim, por exemplo, aí temos três crianças fora desse nó mão direita, mas de uma árvore binária, um nó possui zero, um ou dois filhos maximamente. E isso é uma propriedade agradável, Porque se é tampado por dois, nós vamos ser capazes de ficar um pouco log base dois ação acontecendo aqui, em última instância. Portanto, temos algo logarítmica. Mas mais sobre isso em um momento. Pesquisa árvore significa que os números são disposto de tal modo que a criança esquerda do valor é maior do que a raiz. E seu filho direito é maior do que a raiz. Em outras palavras, se você pegar qualquer um dos nós, os círculos nesta imagem, e olha para sua esquerda criança e seu filho direito, o primeiro deve ser inferior a, o segundo deve ser maior do que. Então verificação de sanidade 55. É criança deixada é de 33. É menos do que. 55, seu filho da direita é de 77. É maior que. E isso é uma definição recursiva. Poderíamos verificar cada um desses nós e o mesmo padrão iria realizar. 

Então, o que é bom em um árvore de busca binária, é esse, podemos implementá-lo com uma estrutura, tal como este. E mesmo que nós estamos jogando lotes de estruturas na sua, eles são um pouco intuitiva agora esperançoso. A sintaxe é ainda misterioso, com certeza, mas o conteúdo de um nó nesta context-- e continuamos utilizando o nó palavra, se é um retângulo na tela ou um círculo, é apenas alguns contêiner genérico, Neste caso de uma árvore, como o vimos, precisamos de um número inteiro em cada um dos nós e então eu preciso de dois ponteiros apontando para o filho esquerdo e direito da criança, respectivamente. Então é assim que nós pudemos implementar isso em um struct. E como eu poderia implementá-lo em código? Bem, vamos dar uma rápida olhar para este pequeno exemplo. Não é funcional, mas eu tenho copiado e colado essa estrutura. E se a minha função para um binário árvore de busca é chamado de busca, e isso leva dois argumentos, um N de número inteiro e um ponteiro para um nó, de modo que um ponteiro para a árvore ou um ponteiro para a raiz de uma árvore, como faço para ir sobre como procurar N? Bem, em primeiro lugar, porque eu sou lidar com ponteiros, Eu vou fazer um teste de sanidade. Se iguais árvore é igual a zero, é N nesta árvore ou não nesta árvore? Não pode ser, certo? Se eu sou passado null, não há nada lá. Eu poderia muito bem apenas cegamente dizer return false. Se você me der nada, eu certamente não posso encontrar qualquer número N. Então, o que mais eu poderia verifique agora? Eu vou dizer bem else if N é menos do que o que está no nó de árvore que eu tenho valor N entregou. Em outras palavras, se o número eu sou procurando, n, for menor do que o nó que eu estou olhando. E o nó que estou procurando a árvore é chamado, e lembrar do exemplo anterior para obter o valor em um ponteiro, Eu uso a notação de seta. Portanto, se N é inferior a seta árvore N, eu quero ir conceitualmente esquerda. Como posso expressar searching esquerda? Para ser claro, se este for a imagem em questão, e eu tenho que passou de nível superior arrow que está apontando para baixo. Esse é o meu ponteiro árvore. Eu estou apontando para a raiz da árvore. E eu estou olhando por exemplo, para o número 44, de forma arbitrária. 44 é inferior ou superior a 55, obviamente,? Por isso é menos do que. E assim este se condição se aplica. Assim, conceitualmente, o que eu quero procurar seguinte se eu estou procurando 44? Sim? 

Exatamente, eu quero procurar o filho esquerdo, ou a sub-árvore à esquerda da imagem. E, na verdade, deixe-me através de a foto aqui por apenas um momento, uma vez que Eu não posso arranhar isso. Se eu começar aqui em 55, e Eu sei que o valor 44 Eu estou procurando é a à esquerda, é uma espécie de como rasgar o livro de telefone em metade ou rasgar a árvore no meio. Eu já não precisa se preocupar com toda esta metade da árvore. E, no entanto, curiosamente, em termos de estrutura, esta coisa aqui que inicia-se com 33, que se é uma árvore de busca binária. Eu disse a palavra recursiva antes porque Na verdade, esta é uma estrutura de dados que por definição é recursiva. Você pode ter uma árvore que é isso grande, mas cada um de seus filhos representa uma árvore apenas um pouco menor. Ao invés de ser vovô ou a avó, agora é só mãe ou-- Eu não posso não dizer-- mãe ou pai, que seria estranho. Em vez das duas crianças lá seria como irmão e irmã. A nova geração da árvore genealógica. Mas estruturalmente, é a mesma idéia. E acontece que eu tenho uma função com o qual eu posso procurar uma pesquisa binária árvore. Ele é chamado de busca. I procurar N na árvore seta para a esquerda outro se n for maior do que o valor que eu sou atualmente. 55 na história um momento atrás. Eu tenho uma função chamada pesquisa que eu posso apenas N passar isso e procurar de forma recursiva a sub-árvore e apenas retorno qualquer que seja a resposta. Outra coisa que eu tenho algum caso base final aqui. 

O que é o caso final? Árvore ou é nulo. O valor que eu tanto estou procurando é menos do que ou maior do que aquela ou igual ao mesmo. E eu poderia dizer igual igual, mas logicamente é equivalente a apenas dizendo outra coisa aqui. Tanto é verdade como eu encontrar alguma coisa. Portanto, esperamos que esta é uma mesmo exemplo mais atraente do que a função sigma estúpido fizemos algumas palestras para trás, onde era tão fácil de usar um loop para contar todos os números de um a N. aqui com uma estrutura de dados que em si é recursivamente definido e de forma recursiva desenhada, agora nós têm a capacidade de nos expressarmos no código que em si é recursiva. Portanto, este é exatamente o mesmo código aqui. 

Então, o que os outros problemas que podemos resolver? Então, um passo rápido longe de árvores para apenas um momento. Aqui é, digamos, a bandeira alemã. E há claramente um padrão para esta bandeira. E há muita bandeiras do mundo que são tão simples como isso em termos das suas cores e padrões. Mas suponhamos que esta é armazenada como um .GIF, Ou um JPEG ou bitmap, ou um ping, qualquer formato de arquivo gráfico com o qual você está familiarizado, alguns dos quais nós somos brincando com em PSet4. Isso não parece valer a pena para armazenar pixel preto, pixel preto, pixel preto, ponto, ponto, ponto, um monte de pixels pretos para a primeira linha de varredura, ou linha, em seguida, um grupo inteiro de a mesma, em seguida, um grupo inteiro do mesmo, e, em seguida, uma todo grupo de pixels vermelhos, pixels vermelhos, pixels vermelhos, em seguida, um todo punhado de pixels amarelo, amarelo, certo? 

Não há tal ineficiência aqui. Como é que você intuitivamente comprimir a bandeira alemã se implementá-lo como um arquivo? Como o que informação pode não incomodar o armazenamento em disco em ordem para diminuir o nosso tamanho do arquivo de como um megabyte de um kilobyte, algo menor? Onde reside a redundância aqui para ser claro? O que você poderia fazer? Sim? Exatamente. Por que não, em vez de se lembrar a cor de cada pixel danado assim como você está fazendo em PSet4 com o formato de arquivo de bitmap, por que você não apenas representar a coluna mais à esquerda de pixels, por exemplo um monte de pixels pretos, um grupo de vermelho, e um monte de amarelo, e depois é só alguma forma codificar o idéia de repetir este 100 vezes ou repetir isto 1.000 vezes? Onde é 100 ou 1000 apenas um número inteiro, para que pode começar afastado com apenas um único número em vez de centenas ou milhares pixels de adicionais. E, de fato, é assim que poderia comprimir a bandeira alemã. E Agora o que acontece com a bandeira francesa? E um pouco de algum tipo de exercício mental, que flag pode ser comprimida mais no disco? A bandeira alemão ou francês bandeira, se levarmos essa abordagem? A bandeira alemão, porque não há mais redundância horizontal. E pelo design, muitos arquivos gráfico formatos de fato trabalhar como linhas de varredura horizontalmente. Eles poderiam trabalhar verticalmente, basta humanidade anos atrás decidiu que vamos Geralmente pensamos em coisas fileira por linha em vez de coluna por coluna. Então, na verdade, se você fosse olhar para o arquivo tamanho de uma bandeira alemã e uma francesa bandeira, desde que a resolução é a mesma, a mesma largura e altura, este aqui vai ser maior, porque você tem que repetir-se três vezes. Você tem que especificar azul, repita -se, branco, repita-se, vermelho, repetir-se. Você não pode simplesmente ir tudo o caminho para a direita. E como um lado, para fazer desmarque a compressão está em toda parte, se estas são quatro quadros de uma video-- você deve se lembrar que um filme ou de vídeo é geralmente como 29 ou 30 quadros por segundo. É como um pouco flip book, onde basta ver imagem, imagem, imagem, imagem, imagem apenas super rápido assim que olha como os atores na tela estão se movendo. Aqui está uma abelha do bumble em cima de um ramo de flores. E embora possa ser uma espécie de difícil de ver à primeira vista, a única coisa que se deslocam em este filme é a abelha. 

O que é mudo sobre o armazenamento vídeo não comprimido? É uma espécie de um desperdício para armazenar vídeo como quatro imagens que quase idênticos diferem apenas na medida em que a abelha é. Você pode jogar fora mais de que as informações e lembre-se somente, por exemplo, o primeiro quadro eo último quadro, quadros-chave se você já ouviu a palavra, e apenas armazenar no meio, onde a abelha é. E você não tem que armazenar todo o rosa, eo azul, ea valores verdes também. Portanto, esta é apenas a dizer que compressão está em toda parte. É uma técnica muitas vezes usamos ou exame para concedido nestes dias. 

Mas como você comprimir texto? Como você vai fazer sobre a compressão de texto? Bem, cada um dos personagens em Ascii é um byte, ou oito bits. E isso é meio idiota, certo? Porque você provavelmente tipo A e E e I e O e U muito mais frequentemente do que como W ou Q ou Z, dependendo do idioma em que você está escrevendo certamente. E então por que estamos usando oito bits para cada letra, incluindo a menos letras populares, certo? Por que não usar menos bits para as letras super popular, E como, as coisas que você adivinhar pela primeira vez em Wheel of Fortune, e usar mais bits para as letras menos populares? Por quê? Porque nós apenas estamos indo para usá-los com menos freqüência. 

Bem, acontece que não têm tentativas de fazer isso sido. E se você se lembra de grau escola ou colégio, código Morse. Código Morse tem pontos e traços que pode ser transmitido ao longo de um fio conforme sons ou sinais de algum tipo. Mas o código Morse é um super limpo. É uma espécie de um sistema binário em que você tem pontos ou traços. Mas se você ver, por exemplo, dois pontos. Ou se você acha que volta para o operador que vai como bip, bip, bip, beep, atingindo um pouco gatilho que transmite um sinal, se você, o destinatário, recebe dois pontos, qual a mensagem que você recebeu? Completamente arbitrária. 

EU? EU? Ou o que about-- ou eu? Talvez fosse apenas dois à direita de E? Portanto, não há esse problema de Decodificação com Morse código, por meio de que a menos que o pessoa que enviou a mensagem na verdade, faz uma pausa para que você possa classificar de ver ou ouvir as lacunas entre as letras, não é suficiente apenas para enviar um fluxo de zeros e uns, ou pontos e traços, porque não há ambigüidade. E é um único ponto, por isso, se você ver dois pontos ou ouvir dois pontos, talvez seja dois e de ou talvez seja uma I. Então, precisamos de um sistema que é um pouco mais inteligente do que isso. Então um homem chamado Huffman anos atrás veio com exatamente isso. Então, nós apenas estamos indo para tomar um rápido olhar a forma como as árvores são pertinentes a esta. Suponha que esta é uma estúpido mensagem que deseja enviar, composto por apenas A, B, C de D's e E do, mas há um monte de redundância aqui. Isso não deveria ser Inglês. Não é criptografado. É apenas uma mensagem estúpida com muita repetição. Então, se você realmente contar para fora toda a A, B de, C de, D's, e E de, aqui está a frequência. 20% do que as letras sejam Um, 45% das cartas E são de, e outros três freqüências. Contamos lá em cima manualmente e apenas fez as contas. 

Assim, verifica-se que Huffman, há algum tempo, percebi que, você sabe o que, se eu começar a construir uma árvore ou floresta de árvores, se quiserem, da seguinte forma, eu posso fazer o seguinte. Eu vou dar um nó para cada das cartas que me interessa e eu estou indo para armazenar dentro desse nó as freqüências como um ponto flutuante valor, ou você pode usá-lo uma N, também, mas vamos apenas usar um flutuador aqui. E que o algoritmo ele propôs é que você aproveitar esta floresta de nó único árvores, árvores tão super curtas, e você começar a conectar-los com novos grupos, pais novos, se você quiser. E você fazer isso escolhendo o dois menores freqüências de cada vez. Então, eu levei 10% e 10%. Eu criar um novo nó. E eu chamo o novo nó de 20%. 

Que dois nós Eu combino o próximo? É um pouco ambígua. Portanto, há alguns casos canto para considerar, mas para manter as coisas bem, Eu vou escolher 20% - Eu agora ignorar as crianças. Eu vou escolher 20% e 15% e desenhar duas novas arestas. E agora que dois nós eu logicamente combinar? Ignorar todas as crianças, todos os netos, basta olhar para as raízes agora. Que dois nós posso amarrar juntos? Ponto dois e 0,35. Então deixe-me desenhar duas novas arestas. E então eu tenho apenas um à esquerda. Então aqui está uma árvore. E foi desenhada deliberadamente olhar tipo de bonito, de notar que as arestas têm Também foi marcado zero e um. Assim, todas as bordas esquerdas são zero arbitrariamente, mas de forma consistente. Todas as bordas direitas são queridos. 

E então o que Hoffman proposta é, se você quiser representar um B, em vez de representar o número 66 como um Ascii que é oito bits inteiros, Você sabe o que, exatamente loja o padrão zero, zero, zero, zero, porque esse é o caminho da minha árvore, árvore do Sr. Huffman, para a folha a partir da raiz. Se você deseja armazenar uma E, por outro lado, não fazer enviar oito bits que representam um E. Em vez disso, enviar o padrão de bits? Uma. E o que é agradável sobre esta é que E é a letra mais popular, e você está usando o código mais curto para ele. O próximo mais popular carta parece que era A. E assim quantos bits ele propor usando para isso? Zero um. 

E porque ele é implementado como esta árvore, por enquanto deixe-me estipular há qualquer ambiguidade em Morse código, porque todo o letras que se preocupam são no final destes bordos. Então, isso é apenas um aplicação de uma árvore. Isso é-- e eu vou acenar minha mão neste como você pode implementar isso como uma estrutura C. Nós apenas precisamos de combinar um símbolo, como um char, ea freqüência em esquerda e direita. Mas vamos olhar para dois exemplos finais que você vai se bastante familiarizado com depois questionário zero no conjunto de problemas cinco. 

Portanto, há a estrutura de dados conhecida como uma tabela de hash. E uma tabela hash é uma espécie de arrefecer na medida em que tem baldes. E suponha que há quatro baldes aqui, apenas quatro espaços em branco. Aqui está um baralho de cartas, e aqui está clube, pá, clube, diamantes, clube, diamantes, clubes, diamantes, clubs-- então este é o acaso. Corações, então estou hearts-- bucketizing todas as entradas aqui. E uma tabela de hash necessidades a olhar para a sua entrada, e, em seguida, colocá-lo em um determinado colocar com base no que você vê. É um algoritmo. E eu estava usando um super- algoritmo visual simples. A parte mais difícil do que foi lembrando-se de que as imagens foram. E depois há quatro coisas totais. 

Agora, as pilhas estavam crescendo, o que é uma coisa deliberada projeto aqui. Mas o que mais eu poderia fazer? Então, na verdade, temos aqui um bando de velhos livros de exame escolar. Suponha que um grupo de nomes alunos estão aqui. Aqui está uma tabela hash maior. Em vez de quatro baldes, Tenho, digamos 26. E nós não queremos ir pedir emprestado 26 coisas de fora [? Annenberg?], Assim aqui está cinco que representam A a Z. E se eu ver um aluno cujo nome começa com A, Eu vou colocar o seu questionário lá. Se alguém começa com C, até lá, A--, na verdade, não queria fazer isso. B passa por aqui. Então eu tenho A e B e C. E Agora, aqui está outro estudante A. Mas, se esta tabela hash é implementado com uma matriz, Eu sou do tipo aparafusado neste momento, certo? Eu meio que precisa colocar isso em algum lugar. 

Assim, uma maneira que eu posso resolver isto é, todos direito, A é ocupado, B estiver ocupado, C está ocupado. Vou colocá-lo em D. Então, em primeiro lugar, eu tenho acesso instantâneo aleatório para cada um dos baldes para os alunos. Mas agora é uma espécie de delegada em algo linear, porque se eu quiser procurar alguém cujo nome começa com A, eu verifico aqui. Mas, se esta não é a um estudante que eu estou procurando, Eu meio que tenho que começar a verificar os baldes, porque o que eu fiz era uma espécie de linearmente sondar a estrutura de dados. Um jeito estúpido de dizer basta olhar para a primeira abertura disponível, e colocar como um plano B, por assim dizer, ou plano D neste caso, o valor nesse local. Este é apenas para que se você tiver tem 26 locais e nenhum aluno com o nome Q ou Z, ou algo parecido que, pelo menos você está usando o espaço. 

Mas já vimos mais soluções inteligentes aqui, certo? O que você faria em vez se você tiver uma colisão? Se duas pessoas têm o nome A, o que seria ter sido um mais esperto ou solução intuitiva do que apenas colocando um D, onde é suposto ser? Por que não posso simplesmente ir lado de fora [? Annenberg?], como malloc, outro nó, coloque- aqui, e em seguida, colocar que um estudante aqui. Assim que eu tiver essencialmente algum tipo de uma matriz, ou talvez mais elegantemente como estamos começando a ver uma lista ligada. 

E assim uma tabela hash é uma estrutura que poderia olhar apenas como este, mas mais inteligente, você algo chamado encadeamento separado, em que uma tabela hash muito simplesmente é uma matriz, cada um dos cujos elementos não é um número, é em si uma lista ligada. Para que você tenha acesso super rápido decidir onde botar o seu valor para. Muito parecido com o exemplo cartões, Eu fiz decisões super rápido. Corações vai aqui, diamantes vai aqui. Mesmo aqui, A vai aqui, D vai aqui, B vai aqui. Então super rápido look-ups, e se acontecer de você correr em um caso colisões, onde você tem dois, pessoas com o mesmo nome, bem, então você acabou de começar ligando-os juntos. E talvez você mantê-los classificadas em ordem alfabética, talvez você não. Mas pelo menos agora temos o dinamismo. Assim, por um lado, temos super rápido constante de tempo e tipo de tempo linear envolvidos se essas listas ligadas começam a ficar um pouco longo. 

Portanto, este tipo de um bobo, gracejo geeky anos atrás. No CS50 Hack-a-thon, quando os alunos check-in, alguns TF ou CA a cada ano acha que é engraçado para colocar-se um sinal como este, onde ele só significa que se seu nome começa com um A, ir por este caminho. Se seu nome começa com um B, ir isto-- OK, é engraçado talvez mais tarde no semestre. Mas há outra maneira de fazer isso também. Vamos voltar a isso. 

Portanto, há essa estrutura. E esta é a nossa última estrutura para hoje, que é algo chamado trie. T-R-I-E, que, por algum motivo é curto para recuperação, mas ele é chamado trie. Assim, um outro interessante é trie amálgama de muitas dessas idéias. É uma árvore, o que temos visto antes. Não é uma árvore de busca binária. É uma árvore com qualquer número de filhos, mas cada uma das crianças em um trie é uma matriz. Uma matriz de tamanho, dizem, 26 ou talvez 27 se você quiser apoiar hifenizado nomes ou apóstrofos em nomes de pessoas. 

E por isso esta é uma estrutura de dados. E se você olhar de cima para baixo, como se você olhar para o nó superior lá, M, é apontando para a coisa mais à esquerda lá, que é, em seguida, A, X, W, E, L, L. Isto é apenas uma estrutura de dados que arbitrariamente é o armazenamento de nomes de pessoas. E Maxwell é armazenado por apenas seguindo um caminho de matriz para matriz para matriz. Mas o que é surpreendente sobre um trie é que, ao passo que uma lista ligada e até mesmo uma matriz, o melhor que eu já cheguei é tempo linear ou logarítmica tempo à procura alguém. Nesta estrutura de dados de um trie, se minha estrutura de dados tem um nome nele e eu estou procurando Maxwell, eu sou vai encontrá-lo muito rapidamente. Acabei de olhar para M-A-X-W-E-L-L. E se esta estrutura de dados, em contraste, Se N é um milhão, se há uma milhão de nomes nesta estrutura de dados, Maxwell ainda vai ser detectável depois de apenas M-A-X-W-E-L-L degraus. E passos David-- D-A-V-I-D. Em outras palavras, através da construção de uma estrutura de dados que é tem todas essas matrizes, todos os quais se sustentar de acesso aleatório, Eu posso começar a olhar para cima de pessoas nome usando uma quantidade de tempo que é proporcional à não o número de coisas na estrutura de dados, como um milhão de nomes existentes. A quantidade de tempo que leva-me a encontrar H-A-X-W-E-G-G na estrutura de dados é este não proporcional ao o tamanho da estrutura de dados, mas com o comprimento do nome. E realisticamente a nomes que nós estamos olhando para cima nunca vai ser louco por muito tempo. Talvez alguém tem um caráter 10 nomear, 20 nome do personagem. É certamente finito, certo? Não é um ser humano em que a Terra tem o nome mais longo possível, mas esse nome é uma constante comprimento valor, certo? Ele não varia em qualquer sentido. Assim, deste modo, nós temos conseguida uma estrutura de dados que é tempo constante look-up. Ele faz ter um número de passos dependendo do comprimento da entrada, mas não o número de nome na estrutura de dados. Então, se nós dobrar o número de nomes no próximo ano de um bilhão a dois bilhões, constatação Maxwell vai levar o mesmo número de sete passos para encontrá-lo. E, assim, parecem ter conseguido nosso Santo Graal do tempo de execução. 

Assim, um par de anúncios rápidos. Questionário de zero está chegando. Mais sobre isso no site do curso durante o próximo par de dias. Segunda-feira de lecture-- É um feriado aqui em Harvard na segunda-feira. Não é em New Haven, assim que nós estamos tomando a classe a New Haven para palestra na segunda-feira. Tudo será filmado e transmitido ao vivo, como de costume, mas vamos terminar hoje com um segundo clipe 30 chamados de "Pensamentos Profundos" Daven por Farnham, que foi inspirado no ano passado até sábado "Pensamentos Profundos" de Night Live por Jack Handy, que agora deve fazer sentido. 

FILME: E agora, "Deep Pensamentos "por Daven Farnham. Mesa de confecção. 

COLUNA 1: Tudo bem, isso é tudo por agora. Vamos vê-lo na próxima semana. 

DOUG: Para vê-lo em ação. Então, vamos dar uma olhada nisso agora. Então, aqui, temos um conjunto indiferenciado. 

IAN: Doug, você pode ir em frente e reinício isso por apenas um segundo, por favor. Tudo bem, as câmeras estão rolando, então ação sempre que você estiver pronto, Doug, OK? DOUG: Tudo bem, então o que nós temos aqui é um conjunto indiferenciado. E eu tenho colorido todos os elementos vermelho para indicar que ele é, na verdade, indiferenciados. Então recordar que a primeira coisa que fazemos é que classificar a metade esquerda da matriz. Em seguida, classificar a direita metade da matriz. E ya-da, ya-da, ya-da, que fundi-las. E nós temos uma matriz completamente ordenada. Então é assim que funciona merge sort. 

IAN: Ei, ei, ei, corta, corta, corta, corta. Doug, você não pode apenas ya-da, ya-da, ya-da, o seu caminho através merge sort. 

DOUG: Eu apenas fiz. Está bem. Nós somos bons de ir. Vamos apenas continuar jogando. Então, de qualquer maneira, 

IAN: Você tem que explicar Ele mais plenamente do que isso. Isso não é apenas o suficiente. DOUG: Ian, nós não precisamos voltar a um. Está bem. De qualquer forma, se continuarmos com merge-- Ian, nós estamos no meio das filmagens. 

IAN: Eu sei. E nós não podemos apenas ya-da, ya-da, ya-da, através de todo o processo. Você tem que explicar como o dois lados se fundiram juntos. 

DOUG: Mas nós já explicou como os dois sides-- 

IAN: Você acabou mostrado -lhes uma variedade de mesclagem. DOUG: Eles sabem o processo. Eles estão bem. Temos ido sobre ele dez vezes. 

IAN: Você acabou de pular direito sobre ele. Vamos voltar para um, você você não pode ya-da, ya-da sobre ele. Tudo bem, de volta a um. 

DOUG: Eu tenho que voltar através de todos os slides? Meu Deus. É como o sexto tempo, Ian. Está bem. 

IAN: Tudo bem. Esta pronto? Ótimo. Açao.