ALGORITMOS E ESTRUTURA DE DADOS II

ALGORITMOS E ESTRUTURA DE DADOS II

Leandro Rosniak Tibola
E-mail: [e-mail]
Página Pessoal: www.fw.uri.br/~tibola

Sumário

1 Listas Lineares
3
1.1 Alocação Estática versus Dinâmica
4
1.2 Alocação Seqüencial
4
1.3 Alocação Encadeada
5

2 Pilhas
6
2.1 Declarando e inicializando uma pilha
7
2.2 Verificando limites da pilha
7
2.3 Inserindo e removendo elementos na pilha
7
2.4 Verificando o elemento do topo da pilha
8

3 Filas
9
3.1 Declarando e inicializando uma fila
10
3.2 Verificando limites da fila
10
3.3 Inserindo e removendo elementos da fila
10
3.4 Problemas na implementação seqüencial de filas
11
3.5 Implementação circular para filas
11
3.6 Inserindo e removendo elementos da fila circular
12

4 Classificação por Inserção
13
4.1 Método da Inserção Direta.
13
4.1.1 Exemplo e implementação de Inserção Direta
13
4.1.2 Análise do Desempenho
14
4.2 Inserção Direta com Busca Binária
15
4.3 Método dos Incrementos Decrescentes - Shellsort
16
4.3.1 Exemplo Incrementos Decrescentes – Shellsort
16
4.3.2 Implementação
17
4.3.3 Análise do Desempenho
17

5 Classificação por Trocas
19
5.1 Método da Bolha – Bubblesort
19
5.1.1 Implementação
20
5.1.2 Análise do Desempenho
20
5.2 Método da Agitação - Shakesort
21
5.3 Método do Pente – Combsort
21
5.4 Método de Partição e Troca - Quicksort
22
5.4.1 Descrição do Método
23
5.4.2 Implementação
25
5.4.3 Análise do Desempenho
26

6 Classificação por Seleção
29
6.1 Método de Seleção Direta
29
6.1.1 Implementação
29
6.1.2 Análise do Desempenho
30
6.2 Método da Seleção em Árvore – HeapSort
30
6.2.1 Exemplo
32
6.2.2 Implementação
37
6.2.3 Análise do Desempenho
38
6.3 Método de Seleção em Árvore Amarrada – ThreadedHeapSort
38

7 Classificação por Distribuição de Chaves - Radixsort
41
7.1 Implementação
43
7.2 Desempenho
45

8 Classificação por Intercalação
46
8.1 Implementação
46
8.2 Análise do