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