class

Transcrição

class

Estrutura de Dados com Orientação
a Objetos
Professor
Dr. Artur Henrique Kronbauer
Classes e Objetos
•
Programadores que utilizam POO criam e/ou usam objetos a partir de
classes, que são relacionadas diretamente com os modelos descritos.
•
Classes são estruturas utilizadas para descrever os modelos, ou seja, contém
a descrição das variáveis (atributos) e das rotinas (métodos) que podem ser
realizadas sobre eles.
•
Um objeto ou instância é a materialização da classe.
•
As variáveis contidos em uma classe são conhecidos
como campos ou atributos daquela classe.
Nome da Classe
Atributo 1
Atributo 2
Atributo 3
•••
Método 1
Método 2
•
Cada campo deve ter um nome e ser de um tipo
de dado nativo ou uma classe existente.
•
As rotinas contidas são os métodos.
•
Métodos podem receber argumentos (parâmetros).
•
O nome mais os parâmetros do método são chamados de assinatura.
•••
2
Classes e Objetos
•
Para que objetos ou instâncias possam ser manipulados, é necessária a
criação de referências a estes objetos, que são variáveis do “tipo” da classe.
•
Classe -> Planta do edifício, que descreve o edifício, mas não corresponde
fisicamente a ele.
•
Instância -> Edifício construído.
•
Referência -> Nome do Objeto (ilhaDoSol)
Classe
Edifício
instâncias
Edifício
ilhaDoSol
Edifício
palaci
Edifício
iguatemi
3
Classes e Objetos
•
•
Uma classe em Java será declarada com a palavra-chave class seguida do
nome da classe.
•
O nome não pode conter espaços.
•
Deve começar com uma letra.
•
Deve ser diferente das palavras reservadas.
•
Caracteres maiúsculos e minúsculos são diferenciados.
•
Conteúdo da classe limitado pelas chaves { }.
Exemplo:
class Empregado
Nome da classe
{ String Nome;
Atributo
public String getNome( )
{ return Nome;
}
Método
}
4
Campos declarados nas classes
•
Os campos das classes (atributos) devem ser declarados dentro do corpo da
classe.
•
Cada campo deve ser representado por um determinado tipo de dado.
•
Em linguagens OO, é possível declarar campos como referências a instâncias
de outras classes já existentes (Objetos).
•
Também é possível declarar campos de tipos primitivos da própria linguagem
(Variáveis).
•
A declaração é simples, basta declarar o tipo de dado, seguido dos nomes
dos campos que são daquele tipo.
•
Podemos observar que, para cada dado do modelo existe um campo
correspondente na classe.
•
Campos podem ser referências a uma classe.
5
Tipos Primitivos (Nativos da linguagem Java)
Tipo
byte
short
int
long
float
double
char
boolean
•
Faixa de Valores
-128 a 127
-32.768 a 32.767
-2.147.483.648 até 2.147.483.647
-9.223.372.036.854.775.808 a
9.223.372.036.854.775.807
1.401298464324811707e-45 a
3.40282346638528860e+38
4.94065645841246544e-324 a
1.79769313486231570e+308
Representam um único caracter
True ou False
Armazenamento
Inteiro de 8 bits
Inteiro de 16 bits
Inteiro de 32 bits
Inteiro de 64 bits
Ponto Flutuante de 32 bits
8 bytes ou 64 bits
16 bits
1 bit
A classe String é usada para representar cadeias de caracteres. (Não são
dados nativos, sendo instâncias da classe String)
6
Operadores da Linguagem Java
•






•
Operadores Aritméticos
+ (soma)
- (subtração)
* (multiplicação)
/ (divisão)
% (resto de uma divisão inteira)
int(A) / int(B) (parte inteira de uma divisão)
Operação com instâncias da classe String.

•
+ (concatenação)
•
•
Operadores Relacionais
 < (menor)
 > (maior)
 <= (menor ou igual)
 >= (maior ou igual)
 == (igual)
 != (diferente)
Operadores Lógicos
 && (and)
 II (or)
 ! (não lógico)
Operadores relacionais para a classe String
 equals
if (nome.equals(“Maria”)
 !equals
if (!nome.equals(“Maria”)
7
Composição de uma programação Orientada a Objetos
•
Programas orientados a objetos, são compostos por:
• conjuntos de objetos que representam os objetos existentes no negócio
modelado.
• conjuntos de objetos que representam estruturas adequadas para a
manipulação de dados.
• Os objetos que compõem o programa comunicam-se por trocas de
mensagens.
• O programa precisa ter um ponto de entrada que indique à máquina virtual
onde iniciar a execução.
public class Aplicacao
{ public static void main(String[] s)
{
}
}
8
Composição de uma programação Orientada a Objetos
•
public static void main(String[] args)
• public: é visível para qualquer outra classe.
• static: dispensa a criação de objetos.
• void: nenhum retorno esperado.
• main: convenção para indicar a máquina virtual qual o ponto de entrada da
aplicação.
• String[] args: parâmetros passados pela aplicação via linha de comando.
args é o identificador.
9
Saída de Dados Padrão
•
Representada por um atributo estático da classe System
System.out.println(...)
•
Tipos primitivos podem ser concatenados a Strings através do operador +
•
Exemplo:
class saidaDados
{ public static void main (String args[])
{ System.out.println(“saida de dados”);
}
}
10
Entrada de Dados Padrão
•
Toda a classe que for se utilizar de entrada de dados via teclado deve utilizar
o package Java.io.*. Esse pacote contêm as classes que tratam de entrada
de dados.
import java.io.*
•
Para obter valores do teclado em uma classe Java é necessário criar um
objeto da classe Scanner. A classe Scanner pertence ao pacote java.util.
Então é necessário colocar o import java.util.*;
Scanner leitor = new Scanner(System.in);
•
Todo a entrada de dados está sujeita a erros, já que fica a mercê da digitação
do usuário final. A forma mais simples de se tratar essa exceção é solicitar
que a exceção não seja tratada localmente através da linha de comando:
throws java.io.IOException
11
Realizando a Leitura pelo Teclado
•
Para realizar a leitura via teclado usaremos a classe Scanner. Instanciando o
objeto leitor da classe Scanner usando a entrada padrão do Sistema.
Scanner leitor = new Scanner(System.in);

Lendo um número inteiro
int i = leitor.nextInt();

Lendo um número float
int i = leitor.nextFloat();

Lendo uma String
int i = leitor.next();
12
Conversão de String para tipos primitivos
•
O Java só permite a entrada de Strings, desta forma, para que possamos
informar valores numéricos é necessário fazer uma conversão de String para
o tipo numérico desejado, como podemos ver a seguir:
A variável str é uma String.

Conversão de String para inteiro
int i = Integer.valueOf(str).intValue();

Conversão de String para long
long l = Long.valueOf(str).longValue();

Conversão de String para float
float f = Float.valueOf(str).floatValue();

Conversão de String para double
double d = Double.valueOf(str).doubleValue();
13
Exemplo de Entrada e Saída de Dados
import java.io.*;
class Soma
{ public static void main (String args[ ] ) throws java.io.IOException
{ String aux;
int a, b;
BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Digite o primeiro número: ");
aux = obj.readLine();
a = Integer.valueOf(aux).intValue();
System.out.println("Digite o segundo número: ");
aux = obj.readLine();
b = Integer.valueOf(aux).intValue();
a = a + b;
System.out.println("O resultado é : " + a);
}
}
14
Conversões entre tipos numéricos
•
Conversão entre Tipos Numéricos: Sempre que for realizada uma
operação numérica (+, -, *, /) entre dois tipos diferentes será considerado
como se os operadores fossem do mesmo tipo. Para isso, o operador de
maior capacidade dita o tipo a ser considerado.
Menor
Maior
byte  short  int  long  float  double
•
Conversões Explicitas: Para fazer conversões que não seguem a regra
anterior é necessário realizar conversões explicitar, veja o exemplo:
double x = 9.997;
int nx = (int) x;
Sintaxe para uma
conversão Explicita
Resultado após a conversão  nx = 9
15
Comandos de Decisão (if-else)

•
if – else
if (expressão_booleana )
{ bloco de comandos do if;
}
[else]
{ bloco de comandos do else;
}
Observações:

O comando else é opcional.

Na construção de if’s aninhados, o else refere-se sempre ao if mais
próximo. Procure usar chaves para delimitar os blocos.

O operador de comparação igual a é representado por == e não por =.

Bloco de comandos pode ser um único comando (terminado por ponto-evírgula) ou vários comandos (delimitados por {}).

É indispensável o uso de parênteses ( ) na expressão_booleana.
16
Comandos de Decisão (switch)

switch
switch(variávelDeControle)
{ case constante1:
bloco1;
break;
case constante2:
bloco2;
break;
[default:
bloco3;
break;]
}
•
Observações:
 Usual para selecionar alguma ação de um número de alternativas.
 A variável de controle só pode ser inteira ou char.
 O case define o ponto de entrada da execução. Se você quiser que só um
bloco de declarações seja executado use break.
17
 A opção default é opcional.
Comandos de Repetição (while)

while
while (expressão_booleana)
{ Bloco de comandos;
}
•
Observações:
 É indispensável o uso de parênteses ( ) na expressão booleana.
 O laço permanece em execução enquanto a expressão booleana for
verdadeira.
 Um erro comum é não atualizar as variáveis de controle do laço, o que
acarreta um loop infinito.
 Outro erro frequente é colocar o ponto e vírgula após o while. A fase de
atualização das variáveis de controle ficam fora do laço, gerando um loop
infinito.
 Use sempre chaves para delimitar o Bloco de comandos.
18
Comandos de Repetição (do while)

do - while
do
{
Bloco de comandos;
} while (expressão_booleana);
•
Observações:
 É semelhante ao comando while, sendo que a condição de parada do laço é
testada após o bloco de comandos.
 Pelo menos uma vez o bloco de comandos será executado.
 Observe as mesmas considerações do comando while.
19
Comandos de Repetição (for)

for
for(inicialiazação; terminação; iteração)
{ bloco de comandos;
}
•
Observações:

Num loop for é explicita as quatro partes de uma iteração.

Um erro comum é colocar o ponto e vírgula após o for, ficando o bloco de
comandos fora do laço. O resultado é um loop que nada realiza.
20
Exemplo de uma classe com estruturas condicionais
class DataSimples
{
byte dia,mes;
short ano;
Tipos primitivos definidos
como atributos (variáveis)
DataSimples(byte dia,byte mes,short aano)
{ if (dataEValida(dia,mes,ano) == true)
{ this.dia = dia; this.mes=mes; this.ano=ano;
}
else
{ this.dia = 0; this.mes=0; this.ano=0;
}
Método
}
da classe
Construtor
da classe
Parâmetros
baseados em
tipos primitivos
boolean dataEValida(byte dia,byte mes,short ano)
{ if ((dia>=1) && (dia<=31) && (mes>=1) && (mes<=12))
return true;
else
return false;
}
21
Exemplo de uma classe com estruturas condicionais
boolean eIgual(DataSimples outraDataSimples)
{ if ((dia == outraDataSimples.dia) &&
( mes == outraDataSimples.mes) &&
(ano == outraDataSimples.ano))
return true;
else
return false;
Método
}
da classe
Parâmetros
baseados em
um objeto da
própria classe
void mostraDataSimples()
{ System.out.println(dia + “/” + mês + “/” + ano);
}
}
22
Exemplo de uma classe com estruturas de repetição
public class exemploCondicaoRepeticao
{ public static void main (String args[])
{ double valor = 1;
char letra='A';
int contador;
while(valor <= 20)
{ System.out.println(valor);
valor = valor * 2;
if (valor >= 20)
{ System.out.println("Fim da exemplificação do while e if");
}
}
for (contador=0; contador < 10; contador++)
{
System.out.println(contador);
}
System.out.println("Fim da exemplificação do for");
23
Exemplo de uma classe com estruturas de repetição
do
{ switch (letra)
{ case 'A' : System.out.println(letra + " é uma vogal");
break;
case 'E' : System.out.println(letra + " é uma vogal");
break;
case 'I' : System.out.println(letra + " é uma vogal");
break;
case 'O' : System.out.println(letra + " é uma vogal");
break;
case 'U' : System.out.println(letra + " é uma vogal");
break;
}
letra++;
} while (letra != 'Z');
System.out.println("Fim da exemplificação do switch e do-while");
}
}
24
Escopo de Variáveis e Objetos
•
O escopo dos campos e variáveis dentro de uma classe determina a sua
visibilidade.
•
Campos declarados em uma classe são válidos por toda a classe, mesmo que
os campos estejam declarados depois dos métodos que os usam.
•
Variáveis e instâncias de objetos declarados dentro de métodos só serão válidos
dentro desse método.
•
Dentro de métodos e blocos de comandos, as variáveis e objetos devem ser
declarados antes de serem utilizadas.
•
Variáveis passadas como argumentos para métodos só são válidas dentro dos
métodos.
•
Exemplo: Veja o exemplo da classe Data.
25
Modificadores de Acesso
•
Modificadores de acesso podem ser usados tanto em campos como em
métodos de uma classe.
•
O objetivo é proteger a integridade e a consistência dos dados e operações que
uma determinada classe manipula.
Exemplo de Proteção aos Atributos (dados)
•
Por exemplo na classe dataSimples analisada anteriormente, observamos que
ao ser inicializada uma data, os campos dia, mês e ano passam por um
processo de consistência, ao ser chamado o método dataEValida.
•
Entretanto, como não são usados modificadores, não podemos garantir que
sempre as datas serão validadas, pois os campos da classe podem ser
acessados diretamente, sem a utilização dos métodos da classe.
26
Exemplo de Proteção aos Métodos (ações)
•
Outro exemplo, seria um método imprimeNumeroDaPagina de uma classe
Relatório.
•
Esta classe teria o método imprimeRelatorio que sempre que necessário se
utilizaria do método imprimeNumeroDaPágina.
•
Seria inadequado a execução de imprimeNumeroDaPagina desatrelado do
método imprimeRelatorio.
•
No primeiro exemplo apresentado, seria conveniente usar um modificador para
proteger os dados, assim garantindo que as datas sempre seriam validados.
•
No segundo exemplo, seria conveniente usar um modificador para restringir o
acesso ao método imprimeNumeroDaPagina, já que este só deve ser usado
através do método imprimeRelatorio.
27
Existem quatro modificadores de acesso
•
public: garante que o campo ou método da classe declarado com este
modificador poderá ser acessados ou executado a partir de qualquer outra
classe.
•
private: só podem ser acessados, modificados ou executados por métodos da
mesma classe, sendo ocultos para o programador usuário que for usar
instâncias desta classe ou criar classes herdeiras ou derivadas.
•
protected: funciona como o modificador private, exceto que classes herdeiras
ou derivadas também terão acesso ao campo ou método.
•
Finalmente, campos e métodos podem ser declarados sem modificadores.
Nesse caso, eles serão considerados como pertencentes à categoria package,
significando que seus campos e métodos serão visíveis para todas as classes
de um mesmo pacote.
28
Exemplo de Escopo e Modificadores
public determina que essa classe pode ser instanciada dentro de qualquer outra
classe.
public class Data
{
private byte dia, mes;
private short ano;
private determina que os dados só podem ser
manipulados dentro da própria classe. Como “dia”,
“mês” e “ano” são declarados fora dos métodos,
são variáveis globais (atributos).
public void inicializaData(byte dia,byte mes, short ano)
{
public
indica
que
o
método
pode ser
acessado
sem
restrições
if (dataEValida(dia,mes,ano) == true)
{ this. dia = dia; this.mes=mes; this.ano=ano;
}
else
{ this.dia = 0; this.mes=0; this.ano=0;
As variáveis “dia”, “mes”
e “ano” são parâmetros
(argumentos)
e
só
podem ser manipulados
dentro desse método.
}
}
29
Exemplo de Escopo e Modificadores
private indica que esse método só pode ser acessado através de outros
métodos da própria classe.
private boolean dataEValida(byte dia,byte mes,short ano)
A variáveis “validade”
é uma variável local e
só
podem
ser
manipulada
dentro
desse método.
{ boolean validade = false;
if ((dia>=1) && (dia<=31) && (mes>=1) && (mes<=12))
validade = true;
return validade;
}
protected indica que esse método só pode ser acessado através de métodos
dessa classe ou de classes herdeiras ou derivadas.
protected void mostraData()
{
}
}
System.out.println(dia + “/” + mes + “/” + ano);
30
Garbage Collection
•
Garbage Collection
 Gerenciador de memória para aplicações java.
 Thread chamada Automatic Garbage Collector.
 Retorna a memória ocupada por objetos que não estão mais sendo usados.
 Monitora a criação de objetos através do new.
 Cria um contador de referência para cada objeto.
 Libera a memória quando o contador chegar a zero.
•
Referência NULA
 Objetos armazenam uma referência nula até serem inicializados.
 A referência nula é representada pela palavra reservada null.
 Pode-se desfazer uma referência para um objeto atribuindo a ela a 31
palavra
null.
Operador New
•
Operador NEW
 new instancia um novo objeto.
 new aloca o espaço necessário para armazenar o estado do objeto e uma
tabela para indicar o corpo do código necessário para efetuar suas
operações.
 new executa as tarefas de inicialização do objeto conforme o seu
Construtor.
 new ‘retorna’ o identificador do objeto criado e o operador de atribuição é
utilizado para copiar este endereço para uma variável, que servirá para
futuras referências ao objeto.
 O compilador e a máquina virtual Java verificam o tipo da variável e o tipo da
referência retornada.
32
Construtores
•
Construtor é um tipo especial de membro de classe chamado automaticamente
quando instâncias são criadas através da palavra chave new.
•
Construtores são úteis para:
 inicializar os atributos de uma classe;
 realizar rotinas complexas de inicialização;
 realizar inicializações segundo parâmetros passados no momento da
criação do objeto.
•
Na declaração de um construtor deve-se considerar que:
 Construtores devem ter exatamente o mesmo nome da classe;
 Construtores não possuem tipo de retorno, nem mesmo void;
 Construtores são, normalmente, públicos.
 Programador não pode chamar construtores diretamente;
•
Toda classe possui um construtor.
•
Caso o programador não forneça uma versão explícita do construtor, o Java
utiliza uma versão de construtor implícita que não recebe nenhum parâmetro.
33
Exemplo da Utilização de Construtores
public class Empregado
{ String nome, endereço, CPF;
float salario;
int idade;
public Empregado ( String nome, String endereco, String CPF, int idade)
{ this.nome = nome;
this.endereco = endereco;
Construtor da classe Empregado.
this.CPF = CPF;
Observe que não foi definido um
this.idade = idade;
tipo de retorno e possui o mesmo
nome da classe.
}
public String getCPF( )
{ return CPF;
}
public String getNome( )
{ return Nome;
}
}
34
Exemplo da Utilização de Construtores
Utilização do Construtor da
classe
Empregado
para
instanciar um objeto.
class CriaEmpregado
{ public static void main(String args[])
{
Empregado obj = new Empregado(“Maria Silva”, “Rua X nº
246", "403.234.567-33",58);
Nome da classe
Nome do Objeto
System.out.println("O nome é = ” +obj.getNome());
System.out.println("O CPF é = "+ obj.getCPF());
}
}
35
Reutilização de Classes
•
Um dos maior benefício que a Programação Orientada a Objeto nos proporciona
é a reutilização de código.
•
A reutilização se caracteriza pelo aproveitamento de classes e seus métodos
que já estejam escritos e que já tenham o seu funcionamento testado e
comprovado.
•
A Reutilização de código diminui a necessidade de escrever novos métodos e
classes gerando economia de tempo e segurança.
•
Existe duas maneiras de conseguir esse reaproveitamento: Através de
Composição ou através de Herança.
36
Composição
•
A composição é o conceito mais usual no desenvolvimento de aplicações
baseadas em Orientação a Objetos.
•
Parte do pressuposto que uma determinada classe vai instanciar objetos de
outras classes, utilizando-se do que esses objetos fazem para compor as
funcionalidades da nova classe.
•
Esse conceito pode ser visto em exemplos anteriores (classe criaEmpregado),
que instanciaram objetos da classe Empregado.
CriaEmpregado
Empregado
37
Herança
•
Herança é a capacidade de uma classe definir o seu comportamento e sua
estrutura aproveitando definições de outra classe, normalmente conhecida como
classe base ou classe pai.
•
A herança não precisa ser interrompida na derivação de uma camada de
classes. A coleção de todas as classes que se estendem de um pai comum
chama-se hierarquia de herança.
•
A palavra reservada extends é que define que uma classe está herdando de
outra.
Empregado
Gerente
Secretária
Analista de Sistemas
38
Herança
•
Através do mecanismo de herança é possível definirmos classes genéricas que
agreguem um conjunto de definições comuns a um grande número de objetos
(Generalização). A partir destas especificações genéricas podemos construir
novas classes, mais específicas, que acrescentem novas características e
comportamentos aos já existentes (Especialização).
Funcionário
Gerente
Gerente de
Banco
Gerente de
Empresas
• codBanco
• codAgência
• codSetor
• nome
• salário
Secretária
Analista de Sistemas
• idiomas
• linguagem
39
Herança e a Referência super
•
A palavra reservada super, nos possibilita:

referência a classe base (pai) do objeto;

acesso a variáveis escondidas (shadow), ou seja, variáveis de uma classe
que tem o mesmo nome de uma variável definida em uma subclasse;

acesso a métodos que foram redefinidos, ou seja, métodos que possuem a
mesma assinatura na classe Pai e na classe derivada;

utilização pela classe derivada do construtor da classe pai.
40
Exemplo de Herança
public class Automovel
Classe Pai
{ public static final byte movidoAGasolina = 1;
Declaração de
constantes.
public static final byte movidoAAlcool = 2;
public static final byte movidoADiesel = 3;
private static final byte numeroMaximoDePrestacoes = 24;
Atributos
private String modelo, cor;
private byte combustivel;
Construtor
public Automovel(String m, String c, byte comb)
{ modelo = m;
cor = c;
combustivel = comb;
}
public byte quantasPrestacoes()
{ return numeroMaximoDePrestacoes;
}
41
Exemplo de Herança
public float quantoCusta()
{ float preco = 0;
switch (combustivel)
{ case movidoAGasolina: preco = 12000.0f;
break;
case movidoAAlcool: preco = 10500.0f;
break;
case movidoADiesel: preco = 11000.0f;
break;
}
return preco;
}
public String toString()
{ String resultado;
resultado = modelo+" "+cor+"\n";
switch(combustivel)
{ case movidoAGasolina: resultado += "Gasolina \n"; break;
case movidoAAlcool: resultado += "Álcool \n";
break;
case movidoADiesel: resultado += "Diesel \n";
break;
}
return resultado;
}
42
Exemplo de Herança
public class AutomovelBasico extends Automovel
{ private boolean retrovisorDoLadoDoPassageiro;
private boolean limpadorDoVidroTraseiro;
private boolean radioAMFM;
Atributos
A palavra extends é
que determina que
AutomovelBasico
herda de Automovel.
public AutomovelBasico (String m, String c, byte comb, boolean r,
boolean l, boolean af)
{ super(m,c,comb);
A palavra super, indica
retrovisorDoLadoDoPassageiro = r;
que deve ser usado o
limpadorDoVidroTraseiro = l;
construtor da classe Pai.
radioAMFM = af;
}
public AutomovelBasico (String m, String c, byte comb)
{ super(m,c,comb);
retrovisorDoLadoDoPassageiro = true;
limpadorDoVidroTraseiro = true;
radioAMFM = true;
}
43
Exemplo de Herança
public float quantoCusta()
Os
dois
métodos
{ float preco = super.quantoCusta();
apresentados
nesse
slide
if (retrovisorDoLadoDoPassageiro == true)
possuem a mesma assinatura
preco = preco + 280;
da classe Automovel, o que
if (limpadorDoVidroTraseiro == true)
caracteriza uma redefinição de
métodos da classe Pai.
if (radioAMFM == true)
return preco;
A palavra super, indica que
}
deve ser chamado o método
quantoCusta() e toString() da
public String toString()
classe Pai.
{ String resultado = super.toString();
if (retrovisorDoLadoDoPassageiro == true)
resultado += "Com retrovisor do lado direito \n";
if (limpadorDoVidroTraseiro == true)
resultado += "Com limpador traseiro \n";
if (radioAMFM == true)
resultado += "Com radio \n";
return resultado;
}
44
}
Exemplo de Herança
public class DemoAutomovel
Instância de um objeto
da classe Automovel.
{ public static void main(String arg[])
{ Automovel a = new Automovel("Fusca","verde", Automovel.movidoAAlcool);
System.out.println(a.toString());
System.out.println(a.quantoCusta());
System.out.println(a.quantasPrestacoes());
Instância de um objeto da
classe AutomovelBasico.
AutomovelBasico ab = new AutomovelBasico("Corsa","cinza",
Automovel.movidoAGasolina,true,true,false);
System.out.println(ab.toString());
System.out.println(ab.quantoCusta());
System.out.println(ab.quantasPrestacoes());
}
}
Observe que o método quantasPrestacoes() está sendo acessado através de
um objeto da classe AutomovelBasico. Isso só é possível porque a classe
AutomovelBasico herda da classe Automovel, assim todos os atributos
e
45
métodos da classe Pai podem ser usados pela classe derivada.
Principais componentes gráficos usados no curso
•
jLabel: São utilizados para identificar ações sobre outros componentes em
uma interface.
 Principal método: setVisible(Boolean);
 Exemplo: jLabel1.setVisible(false);
•
jTextField: São usados para possibilitar que o usuário digite informações
para a aplicação.
 Principais métodos: getText();
setText(String)
 Exemplo: jTextField1.getText();
jTextField1.setText(“”);
•
jButton: São usados para permitir o início da execução de alguma tarefa pelo
aplicativo.
 Principal método: setLabel(String);
 Exemplo: jButton.setLabel(“Entrar”);
•
list: São usados para permitir que dados sejam mostrados na tela em forma
de relatório.
 Principal método: add(String);
46
 Exemplo: list1.add(“”+numero);
Principais componentes gráficos usados no curso
•
JOptionPane.showMessageDialog: Este componente permite apresentar
mensagens para o usuário.
 A classe deve importar a seguinte biblioteca:
import javax.swing.JOptionPane;
• A sintaxe para o uso do comando é:
JOptionPane.showMessageDialog(null,“Mensagem");
•
A plataforma utilizada é a JDK 7u51 with NetBeans 7.4
•
Link para a plataforma:
http://www.oracle.com/technetwork/java/javase/downloads/jdk-7netbeans-download-432126.html
•
Baixar a opção: jdk-7u51-nb-7_4-windows-x64.exe
47
Tratamento de Exceções
•
•
•
•
Exceções são eventos estranhos, que podem fazer um programa falhar. Por
exemplo, quando se espera que um usuário entre com um número e este
digita uma letra.
As exceções na linguagem Java são objetos reais, instâncias de classe que
herdam da classe Throwable. Um objeto da classe Throwable é criada,
quando uma exceção é gerada.
A linguagem Java permite que se tratem exceções através das palavras try,
catch e finally.
– try : no bloco try você protege o código que poderia gerar uma exceção.
– catch : no bloco catch você testa e trata da exceção gerada.
– finally : no bloco finally você possibilita que seu programa execute linhas
de código tendo ou não ocorrido exceções.
Existem vários tipos de exceções na linguagem Java. Para que você possa
tratá-las adequadamente é necessário descobrir quais são as exceções que
podem ser geradas (levantadas) por um determinado método.
– Algumas exceções da linguagem Java
• IOException
• EOFException • FileNotFoundException
• MalformedURLException
• SocketException
48
public class Principal extends javax.swing.JFrame
{
public Principal() {
initComponents();
}
private void initComponents()
{
// Este método é definido pelo NetBeans e não pode ser alterado
}
49
// Aqui está a lógica da Aplicação
private void jButton1MouseClicked(java.awt.event.MouseEvent evt)
{
int n;
try
{ n = Integer.valueOf(jTextField1.getText()).intValue();
}
catch (Exception obj)
{ JOptionPane.showMessageDialog(null,"Você deve digitar apenas números inteiros!");
return;
}
finally
{ jTextField1.setText("");
}
list1.add(""+n);
}
50
public static void main(String args[])
{
// Este método é definido pelo NetBeans e não deve ser alterado
java.awt.EventQueue.invokeLater(new Runnable()
{
public void run()
{
new Principal().setVisible(true);
}
});
}
// Estes atributos são criados pelo NetBeans e não devem ser alterados
private javax.swing.JButton jButton1;
private javax.swing.JLabel jLabel1;
private javax.swing.JTextField jTextField1;
private java.awt.List list1;
}
51
Estrutura Estática - Array (Vetor)
•
Conjunto finito e ordenado de elementos homogêneos.
•
Declaração utilizando tipos primitivos
int[] Vet;
Vet = new int[12];
•
ou
int[] Vet = new int[12]
Declaração utilizando tipos não primitivos (array de uma classe qualquer)
Button[] Botoes;
Botoes = new Button[10]
ou
Button[] Botoes = new Button[10]
52
Estrutura Estática - Utilização de Array
public class Array extends javax.swing.JFrame
{
int vet[];
int total=0;
public Array()
{
vet = new int[100];
total=0;
initComponents();
}
public void ordenar()
{ int i,j, aux;
for(i=0; i < total; i++)
{
for(j=i+1; j < total; j++)
{
if (vet[i] > vet[j])
{
aux = vet[i];
vet[i]=vet[j];
vet[j]=aux;
}
}
}
}
53
{ try
{ vet[total]=Integer.valueOf(jTextField1.getText()).intValue();
list1.add(jTextField1.getText());
total++;
jTextField1.setText("");
}
catch (Exception e)
{ JOptionPane.showMessageDialog(null,“Digite apenas números inteiros!");
return;
}
}
{ ordenar();
for(int i=0; i<total; i++)
{ list2.add(vet[i]+"");
}
}
54
public static void main(String args[]) {
// Este método é definido pelo NetBeans e não deve ser alterado
java.awt.EventQueue.invokeLater(new Runnable() {
public void run() {
new Array().setVisible(true);
}
});
}
// Estes atributos são criados pelo NetBeans e não devem ser alterados
55
}
Estrutura Dinâmica - Lista Encadeada
•
É uma sequência de estruturas (elementos) interligados, com a capacidade de
inserção e remoção em qualquer posição da lista.
•
A cabeça da lista contém um ponteiro para o primeiro elemento da lista (nodo),
que armazena um conjunto de dados e um ponteiro para o nodo seguinte.
Esse nodo, da mesma forma, armazena um item de dados e um ponteiro para
o nodo seguinte, e assim por diante. O último nodo possui um ponteiro null
para indicar o final da lista.
•
Representação Estrutural
Cabeça da Lista
Ponteiro para
o primeiro nodo
•
nodo
Dados
Próximo
nodo
Dados
Próximo
nodo
nodo
Dados
Próximo
Dados
Próximo
null
O critério utilizado em listas determina que as inserções e remoções podem
ser realizadas em qualquer posição da lista. Por conveniência utilizaremos a
inserção por ordem de chave (informação única que destingue um elemento
56
de outro).
Estrutura Dinâmica – Classe Nodo
public class Nodo
{ int info;
Nodo prox;
public Nodo(int n)
{
info = n;
prox = null;
}
}
57
Estrutura Dinâmica - Lista Simplesmente Encadeada
public class ListaSimplesmenteEncadeada
{
Nodo inicio = null, fim = null;
int qtd = 0;
public Nodo pesquisa(int n)
{ Nodo atual = inicio;
while ((atual != null) && (atual.info != n))
{ atual = atual.prox;
}
return atual;
}
58
public boolean insere(int n)
{ Nodo novo = new Nodo(n);
qtd++;
if (inicio == null) // ins. no início da lista
{ fim = novo;
inicio = novo;
return true;
}
if (n < inicio.info)
// antes do 1º
{ novo.prox=inicio;
inicio = novo;
return true;
}
if (n > fim.info)
// no final
{ fim.prox = novo;
fim = novo;
return true;
}
// pesquisa elemento
Nodo atual=inicio;
Nodo aux = inicio;
while (atual.info < n)
{ aux = atual;
atual=atual.prox;
}
if (atual.info == n)
{ qtd--;
return false;
}
// info. existente
else
// inserção no meio
{ novo.prox = atual;
aux.prox = novo;
}
return true;
}
59
public boolean remove(int n)
else
{ Nodo aux = inicio;
{ // remoção no final
Nodo atual=inicio;
if (atual == fim)
if (n == inicio.info)
// remoção do início
{ fim=aux;
{ inicio=inicio.prox;
fim.prox=null;
}
if (atual == fim)
// remoção do único
else // remoção no meio
{ fim=null;
{ aux.prox = atual.prox;
}
}
qtd--;
qtd--;
return true;
return true;
}
}
}
else
}
{ while ((atual != null) && (atual.info != n))
{ aux=atual;
atual=atual.prox;
}
if (atual == null) // elemento não encontrado
60
{ return false;
}
Exemplo de Aplicação de Lista Encadeada
public class AplicacaoListaSimplesmenteEncadeada extends javax.swing.Jframe
{
ListaSimplesmenteEncadeada objLista;
public AplicacaoListaSimplesmenteEncadeada()
{
objLista = new ListaSimplesmenteEncadeada();
initComponents();
}
61
// Ações do botão Inserir
{ int n;
try
}
catch (Exception e)
return;
}
if (objLista.insere(n) == true)
{ list1.removeAll();
mostraLista(objLista);
}
else
{ JOptionPane.showMessageDialog(null,"Elemento Existente!");
}
62
}
// Ações do botão Remover
{
int n;
try
if (objLista.remove(n) == true)
{ JOptionPane.showMessageDialog(null,"Elemento removido com sucesso!");
list1.removeAll();
mostraLista(objLista);
}
else
{ JOptionPane.showMessageDialog(null,"Elemento não encontrado!");
}
}
catch (Exception e)
}
63
}
// Ações do botão Consultar
{
int n;
try
if (objLista.pesquisa(n) != null)
{ JOptionPane.showMessageDialog(null,"Elemento Encontrado na Lista!");
}
else
{ JOptionPane.showMessageDialog(null,"Elemento Não Encontrado na Lista!");
}
}
catch (Exception e)
}
64
}
{
public void run() {
new AplicacaoListaSimplesmenteEncadeada().setVisible(true);
} });
}
void mostraLista(ListaSimplesmenteEncadeada objLista)
{ Nodo aux = objLista.inicio;
while (aux != null)
{ list1.add(aux.info+"");
aux=aux.prox;
}
}
}
65
Estrutura Dinâmica - Lista Duplamente Encadeada
•
Em algumas aplicações que utilizam listas encadeadas pode ser de extrema
necessidade percorre-la da esquerda para a direita, bem como da direita para
a esquerda. Este tipo de estrutura é chamada de Lista Duplamente
Encadeada.
•
A cabeça da lista contém dois ponteiros, um para o primeiro elemento da lista
e outro para o último elemento da lista. Os nodos devem ter dois ponteiros, um
para o próximo nodo e um para o nodo anterior.
•
Representação Estrutural
Cabeça de Lista
Ponteiro para
o primeiro nodo
Ponteiro para o
último nodo
null
nodo
nodo
nodo
nodo
Dados
Próximo
Anterior
Dados
Próximo
Anterior
Dados
Próximo
Anterior
Dados
Próximo
Anterior
null
66
Estrutura Dinâmica – Classe NodoDupEnc
public class NodoDupEnc {
int info;
NodoDupEnc prox;
NodoDupEnc ant;
NodoDupEnc(int n)
{ info = n;
prox = null;
ant = null;
}
}
67
public class ListaDuplamenteEncadeada
{ NodoDupEnc inicio=null, fim=null;
int qtd=0;
public NodoDupEnc pesquisaDirEsq(int n)
{ NodoDupEnc atual = fim;
{
atual = atual.ant;
}
return atual;
}
public NodoDupEnc pesquisaEsqDir(int n)
{ NodoDupEnc atual = inicio;
{
atual = atual.prox;
}
return atual;
}
68
{ NodoDupEnc novo = new
NodoDupEnc(n);
qtd++;
if (n > fim.info) // no final
{ novo.ant = fim;
fim.prox = novo;
fim = novo;
return true;
}
if (inicio == null) // no início da lista
{
fim = novo;
inicio = novo;
return true;
}
// pesquisa o local de inserção
NodoDupEnc atual = inicio;
while ((atual != null) && (atual.info < n))
{
atual = atual.prox;
}
if (atual.info == n) // informação já existe
return false;
else // no meio
{ novo.prox = atual;
novo.ant = atual.ant;
atual.ant.prox = novo;
atual.ant = novo;
}
69
return true;
if (n < inicio.info)
// antes do 1º
{ novo.prox=inicio;
inicio.ant=novo;
inicio = novo;
return true;
}
}
public boolean remove(int n)
{ NodoDupEnc atual = pesquisaDirEsq(n);
if (atual == null) // elemento não encontrado
{ return false;
}
qtd--;
if (atual == inicio) // rem do 1º da lista
{ inicio=atual.prox;
if (atual == fim) // rem. do único
{ fim=null;
}
else
// atualiza o novo início
{ inicio.ant=null;
}
}
return true;
}
if (atual == fim) // rem. do último
{
fim=fim.ant;
fim.prox=null;
return true;
}
// rem. no meio da lista
NodoDupEnc anterior=atual.ant;
NodoDupEnc posterior=atual.prox;
anterior.prox=posterior;
posterior.ant=anterior;
return true;
70
Estrutura Dinâmica - Listas Circulares
•
Em algumas aplicações que utilizam listas encadeadas pode ser de extrema
necessidade que o último nodo aponte para o primeiro. Este tipo de estrutura
é chamada de Lista Circular.
•
Representação Estrutural da lista Circular
Cabeça da Lista
Ponteiro para
o primeiro nodo
•
nodo
Dados
Próximo
Dados
Próximo
nodo
nodo
Dados
Próximo
Dados
Próximo
Representação Estrutural da lista Circular Duplamente Encadeada
Cabeça de Lista
Ponteiro para
o primeiro nodo
Ponteiro para o
último nodo
•
nodo
nodo
nodo
nodo
nodo
Dados
Próximo
Anterior
Dados
Próximo
Anterior
Dados
Próximo
Anterior
Dados
Próximo
Anterior
Exercício: Implemente as duas Representações Estruturais.
71
Fila
FIFO - Fist-In, First-Out (O 1º a Entrar é o 1º a Sair)
Início
Final
A
Início
B
Início
C
(a)
B
insere (A)
insere (B)
insere (C)
Final
remove(Início)
C
(b)
B
Final
C
D
E
insere (D)
insere (E)
(c)
72
Estrutura Estática – Fila Estática
public class FilaEstatica {
int informacoes[];
int inicio=0, fim=0, tamanho;
public int retira()
{ if (inicio == fim)
return -1;
public FilaEstatica(int tamanho)
{ this.tamanho = tamanho;
informacoes = new int[tamanho];
}
// fila vazia
int valor=informacoes[inicio];
inicio=(inicio+1) % tamanho;
return valor;
}
public boolean insere(int info)
{
if (inicio == ((fim + 1) % tamanho)) // testa se a fila está cheia
{
return false;
}
informacoes[fim] = info;
fim = (fim+1) % tamanho;
return true;
}
73
Estrutura Estática – Fila Estática
public boolean consulta(int n)
{ FilaEstatica filaAux = new FilaEstatica(tamanho);
int aux;
boolean achou = false;
while (inicio != fim)
{ aux = retira();
if (n == aux)
{ achou = true;
}
filaAux.insere(aux);
}
while (filaAux.inicio != filaAux.fim)
{ aux = filaAux.retira();
insere(aux);
}
return achou;
}
}
74
Estrutura Dinâmica – Fila Dinâmica
public class FilaDinamica
{
Nodo inicio = null, fim = null;
int qtd = 0;
public void insere(int n)
if (inicio == null) // ins. 1º elemento
{ fim = novo;
inicio = novo;
}
else // inserção no final da fila
{ fim.prox = novo;
fim = novo;
}
qtd++;
}
class Nodo
{ int info;
Nodo prox;
Nodo(int n)
{ info = n;
prox = null;
}
}
75
Estrutura Dinâmica – Fila Dinâmica
public Nodo remove()
{ if (inicio == null) // fila vazia
return null;
else // remoção do inicio da fila
{ Nodo atual=inicio;
inicio=inicio.prox;
qtd--;
return atual;
}
}
{ FilaDinamica filaAux = new FilaDinamica();
Nodo aux;
boolean achou = false;
while (inicio != null)
{ aux = remove();
if (n == aux.info)
{ achou = true;
}
filaAux.insere(aux.info);
}
while (filaAux.inicio != null)
{ aux = filaAux.remove();
insere(aux.info);
}
return achou;
}
}
76
Pilha
LIFO - Last-In, First-Out (O Último a Entrar é o 1º a Sair)
topo
A
B
C
(a)
A
empilha(A)
empilha(B)
empilha(C)
topo
desempilha(topo)
B
(b)
A
B
topo
D
E
empilha(D)
empilha(E)
(c)
77
Estrutura Estática – Pilha Estática
public class PilhaEstatica
{ int informacoes[];
int topo, tamanho;
public int desempilha()
{ if (topo == 0)
{ return -1; // pilha vazia
}
topo--;
return informacoes[topo];
}
public PilhaEstatica(int maxPilha)
{ topo=0;
tamanho=maxPilha;
informacoes = new int[tamanho]; { boolean resultado = false;
}
PilhaEstatica pilhaAux;
pilhaAux = new PilhaEstatica(tamanho);
while ((topo > 0) && (informacoes[topo-1] != n))
public boolean empilha(int n)
{ pilhaAux.empilha(desempilha());
{ if (topo == tamanho)
}
{ return false;
// pilha cheia
if (topo != 0)
}
resultado=true;
while (pilhaAux.topo > 0)
informacoes[topo]=n;
empilha(pilhaAux.desempilha());
topo++;
return resultado;
return true;
}
78
}
}
Estrutura Dinâmica – Pilha Dinâmica
public class PilhaDinamica
{ Nodo topo=null;
int qtd=0;
{ boolean resultado = true;
PilhaDinamica pilhaAux;
pilhaAux = new PilhaDinamica();
public void empilha(int n)
Nodo aux;
while ((topo != null) && (topo.info != n))
if (topo != null)
{ aux = desempilha();
novo.prox=topo;
pilhaAux.empilha(aux.info);
topo=novo;
}
qtd++;
if (topo == null)
}
{ resultado=false;
}
public Nodo desempilha()
while ((pilhaAux.topo != null))
{ if (topo == null)
// Pilha vazia
{ aux = pilhaAux.desempilha();
return null;
empilha(aux.info);
else // remoção no topo da Pilha
}
{ Nodo aux = topo;
return resultado;
topo = topo.prox;
}
qtd--;
}
return aux;
79
}
}
Recursividade
•
Definição: A recursividade pode ser considerada um método eficaz para resolver
um problema originalmente complexo, reduzindo-o em pequenas ocorrências do
problema principal. Assim, segue a ideia de dividir para conquistar. Resolvendo,
isoladamente, cada uma das pequenas partes, podemos obter a solução do
problema original como um todo.
•
Características de uma função recursiva
 Definição de parâmetros;
 Condição de parada da recursão, para que a rotina não seja chamada
infinitamente;
 Chamada da função dentro dela própria;
•
Rotinas recursivas e pilhas
 O controle de chamadas e de retorno de rotinas é efetuado por uma pilha
(criada e mantida dinamicamente pelo sistema). Quando uma rotina é
chamada, empilha-se o endereço da rotina e todas as variáveis locais são
recriadas. Quando ocorre o retorno da rotina as variáveis locais que foram
criadas deixam de existir.
•
Vantagens: Facilidade na resolução de alguns tipos de problemas.
•
Desvantagens:
computador.
Uso
demasiado
dos
recursos
computacionais
de
80
um
Recursividade – Exemplo de Aplicação
public class Recursividade extends
javax.swing.JFrame
{ String resposta;
public Recursividade()
{ initComponents();
}
{ int n;
try
}
catch (Exception e)
{ JOptionPane.showMessageDialog(null,"Digite apenas números inteiros!");
return;
}
int fat = fatorial(n);
list1.removeAll();
list1.add("O fatorial de "+ n + " é "+fat);
81
}
{
int n;
try
}
catch (Exception e)
{ JOptionPane.showMessageDialog(null,"Digite apenas números inteiros!");
return;
}
list1.removeAll();
resposta="";
binario(n);
list1.add("O valor de "+ n + " em binário é "+resposta);
jTextField1.requestFocus();
// TODO add your handling code here:
}
82
public int fatorial(int n)
{ int res;
if (n == 0)
{ return 1;
}
else
{ res = fatorial(n-1);
res = res * n;
return res;
}
}
public void binario(int n)
{ int resto=0;
if (n > 0)
{ resto = n % 2;
binario(n / 2);
resposta+=resto;
}
}
{
public void run() {
new Recursividade().setVisible(true);
}
});
}
}
83
Árvores

Definição:

Relação de hierarquia ou de composição entre os dados (nós).

Conjunto finito T de um ou mais nós, tais que:
 (a) existe um nó denominado raiz da árvore;
 (b) os demais nós formam m >= 1 conjuntos disjuntos S1,...,Sm,
onde cada um desses conjuntos é uma árvore.


As árvores Si recebem a denominação de subárvores.
Terminologia:

Cada nó da árvore é a raiz de uma subárvore.

O número de subárvores de um nó é o grau daquele nó.

Um nó de grau igual a zero é denominado folha ou nó terminal.

A raiz da árvore tem nível 0.

Os demais nós: nível = número de "linhas" que o liga à raiz.

Altura: nível mais alto da árvore.
84
Árvores
•
Representação Estrutural:
Grau = 3; Nível =0 (raíz)
A
C
B
E
F
D
G
H
I
Grau = 1; Nível = 1
Grau = 3; Nível = 2
J
Grau = 0 (Folha)
K Grau = 0; Nível = 3
Árvore com altura igual a 3
85
Árvores Binárias
•
Uma árvore binária é uma estrutura de dados útil quando precisam ser
tomadas decisões bidirecionais em cada ponto de um processo.
•
O Grau de cada nó é menor ou igual a 2 (Subárvores da esquerda e da direita).
•
Se grau = 1, deve ser especificado se a sua subárvore é a da esquerda ou a da
direita.
•
Árvore Estritamente Binária: é a árvore onde todo o nó que não é folha
possuí subárvores a esquerda e a direita.
•
Uma Árvore Binária Completa é uma árvore estritamente binária sendo que
todas as folhas devem estar no mesmo nível.
86
Árvores Binárias
•
Representação Estrutural:
Árvore Estritamente Binária
Árvore Binária Completa
4
5
2
8
9
6
5
2
1
7
4
6
9
7
•
Regra Geral de Inserção:
 Os valores menores devem ficar a esquerda da raiz e os maiores a
direita. Os valores repetidos não devem ser inseridos.
•
Exercício:
 Insira os seguintes nós: 14, 15, 4, 9, 7, 18, 2, 5, 16, 4, 20, 17, 9, 5.
87
Árvores Binárias
•
Como Percorrer uma árvore?



Pré-ordem
1º. visitamos a raiz
2º. subárvore esq. em pré-ordem
3º. subárvore dir. em pré-ordem
Em ordem
1º. subárvore esq. em ordem
2º. visitamos a raiz
3º. subárvore dir. em ordem
Pós-ordem
1º. subárvore esq. em pós-ordem
2º. subárvore dir. em pós-ordem
3º. Visitamos a raiz
(Centro, Esquerda, Direita)
(Esquerda, Centro, Direita)
(Esquerda, Direita, Centro)
88
Árvores Binárias

Exemplos:
20
10
5
4
7
2
3
5
9
6
4
8
Pré-ordem: 5, 4, 2, 3, 9, 7, 6, 8, 10
 Em ordem: 2, 3, 4, 5, 6, 7, 8, 9, 10
 Pós-ordem: 3, 2, 4, 6, 8, 7, 10, 9, 5

6
2
10
15
12
7
18
17
19
20, 10, 5, 2, 4, 6, 7, 15, 12, 18, 17, 19
 2, 4, 5, 6, 7, 10, 12, 15, 17, 18, 19, 20
 4, 2, 7, 6, 5, 12, 17, 19, 18, 15, 10, 20

89
Estrutura Dinâmica – Classe NodoArvore
public class NodoArvore
{
int info;
NodoArvore pai;
NodoArvore f_esq;
NodoArvore f_dir;
boolean deletado;
NodoArvore(int n, NodoArvore p)
{ info = n;
pai = p;
f_esq = null;
f_dir = null;
deletado = false;
}
}
90
Estrutura Dinâmica – Árvore Binária
import java.awt.List;
public class ArvoreBinaria
{
NodoArvore raiz=null;
int qtd=0;
public void preOrdem(NodoArvore subRaiz, List objList)
{ if (subRaiz != null)
{ if (subRaiz.deletado == false)
{ objList.add(""+subRaiz.info);
}
preOrdem(subRaiz.f_esq, objList);
preOrdem(subRaiz.f_dir, objList);
}
}
91
public void ordem(NodoArvore subRaiz, List objList)
{ ordem(subRaiz.f_esq, objList);
if (subRaiz.deletado == false)
}
ordem(subRaiz.f_dir, objList);
}
}
public void posOrdem(NodoArvore subRaiz, List objList)
{ posOrdem(subRaiz.f_esq, objList);
posOrdem(subRaiz.f_dir, objList);
if (subRaiz.deletado == false)
}
}
}
92
{ NodoArvore aux, pai, novo;
if (raiz == null) // inserção da raiz
{ novo = new NodoArvore(n, null);
raiz = novo;
}
else
{ aux = raiz;
pai = raiz; // pesq. posição de inserção
while ((aux != null) && (n != pai.info))
{ pai = aux;
if (n < pai.info)
aux = pai.f_esq;
else
aux = pai.f_dir;
}
if (n == pai.info)
{ if (pai.deletado == true)
{ pai.deletado = false;
return true;
}
else
{ return false;
}
}
novo = new NodoArvore(n, pai);
if (n < pai.info)
{ pai.f_esq = novo;
}
else
{ pai.f_dir = novo;
}
}
qtd++;
return true;
93
public NodoArvore consulta(int n)
{ NodoArvore aux=raiz, pai=raiz;
if (raiz == null)
return null; // árvore sem elementos
while ((aux != null) && (n != pai.info))
{ pai = aux;
if (n < pai.info)
aux = pai.f_esq;
else
aux = pai.f_dir;
}
if ((n == pai.info) && (pai.deletado == false))
return pai;
// informação encontrada
else
return null; // informação não encontrada
}
public boolean retira(int n)
{ NodoArvore remover;
remover = consulta(n);
if ((remover != null) &&
(n == remover.info))
{ remover.deletado=true;
return true;
}
else
{ return false;
}
}
94
Árvores AVL
• Definição: Uma árvore AVL é uma árvore binária de busca construída de tal
modo que a altura de sua Sub-árvore direita difere da altura da Sub-árvore
esquerda de no máximo 1.
• O que pode acontecer quando um novo nó é inserido numa árvore
balanceada ?
 Nós 9 ou 11 podem ser inseridos sem balanceamento .
Sub-árvore com raiz 10 passa a ter uma Sub-árvore e
Sub-árvore com raiz 8 vai ficar melhor balanceada !

Inserção dos nós 1, 3, 5 ou 7 requerem que a árvore
seja balanceada!
• Fator de Balanceamento de um nó:
 É a altura da Sub-árvore direita do nó menos a altura da Sub-árvore
esquerda do nó .
 FB= altura direita - altura esquerda
 Se todos os FB forem [-1, 0, 1] a árvore está balanceada. 95
Árvores AVL
•
Balanceamentos:
 Nos casos abaixo considere P como sendo o nó raiz de uma Sub-árvore
desbalanceada e U como sendo o nó filho dessa raiz.

Caso 1: Altura Esquerda de P > Altura Direita de P
 Caso 1.1 : Rotação Simples a Direita
 Caso 1.2 : Rotação Dupla a Direita
Rotação para a esquerda
e em seguida para a
direita
96
Árvores AVL
 Caso 2: Altura Direita de P > Altura Esquerda de P
 Caso 1.2: Rotação Simples a Esquerda
 Caso 2.2 : Rotação Dupla a Esquerda
Rotação para a direita e em
seguida para a esquerda
97
Árvores AVL
• Exemplos de Rotações ( Rotação simples a direita):
4
Rotação a
Direita
2
8
3
6
10
• Exemplos de Rotações ( Rotação dupla a direita):
Rotação a
Esquerda e
a Direita
98
Árvores AVL
• Exemplos de Rotações ( Rotação simples a esquerda):
10
Rotação a
Esquerda
15
8
4
12
9
• Exemplos de Rotações ( Rotação dupla a esquerda):
10
5
10
Rotação a
Direita e
a Esquerda
20
25
5
30
20
25
30
99
Árvores AVL
• Regras para as rotações:
 Rotação Simples a Direita: rotaciona o U sobre o P para a direita, sendo
que o filho da direita de U passa a ser o filho da esquerda de P.
 Rotação Simples a Esquerda: rotaciona o U sobre o P para a esquerda,
sendo que o filho da esquerda de U passa a ser o filho da direita de P.
 Rotação Dupla a Direita: rotaciona o V sobre U para a esquerda, sendo
que o filho da esquerda de V passa a ser o filho da direita de U. Após,
rotaciona V sobre P para a direita, sendo que o filho da direita de V passa a
ser o filho da esquerda de P.
 Rotação Dupla a Esquerda: rotaciona o V sobre U para a direita, sendo
que o filho da direita de V passa a ser o filho da esquerda de U. Após,
rotaciona V sobre P para a esquerda, sendo que o filho da esquerda de V
passa a ser o filho da direita de P.
100
Árvores B
• Definição:
 É a Construção e manutenção de árvores de busca de grandes
dimensões.
 Ponteiros referem-se a áreas de memória secundária, em vez de
representarem endereços da memória principal.
 Busca: acesso a disco (com os inerentes atrasos de acesso).
 Sub-árvores representadas em unidades, do ponto de vista de acesso
páginas
 Reduz o número de acessos ao disco.
 Necessita de esquema de crescimento controlado.
 Todo nó, exceto a raiz, deve possuir entre n e 2n chaves, para uma dada
constante n.
• Características:
 Cada página (nó) contém no máximo, 2n elementos (chaves);
 cada página, exceto a que contém a raiz, contém no mínimo n chaves;
 os nós chamados folhas não têm descendentes e os demais(nós de
derivação) possuem m + 1 descendentes, onde m é a quantidade de
101
chaves;
 todas as folhas têm o mesmo nível.
Árvores B
• Representação Estrutural:
K1
P0
K2
P1
P2
...
...
Km
Pm-1
Pm
• Exemplo: Árvore B (ordem 2):
Raiz
30
15
2689
22
17 18 20 21
40 50
27 29
36 38 39
42 45 48
51 53 55 56
102
Árvores B
• Regras para redistribuir chaves:
1) Redistribuir a chave mais a esquerda de uma página que extrapolou os
limites da ordem. Suba o elemento mais a esquerda para a página pai e
desça o elemento de ligação para a página irmã esquerda.

Caso não seja possível executar a redistribuição porque a página irmão
está cheia ou não exista, passe para a segunda regra.
2) Redistribuir a chave mais a direita de uma página que extrapolou os limites
da ordem. Suba o elemento mais a direita para a página pai e o elemento
de ligação para a página irmã direita.

Caso não seja possível executar a redistribuição porque a página irmão
está cheia ou não exista, passe para a terceira regra.
3) Quebre em duas a página que extrapolou os limites da ordem e suba o
elemento do meio para a página pai.
103

class

Transcrição

Documentos relacionados

Bubble sort

Programa de Pós-Graduação em Estudos Contemporâneos das

to get the file

Lista de Exercícios Nro. 1

Módulo 03 Identificadores, Palavras Reservadas, e - BCC Unifal-MG

MedBook - Medsky

Resenhas de Richard Blanco Peck

Carta de solicitação de emprestimo

+ JHS Vaticano, 8 de abril de 2016. Caro irmão, invocando a

Exame1 2011-12 versao impressa