MC202 - Estruturas de Dados

Créditos: 6
Horas semanais de atividades teóricas: 4
Horas semanais de atividades de laboratório: 2
Oferecimento: Ambos os períodos letivos
 
Pré-Requisitos
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

Tópicos a serem estudados (preferencialmente nesta ordem):

1 – Algoritmos recursivos de ordenação (Merge Sort e Quicksort)

2 – Estruturas ligadas: nó, apontador, variável apontadora, alocação dinâmica de memória

3 – Listas ligadas: operações básicas (busca, inserção e remoção)

4 – Exemplos de algoritmos para listas ligadas (inversão, cópia e concatenação)

5 – Comparação de listas ligadas com vetores

6 – Listas circulares, duplamente ligadas, com nó cabeça

7 – Algoritmos de ordenação em listas ligadas (Selection Sort, Insertion Sort e Bubble Sort)

8 – Intercalação de listas ligadas (merge) e aplicações (Merge Sort)

9 – Pilhas, filas e aplicações

10 – Fila de prioridade (heap) e Heapsort

11 – Árvores binárias: representação e percurso (recursivo e não recursivo)

12 – Árvores de busca (busca, inserção e remoção)

13 – Árvores binárias de busca balanceadas (AVL, Rubro-Negra ou Auto-Ajustáveis)

14 – Árvores gerais: definição, representação por listas ligadas e percursos

15 – Árvores B e generalizações

16 – Introdução ao espalhamento (hashing): conceito, implementação com listas ligadas

17 – Grafos: conceitos básicos, representação por matrizes e listas ligadas

18 – Percurso de grafos em largura e profundidade

Tópicos opcionais:

– Matrizes esparsas

– Listas generalizadas

– Listas invertidas

– 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.