[Powered by Google Translate] [Seção 6] [Mais Confortável] [Rob Bowden] [Harvard University] [Esta é CS50.] [CS50.TV] 

Nós podemos ir para nossa seção de perguntas. Eu mandei a URL para o espaço antes. O início da seção das perguntas dizem- aparentemente, eu não sou inteiramente unsick é uma pergunta muito fácil de apenas o que é valgrind? O que valgrind fazer? Alguém quer dizer o que valgrind faz? [Estudante] Verifica a memória. Sim, valgrind é um verificador de memória geral. É, no final, diz que se você tiver quaisquer vazamentos de memória, que é principalmente o que estamos usando para isso, porque se você quiser fazer bem no conjunto de problemas ou se você quiser obter na placa grande, você precisa de ter nenhum vazamento de memória que seja, e no caso de você ter um vazamento de memória que você não pode encontrar, também ter em mente que sempre que você abre um arquivo e se você não fechá-lo, isso é um vazamento de memória. 

Um monte de pessoas estão à procura de algum nó que eles não estão liberando quando, na verdade, eles não fechar o dicionário no primeiro passo. Ele também diz que se você tiver qualquer inválido lê ou escreve, o que significa que se você tentar definir um valor que está além do fim da pilha e que não aconteça a falha seg mas valgrind pega, como você não deve realmente ser escrito lá, e então você definitivamente não deve ter nenhuma dessas também. Como você usa Valgrind? Como você usa Valgrind? 

É uma questão geral de tipo de executá-lo e olhar para a saída. A saída é sobrecarregar um monte de vezes. Há também erros de diversão onde se você tem alguma coisa muito errada acontecendo em um loop, em seguida, ele acabará por dizer, "Caminho erros demais. Eu vou parar de contar agora. " É basicamente saída textual que você tem que analisar. No final, ele vai dizer qualquer vazamento de memória que você tem, quantos blocos, o que pode ser útil, pois se é um unfreed bloco, então é geralmente mais fácil de encontrar de 1.000 blocos unfreed. 1.000 blocos unfreed provavelmente significa que você não está liberando suas listas ligadas de forma adequada ou algo assim. Isso valgrind. 

Agora temos nossa seção de perguntas, que você não precisa fazer o download. Você pode clicar no meu nome e puxe-los no espaço. Agora clique em mim. Revisão 1 será de pilha, que estamos a fazer em primeiro lugar. Revisão 2 será fila e Revisão 3 será a lista vinculada isoladamente. Começando com a nossa pilha. Como se diz aqui, uma pilha é uma das mais básicas, estruturas de dados fundamentais da ciência da computação. O exemplo prototípico é muito a pilha de bandejas no salão de jantar. É basicamente sempre que você está sendo apresentado a uma pilha, alguém vai dizer: "Oh, como uma pilha de bandejas." Você empilhar as bandejas para cima. Então quando você vai puxar uma bandeja, a primeira bandeja que está sendo puxado é a última que foi colocado na pilha. A pilha também, como se diz aqui- temos o segmento da memória denominada pilha. E por que é chamado de pilha? 

Porque, como uma estrutura de dados de pilha, ele empurra e aparece pilha de quadros na pilha, onde quadros de pilha são como uma chamada específica de uma função. E como uma pilha, você sempre tem que retornar a partir de uma chamada de função antes de descer em quadros menores pilha novamente. Você não pode ter principal chamada barra chamada foo e retorno barra diretamente principal. Ele sempre tem que seguir a pilha correta empurrando e popping. As duas operações, como eu disse, são push e pop. Esses são termos universais. Você deve saber push e pop, em termos de pilhas, não importa o quê. Vamos ver filas são um pouco diferente. Ele realmente não tem um termo universal, mas push e pop são universais para pilhas. Push é só colocar na pilha. Pop é tirar a pilha. E vemos aqui temos a nossa pilha typedef struct, por isso temos cordas char **. Não fique com medo por qualquer **. Isso vai acabar sendo uma matriz de strings ou uma matriz de ponteiros para caracteres, onde ponteiros para personagens tendem a ser cordas. Ele não tem que ser strings, mas aqui, eles vão ser strings. 

Nós temos uma matriz de strings. Temos um tamanho, o que representa quantos elementos estão na pilha, e depois temos a capacidade, que é o número de elementos pode ser na pilha. A capacidade deve começar como algo maior do que 1, mas o tamanho vai começar como 0. Agora, existem basicamente três maneiras diferentes que você pode pensar de uma pilha. Bem, há provavelmente mais, mas as duas principais formas são você pode implementá-lo usando uma matriz, ou você pode implementá-lo usando uma lista ligada. Listas ligadas são uma espécie de trivial para fazer pilhas de. É muito fácil fazer uma pilha usando listas ligadas, Então, aqui, nós vamos fazer uma pilha usando matrizes, e em seguida, usando matrizes, também há duas maneiras que você pode pensar sobre isso. Antes, quando eu disse que nós temos uma capacidade para a pilha, para que possa ajustar um elemento na pilha. 

A única maneira que poderia acontecer é assim que você acertar 10 elementos, então você está feito. Você pode saber que existe um limite superior de 10 coisas no mundo que você nunca vai ter mais do que 10 coisas em sua pilha, caso em que você pode ter um limite superior sobre o tamanho do seu stack. Ou você poderia ter sua pilha ser ilimitado, mas se você está fazendo uma matriz, o que significa que cada vez que você acertar 10 elementos, então você vai ter que crescer para 20 elementos, e quando você bate 20 elementos, você vai ter que crescer a sua matriz para 30 elementos ou 40 elementos. Você está indo a necessidade de aumentar a capacidade, que é o que nós vamos fazer aqui. Cada vez que atingir o tamanho máximo de nossa pilha, quando empurrar outra coisa, nós vamos precisar de aumentar a capacidade. Aqui, nós impulso declarado como impulso bool (char * str). * Str Char é a cadeia que estamos empurrando para a pilha, bool e apenas diz se conseguimos ou não. 

Como não? Qual é a única circunstância que você pode pensar onde iríamos precisar retornar falso? Sim. [Estudante] Se ele está cheio e estamos usando uma implementação limitada. Sim, assim como nós definimos, ele respondeu se é total e estamos usando uma aplicação limitada. Então, nós definitivamente return false. Assim que atingiu 10 coisas na matriz, não pode caber 11, assim voltamos falso. E se é ilimitado? Sim. Se você não pode se expandir a matriz por algum motivo. Sim, então a memória é um recurso limitado, e, eventualmente, se manter as coisas empurrando para a pilha de uma e outra vez, vamos tentar alocar um maior matriz para caber a maior capacidade, malloc e ou o que estamos usando vai retornar falso. Bem, malloc retornará nulo. 

Lembre-se, cada vez que você sempre chamar malloc, você deve verificar para ver se ele retorna nulo ou então que é uma dedução correção. Desde que nós queremos ter uma pilha ilimitada, o único caso que vamos estar retornando falso é se tentarmos aumentar a capacidade e malloc ou o que retorna falso. Então pop não tem argumentos, e devolve a cadeia de caracteres que está no topo da pilha. Tudo o que foi mais recentemente colocado na pilha é o pop está voltando, e também remove da pilha. E notem que ele retorna nulo se não houver nada na pilha. É sempre possível que a pilha está vazia. Em Java, se você está acostumado a isso, ou outras línguas, tentando aparecer a partir de uma pilha vazia pode causar uma exceção ou algo assim. 

Mas em C, nulo é uma espécie de grande quantidade de casos como lidar com estes problemas. Voltando nulo é como nós vamos para significar que a pilha estava vazio. Nós fornecemos o código que irá testar a funcionalidade do seu stack, implementar push e pop. Isso não vai ser um monte de código. Eu vou, na verdade, antes de fazer isso, dica, sugestão- se você ainda não viu, malloc não é a única função que aloca memória na pilha para você. Há uma família de funções alloc. O primeiro é malloc, que você está acostumado. Então há calloc, que faz a mesma coisa que malloc, mas vai zerar tudo para você. Se você sempre quis para definir tudo para null após mallocing algo você deve ter usado apenas calloc, em primeiro lugar, em vez de escrever um loop for para zerar todo o bloco de memória. 

Realloc é como malloc e tem um monte de casos especiais, mas basicamente o que faz é realloc leva um ponteiro que já havia sido alocado. Realloc é a função que você deseja estar prestando atenção aqui. É preciso um ponteiro que já havia sido devolvido a partir de malloc. Vamos dizer que você solicitar malloc um ponteiro de 10 bytes. Então, mais tarde você percebe que você queria 20 bytes, Então você chama realloc em que o ponteiro com 20 bytes, realloc e automaticamente copiar tudo para você. Se você acabou de chamar malloc novamente, como eu tenho um bloco de 10 bytes. Agora eu preciso de um bloco de 20 bytes, então se eu malloc 20 bytes, então eu tenho que copiar manualmente ao longo dos 10 bytes de a primeira coisa na segunda coisa e então livre a primeira coisa. Realloc vai lidar com isso para você. 

Observe a assinatura vai ser void *, que é apenas retornar um ponteiro para o bloco de memória, em seguida, void * ptr. Você pode pensar em void * como um ponteiro genérico. Geralmente, você nunca lidar com void *, malloc mas está retornando um void *, e então ele é apenas usado como isto é, na verdade, vai ser um char *. Void * anterior, que havia sido devolvido por malloc agora vai ser passado para realloc e tamanho é o novo número de bytes que você deseja alocar, para que a sua nova capacidade. Eu vou te dar um par de minutos, e fazê-lo em nosso espaço. Comece com Revisão 1. Eu vou parar depois espero que sobre tempo suficiente para implementar push, e então eu vou dar-lhe uma outra ruptura de fazer pop. Mas realmente não é que o código muito em tudo. A maior parte do código é provavelmente o material em expansão, a expansão da capacidade. Ok, nenhuma pressão para ser completamente feito, mas contanto que você sente que está no caminho certo, isso é bom. 

Alguém tem algum código que se sentir confortável comigo puxando para cima? Sim, eu vou, mas alguém tem algum código que pode puxar para cima? Ok, você pode começar, salvá-lo, seja o que for? Eu sempre esqueço que passo. Ok, olhando para push, quer explicar o seu código? [Estudante] Primeiro de tudo, eu aumentei o tamanho. Eu acho que talvez eu deveria ter que de qualquer maneira, eu aumentei o tamanho, e eu ver se é menos do que a capacidade. E se é menos do que a capacidade, eu acrescentar à matriz que já temos. E se não for, eu multiplicar a capacidade por 2, e eu realocar a matriz cordas para algo com um tamanho maior capacidade agora. E depois, se falhar, eu digo o usuário e retornar falso, e se ele está bem, então eu coloquei a corda no novo local. 

[Rob B.] Note também que se a um operador bit a bit agradável aqui a multiplicar por 2. Lembre-se, desvio à esquerda é sempre vai ser multiplicada por 2. Deslocamento para a direita é dividido por dois, desde que você lembre-se que isso significa dividir por 2, como em um inteiro dividido por 2. Ele pode truncar a 1 aqui ou ali. Mas mudança deixada por um sempre vai ser multiplicado por 2, a menos que transbordam os limites do número inteiro, e então não vai ser. Um comentário lateral. Eu gosto de fazer-isso não vai mudar a codificação qualquer forma, mas eu gostaria de fazer algo assim. Ele realmente está indo para torná-lo um pouco mais. Talvez este não é o caso perfeito para mostrar isso, mas eu gosto de segmento que nestes blocos de- ok, se isso se acontecer, então eu vou fazer alguma coisa, e, em seguida, a função é feito. Eu não preciso de role meus olhos todo o caminho até a função para ver o que acontece após o outro. É, se isso se acontecer, então eu voltar. Ele também tem o benefício adicional de tudo agradável para além deste agora é deslocado para a esquerda uma vez. Eu já não precisa-se sempre perto ridiculamente longas filas, então esses 4 bytes pode ajudar, e também a algo mais à esquerda é, a menos sobrecarregado você se sentiria se gosta, tudo bem, eu tenho que lembrar Eu estou atualmente em um loop while dentro de um interior mais de um loop. Em qualquer lugar você pode fazer isso de retorno imediato, eu meio que gosto. É totalmente opcional e não é esperado de qualquer forma. 

[Estudante] Deve haver um tamanho - na condição de falha? A condição de falha aqui é que nós não realloc, então sim. Observe como na condição de falha, presumivelmente, a não ser que o material livre depois, estamos sempre vai falhar não importa quantas vezes nós tentar empurrar alguma coisa. Se continuarmos a empurrar, vamos manter o tamanho do incremento, mesmo que não estamos colocando nada na pilha. Normalmente nós não aumentar o tamanho até depois conseguimos colocá-lo na pilha. Podemos fazer, por exemplo, ou aqui e aqui. E então, em vez de dizer s.size capacidade ≤, é menos do que a capacidade, apenas porque nos mudamos onde estava tudo. 

E lembre-se, o único lugar que poderia retornar falso é aqui, onde realloc retornou nulo, e se acontecer de você se lembrar de erro padrão, talvez você pode considerar este um caso em que você deseja imprimir um erro padrão, stderr para fprintf em vez de apenas imprimir diretamente para a saída padrão. Mais uma vez, isso não é uma expectativa, mas se é um erro, printf digitar, então você pode querer fazê-lo imprimir ao erro padrão em vez de saída padrão. 

Alguém tem mais alguma coisa a notar? Sim. [Estudante] Você pode ir até o [inaudível]? [Rob B.] Sim, o binariness real dele ou apenas o que é? [Estudante] Então você multiplicar isso por 2? [Rob B.] Sim, basicamente. Em terra binário, nós sempre temos o conjunto de dígitos. Mudando esta esquerda por uma basicamente insere-lo aqui no lado direito. Voltar para isso, basta lembrar que tudo em binário é uma potência de 2, pelo que esta representa 2 a 0, este 2 a 1, 2 para a esta 2. Ao inserir um 0 para o lado direito agora, só mudar tudo de novo. O que costumava ser de 2 a 0 é agora 2 para a 1, 2 e é o 2. O lado direito que nós inserimos é necessariamente vai ser 0, o que faz sentido. Se você já se multiplicar um número por 2, isso não vai acabar estranho, de modo que o 2 para o local de 0 deve ser de 0, e é isso que eu meio que alertou sobre antes é se você fizer acontecer para mudar para além do número de bits de um número inteiro, então este é um vai acabar saindo. Essa é a única preocupação se acontecer de você estar lidando com capacidades muito grandes. Mas nesse ponto, então você está lidando com uma matriz de milhares de milhões de coisas, que pode não caber na memória de qualquer maneira. 

Agora podemos chegar ao pop, o que é ainda mais fácil. Você poderia fazer como se acontecer de você aparecer um monte, e agora você está na metade de sua capacidade novamente. Você poderia realloc para diminuir a quantidade de memória que você tem, mas você não tem que se preocupar com isso, então o caso realloc só vai ser crescente memória, nunca diminuir a memória, que vai fazer de super pop fácil. Agora filas, que vão ser como pilhas, mas a ordem que você tome as coisas é invertida. O exemplo prototípico de uma fila é uma linha, então eu acho que se você fosse Inglês, eu teria dito um exemplo prototípico de uma fila é uma fila. Assim como uma linha, se você é a primeira pessoa na linha, você espera ser a primeira pessoa fora da linha. Se você é a última pessoa na linha, você vai ser a última pessoa atendida. Nós chamamos esse padrão FIFO, enquanto pilha era padrão LIFO. Essas palavras são bastante universal. 

Como pilhas e diferentemente de matrizes, as filas normalmente não permitem o acesso a elementos no meio. Aqui, uma pilha, temos push e pop. Aqui, acontece que temos chamado enqueue e dequeue. Eu também ouvi-los chamado de turno e unshift. Eu ouvi pessoas dizerem push e pop para também aplicar a filas. Ouvi inserir, remover, para push e pop, se você está falando de pilhas, você está empurrando e popping. Se você está falando sobre filas, você pode escolher as palavras que você deseja usar para inserção e remoção, e não há consenso sobre o que deve ser chamado. Mas aqui, temos enqueue e dequeue. Agora, a estrutura é quase idêntico ao da estrutura de pilha. Mas temos que manter o controle de cabeça. Eu acho que ele diz aqui, mas por que precisamos da cabeça? Os protótipos são praticamente idênticos ao push e pop. Você pode pensar nisso como push e pop. A única diferença é pop está voltando em vez da última, ele está retornando o primeiro. 2, 1, 3, 4, ou algo assim. E aqui está o início. Nossa fila está completamente cheio, por isso há quatro elementos nele. O fim da nossa fila é atualmente de 2, e agora vamos para inserir algo mais. 

Quando queremos inserir esse algo mais, o que fizemos para a versão de pilha é que nós estendemos o nosso bloco de memória. Qual é o problema com isso? [Estudante] Você move o 2. O que eu disse antes sobre o fim da fila, isso não faz sentido que começam em 1, então queremos dequeue 1, então dequeue 3, então dequeue 4, então dequeue 2, então desenfileirar este. Nós não podemos usar realloc agora, ou, no mínimo, você tem que usar realloc de uma maneira diferente. Mas provavelmente você não deve apenas usar realloc. Você vai ter que copiar manualmente sua memória. 

Existem duas funções para copiar a memória. Há memcopy e memmove. Atualmente estou lendo as páginas do manual para ver qual deles você vai querer usar. Ok, memcopy, a diferença é que memcopy e memmove, um trata do caso correctamente onde você está copiando para uma região que acontece a sobrepor-se a região você está copiando. Memcopy não lidar com isso. Memmove faz. Você pode pensar no problema como- digamos que eu quero copiar esse cara, estes quatro para esse cara. No final, o que a matriz deve ser semelhante após a cópia é 2, 1, 2, 1, 3, 4, e, em seguida, algumas coisas no final. Mas esta é dependente da ordem em que, na verdade, copiar, pois, se não considerarmos o fato de que a região que está copiando em sobrepõe a que estamos copiando, então podemos fazer como começo aqui, copie a 2 para o lugar que quer ir, em seguida, passar nossos ponteiros para a frente. 

Agora nós vamos estar aqui e aqui, e agora queremos copiar esse cara esse cara e mover os nossos ponteiros para a frente. O que nós vamos acabar ficando é de 2, 1, 2, 1, 2, 1 em vez do 2 apropriado, 1, 2, 1, 3, 4, porque 2, 1 superou o original 3, 4. Memmove alças que corretamente. Neste caso, basicamente, apenas utilize sempre memmove porque ele lida corretamente. Geralmente não realizar qualquer pior. A idéia é, em vez de começar do início e cópia desta maneira como nós fizemos aqui, que começa a partir do final e copia em, e, nesse caso, você nunca pode ter um problema. Não há perda de performance. Sempre use memmove. Nunca se preocupe com memcopy. E é aí que você vai ter que separadamente memmove a porção envolta em torno de sua fila. Não se preocupe se não completamente feito. Isso é mais difícil do que pilha, pop push, e. 

Alguém tem algum código que poderia trabalhar? Mesmo completamente incompleto? [Estudante] Sim, é completamente incompleta, no entanto. Completamente incompleta é bom, contanto que-você pode salvar a revisão? Eu esqueço que a cada momento. Ok, ignorando o que acontece quando precisamos redimensionar as coisas. Ignorar completamente redimensionamento. Explicar este código. Estou verificando em primeiro lugar, se o tamanho é inferior a primeira cópia de todas e depois disso, eu insiro-me tomar a cabeça + tamanho, e eu ter certeza que envolve a capacidade da matriz, e eu inserir a nova cadeia nessa posição. Então eu aumentar o tamanho e retornar true. 

[Rob B.] Este é definitivamente um daqueles casos em que você vai querer estar usando mod. Qualquer tipo de caso onde você enrolar, se você acha que enrolar, o pensamento imediato deve ser mod. Como uma otimização rápido / fazer o seu código uma linha mais curta, você percebe que a linha imediatamente após este é apenas o tamanho + +, então você mesclar em que esta linha, tamanho + +. Agora aqui em baixo, temos o caso onde não tem memória suficiente, por isso estamos aumentando nossa capacidade por 2. Eu acho que você poderia ter o mesmo problema aqui, mas podemos ignorá-lo agora, onde se você não conseguiu aumentar a sua capacidade, então você vai querer diminuir a sua capacidade em 2 novamente. Outra nota curta é exatamente como você pode fazer + =, você também pode fazer << =. Quase tudo pode ir antes de igual para igual, + =, | =, & =, << =. Char * novo é o nosso novo bloco de memória. Oh, aqui. 

O que as pessoas pensam sobre o tipo do nosso novo bloco de memória? [Estudante] Deve ser char **. Pensando em nossa estrutura aqui em cima, cordas é o que estamos realocando. Estamos a fazer um novo armazenamento dinâmico inteiro para os elementos na fila. O que nós vamos estar atribuindo a suas cordas é o que estamos mallocing agora, e tão nova, vai ser um char **. Vai ser uma matriz de strings. Então o que é o caso em que nós vamos retornar falso? [Estudante] Deveríamos estar fazendo o char *? [Rob B.] Sim, boa chamada. [Estudante] O que foi isso? [Rob B.] Nós queríamos fazer o tamanho de char *, porque não estamos mais- este seria realmente um problema muito grande, porque sizeof (char) seria 1. Sizeof char * vai ser 4, isso um monte de vezes, quando você está lidando com ints, você tende a fugir com ele porque o tamanho de int e tamanho de int * em um sistema de 32 bits vai ser a mesma coisa. Mas aqui, sizeof (char) e sizeof (char *) são agora vai ser a mesma coisa. 

O que é a circunstância em que retornar falso? [Estudante] Nova é nulo. Sim, se novo é nulo, nós retornar falso, e eu vou jogar aqui- [Estudante] [inaudível] [Rob B.] Sim, isso é ótimo. Você poderia fazer duas vezes a capacidade ou mudança de capacidade 1 e só então colocou-a aqui ou o que seja. Nós vamos fazer tudo o que se tinha. Capacidade >> = 1. E você nunca vai ter que se preocupar em perder o seu lugar um porque você deixou desviado por um, de modo que o seu lugar um é necessariamente a 0, tão certo deslocamento por 1, você ainda vai estar bem. [Estudante] Você precisa fazer isso antes do retorno? [Rob B.] Sim, isso não faz nenhum sentido. 

Agora, vamos supor que vamos acabar voltando verdade até o fim. A maneira que nós vamos fazer essas memmoves, temos que ter cuidado com a forma como as fazemos. Alguém tem alguma sugestão de como as fazemos? Aqui está o nosso início. Inevitavelmente, queremos começar no início de novo e cópia em coisas de lá, 1, 3, 4, 2. Como você faz isso? Primeiro, eu tenho de olhar para a página do manual para memmove novamente. Memmove, a ordem de argumentos é sempre importante. Queremos que o nosso primeiro destino, segundo fonte, a terceira dimensão. Há uma série de funções que invertem origem e destino. Origem, destino, tende a ser um pouco consistente. Movimento, o que é voltar? Ele retorna um ponteiro para o destino, por qualquer motivo, você pode querer isso. Eu posso imaginar lê-lo, mas queremos avançar para o nosso destino. 

O que é o nosso destino vai ser? [Estudante] Novo. [Rob B.] Sim, e para onde estamos copiando? A primeira coisa que estamos copiando é este 1, 3, 4. Qual é a esta-1, 3, 4. O que é o endereço do 1? O que é o endereço do que 1? [Estudante] [inaudível] [Rob B.] Head + o endereço do primeiro elemento. Como podemos obter o primeiro elemento na matriz? [Estudante] Fila. [Rob B.] Sim, q.strings. Lembre-se, aqui, a nossa cabeça é 1. Droga. Eu só acho que é magicamente Aqui, nossa cabeça é 1. Eu vou mudar a minha cor também. E aqui está cordas. Isso, nós pode escrever como fizemos aqui com cabeças + q.strings. Um monte de gente também escrevê-lo e q.strings [cabeça]. Isto não é realmente menos eficiente. Você pode pensar nisso como você está dereferencing-lo e em seguida, obter o endereço, mas o compilador vai traduzi-lo para o que tínhamos antes de qualquer forma, q.strings cabeça +. De qualquer maneira que você quer pensar nisso. 

E quantos bytes que queremos copiar? [Estudante] Capacidade - cabeça. Capacidade - cabeça. E então você pode sempre escrever um exemplo para descobrir se isso é certo. [Estudante] Ela precisa ser dividido por dois, então. Sim, então eu acho que nós poderíamos usar tamanho. Nós ainda temos tamanho ser- usando tamanho, que tem tamanho igual a 4. Nosso tamanho é 4. Nossa cabeça é uma. Queremos copiar esses três elementos. Essa é a verificação de sanidade que tamanho - cabeça é corretamente 3. E voltar aqui, como dissemos antes, se usássemos capacidade, então teríamos que dividir por dois porque já crescido nossa capacidade, então em vez disso, vamos usar o tamanho. Que copia essa parte. Agora, precisamos copiar a outra parte, a parte que está à esquerda do início. 

Isso vai memmove em que posição? [Estudante] tamanho Plus - cabeça. Sim, por isso, já copiou em tamanho - bytes de cabeça, e assim por onde queremos copiar os bytes restantes é novo e tamanho de menos bem, o número de bytes que já copiado dentro E então onde estamos copiando? [Estudante] Q.strings [0]. [Rob B.] Sim, q.strings. Podíamos fazer e q.strings [0]. Isso é muito menos comum do que este. Se ele só vai ser 0, então você tende a ver q.strings. É aí que estamos copiando. Quantos bytes que nos resta para copiar? >> [Estudante] 10. Direito. [Estudante] Nós temos que multiplicar 5-10 vezes o tamanho dos bytes ou algo assim? Sim, por isso este é o lugar onde, o que exatamente estamos copiando? [Estudante] [inaudível] Qual é o tipo de coisa que estamos copiando? [Estudante] [inaudível] Sim, então o char * s que estamos copiando, não sabemos onde aqueles são provenientes. Bem, onde eles estão apontando, como as cordas, acabamos empurrando-o para a fila ou enqueuing para a fila. Onde aqueles estão vindo, não temos idéia. Nós só precisamos manter o controle do char * s si. Nós não queremos copiar tamanho - bytes de cabeça. Queremos copiar o tamanho - cabeça char * s, então vamos multiplicar isso por sizeof (char). Mesmo aqui em baixo, cabeça * sizeof (char *). 

[Estudante] E sobre [inaudível]? Isso aqui? [Estudante] Não, abaixo disso, o tamanho - cabeça. [Rob B.] Isso aqui? Aritmética de ponteiro. Como a aritmética de ponteiro está indo para o trabalho é ele automaticamente multiplica pelo tamanho do tipo que estamos lidando. Assim como aqui, novo + (tamanho - cabeça) é exatamente equivalente a & [tamanho - cabeça] novo até que esperamos que funcione corretamente, pois, se estamos lidando com uma matriz int, então não fazer índice int- ou se é do tamanho de 5 e você deseja que o elemento 4, então o índice que no int array [4]. Você NÃO FAZEM [4] * O tamanho de int. Que manipula-lo automaticamente, e neste caso é literalmente equivalente, então, a sintaxe suporte é só ir para ser convertido para isso assim que você compilar. Isso é algo que você precisa ter cuidado com isso quando você está adicionando tamanho - cabeça você está adicionando não um byte. Você está adicionando um char *, que pode ser uma bytes ou o que seja. 

Outras perguntas? Ok, dequeue vai ser mais fácil. Eu vou te dar um minuto de implementar. Ah, e eu acho que essa é a mesma situação onde que o caso enqueue, se estamos enqueuing nulo, talvez nós queremos lidar com isso, talvez não. Nós não vamos fazer isso de novo aqui, mas mesmo que o nosso caso pilha. Se enfileirar nulo, que pode querer ignorá-lo. Alguém tem algum código que pode puxar para cima? [Estudante] eu só tenho dequeue. A versão 2 é que, tudo bem. Você quer explicar? [Estudante] Primeiro, você se certificar de que há algo na fila e que o tamanho está indo para baixo em 1. Você precisa fazer isso, e depois voltar a cabeça e mova a cabeça 1. Ok, então não é um caso extremo, temos de considerar. Sim. [Estudante] Se sua cabeça está no último elemento, então você não quiser cabeça para apontar fora da matriz. 

Sim, tão logo que cabeça bate o fim de nossa matriz, quando desenfileirar, nossa cabeça deve ser modded para 0. Infelizmente, não podemos fazer isso em uma única etapa. Eu acho que a maneira que eu provavelmente corrigi-lo é este vai ser um char *, o que estamos voltando, qualquer que seja o seu nome variável quer ser. Então nós queremos mod cabeça pela nossa capacidade e depois voltar ret. Um monte de gente aqui que poderiam fazer- este é o caso de ver as pessoas, pois você fazer se a cabeça é maior do que a capacidade, fazer a cabeça - capacidade. E isso é apenas a trabalhar em torno do que é mod. Chefe mod = capacidade é muito mais limpo de um invólucro em torno do que se a cabeça maior do que a cabeça de capacidade - a capacidade. 

Perguntas? Ok, a última coisa que nos resta é a nossa lista encadeada. Você pode ser usado para alguns dos comportamentos lista ligada se você fez listas ligadas em suas tabelas de hash, se você fez uma tabela hash. Eu recomendo fortemente a fazer uma tabela hash. Você já deve ter feito uma trie, mas tentativas são mais difíceis. Em teoria, eles são assintoticamente melhor. Mas basta olhar para a placa grande, e tenta não fazer melhor, e eles ocupam mais memória. Tudo sobre tenta acaba sendo pior para mais trabalho. É o que solução David Malan sempre é Ele é sempre mensagens Sua solução trie, e vamos ver onde ele é atualmente. O que ele estava sob, David J? Ele é n º 18, de modo que não é terrivelmente ruim, e que vai ser um dos melhores tentativas você pode pensar ou um dos melhores da procura de um trie. Não é mesmo a sua solução original? Eu me sinto como soluções trie tendem a ser mais nesta faixa de uso de RAM. 

Vá até o topo, e uso de RAM está na casa de um dígito. Desça para o fundo, e então você começa a ver tenta onde você começa o uso de RAM absolutamente enorme, e tentativas são mais difíceis. Não inteiramente pena, mas uma experiência educacional se você fez um. A última coisa é a nossa lista ligada, e essas três coisas, pilhas, filas e listas ligadas, qualquer coisa futura que você faz em ciência da computação supor que você tem familiaridade com essas coisas. Eles são tão fundamental para tudo. 

Listas ligadas, e aqui temos uma lista vinculada isoladamente vai ser nossa implementação. O que significa vinculada isoladamente ao contrário duplamente ligada? Sim. [Estudante] É apenas aponta para o ponteiro próximo e não para os ponteiros, como o que precede e aquele após ele. É, então, em formato de imagem, o que eu faço? Eu tenho duas coisas. Eu tenho imagem e imagem. Em formato de imagem, os nossos individualmente listas ligadas, inevitavelmente, nós temos algum tipo de ponteiro para a cabeça da nossa lista, e, em seguida, dentro de nossa lista, só temos ponteiros, e talvez isso aponta para nulo. Vai ser o seu desenho típico de uma lista vinculada isoladamente. Uma lista duplamente ligada, você pode ir para trás. Se eu lhe der qualquer nó na lista, então você pode necessariamente chegar a qualquer outro nó na lista se ele é uma lista duplamente ligada. Mas se eu te o terceiro nó na lista e é uma lista vinculada isoladamente, nenhuma maneira que você está indo cada vez para chegar a nós de primeiro e segundo. E há benefícios e malefícios, e um um óbvio é você pegar mais tamanho, e você tem que manter o controle de onde essas coisas estão apontando agora. Mas só se preocupam vinculada isoladamente. 

Algumas coisas que vamos ter que implementar. Seu nó typedef struct, int i: struct node * seguinte; nó. Typedef que devem ser queimados em suas mentes. Quiz 1 deve ser como dar um typedef de um nó de lista ligada, e você deve ser capaz de rabiscar imediatamente que para baixo sem sequer pensar sobre isso. Eu acho que algumas perguntas, por que precisamos de struct aqui? Por que não podemos dizer * nó? [Estudante] [inaudível] Sim. A única coisa que define um nó como uma coisa é o typedef si. Mas a partir deste ponto, quando estamos tipo de análise por esta definição do nó de estrutura, nós não terminamos nosso typedef ainda, então desde o typedef não terminou, nó não existe. Mas struct nó faz, e esse nó aqui, isso também poderia ser chamado de qualquer outra coisa. Isto poderia ser chamado n. Poderia ser chamado de nó de lista encadeada. Poderia ser chamado de qualquer coisa. Mas esse nó estrutura precisa ser chamada a mesma coisa que este nó struct. O que você chama isso tem que ser também aqui, e para que também responde o segundo ponto da questão é por isso que, muitas vezes, quando você ver estruturas e typedefs de estruturas, você vai ver estruturas anónimos onde você só vai ver typedef struct, implementação de dicionário estrutura, ou o que seja. 

Por que aqui não precisamos dizer nó? Por que não pode ser uma estrutura anônimo? É quase a mesma resposta. [Estudante] Você precisa se referir a ele dentro da estrutura. Sim, dentro da estrutura, que você precisa para se referir à estrutura em si. Se você não dá a estrutura de um nome, se é uma estrutura anônimo, você não pode se referir a ele. E por último, mas, pelo menos, estes não devem ser todos um pouco simples, e eles devem ajudar você a perceber se você está escrevendo isso que você está fazendo algo errado, se este tipo de coisas não fazem sentido. Por último, mas não menos importante, por que isso tem que ser struct * nó? Por que não pode ser apenas struct próximo nó? [Estudante] Ponteiro para a estrutura que vem. Isso é inevitável o que queremos. Por que ele nunca ser nó struct próximo? Por que tem que ser struct node * próximo? Sim. [Estudante] É como um loop infinito. Sim. [Estudante] Seria tudo em um. Sim, só de pensar como seria fazer o tamanho ou algo assim. Tamanho de uma estrutura é basicamente + ou - um padrão aqui ou ali. É basicamente vai ser a soma dos tamanhos das coisas na estrutura. Isso aqui, sem mudar nada, o tamanho vai ser fácil. Tamanho do nó struct vai ser tamanho de i + tamanho do próximo. Tamanho da i vai ser 4. Tamanho da próxima vai ser 4. Tamanho do nó struct vai ser 8. Se não temos o *, pensando sizeof, em seguida, sizeof (i) vai ser 4. Tamanho do nó struct próximo vai ser o tamanho da i + tamanho do nó seguinte struct + Tamanho da i + tamanho do nó struct seguinte. Seria uma recursividade infinita de nós. É por isso que esta é a forma como as coisas têm que ser. 

Mais uma vez, definitivamente memorizar que, ou pelo menos entendê-lo o suficiente para que você pode ser capaz de razão pela qual ele deve ser parecido. As coisas que vamos querer implementar. Se o comprimento da lista você pode enganar e manter em torno de um comprimento global ou algo assim, mas nós não vamos fazer isso. Nós vamos contar o tamanho da lista. Nós contém, de modo que é, basicamente, como uma pesquisa, por isso temos uma lista ligada de inteiros para ver se este inteiro está na lista ligada. Prepend vai inserir no início da lista. Anexar vai inserir no fim. Insert_sorted vai inserir na posição classificada na lista. Tipo de Insert_sorted assume que você nunca usou preceder ou anexar em maus caminhos. 

Insert_sorted quando você está implementando insert_sorted- vamos dizer que temos a nossa lista ligada. Isto é o que parece actualmente, 2, 4, 5. Quero inserir 3, por isso, enquanto a própria lista já está classificado, é fácil encontrar onde 3 pertence. Eu começo no 2. Ok, 3 é maior que 2, então eu quero continuar. Oh, 4 é muito grande, então eu sei 3 está a ir entre 2 e 4, e eu tenho que corrigir ponteiros e todas essas coisas. Mas se nós não estritamente usar insert_sorted, como vamos apenas dizer que eu preceder 6, então minha lista encadeada vai se tornar isso. Ele agora não faz sentido, portanto, para insert_sorted, você pode simplesmente assumir que a lista é ordenada, embora existam operações o que pode causar-lhe para não ser ordenado, e é isso. Encontre um útil de inserção, de modo essas são as principais coisas que você vai ter que implementar. 

Por agora, tomar um minuto para fazer comprimento e contém, e os que devem ser relativamente rápida. Aproximando-se o tempo de fechamento, por isso ninguém tem nada para o comprimento ou contém? Eles vão ser quase idênticos. [Estudante] Comprimento. Vamos ver, de revisão. Okay. Você quer explicar? [Estudante] Eu só criar um nó ponteiro e inicializar a primeira, que é a nossa variável global, e então eu verificar para ver se é nulo, então eu não tiver uma falha de seg e retornar 0 se for o caso. Caso contrário, eu percorrer, mantendo o controle de dentro inteiro quantas vezes eu já acessou o elemento seguinte da lista e na operação mesmo incremento também acessar esse elemento real, e então eu continuamente fazer a verificação para ver se é nulo, e se é nulo, então ele aborta e só retorna o número de elementos que eu acessados. 

[Rob B.] Alguém tem algum comentário sobre qualquer coisa? Isso parece correto bem sábio. [Estudante] Eu não acho que você precisa do nó == null. É, então, se o nó == 0 retorno nulo. Mas se nulo nó == então esta-oh, não é uma questão de correção. Era só você está retornando i, mas não é de âmbito agora. Você só precisa int i, para i = 0. Mas se o nó é nulo, então eu ainda vai ser 0, e nós estamos indo para retornar 0, portanto, neste caso, é idêntico. Outra coisa comum é a de manter a declaração de dentro do nó do laço for. Você poderia dizer-oh, não. Vamos mantê-lo como este. Eu, provavelmente, colocar int i = 0 aqui, então nó * nó = primeiro aqui. E este é, provavelmente, como-se livrar disso agora. Este é, provavelmente, como eu teria escrito. Você também pode olhar-lo assim. Esta estrutura de loop para aqui deve ser quase tão natural para você quanto para int i = 0 i é inferior ao comprimento da matriz i + +. Se é assim que você iterar sobre uma matriz, isto é como você iterar sobre uma lista ligada. 

Esta deve ser uma segunda natureza em algum ponto. Com isso em mente, este vai ser quase a mesma coisa. Você vai querer iterar sobre uma lista encadeada. Se o nó-Eu não tenho nenhuma idéia do que o valor é chamado. Nó i. Se o valor desse nó = i retornar verdadeiro, e é isso. Observe que a única maneira de sempre retornar false é se iterar sobre a lista inteira ligada e nunca mais voltar verdade, de modo que é o que este faz. Como uma nota lateral, provavelmente não vai começar a acrescentar ou preceder. 

Última nota rápida. Se você ver a palavra-chave estática, então vamos dizer contagem static int = 0, então o que fazemos contagem + +, você pode basicamente pensar nisso como uma variável global, mesmo que eu disse não é assim que nós vamos implementar comprimento. Eu estou fazendo isso aqui, e então contar + +. Qualquer forma, podemos introduzir um nó em nossa lista ligada estamos incrementando nossa contagem. O ponto é que a palavra-chave static significa. Se eu tivesse int count = 0 que seria uma variável antiga regulares global. O que significa contagem static int é que ela é uma variável global para este arquivo. É impossível para algum outro arquivo, gosto de pensar em pset 5, se você começou. Você tem tanto speller.c, e você tem dictionary.c, e se você simplesmente declarar uma coisa global, então qualquer coisa em speller.c pode ser acessado no dictionary.c e vice-versa. As variáveis ​​globais são acessíveis por qualquer arquivo c., mas variáveis ​​estáticas só são acessíveis a partir de dentro do próprio arquivo, para dentro de corretor ortográfico ou dentro de dictionary.c, este é o tipo de como eu iria declarar minha variável para o tamanho da minha matriz ou o tamanho do meu número de palavras no dicionário. Desde que eu não quero declarar uma variável global que qualquer um tem acesso, Eu realmente só se preocupam com isso para meus próprios propósitos. 

A coisa boa sobre isso é também o material de colisão todo nome. Se algum outro arquivo tenta usar uma variável global chamada contagem, as coisas vão muito, muito errado, de modo que este mantém as coisas bem seguro, e só você pode acessá-lo, e ninguém mais pode, e se alguém declara uma variável global chamada contagem, então ele não irá interferir com a sua variável estática chamada contagem. Isso é o que é estática. É uma variável de arquivo global. 

Perguntas sobre alguma coisa? Tudo pronto. Tchau. [CS50.TV]