Baixe o app para aproveitar ainda mais
Prévia do material em texto
FACULDADE NOSSA SENHORA APARECIDA FANAP ESTRUTURA DE DADOS EM JAVA: Introdução, Conceitos Gerais e Abordagens. Prof.: Fernando Gonçalves Abadia 2013/2 Sumário Ementa da Disciplina ...................................................................................................... 4 Objetivos ......................................................................................................................... 4 Conteúdo Programático ................................................................................................. 4 1- CONCEITOS BÁSICOS .......................................................................................... 6 1.1- Conceitos inter-relacionados ............................................................................... 6 1.2- Programação Java ............................................................................................... 7 1.3- Programando em Java ......................................................................................... 7 2- Tipos de Dados ....................................................................................................... 9 3- DIVISÕES BÁSICAS DA PROGRAMAÇÃO ......................................................... 12 3.1- Programação Sequencial ................................................................................... 12 3.1.1- Operadores Aritméticos ............................................................................... 14 3.1.2- Exercícios resolvidos: .................................................................................. 14 3.1.3- Exercícios propostos: .................................................................................. 15 3.2- Programação Condicional .................................................................................. 16 3.2.1- Operadores Relacionais .............................................................................. 18 3.2.2- Operadores Relacionais .............................................................................. 18 3.2.3- Exercícios resolvidos: .................................................................................. 18 3.2.2- Exercícios propostos: .................................................................................. 19 3.3- Programação com Repetição ............................................................................ 20 3.3.1- Repetição pré-testada ................................................................................. 20 3.3.2- Repetição pós-testada ................................................................................ 21 3.3.3- Repetição com varíavel de controle ............................................................ 22 3.3.4- Exercícios resolvidos ................................................................................... 24 3.3.5- Exercícios propostos: .................................................................................. 24 4- VETORES ............................................................................................................. 26 4.1- Declaração de um vetor ..................................................................................... 26 4.2- Realização de busca em um vetor ..................................................................... 27 4.3- Exercício resolvido ............................................................................................. 28 4.4- Exercícios propostos: ......................................................................................... 28 5- MATRIZES ............................................................................................................ 30 5.1- Exercícios resolvidos ......................................................................................... 31 5.2- Exercícios propostos .......................................................................................... 32 6- TIPOS ESPECIAIS DE MATRIZ .............................................................................. 34 6.1- Matrizes Diagonais ............................................................................................ 34 6.2- Matrizes Triangulares ........................................................................................ 35 6.3- Matrizes Simétricas e Anti-Simétricas ............................................................... 35 6.4- Matrizes Esparsas ............................................................................................. 36 7- TIPOS ABSTRATO DE DADO ................................................................................. 39 7.1- Classes e Objetos .............................................................................................. 41 7.2- Especificando uma Classe ................................................................................. 42 7.3- Objetos em Java ................................................................................................ 43 7.4- Atributos e Métodos ........................................................................................... 45 7.5- Exercícios Propostos ......................................................................................... 46 8- MÉTODOS E FUNÇÕES ...................................................................................... 47 8.1- Métodos que Retornam Valores. ....................................................................... 49 8.2- Sobrecarga de Métodos ..................................................................................... 49 8.3- Exercícios Propostos ......................................................................................... 51 9- ENCAPSULANDO MÉTODOS E ATRIBUTOS ..................................................... 53 9.2- Método Construtor ............................................................................................. 56 9.3- Exercícios Propostos ......................................................................................... 57 10- HERANÇA ......................................................................................................... 58 10.1- Extends e Super .............................................................................................. 58 10.2- Exercícios Propostos ....................................................................................... 60 11- LISTAS LINEARES ................................................................................................ 61 11.1- Listas Genéricas .............................................................................................. 61 11.1.1- Operações sobre Listas ............................................................................ 62 11.2- Filas ................................................................................................................. 63 11.3- Pilhas ............................................................................................................... 66 11.4- Exercícios Propostos ....................................................................................... 69 Bibliografia .................................................................................................................... 70 4 ESTRURA DE DADOS Ementa da Disciplina Matriz e Vetor. Tipos abstratos de dados. Estudo das estruturas de dados, conceitos, operações, representações e manipulação de dados estruturados na forma de vetores, matrizes, pilhas, filas. Estudo da alocação seqüencial e ligada Objetivos • Introduzir estrutura de dados fundamentais, tais como: pilhas, filas, árvores e grafos. • Exercitar suas respectivas operações básicas, para o entendimento de sua manipulação nos dados. • Desenvolver o raciocínio para a utilização das estruturas de dados estudadas na implementação de soluções de problemas. Conteúdo Programático Tiposde Dados • Tipos Primitivos • Tipos Construídos • Tipos Abstratos de Dados (TAD) Matrizes • Vetores • Caso Geral 5 • Matrizes Especiais • Matrizes Esparsas Tipos Abstratos de Dados • Conceituação • Classes e Objetos Listas: Filas e Pilhas • Conceituação • Realizações de Fila • Realizações de Pilhas • Aplicações de Pilhas e Filas 6 1- CONCEITOS BÁSICOS O que é um problema? Problemas fazem parte do nosso cotidiano como, por exemplo, trocar o pneu furado de um carro ou definir onde Almoçar. Sempre que nos deparamos com um problema buscamos um procedimento para solucionar o mesmo. O uso da lógica é primordial na solução de problemas. Com ela é possível alcançar objetivos com eficiência e eficácia. Lógica é o ramo da Filosofia e da Matemática que estuda os métodos e princípios que permitem fazer distinção entre raciocínios válidos e não válidos, determinando o processo que leva ao conhecimento verdadeiro. Com a utilização dos computadores, foi preciso criar programas através dos algoritmos. E o que vem a ser o algoritmo? É uma palavra estranha com designação desconhecida, no entanto, fazemos uso constante de algoritmos em nosso cotidiano. Um algoritmo é um conjunto ordenado de passos executáveis não ambíguos, definindo um processo que tem um término. 1.1- Conceitos inter-relacionados Descrição de um conjunto de comandos que, obedecidos, resultam numa sucessão finita de ações. Ação – Acontecimento que, a partir de um estado inicial, após um período de tempo finito, produz um estado final previsível e bem definido. Algoritmo – Abstrato e distinto de sua representação. Programa – É uma das possíveis representações do algoritmo. 7 Processo – A atividade de executar um algoritmo. 1.2- Programação Java A programação java permite a criação de programas através de uma linguagem interpretada e robusta. Linguagem interpretada é uma linguagem de programação, onde o código fonte nessa linguagem é executado por um programa de computador chamado interpretador, que em seguida é executado pelo sistema operacional ou processador. Mesmo que um código em uma linguagem passe pelo processo de compilação, a linguagem pode ser considerada interpretada, se o programa resultante não for executado diretamente pelo sistema operacional ou processador. No caso do Java, é necessário instalar a máquina virtual Java que fará o papel do interpretador da linguagem. Utilizaremos aqui o ambiente de criação (IDE) NetBeans. 1.3- Programando em Java Para iniciar a programação em Java é necessário compreender o cabeçalho e o ambiente a ser trabalhado, importando classes para que estas possam ser utilizadas livremente. Existem diversas classes no Java que permitem a leitura de dados vindos do teclado e a partir do Java 5 a classe java.util.Scanner forneceu uma facilidade nesse quesito. A criação de variáveis é também muito importante, uma vez que esta amazenará temporariamente todo um conteúdo designado. Podem ser classificadas em tipos primitivos e abstratos. Inicialmente trataremos apenas os tipos primitivos. 8 Numéricas: int – variáveis do tipo inteiro float – variáveis do tipo ponto flutuante utilizada para pequenos valores decimais. double – variável para grande valores decimais. Literais: char – Compreende-se como um vetor de caractere, armazenando um caracter qualquer. String – É um tipo composto, formado por cadeia de caracteres. Booleano: As variáveis booleanas não são necessariamente declaradas. São apenas a resposta de comprações tento seu resultado como verdadeiro ou falso. Os nomes das variáveis fica a critério do programador, no entanto, estes nomes devem obedecer algumas regras: a) Não podem iniciar com números; b) Não podem conter caracteres especiais; c) Não pode ter espaços; d) Não podem ser palavras reservadas ou palavras chaves. Obedecendo a estes quatro critérios, a variável poderá ser criada e utilizada. Uma observação importante é que na programação, o “_” (underline) é considerado letra, e sua utilização é livre. 9 2- Tipos de Dados Os dados manipulados por um algoritmo podem possuir natureza distinta, isto e, podem ser numeros, letras, frases, etc. Dependendo da natureza de um dado, algumas operacoes podem ou nao fazer sentido quando aplicadas a eles. Por exemplo, nao faz sentido falar em somar duas letras. Para poder distinguir dados de naturezas distintas e saber quais operacoes podem ser realizadas com eles, os algoritmos lidam com o conceito de tipo de dados. O tipo de um dado define o conjunto de valores ao qual o valor do dado pertence, bem como o conjunto de todas as operações que podem atuar sobre qualquer valor daquele conjunto de valores. Por exemplo, o tipo de dados numérico pode ser imaginado como o conjunto de todos os números e de todas as operações que podem ser aplicadas aos números. Define a forma como um dado deve ser armazenado ou recuperado, bem como os possíveis valores que ele pode assumir e as operações que podem ser efetuadas sobre os mesmos. Exemplo em Pascal: integer - permite valores inteiros e operações de adição, multiplicação, subtração e divisão; string - permite valores literais e operações de concatenação; Obs. Esses tipos estão intrinsecamente relacionados com o hardware. Os tipos de dados manipulados por um algoritmo podem ser classificados em dois grupos: atômicos e complexos. 10 Os tipos atômicos são aqueles cujos elementos do conjunto de valores são indivisíveis. Por exemplo, o tipo numérico é atômico, pois os números não são compostos de partes. Por outro lado, os tipos complexos são aqueles cujos elementos do conjunto de valores podem ser decompostos em partes mais simples. Por exemplo, o tipo cadeia é aquele cujos elementos do conjunto de valores são frases e frases podem ser decompostas em caracteres, os quais são indivisíveis. Tipos de Dados Um tipo de dado consiste em: Um conjunto de valores (domínio) Um conjunto de operações Exemplo: O tipo de dado número inteiro, que aparece em várias linguagens de programação. Os valores que este tipo de dado pode assumir são: ...-2,-1,0,1,2,...; as operações são muitas, dentre elas estão +,*,mod,etc. Podemos dividir os tipos de dados em: Elementares (Atômicos) Estruturados (Complexos) Tipo de Dados Elementares Os tipos de dados elementares são definidos de forma que não existe uma estrutura sobre seus valores. Exemplos: Os tipos inteiros, caracteres, booleanos, etc, são exemplos de tipos elementares. Tipo de Dados Estruturados Nos tipos de dados estruturados existe uma relação estrutural entre seus valores. Esta relação estrutural entre os valores será estudada posteriormente e podem ser classificadas como linear e não linear. 11 Exemplo: Um exemplo de tipo linear de dados são os vetores, presentes em muitas linguagens de programação. Os tipos de dados elementares são caracterizados pelo fato que seus valores são atômicos, isto é, não admitem decomposição. Os tipos de dados numérico, caracter e lógico estão entre os tipos de dados elementares suportados pela maioria das linguagens de programação. Entretanto, se os valores de um tipo de dados admitem decomposição em valores mais simples, então o tipo de dados é dito complexo ou estruturado, ao invés de elementar, e a organização de cada componente e as relações entre eles constitui o que chamamos de estrutura de dados. 12 3- DIVISÕES BÁSICAS DA PROGRAMAÇÃO 3.1- Programação Sequencial Tem-se pelo inicio, seguindo instruções e término. É Também chamada de programação Top Down, executada sequencialmente, da primeira à última linha de código, seguindo-se rigorosamente a ordem em que foi escrito o programa. Segue abaixo um fluxograma simplespara maior compreendimento: Apesar da simplicidade simplicidade de sua forma, a programação sequencial é muito utilizada em linguagens para Banco de Dados e em alguns circuitos integrados. Início Instruções Término 13 Exemplo em Java: import java.util.Scanner; public class sequencial { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x; System.out.print(“Digite um número: "); x=sc.nextInt(); System.out.println(“Número: "+x); } } Inicio – Cabeçalho Java import java.util.Scanner; public class sequencial { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Instruções int x; System.out.print(“Digite um número: "); x=sc.nextInt(); System.out.println(“Número: "+x); Término } } 14 3.1.1- Operadores Aritméticos 3.1.2- Exercícios resolvidos: 1.1. Leia um nome qualquer e imprima uma mensagem de boas vindas com este nome. import java.util.Scanner; public class Nomes { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String nome; System.out.print("Digite um nome qualquer: "); nome=sc.next (); System.out.println("Bem vindo, "+ nome+"!!"); } } 1.2. Leia três valores quaisquer e imprima a soma destes. import java.util.Scanner; public class soma { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double x,y,z,Resp; System.out.print("Digite três números: "); x=sc.nextDouble(); y=sc.nextDouble(); z=sc.nextDouble(); Resp = x+y+z; System.out.println("Somatório dos Números: "+ Resp); } } 15 3.1.3- Exercícios propostos: 1.3. Leia o primeiro nome e a idade de uma pessoa e informe seu nome e seu possível ano de nascimento. 1.4. Ler a massa e a aceleração de um corpo qualquer e escrever qual a força deste corpo através da fórmula F=m*a. 1.5. Ler o salário de um funcionário e imprimi-lo com um aumento de 15%. 1.6. Ler um valor real e escrever apenas a parte decimal deste número lido. 16 3.2- Programação Condicional Este tipo de programação (também chamada de expressão condicional ou ainda construção condicional) basea-se em uma estrutura de desvio do fluxo de controle presente em linguagens de programação. Estas operações realizam diferentes ações dependendo da seleção (ou condição) ser verdadeira ou falsa. O resultado da expressão processada é transformada em um valor booleano. Segue abaixo um fluxograma simples para maior compreendimento: Em java, teremos as estruturas: if (condição) – Caso a condição seja satisfeita, executar-se-á todas instruções dentro deste laço. else – as instruções deste laço somente serão executadas caso a condição if anterior não seja satisfeita. Quando o interpretador encontra o identificador "if", ele espera em seguida uma condição booleana sob forma de expressão relacional (ex.: "x > 7"), podendo ser verdadeira ou falsa. Se a condição é verdadeira, é executado a primeira instrução logo abaixo do “if”. Caso contrário, a instrução logo abaixo do “else” é Início Instruções Término Instruções condição Instruções 17 executado. Em ambos os casos, para ser executado mais de uma instrução, é necessário o uso de chaves “{ }” indicando blocos de intruções e após a execução destes blocos, o fluxo do programa é retornado ao final da última estrutura de controle. O bloco condicional "else" é opcional e pode ser omitido. Caso omitido, a estrutura é chamada de seleção simples, caso contrário é chamada seleção composta. Existe ainda o método condicional encadeado, que após a estrutura else inicia-se um novo método if. É sempre importante estruturar o código, identando e organizando, para que seja obtido um resultado satisfatório e de fácil compreensão. Exemplo em Java: import java.util.Scanner; public class condicional { public static void main(String[] args) { Scanner sc = new Scanner (System.in); int x; System.out.print(“Digite um número: "); x=sc.nextInt(); if (x<=10 && x>=0) System.out.println(“Número está entre 0 a 10"); else System.out.println(“Erro"); } } O exemplo mostrado acima faz uma leitura de um número qualquer e verifica se este número está entre 0 e 10. 18 3.2.1- Operadores Relacionais 3.2.2- Operadores Relacionais 3.2.3- Exercícios resolvidos: 2.1. Leia um número inteiro qualquer e imprima uma mensagem de erro caso ele seja negativo. import java.util.Scanner; public class negativo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num; System.out.print("Digite um número qualquer: "); num=sc.nextInt(); if (num<0) System.out.println("Erro!!! "); } } 19 2.2. Leia três valores quaisquer e mostre o resultado da soma apenas se ultrapassar 100, caso contrário mostre apenas uma mensagem simples. import java.util.Scanner; public class soma2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double x,y,z,resp; System.out.print("Digite três números: "); x=sc.nextDouble(); y=sc.nextDouble(); z=sc.nextDouble(); resp = x+y+z; if (resp > 100) System.out.println("Somatório igual a "+ Resp); else System.out.println("Somatório menor que 100"); } } 3.2.2- Exercícios propostos: 2.3. Ler duas idades e escrever qual delas é a maior. 2.4. Entrar com um valor inteiro e dizer a qual mês do ano pertence. Faça as devidas validações caso o usuário não digitar um mês válido. 2.5. Ler duas notas fazer a média destas e escrever se o aluno foi aprovado ou reprovado (média de aprovação igual ou maior que 7). 2.6. Ler 3 lados do triângulo e dizer se este existe e se ele é escaleno, equilátero ou isóceles. 2.7. Leia um ponto qualquer com as coordenadas (x,y) de um plano cartesiano e dizer em qual quadrante ele está situado, se está em um dos eixos ou localizado na origem. 2.8. Construa um programa para calcular as raízes de uma equação do 2º grau a partir dos seus coeficientes A, B e C. Lembre-se da possibilidade de raízes iguais e de não haves raízes real. 20 3.3- Programação com Repetição Basea-se em uma estrutura de desvio do fluxo de controle presente em linguagens de programação que realiza e/ou repete diferentes ações dependendo se uma condição é verdadeira ou falsa, em que a expressão é processada e transformada em um valor booleano. Estão associados a uma estrutura de repetição uma condição (também chamada "expressão de controle" ou "condição de parada") e um bloco de código: verifica-se a condição, e caso seja verdadeira, a instrução logo abaixo da estrutura é executada. Após o final da execução desta instrução, a condição é verificada novamente, e caso ela ainda seja verdadeira, a intrução é executada novamente. Da mesma forma que na estrutura condicional, é possível executar mais de uma instrução, sendo necessário necessário o uso de chaves “{ }” indicando blocos de intruções. Deve-se observar que, caso o bloco de código nunca modificar o estado da condição, a estrutura será executada para sempre, uma situação chamada laço infinito (loop infinito). Da mesma forma, é possível especificar uma estrutura em que o bloco de código modifica o estado da condição, mas esta é sempre verdadeira. 3.3.1- Repetição pré-testadaWhile (condição) – laço para repetições diversas, seja determinada ou indeterminada. Sairá do laço quando a condição for falsa. Este tipo de repetição é chamada de enquanto, pois executará enquanto a condição for verdadeira. É a estrutura de repetição mais difundida. 21 Exemplo em Java: import java.util.Scanner; public class repete1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a=0; while (a!=3345) { System.out.print("Digite a senha: "); a=sc.nextInt(); if( a!=3345) System.out.println("Erro! "); } System.out.println("Senha Correta"); } } O exemplo mostrado acima executará indeterminadamente enquanto a variável de controle “a” for diferente da senha 3345. Este tipo de programa é chamado de sentinela, pois o programa ficará a espera de um valor para terminar o ciclo de repetição. A repetição pré-testada pode ser utilizada de várias maneiras, no entanto, sua utilização é mais recomendada para casos de programação sentinela. 3.3.2- Repetição pós-testada Do – While (condição); - basea-se em uma variação da construção while, no entanto repetirá obrigatoriamente pelo menos uma vez. A verificação da condição é feita após uma execução do bloco. Nesta estrutura, o bloco de código é primeiramente executado, e então a condição é verificada, e se for verdadeira o bloco é executado novamente. Não é uma estrutura muito usual. 22 Exemplo em Java: import java.util.Scanner; public class repete2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a,r=0; do { System.out.print("Digite um número: "); a=sc.nextInt(); r+=a; } while (r < 3345); System.out.println("Valor Total: "+r); } } É importante perceber que, diferente da estrutura de repetição while, o “do – while” leva ponto e vírgula ao final de sua estrutura. Neste exemplo, as instruções são repetidas até a soma da variável de controle ‘r’, obtida pela variável digitada ‘a’, ser maior que 3345. Não existem recomendações ao uso da repetição pós-testada, uma vez que se trata apenas de uma variação da estrura while. 3.3.3- Repetição com varíavel de controle Representa uma estrutura de repetição que designa uma variável de controle para cada iteração do bloco, e uma operação de passo a cada iteração. For (inicialização ; condição ; incrementação) – laço de repetição ideal quando se sabe quantas vezes se pretende repetir. Sairá do laço quando a condição for verdadeira Esta estrutura é bastante utilizada para a iteração de vetores, em que cada iteração representa um índice do vetor. Nesse caso, para vetores multidimensionais é possível aninhar este tipo de construção para as diversas dimensões associadas. 23 Exemplo em Java: import java.util.Scanner; public class repete3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n; System.out.print("Digite um número maior que zero: "); n=sc.nextInt(); for(int i=0; i <= n ; i++) System.out.println("Número "+i); } } Para este exemplo podemos perceber a variável auxiliar i que será incrementada até atingir o valor n (lida pelo usuário). O programa imprimirá todos os valores inteiros de 0 a n. 24 3.3.4- Exercícios resolvidos 3.1. Leia 50 valores diferentes e imprima o maior. import java.util.Scanner; public class maior50 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num,maior; System.out.print("Digite um número qualquer: "); maior=sc.nextInt(); for (int i=0;i<49;i++) { System.out.print("Digite um número qualquer: "); num=sc.nextInt(); if (num>maior) maior=num; } System.out.print("Maior: "+maior); } } 3.2. Faça o somatório dos números impares de 0 a 150. public class somaimpares { public static void main(String[] args) { int x=0; for (int i=1;i<150; i+=2) x+=i; System.out.println("Total: "+x); } } 3.3.5- Exercícios propostos: 3.3. Imprimir os números pares de 10 a 100. 3.4. Imprimir a sequência: 11, 21, 31... 101. 3.5. Ler 10 números reais e imprimir o maior. 3.6. Ler 10 números e exibir a soma dos impares. 3.7. Ler 10 números e exibir a soma dos múltiplos de 5. 25 3.8. Ler diversos números e exibir quantos foram digitados. O valor -1 será a condição de parada. 3.9. Fazer um algoritmo que imprima a seguinte soma: 3.10. Ler um somatório de números inteiros que irá parar ao ser digitado o número 0 e calcular a média destes números digitados. 3.11. Leia o sexo e a altura de várias pessoas (parando ao encontrar uma altura zero), calcule a média das alturas dos homens e das mulheres, escrever a quantidade de homens e mulheres e qual o grupo é o mais alto. 3.12. A prefeitura de Aparecida de Goiânia fez uma pesquisa entre seus habitantes, coletando dados sobre salário e número de filhos de cada chefe de família. A prefeitura deseja saber: a) Média do salário da população b) Média do número de filhos c) Maior salário d) Percentual de pessoas com salário de até R$450,00 O final da leitura será dado por um salário negativo. 26 4- VETORES Um vetor (Array unidimensional) é um tipo estruturado que pode agrupar numa mesma variável um conjunto finito de valores todos do mesmo tipo. Um vetor é um conjunto de elementos representados por um identificador e um único índice. Cada elemento tem uma única dimensão. O índice varia entre um limite inferior e um limite superior, em correspondência com o número de elementos do conjunto. Os vetores são colocados na memória em posições ordenadas e adjacentes. Um Vetor é uma estrutura de dados que armazena uma sequência de objetos todos do mesmo tipo, em posição consecutivas de memória. Algoritmos de encontrar uma posição de um elemento armazenado no vetor, ou inserir um novo elemento ou alterar um dado elemento são os algoritmos que são trabalhados nesta seção. Os elementos de um vetor estão armazenados em uma posição p do vetor dependendo da linguagem e como o vetor foi mapeado. Em Java, as posições de um vetor variam de [0.a.n-1] para um vetor de n posições. 4.1- Declaração de um vetor Imagine que temos uma longa lista de números armazenada num vetor v. O espaço reservado para o vetor pode ter sido criado pela declaração: int v[ ]; v = new int [N]; Sendo N uma constante (possivelmente definida por uma instrução anterior). 27 4.2- Realização de busca em um vetor Dado um inteiro x e um vetor de inteiros v[0..n-1], considere o problema de encontrar um índice k tal que v[k]=x. O problema faz sentido com qualquer n>=0. Se n=0, o vetor é vazio e portanto essa instância do problema não tem solução. Para evitar que o sistema termine sem encontrar o elemento desejado, usaremos a convenção de devolver -1 nesse caso, já que -1 não é um índice válido do vetor. Exemplo em Java: Faça um algoritmo que busca em um dado vetor numérico, um elemento x. ... //dado o vetor v[ ], basta realizar os seguintes procedimentos: int k; k=n-1; while (k>=0 && v[k] != x) k = k-1; ... Neste exemplo, temos em x o valor a ser pesquisado, k será a posição pretendida de x e n o tamanho máximo do vetor. Outros exemplos da utilização de vetor: tipo frase (char): caracter[0..80] char caracter [ ]; caracter =new char [80]; valor: real[1..10] double [ ] real=new double [10]; Lembre-se que o espaço de armazenamento de um vetoré reservado no momento de sua declaração. Deve ser especificado o tamanho máximo de elementos a serem armazenados; Deve ser especificado o tipo dos elementos do conjunto. 28 Lembrar que o primeiro elemento estará armazenado na posição zero do vetor. As posições x devem ser equivalente a posição x-1 no vetor. Exemplo: int x[ ]; x = new int [400]; 4.3- Exercício resolvido 1- Leia um valor inteiro e a partir deste valor crie um vetor com o tamanho deste valor e faça-o receber valores de 10 em 10 iniciando em 10. import java.util.Scanner; public class vetor1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int v[],pos; System.out.println("Digite um numero maior que zero: "); pos=sc.nextInt(); v = new int [pos]; for(int i=0;i<pos;i++) v[i]=i*10+10; for(int i=0;i<pos;i++) System.out.println("Posicao "+i+": "+v[i]); } } 4.4- Exercícios propostos: 2- Faça um programa para gerar um vetor de 30 posições, onde cada elemento corresponde ao quadrado de sua posição. Mostre o vetor resultante. 3- Ler 15 valores reais em um vetor e imprimir os números localizados nas posições impares. 29 4- Desenvolver um programa para ler um vetor VAL de números inteiros e criar outro vetor VAL2 de mesma quantidade de elementos que VAL, onde os elementos tenham o dobro do valor dos elementos de VAL. O número máximo de elementos é 30. 5- Escreva um algoritmo que recebe um inteiro 0 < n ≤ 100 e um vetor de n números inteiros cuja primeira posição é 1 e inverte a ordem dos elementos do vetor sem usar outro vetor. 6- Leia um vetor de 15 posições e reescreva-o de trás pra frente mostrando apenas as posições impares. 7- Em uma sala com N alunos, faça um programa que informe a maior e a segunda maior nota. 30 5- MATRIZES Uma matriz (Array multidimensional) e um tipo estruturado que pode agrupar numa mesma variavel um conjunto finito de valores todos do mesmo tipo. O vetor e um caso de matriz unidimensional, cujos elementos estao armazenados em um espaco cujos indices sao limitados. Uma matriz e um conjunto de elementos representados por um identificador e dois indices. Da mesma forma do que os vetores, os dois indices varia entre um limite inferior e um limite superior, em correspondencia com o numero de elementos do conjunto. Toda matriz pertence são tipos compostos de dados, ou seja, conjunto de vários elementos de mesmo tipo. Deve possuir um único nome. Ex: M E possuem apenas um tipo. Ex: M:inteiro Declaração: int M[ ] [ ]; M = new int [3] [4]; Representação: 10 8 5 1 M = 5 7 7 7 8 0 0 10 Armazenamento em seqüência para cada dimensão. Ex.: M[3][4]; (3 linhas e 4 colunas). Possui apenas um índice. Acesso direto: M[i][j] Para este caso, escolhendo i = 2 e j = 3, estamos escolhendo segunda linha e terceira coluna, ou seja, o valor será 7. 31 A figura abaixo mostra graficamente o acesso a segunda linha e terceira coluna para uma matriz 3x4. Em Java, o índice da matriz começará sempre de zero. Sendo que para o caso citado acima, M[1][2] indicará a segunda linha e terceira coluna com o valor 7. 5.1- Exercícios resolvidos 1. Faça um algoritmo que leia uma matriz 3x3 e imprima todo seu conteúdo conforme sua representação. import java.util.Scanner; public class mat1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int b[][]; b=new int[3][3]; //leitura for(int i=0;i<3;i++)//referente a linha for(int j=0;j<3;j++)/*referente a coluna*/{ System.out.print("Digite o valor "+i+" "+j+": "); b[i][j]=sc.nextInt(); } //escrita for(int i=0;i<3;i++){ System.out.println(); for(int j=0;j<3;j++) { System.out.print(b[i][j]+" "); } } } } 32 2. Faça um algoritmo para ler as 5 notas dos alunos de uma turma, armazená-las numa matriz e calcular suas médias finais. import java.util.Scanner; public class Notas { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double soma, media, matriz[][]; int num; System.out.print("Digite a qtd de alunos: "); num=sc.nextInt(); matriz=new double[num][5]; for (int i=0;i<num;i++) for (int j=0;j<5;j++){ System.out.print("Digite a nota "+(j+1)+ " do aluno "+(i+1)+": "); matriz[i][j]=sc.nextDouble(); } for (int i=0;i<num;i++) { soma=0; for (int j=0;j<5;j++) soma+=matriz[i][j]; media=soma/5; System.out.println("Aluno "+(i+1)+": "+media); } } } 5.2- Exercícios propostos 3- Leia uma matriz real 3x4 e depois exiba o elemento do canto superior esquerdo e o do canto inferior direito. 4- Ler uma matriz 5x5 e gerar outra em que cada elemento é o cubo do elemento respectivo na matriz original. Imprima as duas matrizes. 5- Leia uma matriz 3x3 e imprima a soma dos valores da diagonal principal. 6- Faça um programa para criar e exibir a matriz identidade NxN. 33 7- Ler uma matriz A de dimensão N x N e verificar se a matriz é simétrica. Uma matriz é simétrica caso coincidir com a sua transposta, ou seja, se A = AT e a matriz transposta é o resultado da troca de linhas por colunas em uma determinada matriz. Ex.: 8- Um aluno possui 4 notas em cada uma das 5 disciplinas que cursa na faculdade. Faça um programa que leia as notas do aluno, e indicar a mais alta. Deve ser exibido também a matriz de notas deste aluno. 34 6- TIPOS ESPECIAIS DE MATRIZ Uma matriz é especial quando a maioria de seus elementos é igual a zero ou a um valor constante. Nesse caso ocorre um despedício de espaço na alocação da memória. Existem várias soluções para resolver este desperdício. Os tipos de matrizes especiais são: Matrizes Diagonais; Matrizes Triangulares; Matrizes Simétricas e Anti-Simétricas; Matrizes Esparsas; 6.1- Matrizes Diagonais Apenas os elementos da diagonal principal ou secundaria sao significativos. Os demais elementos sao iguai a uma constante. Uma forma de evitar o desperdicio de espaco, nesse caso, e representar a matriz por meio de um vetor V[1..L], com L o numero de linhas da matriz. O Tipo Abstrato de Dados da matriz_diagonal fará uso de vetor para representar a matriz e deve fornecer métodos que convertam o acesso a diagonal da matriz ao acesso real no vetor. Exemplo: representar a matriz 4x4 em um vetor contendo os elementos da diagonal principal. 35 6.2- Matrizes Triangulares Apenas os elementos da diagonal principal ou secundária e os abaixo (ou acima) tem valor diferente de constante ou zero. Neste casos, também pode-se somente armazenar os valores significativos em um vetor. Para uma matriz triangular inferior a função de mapeamento é: M[i, j] = v [j + i * (i-1)/2] Pode-se utilizar a mesma definição de tipo do TAD matriz_diagonal, alterando somente o tamanho do vetor que, neste caso, é nlinhas +(nlinhas*(ncolunas-1))/2. 6.3- Matrizes Simétricas e Anti-Simétricas Uma matriz é simétrica quando M[i,j]=M[j,i]. E anti-simétrica quando M[i,j]=-M[j,i]. Nesse caso, utiliza-se a mesma forma de armazenamento das matrizes triangulares, sem o campo referente a constante. Ignora-se os campos iguais e utiliza a forma M[i, j] = v [j + i * (i-1)/2] em sua recontituição. 36 6.4- MatrizesEsparsas A maioria dos elementos da matriz são iguais a zero. Em geral, apenas 30% dos valores são significativos. Neste caso, também é aconselhado o uso de uma representação alternativa. Para maior esclarecimento, tomaremos uma matriz 700x900. 700x900 = 630.000 elementos Considerando esta Matriz como esparsa com apenas 9 elementos não nulos, sua representação seria facil, no entanto o armazenamento seria prejudicial para qualquer máquina. 37 Soluções propostas: 1º Caso - Uso da matriz tradicional Vantagem Ao se representar dessa forma, preserva-se o acesso direto a cada elemento da matriz. Algoritmos simples. Desvantagem Muito espaço para armazenar zeros. Inviável para matrizes esparsas de ordem elevada. 2º Caso - Representação por linhas Listas simples encadeadas: elementos não nulos 9 inteiros x 4 nós com 3 inteiros cada + 3 ponteiros Desvantagens Perda da natureza bidimensional de matriz Acesso ineficiente à linha Para acessar o elemento na i-ésima linha, deve-se atravessar as i-1 linhas anteriores Acesso Ineficiente à coluna Para acessar os elementos na j-ésima coluna, deve-se atravessar toda lista Questão Como organizar esta lista, preservando a natureza bidimensional de matriz? 38 Deve haver também um balanço entre o espaço gasto pela matriz tradicional e a ED em lista (deve valer a pena)! 3º Caso - Listas cruzadas Para cada matriz, usam-se várias matrizes representando um nó que indicará o elemento em questão. Pode-se utilizar ainda dois vetores com N ponteiros para as linhas M ponteiros para as colunas. Cada elemento não nulo é mantido simultaneamente em duas listas Uma para sua linha. Uma para sua coluna. 39 7- TIPOS ABSTRATO DE DADO A ideia de tipo abstrato de dados e desvincular o tipo de dado (valores e operacoes) de sua implementacao. Algumas vantagens desta desvinculacao sao: 1.Integridade dos dados 2.Facilidade de manutencao 3.Reutilizacao Um tipo abstrato de dados pode ser definido matematicamente pelo par (V,O) onde V e um conjunto de valores e O um conjunto de operacoes sobre estes valores. Um tipo abstrato de dados (TAD) é a especificação matemática de um conjunto de dados e das operações que podem ser executadas sobre esses dados. O conceito de tipo de dado abstrato é dissociado do hardware. TAD define o que cada operação faz, mas não como faz. Assim, um mesmo tipo abstrato de dados pode ser concretizado (ou implementado) de diversas formas. TADs são materializados pelas estruturas de dados. Lista Encadeada (implementação com referências) Lista com alocação estática (implementação usando array) Estruturas de dados são formas genéricas de se estruturar informação de modo a serem registradas e processadas pelo computador. Contudo, estas só adquirem significado quando associadas a um conjunto de operações, que visam, de um modo geral, manipulá-las (algoritmos). Observação: Um tipo abstrato de dados está desvinculado de sua implementação, ou seja, quando definimos um tipo abstrato 40 de dados estamos preocupados com o que ele faz e não como ele faz. Em geral, quando usamos o conceito de tipo abstrato de dados, dividimos a programação em duas etapas: Aplicação Implementação Na aplicação, apenas as operações definidas abstratamente são utilizadas, não sendo permitido o acesso direto aos dados, ou seja, o usuário só tem acesso as operações. Exemplo: Suponha que estamos trabalhando com listas de números inteiros e apenas as operações de inclusão e busca estão presentes. Neste tipo abstrato de dados o usuário nunca poderia trocar a posição de dois elementos na lista, pois a ele só é permitido inserir ou procurar por um elemento. As características da implementação permanecem inacessíveis, ou seja, o usuário não consegue saber por exemplo se a lista é dinâmica ou estática. TAD é um conjunto de valores e uma sequência de operações esses valores. Vimos várias características típica de TADs: A manipulação do dado se faz unicamente através das operações definidas para ele. Não é preciso saber a forma exata de implementação do tipo ou de suas operações para conseguir utilizá-los, neste caso não precisamos nos preocupar com a eficiência de tempo e espaço. A definição é independente da implementação, podendo ser alterada sem que o uso se altere. A aplicação não precisa (e não deve) ter acesso à forma de implementação. 41 Portanto, somente após a definição estar completa é que devemos começar a pensar na implementação exata do tipo e suas operações. Veja que, no exemplo, até mesmo a aplicação pode ser definida e um algoritmo para ela escrito sem que se tivesse conhecimento da forma da implementação. Linguagens de programação admitem que você, de alguma forma, expresse essa independência, separando definições de implementações. Existem vários métodos para especificar um TAD. O método que usamos é semi-formal e faz uso intensivo da notação em Java, porem estende essa notação onde necessário. No caso de Java, usaremos o conceito de classes e objetos (definida no inicio do programa) permitindo que você expresse isso, mas exige que se revele a estrutura interna do dado na seção de interface. 7.1- Classes e Objetos Uma classe é um tipo definido pelo usuário que contém o molde, a especificação para os objetos, algo mais ou menos como o tipo inteiro contém o molde para as variáveis declaradas como inteiros. A classe envolve, associa, funções e dados, controlando o acesso a estes, definí-la implica em especificar os seus atributos (dados) e seus métodos (funções). Um programa que utiliza uma interface controladora de um motor elétrico provavelmente definiria a classe motor. Os atributos desta classe seriam: temperatura, velocidade, tensão aplicada. Estes provavelmente seriam representados na classe por tipos como int ou float. Os métodos desta classe seriam funções para alterar a velocidade, ler a temperatura, etc. Um programa editor de textos definiria a classe parágrafo que teria como um de seus atributos uma String ou um vetor de Strings, e como métodos, funções que operam sobre estas strings. 42 Quando um novo parágrafo é digitado no texto, o editor cria a partir da classe Parágrafo um objeto contendo as informações particulares do novo texto. Isto se chama instanciação ou criação do objeto. 7.2- Especificando uma Classe Suponha um programa que controla um motor elétrico através de uma saída serial. A velocidade do motor é proporcional a tensão aplicada e esta proporcional aos bits que vão para saída serial e passam por um conversor digital analógico. Vamos abstrair todos estes detalhes por enquanto e modelar somente a interface do motor como uma classe, a pergunta é que métodos e que atributos deve ter nossa classe, que argumentos e valores de retorno devem ter os métodos? Representação da velocidade: A velocidade do motor será representada por um atributo inteiro (int). Usaremos a faixa de bits que precisarmos, caso o valor de bits necessário não possa ser fornecido pelo tipo , usaremos então o tipo long, isto depende do conversor digital analógico utilizado. Representação da saída serial: O motor precisa conhecer a sua saída serial, a sua ligação com o "motor do mundo real". Suponha uma representação em hexadecimal do atributo endereço de porta serial, um possível nome para o atributo: enderecomotor. Não se preocupe em saber como usar a representação hexadecimal. Alteração do valor da velocidade: Internamente o usuário da classe motor pode desejar alterar a velocidade, cria-se então o método: public void altera_velocidade(int novav);. O código anterior corresponde ao cabeçalho do método ele é definido junto com a classe motor, associado a ela. O valor de retorno da função que "implementa" ométodo é void, poderia ser criado um valor de retorno (boolean) que 43 indicasse se o valor de velocidade era permitido e foi alterado ou não era permitido e portanto não foi alterado. O ato de invocar um método também é chamado de passar uma mensagem para o objeto que está executando este método. Não faz sentido usar, chamar, este método separado de uma variável do tipo motor, mas então porque na lista de argumentos da função não se encontra um motor? Este pensamento reflete a maneira de associar dados e código (funções) das linguagens procedurais. Em linguagens orientadas a objetos o código e os dados são ligados de forma diferente, a própria declaração de um tipo definido pelo usuário já engloba as declarações das funções inerentes a este tipo, isto será explicado em 1.2. O objeto ao qual é aplicado o método é passado de outra forma. Note que não fornecemos o código do método, isto não é importante, por hora a preocupação é com a interface definida pela classe: seus cabeçalhos de métodos e atributos. Apenas pense que sua interface deve ser flexível de modo a não apresentar entraves para a criação do código que seria feita numa outra etapa. Nesta etapa teríamos que imaginar que o valor numérico da velocidade deve ir para o conversor onde irá se transformar numa diferença de potencial a ser aplicada nos terminais do motor, etc. Um diagrama simplificado da classe motor com os atributos e métodos: Motor public int velocidade; public int endereco; public void altera_velocidade (int novav) 7.3- Objetos em Java Objetos são instâncias de uma classe. Quando um objeto é criado ele precisa ser inicializado, ou seja para uma única classe de nome EstudanteDeGraduacao podemos ter vários objetos durante a execução de um programa. 44 Estudante de graduação Andre; Identificação 940718; Curso Computacao | Estudante de graduação Luiza , Identificação 893249, Curso Medicina... A classe representa somente o molde para a criação dos objetos, estes sim contém informação, veja tópico classes e objetos. O atributo Identificação tem valor 940718 para a instância (objeto) André da classe Estudantes de Graduação. INSTANCIAS: Um objeto existente durante um momento da execução de um programa é uma instancia de uma classe. Uma classe e suas instancias: Cada estudante (ou instancia) poderia ser modelado, desenhado como: Para o estudo das classes e objetos, torna-se importante entender alguns atributos e palavras reservadas: Class é a palavra reservada que marca o inicio da declaração de uma classe. Public é um especificador, por enquanto guarde public class como o início da declaração de uma classe. É um qualificador do método que indica que este é acessível externamente a esta classe (para outras classes que eventualmente seriam criadas), não se preocupe com ele agora, apenas declare todos os métodos como public. 45 Static é um outro qualificador ou "specifier", que indica que o método deve ser compartilhado por todos os objetos que são criados a partir desta classe. Os métodos static podem ser invocados, mesmo quando não foi criado nenhum objeto para a classe, para tal deve-se seguir a sintaxe: <NomeClasse>.<NomemetodoStatic>(argumentos);. Void é o valor de retorno da função, quando a função não retorna nenhum valor ela retorna void, uma espécie de valor vazio que tem que ser especificado. Main é um nome particular de método que indica para o compilador o início do programa, é dentro deste método e através das iterações entre os atributos, variáveis e argumentos visíveis nele que o programa se desenvolve. (String args[]) - É o argumento de main e por consequência do programa todo, ele é um vetor de Strings que é formado quando são passados ou não argumentos através da invocação do nome do programa na linha de comando do sistema operacional. 7.4- Atributos e Métodos Veja um exemplo abaixo para uma classe círculo: //Classe circulo, arquivo Circulo.Java public class Circulo { //so atributos entre as chaves public float raio; //atributo raio do circulo public float x; //posicoes em coordenadas cartesianas public float y; public float raio; } A classe mostrada acima não é executável por si só e representa um TAD Círculo. Para a execução deste TAD é necessário a classe principal: //Classe principal, Arquivo Principal.Java public class Principal { 46 public static void main(String args[]) { Circulo umcirc; //declaracao de uma variavel circulo no metodo main. umcirc=new Circulo(); //alocacao dessa variavel umcirc.x=3; umcirc.y=4; umcirc.raio=10; System.out.println("("+umcirc.x+","+umcirc.y+","+umcirc.raio); } } Os métodos determinam o comportamento dos objetos de um classe. Quando um método é invocado, se diz que o objeto está recebendo uma mensagem (para executar uma ação). Programas complexos formam conjuntos de objetos que trocam mensagens entre si gerenciando inclusive os recursos do sistema. 7.5- Exercícios Propostos 7.1.1- Criar um TAD para armazenamento de nome, turma, disciplina, matrícula e notas de alunos. Ler os dados dos 5 alunos de uma turma, inclusive as notas obtidas (a disciplina de cada um pode ser diferente do outro) e armazená-los no conjunto. Mostre os dados. 7.1.2- Crie um TAD para armazenamento de dados de cães para uma clínica veterinária. Deverá possuir nome, idade, raça, doença e informações sobre última consulta. 47 8- MÉTODOS E FUNÇÕES Sintaxe de declaração de métodos: A sintaxe simplificada para a declaração de métodos de uma classe é: especificadordeacesso tipoderetorno nomedometodo (lista_de_argumentos) { /*codigo */ } Uma diferença do uso de funções comuns em linguagens não orientadas a objetos e do uso de métodos é que como o método está definido na classe, ele ganha acesso direto aos atributos, sem precisar usar o "ponto", exemplo um_objeto.atributo;. Lembre-se que as chamadas de métodos em um programa já se referem a um objeto específico, embora os métodos sejam definidos de uma forma geral e parametrizada para toda a classe. Volte agora ao método main e verifique sua sintaxe. this é uma palavra chave usada num método como referência para o objeto corrente, ela tem o significado de: "o objeto para o qual este trecho de código está sendo executado". Suponha uma classe que possui a seguinte declaração de atributo: public int qualquer; . Se quisermos em um método desta classe alterar o atributo qualquer para o valor 3, basta escrever qualquer=3; , mas este código escrito dentro de um método da classe que declara qualquer, é totalmente equivalente a this.qualquer=3; , sendo o último uma opção mais clara e capaz de eliminar ambiguidades entre os nomes dos atributos de uma classe e os nomes dos argumentos de um dos métodos desta (quando estes nomes forem iguais). O uso de this também é válido fazer para chamadas de métodos para o objeto corrente. Sintaxe de chamada ou acesso a métodos: A sintaxe de chamada ou acesso à métodos é semelhante a sintaxe de acesso aos atributos, com exceção dos parênteses que contém a lista de argumentos da função que implementa o método, mesmo que a lista seja vazia eles devem estar presentes: 48 umcontador.incrementa();. Primeiro insere-se o nome do objeto e depois a chamada da função, estes são separados por um ponto. Cuidado para não esquecer os parênteses em programas futuros, este é um erro bastante comum. Nova versão do programa Circulo: Agora reapresentaremos o programa Circulo baseado no exemplo 1.2.2, porém um pouco mais complicado: Método move: O método move altera as coordenadas do objeto. O objetotem suas coordenadas x e y somadas com os argumentos dessa função. Note que este método representa uma maneira mais segura, clara, elegante de alterar as coordenadas do objeto do que acessá-las diretamente da seguinte forma: ac.x+=dx;. ac.y+=dy;. Lembre-se que ac.x+=dx é uma abreviação para ac.x=ac.x+dx;. Método mostra: O método mostra imprime na tela, de forma compacta, os atributos do objeto. Nova classe Círculo: //Classe circulo public class Circulo { public float raio; public float x; //posicoes em coordenadas cartesianas public float y; public void move(float dx,float dy) //move o circulo de lugar { this.x+=dx; y+=dy; } public void mostra() //imprime na tela estado do objeto { System.out.println("("+x+","+y+","+raio+")"); } } //fim da declaracao da classe Feitas as modificações apresentadas acima, podemos modificar o programa principal reduzindo a quantidade de código: //Classe principal, Arquivo Principal.Java 49 class Principal { public static void main(String args[]) { Circulo umcirc; //declaracao de atributo circulo umcirc=new Circulo(); umcirc.x=0; umcirc.y=0; umcirc.raio=12; umcirc.mostra(); umcirc.move(10,10); umcirc.mostra(); umcirc.x=100; umcirc.mostra(); } } 8.1- Métodos que Retornam Valores. Até agora só havíamos visto métodos com valor de retorno igual a void. Um método, assim como uma função comum, pode retornar um único elemento de qualquer tipo, inclusive os definidos pelo usuário ou seja: objetos. Sendo assim, sua chamada no programa se aplica a qualquer lugar onde se espera um tipo igual ou equivalente ao tipo do seu valor de retorno, seja numa lista de argumentos de outro método , numa atribuição ou num operador+ em System.out.println( variavel + chamada_de_metodo_que_retorna_valor); 8.2- Sobrecarga de Métodos Java nos permite criar vários métodos com o mesmo nome desde que tenham parâmetros diferentes. Isso é o que chamamos de sobrecarga de métodos. A sobrecarga de métodos consiste em criarmos o mesmo método com possibilidades de entradas diferentes. Essas entradas, caracterizadas como parâmetros, devem sempre ser de tipos diferentes, quantidades de parâmetros diferentes ou posições dos tipos diferentes. Para visualizarmos um cenário, vejamos a classe abaixo: 50 public TV { int canal; int volume; boolean ligada; int tamanho; } O método ligar, simplesmente, muda o valor dos atributos canal e volume para 3 e 25, respectivamente. void ligar (){ canal = 3; volume = 25; ligada = true; } Personalizando este método para que ele mude o atributo ligada de acordo com o parâmetro: void ligar (boolean ligada){ canal = 3; volume = 25; this.ligada = ligada; } Poderíamos utilizar ambos os métodos na mesma classe se quisermos, porque um possui argumentos e o outro não. void ligar (){ canal = 3; volume = 25; ligada = true; } void ligar (boolean ligada){ canal = 3; volume = 25; this.ligada = ligada; } Porém, o mesmo não pode ser aplicado aos atributos canal e volume. Porque não é possível criar um método que recebe um inteiro e criar um outro método com o mesmo nome que também recebe um inteiro, mesmo que estes dois inteiros sejam totalmente diferentes. Se visualizarmos como Java interpreta o método, veríamos: 51 void ligar (int volume) == void ligar (int canal) void ligar (int) == void ligar (int) Por outro lado, é perfeitamente possível criarmos dois métodos que recebam um booleano e um inteiro, inclusive se forem os mesmos, mas em posições diferentes. Isso acontece porque Java não verifica o nome do parâmetro, mas apenas o tipo dele. void ligar (boolean ligada, int canal) ≠ void ligar (int canal, boolean ligada) void ligar (boolean, int) ≠ void ligar (int, boolean) Portanto, pode-se fazer muitas combinações desde que essas combinações não sejam em números iguais, de tipos iguais e nas mesmas posições. 8.3- Exercícios Propostos 8.1- Crie um TAD para armazenamento de dados de cães para uma clínica veterinária. Deverá possuir nome, idade, raça, doença e informações sobre última consulta. A classe deve possuir também: a) Todos os dados devem ser cadastrados através de funções. b) Crie uma função que aumente a idade do cachorro. c) Crie uma função que imprima todos os valores. 8.2- Dentro de uma classe que possua um vetor do tipo inteiro, crie uma função que leia estes valores e uma outra função que mostre a soma de todos os valores deste vetor. 8.3- Crie um TAD que possua uma matriz NxN (quadrada). Este valor N deve ser lido e a matriz NxN preenchida de forma que o número da linha seja o valor para todas as linhas desta matriz. Crie uma função que Imprima a matriz. Ex: 1 1 1 2 2 2 3 3 3 52 8.4- Dentro de uma classe que possua um vetor de 15 posições do tipo inteiro, crie uma função que leia os valores deste vetor e uma outra função que mostre o maior e o segundo maior valor deste vetor. O programa principal deve possuir apenas as duas chamadas às funções e a classe deve possuir sobrecarga de métodos. 8.5- Crie um programa com sobrecarga de métodos que caso dado três coeficientes a, b e c, ele informe se existe raízes e quais são elas dentro da equação do segundo grau. Caso dado dois valores a e b, ele mostre o resultado de acordo com a equação do primeiro grau. Mostre mensagens de erro caso não seja informado diferentes números de coeficientes. 53 9- ENCAPSULANDO MÉTODOS E ATRIBUTOS Encapsulamento, "data hiding" é um conceito bastante importante em orientação a objetos. Neste tópico vamos falar das maneiras de restringir o acesso as declarações de uma classe e a própria classe, isto é feito através do uso das palavras reservadas public, private e protected que são qualificadores. Alguém pode estar se perguntando o porquê de se restringir o acesso a certas partes de uma classe. A idéia é simples, devemos fornecer ao usuário, cliente de uma classe, o necessário e somente o necessário para que ele tire proveito da funcionalidade desta classe. Os detalhes devem ser omitidos, somente a lista de operações a qual uma classe deve atender fica visível. Os benefícios são muitos: clareza do código, minimização de erros, facilidade de extensão. Talvez a facilidade de modificação seja o mais importante dos benefícios. Como a classe é conhecida pela sua interface, é muito fácil mudar a representação interna sem que o cliente, usuário, perceba a diferença Estaremos preocupados em separar design de implementação, Java é uma linguagem boa de se programar em termos de design e em termos de implementação. Programar tendo em vista o design é também chamado de "programming in the large", enquanto que programar tendo em vista implementação, codificação é chamado de "programming in the small". Alguns programadores experientes afirmam que Java se parece com C quando estamos preocupados com codificação, mas quando estamos preocupados com design, Java se assemelha a Smalltalk. Com encapsulamento você será capaz de criar componentes de software reutilizáveis, seguros, fáceis de modificar. Como controlar o acesso de atributos e métodos em uma classe? Simples, através das palavras reservadas private, public e protected cujos significados quando qualificando métodos e atributos 54 (private e public podem também qualificar classes) são descritos abaixo: Public Estes atributos e métodos são sempre acessíveis em todos os métodos de todas as classes. Este é o nível menos rígido de encapsulamento, que equivale a não encapsular. PrivateEstes atributos e métodos são acessíveis somente nos métodos(todos) da própria classe. Este é o nível mais rígido de encapsulamento. Protected Estes atributos e métodos são acessíveis nos métodos da própria classe e suas subclasses. Nada especificado, equivale "package" ou "friendly" Estes atributos e métodos são acessíveis somente nos métodos das classes que pertencem ao "package" em que foram criados. Este modo de acesso é também chamado de "friendly". Package e friendly: Aparecem entre aspas porque não são palavras reservadas da linguagem, são apenas nomes dados para o tipo de encapsulamento padrão (default), que ocorre quando não existe um especificador. São nomes fáceis de memorizar. Friendly significa amigável, no sentido de que as classes que permitem este tipo de acesso possuem um encapsulamento mais relaxado com relação as classes do mesmo package (amigas). Package é um grupo de classes relacionadas. 55 Exemplo: class Ponto { private float x private float y public void inicializa(float a,float b) {x=a; y=b;}; public void move (float dx,float dy); } Fica fácil entender essas declarações se você pensar no seguinte: esses qualificadores se aplicam aos métodos e atributos que vem imediatamente após eles. Os elementos da classe qualificados como private aparecem com fundo cinza escuro indicando que sua "visibilidade" é mais limitada que os atributos qualificados como public (cinza claro). Agora vamos entender o que é private e o que é public. Vamos supor que você instanciou (criou) um objeto do tipo Ponto em seu programa: Ponto meu; //instanciacao meu=new Ponto(); Segundo o uso da definição da classe Ponto dada acima você não pode escrever no seu programa: meu.x=(float)5.0; //erro ! Este tipo de ação gera um erro, a não ser que x fosse declarado como public na definição da classe o que não ocorre aqui. Mas você pode escrever x=5.0; na implementação (dentro) de um método porque enquanto não for feito uso de herança, pode-se dizer que um método tem acesso a tudo que é de sua classe. 56 Você pode escrever: meu.move(5.0,5.0); ,porque sua declaração (move) está como public na classe, em qualquer lugar se pode escrever meu.move(5.0,5.0);. Visibilidade das declarações de uma classe, fora dela ,de sua hierarquia e de seu package. Veja que só a parte public é visível neste caso: A visibilidade das declarações de uma classe, dentro dela mesma é total. 9.2- Método Construtor O método construtor é desenvolvido da mesma forma que uma função, a única diferença é que ele tem o mesmo nome da classe. Isso se deve ao fato de que um objeto deve ser construído cada vez que chamamos a classe. E a responsabilidade de fazer isso é do construtor. Isso parte do princípio que podemos ter dois objetos com a mesma característica, mas que não são os mesmos objetos. Ou seja, nós podemos ter uma TV de 29" ligada no canal 15 e nosso amigo tem uma outra TV que também é de 29" e está ligada no canal 15. Perceba que ambas as TVs têm as mesmas características, mas continuam sendo duas TVs diferentes. Sempre que criamos uma classe, Java automaticamente vincula um método construtor padrão interno com o mesmo nome da classe, mas sem inicializar nenhum atributo. Para demonstrar um método construtor, criaremos um construtor padrão sem argumentos no qual já contém os valores dos atributos definidos por nós mesmos. 57 Então, vamos imaginar que sempre que uma TV é construída, o seu padrão é tamanho 21", desligada e no canal 0. Então, podemos definí-lo como: class TV { int tamanho; int canal; boolean ligada; TV(){ tamanho=21; canal=0; ligada=false; } } 9.3- Exercícios Propostos 9.1- Crie um TAD que possua nome, telefone e endereço. Faça todos os seus dados com o método de acesso private. Insira valores e imprima-os. 9.2- Para um TAD A qualquer, crie os seguintes dados: a) Nome, literal, public; b) Valor, real, public; c) código, inteiro, private; Insira e imprima os dados através de funções. 9.3- Implemente os métodos public void altera_x(float a) , public float retorna_x(void), public void move (float dx, float dy );. Exemplo: public void distancia(ponto a) { return dist(X,Y,a.X,a.Y); } Onde dist representa o conjunto de operações matemáticas necessárias para obter a distância entre (X,Y) (a.X,a.Y). Você provavelmente usará a função Math.sqrt() que define a raiz quadrada de um double, não é preciso fazer nenhum import para usar Math.sqrt(), mas é preciso converter os argumentos de float para double e o valor de retorno de double para float. 58 10- HERANÇA Enquanto programamos em Java, há a necessidade de trabalharmos com várias classes. Muitas vezes, classes diferentes tem características comuns, então, ao invés de criarmos uma nova classe com todas essas características usamos as características de um objeto ou classe já existente. Ou seja, herança é, na verdade, uma classe derivada de outra classe. Para simplificar de uma forma mais direta, vejamos: Vamos imaginar que exista uma classe chamada Eletrodomestico, e nela estão definidos os seguintes atributos: ligado (boolean), voltagem (int) e consumo (int). Se levarmos em conta a classe TV que estamos usando de exemplo até agora, podemos dizer que TV deriva de Eletrodomestico. Ou seja, a classe TV possui todas as características da classe Eletrodomestico, além de ter suas próprias características. 10.1- Extends e Super Para fazermos uma classe herdar as características de uma outra, usamos a palavra reservada extends logo após a definicação do nome da classe. Dessa forma: class NomeDaClasseASerCriada extends NomeDaClasseASerHerdada A linguagem Java permite que uma classe herde apenas as características de uma única classe, ou seja, não pode haver heranças múltiplas. Porém, é permitido heranças em cadeias, por exemplo: se a classe Mamifero herda a classe Animal, quando fizermos a classe Cachorro herdar a classe Mamifero, a classe Cachorro também herdará as características da classe Animal. 59 Como estamos tratando de herança de classes, toda classe tem seu método construtor. Portanto, se estamos trabalhando com duas classes, temos dois métodos construtores. Para acessarmos o método construtor da classe que está sendo herdada usamos o super(). Podemos usar o super para qualquer construtor da classe pai, pois o Java consegue diferenciar os construtores por causa da sobrecarga de métodos. Exemplificando, será mostrado o exemplo citado mais acima da classe Eletrodomestico e TV: Classe 1: Eletrodomestico package tiexpert; public class Eletrodomestico { private boolean ligado; private int voltagem; private int consumo; public Eletrodomestico(boolean ligado, int voltagem, int consumo) { this.ligado = ligado; this.voltagem = voltagem; this.consumo = consumo; } // (...) } Classe 2: TV package tiexpert; public class TV extends Eletrodomestico { private int canal; private int volume; private int tamanho; public TV(int voltagem, int consumo, int canal, int volume, int tamanho) { super(false, voltagem, consumo); this.canal = canal; this.volume = volume; this.tamanho= tamanho; } 60 //(...) } Classe que mostra a instanciação de TV. package tiexpert; public class ExemploHeranca { public static void mostrarCaracteristicas(TV obj) { System.out.print("Esta TV tem as seguintes características:\n" + "Tamanho: " + obj.getTamanho() + "\"\n" + "Voltagem Atual: "+ obj.getVoltagem() + "V\n" + "Consumo/h: " + obj.getConsumo() + "W\n"); if (obj.isLigado()) { System.out.println("Ligado: Sim\n" + "Canal: " + obj.getCanal() + "\n" + "Volume: " + obj.getVolume()+"\n"); } else { System.out.println("Ligado: Não\n"); } } public static void main(String args[]) { TV tv1 = new TV(110, 95, 0, 0, 21); TV tv2 = new TV(220, 127, 0, 0, 29); tv2.setLigado(true); tv2.setCanal(3); tv2.setVolume(25); mostrarCaracteristicas(tv1); mostrarCaracteristicas(tv2); } } 10.2- Exercícios Propostos 10.1- Para um TAD A qualquer, crie os seguintes dados: a) Nome, literal, public, default “A”; b) Vetor de 15 posições, real, public, default zerado; c) código, inteiro, protected, default 0; Para um TAD B qualquer, herdar os valores de A e criar métodos de inserção, busca de valores dentro do vetor. 61 11- LISTAS LINEARES 11.1- Listas Genéricas Conjunto de dados que mantém a relação de ordem Linear entre os componentes. É composta de elementos (componentes ou nós), os quais podem conter um dado primitivo ou estruturado. Lista Linear É uma estrutura que permite representar um conjunto de dados de forma a preservar a relação de ordem entre eles. Uma lista linear X é um conjunto de nodos (nós) X1, X2, ... Xn, tais que: 1) Existem “n” nodos na lista (n >= 0) 2) X1 é o primeiro nodo da lista 3) Xn é o último nodo da lista 4) Para todo i,j entre 1 e n, se i<j, então o elemento Xi antecede o elemento Xj 5) Caso i = j-1, Xi é o antecessor de Xj e Xj é o sucessor de Xi. Observação: Quando n = 0, diz-se que a Lista é Vazia Exemplos de Listas · Lista de clientes de um Banco · Lista de Chamada · Fichário 62 11.1.1- Operações sobre Listas 1) Percurso Permite utilizar cada um dos elementos de uma lista, detal forma que: · 0 primeiro nodo utilizado é o primeiro da lista; · Para utilizar o nodo Xj, todos os nodos de X1 até X(j-1) já foram utilizados; · último nodo utilizado é o último nodo da lista. 2) Busca Procura um nodo específico da lista linear, de tal forma que: · nodo é identificado por sua posição na lista; · nodo é identificado pelo seu conteúdo. 3) Inserção Acrescenta um nodo X a uma lista linear, de tal forma que: · nodo X terá um sucessor e/ou um antecessor; · Após inserir o nodo X na posição i (i >= 1 e i <= n+1), ele passará a ser i-ésimo nodo da lista; · número de elementos (n) é acrescido de uma unidade. 4) Retirada (Exclusão) Retira um nodo X da lista, de tal forma que: · Se Xi é o elemento retirado, o seu sucessor passa a ser o sucessor de seu antecessor. X(i+1) passa a ser o sucessor de X(i- 63 1). Se Xi é o primeiro nodo, o seu sucessor passa a ser o primeiro, se Xi é o último, o seu antecessor passa a ser o último; · número de elementos (n) é decrescido de uma unidade. 11.1.2- Operações Válidas sobre Listas Acessar um elemento qualquer da lista; Inserir um novo elemento à lista; Concatenar duas listas; Determinar o número de elementos da lista; Localizar um elemento da lista com um determinado valor; Excluir um elemento da lista; Alterar um elemento da lista; Criar uma lista; Destruir a lista. 11.2- Filas É uma Lista Linear na qual as inserções são feitas no fim e as exclusões e consultas no início da fila. Critério de Utilização FIFO - "Fi rst In First Out" (primeiro a entrar é o primeiro asair) Operações sobre Filas criaFila(); Cria FILA Vazia insereFila(i); Insere o dado "i" no fim da FILA 64 erro = excluiFila (); Exclui da FILA o primeiro elemento dado = consultaFila (); Copia em "j" primeiro elemento FILA Problema: Escrever um programa em Java que insere, exclui e consulta dados (números inteiros) em uma fila. Programa exemplo: O programa abaixo demonstra a inclusão, exclusão e consulta de números inteiros em uma Fila usando as classes: Fila. public class Fila { final int SUCESSO = 0; final int PILHA_CHEIA = 1; final int PILHA_VAZIA = 2; protected final int m = 7; protected int topo; protected int []elem = new int[m]; //----------- criaVetor public void criaVetor() { topo = -1; } // ----------- push public int push(int dado) { if (topo == m - 1) { System.out.println("Vetor Cheio!!"); return(PILHA_CHEIA); } else { topo = topo + 1; elem[topo] = dado; return(SUCESSO); } } 65 // ------------ Topo public int Topo() { if (topo == -1) { System.out.println("Vetor Vazio!!"); return(PILHA_VAZIA); } else { System.out.println("Topo: " + elem[topo]); return(SUCESSO); } } // ---------- pop public int pop() { if (topo == -1) { System.out.println("Fila Vazia!!"); return(PILHA_VAZIA); } else { System.out.println("Pop: " + elem[0]); aux=elem[0]; topo = topo - 1; for(int cont=1;cont<m;cont++) elem[cont-1]=elem[cont]; return(aux); } } // -------- exibePilha public void exibeFila() { System.out.print("Fila: "); if (topo != -1) { for (int i = topo;i >= 0; i--) { System.out.print(elem[i] + " "); } System.out.println(); } } } 66 11.3- Pilhas É uma Lista Linear na qual as inserções, exclusões e consultas são feitas em um mesmo extremo (Topo). Critério de Utilização LIFO - "Last In First Out" (último a entrar é o primeiro a sair) Operações sobre Pilhas criaPilha(); Cria pilha Vazia erro = push(i); Empilha o dado "i" no topo da Pilha erro = pop(); Desempilha o primeiro elemento erro = consultaPilha(); Exibe o primeiro elemento Identificadores da Pilha B(p) Base da Pilha T(p) Topo da Pilha L(p) Limite da Pilha Problema: Escreva um programa em Java que insere (push),exclui (pop) e consulta dados (números inteiros) em uma Pilha alocada estaticamente. 67 Programa exemplo: O programa abaixo demonstra a inclusão, exclusão e consulta de números inteiros em uma Pilha alocada estaticamente usando a classe Pilha: public class Pilha { final int SUCESSO = 0; final int PILHA_CHEIA = 1; final int PILHA_VAZIA = 2; protected final int m = 7; protected int topo; protected int [ ]elem = new int[m]; //----------- criaVetor public void criaVetor() { topo = -1; } // ------------ Topo public int Topo() { if (topo == -1) { System.out.println("Vetor Vazio!!"); return(PILHA_VAZIA); } else { System.out.println("Topo: " + elem[topo]); return(SUCESSO); } } // -------- exibePilha public void exibePilha() { System.out.print("Pilha: "); if (topo != -1) { for (int i = topo;i >= 0; i--) { System.out.print(elem[i] + " "); } System.out.println(); 68 } } // ----------- push public int push(int dado) { if (topo == m - 1) { System.out.println("Vetor Cheio!!"); return(PILHA_CHEIA); } else { topo = topo + 1; elem[topo] = dado; return(SUCESSO); } } // ---------- pop public int pop() { if (topo == -1) { System.out.println("Pilha Vazia!!"); return(PILHA_VAZIA); } else { System.out.println("Pop: " + elem[topo]); topo = topo - 1; return(elem[topo+1]);
Compartilhar