CS50CS50x em Português - Aula 5 - Estruturas de Dados
CS50
Última semana em C 0:44
Esta é a semana 5 do curso e o foco será estruturas de dados, um tema já tocado de forma simples antes, mas agora explorado com mais profundidade. Esta é a última semana trabalhando com C, já que na semana seguinte o curso migra para Python, uma linguagem de nível mais alto que facilita a vida do programador, embora o código resultante não rode tão rápido quanto o C. O tema central, tanto desta semana quanto da próxima, continua sendo as trocas, ou seja, os prós e contras de cada escolha de implementação.
Pilhas e filas no cotidiano 1:31
Uma pequena animação conta a história de Jack, que guardava roupas, CDs e livros em uma caixa amontoada, sempre pegando o item de cima e devolvendo ali mesmo depois de usar. Seu amigo Lou percebe o problema e sugere organizar tudo em fileiras dentro de um armário, guardando as roupas usadas à esquerda e pegando as próximas sempre da direita, garantindo que tudo seja usado antes de repetir algo. Essa história ilustra duas estruturas de dados abstratas: a pilha, onde você sempre acessa o item colocado por último, e a fila, onde você acessa sempre o item que está lá há mais tempo.
Fila com propriedade FIFO 3:31
Uma fila é algo vivido constantemente, como ao esperar em uma loja ou evento, e sua propriedade central é a justiça: quem chega primeiro sai primeiro, o que os cientistas da computação chamam de FIFO, primeiro a entrar, primeiro a sair. As duas operações fundamentais de uma fila são enfileirar, que significa entrar na fila, e desenfileirar, que significa sair pela frente. Em código C, uma fila pode ser implementada como uma estrutura contendo um array de pessoas com capacidade fixa, por exemplo cinquenta, e uma variável separada para guardar o tamanho atual, ou seja, quantas posições do array estão realmente ocupadas. O problema dessa implementação é que o tamanho é decidido antes mesmo de compilar o código, então se aparecer uma pessoa a mais que a capacidade prevista, não há como registrá-la, e aumentar demais o tamanho apenas desperdiça memória à toa.
Pilha com propriedade LIFO 7:04
A pilha, ao contrário, segue a propriedade LIFO, último a entrar, primeiro a sair, como aconteceu com as roupas de Jack ou como acontece com e-mails novos que aparecem sempre no topo da caixa de entrada, fazendo com que as pessoas tendam a responder primeiro às mensagens mais recentes. As operações equivalentes na pilha são chamadas de push, empurrar algo para o topo, e pop, remover algo do topo, exemplificadas pela pilha de bandejas em um refeitório, onde a bandeja do fundo pode nunca ser realmente usada. Em código, uma pilha pode ser implementada com a mesma estrutura de array e contador de tamanho usada na fila, sendo até mais simples porque a remoção sempre ocorre no final do array, mas carrega a mesma limitação de tamanho fixo definido previamente.
Dicionários como pares chave-valor 10:31
Um dicionário é outro tipo de dado abstrato onipresente, representado como uma tabela de duas colunas, palavra e definição, ou nome e número numa lista telefônica. Generalizando, um cientista da computação chama a coluna da esquerda de chave e a da direita de valor, formando o chamado par chave-valor, essencial sempre que se quer associar um dado a outro. Assim como filas e pilhas, dicionários podem ser implementados de formas diferentes, sendo algumas mais rápidas e outras mais lentas, e aplicativos de contatos em smartphones certamente não usam arrays de tamanho fixo, pois isso limitaria artificialmente o número de amigos possíveis.
Arrays estáticos e seus limites 12:33
Um array armazena valores sequencialmente na memória e exige que seu tamanho seja decidido antecipadamente, no momento da compilação. Um programa de demonstração em C, chamado list.c, cria um array estático de três inteiros, 1, 2 e 3, e os imprime com um laço for, mostrando a mecânica básica. O problema aparece quando se precisa adicionar um quarto valor: como o array está cercado por outros dados na memória, não há garantia de espaço livre ao lado dele, sendo necessário alocar um novo bloco maior e copiar os valores antigos para lá.
Alocação dinâmica com malloc 16:31
Usando malloc, é possível alocar memória para o array em tempo de execução, pedindo, por exemplo, espaço para três inteiros multiplicando três pelo tamanho de um int. O valor retornado por malloc é o endereço do primeiro byte do bloco, que pode ser tratado com a mesma notação de colchetes usada em arrays comuns, já que a linguagem C permite essa equivalência entre ponteiros e arrays. Quando surge a necessidade de mais espaço, simplesmente reatribuir a mesma variável a um novo malloc sem antes copiar os dados antigos causa um vazamento de memória, porque o ponteiro original é perdido e aquele bloco antigo fica inacessível, mas ainda ocupado.
Copiando dados com segurança 21:30
A solução correta envolve criar uma variável temporária, chamada tmp, para guardar o endereço do novo bloco de memória maior, copiar os valores antigos para lá usando um laço for, e só então adicionar o novo valor desejado, como o número 4 na quarta posição. Duas boas práticas de segurança com malloc são sempre verificar se o retorno não é nulo, o que indicaria falta de memória ou outro erro, e sempre liberar a memória que não é mais necessária. Por fim, é importante lembrar que, ao verificar se a segunda chamada de malloc falhou, o primeiro bloco de memória alocado com sucesso ainda precisa ser liberado antes de encerrar o programa, para não deixar memória perdida para trás.
Liberando e realocando memória na lista 24:31
Depois de copiar os valores antigos para o novo bloco de memória, o próximo passo é liberar a lista original e atualizar a variável de lista para apontar para o novo bloco recém-alocado. Ao final do programa, essa nova lista também precisa ser liberada, já que agora ela aponta para o pedaço maior de memória contendo os quatro valores. Durante a demonstração, aparece um erro de compilação porque a função malloc não foi declarada, o que se resolve incluindo a biblioteca stdlib.h junto com stdio.h.
A função realloc simplifica o processo 28:31
Em vez de alocar manualmente um novo bloco, copiar valores com um laço e depois liberar o bloco antigo, existe a função realloc, também definida em stdlib.h, que tenta aumentar o bloco de memória existente ou, se não houver espaço, copia automaticamente os dados para um novo local. Mesmo assim, é preciso verificar se o retorno é nulo, liberar a lista original em caso de erro e adicionar manualmente o novo valor, já que o realloc não sabe o que mais se quer armazenar. Usar uma variável temporária continua sendo necessário, pois se o realloc falhar e sobrescrevermos diretamente a variável da lista, perdemos a referência ao bloco original.
Como o realloc sabe o que fazer 29:02
O primeiro argumento passado ao realloc é o endereço do bloco de memória alocado anteriormente com malloc, permitindo que a função saiba onde procurar espaço adicional ou decida mover os dados para outro lugar. O sistema, por meio da biblioteca padrão, mantém uma espécie de tabela que registra qual memória já foi alocada. Mesmo assim, o realloc pode falhar e retornar nulo se a memória estiver fragmentada, ou seja, se os bytes livres estiverem espalhados em pedaços pequenos demais para formar um bloco contíguo do tamanho necessário.
Arrays versus listas encadeadas 31:32
Um array é rápido porque os dados ficam em um bloco contíguo de memória, permitindo até busca binária, mas seu tamanho é fixo e redimensioná-lo exige bastante código, como visto nos exemplos anteriores. Uma alternativa é a lista encadeada, que não exige que os valores fiquem lado a lado na memória. Cada valor é acompanhado de um metadado, um ponteiro para o próximo valor, formando algo como um mapa de tesouro que liga um nó ao outro até chegar a um ponteiro nulo, que marca o fim da lista. Essa estrutura genérica que guarda um valor e um ponteiro para o próximo é chamada de nó, e é assim que listas em Python, por exemplo, funcionam por baixo dos panos.
Definindo a estrutura struct node em C 38:00
Para representar um nó em código C, reaproveita-se a struct usada antes para pessoas, mas agora com um inteiro para o valor e um ponteiro chamado next para o próximo nó, do tipo struct node estrela. É necessário dar um nome à struct logo no início, como struct node, porque o compilador lê o código de cima para baixo e ainda não conheceria a palavra node ao declarar o ponteiro dentro da própria struct. Essa é a mesma lógica dos protótipos de função vistos anteriormente.
Construindo a lista encadeada passo a passo 40:00
No código, a lista encadeada começa vazia, representada por uma variável do tipo node estrela definida como nula, já que a lista é, por definição, o endereço do primeiro nó. Em um laço que se repete três vezes, aloca-se memória para um novo nó com malloc, verifica-se se o retorno não é nulo, pede-se ao usuário um número para armazenar no campo number, e define-se o campo next como nulo. Em seguida, o novo nó é inserido no início da lista, fazendo o ponteiro next do novo nó apontar para o antigo início da lista e atualizando a lista para apontar para o novo nó. A notação com seta, como n->number e n->next, substitui a forma mais complicada de desreferenciar com asterisco e ponto, e representa visualmente a mesma seta desenhada nas explicações com ponteiros.
Construindo a lista e evitando vazamentos de memória 49:30
Ao continuar inserindo os números 2 e 3, o professor mostra o processo de alocar um novo nó, definir seu valor e depois encaixá-lo na lista existente. Ele demonstra um erro comum: se você atualizar a variável 'list' para apontar para o novo nó antes de conectar o campo 'next' desse novo nó ao restante da lista, você perde a referência ao nó anterior. Isso é chamado de vazamento de memória, porque aquele pedaço de memória continua ocupado, mas o programa não tem mais como acessá-lo ou liberá-lo. A solução correta é primeiro apontar o campo 'next' do novo nó para o que a lista já apontava, e só depois atualizar a lista para apontar para o novo nó. Ele compara essa técnica a amarrar grãos de pipoca em um fio na época de Natal: cada grão precisa estar conectado ao próximo antes de soltar a ponta anterior, senão parte do fio se perde.
Percorrendo a lista para imprimir os valores 52:31
Com a lista construída, mas em ordem invertida, o professor mostra como percorrê-la usando uma variável temporária chamada 'ptr' ou 'pointer', que funciona como outro dedo apontando para o início da lista. O código imprime o valor do nó atual, depois atualiza o ponteiro para o campo 'next', repetindo até chegar a nulo. Ele implementa essa lógica tanto com um loop 'while' quanto com um loop 'for' equivalente, destacando que a versão com 'while' é mais legível, embora a versão com 'for' seja mais compacta. Em resposta a perguntas da turma, ele explica que o uso de mais memória, como a variável temporária 'n' e 'pointer', é o preço a pagar pelo benefício de uma estrutura de dados que cresce e diminui dinamicamente: tempo, espaço e outros recursos sempre precisam ser avaliados em conjunto.
Tempo de execução das operações na lista 1:00:00
O professor analisa o tempo de execução, em notação Big O, das principais operações de uma lista encadeada. Quando novos elementos são sempre inseridos no início da lista, a inserção é Big O de 1, pois não é necessário percorrer a lista inteira. Porém, essa abordagem deixa os elementos fora de ordem, o que torna busca, percurso e exclusão todas Big O de n, já que no pior caso o elemento procurado está no final.
Inserção no final e a necessidade de ordem 1:03:00
Ele testa uma segunda estratégia: inserir sempre no final da lista. Isso também resulta em Big O de n para a inserção, o que é pior que a abordagem anterior. O verdadeiro objetivo, no entanto, é manter a lista sempre em ordem crescente, independentemente da ordem em que os números são digitados, da mesma forma que uma lista de contatos no celular aparece organizada. Ele divide o problema em quatro cenários possíveis: a lista está vazia, o novo número pertence ao início, pertence ao final, ou pertence a algum lugar no meio.
Implementando a inserção ordenada em código 1:06:00
Usando versões prontas do código no VS Code, o professor mostra como tratar cada um dos quatro cenários separadamente: lista vazia, inserção no início, inserção no final e inserção no meio. O caso mais delicado é o do meio, onde é preciso ajustar dois ponteiros com cuidado, primeiro conectando o novo nó ao próximo nó da sequência, depois religando o nó anterior ao novo nó. Ele reforça que a ordem das operações importa muito, já que um erro pode desconectar partes da lista. Por fim, mostra o código que libera cada nó da memória usando 'free', explicando que essa função não sabe nada sobre listas encadeadas: é preciso percorrer a lista manualmente, guardando um ponteiro para o próximo nó antes de liberar o atual, repetindo essa sequência até o fim, para não perder o rastro dos nós restantes.
Falha de malloc e função de descarregamento 1:14:35
O professor mostra um bug sutil na lista encadeada: se malloc falhar numa iteração posterior do loop, a memória alocada nas iterações anteriores fica sem ser liberada. Para resolver isso de forma elegante, ele cria uma função separada de descarregamento que percorre a lista e libera cada nó, podendo ser chamada tanto em caso de erro quanto no final normal do programa, evitando copiar e colar código repetido.
O preço da lista encadeada 1:16:59
Depois de todo o trabalho para montar a lista encadeada, ele revela o custo: inserir, pesquisar e deletar são todos O grande de n, ou seja, tempo linear. Isso é pior do que a busca binária em arrays ordenados, que era O grande de log n. Ganhamos dinamismo, a capacidade de crescer a estrutura sem desperdiçar memória, mas perdemos a velocidade que os arrays ordenados ofereciam.
Recapitulando arrays e listas encadeadas 1:18:01
Arrays são rápidos porque ficam contíguos na memória, permitindo busca binária em tempo logarítmico, mas têm tamanho fixo e redimensionar exige copiar todos os elementos para um novo espaço, o que é caro para milhões de valores. Listas encadeadas resolvem isso alocando memória nó a nó, sem precisar mover nada, mas perdem a busca binária porque não há como saltar direto para o meio sem percorrer a lista inteira primeiro, tornando toda operação O grande de n.
Árvores de busca binária como combinação 1:22:02
Para juntar a velocidade dos arrays com o dinamismo das listas encadeadas, surge a árvore, a primeira estrutura de dados bidimensional apresentada. Numa árvore de busca binária, cada nó guarda um número e dois ponteiros, um para o filho esquerdo e outro para o direito, de modo que o elemento é sempre maior que o filho esquerdo e menor que o filho direito. Essa propriedade é recursiva, valendo para cada subárvore, e permite buscar um valor cortando pela metade a cada passo, restaurando o tempo logarítmico, O grande de log n, tanto para busca quanto para inserção e remoção. O custo é usar cerca de três vezes mais memória, já que cada nó carrega um inteiro e dois ponteiros em vez de um único ponteiro.
Busca recursiva e risco de degeneração 1:30:01
A função de busca em C é implementada de forma recursiva: se a árvore for nula retorna falso, se o número procurado for menor desce para a subárvore esquerda, se for maior desce para a direita, e se for igual retorna verdadeiro. Porém, se os valores forem inseridos numa ordem desfavorável, como 1, 2, 3, 4, 5 em sequência, a árvore degenera numa lista encadeada disfarçada, perdendo o benefício do tempo logarítmico e voltando a O grande de n. Estruturas mais avançadas conseguem se reequilibrar automaticamente a cada inserção para evitar esse problema, embora isso não seja implementado no curso. O professor então aponta para a meta final, um tempo de execução O grande de 1, constante, que não dependeria da quantidade de dados armazenados.
Hashing: de domínio infinito a intervalo finito 1:38:02
O hashing é apresentado como uma técnica que pega um conjunto infinito de valores possíveis e os mapeia para um número finito de categorias. O exemplo usado é o de organizar cartas de baralho: em vez de ordenar 52 cartas uma a uma, você primeiro as separa em quatro baldes por naipe, transformando um problema grande em vários problemas menores e mais simples. Essa mesma lógica pode ser aplicada a números ou palavras, mapeando-os para um número finito de 'buckets' para resolver o problema de forma mais eficiente.
Função hash aplicada a nomes 1:42:31
A ideia é usar uma função hash para decidir em qual balde um dado deve ir, como no caso de uma agenda de contatos. Em vez de buscar um nome do início ao fim, ou dividir a lista pela metade repetidamente, a função hash calcula diretamente o balde certo, por exemplo, usando a primeira letra do nome. Assim, Mario cairia no balde 12, correspondente à letra M, e Luigi no balde 11, correspondente à letra L, transformando o alfabeto inglês de 26 letras no intervalo finito de saída. Em C, essa função pode ser escrita convertendo a primeira letra para maiúscula e subtraindo o valor ASCII de 'A', retornando um número entre 0 e 25.
Tabelas hash e colisões 1:45:00
Uma tabela hash combina um array de tamanho fixo, como 26 posições para as letras do alfabeto, com listas encadeadas dentro de cada posição. Ela é descrita como uma das estruturas de dados mais úteis que existem, por permitir associar chaves a valores, da mesma forma que uma lista telefônica associa nomes a números ou um dicionário associa palavras a definições. O problema surge quando vários nomes caem no mesmo balde, chamado de colisão: por exemplo, muitos personagens do universo Nintendo começam com M ou L. A solução é encadear esses nomes em uma lista ligada dentro do próprio balde, evitando sobrescrever ou descartar dados.
O custo de reduzir colisões 1:52:01
Usar mais letras do nome como base do hash, como as três primeiras letras em vez de apenas uma, reduz a chance de colisões, mas exige muito mais memória, pois é preciso criar buckets para praticamente todas as combinações possíveis, mesmo aquelas que nunca serão usadas. Mesmo com uma tabela hash bem construída, o tempo de busca continua sendo, em termos assintóticos, da ordem de n, porque cada lista dentro de um balde ainda cresce proporcionalmente ao tamanho total dos dados, apesar de ser, na prática, várias vezes mais rápida que uma lista encadeada simples.
Tries: alcançando tempo constante 1:53:33
A trie é apresentada como uma árvore feita de arrays, em que cada nó contém 26 posições, uma para cada letra do alfabeto, e cada ponteiro aponta para o próximo nó representando a letra seguinte de um nome. Para inserir um nome como Toad, percorre-se a estrutura letra por letra, criando nós conforme necessário e marcando com um booleano o ponto em que o nome termina. Isso permite buscar um nome em um número fixo de passos, igual ao número de letras do próprio nome, independentemente de o conjunto de dados ter três ou três milhões de nomes, alcançando finalmente o tempo constante buscado desde o início. A grande desvantagem é o desperdício de memória, já que a maioria dos ponteiros em cada array permanece nula, motivo pelo qual o conjunto de problemas 5 pede a implementação de tabelas hash em vez de tries.
Hashing na vida real: o exemplo da Sweetgreen 2:01:32
O professor descreve como a rede de restaurantes Sweetgreen usa hashing para organizar as saladas dos clientes em prateleiras de madeira, separadas por faixas de letras do nome, como A a E ou F a J. Isso mostra na prática o mesmo princípio de tabelas hash estudado em aula.
O problema do transbordamento nos baldes 2:02:00
Ele explica que o sistema original, com um balde por letra do alfabeto, falhava porque letras como A, B e C recebiam saladas demais e transbordavam para os baldes vizinhos, enquanto letras como Q e Z quase não eram usadas. A solução foi reduzir o número de baldes e torná-los maiores, agrupando várias letras juntas.
Traduzindo soluções reais para código 2:02:32
O ponto central é que estruturas de dados como essas, mesmo parecendo abstratas com ponteiros e desreferenciação, são apenas versões em código de soluções que já existem no mundo real. Como projeto final da semana em C, os alunos vão implementar um corretor ortográfico, carregando um arquivo com mais de 100.000 palavras em inglês na memória de forma eficiente, usando ferramentas que medem velocidade e uso de memória do código.
AI-generated summary. It can be wrong or incomplete - check anything that matters against the original.
