Estruturas de Dados 2019/2020 (CC1007) - DCC/FCUP

Aula Prática #03 - Introdução a Classes
(semana de 02/03 a 06/03)

Exercício 1) "Brincando" com classes

// Uma classe simples para representar um aluno
class Aluno {
   // Atributos da classe (variáveis para conter informação)
   String nome;
   int numero;

   // Construtor "padrão"
   Aluno() {
      nome   = "indefinido";
      numero = -1;
   }
}

// Classe principal contendo o main para testar a classe Aluno
public class TestAluno {
   public static void main(String[] args) {
      Aluno a = new Aluno();
      
      System.out.println("a.nome = " + a.nome);
      System.out.println("a.numero = " + a.numero);
   }
}

1. Várias classes num ficheiro.
   Copie o código de cima para um ficheiro TestAluno.java. Compile o código. Quantos ficheiros .class foram criados?
   (usualmente temos um ficheiro para cada classe, mas também é possível ter várias classes num só ficheiro)
2. Executar uma classe.
   Experimente executar a classe Aluno ($ java Aluno). O que acontece? Porquê? Experimentar agora executar a classe TestAluno e verifique que tal já é possível, pois esta classe contém um método main com a assinatura esperada.
3. Referências.
   1. Adicione a seguinte linha na parte final método main:

      System.out.println("a = " + a);   
      

      Experimente compilar e executar. O que acontece? Note que está a imprimir... a referência ao objecto!
   2. Sem apagar a linha que imprimia a referência, adicione agora o seguinte método à classe Aluno:
      

      public String toString() {
         return "(" + nome + "," + numero + ")";
      }
      

      Compile e execute. O que acontece? De um modo geral, se quiser modificar o que é escrito quando imprimir uma referência a um objecto, basta implementar um método public String toString() que devolva uma String que represente o objecto.
      Quero saber mais: tecnicamente, estamos a fazer override do método toString() padrão de todos os objectos. O que é usualmente imprimido é fruto da implementação padrão que pode ser vista aqui.
   3. Acrescente o seguinte código ao main:

      Aluno b = new Aluno();
      Aluno c = b;
      b.nome = "modificado";
      System.out.println("b = " + b);
      System.out.println("c = " + c)
      

      Compile e execute. O que é mostrado? Uma referência é "quase como um apontador" e ao usarmos o operador = não estamos a copiar todos os atributos (variáveis) da classe, mas sim a colocar a referência a apontar para a mesma instância do objecto.
4. Construtores e overload de métodos.
   Seria útil poder dar valores diferentes aos atributos de um aluno quando o criamos. Vamos criar um construtor para isso. Acrescente o seguinte código à classe Aluno:

   Aluno(String n, int mec) {
      nome = n;
      numero = mec;
   }
   

   Já no método main acrescente o seguinte pedaço de código para testar:

   Aluno d = new Aluno();
   Aluno e = new Aluno("Manuel", 201506234);
   System.out.println("d = " + d);
   System.out.println("e = " + e);
   

   Compile e execute. O que é mostrado? No Java podem existir várias funções com o mesmo nome mas com argumentos diferentes. Quando o código é executado é chamada a função que corresponde aos argumentos utilizados. Experimente por exemplo tentar criar um objecto com Aluno f = new Aluno("Maria");. O que acontece? Porquê?
5. Criando um novo método.
   Para além dos atributos (variáveis contendo dados) e de métodos construtores, uma classe pode conter métodos implementando quaisquer funções que necessite. Assumindo que um número mecanográfico tem sempre 9 dígitos e que os primeiros 4 indicam o ano de entrada na universidade, vamos criar um método para devolver o ano de um aluno. Acrescente o seguinte código à classe Aluno:

   int ano() {
      return numero / 100000;
   }

   Já no main acrescente o seguinte para testar:

   Aluno g = new Aluno("Ana", 201408762);
   Aluno h = new Aluno("Bruno", 201508145);
   System.out.println(g.ano() + " " + h.ano());
   

   Compile e execute para verificar o funcionamento.
6. Arrays de objectos e o "meu primeiro NullPointerException"
   Experimente adicionar o seguinte código ao seu main:

   int n = 3;
   Aluno[] v = new Aluno[n];
   for (int i=0; i<n; i++)
      System.out.println("v[" + i + "] = " + v[i]);
   v[0].nome = "Pedro";
   

   Compile e execute. O que acontece?
   
   Quando cria um array de objectos, cada uma das suas posições fica com uma referência. No entanto as referências ainda estão todas a apontar para null, que é o valor padrão de uma referência, ou seja, ainda não foram criadas as instâncias correspondentes a cada um dos objectos. E quando se tenta aceder ao atributo nome de uma referência nula, obtém-se... um NullPointerException! Para inicializar podia fazer algo como for (int i=0; i<n; i++) v[i] = new Aluno(); a seguir a declarar o array (experimente essa adição e verifique que já não obtém nenhum erro na execução).
7. Variáveis e métodos estáticos.
   Cada instância de um objecto tem uma cópia diferente de todos as suas variáveis. E se quisermos ter uma variável comum a todas as instâncias de um Aluno? Para isso podemos usar o qualificador static.
   • Adicione a linha public static int contador = 0; logo a seguir à linha class Aluno {.
   • Acrescente também a linha contador++; aos dois construtores que criou.
   • Na função main acrescente a linha System.out.println("contador = " + Aluno.contador); logo no início e também no final, depois de criados todos os alunos.
   O que é imprimido? Que valor tinha o contador no início e que valor tem no final depois de todas as chamadas a new Aluno? Note também como pode chamar a variável mesmo antes de criar um qualquer objecto desse tipo (usando para isso NomeDaClasse.VariavelEstatica).
    
   Do mesmo modo que uma variável pode ser estática, também um método o pode ser, e nesse caso só poderá chamar variáveis estáticas, pois as outras variáveis estão associados a uma única instância de um objecto.

Exercício 2) Objectos Geométricos

// Uma classe simples para representar um ponto 2D
class Point {
   int x, y;

   Point() {
      x = y = 0;
   }
   
   Point(int x0, int y0) {
      x = x0;
      y = y0;
   }

   // Devolve uma representação em texto do conteúdo de um Ponto
   public String toString() {
      return "(" + x + "," + y + ")";
   }
}

// Classe principal com a função main
public class TestGeometry {
   public static void main (String[] args){
      Point p1 = new Point();
	
      System.out.println("p1 original: " + p1);
      p1.x = 1;
      System.out.println("p1 modificado: " + p1);

      Point p2 = new Point(2,3);
      System.out.println("p2: " + p2);
   }
}

1. Criando pontos.
   Compile e execute este código. Procure perceber o que fazem cada uma das linhas de código dadas.
2. Criação de uma nova classe e métodos associados.
   O objectivo deste exercício é a criação de uma nova classe Rectangle para representar um rectângulo.
   
   Resolva e submeta com sucesso o problema [ED186] TAD Rectângulo (Rectangle), disponível no "Volume 2 (TADs)".
   Notas/Dicas:
• TAD é o acrónimo de "Tipo Abstracto de Dados" e vamos falar nele nas próximas semanas nas teóricas.
• Deve submeter um ficheiro apenas a classe que implementa a classe Rectangle. O Mooshak já tem implementada a classe Point e irá criar várias instâncias da sua classe Rectangle usando os construtores definidos e irá fazer uma série de testes aos métodos por si implementados.
• O enunciado no Mooshak inclui exemplo de utilização de utilização que poderá usar para testar o seu programa.
• Deve implementar um método de cada vez e ir testando o seu funcionamento para garantir que está a funcionar como desejado.
• Este volume do Mooshak inclui pontuação parcial, o que significa que poderá ver que métodos é que já estão correctamente implementados, mesmo que não os tenha ainda feito todos.
3. Generalizando uma classe.
   Como poderia modificar a classe Point para passar a aceitar pontos a 3 dimensões? E para aceitar pontos com N dimensões? Consegue modificar a classe para que aceitar também a dimensão como parâmetro de criação do ponto?

Exercício 3) Uma classe para representar matrizes

import java.util.Scanner;

class Matrix {
   int data[][]; // os elementos da matriz em si
   int rows;     // numero de linhas
   int cols;     // numero de colunas

   // construtor padrao de matriz
   Matrix(int r, int c) {
      data = new int[r][c];
      rows = r;
      cols = c;
   }

   // Ler os rows x cols elementos da matriz
   public void read(Scanner in) {
      for (int i=0; i<rows; i++)
         for (int j=0; j<cols; j++)
            data[i][j] = in.nextInt();
   }

   // Representacao em String da matrix
   public String toString() {
      String ans = "";
      for (int i=0; i<rows; i++) {
         for (int j=0; j<cols; j++)
            ans += data[i][j] + " ";
         ans += "\n";
      }
      return ans;
   }
   
}

public class TestMatrix {
   public static void main(String[] args) {
      Scanner stdin = new Scanner(System.in);
      Matrix m = new Matrix(stdin.nextInt(), stdin.nextInt());
      m.read(stdin);
      System.out.print(m);
   }    
}

1. Executando o programa.
   Compile e execute este código, redirecionando o input a partir do ficheiro matrix.txt
   $ java TestMatrix < matrix.txt
   Procure compreender todas as partes do código.
2. Lançando uma excepção
   Acrescente no final (mas dentro) do método main o seguinte código:
   throw new RuntimeException("My very first custom error.");
   Execute o programa e verifique que agora uma excepção é gerado com a mensagem que foi indicada.
3. Criação de alguns métodos associados.
   O objectivo deste exercício é a criação vários métodos estáticos que acrescentam funcionalidades a esta classe de matrizes.
   
   Resolva e submeta com sucesso o problema [ED187] TAD Matriz (Matrix), disponível no "Volume 2 (TADs)".
   Notas/Dicas:
• O funcionamento deste problema é igual ao dos rectângulos. Deverá apenas submeter a classe Matrix e tem disponível um exemplo de utilização no enunciado do problema.
• Caso esteja esquecido das definições de matrizes necessárias (ex: o que é uma matriz identidade ou transposta) o enunciado disponibiliza links para as páginas respectivas na Wikipedia.

Exercícios extra para consolidação de conhecimentos

1. Uma classe para frações.
   • Crie uma classe Fraction para representar frações, que deverá conter como atributos dois inteiros: o numerador e o denominador. Não se esqueça de criar os respectivos construtores.
   • Adicione à classe os seguintes metódos:
   1. public String toString()
      Devolva uma representação em texto no formato u + n/d onde u são unidades e n/d uma fração menor que 1
      Exemplo: a fração 7/3 seria descrita como "2 + 1/3"
   2. public Fraction add(Fraction f)
      Devolve uma nova fração que é o resultado de adicionar f à fração
   3. public Fraction multiply(Fraction f)
      Devolve uma nova fração que é o resultado de multiplicar f pela fração
   4. public void simplify()
      Simplifica a fração dividindo o numerador e o denominador pelo seu máximo divisor comum (MDC).
      Exemplo: 18/48 ficaria simplificada para 3/8, sendo que MDC(18,48)=6.
      Para calcular o máximo divisor comum pode usar o Algoritmo de Euclides.
   • Teste a sua classe.
      
2. Ciclos e Matrizes.
   Para cimentar os seus conhecimentos sobre ciclos e matrizes tem mais um exercícios disponíveis no Mooshak (no volume 1):
   
   
   
   • Resolva e submeta com sucesso o problema [ED216] Contando Cardinais
      
3. Números aleatórios.
   Adicione um construtor novo à classe Matrix que dadas as dimensões e dois inteiros min e max cria uma nova matriz preenchida com números aleatórios entre min e max. A única dica que vamos dar é que existe uma classe java.util.Random para lidar com geração de números (pseudo)aleatórios.

Exercício de Desafio

Para esta semana o desafio tem a ver com a eficiência algorítmica. Deve tentar resolver o seguinte problema, que está disponível para submissão no Mooshak (o volume de Desafios):

• [ONI_RQ] Regras Quadriculadas (Prova de Seleção para as Olimpíadas Internacionais de Informática'2016)