algoritmos - estruturas - dados - java

algoritmos - estruturas - dados - java

(Parte 1 de 10)

Índice

2.1 Introdução2
2.2 Algoritmo e Implementação3
2.3 Estrutura de Dados3
2.4 Sobre este texto4

2 Introdução 2

3.1 Motivação5
3.2 O problema da listagem de alunos6
3.3 Listas8
3.4 Modelagem9
3.5 Exercícios: Armazenamento10

3 Armazenamento Sequencial 5

4.1 Os testes primeiro13
4.2 Operações em vetores16
4.3 Adicionar no fim da Lista16
4.4 O método toString() para o Vetor19
4.5 Informar o tamanho da Lista20
4.6 Verificar se um aluno está presente no vetor20
4.7 Pegar o aluno de uma dada posição do array2
4.9 Remover um aluno de uma dada posição25
4.10 Alocação Dinâmica26
4.1 Generalização27
4.12 API do Java29
4.13 Exercícios: Vetores30
4.14 Exercícios opcionais39
5.1 Solução clássica de Lista Ligada42
5.2 Célula e Lista Ligada43
5.3 Definindo a interface4
5.4 Testes45
5.5 Operações sobre uma Lista48
5.6 Adicionando no começo da Lista48
5.7 Adicionando no fim da Lista50
5.8 Percorrendo nossa Lista51
5.9 Adicionando em qualquer posição da Lista52
5.10 Pegando um elemento da Lista53
5.1 Removendo do começo da Lista53
5.12 Removendo do fim da Lista5
5.13 Removendo de qualquer posição56
5.14 Verificando se um elemento está na Lista57
5.15 O tamanho da Lista57
5.16 Lista Duplamente Ligada57
5.17 Adicionando no começo da Lista58
5.18 Adicionando no fim da Lista59
5.19 Adicionando em qualquer posição da Lista60
5.20 Removendo do começo da Lista60
5.21 Removendo do fim da Lista ou de qualquer posição61
5.2 API62
5.23 Exercícios: Lista Ligada63

5 Listas Ligadas 41 i

6.1 Introdução70
6.2 Solução do problemas das Peças72
6.3 Operações em pilhas73
6.4 Inserir uma peça74
6.5 Remover uma peça74
6.6 Informar se a pilha está vazia74
6.7 Generalização75
6.8 API do Java76
6.9 Escapando do Labirinto7
6.10 Exercícios: Pilha78
7.1 Introdução82
7.2 Interface de uso83
7.3 Operações em Fila84
7.4 Inserir uma aluno84
7.5 Remover um aluno84
7.6 Informar se a Fila está vazia84
7.7 Generalização85
7.8 API do Java87
7.9 Exercícios: Fila87
8.1 Motivação92
8.2 O problema do vocabulário94
8.3 Conjuntos95

8 Armazenamento sem repetição com busca rápida 92

9.1 Introdução96
9.2 Tabela de Espalhamento98
9.3 Função de Espalhamento100
9.4 Operações necessárias100

9 Tabelas de Espalhamento 96 i

9.6 Remover uma palavra101
9.7 Verificar se uma palavra está ou não no Conjunto101
9.8 Recuperar todas as palavras do Conjunto101
9.9 Informar o tamanho do Conjunto de palavras102
9.10 Exercícios: Tabela de Espalhamento 1102
9.1 Diminuindo Colisões105
9.12 Espalhando Melhor105
9.13 Exercícios: Tabela de Espalhamento 2106
9.14 Tabela Dinâmica107
9.15 Exercícios: Tabela de Espalhamento 3109
9.16 Generalização110
9.17 equals e hashCode112
9.18 Parametrizando o Conjunto113
9.19 API do Java115
9.20 Exercícios: Tabela de Espalhamento 4115
10.1 Motivação117
10.2 Mapa117
10.3 Exercícios: Armazenamento Associativo118

10 Armazenamento Associativo 117

1.1 Introdução120
1.2 Operações em mapas120
1.3 Adicionar uma associação120
1.4 Recuperar o valor associado a uma dada chave121
1.5 Remover a associação que contem uma determinada chave121
1.6 Verificar se uma dada chave está em alguma associação122
1.7 Informar o tamanho do Mapa122
1.8 Exercícios: Mapas122

1 Mapas com Lista 120 iv

12.1 Introdução125
12.2 Operações126
12.3 Verificando se uma chave existe126
12.4 Removendo uma associação dado uma chave126
12.5 Adicionando uma associação dado uma chave126
12.6 Recuperando o valor associado a uma determinada chave127
12.7 Performance das operações127
12.8 Generalização e Parametrização127
12.9 API do Java129

12 Mapas com Espalhamento 125 Versão: 9.7.19

CAPÍTULO 1

Prefácio

Este material foi escrito por Paulo Eduardo Azevedo Silveira e Rafael Antonio Cosentino para ser utilizado no curso de verão Introdução a Estrutura de dados e Algoritmos em Java, do Instituto de Matemática e Estatística da Universidade de São Paulo.

Paulo Silveira é bacharel e mestre em ciência da computação pelo Instituto de Matemática e Estatística da Universidade de São Paulo (IME-USP). É um dos fundadores do Grupo de Usuários Java (http://w.guj. com.br) e trabalha atualmente na Caelum (http://w.caelum.com.br).

Rafael Cosentino é bacharel em ciência da computação pelo Instituto de Matemática e Estatística da Universidade de São Paulo (IME-USP), é mestrando em Ciência da Computação também pelo IME-USP e trabalha atualmente na Caelum.

As experiências como alunos e professores mostrou aos autores desta apostila os principais pontos de dificuldades no aprendizado. Isso motivou uma abordagem um pouco diferente para esta apostila em relação ao que é comum na maioria dos livros sobre o assunto

A cada capítulo, apresentaremos diversos problemas que servirão de motivação para os principais conceitos de estrutura de dados. Os exercícios complementarão o apredizado pois ajudam a fixar os conceitos vistos na apostila e estimulam o aluno para conceitos avançados que fogem do escopo deste material.

Além disso, no fim de cada capítulo, apresentaremos as bibliotecas do Java que modelam as estruturas de dados apresentadas nesta apostila.

CAPÍTULO 2

Introdução

“As três coisas mais difíceis no mundo: guardar segredo, perdoar uma injúria e aproveitar o tempo” – Benjamin Franklin

2.1 - Introdução

Considere o problema de descobrir a altura da pessoa mais alta de um grupo de pessoas. Suponha que estas pessoas estão em seqüência, como em uma fila de banco, e que esta fila não está vazia.

Vamos elaborar uma estratégia para resolver este problema. Uma solução bem simples seria fazer o seguinte:

Fig.: Fila de pessoas

1) Pegue a altura da primeira pessoa. A única informação que você tem é que esta altura é a máxima até o momento. Então, “guarde” em algum lugar esta informação.

2) Percorra cada uma das próximas pessoas e faça o seguinte:

1) Pegue a altura da pessoa, esta é a altura atual.

2) Compare a altura atual com a máxima até o momento. Esta comparação pode resultar em três possibilidades: a altura atual é menor, é igual ou é maior.

3) Se a altura atual for maior, então faça o valor da altura máxima ser igual a atual.

Será que este procedimento é bom? Nesse caso temos de percorrer todas as pessoas da fila até ter certeza que encontramos a maior pessoa, pois a única invariante que temos, a cada passo do procedimento, é que até aquele momento todas as pessoas percorridas tem tamanho igual ou menor a um determinado número.

Material do Treinamento Algoritmos e Estruturas de Dados em Java

Existe solução melhor? E se tivessemos as pessoas organizadas de alguma maneira especial, chegariamos a solução em um menor tempo? E se houveram empates, quais outras pessoas são tão altas quanto essa nossa resposta?

Um algoritmo é uma seqüência de passos que resolve algum problema ou alcança algum objetivo, como a seqüência de passos para resolver o problema de descobrir a máxima altura. É importante salientar que um algoritmo simplesmente diz o que deve ser feito.

Para resolver de fato um problema, devemos definir como executar os passos do algoritmo. Por exemplo, para o problema anterior de achar a máxima altura, deveríamos definir como “pegar” as informações sobre as alturas da pessoas (perguntar para a própria pessoa, medir a altura usando uma fita métrica ou obter a altura de algum cadastro que a pessoa tenha feito) e como manter as informações sobre as alturas (anotar em um papel ou guardar em uma varíavel no computador).

A definicão de como os passos de um algoritmo serão executados é uma implementação do algoritmo. Resumindo, algoritmo é o que deve ser feito e implementação é o como deve ser feito.

Estamos interessados em desenvolver algoritmos computacionais. Para isso, utilizaremos um modelo de programação. Um modelo de programação fornece idéias e conceitos para nos ajudar a criar algoritmos. Neste curso, será utilizado o paradigma de programação orientado a obejetos (O).

Os nossos algoritmos serão executados por um computador. Então, devemos implementá-lo através de programas de computador. Um programa é a definição de como os passos de um algoritmo serão executados no computador.

Os programas são escritos em alguma linguagem de programação. Uma linguagem de programação é a maneira de “conversarmos” com um computador. A linguagem que utilizaremos aqui é a Java. Esta linguagem é voltador para o paradigma de programação orientado a objetos.

2.3 - Estrutura de Dados

Hoje em dia, a grande maioria das pessoas utilizam a agenda do celular para armazenar seus contatos. As tarefas de uma agenda de contatos são basicamente duas:

1) Definir como as informações dos contatos serão armazenadas. Uma informação armazenada em algum lugar (pedaço de papel, livro, computador, etc) é um dado.

2) Disponibilizar operações para criar, recuperar, ordernar, atualizar e remover contatos. Além de operações para informar o estado da agenda (a quantidade de contatos existentes na agenda ou a quantidade de espaço disponível para novos contatos).

A primeira tarefa é crucial para o desempenho. Se a agenda armazena as informações de uma forma desorganizada então será muito mais complicado manipular os dados de forma eficiente. A escolha de como guardar as informações deve levar em cosideração as operações que serão disponibilizadas pela agenda. Por exemplo, seria interessante manter os contatos em ordem alfabética para facilitar a busca.

Mas, apesar da importância de como os contatos são armazenados, a organização interna da agenda não precisa e não deve ser exposta ao usuário. Afinal de contas, o que o usuário deseja é usar a agenda através das operações e que tudo seja feito o mais rápido possível.

Capítulo 2 - Introdução - Algoritmo e Implementação - Página 3

Material do Treinamento Algoritmos e Estruturas de Dados em Java

A única coisa que precisa ser mostrada para o usuário são as operações que ele pode fazer na agenda (inserir, recuperar, atualizar, remover contato, saber quantos contatos estão na agenda, etc). Este conjunto de operações é a interface que o usuário tem com a agenda.

Cada celular pode implementar a sua agenda de contatos de uma forma totalmente diferente um do outro, na tentativa de obter mais performance, ser mais confiável ou gastar menos memória. Porém o conjunto básico de operações oferecidas pelas agendas é sempre o mesmo. Isso facilita a vida do usuário pois se ele tiver que trocar de celular não vai ter que aprender novamente como usar uma agenda de contatos.

Essa é a grande vantagem em se pensar em interface. Mantida a interface, podemos trocar uma agenda que não é tão eficiente ou que já não atende mais as nossas necessidades por outra mais eficiente ou adequada, sem problemas em ter de aprender a usar a nova agenda: troca-se a implementação, mas não mudamos a interface.

Uma agenda de celular pode ser vista como uma estrutura de dados. Uma estrutura de dados mantém os dados organizados seguindo alguma lógica e disponibiliza operações para o usuário manipular os dados.

(Parte 1 de 10)

Comentários