Fundamentos de Programação
Luiz Paulo Maia
[email protected]
Vetores e Matrizes
•
•
•
•
•
•
•
2
Motivações
Definição
Declaração
Criação
Acesso aos elementos
Exemplos
Exercícios
Motivação
• Faça um programa que leia dois números,
calcule a média e mostre o(s) número(s) que
sejam maiores ou iguais a média
• Faça o mesmo programa para cinco números
• Faça o mesmo programa para 100 números
3
Definição
• Um array ou vetor permite armazenar informações do
mesmo tipo em uma única estrutura de dados
• A estrutura de dados é formada por elementos do
mesmo tipo (inteiro, real, lógico ou caractere): tipo
de dado estruturado homegêneo
• Cada elemento é acessado através de um índice,
geralmente inteiro, que está associado à posição do
elemento
• O tamanho do array é estático e definido na sua
criação
4
Definição
vet
5
1
2
3
4
5
6
7
8
10
0
11
-1
201
13
123
3
vet[1]
vet[2]
vet[3]
vet[4]
vet[5]
vet[6]
vet[7]
vet[8]
Declaração
variável: vetor[liminf..limsup] de tipo
• liminf: posição inicial
• limsup: posição final
• tipo: tipo do elemento do vetor
6
Exemplo
• O programa “ListaInvertida” le do teclado uma
sequência de 10 números inteiros e mostra a
sequência invertida. Para a resolução desse problema
é necessário armazenar todos os números lidos para,
posteriormente, exibi-los na ordem invertida. Sem a
utilização de um vetor, seria necessário declarar 10
variáveis inteiras, realizar 10 comandos de leitura e
10 de gravação. Imaginem a resolução do mesmo
problema sem o uso de um vetor para uma lista de
1000 números.
7
Tamanho físico x lógico
LimInf
LimSup
....
Tamanho
lógico
....
Tamanho
físico
• O tamanho físico é definido no momento da
declaração do vetor
• O tamanho lógico é conhecido durante a execução do
programa
8
Exemplo
• O programa “NotasMedia” le do teclado uma
sequência de notas inteiras de uma turma de
no máximo 50 alunos e depois exibe quais as
notas são maiores que a média. A sequência
de notas termina com uma nota negativa.
9
Vetor contador
• Nem sempre vetores são utilizados para
armazenar dados de entrada. O programa
“VetorContador” permite contar a ocorrência
de cada número de uma sequência de números
inteiros entre 1 e 10. A sequência termina com
um número igual a zero.
10
Matrizes
• Matrizes são vetores de duas ou mais dimensões
(multidimensionais)
• Uma matriz de duas dimensões forma uma tabela de
linhas e colunas
• A matriz é formada por elementos apenas do mesmo
tipo
• Cada elemento é acessado através de dois índices que
está associado à posição do elemento (linha e coluna)
• O tamanho da matriz é estático e definido na sua
criação
11
Definição
Colunas
mat
12
1
2
3
4
1
10
0
11
-1
2
201
66
123
17
3
88
0
66
-9
4
3
13
23
44
5
55
56
33
3
Linhas
Declaração
variável: vetor[liminf..limsup, liminf..limsup] de tipo
• 1º liminf..limsup: linhas
• 2º liminf..limsup: colunas
• tipo: tipo do elemento do vetor
13
Exemplo
• O programa “Matriz1” le os elementos de uma
matriz mat de cinco linhas e quatro colunas e
depois exibe os elemetos lidos.
14
Ordenação
vet
vet
15
1
2
3
4
5
50
10
90
40
20
1
2
3
4
5
10
20
40
50
90
Ordenação – Bolha 1
vet
1
2
3
4
5
50
10
90
40
20
Tamlog
vet
vet
vet
vet
16
1
2
3
4
5
10
50
90
40
20
1
2
3
4
5
10
50
90
40
20
1
2
3
4
5
10
50
40
90
20
1
2
3
4
5
10
50
40
20
90
Troca vet[1]
com vet[2]
Não troca vet[2]
com vet[3]
Troca vet[3]
com vet[4]
Troca vet[4]
com vet[5]
Ordenação – Bolha 2
vet
1
2
3
4
5
10
50
40
20
90
Tamlog
vet
vet
vet
17
1
2
3
4
5
10
50
40
20
90
1
2
3
4
5
10
40
50
20
90
1
2
3
4
5
10
40
20
50
90
Não troca vet[1]
com vet[2]
Troca vet[2]
com vet[3]
Troca vet[3]
com vet[4]
Ordenação – Bolha 3
vet
1
2
3
4
5
10
40
20
50
90
Tamlog
vet
vet
18
1
2
3
4
5
10
40
20
50
90
1
2
3
4
5
10
20
40
50
90
Não troca vet[1]
com vet[2]
Troca vet[2]
com vet[3]
Exemplo
• O programa “Ordenacao” implementa o
algoritmo descrito anteriormente e está
dividido em três partes.
19
Pesquisa
• A pesquisa ou busca em um vetor é procurar
um determinado valor entre os seus elementos.
Existem diversos algoritmos de pesquisa em
vetores e nessa seção serão apresentados dois
dos mais importantes: pesquisa sequencial e
pesquisa binária.
20
Pesquisa Sequencial 1
• O programa “PesquisaSequencial1” lê um
vetor de cinco posições, depois lê um número
que se deseja procurar no vetor, realiza a
pesquisa sequencial e retorna se o elemento
foi encontrado ou não.
21
Pesquisa Sequencial 2
• O programa “PesquisaSequencial2” também realiza a
pesquisa, mas não é eficiente como o
“PesquisaSequencial1”. Se por acaso, o elemento
procurado for um dos primeiros a aparecer no vetor,
todos os demais elementos serão testados até o
último componente. O programa
“PesquisaSequencial2” utiliza a variável lógica achou
que permite encerrar a busco logo que o elemento
procurado for encontrado.
22
Pesquisa Binária
vet
1
2
3
4
5
6
7
20
30
50
60
70
80
90
posini
posmeio
• Utilizada quando o vetor está ordenado
• posmeio = (posini + posfim) \ 2
23
posfim
Download

Slides 6