[Música tocando] ANDI Peng: Bem-vindo à semana 6 da seção. Nós desviado o nosso padrão tempo seção desta terça-feira tarde para esta linda manhã de domingo. Obrigado por todos que se juntou a mim hoje, mas a sério, uma salva de palmas. Isso é um bem grande esforço. Eu quase não mesmo fazê-lo -se no tempo, mas foi OK. Então eu sei que todos vocês que acaba de fazer-lo para o quiz. Primeiro de tudo, bem-vindo ao o outro lado disso. Em segundo lugar, vamos falar sobre isso. Vamos falar sobre o quiz. Vamos falar sobre como você está fazendo na classe. Você vai ficar bem. Tenho seus testes para você no final de aqui, por isso, se vocês querem tomar um olhar para ele, totalmente bem. Então, rapidamente, antes de começar, o agenda para hoje é o seguinte. Como você pode ver, estamos queima basicamente rápida através de um monte de estruturas de dados realmente, realmente, realmente rapidamente. Assim, como tal, não será hoje de super interativo. Vai ser apenas me espécie de gritar coisas que você, e se eu confundi-lo, se eu estiver indo rápido demais, deixe-me saber. Eles são apenas diferentes dados estruturas, e como parte do seu pset para este próxima semana, você vai ser solicitado para implementar um deles, talvez duas eles-- dois deles em sua pset. OK, então eu estou indo só para começar com alguns anúncios. Nós vamos passar por cima de pilhas e filas mais em profundidade do que o que fizemos antes do quiz. Nós vamos passar por cima ligado lista novamente, mais uma vez, mais em profundidade do que o que tivemos antes do quiz. E então nós vamos falar sobre haxixe mesas, árvores e tentativas, que são todos muito necessário para o seu pset. E então nós vamos passar por cima de alguns dicas úteis para pset5. OK, então questionário 0. A média era de 58%. Ele foi muito baixa, e assim vocês todos fez muito, muito bem, de acordo com aquilo. Muito bonito, regra de ouro é se você estiver dentro de um desvio padrão da média especialmente uma vez que estamos em um a menos seção de conforto, você está totalmente bem. Você está no caminho certo. A vida é boa. Eu sei que é assustador pensar que Eu tenho como um 40% neste quiz. Vou deixar esta classe. Eu prometo a você, você não está vai falhar a classe. Você está totalmente bem. Para aqueles de vocês que tenho mais a média, impressionante, impressionante, como, a sério bem feito. Eu tê-los comigo. Sinta-se livre para vir buscá-los no final da seção. Deixe-me saber se você tem qualquer questões, perguntas com eles. Se somarmos a sua pontuação errado, deixe-nos saber. OK, então pset5, este é realmente um semana estranho para Yale no sentido que a nossa pset é devido Quarta-feira ao meio-dia, incluindo o dia de atraso, por isso é, na verdade, teoricamente devido terça-feira ao meio-dia. Provavelmente ninguém terminou em terça-feira ao meio-dia. Isso é totalmente bom. Nós vamos ter o horário de expediente hoje à noite, bem como na noite de ontem. E todas as seções desta semana vai na verdade, ser transformado em oficinas, tão à vontade para pop em qualquer seção que você quer, e eles vão ser uma espécie de mini-pset oficinas para ajuda sobre isso. Assim, como tal, esta é a única secção onde estamos material didático. Todas as outras secções será centrado exclusivamente na ajuda para o pset. Sim? AUDIÊNCIA: Onde estão as horas de expediente? ANDI Peng: Horário de atendimento tonight-- oh, boa pergunta. Eu acho que o horário de expediente hoje à noite estão em Teal ou em Commons. Se você verificar on-line CS50 e você vai para o horário de expediente, deve haver um cronograma que diz-lhe onde todos eles são. Eu sei tanto esta noite ou amanhã é cerceta, e eu acho que nós podemos ter commons para a outra noite. Eu não tenho certeza. Boa pergunta. Verifique em CS50. Cool, qualquer dúvida sobre o cronograma para a próxima como três dias? Eu prometo a vocês como David Dito isto, este é o topo da colina. Vocês estão quase lá. Apenas três mais dias. Chegar lá, e então todos nós vamos descer. Nós vamos ter uma pausa agradável CS-free. Bem vindo de volta. Vamos mergulhar na web programação e desenvolvimento, coisas que são muito divertido comparação para alguns dos outros Série de Exercícios. E vai ser frio, e vamos ter muita diversão. Teremos mais doces. Desculpem-me por doces. Eu esqueci de doces. Era uma manhã áspera. Então vocês estão quase lá, e eu estou realmente orgulhoso de vocês. OK, então empilha. Que amava a pergunta sobre Jack e as suas vestes no teste? Ninguém? OK, tudo bem. Então, basicamente, como você pode imagem de Jack, esse cara aqui, gosta de tirar a roupa para fora do topo da pilha, e ele coloca-lo de volta para a pilha depois que ele é feito. Assim, deste modo, ele nunca parece estar ficando para a parte inferior do empilhar em sua roupa. Portanto, este tipo de descreve a estrutura de base de dados de como uma pilha é implementada. Essencialmente, pense em um pilha como qualquer pilha de objetos onde você colocar as coisas para o topo, e então você pop-los para fora do topo. Então LIFO é a sigla que gostamos para use-- Last In, First Out. E assim durar para o topo da pilha é o primeiro que sai. E assim os dois termos nós gostamos de associar com que são chamados push e pop. Quando você empurrar algo para o pilha, e você colocá-la de volta. E então eu acho que esta é uma espécie de conceito abstrato para aqueles de vocês que querem ver como um aplicação efectiva desta no mundo real. Como muitos de vocês têm escrito um ensaio talvez como uma hora antes do vencimento, e você excluiu acidentalmente um enorme pedaço dele, como acidentalmente? E então o que fazer controle que usamos para colocá-lo de volta? Control-Z, sim? Controlo-Z, de modo que a quantidade de vezes que Control-Z salvou minha vida, salvou minha bunda, cada vez que é implementado através de uma pilha. Essencialmente todas as informações que está em seu documento do Word, ele é empurrado e bateu à vontade. E assim, essencialmente, sempre que você excluir qualquer coisa, você colocá-la de volta. E então se você precisar dele novamente, você empurrá-lo, que é o Control-C faz. E função mundo tão real de estrutura de dados como simples pode ajudar com sua vida cotidiana. Assim, um struct é o caminho que nós realmente criar uma pilha. Nós digite definir struct, e, em seguida, chamamos isso de pilha na parte inferior. E dentro da pilha, temos dois parâmetros que pode, essencialmente, manipular, por isso temos de char capacidade cordas estrela. Tudo o que está a fazer é a criação de uma matriz que pode armazenar o que quiser qual podemos determinar a sua capacidade. Capacidade é a quantidade máxima de itens que podemos colocar em esta matriz. tamanho int é o contador que mantém o controle de quantos itens são atualmente na pilha. Então nós pode acompanhar, A, tanto como grande a pilha é real, e, B, quanto dessa pilha enchemos porque nós não queremos transbordar sobre o que é a nossa capacidade. Assim, por exemplo, esta linda pergunta era sobre seu quiz. Essencialmente, como vamos empurrar sobre o topo de uma pilha. Muito simples. Se você olhar para ele, vamos caminhar por este. Se [inaudível] size-- lembre-se, sempre que você deseja acessar qualquer parâmetro dentro de uma estrutura, você faz o nome do struct.parameter. Neste caso, s é o nome da nossa stack. Queremos acessar o tamanho da mesma, por isso fazemos s.size. Assim, desde que o tamanho não é igual capacidade ou desde já que é menos do que a capacidade, quer iria trabalhar aqui. Você deseja acessar o interior do seu stack, então s.strings, e você está indo para colocar esse novo número que você deseja inserir lá. Vamos apenas dizer que vamos querer inserir int n na pilha, nós poderíamos fazer s.strings, colchetes, s.size iguala n. Porque o tamanho é onde nós Estão na pilha se nós estamos indo para empurrar -lo, nós apenas acessar onde quer que o tamanho seja, o plenitude corrente da pilha, e nós empurrar o int n nele. E então nós queremos ter certeza de que também estamos incrementando tamanho do n, para que possamos manter o controle de nós temos adicionada uma coisa extra para a pilha. Agora temos um tamanho maior. Será que isso aqui faz sentido todos, logicamente como ele funciona? Era uma espécie de rápido. AUDIÊNCIA: Você pode passar por cima os s.stringss.strings [s.size] novamente? ANDI Peng: Certo, então o que faz s.size atualmente nos dar? AUDIÊNCIA: É o tamanho atual. ANDI Peng: Exatamente, por isso a índice atual que nosso tamanho é em, e por isso queremos colocar o novo inteiro que queremos inserir s.size. Isso faz sentido? Porque s.strings, tudo isso é é o nome da matriz. Tudo o que é acessando o matriz dentro da nossa estrutura, e assim, se quisermos coloque n em que o índice, podemos simplesmente acessá-lo utilizando suportes s.size. Legal. Tudo bem, pop, eu Pseudocódigo para fora para vocês, mas conceito similar. Isso faz sentido? Se o tamanho for maior que zero, então você sei que você quer tomar algo porque se o tamanho não é maior do que zero, então você tem nada na pilha. Assim, você só quer executar este código, ele só pode pop se há algo a estalar. Assim, se o tamanho é maior do que 0, que menos o tamanho. Nós diminuir o tamanho e, em seguida, retornar o que está dentro dela, porque estalando, queremos acesso tudo o que está armazenado no índice do topo da pilha. Tudo faz sentido? Se eu fiz vocês escrever isto, se vocês ser capaz de escrevê-lo? OK, vocês podem brincar com ele. Não se preocupe se você não obtê-lo. Não temos tempo para codificar -lo hoje, porque nós temos tem um monte de estas estruturas para percorrer, mas, essencialmente, pseudocódigo, muito, muito semelhante ao empurrar. Basta seguir ao longo da lógica. Certifique-se de que você está acessando todo o características de sua estrutura corretamente. Sim? AUDIÊNCIA: Será que esses slides e essa coisa toda ser até hoje-ish? ANDI Peng: Sempre, sim. Vou tentar colocar isto como uma hora depois. Vou enviar e-mail David, David vai tentar colocá-lo como uma hora depois disso. OK, então, em seguida, nos movemos para este outro estrutura de dados adorável chamada de fila. Como vocês podem ver aqui, um fila, para os britânicos entre nós, tudo isso é uma linha. Assim, ao contrário do que Você acha que é uma pilha, uma fila é exatamente o que logicamente que você pensa que é. É realizado pelas regras do FIFO, que é first in, first out. Se você é o primeiro um na linha, você está que o primeiro sai da linha. Então, o que nós gostamos de chamar este é dequeueing e enqueueing. Se queremos acrescentar algo a nossa fila, nós enfileirar. Se queremos retirar da fila, ou tomar algo longe, nós retirar da fila. Assim mesmo sentido que nós somos tipo de a criação de elementos de tamanho fixo que pode armazenar certa coisas, mas nós também podemos mudar para onde estamos colocando parâmetros dentro deles com base no que tipo de funcionalidade que queremos. Então, pilhas, queríamos a última um, N para ser o primeiro a sair. Fila é que queremos a primeira coisa para ser a primeira coisa para fora. Assim, o tipo struct definir, como você pode ver, é um pouco diferente a partir do que foi a pilha porque não só temos de manter o controle de onde o tamanho é atualmente, também queremos manter o controle da cabeça bem como onde estamos atualmente. Então, eu acho que é mais fácil se eu tirar isso. Então, vamos imaginar que temos uma fila, então vamos dizer que a cabeça está bem aqui. O chefe da linha, vamos apenas dizer que é atualmente lá, e queremos inserir algo na fila. Eu vou ligar para o tamanho essencialmente é a mesma coisa que a cauda, o fim da fila é sempre que o seu. Vamos apenas dizer que tamanho é aqui mesmo. Assim como um praticàvel inserir algo em uma fila? O índice queremos colocá onde queremos inserir. Se este é o início de sua fila e este é o fim de tudo ou o tamanho dele, onde é que vamos deseja adicionar o próximo objeto? AUDIÊNCIA: [inaudível] ANDI Peng: Exatamente, você deseja adicionar -lo, dependendo você escreveu ele. Ou este é em branco ou que está em branco. Então você deseja adicioná-lo, provavelmente, aqui porque, se o tamanho é-- se estes são todos completo, você quer adicioná-lo aqui, certo? E assim que é, ao mesmo tempo muito, muito simples, não é bem sempre correto porque a principal diferença entre uma fila e uma pilha é que a fila pode na verdade, ser manipulado de modo que as alterações de cabeça dependendo de onde você quer o início de sua sugestão para começar. E, como resultado, sua cauda também vai mudar. E então dê uma olhada este código agora. Como vocês também foram convidados a escrever sobre o quiz, enqueue. Talvez nós vamos falar através porquê a resposta era o que era. Eu não conseguia encaixar esta linha em um, mas, essencialmente, este pedaço de código deve estar em uma linha. Gastar como 30 segundos. Dê uma olhada, e veja por que esta é a maneira que é. Muito, muito semelhante struct, muito, muito estrutura semelhante à do anterior empilhar exceto, talvez, uma linha de código. E que uma linha de código determina a funcionalidade. E isso realmente diferencia uma fila de uma pilha. Quem quiser tomar uma facada para explicar por que você tem tem essa coisa complicada aqui? Nós vemos o retorno de nosso maravilhoso módulo amigo. Como vocês virá logo de reconhecer na programação, quase a qualquer momento você precisa de algo para envolver qualquer coisa, módulo vai ser a maneira de fazê-lo. Então, sabendo que, alguém quer para tentar explicar essa linha de código? Sim, todas as respostas são aceito e bem-vindo. AUDIÊNCIA: Você está falando comigo? ANDI Peng: Sim. AUDIÊNCIA: Oh, não me desculpe. ANDI Peng: OK, então vamos caminhar por este código. Então, quando você está tentando adicionar algo em uma fila, no caso adorável que a cabeça acontece para estar aqui, é muito fácil para nós apenas para ir até o fim inserir alguma coisa, certo? Mas o ponto inteiro de uma fila é que a cabeça pode realmente dinamicamente mudar, dependendo de onde nós quer o início da nossa q ser, e, como tal, a cauda também vai mudar. E assim imaginar que este não era o fila, mas esta foi a fila. Vamos dizer que a cabeça está bem aqui. Vamos dizer que nossa fila olhou como esta. Se quiséssemos deslocar onde o início da linha é, vamos dizer que mudou cabeça Desta forma e tamanhos aqui. Agora queremos acrescentar algo ao essa fila, mas como vocês podem ver, não é tão simples como apenas adicionar o que é após o tamanho porque então nós funcionamos fora do limites da nossa matriz real. Onde queremos realmente é here. Essa é a beleza de uma fila é que, para nós, visualmente Parece que a linha vai como esta, mas quando armazenada numa estrutura de dados, eles dão-lo como como um ciclo. É o tipo de envolve para a frente da mesma maneira que uma linha também pode envolvê em torno dependendo de onde quer que você quer início da linha para ser. E por isso, se dermos uma olhar para baixo aqui, vamos dizer que queria criar um função chamada enqueue. Nós queríamos adicionar int n em que q. Se q.size nós q-- chamaremos que os nossos dados structure-- se o nosso queue.size não igual capacidade ou se é menos do que a capacidade, q.strings é a matriz dentro da nossa q. Nós estamos indo para definir que igual a q.heads, que é aqui mesmo, além de q.size módulo pela capacidade, que envolvê-nos de volta por aqui. Assim, neste exemplo, o índice de de cabeça é um, certo? O índice de tamanho é 0, 1, 2, 3, 4. Então, podemos fazer mais um módulo 4 por nossa capacidade, que é 5. O que isso nos dá? O que é que o índice sai dessa? AUDIÊNCIA: 0. ANDI Peng: 0, que passa a ser aqui mesmo, e por isso queremos ser capazes para inserir aqui. E assim esta equação tipo aqui de apenas funciona com todos os números dependendo de onde o seu cabeça e seu tamanho é. Se você sabe o que aqueles as coisas são, você sabe exatamente onde você deseja inserir tudo o que é depois de sua fila. Isso faz sentido para todo mundo? Eu sei que tipo de um cérebro provocação especialmente uma vez que este veio na sequência do seu quiz. Mas espero que todos agora pode entender por isso que esta solução ou este função é a maneira que é. Qualquer um um pouco incerto sobre isso? ESTÁ BEM. E agora, se você queria para retirar da fila, este é onde a nossa cabeça seria deslocando porque se fôssemos para retirar da fila, nós não tirar a final do q. Queremos tirar a cabeça, certo? Então, como resultado, a cabeça vai mudar, e é por isso que quando você enfileirar, você tem que manter o controle de onde sua cabeça e seu tamanho são para ser capaz de inserir para a posição correcta. E assim, quando você retirar da fila, Eu também Pseudocódigo-lo. Sinta-se livre para se você quiser a tentativa de codificação isso. Você deseja mover a cabeça, certo? Se eu quisesse para retirar da fila, eu moveria a cabeça sobre. Esta seria a cabeça. E o nosso tamanho atual faria subtrair porque já não temos quatro elementos na matriz. Nós só temos três, e então nós queremos para retornar o que estava armazenado dentro da cabeça porque queremos aproveitar esta valor para fora de modo muito semelhante ao da pilha. Assim você está tomando de um lugar diferente, e você tem que voltar a atribuir o ponteiro para lugar diferente como resultado. Logicamente, todos sigam? Ótimo. OK, então vamos falar um pouco mais em profundidade sobre listas ligadas porque vai ser muito, muito valioso para você no decorrer desta semana Série de Exercícios. Listas ligadas, como vocês lembro, todos eles são são os nós que são nós de certa valores de ambos um valor e um ponteiro que estão ligados entre si por esses ponteiros. E assim, a estrutura de como criamos um nó aqui é nós tem int n, que é o que quer o valor em uma loja ou cadeia de n ou o que você quiser chamá-lo, o caractere estrela n. Struct estrela nó, que é o ponteiro que você quer ter em cada nó, você vai ter que ponteiro ponto em direção ao lado. Você vai ter a cabeça de uma lista ligada que é indo para apontar para o resto os valores assim por diante e assim por diante até que você finalmente chegar ao fim. E este último nó é apenas indo para não ter um ponteiro. Vai para apontar para null, e que, quando você sabe que você bateu o final da sua lista ligada é quando o último ponteiro não aponta para qualquer coisa. Então, nós estamos indo para ir um pouco mais em profundidade a respeito de como se faria possivelmente procurar uma lista ligada. Lembre-se o que são alguns dos inconvenientes das listas ligadas versículos uma matriz sobre pesquisas. Uma matriz que puder busca binária, mas por que você não pode fazer isso em uma lista vinculada? AUDIÊNCIA: Porque eles estão todos conectados, mas não sei bem onde [INAUDÍVEL]. ANDI Peng: Sim, exatamente por isso lembre- que o brilho de uma matriz foi o fato de que tínhamos memória de acesso aleatório onde se eu queria o valor do índice seis, eu poderia apenas dizer índice seis, dá-me esse valor. E isso é porque as matrizes são classificadas num espaço contíguo de memória em um só lugar, ao passo que tipo de listas ligadas são intercaladas aleatoriamente por toda parte, ea única maneira que você pode encontrar um é através de um ponteiro que lhe diz o endereço de onde o próximo nó é. E assim, como resultado, a única maneira para pesquisar uma lista ligada é a busca linear. Porque eu não sei exatamente onde o valor 12º na lista ligada é, Eu tenho que atravessar a totalidade dessa lista um ligado a um, da cabeça para o primeiro nó, para o segundo nó, para o terceiro nó, todo o caminho até que eu finalmente chegar para onde esse nó eu estou procurando é. E assim, neste sentido, busca em uma lista ligada é sempre n. É sempre n. É sempre em tempo linear. E assim o código em que vamos implementar isto, e isto é um pouco novo para vocês desde que você caras realmente não tenho falado ou nunca ponteiros visto em como pesquisar através de ponteiros, então vamos percorrer esta muito, muito lentamente. Assim, busca bool, direito, vamos imaginar que queremos para criar uma função chamada pesquisa que retorna verdadeiro Se você encontrou um valor dentro do ligada lista, e retorna false de outra forma. Lista estrela nó é Atualmente apenas o ponteiro para o primeiro item em sua lista ligada. int n é o valor que você está procurando na lista. Então ponteiro estrela nó lista é igual. Isso significa que nós estamos estabelecendo e criando um ponteiro para que o primeiro nó dentro da lista. Todo mundo comigo? Então, se tivéssemos de ir voltar aqui, eu teria inicializado um ponteiro que indica o cabeça de tudo o que é lista. E, em seguida, uma vez que você chegar aqui, enquanto ponteiro não é igual a null, de modo que é o ciclo em que estamos vai ser, subsequentemente, atravessando o resto da nossa lista, porque o que acontece quando o ponteiro é igual a null? Sabemos que have-- AUDIÊNCIA: [inaudível] ANDI Peng: Exatamente, por isso sabemos que chegamos ao fim da lista, certo? Se você voltar aqui, cada nó deve estar apontando para outro nó e assim por diante até chegar, eventualmente, a cauda da sua lista ligada, que tem um ponteiro que apenas não aponta qualquer lugar que não. E para que você saiba que, basicamente, sua lista ainda está lá em cima até ponteiro não é igual nula porque uma vez que ele é igual a null, você sabe que não há mais coisas. Então esse é o ciclo em que estamos vai ter a pesquisa real. E se os pointer-- você vê esse tipo de função seta lá? Portanto, se o ponteiro aponta n, se o ponteiro em que n é igual é igual a N, de modo que significa que se o ponteiro que você é procurando na extremidade de cada nó é efectivamente igual ao valor você está procurando, em seguida, você quer retornar verdadeiro. Então, basicamente, se você estiver em um nó que tem o valor que você está procurando, você sabe que você esteve capaz de pesquisa com êxito. Caso contrário, você deseja definir o ponteiro para o próximo nó. Isso é o que essa linha está fazendo aqui. Ponteiro é igual ponteiro próximo. Todo mundo ver como é que está trabalhando? E, essencialmente, você vai apenas atravessam a totalidade da lista, redefinir o ponteiro de cada vez até você finalmente bateu o final da lista. E você sabe que não há mais nós para pesquisar, e então você pode retornar false porque você sabe que, oh, bem, se eu fui capaz de pesquisar através da totalidade da lista. Se neste exemplo, se eu quisesse a olhar para o valor de 10, e eu começo na cabeça, e Eu procuro todo o caminho, e eu finalmente cheguei a esta, que um ponteiro que aponta para null, Eu sei que, uma porcaria, eu acho que 10 não está na esta lista porque eu não poderia encontrá-lo. E eu estou no fim da lista. E no caso de que você sabe Eu estou indo para retornar falso. Deixe que molho em um pouco. Isso vai ser muito importante para o seu pset. A lógica dele é muito simples, talvez sintaticamente apenas implementá-lo. Vocês querem fazer Certifique-se de que você entenda. Legal. OK, então como nós ficaríamos inserção de nós, certo, em uma lista de lembrar, porque o que são o que os benefícios de ter uma lista vinculada contra uma matriz em termos de armazenamento? AUDIÊNCIA: É dinâmico, por isso é mais fácil a-- ANDI Peng: Exatamente, por isso é dinâmica, o que significa que pode expandir-se e encolher dependendo das necessidades do usuário. E assim, neste sentido, nós não precisamos desperdiçar memória desnecessária porque eu se eu não sei quantos valores que eu quero a loja, não faz sentido para mim para criar uma matriz porque se eu quiser armazenar 10 valores e eu criar uma matriz de 1000, que é uma grande quantidade de memória desperdiçada, atribuído. É por isso que nós queremos usar um ligado lista para ser capaz de dinamicamente alterar ou diminuir o tamanho da nossa. E assim que faz a inserção um pouco mais complicado. Já que não podemos acessar aleatoriamente elementos da maneira que gostaríamos de uma matriz. Se eu quiser inserir um elemento na sétima índice, Eu só pode inseri-lo na sétima índice. Em uma lista ligada, isso não acontece bastante trabalhar tão facilmente, e por isso, se queríamos para inserir o aqui na lista ligada, visualmente, é muito fácil de ver. Nós apenas queremos inseri-lo ali mesmo, logo no início da lista, logo após a cabeça. Mas a maneira em que nós temos que voltar a atribuir os ponteiros é um pouco complicado ou, logicamente, faz sentido, mas você quer ter certeza de que você tem- completamente para baixo, porque a última coisa que você quer é reatribuir um ponteiro a maneira que nós estamos fazendo aqui. Se você excluir a referência o ponteiro da cabeça aos 1, então, de repente, o resto de sua lista ligada está perdido, porque você não tem, na verdade, criado um nada temporária. Isso apontou para o 2. Se transferir o ponteiro, então o resto de sua lista está totalmente perdido. Então você quer ser muito, muito cuidado aqui para atribuir o primeiro ponteiro de tudo o que você deseja inserir em qualquer lugar você quer, e então você pode cancelar o resto de sua lista. Então, isso se aplica para onde quer você está tentando inserir. Se você deseja inserir no cabeça, se você quiser responder aqui, se você deseja inserir no Ao final, bem, o fim I acho que você faria apenas não tem um ponteiro, mas você quer ter a certeza de que você não fazer perder o resto de sua lista. Você sempre quer ter a certeza o novo nó está apontando no sentido de tudo o que você deseja inserir, e então você pode adicionar o encadeamento diante. Todo mundo é clara? Este vai ser uma das questões reais. Uma das mais importantes questões você vai ter no seu pset é que você está indo para tentar criar uma lista encadeada e as coisas de inserção mas depois é só perder o resto de sua lista ligada. E você vai ser como eu Não sei por que isso está acontecendo? E é uma dor de passar por e pesquisar todos os seus ponteiros. E eu garanto que nesta pset, escrever e desenhar esses nós fora vai ser muito, muito útil. Assim você pode manter completamente a noção de onde todos os seus ponteiros são, o que está acontecendo de errado, onde todos os seus nodos são, o que você precisa fazer para acessar ou inserir ou excluir ou nenhum deles. Todo mundo bem com isso? Legal. Então, se nós queria olhar para o código? Oh, eu não sei se nós pode ver as-- OK, então no topo de tudo, é uma função inserção nomeado onde queremos para inserir int n na lista ligada. Nós vamos caminhar por este. É um monte de código, um monte de nova sintaxe. Nós vamos ficar bem. Assim, no topo, sempre que queremos criar nada o que precisamos de fazer, especialmente se você deseja que ele não deve ser armazenado na pilha mas na pilha? Nós vamos para um malloc, certo? Então vamos criar um ponteiro. Nó, ponteiro, novas equals malloc o tamanho de um nó porque queremos que nó a ser criado. Queremos que a quantidade de memória que um nó ocupa a ser alocado para o criação do novo nó. E então nós vamos verificar para ver se é igual a novos iguais nulo. Lembre-se do que dissemos? Tudo o que você malloc, o que você deve sempre fazer? Você deve sempre verificar para ver se isso é ou não nulo. Por exemplo, se seu funcionamento sistema foi completamente cheio, se você não tinha mais memória em tudo e tentar malloc, ele iria retornar nulo para você. E por isso, se você tentar usá-lo quando ele estava apontando para null, você não vai poder para acessar essa informação. E assim, como tal, nós queríamos fazer Certifique-se de que sempre que você está mallocing, você está sempre verificando se que a memória dado a você é nulo. E se não é, então podemos passar com o resto do nosso código. Então, nós estamos indo para inicializar o novo nó. Nós vamos fazer nova n é igual a n. E então nós vamos fazer definir novo o ponteiro na nova como nulo porque agora nós não quer nada para ele para apontar para. Nós não temos nenhuma idéia de onde ele vai colocá-lo, e, em seguida, se quisermos inseri-lo na cabeça, então podemos atribuir novamente o ponteiro para a cabeça. Será que todo mundo seguir a lógica de onde isso está acontecendo? Tudo o que estamos fazendo é criar uma nova nó, definir o ponteiro para null, e, em seguida, a reafectação -lo para a cabeça se sabemos que queremos para inseri-lo na cabeça. E, em seguida, a cabeça vai apontam para que o novo nó. Todo mundo bem com isso? Portanto, é um processo de duas etapas. Você tem que primeiro atribuir o que quer que você está criando. Definir que ponteiro para o referência, e então você pode tipo de dereference o primeiro ponteiro e apontá-lo para o novo nó. Onde quer que você deseja inseri-lo, que a lógica vai realizar verdadeiro. É uma espécie de como atribuir variáveis ​​temporárias. Lembre-se, você tem para se certificar de que você não perder de vista se você está trocando. Você quer ter certeza de que você tem um variável temporária esse tipo de guarda o controle de onde essa coisa é armazenada de modo que você não perdem qualquer valor no curso de como mexer com ele. OK, então o código será aqui. Vocês vejam após a secção. Ele vai estar lá. Então eu acho que como é que isso difere se quiséssemos inserir no meio ou no fim? Alguém tem uma idéia de qual é o pseudocódigo como referência lógica que levaria se quiséssemos para inseri-lo no meio? Então, se nós queria para inseri-lo no cabeça, tudo o que fazemos é criar um novo nó. Nós definir o ponteiro de que novo nó a tudo o que a cabeça, e, em seguida, vamos definir o cabeça para o novo nó, certo? Se quiséssemos para inseri-lo no meio da lista, o que teria que fazer? AUDIÊNCIA: É ainda faria ser um processo semelhante de como a atribuição de ponteiro e em seguida, atribuindo esse ponteiro, mas teríamos de encontrar lá. ANDI Peng: Exatamente, exatamente por isso o mesmo processo, exceto você tem que localizar onde exatamente você deseja que o novo ponteiro para entrar, por isso, se eu quero inserir em no meio de ligado lista-- OK, vamos dizer que essa é a nossa lista ligada. Se queremos inseri-lo aqui, vamos criar um novo nó. Nós estamos indo para malloc. Nós vamos criar um novo nó. Nós vamos atribuir o ponteiro deste nó aqui. Mas o problema que difere de onde a cabeça é é que nós sabíamos exatamente onde está a cabeça. Foi à direita no primeiro, certo? Mas aqui nós temos que manter o controle de onde estamos inserindo-o. Se estamos inserindo nosso nó aqui, nós temos para se certificar de que o anterior a este nó é aquele que atribui novamente o ponteiro. Então você tem que tipo de manter o controle de duas coisas. Se você manter o controle de onde esta nó atualmente está inserindo. Você também tem que manter o controle de onde o nó anterior que você está olhando também estava lá. Todo mundo bem com isso? ESTÁ BEM. Como cerca de inserir no final? Se eu queria adicioná-lo aqui-- se eu queria para adicionar um novo nó ao fim de uma lista, como eu poderia ir sobre como fazer isso? AUDIÊNCIA: Então, atualmente, a do último apontado como nulo. ANDI Peng: Sim. Exatamente, por isso este Atualmente é apontado saber, e então eu acho que, nesse sentido, é muito fácil de adicionar ao fim de uma lista. Tudo que você tem a fazer é configurá-lo igual a nulo e depois crescer. Bem ali, muito fácil. Muito simples. Muito semelhante ao cabeça, mas logicamente você quer ter a certeza que os passos você tomar para fazer nada disso, você está acompanhando. É muito fácil, no meio do seu código, pego em, oh, eu tenho tantos ponteiros. Eu não sei onde nada está apontando. Eu nem sei qual o nó em que estou. O que está acontecendo? Relaxe, acalme-se, tomar uma respiração profunda. Desenhe a sua lista ligada. Se você disser, eu sei onde exatamente Eu preciso inserir isto em e eu sei exatamente como realocar o meu ponteiros, muito, muito mais fácil de imaginar out-- muito, muito mais fácil de não se perder nos erros do seu código. Todo mundo bem com isso? ESTÁ BEM. Então eu acho que um conceito que não tem realmente falamos antes agora, e eu acho que você provavelmente não vai encontrar muito yet-- é uma espécie de um concept-- avançada é que nós realmente temos um conjunto de dados estrutura chamada uma lista duplamente ligada. Então, como vocês podem ver, tudo o que estamos fazendo é criar um valor real, um extra ponteiro em cada uma de nossas nós que também aponta para o nó anterior. Portanto, não só temos o nosso nodos apontar para a próxima. Eles também apontam para o anterior. Eu vou ignorar esses dois agora. Então você tem uma cadeia que pode mover-se em ambos os sentidos, e então é um pouco mais fácil a seguir logicamente junto. Como aqui, em vez de manter o controle de, oh, I tem que saber que esse nó é o que eu tenho que voltar a atribuir, Eu só posso ir aqui e basta puxar o anterior. Então eu sei exatamente onde que é, e então você não tem que atravessar a totalidade da lista ligada. É um pouco mais fácil. Mas, como tal, você tem duplamente a quantidade de ponteiros, que é o dobro da quantidade de memória. É um monte de ponteiros para acompanhar. É um pouco mais complexo, mas é um pouco mais amigável, dependendo o que você está tentando realizar. Portanto, este tipo de dados estrutura existe totalmente, ea estrutura para é muito, muito simples, exceto tudo que você está tendo é, em vez de apenas um ponteiro para o próximo, você também tem um ponteiro para anterior. Isso é tudo que a diferença era. Todo mundo bem com isso? Legal. Tudo bem, então agora eu sou para realmente passar, provavelmente, como 15 a 20 minutos ou a granel do resto do tempo na secção falando de tabelas de hash. Como muitos de vocês li pset5 especificação? Tudo bem, bom. Isso é mais elevado do que os 50% do normalmente. Está certo. Então, como vocês vão ver, você é desafio em pset5 será a implementação de um dicionário onde você carregar mais de 140.000 palavras que nós damos-lhe e verificação ortográfica contra todo o texto. Nós vamos dar-lhe aleatória peças de literatura. Nós vamos dar-lhe The Odyssey. Nós vamos dar-lhe a Ilíada. Nós vamos dar-lhe Austin Powers. E seu desafio será a de verificação ortográfica cada palavra em tudo desses dicionários essencialmente com nosso corretor ortográfico. E por isso há poucas partes de criar este pset, primeiro você quer ser capaz de carregar, na verdade, todas as palavras em seu dicionário, e então você quer ser capaz de verificação ortográfica todos eles. E assim, como tal, você está indo para exigir uma estrutura de dados que pode fazer isso rápido e eficientemente e de forma dinâmica. Então, eu suponho que o mais fácil maneira de fazer isso, você provavelmente criar uma matriz, certo? A maneira mais fácil de armazenamento é você pode criar uma matriz de 140.000 palavras e apenas colocá-los todos lá e então atravessá-los por busca binária ou pelas selecções ou não-- Lamentamos que é a classificação. Você pode classificá-los e depois atravessá-los por busca binária ou busca apenas linear e apenas as palavras finais, mas que leva uma grande quantidade de memória, e não é muito eficiente. E assim nós vamos começar falando sobre maneiras de fazer nosso tempo de funcionamento mais eficiente. E nosso objetivo é fazer com que constante de tempo onde é quase como matrizes, onde você tem acesso instantâneo. Se eu quisesse procurar qualquer coisa, Eu quero ser capaz de apenas, crescimento, encontrá-lo exatamente, e puxe-o para fora. E assim uma estrutura na qual nós vamos estar a tornar-se muito perto para acessar a constante tempo, esse santo graal na programação da constante tempo é chamado de tabela de hash. E assim por David mencionado anteriormente o [Inaudível] um pouco na palestra, mas nós vamos realmente mergulho em profundidade esta semana em um pedaço que está sobre como uma tabela hash funciona. Assim, a maneira que um hash obras de mesa, por exemplo, se eu queria guardar um monte de palavras, um monte de palavras no idioma Inglês, Eu poderia, teoricamente, colocar banana, maçã, kiwi, manga, par, e melão tudo em apenas uma matriz. Todos eles poderiam se encaixar e ser encontrar. Seria uma espécie de dor para pesquisar e acesso, mas a maneira mais fácil de fazer isto é que pode criar efectivamente uma estrutura chamado uma tabela hash onde nós hash. Corremos todos os nossos chaves através uma função hash, uma equação, que transforma-los todos em algum tipo de valor que então podemos armazenar em essencialmente um array de lista ligada. E aqui, se quiséssemos para armazenar palavras em inglês, Podemos potencialmente apenas, eu não sabe, transformar todas as primeiras letras em algum tipo de um número. E assim, por exemplo, se eu quisesse Um a ser sinônimo de apple-- ou com o índice de 0, e B a ser sinônimo de 1, nós podemos ter 26 entradas que podem apenas armazenar todas as letras do alfabeto que vamos começar. E então nós podemos ter maçã no índice de 0. Podemos ter de banana no índice de 1, melão no índice de 2, e assim por diante. E, assim, se eu quisesse pesquisar meu hash de mesa e acesso maçã, Eu sei que a Apple começa com um A, e eu sei exatamente que deve ser eo hash tabela no índice 0, pois da função atribuído anteriormente. Então, eu não sei, nós somos um programa de usuário, onde você vai ser cobrado com não arbitrarily-- arbitrariamente, com a tentativa de pensativamente pensar em boas equações para ser capaz de se espalhar fora todos os seus valores de uma maneira que eles podem acessar facilmente -lo mais tarde com como uma equação que você, você mesmo, sabe. Assim, no sentido de se eu queria ir para manga, eu sei, oh, ele começa com m. Deve ser no índice de 12. Eu não tenho a busca através de qualquer coisa. Eu sei exactly-- eu poderia apenas ir para o índice de 12 e puxar isso. Todos clara sobre como um A função da tabela hash funciona? É uma espécie de apenas uma matriz mais complexa. Isso é tudo o que é. ESTÁ BEM. Então eu acho que correr em esta questão do que acontece se você tiver várias coisas que dar-lhe o mesmo índice? Então, dizer que a nossa função, tudo o que fez foi tomar essa primeira letra e transformar isso em um respectivo índice 0 a 25. Isso é totalmente bem se você só tem um de cada. Mas a segunda você começa ter mais, você é vai ter o que é chamado uma colisão. Então, se eu tentar inserir enterrar em um hash tabela que já tenha banana nele, o que vai acontecer quando tentar inserir isso? Coisas ruins por causa da banana já existe dentro do índice que você deseja armazená-lo em. Berry tipo de é como, ah, o que eu faço? Eu não sei para onde ir. Como posso resolver isso? E assim vocês vão tipo de ver o que fazemos esta coisa complicada onde podemos tipo de verdade criar lista ligada em nossas matrizes. E assim, a maneira mais fácil para pensar sobre isso, tudo é uma tabela hash matriz de listas ligadas. E assim, nesse sentido, você tem esta bela matriz de ponteiros, e, em seguida, em cada ponteiro esse valor, em que o índice, pode realmente apontar para outras coisas. E então você tem todos esses separado cadeias saindo de uma grande matriz. E aqui, se eu queria inserir baga, Eu sei, OK, eu estou indo para introduzir -lo através de minha função hash. Eu vou acabar com o índice de 1, e então eu vou ser capaz de ter apenas um subconjunto menor da presente gigante dicionário de 140.000 palavras. E então eu posso apenas olhar através de 1/26 do que isso. E então eu só posso inserir baga, quer antes ou depois da banana nesse caso? Depois, certo? E então você vai querer inserir esse nó depois de banana, e então você vai para inserir em que a cauda de lista ligada. Eu vou voltar a este slide anterior, para que vocês possam ver como função hash funciona. Então função hash é esta equação que você está executando o seu tipo de entrada através de obter o que quer índice pretende atribuir-lo para. E assim, neste exemplo, tudo o que queríamos a fazer era tomar a primeira letra, transformar isso em um índice, então nós pode armazenar que em nossa função hash. Tudo o que estamos fazendo aqui é que estamos converter a primeira letra. Então KeyKey [0] é apenas a primeira letra de qualquer seqüência que estamos tendo, estamos passando. Estamos convertendo que a superior, e estamos subtraindo por letras maiúsculas A, assim tudo que está fazendo está nos dando um número em que podemos botar nossos valores para. E então nós vamos retornar de hash TAMANHO módulo. Seja muito, muito cuidado porque, teoricamente, aqui o seu valor de hash pode ser infinita. Ele poderia simplesmente ir sobre e sobre e sobre. Pode haver alguma verdade, realmente grande valor, mas porque sua tabela hash que que você criou possui apenas 26 índices, você quer ter certeza de seu modulusing para que você não run-- é o mesmo coisa como seu queue-- para que você não corra fora da inferior de sua função hash. Você quer envolvê-la de volta ao redor da mesma forma em [inaudível] quando você teve como um muito, muito grande carta, você Não queria que isso basta executar fora da final. Mesma coisa aqui, você quer certificar-se ele não é executado fora da final por envolvimento em torno ao topo da mesa. Portanto, esta é apenas uma muito função hash simples. Tudo o que fiz foi dar o primeiro carta de tudo o que o nosso contributo foi e transformar isso em um índice que poderíamos colocar em nossa tabela de hash. Sim, e assim como eu disse antes, a maneira que nós resolver colisões em nosso hash de tabelas estão tendo, o que chamamos de encadeamento. Então, se você tentar inserir múltiplo palavras que começam com a mesma coisa, você vai ter um valor de hash. Abacate e maçã, se você tiver executá-lo através de nossa função hash, vai dar-lhe a mesmo número, o número de 0. E assim a nossa forma de resolver isso é que podemos realmente tipo de vinculá-los juntos via listas ligadas. E assim, neste sentido, vocês podem ver espécie de forma que as estruturas de dados temos vindo a criação anteriormente como uma uva passa ligada lista espécie de podem se unir em um só. E então você pode criar muito estruturas de dados mais eficientes que pode lidar com grandes quantidades de dados, que redimensionar dinamicamente dependendo de suas necessidades. Todo mundo é clara? Todos tipo de clara sobre o que acontece aqui? Se eu quisesse insert-- o que é um fruta que começa com, eu não sei, B, com excepção baga, banana. AUDIÊNCIA: Blackberry. ANDI Peng: Blackberry, amora. Onde é que blackberry aqui? Bem, nós realmente não ter resolvido isso ainda, mas, teoricamente, se quiséssemos ter este em ordem alfabética, onde deve ir blackberry? AUDIÊNCIA: [inaudível] ANDI Peng: Exatamente, após aqui, certo? Mas já que é muito difícil reorder-- Eu acho que cabe a vocês. Vocês podem totalmente implementar o que quiser. A maneira mais eficiente de fazer isso, talvez, seria a de classificar sua ligado lista em ordem alfabética, e então quando você está inserção de coisas, você quer ter a certeza de inseri-los em ordem alfabética para que, em seguida, quando você está tentando procurá-los, você não tem que atravessar tudo. Você sabe exatamente onde que é, e é mais fácil. Mas se você tipo de ter coisas intercalado aleatoriamente, você ainda vai ter para atravessá-lo de qualquer maneira. E então se eu queria apenas inserir blackberry aqui e eu queria procurar isso, eu sei, oh, blackberry deve começar com o índice de 1, então eu saber instantaneamente basta pesquisar a 1. E então eu posso tipo de atravessar a lista vinculada até eu chegar para o BlackBerry, e entăo-- sim? Audiência: Se você está tentando create-- Eu acho que como este é um hash muito simples função. E se o que queríamos fazer várias camadas de que, como o OK, nós queremos separar em como todas as letras do alfabeto e depois novamente a gostar de outro conjunto de letras do alfabeto em que, que estamos colocando como um hash tabela dentro de uma tabela hash, ou como uma função dentro de uma função? Ou é isso-- ANDI Peng: Então seu haxixe function-- sua tabela hash pode ser tão grande quanto você quer que ele. Portanto, nesse sentido, pensei era muito fácil, muito simples para mim com base apenas sorte em cartas de a primeira palavra. E por isso há apenas 26 opções. Eu só pode obter 26 opções de 0-25 porque eles só podem começar de A a Z. Mas Se você queria a acrescentar, talvez, mais complexidade ou mais rápido tempo de execução para o seu tabela de hash, é absolutamente pode fazer todo tipo de coisas. Você pode fazer o seu próprio equação que dá a você mais em sua distribuição palavras, então quando você procura, ele vai ser mais rápido. É totalmente até vocês como você deseja implementar isso. Pense nisso como apenas baldes. Se eu queria ter 26 baldes, eu vou para resolver as coisas para aqueles baldes. Mas eu vou ter um monte de material em cada balde, por isso, se você quiser torná-lo mais rápido e mais eficiente, deixe-me ter uma centena de baldes. Mas então você tem que descobrir uma maneira de resolver as coisas para que eles sejam no balde adequada eles devem estar em. Mas então quando você realmente quero olhar para esse balde, é muito mais rápido porque não há menos coisas em cada balde. E então, sim, isso é verdade, o truque para vocês em pset5 é que você vai ser desafiados a criar apenas qualquer que seja o mais eficiente função que você pode pensar de ser capaz de armazenar e verificar esses valores. Totalmente até vocês no entanto, você quer fazê-lo, mas isso é um ponto muito bom. Que o tipo de lógica você quer começar a pensar em é, bem, por que não posso fazer mais baldes. E então eu tenho que procurar menos coisas, e então talvez eu tem uma função hash diferente. Sim, há um monte de maneiras de fazer isso pset, alguns são mais rápidos do que outros. Estou totalmente vai apenas ver como rápido foi o mais rápido que vocês vão ser capaz de obter suas funções para trabalhar. OK, todos em bom encadeamento e hash tabelas? É realmente como uma forma muito simples conceito, se você pensar sobre isso. Tudo o que é separar o que quer suas entradas estão em baldes, classificando-os, em seguida, procura o lista que não está associado. Legal. Tudo bem, agora nós temos um tipo diferente de estrutura de dados que é chamado de uma árvore. Vamos seguir em frente e falar sobre tentativas que são distintamente diferentes, mas na mesma categoria. Essencialmente, toda a árvore é uma vez de organização de dados na forma linear que uma tabela hash does-- você sabe, ele tem um superior e um inferior e, em seguida, você tipo de ligação fora de um ele-- árvore tem um top que você chamar a raiz, e em seguida, ele tem as folhas toda em torno dele. E assim tudo que você tem aqui é apenas o nó superior que aponta para outros nós, que pontos para mais nós, e assim por diante e assim por diante. E assim você só tem ramos de divisão. É apenas uma maneira diferente de organizar dados, e porque nós o chamamos de uma árvore, vocês só-- é apenas modelado para se parecer com uma árvore. É por isso que nós o chamamos de árvores. Tabela de hash parece uma tabela. Uma árvore apenas se parece com uma árvore. Tudo o que é um separado forma de organizar os nós dependendo de quais são suas necessidades. Então você tem uma raiz e então você tem folhas. A maneira que nós podemos particularmente pensar sobre isso é uma árvore binária, uma árvore binária é apenas um tipo específico de uma árvore onde cada nó únicos pontos a, no máximo, dois outros nós. E por isso aqui você tem distintas simetria em sua árvore que torna mais fácil tipo de olhar em que os valores que são, porque então você ter sempre um esquerdo ou direito. Nunca há como uma terceira esquerda de a esquerda ou um quarto da esquerda. É só você tem uma esquerda e uma direita e você pode procurar qualquer um dos dois. E assim por que isso é útil? A maneira que este é é útil se você está procurando a busca através de valores, certo? Em vez de implementar binário pesquisar em uma matriz de erro, se você queria ser capaz de inserir os nós e tirar os nós à vontade e também preservar a pesquisa capacidades de busca binária. Assim, deste modo, nós somos tipo de tricking-- lembro quando nós disse listas ligadas não posso busca binária? Estamos tipo de criação de uma estrutura de dados que truques que em trabalhar. E isso porque listas ligadas são lineares, eles só ligar um após o outro. Podemos tipo de ter diferente tipo de ponteiros que apontam para diferentes nós que pode nos ajudar com a pesquisa. E aqui, se eu quisesse ter uma árvore de busca binária, Eu sei que o meu meio se 55. Eu só vou criar esse como meu meio, como a minha raiz, e então eu vou ter valores girar fora dele. Então, aqui, se eu vou procurar o valor de 66, eu posso começar a 55. É 66 maior do que 55? Sim, é, então eu sei que mus pesquisa i n o ponteiro direita da árvore. Eu vou para 77. OK, é menos do que 66 ou maior do que 77? É menos do que, por isso, você sabe, oh, que tem de ser o nó à esquerda. E então aqui estamos tipo de preservação todas as grandes coisas sobre arrays, assim como redimensionamento dinâmico de objetos, sendo capaz de inserir e excluir à vontade, sem ter que se preocupar com o fixo quantidade de espaço. Nós ainda preservar todos aquelas coisas maravilhosas enquanto também é capaz de preservar a log e tempo de busca binária pesquisa que nós só anteriormente capaz de obter uma frase. Estrutura de dados legal, tipo de complexo de implementar, o nó. Como você pode ver, tudo o que representa a estrutura do nó é que você tem uma esquerda e um ponteiro direito. Isso é tudo o que é. Então, ao invés de apenas Tendo um X ou uma anterior. Você tem uma esquerda ou a direita, e, em seguida, você pode tipo de ligá-los juntos no entanto você escolhe assim. OK, nós estamos indo realmente basta tirar alguns minutos. Então vamos voltar aqui. Como eu disse anteriormente, Eu meio que explicou a lógica por trás de como nós iria procurar por isso. Nós estamos indo para tentar pseudocoding este para fora para ver se podemos aplicar o tipo de mesma lógica de busca binária a um tipo diferente de estrutura de dados. Se vocês querem tomar como um casal minutos para apenas pensar sobre isso. ESTÁ BEM. Tudo bem, eu vou na verdade, apenas dar-lhe as-- não, vamos falar sobre o pseudocódigo primeiro. Então, alguém quer para dar uma facada em que a primeira coisa que você quer fazer quando você está começando a pesquisa é? Se nós estamos procurando o valor de 66, o que é a primeira coisa que queremos fazer, se queremos Pesquisa Binária esta árvore? AUDIÊNCIA: Você quer olhar direito e olhar esquerda e ver [inaudível] maior número. ANDI Peng: Sim, exatamente. Então, você vai olhar para a sua raiz. Há muitas maneiras que você pode chamar ele, seu nó pai pessoas dizem. Eu gosto de dizer porque raiz que é como a raiz da árvore. Você vai olhar para o nó raiz, e você está vai ver é 66 maior que ou menor do que 55. E se é maior do que, bem, é superior, onde é que vamos querer olhar? Aonde queremos procurar agora, certo? Queremos procurar o metade direita da árvore. Portanto, temos, convenientemente, um ponteiro que aponta para a direita. E então podemos definir nossa nova raiz para ser 77. Nós podemos apenas ir para onde quer o ponteiro está apontando. Bem, oh, aqui estamos começando aos 77 anos, e nós podemos apenas fazer isso de forma recursiva novamente e novamente. Desta forma, você meio de ter uma função. Você tem uma maneira de pesquisar que você pode apenas repetir mais e mais e mais, dependendo de onde você quer olhar até finalmente chegar ao valor que você está procurando. Faz sentido? Estou prestes a mostrar-lhe o real código, e é um monte de código. Não há necessidade de assustar. Vamos falar com ele. Na verdade não. Isso foi apenas pseudocódigo. OK, isso foi apenas o pseudocódigo, que é um pouco complexo, mas é totalmente bom. Todo mundo seguindo ao longo aqui? Se a raiz é nulo, o retorno falso, porque isso significa você não tem sequer qualquer coisa lá. Se raiz n é o valor, assim que se acontece a ser o que você está olhando, então você está indo para retornar true porque você sabe que você encontrou. Mas, se o valor for inferior de raiz n, você é vai procurar a esquerda criança ou a folha esquerda, tudo o que você quiser chamá-lo. E se o valor for superior a raiz, você está indo para procurar a árvore direita, em seguida, basta executar a função através de pesquisa novamente. E se a raiz é nulo, para que aquele Significa que você chegou ao fim? Isso significa que você não tem nenhuma mais mais folhas de pesquisa, então você sabe, oh, I acho que não é aqui porque depois que eu olhei através a coisa toda e não é aqui, ele só poderia não estar aqui. Isso faz sentido para todo mundo? Então, é como busca binária preservação as capacidades de listas ligadas. Arrefecer, e de modo que o segundo tipo de estrutura de dados que vocês pode tentar implementar em seu pset, você só tem que escolher um método. Mas talvez um método alternativo para a tabela hash é o que chamamos um trie. Tudo é um trie é um tipo específico de árvore que tem valores que vão para outros valores. Então, ao invés de ter um binário árvore no sentido de que apenas um coisa pode apontar para dois, você pode ter uma coisa aponte para muitas, muitas coisas. Você tem basicamente matrizes dentro do qual você armazena ponteiros que apontam para outras matrizes. Assim, o nó de como nós definiria um trie é que nós queremos ter um Booleano, palavra de c, certo? Assim, o nó é booleano como verdadeira ou falsa, em primeiro lugar, à frente de essa matriz, isso é uma palavra? Em segundo lugar, você quer ter ponteiros a tudo o que o resto deles são. Um pouco complexo, um pouco abstrato, mas Vou explicar o que tudo isso significa. Então, aqui, no topo, se você tenho uma matriz já declarou, um nó onde você tem um valor booleano valor armazenado na frente que lhe diz é esta uma palavra? Não é esta uma palavra? E então você tem o resto de sua matriz que na verdade, armazena todas as possibilidades do que poderia ser. Assim, por exemplo, como no topo você tem a primeira coisa que diz verdadeira ou falso, sim ou não, esta é uma palavra. E então você tem de 0 a 26 de as cartas que você pode armazenar. Se eu quisesse pesquisar aqui para morcego, eu ir para o topo e eu olho para B. Acho B na minha array, e então eu sei, OK, é uma palavra B? B não é uma palavra, de modo que assim Devo continuar pesquisando. Eu vou de B, e eu olho para o ponteiro que aponta para B e eu vejo outro conjunto de informações, a mesma estrutura que tínhamos antes. E aqui-- oh, o próximo carta em [inaudível] é A. Então, nós olhamos nesse array. Nós encontramos o oitavo valor, e, depois, olhar para ver, oh, hey, que é uma palavra, é B-A uma palavra? Não é uma palavra. Nós temos que continuar procurando. E então olhamos para onde o ponteiro de pontos A, e aponta para uma outra maneira em que temos mais valor armazenado. E, eventualmente, temos de B-A-T, o que é uma palavra. E assim na próxima vez você olha, você está indo para ter esse cheque de, sim, esta função booleana é verdadeira. E assim, no sentido de que estamos espécie de ter uma árvore com matrizes. Então você pode tipo de busca para baixo. Ao invés de uma função hash e atribuindo valores de lista ligada, você pode simplesmente implementar um trie que procura downwords. Realmente, realmente complicado coisas. Não é fácil pensar, porque eu sou como cuspindo tantas estruturas de dados para fora em você, mas como todo tipo de entender como a lógica de tudo isto funciona? OK legal. Assim B-A-T e, em seguida você vai procurar. A próxima vez que você está indo para ver, oh, hey, é verdade, assim, eu sei que isso deve ser uma palavra. Mesma coisa para jardim zoológico. Então aqui é a coisa certa agora, se nós queria procurar jardim zoológico, agora, Atualmente não é um jardim zoológico palavra em nosso dicionário porque, como vocês podem ver, o o primeiro lugar que temos um booleano return true é no final de zoom. Temos Z-O-O-H. E aqui, nós não realmente ter a palavra, jardim zoológico, no nosso dicionário porque esta caixa de seleção não está marcada. Assim, o computador não faz sei que zoo é uma palavra porque a maneira que nós temos armazenados, só um zoom aqui na verdade tem um valor booleano que tem sido virou verdade. Portanto, se queremos inserir o palavra, jardim zoológico, em nosso dicionário, como é que nós vamos fazer sobre isso? O que temos que fazer para garantir que a nossa computador sabe que Z-O-O é uma palavra e não a primeira palavra é Z-O-O-H? AUDIÊNCIA: [inaudível] ANDI Peng: Exatamente, nós quer ter a certeza de que este aqui, que é valor booleano verificado fora que é verdade. Z-O-O, em seguida, vamos verificar que, por isso sabemos exatamente, hey, jardim zoológico é uma palavra. Eu vou dizer a computador que é uma palavra tão que quando o computador verifica, ele sabe que zoo é uma palavra. Porque lembre-se todos estes dados estruturas, é muito fácil para nós quer dizer, oh, morcego é uma palavra. Zoo é uma palavra. Zoom é uma palavra. Mas quando você está construindo, o computador não tem idéia. Então você tem que dizer a ele exatamente em que ponto é esta uma palavra? Em que ponto é que nem uma palavra? E em que ponto I precisa procurar coisas, e em que ponto eu preciso ir em seguida? Todos clara de que? Legal. E então vem o problema de como seria de nós ir sobre como inserir algo que, na verdade, não está lá? Então vamos dizer que queremos inserir a palavra, banho, em nossa trie. Como vocês podem ver como actualmente tudo o que temos agora é B-A-T, e esta nova estrutura de dados lá tinha uma caneca que apontou para nula porque assumimos que, oh, não há palavras após B-A-T, por que precisamos para manter ter as coisas depois que T. Mas o problema surge se você quero ter uma palavra que vem depois a T. Se você tiver banheira, você está vai querer um direito H. E assim, a maneira que nós estamos indo para fazer isso é vamos criar um nó separado. Nós não vamos colocar qualquer quantidade de memória para esta nova matriz, e vamos voltar a atribuir ponteiros. Nós vamos atribuir o H, Primeiro de tudo, este nulo, nós estamos indo para se livrar. Nós vamos ter os para baixo ponto H. Se vemos um H, queremos que para ir para outro lugar. Em aqui, então podemos marcar sim. Se nós batemos um H após o T, oh, então sabemos que esta é uma palavra. O booleano vai retornar true. Todos clara sobre como isso aconteceu? ESTÁ BEM. Assim, essencialmente, todos estas estruturas de dados que temos ido mais hoje, eu tenho ido sobre eles muito, muito rapidamente e em que não mais detalhe, e isso é OK. Uma vez que você começar a brincar com ele, você poderá manter o controle de onde Todos os ponteiros são, o que está acontecendo em sua estruturas de dados, et cetera. Eles vão ser muito útil, e cabe a você caras para descobrir como totalmente fora você deseja implementar coisas. E assim PSet4, de 5-- oh, isso é errado. Pset5 é erros de ortografia. Como eu disse antes, você vai, uma vez novamente, baixar o código fonte de nós. Não vai ser de três principal coisas que você vai ser o download. Você vai baixar dicionários, kers e textos. Todas essas coisas são são quer dicionários de palavras que nós queremos que você vá ou teste de informações que nós queremos que você verificação ortográfica. E assim os dicionários nós damos-lhe vão para dar-lhe palavras reais que queremos você armazene alguma forma em uma forma que é mais eficiente do que uma matriz. E, em seguida, os textos são vai ser o que nós somos pedindo-lhe para soletrar verifique se todas as palavras são palavras reais lá. E assim os três blocos de programas que nós vamos dar-lhe são chamados dictionary.c, dictionary.h, e speller.c. E assim todo o dictionary.c faz é o que você está convidado a implementar. Ele carrega palavras. Ele ortográfico verifica-los, e isso torna-se de que tudo está inserido corretamente. diction.h é apenas um arquivo de biblioteca que declara todas essas funções. E speller.c, nós vamos dar-lhe. Você não precisa modificar nada disso. Todos speller.c faz é tomar que, carrega-lo, verifica a velocidade do mesmo, testa o valor de referência de como como rapidamente você é capaz de fazer as coisas. É um verificador ortográfico. Apenas não mexer com isso, mas fazer certeza que você entende o que está fazendo. Nós usamos uma função chamada getrusage que testa o desempenho do seu feitiço verificador. Tudo que faz é basicamente testar a tempo de tudo em seu dicionário, por isso certifique-se de compreendê-lo. Tenha cuidado para não mexer com ele ou as outras coisas não funcionará corretamente. E a maior parte desse desafio é para vocês para realmente modificar dictionary.c. Nós vamos dar-lhe 140.000 palavras em um dicionário. Nós vamos dar-lhe um texto arquivo que tenha essas palavras, e nós queremos que você seja capaz de organizar -los em uma tabela hash ou um trie porque quando pedimos-lhe para soletrar check-- imagine se você é mágica verificar como a Odisséia de Homero. É como esta enorme teste enorme,. Imagine se cada palavra que você tinha que olhar através de uma matriz de valores de 140.000. Isso levaria para sempre para a sua máquina para funcionar. É por isso que queremos organizar a nossa dados em estruturas de dados mais eficientes tais como uma tabela de hash ou um trie. E então vocês podem tipo de quando você procura acesso coisas com mais facilidade e mais rapidamente. E por isso tome cuidado para resolver colisões. Você está indo para obter um bando de palavras de que começo com A. Você vai ter um monte palavras que começam com B. Até você caras como você deseja resolver. Talvez haja mais função hash eficiente que apenas a primeira letra alguma coisa, e por isso é até você caras para tipo de fazer o que quiser. Talvez você deseja adicionar todas as letras juntas. Talvez você deseja como fazer coisas estranhas para contabilizar o número de letras, tanto faz. Até vocês como você quer fazer. Se você quer fazer uma tabela hash, se você quer tentar uma trie, totalmente até você. Vou avisá-lo antes do tempo que o trie é normalmente um pouco mais difícil apenas porque há um monte mais ponteiros para acompanhar. Mas totalmente até vocês. É muito mais eficiente na maioria dos casos. Você quer realmente ser capaz de manter a par de todos os seus ponteiros. Como fazer a mesma coisa que eu estava fazendo aqui. Quando você está tentando inserir valores em uma tabela hash ou excluir, certifique-se que você é realmente manter o controle de onde tudo é porque é realmente fácil para se estou tentando inserir como a palavra, andy. Vamos apenas dizer que é um palavra verdadeira, a palavra, andy, em uma lista gigante de um palavras. Se eu só acontecerá a reafectação um ponteiro errado, oops, lá se vai a totalidade do o resto da minha lista ligada. Agora, a única palavra que eu tem é Andy, e agora todas as outras palavras do dicionário ter sido perdida. E assim que você quer certificar-se de que você manter o controle de todos os seus ponteiros ou então você está indo para obter enormes problemas em seu código. Desenhe as coisas cuidadosamente, passo a passo. Isso torna muito mais fácil de pensar. E, finalmente, você quer ser capaz de testar o seu desempenho do seu programa no grande tabuleiro. Se vocês tomar uma olhar para CS50 agora, nós temos o que é chamado o grande quadro. É a súmula dos mais rápidos soletrar tempos de aferição, em todos CS50 agora, eu acho que o top 10 como vezes eu acho que oito deles são funcionários. Nós realmente queremos que vocês nos vencer. Todos nós estávamos tentando implementar o código mais rápido possível. Queremos que vocês tentar desafiar nós e implementar mais rapidamente do que todos nós podem. E assim, este é realmente a primeira vez que nós somos pedindo a vocês para fazer um pset que você realmente pode fazer em qualquer método tu queres. Eu sempre digo, este é mais parecido a uma solução da vida real, certo? Eu digo, hey, eu preciso de você para fazer isso. Construir um programa que faz isso para mim. Fazê-lo como quiser. Eu só sei que eu quero jejuar. Esse é o seu desafio para esta semana. Vocês, vamos para dar-lhe uma tarefa. Nós vamos dar-lhe um desafio. E então cabe a vocês completamente apenas descobrir qual é a mais rápida e mais maneira eficiente de implementar isso. Sim? AUDIÊNCIA: É permitido se queria pesquisar maneiras mais rápidas para fazer tabelas de hash on-line, podemos fazer que e citar código de outra pessoa? ANDI Peng: Sim, totalmente bem. Então, se vocês a ler spec, há uma linha na especificação que diz que vocês são totalmente livres para pesquisar de hash funções em que são alguns das funções hash mais rápidos para executar as coisas através como Contanto que você citar esse código. Por isso, algumas pessoas já têm descobri maneiras rápidas de fazer corretores ortográficos, de rápida formas de armazenar informações. Totalmente até que vocês se quero tomar apenas isso, certo? Certifique-se de que você está citando. O desafio aqui é realmente que estamos tentando testar é ter certeza que você sabe o caminho de volta ponteiros. Tanto quanto você implementar a função hash real e chegando com como a matemática para fazer isso, vocês podem pesquisar o que quer métodos on-line que vocês querem. Sim? AUDIÊNCIA: Podemos citar apenas usando o [inaudível]? ANDI Peng: Sim. Você pode apenas, em seu comentário, você pode citar como, oh, tomado de yada, yada, yada, a função hash. Alguém tem alguma pergunta? Nós, na verdade breezed a seção de hoje. Eu vou estar aqui a responder a perguntas bem. Além disso, como eu disse, escritório horas esta noite e amanhã. A especificação desta semana é, na verdade, super fácil e super rápido de ler. Eu gostaria de sugerir tendo um olhar, apenas ler através da totalidade do mesmo. E Zamyla realmente anda você através de cada uma das funções você precisa para implementar, e por isso é muito, muito claro como fazer tudo. Só para ter certeza que você é manter o controle dos ponteiros. Este é um pset muito desafiador. Não é um desafio porque, como, oh, os conceitos são muito mais difícil, ou você tem que aprender muito nova sintaxe do caminho que você fez para a última pset. Isto é difícil porque pset há muitos pontos, e então é muito, muito fácil de uma vez você tem um bug em seu código não ser capaz para descobrir onde é que o bug. E assim completa e absoluta fé em você caras para ser capaz de bater o nosso [inaudível] grafias. Na verdade, eu não tenho qualquer mina escrito Ainda não, mas estou prestes a escrever o meu. Então, enquanto você está escrevendo seu, eu vou estar escrevendo meu. Vou tentar fazer mina mais rápido do que o seu. Vamos ver quem tem o mais rápido. E sim, vou ver todos vocês aqui na terça-feira. Vou correr um tipo como uma oficina pset. Todas as secções este semana são oficinas PSet, então vocês têm muitas oportunidades por ajuda, o horário de expediente, como sempre, e eu realmente ansioso para ler todo o código dos seus rapazes. Eu tenho quizzes-se aqui se você caras querem vir buscar aqueles. Isso é tudo.