Apostila de Estrutura de Dados

Apostila de Estrutura de Dados

(Parte 1 de 11)

JOÃO PESSOA / PB JULHO / 2003

1 – INTRODUÇÃO3
2 – LISTAS4
3 – LISTAS ORDENADAS16
4 – PILHAS2
5 – FILAS27
6 – ÁRVORES34
7 – ÁRVORE BINÁRIA39
8 – PESQUISA DE DADOS45
9 – ÁRVORE BINÁRIA DE PESQUISA49
10 – ÁRVORE AVL53
1 – INDEXAÇÃO61
12 – HASHING63
13 – ÁRVORE-B6

1 – INTRODUÇÃO

O que é uma Estrutura de Dados (ED)?

· Tipos de Dados • Estruturas de Dados e

• Tipos Abstratos de Dados

Embora estes termos sejam parecidos, eles têm significados diferentes. Em linguagens de programação, o tipo de dados de uma variável define o conjunto de valores que a variável pode assumir. Por exemplo, uma variável do tipo lógico pode assumir o valor verdadeiro ou falso.

Uma declaração de variável em uma linguagem como C ou Pascal especifica:

1. O conjunto de valores que pode assumir. 2. O conjunto de operações que podemos efetuar.

3. A quantidade de bytes que deve ser reservada para ela. 4. Como o dado representado por esses bytes deve ser interpretado (por exemplo, uma cadeia de bits pode ser interpretada como um inteiro ou real...).

Então, tipos de dados podem ser vistos como métodos para interpretar o conteúdo da memória do computador.

Mas podemos ver o conceito de Tipo de Dados de uma outra perspectiva: não em termos do que um computador pode fazer (interpretar os bits...) mas em termos do que os usuários desejam fazer (somar dois inteiros...)

Este conceito de Tipo de Dado divorciado do hardware é chamado Tipo Abstrato de Dado - TAD. Estrutura de Dados é um método particular de se implementar um TAD.

A implementação de um TAD escolhe uma ED para representá-lo. Cada ED é construída dos tipos primitivos (inteiro, real, char,...) ou dos tipos compostos (array, registro,...) de uma linguagem de programação.

Não importa que tipo de dados estaremos trabalhando, a primeira operação a ser efetuada em um TAD é a criação. Depois, podemos realizar inclusões e remoções de dados. A operação que varre todos os dados armazenados num TAD é o percurso, podendo também ser realizada uma busca por algum valor dentro da estrutura.

Lineares: - Listas Ordenadas

- Pilhas - Filas

- Deques

Não Lineares: - Árvores

- Grafos

2 – LISTAS

São estruturas formadas por um conjunto de dados de forma a preservar a relação de ordem linear entre eles. Uma lista é composta por nós, os quais podem conter, cada um deles, um dado primitivo ou composto.

L1 L2 L3Ln-1 Ln

Sendo:

L1 à 1º elemento da lista L2 à Sucessor de L1

Ln-1 à Antecessor de Ln-1 Ln à Último elemento da lista.

· Lista Telefônica • Lista de clientes de uma agência bancária

• Lista de setores de disco a serem acessados por um sistema operacional • Lista de pacotes a serem transmitidos em um nó de uma rede de computação de pacotes.

Operações Realizadas com Listas: • Criar uma lista vazia

• Verificar se uma lista está vazia • Obter o tamanho da uma lista

• Obter/modificar o valor do elemento de uma determinada posição na lista • Obter a posição de elemento cujo valor é dado

• Inserir um novo elemento após (ou antes) de uma determinada posição na lista

• Remover um elemento de uma determinada posição na lista • Exibir os elementos de uma lista

• Concatenar duas listas a) Seqüencial:

Explora a sequencialidade da memória do computador, de tal forma que os nós de uma lista sejam armazenados em endereços sequenciais, ou igualmente distanciados um do outro. Pode ser representado por um vetor na memória principal ou um arquivo seqüencial em disco.

L pato cabra rato anta macaco

b) Encadeada:

conter, além do dado propriamente dito, uma referência para o próximo elemento da lista

Esta estrutura é tida como uma seqüência de elementos encadeados por ponteiros, ou seja, cada elemento deve Ex: L = pato, cabra, rato, anta, macaco patopato macacomacaco antaanta ratorato cabracabra L

Uma lista representada de forma seqüencial é um conjunto de registros onde estão estabelecidas regras de precedência entre seus elementos. O sucessor de um elemento ocupa posição física subsequente.

A implementação de operações pode ser feita utilizando array e registro, associando o elemento a(i) com o índice i (mapeamento seqüencial).

· os elementos na lista estão armazenados fisicamente em posições consecutivas;

• a inserção de um elemento na posição a(i) causa o deslocamento a direita do elemento de a(i) ao último; • a eliminação do elemento a(i) requer o deslocamento à esquerda do a(i+1) ao último;

Mas, absolutamente, uma lista seqüencial ou é vazia ou pode ser escrita como (a(1), a(2), a(3),a(n)) onde a(i) são

átomos de um mesmo conjunto A.

Além disso, a(1) é o primeiro elemento, a(i) precede a(i+1), e a(n) é o último elemento.

Assim as propriedades estruturadas da lista permitem responder a questões tais como: • se uma lista está vazia

• se uma lista está cheia

• quantos elementos existem na lista

• qual é o elemento de uma determinada posição • qual a posição de um determinado elemento

• inserir um elemento na lista

• eliminar um elemento da lista

Conseqüência: As quatro primeiras operações são feitas em tempo constante. As demais, porém, requererão mais cuidados.

Vantagem:

• acesso direto indexado a qualquer elemento da lista • tempo constante para acessar o elemento i - dependerá somente do índice.

(Parte 1 de 11)

Comentários