Lista ligada

Uma lista ligada é uma coleção de nós (ou registros) em que cada um aponta (referencia) o próximo.
As operações que geralmente são executadas sobre uma lista ligada são inserção, remoção e busca. São as operações de dicionário.
Listas ligadas tem comprimento variável.
Sua tarefa é entender os métodos que inserem, removem e buscam.
Aqui está o código fonte:
https://drive.google.com/file/d/0B2aucTjhMlIVQWV6MDFLUHEwV2c/view?usp=sharing

Segue a listagem:

01 package Lista; 02 class No { 03    protected String chave, conteudo; 04    protected No prox; 05    No () { 06       chave=null; 07       conteudo=null; 08    } 09    No (String chave, String conteudo) { 10       this.chave= new String (chave); 11       this.conteudo= new String (conteudo); 12    } 13    String getChave () { 14       return new String (chave); 15    } 16    String getConteudo () { 17       return new String (conteudo); 18    } 19    No getProx () { 20       return prox; 21    } 22    void setChave (String chave) { 23       this.chave=new String (chave); 24    } 25    void setConteudo (String conteudo) { 26       this.conteudo=new String (conteudo); 27    } 28    void setProx (No prox) { 29       this.prox=prox; 30    } 31 }

Java2html

01 package Lista; 02 public class Lista { 03    protected No inicio; 04    public Lista () { 05       inicio=null; 06    } 07    public void insereNoInicio (String chave, String conteudo) { 08       No novoInicio=new No (chave, conteudo); 09       novoInicio.setProx (inicio); 10       inicio=novoInicio; 11    } 12    public void insereNoFinal (String chave, String conteudo) { 13       No aux=inicio; 14       if (aux==null) { 15          inicio=new No (chave, conteudo); 16       } else { 17          while (aux.getProx()!=null) 18             aux=aux.getProx(); 19          aux.setProx (new No (chave, conteudo)); 20       } 21    } 22    public String busca (String chave) { 23       // retorna o conteúdo 24       No aux=inicio; 25       while ((aux!=null) && (!chave.equals(aux.getChave()))) 26          aux=aux.getProx(); 27       if (aux!=null) return aux.getConteudo(); 28       return null; 29    } 30    public boolean remove (String chave) { 31       No aux=inicio; 32       if (aux==null) { 33          //throw EmptyListException(); 34          System.out.println ("Erro: tentou remover de lista vazia"); 35       } else { 36          if (chave.equals(aux.getChave())) { 37             // eh o primeiro que tem que ser removido. 38             inicio=inicio.getProx(); 39             return true; 40          } 41          while ((aux.getProx()!=null) && (!chave.equals(aux.getProx().getChave()))) 42             aux=aux.getProx(); 43          if (aux.getProx()!=null) { 44             aux.setProx(aux.getProx().getProx()); 45             return true; 46          } 47       } 48       return false; 49    } 50    public boolean isEmpty () { 51       return inicio==null; 52    } 53    public void imprime () { 54       No aux=inicio; 55       if (isEmpty()) { 56          System.out.println ("Lista Vazia"); 57       } else { 58          System.out.println ("{"); 59          while (aux!=null) { 60             System.out.println ("    {" + aux.getChave() + "," + aux.getConteudo () + "}"); 61             aux=aux.getProx(); 62          } 63          System.out.println ("}"); 64       } 65    } 66 } 67  68 /* 69 class EmptyListException () { 70 } 71 */

Java2html

Leitura e escrita

A leitura e escrita de arquivos é implementada por classes no pacote Java.io. Com essas classes pode-se usar pipes (são arquivos criados em memória para que processos executados no mesmo computador comuniquem-se - o sistema operacional pode ou não dar suporte a pipes).

Caso o sistema operacional emule arquivos de rede como arquivos locais (por exemplo o compartilhamento de drives do Windows e o Network File System no Linux), esse pacote pode também ser usado, reforçando, porque o sistema operacional apresenta um arquivo remoto como se fosse local.

Há diversos outros pacotes que tratam outros tipos de entrada e saída:

• HTTP o pacote é javax.swing.text.html
• imagens o pacote é javax.imageio.stream
• rede e sockets o pacote é java.nio.channels

A hierarquia de classes de java.io é grande. Uma parte dela é apresentada no diagrama abaixo:

Observe o padrão decorator:

• InputStream é o componente, FileInputStream é a implementação e ObjectInputStream é o decorador;
• Reader é o componente, InputStreamReader é a implementação e BufferedReader é o decorador.

Tarefa:
    Crie um programa que lê um arquivo texto e o imprime na tela.

Exemplo - decorator

código fonte zipado aqui.

01 /** Esta Ã© a classe (abstrata) básica. 02     Escolhi este porque creio ser o caso mais simples. 03 */ 04 interface Basico { 05    /** Nas classes concretas descreve o modelo,  06        nos decoradores acrescenta algo. 07    */ 08    public String getDescription(); 09    /** Nas classes concretas retorna o custo, 10        nos decoradores, inclui o custo da decoração 11       e retorna o custo. 12    */ 13    public double getCost(); 14 }

Java2html

01 /** Primeiro dos dois modelos básicos que pretendo implementar. 02 */ 03 public class Modelo1 implements Basico { 04    /** Nas classes concretas descreve o modelo,  05        nos decoradores acrescenta algo. 06    */ 07    public String getDescription() { 08       return "Carroceria"; 09    } 10    /** Nas classes concretas retorna o custo, 11        nos decoradores, inclui o custo da decoração 12       e retorna o custo. Caso valores precisem ser 13       exatos, sem truncar nem arredondar, Ã© melhor 14       usar int e codificá-los em centavos. 15    */ 16    public double getCost() { 17       return 10000.00; 18    } 19 }

Java2html

01 /** Decorador. 02 */ 03 public class Ar implements Basico { 04    /** Nas classes concretas descreve o modelo,  05        nos decoradores acrescenta algo. 06    */ 07    Basico b; 08    Ar (Basico b) { 09       this.b=b; 10    } 11    public String getDescription() { 12       return b.getDescription() + " Ar-condicionado"; 13    } 14    /** Nas classes concretas retorna o custo, 15        nos decoradores, inclui o custo da decoração 16       e retorna o custo. Caso valores precisem ser 17       exatos, sem truncar nem arredondar, Ã© melhor 18       usar int e codificá-los em centavos. 19    */ 20    public double getCost() { 21       return b.getCost() + 3500.00; 22    } 23 }

Java2html

01 /** Decorador. 02 */ 03 public class Direcao implements Basico { 04    /** Nas classes concretas descreve o modelo,  05        nos decoradores acrescenta algo. 06    */ 07    Basico b; 08    Direcao (Basico b) { 09       this.b=b; 10    } 11    public String getDescription() { 12       return b.getDescription() + " Direção Eletro-assistida"; 13    } 14    /** Nas classes concretas retorna o custo, 15        nos decoradores, inclui o custo da decoração 16       e retorna o custo. Caso valores precisem ser 17       exatos, sem truncar nem arredondar, Ã© melhor 18       usar int e codificá-los em centavos. 19    */ 20    public double getCost() { 21       return b.getCost() + 2000.00; 22    } 23 }

Java2html

01 /** Decorador. 02 */ 03 public class DVDplayer implements Basico { 04    /** Nas classes concretas descreve o modelo,  05        nos decoradores acrescenta algo. 06    */ 07    Basico b; 08    DVDplayer (Basico b) { 09       this.b=b; 10    } 11    public String getDescription() { 12       return b.getDescription() + " DVD player"; 13    } 14    /** Nas classes concretas retorna o custo, 15        nos decoradores, inclui o custo da decoração 16       e retorna o custo. Caso valores precisem ser 17       exatos, sem truncar nem arredondar, Ã© melhor 18       usar int e codificá-los em centavos. 19    */ 20    public double getCost() { 21       return b.getCost() + 800.00; 22    } 23 }

Java2html

01 class TestaDecorador { 02    public static void main (String[] args) { 03       Basico b = new Modelo1(); 04       System.out.println (b.getCost()); 05       Basico c = new Ar(new Modelo1()); 06       System.out.println (c.getDescription()); 07       Basico d = new Direcao(new Ar(new Modelo1())); 08       System.out.println (d.getDescription()); 09    } 10 }

Java2html

Decorator

Decorator é um "padrão de projeto" (design pattern). Não tem nada a ver com uma norma, é uma forma de arranjar classes de forma a obter certa funcionalidade.

Este padrão permite estender (ampliar ou modificar) funcionalidades em tempo de execução. Em comparação com herança, reduz o número de subclasses para implementar as mesmas variações de funcionalidades.

É extensivamente usado no pacote java.io.

Decorator é construído a partir de uma classe (em geral interface ou classe abstrata) que define os métodos que existem tanto nas classes concretas quanto nos decoradores. As classes concretas implementam a funcionalidade básica que ainda não o foram na superclasse. Os decoradores contém (em geral como atributo), instâncias das classes concretas e estendem a funcionalidade invocando os métodos da classe concreta e acrescentando algo quando necessário. A relação básica entre as classes é ilustrada abaixo.

 Exemplos deixarão isto mais claro.

Exceções - explicações

Java provê um mecanismo especifico para gerenciar eventos inesperados durante o ciclo de codificação e execução de programas. Neste mecanismo, a ocorrência desses eventos é transmitida através de objetos. A hierarquia de classes é apresentada abaixo:

Os objetos para gerenciar os eventos inesperados são Error e Exception. RunTimeException é subclasse de Exception. Todos são subclasse de Throwable (algo como Lançável). Nesta superclasse está implementada a maioria dos métodos.(https://docs.oracle.com/javase/8/docs/api/java/lang/RuntimeException.html)

As instâncias de Throwable, ou de suas subclasses, são lançadas pelo comando throw. Caso seja necessário marcar que determinado método lança exceções, sua assinatura é seguida pela declaração throws Exception. Exception requer essa marcação, ou seja, se um método lança (throw) uma instância de Exception então ele e todos os métodos que o invocam (numa sequência de chamadas) devem ou ser marcados (com isso eles repassam a exceção para o método que o invocou), ou tratar a exceção. O tratamento de uma exceção consiste em tentar executar o método que lança a exceção (para "tentar", coloca-se a invocação do método dentro de um bloco try), caso alguma exceção seja lançada, capturá-la (com o comando catch), tratá-la (num bloco de comandos associado ao comando catch) e fazer uma "limpeza" com o comando finally.

0.0.0.17.8 - Aula 9 - 09.04

Revisar teorema da programação estruturada:

~ 0.0.0.3 - Teoria - teorema da programação estruturada

• ~  0.0.0.3.1 - Tente notar os detalhes....
  

Estudar teoria:
~ 0.0.0.10 - Métodos

• ~ 0.0.0.10.0 - metodos 2
• ~ 0.0.0.10.1 - métodos 3
• ~ 0.0.0.10.2 - métodos 4
• ~ 0.0.0.10.3 - métodos 5

Estudar solução proposta para problema da semana passada:http://fabionakano.blogspot.com.br/2015/04/0001770-proposta-de-programa-para.html

Objetivo: melhorar a estrutura da solução proposta usando métodos.

Material sobre orientação a objetos, UML, e projeto de software no xerox, pasta 12.

Veja propostas de programas em:

~ 0.0.0.17.8 - Aula 9 - 09.04

• ~  0.0.0.17.8.0 - Métodos e globais
  ~  0.0.0.17.8.1 - Métodos e locais por uso
  ~  0.0.0.17.8.2 - Métodos e locais por persistência de valor
  ~  0.0.0.17.8.3 - Usando particularidades da codificação de caracteres
  

0.0.0.11.5.0.1 - Código do exemplo, gerado por ArgoUML

Código gerado a partir do diagrama usando ArgoUML, com indentação ajustada por Indent by Fold e visualização html gerada por j2html

01 public class Mesa { 02     public int altura; 03     public int largura; 04     public int profundidade; 05     public int maxPeso; 06     public int maxCarga; 07     public boolean cabe(int locAltura, int locLargura, int locProfundidade) { 08         return false; 09     } 10      11     public boolean suporta(int carga) { 12         return false; 13     } 14      15     public Mesa(int altura, int largura, int comprimento, int maxPeso, int maxCarga) { 16     } 17      18 }

Java2html indent by fold

0.0.0.11.5.0 - Exemplo de classe

O diagrama para uma classe:

A classe é pública (+) chama-se Mesa.
Tem os atributos (+) públicos, todos de tipo int, com nomes altura, largura, profundidade, maxPeso e maxCarga.
Tem os métodos cabe, que recebe três argumentos de tipo int e retorna um boolean; suporta, que recebe um argumento de tipo boolean e retorna um boolean e um construtor (estereótipo <<create>>).
(o diagrama foi feito usando ArgoUML).

0.7 - Grafos

Este post é sobre a piada das árvores em computação crescerem de cima para baixo...
Relaciona-se aos temas "tipos abstratos de dados", "arrays" e "matrizes" do conteúdo de ACH2001. O conteúdo deste post será melhorado aos poucos.

Grafos são trincas G=(V,A,f) onde V é um conjunto de vértices ou nós (são os pontos da figura), A é um conjunto de arcos, ou arestas (são as linhas das figuras) cada extremidade da aresta incide em um único vértice, então arestas ligam dois vértices. f é uma função que informa como essa ligação é feita.

Passeio em um grafo é uma sequencia alternante de vértices e arestas iniciada e terminada em vértices.

Caminho em um grafo é uma sequencia alternante de vértices e arestas iniciada e terminada em vértices Sem repetição.

Circuito em um grafo é um caminho que inicia e termina no mesmo vértice.

Árvores são grafos acíclicos.

Qualquer vértice de uma árvore pode ser raiz (imagine que o grafo é um conjunto de bolas e que as arestas são fios ligando as bolas. Escolha qualquer bola, segure e levante-a - as outras sobem puxadas pelas arestas, no formato de árvore com raiz.

O que informa a necessidade de escolher um vértice como raiz e qual é ele é o uso que faremos da árvore.