[Powered by Google Translate] [Semana 6, continuação] [David J. Malan] [Harvard University] [Esta é CS50.] [CS50.TV] Este é CS50 e este é o fim da semana 6. Então CS50x, um dos primeiros cursos de Harvard envolvidos na iniciativa EDX de fato estreou esta segunda-feira passada. Se você gostaria de obter um vislumbre do que os outros na Internet estão agora acompanhando com, você pode ir para x.cs50.net. Que irá redirecioná-lo para o local apropriado no edx.org, que foi onde este e outros cursos do MIT e Berkeley vivem agora. Você vai ter que se inscrever para uma conta, você vai descobrir que o material é basicamente o mesmo como você teve neste semestre, embora algumas semanas atrasadas, como temos tudo pronto. Mas o que os alunos em CS50x vai ver agora é uma interface bastante como este. Este, por exemplo, é Zamyla levando passo a passo para conjunto de problemas 0. Ao fazer o login para edx.org, um estudante CS50x vê os tipos de coisas que seria de esperar para ver em um curso: a palestra para a segunda-feira, palestra para quarta-feira, shorts diversos, os conjuntos de problemas, as orientações, PDFs. Além disso, como você vê aqui, traduções automáticas transcrições de inglês para chinês, japonês, espanhol, italiano, e um bando inteiro de outras línguas que certamente vai ser imperfeito como nós rolamos-los programaticamente usando uma coisa chamada API, ou interface de programação de aplicativo, do Google que nos permite converter Inglês para essas outras línguas. Mas, graças ao maravilhoso espírito de alguns voluntários mais de cem, pessoas aleatórias na Internet que gentilmente oferecidos a se envolver Neste projeto, nós vamos ser gradualmente melhorar a qualidade dessas traduções por ter humanos corrigir os erros que nossos computadores fizeram. Assim, verifica-se que havia alguns estudantes mais aparecer na segunda-feira do que o inicialmente esperado. Na verdade, agora CS50x tem 100.000 pessoas que seguem junto em casa. Então, percebe que são todos parte dessa aula inaugural de fazer este curso de ciência da computação educação mais geralmente, de forma mais ampla, acessível. E a realidade é agora, com alguns desses cursos massivos online, todas elas começam com estes números muito elevados, como parece ter feito aqui. Mas o objetivo, em última instância, para CS50x é realmente levar as pessoas como muitos a linha de chegada quanto possível. Pelo projeto, CS50x vai ser oferecido a partir desta segunda-feira passada todo o caminho até 15 de abril de 2013, para que as pessoas que têm compromissos escolares em outros lugares, trabalho, a família, os conflitos outros e semelhantes, tem um pouco mais de flexibilidade com o qual a mergulhar neste curso, que, basta dizer, é bastante ambiciosa feito apenas ao longo de apenas três meses, durante um semestre de costume. Mas esses alunos serão enfrentar os conjuntos mesmo problema, vendo o mesmo conteúdo, ter acesso aos mesmos calções e semelhantes. Então, percebemos que todos nós somos verdadeiramente juntos nessa. E um dos objetivos finais de CS50x não é só para ter pessoas como muitos para a linha de chegada e dar-lhes essa nova compreensão da ciência da computação e programação, mas também para que eles têm essa experiência compartilhada. Uma das características definidoras de 50 no campus, esperamos, foi este tipo de experiência comum, para melhor ou para pior, às vezes, mas ter essas pessoas a voltar-se para a esquerda e para a direita, e as horas de expediente e Hackathon e da feira. É um pouco mais difícil de fazer isso pessoalmente com pessoas on-line, mas CS50x vai concluir em abril, com a primeira CS50 Expo, que será uma adaptação online da nossa idéia da feira onde estes milhares de estudantes todos serão convidados a apresentar uma 1 - a 2 minutos de vídeo, ou um screencast de seu projeto final ou vídeo deles acenando Olá e falar sobre seu projeto e demos-lo, bem como os seus antecessores fizeram aqui no campus da feira, de modo que até o final do semestre, a esperança é ter uma exposição global de projetos dos alunos CS50x 'finais, bem como aquele que o espera em dezembro aqui no campus. Assim, mais do que em próximos meses. Com 100.000 estudantes, porém, vem a necessidade de uma CAs mais alguns. Dado que vocês estão abrindo a trilha aqui e tendo CS50 várias semanas antes do lançamento deste material para as pessoas em EDX, perceber que gostaríamos de envolver como muitos de nossos próprios alunos quanto possível a esta iniciativa, tanto durante o semestre, assim como neste inverno e na próxima Primavera. Então, se você gostaria de se envolver em CS50x, juntando-se particularmente em CS50x discutir, a versão de EDX CS50 discutir, que muitos de vocês estão usando no campus, no quadro de avisos online, por favor, faça a cabeça para essa URL, deixe-nos saber quem você é, porque nós adoraríamos para construir uma equipe de alunos e funcionários e professores iguais no campus que estão simplesmente jogando bem e ajudando. E quando vêem uma questão que é familiar a eles, você ouve um estudante relatar algum bug em algum lugar lá fora, em algum país na Internet, e que toca uma campainha porque você também teve que mesmo assunto em seu d-hall, há algum tempo, espero, então você pode dialogar e partilhar a sua própria experiência. Então por favor não participar se você gostaria. Cursos de ciência da computação na Universidade de Harvard tem um pouco de uma tradição, CS50 entre eles, de ter algum fato, algumas roupas, que você pode usar com orgulho no final do semestre, dizendo com um certo orgulho que você terminou CS50 e tomou CS50 e afins, e nós tentamos sempre envolver os alunos neste processo, tanto quanto possível, em que convidamos, nessa época do semestre, os alunos a apresentarem projetos usando o Photoshop, ou qualquer ferramenta de escolha que você gostaria de usar se você é um designer, a submeter projetos para T-shirts e camisolas e guarda-sóis e bandanas para cães pequenos que temos agora e similares. E tudo é então - os vencedores de cada ano são, então, exibiu no site do curso em store.cs50.net. Tudo é vendido ao custo de lá, mas o site só funciona sozinho e permite que as pessoas a escolher as cores e desenhos que eles gostam. Então eu pensei que tinha acabado de partilhar alguns dos projetos do ano passado que estavam no site além deste aqui, que é uma tradição anual. "Todo dia eu estou Seg Faultn" era uma das propostas do ano passado, que ainda está disponível lá para ex-alunos. Tivemos um presente ", CS50, Fundação 1989." Um dos nossos Bowdens, Rob, era muito popular no ano passado. "Team Bowden" nasceu, este projeto foi submetido, entre os mais vendidos. Como foi este aqui. Muitas pessoas tiveram "Fever Bowden" de acordo com os registros de vendas. Perceba que que poderia agora ser seu projeto lá, em cima da Internet. Mais detalhes sobre este problema na próxima define por vir. Mais uma ferramenta: você teve alguma exposição e espero que agora alguma experiência hands-on com o GDB, que é, naturalmente, um depurador e permite que você manipule o seu programa em um nível bastante baixo, fazendo o tipo de coisas? O que o GDB deixar você fazer? Sim? Dê-me alguma coisa. [Responder Estudante, ininteligível] Bom. Etapa em função, para que você não só tem que digitar run e ter o golpe programa através do seu conjunto, imprimir coisas para a saída padrão. Em vez disso, você pode percorrê-lo linha por linha, digitando próxima ir linha por linha por linha ou passo para mergulhar em uma função, normalmente aquele que você escreveu. O que mais faz GDB deixar você fazer? Sim? [Responder Estudante, ininteligível] Imprimir variáveis. Então, se você quer fazer um pouco de introspecção dentro de seu programa sem ter que recorrer a escrever instruções printf em todo o lugar, você pode apenas imprimir uma variável ou exibir uma variável. O que mais você pode fazer com um depurador como o GDB? [Responder Estudante, ininteligível] Exatamente. Você pode definir pontos de interrupção, você pode dizer que a execução pausa a função principal ou a função foo. Você pode dizer que a execução pausa na linha 123. E pontos de interrupção são uma técnica muito poderosa porque se você tem uma sensação geral de que o seu problema provavelmente é, você não precisa perder tempo percorrendo totalidade do programa. Você pode pular essencialmente à direita e então começar a escrever - percorrendo-a com passo ou próximo ou semelhante. Mas o problema com algo parecido com o GDB é que ele ajuda você, o humano, encontrar os seus problemas e encontrar seus bugs. Isso não significa necessariamente encontrá-los muito por você. Então, nós introduzimos o style50 outro dia, que é uma ferramenta de linha de comando curta que tenta estilizar seu código um pouco mais limpa do que você, o humano, poderia ter feito. Mas isso, também, é realmente apenas uma coisa estética. Mas acontece que há essa outra ferramenta chamada Valgrind que é um pouco mais misterioso de usar. Sua saída é atrozmente enigmática, à primeira vista. Mas é maravilhosamente útil, especialmente agora que estamos na parte do termo onde você está começando a usar malloc e alocação dinâmica de memória. As coisas podem dar muito, muito errado rapidamente. Porque se você esquecer de libertar a sua memória, ou você cancelar a referência de algum ponteiro NULL, ou você cancelar a referência de algum ponteiro de lixo, que normalmente é o sintoma que resultados? Seg culpa. E você começa este arquivo núcleo de algum número de kilobytes ou megabytes que representa o estado da memória do seu programa quando ele caiu, mas o seu programa, em última análise seg falhas, falha de segmentação, o que significa que algo de ruim aconteceu quase sempre relacionados a um erro relacionado com a memória que você fez em algum lugar. Então Valgrind ajuda a encontrar coisas como esta. É uma ferramenta que você execute, como GDB, depois de ter compilado seu programa, mas em vez de executar o programa diretamente, você corre Valgrind e você passar para ele o seu programa, assim como você faz com o GDB. Agora, o uso, para obter o melhor tipo de saída, é um pouco longo, por isso lá no topo da tela, você verá Valgrind-v. "-V" quase universalmente significa verbose quando você está usando programas em um computador Linux. Então isso significa cuspir mais dados do que você pode, por padrão. "- Leak-check = total". Este é apenas dizer seleção para todos os possíveis vazamentos de memória, erros que eu poderia ter feito. Isto, também, é um paradigma comum com programas Linux. Geralmente, se você tem um argumento de linha de comando que é um "interruptor", que deveria mudar o comportamento do programa, e é uma única letra, é-v, mas se isso está ligado, apenas pelo design do programador, é uma palavra completa ou série de palavras, o argumento de linha de comando começa com -. Estes são apenas convenções humanas, mas você vai vê-los cada vez mais. E, em seguida, finalmente, "a.out" é o nome arbitrário para o programa, neste exemplo particular. E aqui vai uma saída representativa. Antes de olharmos para o que isso significa, deixe-me ir para um trecho de código aqui. E deixe-me passar esta fora do caminho, em breve, e vamos dar uma olhada em memory.c, que é este pequeno exemplo aqui. Portanto, neste programa, deixe-me zoom e as funções e perguntas. Nós temos uma função principal que chama uma função, f, e então o que se f continuar a fazer, em Inglês um pouco técnico? O que faz f proceder para fazer? Que tal eu vou começar com a linha 20, e localização da estrela não importa, mas eu só vou ser coerente aqui com última palestra. Qual é a linha 20 não para nós? No lado da mão esquerda. Vamos dividi-la ainda mais. Int * x: o que é que faz? Okay. É declarar um ponteiro, e agora vamos ser ainda mais técnico. O que significa, muito concretamente, para declarar um ponteiro? Alguém mais? Sim? [Responder Estudante, ininteligível] Muito longe. Então você está lendo para o lado direito do sinal de igual. Vamos nos concentrar apenas na esquerda, apenas em int * x. Isso significa "declarar" um ponteiro, mas agora vamos mergulhar mais fundo para essa definição. O que isso concretamente, tecnicamente significa? Sim? [Responder Estudante, ininteligível] Okay. Ele está se preparando para gravar um endereço na memória. Bom. E vamos dar um passo adiante, que é declarar uma variável, x, que é de 32 bits. E eu sei que é de 32 bits porque -? Não é porque é um int, porque é um ponteiro neste caso. Coincidência que é um eo mesmo com um int, mas o fato de que não é a estrela que significa que este é um ponteiro e no interior do aparelho, como acontece com muitos computadores, mas não todas, as indicações são de 32 bits. Em mais hardware moderno, como os mais recentes Macs, os mais recentes PCs, você pode ter ponteiros de 64 bits, mas no aparelho, essas coisas são de 32 bits. Então, vamos padronizar isso. Mais concretamente, a história é a seguinte: Nós "declarar" um ponteiro, o que é que isso significa? Nós nos preparamos para armazenar um endereço de memória. O que significa isso? Nós criamos uma variável chamada x, que ocupa 32 bits que em breve armazenar o endereço de um inteiro. E isso é provavelmente tão preciso quanto podemos chegar. É bom avançar para simplificar o mundo e dizer declarar um ponteiro chamado x. Declare um ponteiro, mas perceber e entender o que está realmente acontecendo mesmo em apenas alguns desses personagens. Agora, este é quase um pouco mais fácil, mesmo que seja uma mais expressão. Então o que é que esta fazendo, que é destaque agora: "malloc (10 * sizeof (int));" Sim? [Responder Estudante, ininteligível] Bom. E eu vou levá-lo lá. É atribuição de um bloco de memória para 10 inteiros. E agora vamos mergulhar em um pouco mais profunda, que é alocar um bloco de memória para 10 inteiros. O que é malloc depois retornar? O endereço do bloco, ou, de forma mais concreta, o endereço do primeiro byte do referido pedaço. Como, então, sou eu, o programador, para saber onde esse pedaço de fins de memória? Eu sei que é contíguo. Malloc, por definição, lhe dará um pedaço contíguo de memória. Nenhum lacunas. Você tem acesso a todos os bytes nesse pedaço, de costas para trás, mas como eu sei que o fim deste pedaço de memória é? Quando você usa malloc? [Responder Estudante, ininteligível] Boa. Você não. Você tem que se lembrar. Eu tenho que lembrar que eu usei o valor 10, e eu não parecem mesmo ter feito isso aqui. Mas a responsabilidade é inteiramente em mim. Strlen, que nos tornamos um pouco dependente para cordas, só funciona por causa dessa convenção de ter \ 0 ou este caráter especial nul, NUL, no final de uma string. Isso não vale para apenas pedaços arbitrários de memória. Cabe a você. Assim, a linha 20, então, aloca um bloco de memória que pode armazenar 10 inteiros, e armazena o endereço do primeiro byte desse pedaço de memória na variável x chamado. Logo, o que é um ponteiro. Então, linha 21, infelizmente, foi um erro. Mas, primeiro, o que ele está fazendo? É dizer loja no local 10, 0 indexados, do bloco de memória chamado x o valor 0. Então, observe algumas coisas estão acontecendo. Mesmo que x é um ponteiro, lembrar de algumas semanas atrás que você ainda pode usar a matriz estilo de notação de colchete. Porque isso é realmente curto-mão notação para a aritmética de ponteiro mais crítico para o futuro. onde iríamos fazer algo como isto: Pegue o endereço x, mover mais de 10 pontos, em seguida, ir para lá a qualquer endereço é armazenado no local. Mas, francamente, este é apenas atroz de ler e se sentir confortável com. Assim, o mundo geralmente usa os colchetes só porque ele é muito mais humano-amigável para ler. Mas isso é o que realmente está acontecendo debaixo do capô; x é um endereço não, uma matriz, de per si. Portanto, este é armazenar 0 na posição 10 em x. Por que isso é ruim? Sim? [Responder Estudante, ininteligível] Exatamente. Nós só alocados 10 ints, mas contar de 0 ao programar em C, para que você tenha acesso a 0 10 1 2 3 4 5 6 7 8 9, mas não. Assim, ou o programa vai culpa seg ou não é. Mas nós realmente não sabemos, este é um tipo de comportamento não determinístico. Isso realmente depende se temos sorte. Se se verificar que o sistema operacional não se importa se eu usar esse byte extra, mesmo que não tenha dado para mim, o meu programa não pode falhar. É cru, é buggy, mas você não pode ver esse sintoma, ou você pode vê-lo só de vez em quando. Mas a realidade é que o bug é, de fato, não há. E é realmente problemático se você escreveu um programa que você quer ser correto, que você vendeu o programa que as pessoas estão usando que de vez em quando cai porque, é claro, este não é boa. De fato, se você tem um celular com Android ou um iPhone e você baixar aplicativos nos dias de hoje, se você já teve um app abortar, de repente ele desaparece, que é quase sempre o resultado de algum problema relacionado à memória, qual o programador asneira e dereferenced um ponteiro que ele ou ela não deve ter, eo resultado do iOS ou Android é apenas para matar o programa completo em vez de comportamento indefinido risco ou algum tipo de comprometimento da segurança. Há um outro bug no programa além deste. O que mais eu estraguei tudo neste programa? Eu não pratiquei o que eu tenho pregado. Sim? [Responder Estudante, ininteligível] Boa. Eu não libertou a memória. Portanto, a regra de ouro agora tem que ser sempre que você chamar malloc, você deve chamar livre quando você é feito usando a memória. Agora, quando eu iria querer libertar esta memória? Provavelmente, assumindo que esta primeira linha foi correta, eu gostaria de fazê-lo aqui. Porque eu não poderia, por exemplo, faça-o aqui. Por quê? Apenas fora do escopo. Assim, mesmo que estamos falando de ponteiros, esta é uma semana 2 ou 3 questão, em que x é apenas um alcance dentro das chavetas onde foi declarado. Então você definitivamente não pode libertá-lo lá. Minha única chance de libertá-la é de aproximadamente após a linha 21. Este é um programa bastante simples, era bastante fácil, uma vez que o tipo de enrolado sua mente em torno do que o programa está fazendo, onde os erros foram. E mesmo se você não vê-lo em primeiro lugar, espero que seja um pouco óbvio agora que esses erros são muito facilmente resolvidos e facilidade. Mas quando um programa é mais do que 12 linhas de tempo, é 50 linhas, 100 linhas, andar através de seu código linha por linha, pensando por isso, logicamente, é possível, mas não particularmente divertido de fazer, constantemente à procura de bugs, e também é difícil de fazer, e é por isso que uma ferramenta como Valgrind existe. Deixe-me ir em frente e fazer isso: deixe-me abrir a janela de terminal, e deixe-me não apenas executar memória, porque a memória parece estar bem. Eu estou tendo sorte. Indo para o byte adicional no fim da matriz não parece ser muito problemático. Mas deixe-me, no entanto, fazer uma verificação de sanidade mental, o que significa apenas para verificar se este é ou não realmente correto. Então vamos fazer valgrind-v - leak-check = completo, e, em seguida, o nome do programa, neste caso, é a memória, e não a.out. Então deixe-me ir em frente e fazer isso. Pressione Enter. Querido Deus. Esta é a sua saída, e é isso que me referi anteriormente. Mas, se você aprender a ler através de todos os disparates aqui, mais isso é apenas a saída de diagnóstico que não é tão interessante. O seu olho realmente quer estar procurando é qualquer menção de erro ou inválido. Palavras que sugerem problemas. E, de fato, vamos ver o que está acontecendo de errado aqui. Eu tenho um resumo de algum tipo, "em uso na saída:. 40 bytes em blocos de 1" Eu não tenho certeza do que um bloco é ainda, mas 40 bytes realmente se sente como se eu pudesse descobrir de onde que vem. 40 bytes. Por que 40 bytes em uso na saída? E, mais especificamente, se rolar aqui, por que eu definitivamente perdeu 40 bytes? Sim? [Responder Estudante, ininteligível] Perfeito. Sim, exatamente. Havia dez números inteiros, e cada um destes é o tamanho de 4 ou 32 bits, então eu perdi exatamente 40 bytes, porque, como você propôs, eu não chamei livre. Isso é um erro, e agora vamos olhar para baixo um pouco mais e ver ao lado deste, "Inválido escrever de tamanho 4". Agora, o que é isso? Este endereço é expresso que a notação de base, aparentemente? Este é hexadecimal, ea qualquer momento você vê um número começando com 0x, isso significa hexadecimal, o que fizemos no caminho de volta, eu acho, seção pset 0 de perguntas, que era apenas para fazer um exercício de aquecimento, a conversão de decimal para hexadecimal para binário e assim por diante. Hexadecimal, apenas por convenção humana, é geralmente usado para representar ponteiros ou, de modo mais geral, aborda. É apenas uma convenção, porque é um pouco mais fácil de ler, é um pouco mais compacto do que algo como decimal, e binário é inútil para a maioria dos seres humanos de usar. Então agora o que isso significa? Bem, parece que há uma gravação inválido de tamanho 4 na linha 21 de memory.c. Então vamos voltar para a linha 21, e, de fato, é aqui que a gravação inválido. Então Valgrind não vai completamente segura minha mão e me diga o que a correção é, mas ele está detectando que eu estou fazendo uma gravação inválido. Estou tocando 4 bytes que eu não deveria ser, e, aparentemente, isso porque, como você apontou, eu estou fazendo [10] em vez de [9] maximamente ou [0] ou algo entre os dois. Com Valgrind, realizar qualquer momento que você está escrevendo um programa que usa ponteiros e utiliza a memória, e mais especificamente malloc, definitivamente o hábito de correr tanto tempo mas muito facilmente copiado e colado comando do Valgrind para ver se há alguns erros lá. E vai ser esmagadora cada vez que você ver a saída, mas apenas analisar visualmente através de toda a saída e veja se você ver menções de erros ou avisos ou inválido ou perdido. Quaisquer palavras que soam como você errou em algum lugar. Então percebe que é uma nova ferramenta em seu toolkit. Agora na segunda-feira, tivemos um monte de gente veio aqui e representar a noção de uma lista ligada. E introduzimos a lista ligada como uma solução para o problema? Sim? [Responder Estudante, ininteligível] Boa. Matrizes não podem ter memória adicionados a eles. Se você alocar uma matriz de tamanho 10, que é tudo que você conseguir. Você pode chamar uma função como realloc se inicialmente chamada malloc, e que pode experimentar a crescer a matriz, se houver espaço para o fim de que que ninguém mais está usando e, se não há, ela só vai encontrar um pedaço maior em outro lugar. Mas então ele vai copiar todos os bytes para a nova matriz. Isso soa como uma solução muito correta. Por que isso é pouco atraente? Quero dizer que funciona, os seres humanos têm resolvido este problema. Por que temos que resolver isso na segunda-feira com listas ligadas? Sim? [Responder Estudante, ininteligível] Pode levar um longo tempo. Na verdade, a qualquer momento que você está chamando malloc calloc ou realloc ou, o que é ainda um outro, qualquer momento que você, o programa, está falando com o sistema operacional, você tende a tornar o programa lento. E se você está fazendo esses tipos de coisas em loops, você está realmente abrandar as coisas. Você não vai perceber isso por mais simples de "Hello World" programas do tipo, mas em programas muito maiores, pedindo que o sistema operacional novo e de novo para a memória ou dando-lhe de volta uma e outra vez tende a não ser uma coisa boa. Além disso, é apenas uma espécie de intelectual - é um completo desperdício de tempo. Por que alocar mais memória e mais risco, copiar tudo para a nova matriz, se você tem uma alternativa que permite alocar memória apenas o quanto você realmente precisa? Portanto, há prós e contras aqui. Uma das vantagens é que agora temos dinamismo. Não importa de onde os pedaços de memória são de que estão livres, Eu só posso classificar de criar estas migalhas de pão através de ponteiros amarrar minha lista inteira ligados. Mas eu pagar pelo menos um preço. O que eu tenho a dar-se na obtenção de listas ligadas? Sim? [Responder Estudante, ininteligível] Boa. Você precisa de mais memória. Agora eu preciso de espaço para estas indicações, e no caso de esta lista super simples ligado que está apenas a tentar armazenar números inteiros, que são 4 bytes, que continua dizendo bem, um ponteiro é de 4 bytes, então agora eu tenho literalmente dobrou a quantidade de memória que eu preciso apenas para armazenar esta lista. Mas, novamente, esta é uma troca constante em ciência da computação entre tempo e espaço e esforço de desenvolvimento, e outros recursos. O que é outra desvantagem de usar uma lista ligada? Sim? [Responder Estudante, ininteligível] Bom. Não é tão fácil de acessar. Nós não podemos mais alavancagem Semana 0 princípios como dividir e conquistar. E, mais especificamente, a pesquisa binária. Porque mesmo que nós, seres humanos pode ver mais ou menos onde a meio da lista é, o computador só sabe que esta lista ligada começa no endereço chamado primeiro. E isso é 0x123 ou algo parecido. E a única maneira que o programa pode encontrar o elemento do meio é realmente procurar a lista inteira. E mesmo assim, ele literalmente tem que pesquisar a lista inteira porque mesmo quando chegar o elemento do meio, seguindo os ponteiros, você, o programa, não tem idéia de quanto tempo essa lista é, potencialmente, até chegar ao final do mesmo, e como você sabe de programação que está no final de uma lista ligada? Há um ponteiro especial NULL, portanto, novamente, uma convenção. Em vez de usar esse ponteiro, nós definitivamente não queremos que seja algum valor lixo apontando para fora do palco em algum lugar, nós queremos que seja mão para baixo, NULL, de modo que temos este terminal nesta estrutura de dados para sabermos onde ela termina. O que se quer manipular isso? Fizemos a maior parte deste visualmente, e com os seres humanos, mas o que se quer fazer uma inserção? Assim, a lista original era de 9, 17, 20, 22, 29, 34. E se nós então queria espaço malloc para o número 55, um nó para ele, e então nós queremos inserir 55 na lista, assim como fizemos na segunda-feira? Como podemos fazer isso? Bem, Anita veio e ela caminhou essencialmente da lista. Ela começou no primeiro elemento, então o próximo, o próximo, o outro, o próximo, o próximo. Finalmente atingiu a mão esquerda todo o caminho e percebi oh, isso é NULL. Então, o que a manipulação de ponteiros precisava ser feito? A pessoa que estava no fim, número 34, precisava de sua mão esquerda levantada para apontar para 55, 55 precisavam de seu braço esquerdo apontando para baixo para ser o novo terminador nulo. Concluído. Muito fácil de inserir em uma lista de 55 classificados. E como isso pode olhar? Deixe-me ir em frente e abrir algum exemplo de código aqui. Vou abrir o gedit, e deixe-me abrir dois arquivos primeiro. Um é list1.h, e deixe-me lembrar que este foi o pedaço de código que usamos para representar um nó. Um nó tem tanto um int chamado n e um ponteiro chamado em seguida que apenas pontos para a próxima coisa na lista. Que agora está em um arquivo h.. Por quê? Há essa convenção, e não temos aproveitado este uma enorme quantidade de nós mesmos, mas a pessoa que escreveu funções printf e outros deu como um presente para o mundo todas essas funções por escrever um arquivo chamado stdio.h. E depois há string.h, e então há map.h, e há todos esses arquivos h que você pode ter visto ou usado durante o prazo escritos por outras pessoas. Normalmente nos. Arquivos h são apenas coisas como typedefs ou declarações de tipos personalizados ou declarações de constantes. Você não colocar implementações funções 'em arquivos de cabeçalho. Você coloca, em vez disso, apenas os seus protótipos. Você coloca as coisas que você deseja compartilhar com o mundo o que eles precisam para compilar o seu código. Então, só para chegar a este hábito, decidimos fazer a mesma coisa. Não há muito em list1.h, mas nós colocamos algo que pode ser do interesse de pessoas no mundo que querem usar a nossa implementação lista encadeada. Agora, em list1.c, eu não vou passar por essa coisa toda porque é um pouco longo, este programa, mas vamos executá-lo real rapidamente no prompt. Deixe-me compilar list1, deixe-me em seguida, executar list1, eo que você vai ver é temos um programa de simulação simples pouco aqui que vai me permite adicionar e remover números a uma lista. Então deixe-me ir em frente e digite 3 para a 3 opção de menu. Quero inserir o número - vamos fazer o primeiro número, que foi de 9, e agora eu sou informado a lista é agora 9. Deixe-me ir em frente e fazer outra inserção, então eu bati opção de menu 3. Qual o número que eu quero inserir? 17. Enter. E eu vou fazer só mais um. Deixe-me inserir o número 22. Portanto, temos o início da lista encadeada que tínhamos em forma de slides um momento atrás. Como é que esta inserção realmente acontecendo? De facto, 22 é agora no fim da lista. Assim, a história que contou no palco na segunda-feira e só agora recapitulou deve realmente estar acontecendo no código. Vamos dar uma olhada. Deixe-me rolar neste arquivo. Nós vamos passar por cima algumas das funções, mas nós vamos descer para, digamos, a função de inserção. Vamos ver como nós vamos sobre a inserção de um novo nó para esta lista ligada. Onde está a lista declarada? Bem, vamos percorrer todo o caminho até ao topo, e perceber que a minha lista ligada essencialmente declarado como um ponteiro único que é inicialmente NULL. Então, eu estou usando uma variável global aqui, que em geral temos pregado contra porque faz com que o seu código um pouco confuso para manter, é uma espécie de preguiça, normalmente, mas não é preguiçoso e não é errado e não é ruim se o propósito único de seu programa na vida é para simular uma lista ligada. Que é exatamente o que estamos fazendo. Então ao invés de declarar isso em principal e depois ter de passá-lo para cada função temos escrito neste programa, em vez perceber oh, vamos torná-lo global porque todo o propósito deste programa é demonstrar uma e apenas uma lista ligada. Então, que se sente bem. Aqui estão os meus protótipos, e não vamos passar por tudo isso, mas eu escrevi uma função de exclusão, uma função de encontrar, uma função de inserção, e uma função de travessia. Mas vamos agora voltar-se para a função de inserção e ver como este funciona aqui. Inserção é on line - aqui vamos nós. Inserir. Então, não é preciso nenhum argumento, porque nós vamos pedir o interior usuário desta função para o número que deseja inserir. Mas, primeiro, nos preparamos para dar-lhes um pouco de espaço. Esta é uma espécie de copiar e colar do outro exemplo. Nesse caso, fomos atribuição de um int, desta vez estamos alocando um nó. Eu realmente não me lembro quantos bytes um nó é, mas isso é bom. Sizeof pode descobrir isso para mim. E por que estou verificando NULL na linha 120? O que poderia dar errado na linha 119? Sim? [Responder Estudante, ininteligível] Bom. Só poderia ser o caso que eu pedi muita memória ou algo está errado eo sistema operacional não tem bytes suficiente para me dar, por isso sinaliza tanto por retornar nulo, e se eu não verificar que e eu apenas cega continuar a usar o endereço retornado, pode ser NULL. Poderia ser algum valor desconhecido, não é uma boa coisa a menos que eu - na verdade, não será um valor desconhecido. Pode ser NULL, então eu não quero a abusar dela e arriscar dereferencing-lo. Se isso acontecer, eu só voltar e vamos fingir que eu não voltar qualquer memória de todos. Caso contrário, eu digo o usuário me dar um número para inserir, eu chamo a nossa GetInt velho amigo, e então esta foi a nova sintaxe que introduziu na segunda-feira. 'Newptr-> n' significa ter o endereço que lhe foi fornecido por malloc que representa o primeiro byte de um objecto novo nó, e depois ir para o campo chamado n. Uma questão pouco trivial: Este é equivalente ao que linha mais enigmática do código? Como poderia eu ter escrito isso? Quer dar uma facada? [Responder Estudante, ininteligível] Bom. Usando o n., Mas não é tão simples como isso. O que eu primeiro preciso fazer? [Responder Estudante, ininteligível] Bom. Eu preciso fazer newptr.n *. Portanto, este novo ponteiro está dizendo é, obviamente, um endereço. Por quê? Porque ele foi devolvido por malloc. O newptr * dizendo "vá lá", e, em seguida, uma vez que você estiver lá, então você pode usar o mais familiar. n, mas isso só parece um pouco feio, especialmente se nós, seres humanos vão desenhar os ponteiros com as setas todo o tempo, o mundo tem padronizado nesta notação de seta, que faz exatamente a mesma coisa. Assim, você só usar o - notação> quando a coisa da esquerda é um ponteiro. Caso contrário, se é uma estrutura real, use o n.. E depois este: Por que eu inicializar newptr-> ao lado nulo? Nós não queremos uma mão pendurada esquerda fora da final da etapa. Queremos que ele apontando diretamente para baixo, o que significa o fim desta lista poderia ser neste nó, então é melhor ter certeza que é NULL. E, em geral, inicializar suas variáveis ​​ou membros de dados e estruturas a algo é apenas uma boa prática. Apenas deixar lixo existem e continuarão a existir, geralmente você fica em apuros se você se esquecer de fazer alguma coisa mais tarde. Aqui está alguns casos. Isso, novamente, é a função de inserção, ea primeira coisa que eu verificar é se a variável chamada primeiro, essa variável global é NULL, que significa que não há lista ligada. Nós não inseriu nenhum número, por isso é trivial para inserir este número atual na lista, porque apenas pertence no início da lista. Então, isso foi quando Anita estava em pé aqui sozinho, fingindo não havia mais ninguém aqui no palco até alocamos um nó, então ela poderia levantar a mão pela primeira vez, se todo mundo tivesse vindo no palco depois de sua segunda-feira. Agora, aqui, este é um cheque pequeno onde eu tenho que dizer se o valor do novo nó de n é seguinte, o que significa ir para a estrutura que está sendo apontado por newptr, então aqui estamos nós, vá lá. Em seguida, a seta está dizendo obter o próximo campo, e então a = está dizendo colocar o valor lá? O valor que estava em primeiro, qual o valor que estava em primeiro lugar? Primeiro foi apontando para esse nó, o que significa que este deve agora apontar para este nó. Em outras palavras, o que parece ainda uma bagunça ridículo com a minha letra, o que é uma idéia simples de apenas mover essas setas ao redor traduz em código com apenas forro este. Armazenar o que está em primeiro no campo ao lado e então atualizar o primeiro realmente é. Vamos em frente e avançar rapidamente um pouco disso, e olhar apenas para essa inserção da cauda para agora. Suponha que eu chegar ao ponto em que eu achar que o próximo campo de algum nó é NULL. E neste ponto da história, um detalhe que eu estou passando por cima é que eu introduzi outro ponteiro-se aqui na linha 142, ponteiro antecessor. Essencialmente, neste ponto da história, uma vez que a lista é longa, Eu meio que preciso andar com dois dedos, porque se eu for muito longe, lembre-se em uma única lista de comprimento, você não pode ir para trás. Então essa idéia de predptr é o meu dedo para a esquerda, e newptr - não newptr. Outro indicador que está aqui é o meu outro dedo, e eu sou apenas um tipo de andar a lista. É por isso que existe. Mas vamos considerar apenas um dos casos mais simples aqui. Se o campo seguinte que ponteiro é NULL, o que é a implicação lógica? Se você está atravessando esta lista e você bater um ponteiro NULL? Você está no fim da lista, e assim o código para então acrescentar este elemento adicional é uma espécie de intuitiva terá que nó cuja próxima ponteiro é NULL, por isso este é atualmente NULL, e alterá-lo, embora, para ser o endereço do novo nó. Então, estamos apenas desenhando no código da seta que traçamos no palco, levantando a mão esquerda de alguém. E o caso que eu vou acenar as mãos menos por enquanto, só porque eu acho que é fácil se perder quando o fazemos neste tipo de ambiente, é a verificação de inserção no meio da lista. Mas apenas de forma intuitiva, o que deve acontecer se você quiser descobrir onde um número pertence no meio é que você tem que caminhar com mais de um dedo, mais de um ponteiro, descobrir onde ele pertence, a verificação é o elemento O atual, e uma vez que você encontrar esse lugar, então você tem que fazer esse tipo de jogo de conchas onde você move os ponteiros em torno de muito cuidado. E essa resposta, se você gostaria de razão por este em casa no seu próprio país, se resume apenas a essas duas linhas de código, mas a ordem das linhas é super importante. Porque se você soltar a mão de alguém e levantar outra pessoa na ordem errada, novamente, você pode acabar orfandade da lista. Para resumir mais conceitualmente, a inserção na cauda é relativamente simples. A inserção na cabeça também é relativamente simples, mas você precisa atualizar um ponteiro adicional neste momento para espremer o número 5 na lista aqui, e, em seguida, a inserção no meio envolve um esforço ainda maior, para inserir cuidadosamente o número 20 na sua posição correcta, que é entre 17 e 22. Então, você precisa fazer algo como ter o novo nó de ponto de 20 a 22, e, em seguida, o ponteiro que nó precisa ser atualizado passado? É 17, de realmente inseri-lo. Então, novamente, eu vou adiar o código real para que a implementação particular. À primeira vista, é um pouco assustador, mas é realmente apenas um ciclo infinito que é looping, looping, looping, looping, e quebrando assim que bateu o ponteiro NULL, em que ponto você pode fazer a inserção necessária. Este, então, é o código de inserção representante lista ligada. Que era uma espécie de um lote, e parece que nós resolvemos um problema, mas nós introduzimos um totalmente diferente. Francamente, nós passamos todo esse tempo em grande O e Ω e correndo o tempo, tentando resolver problemas mais rapidamente, e aqui estamos dando um grande passo para trás, ele se sente. E, no entanto, se o objetivo é armazenar dados, parece que o Santo Graal, como dissemos na segunda-feira, seria realmente para guardar coisas instantaneamente. Na verdade, acho que fizemos colocar lista de lado ligado por um momento e nós, em vez introduziu a noção de uma mesa. E vamos pensar em uma mesa por um momento como uma matriz. Esta matriz e neste caso aqui tem cerca de 26 elementos, de 0 a 25, e suponha que você precisava de algum pedaço de armazenamento de nomes: Alice e Bob e Charlie e similares. E você precisa de alguma estrutura de dados para armazenar esses nomes. Bem, você poderia usar algo como uma lista ligada e você pode percorrer a lista de inserir Alice antes de Bob e Charlie depois de Bob e assim por diante. E, de fato, se você quiser ver o código assim como um aparte, sei que em list2.h, fazemos exatamente isso. Nós não vai passar por esse código, mas esta é uma variante do primeiro exemplo que introduz uma outra struct que já vimos antes estudante chamado, e então o que realmente armazena na lista vinculada é um ponteiro para uma estrutura de estudante em vez de inteiro um pouco simples, n. Então, percebo que há código lá que envolve cordas reais, Mas se o objetivo em mãos realmente agora é resolver o problema da eficiência, Não seria bom se nós estamos dando um objeto chamado Alice, queremos colocá-la no local certo, em uma estrutura de dados, parece que seria muito bom para apenas colocar Alice, cujo nome começa com A, no primeiro local. E Bob, cujo nome começa com B, na segunda posição. Com uma matriz, ou vamos começar chamando-o de uma tabela, uma tabela hash em que, nós podemos fazer exatamente isso. Se nos é dado um nome como Alice, uma seqüência como Alice, onde você põe A-l-i-c-e? Precisamos de um hueristic. Precisamos de uma função para tirar alguma entrada como Alice e retornar uma resposta, "Alice Coloque neste local." E esta função, esta caixa preta, vai ser chamado de função hash. Uma função hash é algo que tem uma entrada, como "Alice", e volta para você, normalmente, a localização numérica em alguma estrutura de dados onde Alice pertence. Neste caso, a função hash deve ser relativamente simples. Nossa função hash deve dizer, se você está dado "Alice", que a personagem deveria me importar com? O primeiro. Então eu olho para [0], e então eu digo se [0] o caráter é A, retornar o número 0. Se for B, retornar 1. Se é C, o retorno 2, e assim por diante. Todos índice 0, e que me permita inserir Alice e Bob e Charlie e assim por diante para essa estrutura de dados. Mas há um problema. O que se Anita vem de novo? Onde colocamos Anita? Seu nome também começa com a letra A, e parece que fizemos uma confusão ainda maior do problema. Nós temos agora a inserção imediata, inserção constante de tempo, para uma estrutura de dados em vez de pior caso linear, mas o que podemos fazer com Anita neste caso? Quais são as duas opções, realmente? Sim? [Responder Estudante, ininteligível] Ok, então nós poderíamos ter outra dimensão. Isso é bom. Assim, podemos construir coisas em 3D como falamos verbalmente na segunda-feira. Poderíamos acrescentar um outro acesso aqui, mas acho que não, eu estou tentando manter isso simples. O objetivo geral aqui é ter acesso constante de tempo imediato, de modo que é a adição de muita complexidade. Quais são as outras opções ao tentar inserir Anita para esta estrutura de dados? Sim? [Responder Estudante, ininteligível] Boa. Então, nós poderíamos passar todo mundo para baixo, como Charlie cutuca baixo Bob e Alice, e então colocamos Anita onde ela realmente quer ser. É claro que, agora, há um efeito colateral dessa. Esta estrutura de dados é provavelmente útil não porque queremos inserir as pessoas uma vez mas porque queremos verificar se eles estão lá mais tarde se queremos imprimir todos os nomes na estrutura de dados. Nós vamos fazer alguma coisa com esses dados, eventualmente. Então agora nós meio que parafusado sobre Alice, que não é mais onde ela deveria estar. Nem é Bob, nem é Charlie. Então talvez isso não é uma boa idéia. Mas, na verdade, esta é uma opção. Nós poderíamos mudar todos para baixo, ou diabos, Anita chegou atrasado para o jogo, por que não vamos apenas colocar Anita aqui não, aqui não, aqui não, vamos colocá-la um pouco mais abaixo na lista. Mas, então, este problema começa a devolver novamente. Você pode ser capaz de encontrar Alice instantaneamente, com base em seu primeiro nome. E Bob instantaneamente, e Charlie. Mas então você olha para Anita, e você vê, hein, Alice está no caminho. Bem, deixe-me ver abaixo Alice. Bob não é Anita. Charlie não é Anita. Oh, há Anita. E se você continuar nesse trem da lógica toda a maneira, o que é o tempo de execução do pior caso de encontrar ou inserção de Anita para esta nova estrutura de dados? É O (n), certo? Porque, na pior das hipóteses, há Alice, Bob, Charlie. . . todo o caminho para alguém chamado "Y", por isso há apenas um ponto à esquerda. Felizmente, não temos um chamado de "Z", então colocamos Anita na parte inferior. Nós realmente não resolveu o problema. Então talvez nós precisamos introduzir esta terceira dimensão. E não é que, se nós não introduzir esta terceira dimensão, nós não podemos fazer isso perfeitamente, mas o Santo Graal vai estar recebendo constante de tempo de inserção e dinâmicos de modo a que as inserções não temos a hard-código uma matriz de tamanho 26. Podemos inserir tantos nomes como queremos, mas vamos dar o nosso intervalo de 5 minutos aqui e depois fazer isso corretamente. Tudo bem. Eu defini a história até muito artificialmente há escolhendo Alice e Bob e Charlie e Anita, cujo nome foi, obviamente, vai colidir com Alice. Mas a pergunta que terminou na segunda-feira com é apenas quão provável é que você deseja obter esses tipos de colisões? Em outras palavras, se começarmos a usar essa estrutura de tabela, que é realmente apenas uma matriz, neste caso, de 26 posições, E se nossos insumos são distribuídos uniformemente em vez? Não é artificialmente Alice e Bob e Charlie e David e assim por diante em ordem alfabética, é uniformemente distribuída ao longo de A a Z. Talvez nós vamos ter sorte e nós não vamos ter dois Um ou dois de B com probabilidade muito alta, mas como alguém apontou, se este problema generalizado e não 0-25 mas, digamos, de 0 a 364 ou 65, muitas vezes, o número de dias em um ano típico, e fez a pergunta: "Qual é a probabilidade de que dois de nós nesta sala tem a mesma data de aniversário?" Dito de outra forma, qual é a probabilidade de que dois de nós tem um nome que começa com A? O tipo de pergunta é a mesma, mas este espaço de endereços, este espaço de busca, é maior no caso de aniversários, porque temos tantos dias a mais no ano do que letras no alfabeto. Qual é a probabilidade de uma colisão? Bem, podemos pensar nisso por descobrir a matemática de forma oposta. Qual é a probabilidade de colisões não? Bem, essa expressão aqui diz que o que é a probabilidade se há apenas uma pessoa neste quarto, que tem um aniversário? É 100%. Porque se há apenas uma pessoa na sala, seu aniversário pode ser qualquer um dos 365 dias fora do ano. Logo, as opções 365/365 me dá um valor de 1. Assim, a probabilidade em questão no momento é apenas 1. Mas se há uma segunda pessoa no quarto, qual é a probabilidade de que seu aniversário é diferente? Há apenas 364 dias possíveis, anos bissextos, ignorando para seu aniversário para não colidir com as outras pessoas. Assim, 364/365. Se uma terceira pessoa entra, é 363/365, e assim por diante. Assim, continuam se multiplicando junto destas frações, que estão ficando cada vez menores, para descobrir qual é a probabilidade de que todos nós temos aniversários originais? Mas, então, nós podemos, é claro, basta ter essa resposta e lançá-lo em torno de e fazer 1 menos de tudo isso, uma expressão que vai finalmente chegar se você se lembra a parte de trás de seus livros de matemática, que parece um pouco algo como isto, que é muito mais facilmente interpretada graficamente. E este gráfico aqui tem no eixo x o número de aniversários, ou o número de pessoas com aniversários, e no eixo y é a probabilidade de uma partida. E o que isso está dizendo é que se você tem, digamos, até mesmo, vamos escolher algo como 22, 23. Se há 22 ou 23 pessoas na sala, a probabilidade de que duas dessas poucas pessoas vão ter o mesmo aniversário é realmente super alta, combinatoriamente. 50% as probabilidades de que em uma classe de apenas 22 pessoas, de um seminário, praticamente, 2 de essas pessoas vão ter o mesmo aniversário. Porque há muitas maneiras em que você pode ter o mesmo aniversário. Pior ainda, se você olhar para o lado direito do gráfico, no momento em que você tem uma classe com 58 alunos em que, a probabilidade de duas pessoas que tenham um aniversário é alta, super super, cerca de 100%. Agora, isso é uma espécie de fato divertido sobre a vida real. Mas as implicações, agora, para estruturas de dados e armazenamento de informações significa que apenas supondo que você tem um bom, distribuição, limpa e uniforme de dados e você tem uma matriz grande o suficiente para caber um monte de coisas não significa que você está indo para obter as pessoas em locais exclusivos. Você vai ter colisões. Portanto, esta noção de hash, como é chamado, tomando uma entrada como "Alice" e massageando-o de alguma forma e depois voltar uma resposta como 0 ou 1 ou 2. Voltando alguma saída dessa função é atormentado por essa probabilidade de colisão. Então, como podemos lidar com essas colisões? Bem, em um caso, podemos ter a idéia de que foi sugerido. Nós podemos apenas mudar todos para baixo, ou talvez, um pouco mais simples, em vez de todos os outros movimento, vamos mover Anita para o fundo do local disponível. Então, se Alice está em 0, Bob está em 1, Charlie está em 2, vamos colocar Anita na localização 3. E esta é uma técnica em estruturas de dados chamado linear sondagem. Linear porque você está apenas caminhando nessa linha, e você é uma espécie de sondagem para os locais disponíveis na estrutura de dados. Naturalmente, este transforma em O (n). Se a estrutura de dados é realmente completo, há 25 pessoas que já, e Anita vem, ela acaba com o que seria localização Z, e isso é bom. Ela ainda se encaixa, e podemos encontrá-la mais tarde. Mas isso era contrário ao objetivo de acelerar as coisas. Então, o que se criou, essa terceira dimensão? Essa técnica é geralmente chamado encadeamento separado, ou que possuam cadeias. E o que uma tabela hash é agora, esta estrutura tabular, sua tabela é apenas uma matriz de ponteiros. Mas o que os ponteiros apontam para adivinhar o que é? Uma lista ligada. Então, o que se tirar o melhor de ambos os mundos? Usamos matrizes para os índices iniciais na estrutura de dados, de modo que pode imediatamente ir para [0] [1], [30], ou assim por diante, mas para que possamos ter alguma flexibilidade e podemos encaixar Anita e Alice e Adam e qualquer nome de um outro, nós mas deixar que o outro eixo crescer de forma arbitrária. E finalmente, a partir de segunda-feira, tem essa capacidade expressiva com lista encadeada. Podemos crescer uma estrutura de dados de forma arbitrária. Alternativamente, podemos apenas fazer uma matriz de 2 dimensões enormes, mas que vai ser uma situação terrível se uma das linhas de uma matriz de 2 dimensões não é suficientemente grande para a pessoa cujo nome adicional acontece a começar com A. Deus nos livre de ter que realocar uma estrutura 2-dimensional enorme apenas porque há tantas pessoas denominados A, especialmente quando há tão poucas pessoas nomeadas algo Z. Ele só vai ser uma muito escassa estrutura de dados. Portanto, não é perfeito, por qualquer meio, mas agora pelo menos temos a capacidade Para encontrar onde Alice ou Anita pertence, pelo menos em termos do eixo vertical, e depois só temos de decidir onde colocar Anita ou Alice nesta lista ligada. Se nós não nos importamos com classificando as coisas, com que rapidez podemos inserir Alice em uma estrutura como esta? É tempo constante. Nós índice para [0], e se não houver ninguém, Alice vai no início dessa lista ligada. Mas isso não é um grande negócio. Porque se Anita então vem um número de passos depois, onde é que Anita pertence? Bem, [0]. POO. Alice já está na lista ligada. Mas, se não se importam com a classificação desses nomes, podemos apenas passar mais de Alice, inserção Anita, mas mesmo isso é tempo constante. Mesmo se houver Alice e Adão e todos esses outros nomes A, ele não está realmente mudando-los fisicamente. Por quê? Porque nós fizemos aqui com lista encadeada, quem sabe se esses nós são afinal? Tudo que você tem a fazer é mover as migalhas de pão. Mova as setas ao redor, você não tem que mover fisicamente todos os dados ao redor. Assim, podemos inserir Anita, nesse caso, instantaneamente. Tempo constante. Portanto, temos de tempo constante de pesquisa e de tempo constante inserção de alguém como Anita. Mas tipo de simplificar o mundo. O que se mais tarde quiser encontrar Alice? O que se mais tarde quiser encontrar Alice? Quantos passos é que vai levar? [Responder Estudante, ininteligível] Exatamente. O número de pessoas antes de Alice na lista ligada. Portanto, não é perfeita, porque a nossa estrutura de dados, mais uma vez, tem este acesso vertical e então ele tem essas listas ligadas de suspensão - na verdade, não vamos desenhar uma matriz. Tem essas listas ligadas pendurado fora dele que se parece um pouco algo como isto. Mas o problema é se Alice e Adão e todos esses outros nomes A acabar mais e mais para lá, encontrar alguém pode acabar levando um monte de etapas, bcause você tem que atravessar a lista ligada, que é uma operação linear. Então, realmente, em seguida, o tempo de inserção, em última análise é O (n), onde n é o número de elementos na lista. Dividido por, vamos chamá-lo arbitrariamente m, onde m é o número de listas ligadas que temos neste eixo vertical. Em outras palavras, se realmente assumir uma distribuição uniforme de nomes, totalmente irrealista. Há, obviamente, mais de algumas letras do que outros. Mas se nós assumimos para o momento de uma distribuição uniforme, e temos n total de pessoas, e m correntes totais à nossa disposição, em seguida, o comprimento de cada uma destas cadeias forma muito simples, vai ser o total, n, dividido pelo número de correntes. Assim, n / m. Mas aqui é onde podemos ser tudo matematicamente inteligente. m é uma constante, porque não há um número fixo de estes. Você está indo para declarar a matriz no início, e não estamos redimensionando o eixo vertical. Por definição, que permanece fixo. É apenas o eixo horizontal, por assim dizer, isso está mudando. Então, tecnicamente, é uma constante. Então, agora, o tempo de inserção é muito bonito O (n). De modo que não se sente tudo o que muito melhor. Mas o que há de verdade nisso? Bem, todo esse tempo, por semanas, estamos dizendo O (n ²). O (n), 2 x n ², - n, dividido por 2. . . ech. É apenas ² n. Mas agora, nesta parte do semestre, podemos começar a falar sobre o mundo real novamente. E n / m é absolutamente mais rápido do que apenas n sozinha. Se você tem mil nomes, e dividi-las em vários baldes para que você tenha apenas 10 nomes em cada uma dessas cadeias, absolutamente buscar 10 coisas vai ser mais rápido do que mil coisas. E assim um dos conjuntos de problemas futuros vai desafiá-lo para pensar sobre exatamente que, apesar de, sim, assintoticamente e matematicamente, isso ainda é apenas linear, que suga, em geral, ao tentar encontrar as coisas. Na realidade, o que vai ser mais rápido do que devido a este divisor. E assim, lá está de novo vai ser este trade-off e este conflito entre a teoria ea realidade, e um dos botões vai começar a girar neste ponto no semestre é mais a realidade como um tipo de preparar para o final de semster, como vamos introduzir no mundo da programação web, onde realmente, o desempenho vai contar porque seus usuários estão indo para começar a sentir e apreciar as decisões de design pobre. Então, como você vai fazer sobre a implementação de um ligado - uma tabela hash com 31 elementos? E o exemplo anterior foi arbitrariamente sobre aniversários. Se alguém tem um aniversário de 01 de janeiro ou 01 de fevereiro, vamos colocá-los neste balde. Se é 02 de janeiro, 02 de fevereiro, 2 de março, nós vamos colocá-los neste balde. É por isso que foi de 31. Como você declarar uma tabela hash? Ele pode ser bastante simples, mesa * nó é o meu nome arbitrário para ele, [31]. Isso me dá 31 dicas para nós, e que me permite ter 31 ponteiros para listas ligadas mesmo que essas correntes são inicialmente NULL. O que eu quero colocar, se eu quiser armazenar "Alice", "Bob", "Charlie"? Bem, é preciso envolver essas coisas em uma estrutura porque precisamos de Alice para apontar para Bob, para apontar para Charlie, e assim por diante. Nós não podemos apenas ter os nomes só, então eu poderia criar uma nova estrutura chamada nó aqui. O que é um nó real? O que é um nó nesta nova lista ligada? O primeiro, chamado palavra, é para o nome da pessoa. COMPRIMENTO, presumivelmente, refere-se ao comprimento máximo do nome de um ser humano, seja o que for, 20, 30, 40 personagens em casos de canto louco, e um é para o que? É apenas o caractere NULL extra, \ 0. Portanto, este nó é embrulho "algo" dentro de si, mas também declara um ponteiro chamado próxima para que possamos cadeia de Alice para Bob para Charlie e assim por diante. Pode ser NULL, mas não necessariamente tem que ser. Qualquer dúvida sobre estas tabelas de hash? Sim? [Estudante pedindo questão, ininteligível] Uma matriz - boa pergunta. Porque é que esta palavra char em uma matriz em vez de apenas char *? Neste exemplo um tanto arbitrária, eu não queria ter que recorrer para malloc para cada um dos nomes originais. Eu queria declarar uma quantidade máxima de memória para a cadeia para que eu pudesse copiar para a estrutura de Alice \ 0 e não ter de lidar com malloc e free e similares. Mas eu poderia fazer isso se eu queria ser mais consciente do uso do espaço. Boa pergunta. Então, vamos tentar generalizar longe deste e focar o restante de hoje em estruturas de dados mais geral e outros problemas que podemos resolver usando os mesmos fundamentos mesmo que as estruturas de dados elas mesmas podem diferir nos seus pormenores. Assim, verifica-se em ciência da computação, as árvores são muito comuns. E você pode pensar em uma espécie de árvore como uma árvore genealógica, onde há algumas raízes, alguns matriarca ou patriarca, avô ou avó ou mais cedo de volta, sob o qual estão a mãe eo pai ou irmãos diversas ou similares. Assim, uma estrutura de árvore tem nós e tem filhos, geralmente 0 ou mais crianças para cada nó. E alguns dos jargões que você vê nesta foto aqui é qualquer uma das crianças pequenas ou netos nas bordas que não têm setas que emanam a partir deles, essas são as folhas chamados, e qualquer pessoa no interior é um nó interno, você pode chamá-lo de qualquer coisa nesse sentido. Mas essa estrutura é muito comum. Este aqui é um pouco arbitrária. Nós temos um filho à esquerda, temos três filhos, à direita, duas crianças no canto inferior esquerdo. Assim podemos ter diferentes tamanhos de árvores, mas se começarmos a padronizar as coisas, e você pode chamar este de vídeo Patrick em busca binária de um curta anterior pesquisa, online binário não tem que ser implementado com uma matriz ou pedaços de papel em um quadro negro. Suponha que você queria para armazenar seus números em uma estrutura de dados mais sofisticados. Você poderia criar uma árvore como esta. Pode ter um nó declarado em C, e que o nó pode ter, pelo menos, dois elementos no interior do mesmo. Um deles é o número que deseja armazenar, eo outro é - bem, nós precisamos de mais um. A outra é seus filhos. Então, aqui está uma outra estrutura de dados. Desta vez, o nó é definido como o armazenamento de um número n e, em seguida, dois ponteiros, criança esquerdo e direito da criança. E eles não são arbitrárias. O que é interessante sobre esta árvore? Qual é o padrão na forma como temos colocado isso ou como Patrick colocou-o em seu vídeo? É meio óbvio que há alguma ordenação acontecendo aqui, mas o que é a regra simples? Sim? [Responder Estudante, ininteligível] Perfeito. Se você olhar para isso, você vê os números pequenos de esquerda, grandes números do lado esquerdo, mas isso é verdade para cada nó. Para cada nó, o seu filho esquerdo inferior, e a sua criança direita maior do que. O que isto significa que agora é que se eu quiser procurar esta estrutura de dados para, por exemplo, o número 44, Eu tenho que começar na raiz, porque, como com todas essas estruturas mais complexas de dados, agora, temos apenas um ponteiro para uma coisa, o início. E, neste caso, o início é a raiz. Não é o lado esquerdo, é a raiz desta estrutura. Então eu vejo aqui é 55, e eu estou procurando 44. Qual direção que eu quero ir? Bem, eu quero ir para a esquerda, porque, obviamente, para a direita vai ser muito grande. Então, observe aqui, você é uma espécie de conceitualmente cortar a árvore em meia porque você nunca está indo para o lado direito. Então agora eu ir do 55 ao 33. É muito pequeno de um número. Estou à procura de 44, mas agora eu sei, se 44 é nesta árvore, eu posso ir, obviamente, para a direita. Então, novamente, eu sou a poda da árvore no meio. É praticamente idêntico conceitualmente para o livro de telefone. É idêntico ao que fizemos com os papéis no quadro negro, mas é uma estrutura mais sofisticada, que nos permite realmente fazer este dividir e conquistar, pelo design do algoritmo, e, de fato, atravessando uma estrutura como esta - gritos. Atravessando uma estrutura como esta, onde é apenas "ir por este caminho ou ir por esse caminho", significa todo o código que que dobrado sua mente em primeiro lugar quando implementá-lo na seção ou andar com ele em casa, por busca binária, usando recursão ou iteração, é uma dor no pescoço. Encontre o elemento do meio, em seguida, fazer o seu arredondamento para cima ou para baixo. Há uma beleza a este, porque agora podemos usar recursão novamente, mas muito mais limpa. Na verdade, se você está no número 55 e você quer encontrar 44, você vá para a esquerda, neste caso, então o que você faz? Você corre o algoritmo exato. Você verifica o valor do nó, então você vá para a esquerda ou direita. Então você verificar o valor do nó, vá para a esquerda ou direita. Isto é perfeitamente adequado para a recursividade. Assim, mesmo que no passado fizemos alguns exemplos bastante arbitrárias que envolvem recursão que não precisa ser recursiva, com stuctures de dados, especialmente árvores, é uma perfeita aplicação desta idéia de levar um problema, reduzindo-a, e em seguida a solução do mesmo tipo de, mas menor do programa. Portanto, há uma outra estrutura de dados que podemos apresentar. Este é projetada à primeira vista olhar enigmático, mas este é incrível. Portanto, esta é uma estrutura de dados chamada trie, trie, que é herdado da recuperação de palavra, que não é pronunciado re-try-val, mas é o que o mundo chama essas coisas. Tenta. T-r-i-e. É uma estrutura de árvore de algum tipo, mas cada um de nós em um trie parece ser o que? E isso é um pouco enganoso, porque é uma espécie de abreviado. Mas parece que cada nó neste trie é na verdade uma matriz. E mesmo que o autor deste diagrama não tem mostrado que, neste caso, este trie é uma estrutura de dados cujo propósito na vida é armazenar palavras como A-l-i-c-e ou B-o-b. E a maneira pela qual os dados lojas Alice e Bob e Charlie e Anita e assim por diante é que ele usa uma matriz para armazenar qual Alice em uma trie, começamos no nó raiz que se parece com uma matriz, e que ele foi escrito em notação abreviada. O autor omitido abcdefg porque não havia nomes com isso. Eles só mostrou M e P e T, mas neste caso, vamos passar longe de Alice e Bob e Charlie para alguns nomes que estão aqui. Maxwell é realmente neste diagrama. Então, como o armazenamento de autor M-a-x-w-e-l-l? Ele ou ela começou no nó raiz, e foi para [M], de modo mais ou menos 13, o local 13 na matriz. Então, a partir daí, há um ponteiro. Um ponteiro levando para outro array. A partir daí o autor indexados em que a matriz na posição A, como mostrado lá em cima, à esquerda, e depois que ele ou ela seguiu esse ponteiro para outra matriz, e foi para o ponteiro no local X. Em seguida, na próxima localização matriz W, E, L, L, e assim por diante, e, finalmente, vamos realmente tentar colocar uma imagem para isso. O que faz um nó como no código? Um nó em uma trie contém uma matriz de ponteiros para nós mais. Mas há também tem de haver algum tipo de valor booleano, pelo menos nesta implementação. Acontece que eu chamá-lo is_word. Por quê? Porque quando você está inserindo Maxwell, você não está inserindo nada para esta estrutura de dados. Você não está escrevendo M. Você não está escrevendo X. Tudo o que você está fazendo é seguir ponteiros. O ponteiro que representa M, então o ponteiro que representa A, em seguida, o ponteiro que representa X, em seguida, W, E, L, L, mas o que você precisa fazer no final é uma espécie de vão, verificar, cheguei a este local. Havia uma palavra que termina aqui na estrutura de dados. Então, o que uma trie é realmente cheio e com o autor escolheu para representar estes terminuses com pequenos triângulos. Isto apenas significa que o fato de esse triângulo está aqui, este valor booleano verdadeiro significa que se você ir para trás na árvore, significa que uma palavra é chamado Maxwell neste. Mas a palavra foo, por exemplo, não está na árvore, porque se eu começar no nó raiz aqui em cima, Não há ponteiro f, nenhum ponteiro o, não o ponteiro. Foo não é um nome neste dicionário. Mas por outro lado, turação, t-u-r-i-n-g. Mais uma vez, eu não armazenar t ou u ou r ou i ou n ou g. Mas eu fiz na loja esta estrutura de dados um valor de verdadeiro caminho até aqui neste nó - na árvore definindo esse valor booleano de is_word a verdade. Assim, um trie é uma espécie de esta estrutura meta muito interessante, onde você não está realmente armazenar as próprias palavras para este tipo de dicionário. Para ser claro, você está apenas armazenando sim ou não, não é uma palavra que termina aqui. Agora, qual é a implicação? Se você tem 150 mil palavras em um dicionário que você está tentando armazenar na memória usando algo como uma lista ligada, você vai ter 150 mil nós em sua lista ligada. E encontrar uma dessas palavras em ordem alfabética pode levar tempo O (n). Tempo linear. Mas no caso aqui de uma trie, o que é o tempo de execução de encontrar uma palavra? Acontece que a beleza aqui é que mesmo se você tem 149.999 palavras já neste dicionário, como implementado com esta estrutura de dados, quanto tempo leva para encontrar ou inserir mais uma pessoa em que, como Alice, Alice? Bem, é apenas 5, talvez 6 passos para o personagem de fuga. Porque o presense de outros nomes na estrutura não ficar no caminho de inserção de Alice. Além disso, encontrar Alice uma vez que existem 150.000 palavras neste dicionário não entrar em seu caminho de encontrar Alice em tudo, porque Alice é. . . . . aqui, porque eu encontrei um valor booleano. E se não houver booleano verdadeiro, então Alice não está na esta estrutura de dados de palavras. Em outras palavras, o tempo de execução de encontrar as coisas e inserindo as coisas para este novo estrutura de dados de trie é O de - não é n. Porque o presense de 150.000 pessoas não tem efeito sobre Alice, que parece. Então, vamos chamá-lo de k, onde k é o comprimento máximo de uma palavra em Inglês que é, tipicamente, não mais do que 20 e poucos caracteres. Assim, k é uma constante. Assim, o Santo Graal que parecem ter encontrado agora é o de uma vez, trie constante para pastilhas, para pesquisas, por eliminações. Como o número de coisas já na estrutura, que não são nem mesmo fisicamente lá. Mais uma vez, eles estão apenas uma espécie de desmarcado, sim ou não, não tem impacto no seu tempo futuro em execução. Mas tem de ser um problema, caso contrário, não teria perdido tanto tempo em todas essas estruturas de dados outros apenas para finalmente chegar ao um segredo que é incrível. Então, qual o preço que estamos pagando para alcançar essa grandeza aqui? Espaço. Essa coisa é enorme. E a razão que o autor não apresentá-lo aqui, notar que todas essas coisas que se parecem com matrizes, ele não desenhar o restante da árvore, o resto do trie, porque eles são não apenas relevantes para a história. Mas todos esses nós são super grande, e cada nó na árvore ocupa 26 ou, na verdade, poderia ser de 27 caracteres, porque neste caso eu estava incluindo espaço para o apóstrofo para que pudéssemos ter palavras apostrofado. Neste caso, trata-se matrizes de largura. Assim, mesmo que eles não estão picutured, isso leva-se uma enorme quantidade de RAM. O que pode ser bom, especilly em hardware moderno, mas essa é a troca. Nós temos menos tempo, gastando mais espaço. Então, onde é que isto tudo vai? Bem, vamos fazer - vamos ver aqui. Vamos fazer um salto para esse cara aqui. Acredite ou não, divertido como C tem sido já há algum tempo, estamos chegando ao ponto em que, no semestre é hora de transição para as coisas mais modernas. Coisas em um nível superior. E mesmo que para o próximo par de semanas vamos continuar a mergulhar no mundo de ponteiros e gerenciamento de memória para obter esse conforto com a qual podemos então construir, O jogo final é, finalmente, para introduzir, ironicamente, não esta linguagem. Nós vamos gastar, como 10 minutos falando sobre HTML. Todo o HTML é uma linguagem de marcação, e que é uma linguagem de marcação é é esta série de suportes abertos e fechados suportes que dizem "fazer este bold ' "Tornar esta itálico" "fazer esta centrada." Não é tudo o que intelectualmente interessante, mas é super útil. E é certamente onipresente nos dias de hoje. Mas o que é poderoso sobre o mundo do HTML e programação web em geral, está construindo coisas dinâmicas; escrever código em linguagens como PHP ou Python ou Ruby ou Java ou C #. Realmente, qualquer que seja o idioma de sua escolha, e gerar HTML dinamicamente. Gerando uma coisa chamada CSS dinamicamente. Folhas de estilo em cascata, o que é também sobre a estética. E por isso mesmo que, hoje, se eu for para algum site como o Google.com familiar, e vou ver, desenvolvedor, fonte de visão, que talvez você tenha feito antes, mas vai ver o código fonte, este material provavelmente parece muito enigmática. Mas este é o código subjacente que implementa Google.com. Na extremidade dianteira. E, na verdade, tudo isso é coisa de estética fofo. Este é CSS aqui. Se eu continuar a rolagem para baixo nós vamos pegar algumas coisas com código de cores. Este é HTML. Código do Google parece uma bagunça, mas se eu realmente abrir uma janela diferente, podemos ver alguma estrutura para isso. Se eu abrir isto, observe aqui, é um pouco mais legível. Nós vamos ver em pouco tempo essa marca, [palavra] é uma tag, HTML, cabeça, corpo, div, roteiro, área de texto, extensão, centrado, div. E esta é também classificar de aparência enigmática, à primeira vista, mas toda esta confusão segue certos padrões, e padrões repetitivos, de modo que uma vez que temos o básico para baixo, você vai ser capaz de escrever um código como este e, então, manipular o código como esta usando outra linguagem, chamada de JavaScript. E JavaScript é uma linguagem que roda dentro de um browser hoje, que usamos em Harvard cursos, para a ferramenta de compras curso que usa mapas do Google para dar-lhe um monte de dinamismo, o Facebook dá a você para mostrar atualizações de status instantâneas, Twitter usa para mostrar o tweets instantaneamente. Tudo isso, vamos começar a mergulhar dentro Mas para chegar lá, precisamos entender um pouco sobre a Internet. Este clip aqui é apenas um minuto de duração, e vamos assumir por agora este é, de fato, como a Internet funciona como um teaser para o que está por vir. Eu dar-lhe "Guerreiros do líquido." [♫ ♫ música lenta coro] [Narrador Masculino] Ele veio com uma mensagem. Com um protocolo de todo seu. [♫ ♫ música Faster eletrônico] Ele veio para um mundo de firewalls frias, insensíveis roteadores, e perigos muito piores do que a morte. Ele é rápido. Ele é forte. Ele é o TCP / IP, e ele tem o seu endereço. Guerreiros da rede. [Malan] Na próxima semana, então. A Internet. Programação web. Este é CS50. [CS50.TV]