Apresentação
Estrutura de Dados I. Algoritmos, estruturas de dados e abstrações em C, da análise de algoritmos às estruturas genéricas.
Bem-vindo à disciplina de Estrutura de Dados I.
Neste curso, vamos estudar como organizar, manipular e analisar dados de forma eficiente. A linguagem C será utilizada para compreender não apenas a implementação das estruturas, mas também os detalhes de memória, ponteiros, alocação dinâmica e gerenciamento de recursos que sustentam essas soluções.
O que você vai aprender
Os conteúdos estão organizados em uma progressão que conecta análise, especificação e implementação. A ordem do menu lateral é a ordem recomendada de estudo.
| Etapa | Páginas |
|---|---|
| 1. Ponto de partida | Algoritmos e estruturas de dados, guia de estilo, compilando em C e análise de algoritmos |
| 2. Memória e recursão | Alocação dinâmica de memória, ponteiros void, Valgrind e sanitizers, recursão e backtracking |
| 3. Busca | Busca sequencial e binária |
| 4. Abstração e organização | Tipos Abstratos de Dados e compilação separada e make |
| 5. Estruturas lineares | Listas simplesmente encadeadas, duplamente encadeadas e circulares, pilhas, filas e tabela de símbolos |
| 6. Árvores | Conceitos, árvores binárias, árvores binárias de busca, árvores balanceadas, AVL, rubro-negra e rubro-negra esquerdista (LLRB) |
| 7. Filas de prioridade | Fila de prioridade e heap |
| 8. Generalização | Funções de callback e estruturas genéricas |
Como estudar
Cada página combina explicação conceitual, análise de custo, implementação em C e exercícios. Os programas das páginas podem ser executados no próprio navegador, com o mesmo compilador e as mesmas verificações de memória usadas nos testes. Altere o código, execute de novo e observe o que muda. Ao longo das páginas, você vai encontrar:
- Perguntas para pensar antes de continuar a leitura, com dicas e a resposta escondidas até você pedir.
- Questões de múltipla escolha, com a explicação de cada alternativa.
- Encontre e corrija o erro: programas com um erro proposital. Execute, leia a mensagem do compilador ou do sanitizer e descubra a causa antes de abrir a resposta.
- Exercícios de implementação, corrigidos automaticamente por uma bateria de testes, que inclui casos grandes e casos de borda.
Ao estudar uma estrutura, procure sempre responder às seguintes perguntas:
- Qual problema a estrutura resolve?
- Quais operações ela oferece?
- Qual é o custo de cada operação?
- Como seus invariantes são preservados?
- Quais são suas limitações e alternativas?
A implementação é parte importante do curso, mas compreender as decisões por trás dela é o objetivo central.
Objetivos da disciplina
Ao final do curso, espera-se que você consiga analisar o custo de algoritmos, especificar Tipos Abstratos de Dados, implementar estruturas clássicas em C e selecionar uma representação adequada para cada problema.
Ementa
Fundamentos de análise de algoritmos. Conceito de Tipos Abstratos de Dados. Listas encadeadas. Pilhas e filas. Filas de prioridade e Heap. Algoritmos de busca sequencial e binária. Árvores binárias de busca não balanceadas. Árvores binárias de busca balanceadas: AVL e Rubro-Negra. Funções genéricas.
Programas necessários
Os exemplos e exercícios podem ser feitos no navegador, mas é importante ter um ambiente de desenvolvimento no seu computador, para os trabalhos e para as aulas práticas.
Compilador
- GCC (Linux)
- MinGW (Windows)
Editores e IDEs
Bibliografia
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmos: Teoria e Prática. 3. ed. Rio de Janeiro: Elsevier/Campus, 2012.
- Robert Sedgewick. Algorithms in C, Parts 1-4. 3. ed. Addison-Wesley, 2001.
- André Backes. Estrutura de Dados Descomplicada em Linguagem C. 1. ed. Elsevier, 2016.