apostila estrutura de dados

Universidade de São Paulo
Escola de Artes, Ciências e Humanidades
Sistemas de Informação

ACH2023 - ALGORITMOS E
ESTRUTURAS DE DADOS I

Willian Yukio Honda
Ivandré Paraboni

atualizada em 03/06/2011

Esta apostila encontra-se em fase de elaboração.
Por favor comunique eventuais erros, críticas ou sugestões escrevendo para [e-mail]

1.

Introdução

Esta apostila apresenta uma coletânea de algoritmos sobre uma variedade de estruturas de dados de memória principal estudadas na disciplina ACH2023 – Algoritmos e Estruturas de Dados I, a saber:
Listas Lineares
Sequenciais
Ligadas
Implementação Estática
Implementação Dinâmica
Técnicas Especiais: Cabeça, Sentinela, Circularidade, Encadeamento Duplo
Filas
Implementação Estática
Implementação Dinâmica
Deques (Filas de duas Pontas)
Implementação Dinâmica
Pilhas
Implementação Estática
Implementação Dinâmica
Implementação de Múltiplas Pilhas em um Vetor
Aplicações
Matrizes Esparsas
Listas Generalizadas
Listas não Lineares
Árvores Binárias
Árvores de Busca Binária
Árvores AVL

1.1.

Notação utilizada

Para simplificar o código apresentado ao longo desta apostila, tornando-o o mais genérico possível, pressupõe-se as duas definições a seguir:
// tamanho máximo do vetor estático
# define MAX 50
// definição do tipo chave utilizado typedef int TIPOCHAVE;

ACH2023 – Algoritmos e Estruturas de Dados I

2

2.

Listas Lineares

Uma lista linear é uma série de elementos ordenados na qual cada elemento exceto o primeiro possui um e apenas um antecessor, e cada elemento exceto o último possui um e apenas um sucessor.

2.1.

Listas Lineares Sequenciais

É a lista linear na qual a ordem (lógica) dos elementos da lista coincide com sua posição física (em memória).
Ou seja, elementos adjacentes da lista ocupam posições contíguas de memória.
A forma mais comum de implementação de uma lista sequencial é através de um vetor de elementos (A) do tipo REGISTRO de