Vetores-Dados Homogêneos

Prévia do material em texto

Estruturas de Dados Homogêneas
Introdução à Ciência da Computação
Prof. Dr. Fábio Roberto Chavarette
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Objetivos
� Introdução
� Definição
� Necessidade de uso
� Operações básicas
� Exemplos
Página 2
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Introdução
Geralmente, os algoritmos são elaborados para manipulação de dados. 
Quando estes dados estão organizados (dispostos) de forma coerente, 
caracterizam uma forma, uma estrutura de dados. 
A organização dos dados é chamada de estrutura composta de dados
que se divide em duas formas fundamentais: 
- homogêneas (vetores e matrizes) 
- heterogêneas (registros).
Página 3
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Introdução
ESTRUTURA DE DADOS COMPOSTA HOMOGÊNEA
� As estruturas de dados homogêneas possibilitam o armazenamento de 
grupos de valores em uma única variável que será armazenada na 
memória do computador. Essas estruturas são ditas “homogêneas”
porque os valores que serão armazenados são de um mesmo tipo de 
dado.
� Estas estruturas homogêneas são divididas em unidimensionais e 
multidimensionais. 
� Normalmente, as estruturas unidimensionais são chamadas de vetores 
e as multidimensionais são chamadas de matrizes. De fato, um vetor 
também é uma matriz, porém varia em somente uma dimensão.
Página 4
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Introdução
ESTRUTURA DE DADOS COMPOSTA HOMOGÊNEA
algoritmo "alturas de atletas"
// Síntese
// Objetivo: armazenar 5 alturas de atletas de basquete
// Entrada: 5 alturas
// Saída: -
// Declarações
var
altura1,altura2,altura3,altura4,altura5 : real
inicio
escreva("Informe a altura do 1º atleta: ");
leia (altura1)
escreva("Informe a altura do 2º atleta: ")
leia (altura2)
escreva("Informe a altura do 3º atleta: ")
leia (altura3)
escreva("Informe a altura do 4º atleta: ")
leia (altura4)
escreva("Informe a altura do 5º atleta: ")
leia (altura5)
fimalgoritmo
Vetores – Unidimensional
Matrizes - Multidimensional
Página 5
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetores
Definição: 
Um vetor é uma coleção de elementos de um mesmo tipo. Cada um dos 
elementos é unicamente identificado por um número inteiro.
2
1
3
4
6
5
Página 6
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Representação Gráfica de um Vetor
num[1] ←←←← 4
4
num[1]
num[25]
Página 7
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetores
�O valor do índice não deve ser confundido com o conteúdo 
da posição do vetor. 
�O índice identifica o elemento dentro do conjunto. O índice 
tem de ser obrigatoriamente inteiro.
�O elemento do vetor pode ser um número inteiro, um 
número real, uma variável booleana, um caractere, uma 
string, ...
Página 8
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Analogia
� O índice de um vetor corresponde à numeração das casas numa rua.
� O número de uma casa nada tem a ver com o seu conteúdo.
Página 9
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
� Quando desejamos processar uma grande quantidade de informações 
fica extremamente complicado, ou praticamente impossível, criar e 
manter um conjunto grande de variáveis.
Página 10
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
� Podemos imaginar a situação onde, em um programa para manutenção 
do cadastro de um banco, os dados de cada cliente fossem 
armazenados em uma variável diferente. 
� O programa teria de lidar com milhares de variáveis. 
� Seria dificílimo, por exemplo, percorrer a lista de clientes e procurar pelo
cliente ‘Fernando Henrique Cardoso’
Página 11
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
Dificuldade de manipulação de informação relacionada 
armazenada em variáveis simples
{Calcular a média das idades de 5 crianças}
- início
- leia idadeA
- leia idadeB
- leia idadeC
- leia idadeD
- leia idadeE
- media ← (idadeA+ idadeB + idadeC +
- idadeD + idadeE)/5
- imprime media
- fim
Página 12
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
�Alternativa: informação armazenada em 
vetores
-início
- soma ← 0
- ...
-fim
Página 13
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
�Alternativa: informação armazenada em 
vetores
-início
- soma ← 0
- para i ← 1 até 5 faça
- ...
- próximo i
- ...
-fim
Página 14
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
� Alternativa: informação armazenada em vetores
-início
- soma ← 0
- para i ← 1 até 5 faça
- leia idade[i]
- ...
- próximo i
- ...
-fim
Página 15
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
� Alternativa: informação armazenada em vetores
-início
- soma ← 0
- para i ← 1 até 5 faça
- leia idade[i]
- soma ← soma + idade[i]
- próximo i
- ...
-fim
Página 16
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
� Alternativa: informação armazenada em vetores
-início
- soma ← 0
- para i ← 1 até 5 faça
- leia idade[i]
- soma ← soma + idade[i]
- próximo i
- media ← soma/5
- ...
-fim
Página 17
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
� Alternativa: informação armazenada em vetores
-início
- soma ← 0
- para i ← 1 até 5 faça
- leia idade[i]
- soma ← soma + idade[i]
- próximo i
- media ← soma/5
- imprime media
-fim
Página 18
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
� E se fossem 1000 crianças?
Página 19
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Quando usar vetores?
� Alternativa: informação armazenada em vetores
-início
- soma ← 0
- para i ← 1 até 1000 faça
- leia idade[i]
- soma ← soma + idade[i]
- próximo i
- media ← soma/1000
- imprime media
-fim
Página 20
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetores e Laços
�Observe a construção:
- para i ← 1 até 1000 faça
- leia crianca[i]
- próximo i
�A grande força na utilização de um vetor consiste em
associá-lo a um laço.
�Com isso podemos facilmente percorrer um vetor para
consultas ou atualizações.
Página 21
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Exemplo: Inicializando e correndo um vetor
-início
- para i ← 1 até 5 faça
- leia carros[i]
- próximo i
- ...
-fim
Inicializando
Página 22
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Exemplo: Inicializando e correndo um vetor
-início
- para i ← 1 até 5 faça
- leia carros[i]
- próximo i
- para i ← 1 até 5 faça
- imprima 'carro',i,'quantidade:', carros[i]
- próximo i
-fim
Inicializando
Correndo
Página 23
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Exemplo: Inicializando e correndo um vetor
� Saída:
-carro 1 quantidade: 10
-carro 2 quantidade: 11
-carro 3 quantidade: 12
-carro 4 quantidade: 13
-carro 5 quantidade: 14
Valor digitado
Página 24
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Outro Exemplo
Leitura de uma tabela de 100 valores e impressão da tabela 
multiplicada por uma constante.
Página 25
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Outro Exemplo
-início
- {entrada de dados}
- para i ← 1 até 100 faça
- leia tab[i]
- próximo i
- ...
-fimPágina 26
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Outro Exemplo
-início
- {entrada de dados}
- para i ← 1 até 100 faça
- leia tab[i]
- próximo i
- {processamento}
- para i ← 1 até 100 faça
- tab[i] ← 3.1415*tab[i]
- próximo i
- ...
-fim
Página 27
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Outro Exemplo
-início
- {entrada de dados}
- para i ← 1 até 100 faça
- leia tab[i]
- próximo i
- {processamento}
- para i ← 1 até 100 faça
- tab[i] ← 3.1415*tab[i]
- próximo i
- {saída de dados}
- para i ← 1 até 100 faça
- imprima tab[i]
- próximo i
-fim
Página 28
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Outro Exemplo 2
Determinar o maior elemento de um vetor e a sua posição
Página 29
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Maior elemento de um vetor
-início
- {entrada de dados}
- para i ← 1 até 20 faça
- leia tabela[i]
- próximo i
- ...
-fim
Página 30
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Maior elemento de um vetor
-início
- {entrada de dados}
- para i ← 1 até 20 faça
- leia tabela[i]
- próximo i
- {assume que o primeiro elemento da }
- {tabela é o maior}
- maior ← tabela[1]
- pos ← 1
- ...
-fim
Página 31
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Maior elemento de um vetor
-início
- ...
- {assume que o primeiro elemento da }
- {tabela é o maior}
- maior ← tabela[1]
- pos ← 1
- {procura o maior}
- para i ← 2 até 20 faça
- se tabela[i] > maior então
- maior ← tabela[i]
- pos ← i
- fim se
- próximo i
- ...
-fim
Página 32
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Maior elemento de um vetor
-início
- ...
- {assume que o primeiro elemento da }
- {tabela é o maior}
- maior ← tabela[1]
- pos ← 1
- {procura o maior}
- para i ← 2 até 20 faça
- se tabela[i] > maior então
- maior ← tabela[i]
- pos ← i
- fim se
- próximo i
- imprima maior, pos
-fim
Página 33
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Constantes
�A declaração de constantes em algoritmos
-constante
- DIM = 100
Página 34
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Exemplo
-constante
- DIM = 100
-inicio
- para i ← 1 até DIM faça
- leia tab[i]
- próximo i
- para i ← 1 até DIM faça
- tab[i] ← 3.1415*tab[i]
- próximo i
- para i ← 1 até DIM faça
- imprima tab[i]
- próximo i
-fim
Página 35
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Constantes
� Vantagem na utilização de constantes: 
- Se houver necessidade de alterar a dimensão 
do vetor, basta alterar o valor da constante DIM.
Página 36
Processamento de Dados
Candidato: Fábio Roberto Chavarette
Estruturas de Dados Homogêneas
em C++
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetor em C/C++Vetor em C/C++Vetor em C/C++Vetor em C/C++
Um vetor é um conjunto unidimensional de variáveis. 
Um nome é associado ao vetor como um todo; cada 
elemento deste vetor é referenciado por um índice (ou 
subscrito), entre chaves, que acompanha o nome 
atribuído ao vetor.
O nome do vetor deve seguir as mesmas regras, já
vistas, para nomes de variáveis simples
Página 38
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetor em C/C++Vetor em C/C++Vetor em C/C++Vetor em C/C++
�Vetores
O índice que discrimina os elementos constituintes do vetor 
pode ser qualquer expressão do tipo inteiro.
Ex. Vetex
20.
1987.
4.6
-4.2
0.0
VETEX(1)
Nome do 
vetor Índice 
ou 
subscrito
VETEX(I)
(0)
(1)
(2)
(3)
(4)
Página 39
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetor em C/C++
� Vetores
Observações:
1. As variáveis indexadas, podem ter até 7 índices.
2. O índice de uma variável pode assumir valores 
inteiros quaisquer
3. Todos os elementos de um vetor têm o mesmo
tipo. O tipo é definido como no caso das variáveis 
simples.
4. Um elemento de um vetor pode ser usado numa 
expressão como uma variável.
5. Os índices utilizados na linguagem C/C++ para
identificar as posições de um vetor começam 
sempre em 0 (zero) e vão até o tamanho do vetor 
menos uma unidade.
Página 40
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetor em C/C++Vetor em C/C++Vetor em C/C++Vetor em C/C++
� Declaração de vetor
A declaração da variável é seguida por um par de colchetes contendo 
um número inteiro indicando o tamanho da matriz, podendo
também conteruma constante declarada anteriormente.
Exemplo:
int notas[5]; cinco elementos inteiros.
float corrente[2]; 2 elementos reais.
No exemplo acima, cada elemento é referenciado por um único índice, 
sendo estes iniciados por zero. Os elementos de uma matriz
são armazenados em seqüência contínua de memória.
• Obs.: C não avisa quando o limite de uma matriz foi excedido. 
Se você ultrapassar o valor do limite imposto na declaração da matriz, 
os valores sobressalentes irão sobrepor outros dados da
memória.
Página 41
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetor em C/C++
� Atribuindo valores ao vetor
Na declaração:
int dmes[12]={31,28,31,30,31,30,31,3,1,30,31,30,31};
No decorrer do programa:
As atribuições em vetor exigem que seja informada em qual de suas 
posições o valor ficará armazenado.
V[0]=1; atribui o valor 1 à primeira posição do vetor.
x[3]=‘b’; Atribui a letra b à quarta posição do vetor.
Página 42
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetor em C/C++
� Preenchendo um vetor
Preencher significa atribuir valores a todas as suas 
posições. Assim, deve implementar um mecanismo que 
controle o índice.
for (i=0; i<10; i++)
scanf(“%d”, vetor[i]);
ou
cin >> vetor[i] 
Neste caso, a estrutura de repetição FOR foi utilizada para 
garantir que a variável i assuma todos os valores 
possíveis para o índice do vetor (0 a 9). Assim, para 
cada execução da repetição, será utilizada uma 
posição diferente do vetor.
Página 43
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Vetor em C/C++Vetor em C/C++Vetor em C/C++Vetor em C/C++
� Mostrando elementos do vetor
Mostrar os valores contidos em um vetor também exige a 
utilização do índice.
for (i=0; i<10; i++)
printf(“%d \n”, vetor[i]);
ou
cout << vetor[i] 
Neste caso, a estrutura de repetição FOR foi utilizada para 
garantir que a variável i assuma todos os valores 
possíveis para o índice do vetor (0 a 9). Assim, para 
cada execução da repetição, será utilizada uma 
posição diferente do vetor.
Página 44
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Exemplo de Vetor em C/C++
Ler 100 números e imprimi-los em 
ordem inversa. Neste 
exemplo, os dados devem ser 
fornecidos um em cada linha; 
os resultados são 
impressos, também, um em 
cada linha.
#include <cstdlib>
#include <iostream>
#define indice 100
using namespace std;
int main(int argc, char *argv[ ])
{
int numero[indice], i;
for (i=0; i<indice; i++){
printf("Entre com o elemento %d: ", i+1);
scanf("%d", &numero[i]);
}
printf("\n \n");
for (i=indice-1;i >= 0; i - -)
printf("saida %d \n", numero[i]); 
system("PAUSE");
return EXIT_SUCCESS;
}
Define um índice fixo para o vetor
Leitura do vetor
Impressão do vetor
Página 45
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Exemplo 2 de Vetor em C/C++
Dado um vetor de NUMEL 
elementos, determinar o maior 
elemento do vetor. Os 
elementos do vetor devem ser 
fornecidos um em cada linha 
de entrada.
#include <cstdlib>
#include <iostream>
#define indice 5
using namespace std;
int main(intargc, char *argv[])
{
int numero[indice], i, maior; 
for (i=0; i<indice; i++){ //leitura do vetor
printf("Entre com o elemento %d: ", i+1);
scanf("%d", &numero[i]);
if (i==0) //verificação do maior
maior=numero[i];
else if (maior<numero[i])
maior=numero[i];
}
printf("O maior elemento do vetor e %d \n", maior);
system("PAUSE");
return EXIT_SUCCESS;
}
Página 46
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Conjuntos Multidimensionais - MATRIZ
Os conjuntos com mais de uma dimensão, referenciados aqui como 
matrizes, também são representados com o uso de variáveis 
indexadas, só que agora com mais de um índice. Cada índice 
referencia uma dimensão.
49 19 58
30 13 2Matex(2,3)
2º índice(deve ser usado para indicar o 
número da coluna)
1º índice(deve ser usado para indicar o 
número da linha)
Nome da matriz
Página 47
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Conjuntos Multidimensionais - MATRIZ
Declaração
Utiliza-se dois pares de colchetes. Cada par de colchetes adicionais 
obtemos matrizes com uma dimensão a mais. A lista de valores 
usada para inicializar a matriz é uma lista de constantes separadas 
por vírgulas e envolta por chaves.
Exemplo:
int soma[3][3];
float nota[2][3]={{9,8,7},{6.5,4,2}};
Da mesma maneira como, ocorre com os vetores, os índices 
começam sempre em 0 (zero). 
Página 48
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Conjuntos Multidimensionais - MATRIZ
Exemplo:
char MAT[4][3];
MAT
0
1
2
3
0 1 2
Página 49
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Conjuntos Multidimensionais - MATRIZ
Exemplo:
flot Y[2][4][3];
A declaração criou uma matriz chamada Y contendo:
2 linha (0 a 1) 
4 colunas (0 a 3)
3 profundidade (0 a 2)
Página 50
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Conjuntos Multidimensionais - MATRIZ
Atribuindo valor a uma matriz:
X[1][4]=5; Atribui o valor 5 à posição identificada pelos índices 1 
(2ª linha) e 4 (5ª coluna).
5
X
0
1
0 1 2 3 4 5
Página 51
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Conjuntos Multidimensionais - MATRIZ
Preenchendo uma Matriz
Preencher uma matriz significa percorrer todos os seus elementos, atribuindo-lhe 
um valor.
Exemplo para matriz bidimensional:
for (i=0; i<7; i++)
{
for (j=0; j<3; j++)
scanf(“%d”, MAT[i][j]);
}
Como a matriz possui sete linhas e três colunas, o for externo deve variar 
de 0 a 6 (percorrendo, assim, as sete linhas da matriz) e o for
interno deve variar de 0 a 2 (percorrendo, assim, as três colunas 
da matriz).
Linha
Coluna
Página 52
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Conjuntos Multidimensionais - MATRIZ
Exemplo
� A matriz BAR, mostra a seguir, apresenta os totais das vendas 
de três itens comercializados em um bar, em cada uma 
das quatro semanas de um mês
ITENS 1 2 3
SEMANAS (Cerveja) (Refrigerante) (Cachaça)
1º 15 7 10
2º 2 21 15
3º 20 3 5
4º 8 12 40
O trecho do programa seguinte calcula o total de itens vendidos por 
semana e o total de itens do mês.
Página 53
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br
Conjuntos Multidimensionais - MATRIZ
ITENS 1 2 3
SEMANA
S
(Cerveja) (Refrigera
nte)
(Cachaça)
1º 15 7 10
2º 2 21 15
3º 20 3 5
4º 8 12 40
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
int bar[4][3]={{15,7,10},{2,21,15},{20,3,5},{8,12,40}};
int total, totalmes, i, j;
totalmes=0;
for (i=0;i<4;i++)
{
total=0;
for (j=0;j<3;j++)
total+=bar[i][j];
printf("O total para o semana %d e %d \n", i+1, total);
totalmes+=total;
}
printf("O total para do mes e %d \n", totalmes); 
system("PAUSE");
return EXIT_SUCCESS;
}
Página 54
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br Página 55
Algoritmos: Definição e Caracterização
Referencias 
�Harry Farrer, Christiano Goncalves Becker,Eduardo Chaves 
Faria, Helton Fabio de Matos, Marcos Augusto dos Santos e 
Miriam Lourenco Maia, “Algoritmos Estruturados", editora 
Guanabara Koogan.
�Marco A. F. Souza et al. “Algoritmos e lógica de 
programação”. Thompson, 2005.
�Harvey M. Deitel. “Java – Como programar”. Prentice Hall, 
2006.
Prof. Dr. Fábio Roberto Chavarette – fabioch@mat.feis.unesp.br Página 56
Introdução a Ciências da Computação
� Universidade Estadual Paulista “Julio 
de Mesquita Filho”
� Faculdade de Engenharia do Campus 
de Ilha Solteira
� Departamento de Matemática
Prof. Dr. Fábio Roberto Chavarette
E-Mail: fabioch@mat.feis.unesp.br
F I M