DCC 119 Algoritmos 2 Em diversas situações os tipos básicos de dados (inteiro, real, caracter, ....) não são suficientes para representar a informação que se deseja armazenar. Exemplo, uma palavra: AULA . Valor de 50 produtos em uma loja Existe a possibilidade de construção de novos tipos de dados a partir da composição (ou abstração) de tipos de dados primitivos. Esses novos tipos têm um formato denominado ESTRUTURA DE DADOS, que define como os tipos primitivos estão organizados. Estruturas de Dados 3 Problema 1: Como poderíamos fazer um algoritmo para ler 50 notas de uma turma e calcular sua média? Motivação principal { inteiro i; //variável de controle real nota, media, soma = 0; para (i 1; i <= N; i i+1) faça { imprima("Digite uma nota:"); leia(nota); soma soma + nota; } media soma/N; imprima("Media = ", media); } Problema: Qual o valor da 1a ou 5a ou 40a nota? 4 Problema 2: Fazer um programa para ler 50 notas de uma turma e calcular a sua média. Imprimir as notas lidas juntamente com a média da turma como na tabela. Motivação Nota Media 8.0 7.75 4.6 7.75 2.3 7.75 3.7 7.75 7.8 7.75 9.0 7.75 .... ... Como fazê-lo? No exemplo anterior, uma nota é sobreposta por outra em cada iteração do para. A solução é armazenar todas as 50 notas lidas... Mas como?!? 5 Quando uma determinada estrutura de dados for composta de variáveis com o mesmo tipo primitivo, temos um conjunto homogêneo de dados. Essas variáveis são chamadas de variáveis compostas homogêneas. Variáveis Compostas Homogêneas 6 As variáveis compostas homogêneas unidimensionais são utilizadas para representar arranjos unidimensionais de elementos de um mesmo tipo, em outras palavras, são utilizadas para representar vetores. Variáveis Compostas Homogêneas Unidimensionais (Vetores) 7 A sintaxe para declaração de uma variável deste tipo, tanto na pseudolinguagem quanto em C é a seguinte: tipo identificador [qtd de elementos]; Exemplo: // vetor com 5 elementos do tipo inteiro inteiro dados[5] ; // em C seria ficaria int dados[5]; Vetores: Declaração 0 1 2 3 4 dados 5 elementos quaisquer do tipo inteiro Í ndices do vetor 8 Cada um dos elementos de um vetor é referenciado individualmente por meio de um número inteiro entre colchetes após o nome do vetor. Exemplos: Considerando o vetor dados, quais valores serão atribuídos a X e Y nos exemplos abaixo??? A instrução abaixo atribui um valor ao elemento 0 (zero) do vetor dados: Vetores: Referência (Manipulação) 0 1 2 3 4 dados 3 2 74 1 PseudoLinguagem X dados[1]; Y dados[4]; Linguagem c dados[0] = 6; ou I = 0; dados[i] = 6; PseudoLinguagem dados[0] 6; ou I 0; dados[i] 6; Linguagem c X = dados[1]; Y = dados[4]; 9 O programa a seguir, usa o comando para para inicializar com zeros os elementos de um array inteiro n de 10 elementos e o imprime sob a forma de uma tabela. Vetores: Exemplos principal { inteiro n[10], i; para (i 0; i <= 9; i i+1) faça { n[i] 0; } imprima("Elemento Valor"); para (i 0; i <= 9; i i+1) faça { imprima(i," ", n[i]); } } Elemento Valor 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 Exemplo anterior em C: Vetores: Exemplos //inicializando um vetor (array) #include <stdio.h> int main() { int n[10], i; for (i=0; i<= 9; i++) { n[i] = 0; } printf("%s%13s\n","Elemento", "Valor"); for (i=0; i<= 9; i++) { printf("%7d%13d\n",i,n[i]); } return 0; } Elemento Valor 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 11 O programa abaixo inicializa os dez elementos de um array s com os valores: 2, 4, 6, ..., 20 e imprime o array em um formato de tabela. Vetores: Exemplos Elemento Valor 0 2 1 4 2 6 3 8 4 10 5 12 6 14 7 16 8 18 9 20 principal { constante inteiro TAMANHO 10; inteiro s[TAMANHO], j; para (j 0; j <= TAMANHO - 1; j j+1) faça { s[j] 2 + 2*j; } imprima("Elemento Valor"); para (j 0; j <= TAMANHO - 1; j j+1) faça { imprima (j, " ",s[j]); } } 12 Vetores: Exemplos #include <stdio.h> #define TAMANHO 10 int main() { int s[TAMANHO], j; for (j=0; j<= TAMANHO - 1; j++) { s[j] = 2 + 2*j; } printf("%s%13s\n","Elemento", "Valor"); for (j=0; j<= TAMANHO - 1; j++) { printf("%8d%13d\n",j,s[j]); } return 0; } Elemento Valor 0 2 1 4 2 6 3 8 4 10 5 12 6 14 7 16 8 18 9 20 Exemplo anterior em C: 13 Em pseudolinguagem, a passagem de parâmetros em procedimentos e funções é feita por cópia. Para realizar a passagem por referência, utilize a palavra ref antes do tipo de vetor. Em C, vetores são passados sempre por referência. 14 No exemplo abaixo é apresentado um procedimento imprimeVetor que imprime um vetor de tamanho tam. imprimeVetor (inteiro vet[], inteiro tam) { inteiro i; para (i 0; i <= tam - 1; i i+1) faça { imprima (vet[i]); } } principal { constante inteiro TAMANHO 10; inteiro s[TAMANHO], j; para (j 0; j <= TAMANHO - 1; j j+1) { imprima ("Informe o valor do vetor na posição ", j); leia (s[j]); } imprimeVetor(s, TAMANHO); } 15 Exemplo anterior em C: #include <stdio.h> #define TAMANHO 10 void imprimeVetor (int vet[], int tam) { int i; for (i = 0; i <= tam - 1; i++) { printf("%d\n", vet[i]); } } int main() { int s[TAMANHO], i; for (i = 0; i <= tam - 1; i++) { printf ("Informe o valor do vetor na posição %d: ", i); scanf ( %d", &s[j]); } imprimeVetor(s, TAMANHO); } 16 Vamos ver agora o teste de mesa para o seguinte problema: Criar uma função que receba um vetor de números reais e seu tamanho e retorne o índice do maior valor contido no vetor. Se houver mais de uma ocorrência do maior valor, retornar o índice do primeiro. Faça um programa principal para testar a função. 17 Exercício 1 - Solução Proposta int encontraMaior (real vet[], inteiro tam) { inteiro indice, i; real maior = vet[0]; indice 0; para (i 1; i < tam; i i+1) faça { se( vet[i] > maior) { maior vet[i]; indice i; } } retorne indice; } principal { real vetor[6] = {3.0, 4.3, 5.6, 2.8, 7.9, 3.4}; inteiro posicao; posicao encontraMaior( vetor, 6) imprima("Maior valor esta na posicao ", posicao); } 18 Exercício 1 - Teste de Mesa int encontraMaior (real vet[], inteiro tam) { inteiro indice, i; real maior = vet[0]; indice 0; para (i 1; i < tam; i i+1) faça { se( vet[i] > maior) { maior vet[i]; indice i; } } retorne indice; } principal { real vetor[6] = {3.0, 4.3, 5.6, 2.8, 7.9, 3.4}; inteiro posicao; posicao encontraMaior( vetor, 6) imprima("Maior valor esta na posicao ", posicao); } Inicialmente são criadas as variáveis 19 Exercício 1 - Teste de Mesa int encontraMaior (real vet[], inteiro tam) { inteiro indice, i; real maior = vet[0]; indice 0; para (i 1; i < tam; i i+1) faça { se( vet[i] > maior) { maior vet[i]; indice i; } } retorne indice; } principal { real vetor[6] = {3.0, 4.3, 5.6, 2.8, 7.9, 3.4}; inteiro posicao; posicao encontraMaior( vetor, 6) imprima("Maior valor esta na posicao ", posicao); } Chama a função encontraMaior 20 Exercício 1 - Teste de Mesa int encontraMaior (real vet[], inteiro tam) { inteiro indice, i; real maior = vet[0]; indice 0; para (i 1; i < tam; i i+1) faça { se( vet[i] > maior) { maior vet[i]; indice i; } } retorne indice; } principal { real vetor[6] = {3.0, 4.3, 5.6, 2.8, 7.9, 3.4}; inteiro posicao; posicao encontraMaior( vetor, 6) imprima("Maior valor esta na posicao ", posicao); } Vetor e seu tamanho são passados como parâmetro 21 Exercício 1 - Teste de Mesa int encontraMaior (real vet[], inteiro tam) { inteiro indice, i; real maior = vet[0]; indice 0; para (i 1; i < tam; i i+1) faça { se( vet[i] > maior) { maior vet[i]; indice i; } } retorne indice; } principal { real vetor[6] = {3.0, 4.3, 5.6, 2.8, 7.9, 3.4}; inteiro posicao; posicao encontraMaior( vetor, 6) imprima("Maior valor esta na posicao ", posicao); } Variáveis maior = 3.0 indice = 0 Variávies locais da função são inicializadas 22 Exercício 1 - Teste de Mesa int encontraMaior (real vet[], inteiro tam) { inteiro indice, i; real maior = vet[0]; indice 0; para (i 1; i < tam; i i+1) faça { se(