MC202 - Estruturas de Dados

A partir de 2011

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 - Árvores binárias de busca balanceadas
12 - Fila de prioridade (heap) implementação com vetor e heapsort
13 - Árvores gerais: definição, representação por listas, percursos
14 - Listas generalizadas e uso para representar estruturas ligadas em geral
15 - Árvores B e generalizações
16 - Introdução ao espalhamento (hashing): conceito, implementação com listas ligadas. Técnicas de espalhamento para arquivos
17 - Grafos: conceito, representação por matrizes e listas ligadas
18 - Percurso de grafos em largura e profundidade
19 - 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.