Programação Orientada a Objetos II
JAVA
Décima Aula
Prof. Rogério Albuquerque de 1
Almeida
Programação Orientada a Objeto II
Introdução à Estruturas de Dados
Alocação Dinâmica
Listas, pilhas e filas
Construção de classes
Listas, pilhas e filas
Prof. Rogério Albuquerque de Almeida
Estrutura de Dados
Foram vistas no semestre passado as formas mais
simples de estruturas de dados, descritas a seguir:
Listas
Pilhas
Filas
3
Prof. Rogério Albuquerque de Almeida
Estrutura de Dados
Estruturas de armazenamento
• Lista Seqüencial
• Lista encadeada
Exemplos de outras
estruturas
4
Prof. Rogério Albuquerque de Almeida
Lista encadeada
Uma lista encadeada consiste numa seqüência encadeada de elementos, em
geral chamados de nós da lista. A lista é representada por um ponteiro para o
primeiro elemento (ou nó). Do primeiro elemento, podemos alcançar o segundo
seguindo o encadeamento, e assim por diante. O último elemento da lista aponta
para NULL, sinalizando que não existe um próximo elemento.
Começaremos com um exemplo de uso de uma lista encadeada, demonstrando-a
com um applet. Essa abordagem dará a você uma idéia sobre o que faz este
tipo de estrutura.
[Link]
5
Prof. Rogério Albuquerque de Almeida
Lista encadeada
Principais Operações:
Inclusão de um elemento
Remoção de um elemento
Acesso a um elemento
Atualização de um valor
Exibir o conteúdo da lista
6
Prof. Rogério Albuquerque de Almeida
Lista encadeada
No slide seguinte é apresentado o
código fonte da implementação de um
programa que manipula uma lista
encadeada simples.
7
Prof. Rogério Albuquerque de Almeida
Lista encadeada - Estrutura de um nó
Pato 6
Nome Idade Prox
class No
{
public String nome;
public int idade;
public No prox;
// ----------------------------------------------------------
public No(String name, int id) // construtor
{
nome = name;
idade = id;
}
// ----------------------------------------------------------
public void mostraNo( )
{
[Link]("{" + nome + ", " + idade + "} ");
}
} // fim da classe No 8
Prof. Rogério Albuquerque de Almeida
Lista encadeada - Estrutura da Lista
class Lista
{
private No prim; // referência ao primeiro nó da lista
public Lista( ) { // construtor
prim = null; // nenhum nó na lista, ainda
}
public boolean vazia( ) { // true se a lista está vazia.
return (prim==null);
}
public void incluiPrim(String name, int id) {
No novoNo = new No(name, id);
[Link] = prim;
prim = novoNo;
}
public No deletePrim( ) {
No temp = prim;
prim = [Link];
return temp;
}
public void printLista( ) {
[Link]("Lista: ");
No aux = prim;
while(aux != null) {
[Link]();
aux = [Link];
}
[Link]("");
} 9
} //fim da classe Lista
Prof. Rogério Albuquerque de Almeida
Pilha
Permite acesso
apenas a um item
de dados: o último
item inserido.
Esta estrutura é também
conhecida como lista do tipo LIFO
(last in first out) o último nó que
entra é o primeiro que sai.
10
Prof. Rogério Albuquerque de Almeida
TOPO 98
85
56
Pilha 14
17
15
20
45
Principais Empilhar (Push)
Operações: Desempilhar (Pop)
98 85 56 15
11
Prof. Rogério Albuquerque de Almeida
Exemplos de código fonte
Baixe no link abaixo os códigos-fonte da
implementação de programa que
manipulam os tipos de estruturas mais
elementares, usando encadeamento.
[Link]
12
Prof. Rogério Albuquerque de Almeida
Fila
Permite acesso
apenas a um item
de dados: o último
item inserido.
Esta estrutura é também
conhecida como lista do tipo FIFO
(first in first out) o primeiro nó
que entra é o primeiro que sai.
13
Prof. Rogério Albuquerque de Almeida
Fila Início Fim
(Cabeça) (cauda)
(head) (tail)
Principais
Operações:
Incluir
Retirar
5 7 3 2 8 12
14
Prof. Rogério Albuquerque de Almeida
Fila
Baixe no link abaixo o código fonte da
implementação de um programa que
manipula uma fila usando encadeamento.
[Link]
15
Prof. Rogério Albuquerque de Almeida
