PRÉ-REQUISITO: MC102
EMENTA
Estruturas básicas para representação de informações: listas, árvores, grafos, e suas generalizações. Algoritmos para construção, consulta, e manipulação de tais estruturas. Desenvolvimento, implementação e testes de programas usando tais estruturas em aplicações específicas.
PROGRAMA:
1. Estruturas ligadas: nó, apontador, variável apontadora, alocação dinâmica de memória.
2. Listas ligadas simples: operações básicas.
3. Comparação de listas ligadas com vetores.
4. Algoritmos gerais para listas simples: enumeração, inversão, cópia, concatenação.
5. Pilhas, filas, e aplicações (inclusive eliminação de recursão).
6. Intercalação (merge) de listas e mergesort; análise informal.
7. Variações: listas circulares, duplamente ligadas, com cabeça. Lista livre.
8. Algoritmos de ordenação.
9. Árvores binárias: representação e percurso (recursivo).
10. Aplicação: árvores de busca (com inserção e remoção).
11. Fila de prioridade (heap) implementação com vetor e heapsort.
12. Árvores gerais: definição, representação por listas, percursos.
13. Listas generalizadas e uso para representar estruturas ligadas em geral.
14. Árvores B e generalizações.
15. Introdução ao espalhamento (hashing): conceito, implementação com listas ligadas. Técnicas de espalhamento para arquivos
16. Grafos: conceito, representação por matrizes e listas ligadas.
17. Percurso de grafos em largura e profundidade.
18. Implementação de estruturas de dados em disco
BIBLIOGRAFIA:
A. V. Aho, J. E. Hopcroft, J. Ullmann. Data Structures and Algorithms. Addison-Wesley, 1983.
W. Celes, R. Cerqueira, J. L. Rangel. Introdução a Estruturas de Dados. Campus, 2004.
T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Algoritmos - Teoria e Prática. Campus, 2002.
M. J. Folk e B. Zoellick. File Structures. Addison-Wesley, 1992.
F. Lorenzi, P. N. de Mattos, T. P. de Carvalho. Estruturas de Dados. Thomson, 2007.
S. L. Pereira. Estruturas de Dados Fundamentais. Érica, 1996.
E. M. Reingold e W. J. Hanson, Data Structures. Little-Brown (1983).
R. Sedgewick, Algorithms in C. Addison-Wesley ,1990.
J. L. Szwarcfiter e L. Markenzon. Estruturas de Dados e Seus Algoritmos. Editora LTC (1994).
D. E. Knuth, The Art of Computer Programming, Vol I: Fundamental Algorithms. Addison-Wesley (1978).
N. Wirth, Algorithms + Data Structures = Programs. Prentice-Hall (1976).
A. M. Tenembaum. Estruturas de Dados Usando C. Makron Books, 1995.
N. Ziviani. Projeto de Algoritmos. Thomson, 2004.
