Vetores - dei.isep.ipp.ptnfreire/VETORES - Algoritmia e Java.pdf · Nelson Freire (ISEP–DEI-APROG 2012/13) 2/32 Arrays Sumário Introdução Enquadramento Interesse Noção Tipos

Nelson Freire (ISEP–DEI-APROG 2012/13) 1/32

Vetores Algoritmia e Java

APROG Algoritmia e Programação


Arrays Sumário

Introdução

Enquadramento

Interesse

Noção

Tipos Vetor Matriz

Vetores

Noções Básicas

Interesse

Uso

Declaração

Java : Vetor é um Objeto

Manipulação de Elementos Indicar/Modificar um Elemento Indicar/Modificar todos Elementos

Transferência entre Módulos/Métodos Passagem de Parâmetros Retorno da Função

Exemplos

Ordenação de Vetores

Métodos de Ordenação

Troca Directa

Bubble Sort

Troca Directa

Método

Algoritmo

Exemplo

Variante


Arrays

São Estruturas de Dados Complexas

Arrays Enquadramento 1/2


Categorias de Estruturas de Dados

Simples

Complexas

Simples

Permitem armazenar um só valor, de cada vez

Representam uma posição da memória principal (RAM)

Exemplos

Algoritmia: INTEIRO, REAL, CARATER

Java: tipos primitivos (ex: int, long, float, double, char)

Complexas

Permitem armazenar múltiplos valores, ao mesmo tempo

Exemplos: Arrays

Permitem guardar um conjunto de valores do mesmo tipo (todos)

Exemplos

Notas de alunos (conjunto de reais)

Nomes de alunos (conjunto de Strings)

Representam conjunto de posições contíguas da RAM

RAM

INTEIRO

REAL

CARACTER

REAL

REAL

ARRAY ...

...

...

TEXTO

TEXTO

ARRAY ...

Arrays Enquadramento 2/2

Classificação segundo quantidade de valores armazenados simultaneamente


Problema

Envolve grandes quantidades de valores relacionados entre si

Exemplo

Ler nomes e notas de 20 alunos obtidas numa disciplina

Mostrar os nomes dos alunos cuja nota está acima da média

Arrays Interesse dos Arrays (introdução) 1/2


Solução

Usando apenas estruturas de dados simples

42 variáveis

grande quantidade de código repetido

Conclusão Estruturas de dados simples podem conduzir a soluções impraticáveis

Solução viável Estruturas de dados complexas

Arrays Interesse dos Arrays (introdução) 2/2

ED TEXTO nome1, nome2, ..., nome20 INTEIRO nota1, nota2, ..., nota20, soma REAL media INÍCIO

// Leitura e soma soma 0 LER(nome1, nota1) soma soma + nota1 LER(nome2, nota2) soma soma + nota2 ... LER(nome20, nota20) soma soma + nota20

// Média media soma / 20

// Escrita de alunos acima da média SE (nota1>media) ENTÃO ESCREVER(nome1) SE (nota2>media) ENTÃO ESCREVER(nome2) ... SE (nota20>media) ENTÃO ESCREVER(nome20) FIM


Array

Estrutura de dados complexa

Armazena conjunto de valores

Valores todos do mesmo tipo

Exemplos

Array de números inteiros

Array de textos

Dimensão é fixa

Não modificável em tempo de execução (run-time)

Arrays Noção de Array


Tipos de Arrays

Vetor

Matriz

Vetor

Array Unidimensional

Valores organizados de forma linear

Matriz

Array Bidimensional

Valores organizados em linhas e colunas

12 15 ... 20 14

11 24 ... 27

5 56 18

... ... ... ...

1 8 ... 34

Arrays Tipos de Arrays


Introdução de Arrays

Enquadramento

Interesse

Noção

Tipos Vetor Matriz

Vetores

Noções Básicas

Interesse

Uso

Declaração


Manipulação de Elementos Indicar/Modificar um Elemento Indicar/Modificar todos os Elementos


Exemplos

Arrays Sumário



Troca Directa

Bubble Sort

Troca Directa

Método

Algoritmo

Exemplo

Variante


Vetor

Constituído por conjunto de elementos

Comprimento fixo // Dimensão não modificável em tempo de execução

Elementos organizados de forma linear

Elementos armazenam valores, todos do mesmo tipo

Exemplos: vetor só de reais ou vetor só de texto

Elementos funcionam como variáveis simples

Acesso aos elementos através de índices

Índices

Indicam posições dos elementos

Números inteiros desde 0

Último índice = comprimento-1

12 15 10 20 ... 13 14

0 1 2 3 ... n-2

n-1

elemento 2 valor 10

comprimento (ou dimensão) n

elementos

índices

Vetores Noções Básicas


Armazenar

Listas de valores

Valores

Todos do mesmo tipo

Organizados de forma linear

Exemplos

Lista de notas de alunos a uma disciplina (conjunto de números inteiros)

Lista de disciplinas de um ano escolar (conjunto de Strings)

Vetores Interesse

Português

12

18

15

Disciplinas

APROG

ARQCP

ASIST


Preciso Saber

Declarar um vetor

Java

Vetor é um Objeto

Manipular elementos de um vetor

Um

Todos

Transferir um vetor entre módulos/métodos

Passagem de Parâmetros

Retorno da Função

Vetores Uso


Algoritmia

Declaração 1: dimensão definida na declaração

Sintaxe: tipo nomeVetor[dimensão]

Ex: ED: TEXTO nomes[20]

Declaração 2: dimensão definida depois da declaração

Sintaxe: tipo nomeVetor[ ] criar nomeVetor[dimensão]

Ex: ED : TEXTO nomes[ ] INÍCIO criar nomes[20] FIM

Java

tipo nomeVetor[ ] = new tipo[dimensão];

String nomes[ ] = new String[20];

ou tipo[] nomeVetor = new tipo[dimensão];

String[] nomes = new String[20];

tipo nomeVetor[ ]; nomeVetor = new tipo[dimensão];

String nomes[ ];

nomes = new String[20];

RAM

nomes[0]

nomes[1]

nomes[2]

nomes[19]

...

19 = 20-1

Inicializações automáticas

Tipo primitivo

Numérico: 0

Booleano: false

Tipo referência: null (Ex: String)

Vetor é objeto // ver slide 15

Nome do vetor é referência de objeto

Vetores Declaração 1/2


// Algoritmia

ED

TEXTO nomes[20], paises[]

INTEIRO c

INÍCIO

...

c lerComprimento() // lerComprimento é função do programa

criar paises[c]

...

FIM

...

// Java

public class Exemplo_1 {

public static void main(String[] args) {

String nomes[] = new String[20]; // vetor criado ; elementos inicializados a null ...

String paises[];

...

int c = lerComprimento(); // lerComprimento é função particular do programa paises = new String[c];

...

}

...

}

Vetores Declaração 2/2

Exemplos


Nome de vetor

É referência do objeto que contém os seus elementos // referência = endereço

Exemplo

Vetor nomes

String[] nomes = new String[20]; RAM

nomes[0]

nomes[1]

nomes[2]

nomes[19]

...

...

referência de objeto

...

nomes

...

Objeto

Vetores Java : Vetor é um Objeto


Elemento

Pode ser manipulado individualmente

Funciona como uma variável simples

Identificado

Nome do vetor

Índice respetivo

Indicar Elemento

Algoritmia

Sintaxe: nomeVetor[índice]

Ex: nomes[5]

Manipulações Típicas

De um elemento

De todos os elementos

Java

nomeVetor[índice];

nomes[5]

Vetores Manipulação de Elementos


Algoritmia

Atribuir um valor a um elemento

Ex: guardar ou actualizar um elemento

Sintaxe: nomeVetor[índice] valor

Ex: nomes[5] "Ana"

Atribuir o valor de um elemento a uma variável

Sintaxe: variável nomeVetor[índice]

Ex: s nomes[5]

// s do tipo TEXTO

Java

nomeVetor[índice] = valor;

nomes[5] = "Ana";

variável=nomeVetor[índice];

s=nomes[5];

// s do tipo String

Vetores Manipulação de um Elemento


Algoritmia

• Indicar todos os n elementos (n é comprimento vetor)

PARA (i0 ATÉ n-1 PASSO 1) FAZER

... nomeVetor[i] ...

FPARA

• Ex: Guardar no vetor n notas lidas do teclado

PARA (i0 ATÉ n-1 PASSO 1) FAZER

LER( notas[i] )

FPARA

• Ex: Contar o número de notas superiores a 15

c0 PARA (i0 ATÉ n-1 PASSO 1) FAZER SE ( notas[i] > 15 ) ENTÃO cc+1 FSE FPARA

Java

for( i=0; i < nomeVetor.length; i++ ){ ... nomeVetor[i] ... }

Scanner ler =new Scanner(System.in);

for(i=0; i<notas.length; i++){

notas[i] = ler.nextInt();

} c=0; for(i=0; i<notas.length; i++){ if ( notas[i] > 15 ) c++; }

nomeVetor.length (atributo)

Vetores Manipulação de todos os Elementos


Problema

Ler os nomes e as notas de 20 alunos obtidas apenas numa disciplina e mostrar os nomes dos alunos cuja nota está acima da média.

Solução

Estruturas de dados simples

ED: TEXTO nome1, nome2, ..., nome20 INTEIRO nota1, nota2, ..., nota20, soma REAL media INÍCIO // Leitura e soma soma 0 LER(nome1, nota1) soma soma + nota1 LER(nome2, nota2) soma soma + nota2 ... LER(nome20, nota20) soma soma + nota20 // Média media soma / 20 // Escrita alunos acima da média SE (nota1>media) ENTÃO ESCREVER(nome1) ... SE (nota20>media) ENTÃO ESCREVER(nome20) FIM

Arrays

ED: TEXTO nomes[20] INTEIRO notas[20], soma, i REAL media

INÍCIO

// Leitura e soma soma 0

PARA (i0 ATÉ 19 PASSO 1) FAZER LER(nomes[i], notas[i]) soma soma + notas[i] FPARA

// Média media soma / 20

// Escrita alunos acima da média PARA ( i0 ATÉ 19 PASSO 1 ) FAZER SE ( notas[i]>media ) ENTÃO

ESCREVER( nomes[i] ) FPARA

FIM

5 variáveis

Muito mais fácil escrever

Arrays Interesse dos Arrays (conclusão)

Muito mais fácil escrever


Em Java

Vetor é objeto basta transferir referência desse objeto indicar nome do vetor

Exemplo

Vetores Transferência entre Módulos/Métodos 1/6

RAM

notas[0]

notas[1]

notas[2]

notas[19]

...

...

referência de objeto

...

notas

...

Objeto

int[ ] notas = new int[20];

nome do vetor (objeto)


Formas de Transferir um Vetor

Passagem de parâmetros

Retorno da função

DEFINIR tipo_retornado nome (..., tipo[ ] nomeVetor, ...) ED // variáveis e constantes locais

INÍCIO // corpo da função

RETORNAR expressão_tipo_retornado FDEF

DEFINIR nome (..., tipo nomeVetor [ ], ...) ED // variáveis e constantes locais

INÍCIO // corpo do procedimento

FDEF

Procedimento

Função

DEFINIR tipo[ ] nome (...) ED tipo[ ] nomeVetor INÍCIO // corpo da função

RETORNAR nomeVetor FDEF

Função



Passagem de Parâmetros (1/2)

Passada cópia da referência do vetor

Módulo acede ao vetor original Pode modificar vetor original

Parâmetro formal funciona como parâmetro de entrada e de saída

Declaração de um parâmetro formal

Para receber referência do vetor

Algoritmia

Sintaxe: tipo nomeVetor[]

ou

tipo[] nomeVetor

Ex: DEFINIR ler( INTEIRO vetor[ ] , ...) ...

Chamada de um módulo

Passar referência do vetor (i.e., nome do vetor)

Algoritmia

Sintaxe: nomeVetor

Ex: ler(notas, ...)

Java

tipo nomeVetor[];

ou

tipo[] nomeVetor;

public static void ler( int vetor[], ...){...}

public static void ler( int[] vetor, ...){...}

Java

nomeVetor

ler(notas, ...);


DEFINIR tipo nome(..., tipo nomeVetor [ ], ...)


Passagem de Parâmetros (2/2)

Exemplo (Java)

public class Exemplo{

public static void main(String[] args){

int[] vet = new int[3];

vet[2] = 1;

m(vet);

System.out.println("vet[2]=" + vet[2]);

}

private static void m(int[] v){

v[2]=3;

}

}

// Programa escreve vet[2]=3

0

RAM

vet[0]

0 vet[1]

1 vet[2]

...

referência x vet

...

referência x v

0 vet[0]

0 vet[1]

3 vet[2]

...

referência x vet

...

referência x v

Na execução de m

Na chamada de m



Retorno da Função

Retornada referência do vetor

Declaração do tipo_retornado da função

Tipo vetor

Algoritmia

Sintaxe: DEFINIR tipo[ ] nomeFunção ( ...) ...

Ex: DEFINIR INTEIRO[ ] filtrar(...) ...

Retorno

Referência do vetor (i.e., nome do vetor)

Algoritmia

Sintaxe: RETORNAR nome_vetor

Ex: RETORNAR notas

Java

public static tipo[ ] nomeMétodo(...){...};

public static int[ ] filtrar(...){...}

Java

return nome_vetor;

return notas;


DEFINIR tipo[ ] nome(...) ED tipo[ ] nomeVetor INÍCIO // corpo da função

RETORNAR nomeVetor FDEF


private static float media(int[] v) {

float s=0;

for (int i = 0; i < v.length; i++)

s+=v[i];

return s/v.length;

}

private static int lerTotalNotas() {

Scanner ler = new Scanner(System.in);

System.out.println("Digite o nº notas:");

int n = ler.nextInt();

while (n <= 0) {

System.out.println("Valor Inválido!! "

+ "Insira novo nº de notas:");

n = ler.nextInt();

}

return n;

}

private static void incrementar(int[] notas,

float media) {

int d = 10 - (int) media;

if(d>0)

for (int i = 0; i < notas.length; i++)

if (notas[i] + d > 20)

notas[i] = 20;

else

notas[i] += d;

}

}

Exemplos

import java.util.Scanner;

public class Notas {

public static void main(String[] args) {

int totNotas = lerTotalNotas();

int[] notas = lerNotas(totNotas);

float m = media(notas);

if(m<10)

incrementar(notas, m);

listar(notas);

}

private static int[] lerNotas(int n) {

Scanner ler = new Scanner(System.in);

int[] vec = new int[n];

for (int i = 0; i < vec.length; i++) {

System.out.println("Nota " + (i + 1) + ":");

vec[i] = ler.nextInt();

while (vec[i] < 0 || vec[i] > 20) {

System.out.println("Nota Inválida!!" +

"Insira a nota:" + (i + 1) + ":");

vec[i] = ler.nextInt();

}

}

return vec;

}

private static void listar(int[] vec) {

System.out.println("Listagem Notas:")

for (int i = 0; i < vec.length; i++)

System.out.println(vec[i]);

}



Arrays Sumário

Introdução de Arrays

Enquadramento

Interesse

Noção

Tipos Vetores Matrizes

Vetores

Noções Básicas

Interesse

Uso

Declaração


Manipulação de Elementos Indicar/Modificar um Elemento Indicar/Modificar todos os Elementos


Exemplos



Troca Directa

Bubble Sort

Troca Directa

Método

Algoritmo

Exemplo

Variante


Há vários métodos

Exemplos

Troca Directa

Bubble Sort

Ordenação de Vetores Métodos


Ordenar, sucessivamente, os primeiros n-1 elementos do vetor (n = comprimento do vetor)

Exemplo:

Ordenar o i-ésimo elemento

Comparar esse elemento, sucessivamente, com cada um dos elementos seguintes

Exemplo

Após cada comparação, trocar os elementos comparados (i e j) se ...

Ordenação crescente: v[j] < v[i] Ordenação decrescente: v[j] > v[i]

1ª Ordenação 2ª Ordenação 3ª Ordenação

i

j

i

j

i

j

Elemento 0:

i

j

Elemento 1: i

j

i

j

Elemento 2:

6 5 . . . . . . 2 8 . . . . . .

menor maior

Ordenação de Vetores Troca Directa : Método 1/5


Ordenação Crescente

6 5 7 3

i

j

6 5 7 3

(i=0) 5 6 7 3 5 6 7 3

i

j

5 6 7 3

i

j

3 6 7 5

3 6 7 5

i

j

(i=1) 3 6 7 5

i

j

3 5 7 6

3 5 7 6

i

j

(i=2) 3 5 6 7

Ordenação de Vetores Troca Directa : Exemplo 2/5


Algoritmo


PARA ( i0 ATÉ n-2 PASSO 1 ) FAZER

PARA( j i+1 ATÉ n-1 PASSO 1 ) FAZER

SE ( v[j] < v[i] ) ENTÃO

tmp v[i]

v[i] v[j]

v[j] tmp

FSE

FPARA

FPARA

Ordenação Decrescente

• Única alteração

v[j] > v[i]

i

j

n-2

n-1

0

i+1

comprimento do vetor (n)

Ordenação de Vetores Troca Directa : Algoritmo 3/5


Ordenação de Vetores Troca Directa : Exemplo de Ordenação Alfabética de Strings 4/5

Algoritmo

ED: TEXTO tmp, nomes[ ] INTEIRO i, j, n ALG INÍCIO REPETIR LER(n) ENQUANTO n<=0

criar nomes[n]

...

PARA ( i0 ATÉ n-2 PASSO 1 ) FAZER PARA( j i+1 ATÉ n-1 PASSO 1 ) FAZER SE ( nomes[j] < nomes[i] ) ENTÃO tmp nomes[i] nomes[i] nomes[j] nomes[j] tmp FSE FPARA FPARA ... FIM

Java

public class TrocaDirecta{ public static void main(String[] args) { String tmp, nomes[ ]; int i,j,n; Scanner ler = new Scanner(System.in); do { System.out.print("N:") n=ler.nextInt(); } while(n<=0); nomes = new String[n]; ... for ( i=0; i<=n-2; i++ ) { for( j=i+1; j<=n-1; j++ ) { if ( nomes[j].compareTo( nomes[i] ) < 0 ) { tmp = nomes[i]; nomes[i] = nomes[j]; nomes[j] = tmp; } } } ... } }


Algoritmo


PARA ( i0 ATÉ n-2 PASSO 1 ) FAZER

menor i

PARA( j i+1 ATÉ n-1 PASSO 1 ) FAZER

SE ( v[j] < v[menor] ) ENTÃO

menor j

FSE

FPARA

SE ( menor != i ) ENTÃO

tmp v[i]

v[i] v[menor]

v[menor] tmp

FSE

FPARA

Ordenação Decrescente

Única alteração

v[j] > v[i]

i

j

n-2

n-1

0

i+1

comprimento do vetor (n)

Ordenação de Vetores Troca Directa : Algoritmo mais Eficiente 5/5

Documents

Vetores - dei.isep.ipp.ptnfreire/VETORES - Algoritmia e Java.pdf · Nelson Freire (ISEP–DEI-APROG 2012/13) 2/32 Arrays Sumário Introdução Enquadramento Interesse Noção Tipos