Baixe o app para aproveitar ainda mais
Prévia do material em texto
Lógica de Programação Aula 4 Estrutura de Dados Prof Carlos Lahoz Baseada no Livro de André Forbellone & Henri Eberspacher, Person, São Paulo, 2005 Estrutura de Dados Tipos de dados construidos a partir de composição dos tipos primitivos: estrutura de dados. Necessita se criar uma nova estrutura (tipo primitivo) de dados para representar este conjunto homogeneo de dados. Exemplo figurativo: uma variável composta (alcatéia) com um conjunto de elementos (lobos) , que são da mesma espécie. Como se fosse tipo ALCATEIA = lobo [de 1 até 20] de animal ALCATEIA: vALCATEIA Estrutura de Dados Variaveis compostas UNIDIMENSIONAIS Estrutura de uma unica dimensão –> vetores. Um vetor é uma estrutura de dados utilizada para representar certa quantidade de variáveis de valores homogêneos, ou seja: um conjunto de variáveis, todas do mesmo tipo. Um vetor é como uma coleção de gavetas numeradas de um mesmo armário. Cada gaveta é capaz de armazenar um valor e tem o seu “endereço”. O “endereço” de cada gaveta é conhecido como índice e serve para identificar qual posição do armário se quer acessar. Estrutura de Dados Vetores No vetor abaixo temos, por exemplo, armazenado no índice “2” o valor “9.3”. Note que, como declaramos um vetor com 10 posições,os índices variam de 0 a 9. Assim, para armazenar o valor 8.5 na primeira posição do nosso vetor, seria utilizado o comando: notas[0] = 8.5; Estrutura de Dados Exemplo de vetor VCLASSE do tipo construído CLASSE, onde a primeira posição é 1 (LI) e a ultima posição é 40 (LF) (vetor de 40 posições reais) tipo CLASSE = vetor [1..40] de reais //definição de vetor de num reais CLASSE: VCLASSE; //declaração de variável vetor Vetor VCLASSE Estrutura de Dados Vetor: LI e LF devem ser constantes inteiras, sendo LI<LF. O numero de elementos do vetor será dado por LF-LI+1. É importante não confundir o índice com o elemento.. O índice é a posição do vetor, enquanto que o elemento é o que está contido naquela posição, Estrutura de Dados Exemplo de calculo de media de uma classe de 10 alunos e imprimir as notas acima da média calculada (sem vetor). Para calcular a média, seria: Estrutura de Dados Exemplo de calculo de media de uma classe de 10 alunos O Segundo passo: problema!! Para proceder a contagem dos alunos com nota acima da média, faz-se necessário a comparação de cada uma das dez notas com o conteúdo da variável MAT. Todas as notas foram lidas em uma mesma variável (MA) e seu valor foi acumulado em uma segunda variável (ACM), a fim de poder calcular a média (MAT). Isto implica que, ao ter calculado a média, não teríamos acesso às nove notas anteriores que o algoritmo utilizou. Estrutura de Dados Exemplo de calculo de media de uma classe de 10 alunos. Parte das “notas acima” cont.... Estrutura de Dados Exemplo de calculo de media de uma classe de 10 alunos. Parte das “notas acima” cont.... Estrutura de Dados Exemplo de calculo de media de uma classe de 10 alunos. Parte das “notas acima” Estrutura de Dados Exemplo de calculo de media de uma classe de 10 alunos. Este tipo de solução torna-se impraticável para uma grande quantidade de notas. Seria muito incoerente usar uma única variável que comportasse muitos dados , isto é um vetor armazenando cada nota em uma posição diferente do mesmo. Para acessar os elemento de um vetor, basta utilizar uma variavel com indice, ao qual teria o acesso as informações de acordo com a posição do element no vetor. Estrutura de Dados Exemplo de cálculo de media de uma classe de 10 alunos, usando vetor: cont... Estrutura de Dados Exemplo de cálculo de media de uma classe de 10 alunos, usando vetor: Estrutura de Dados Exercicio: Elabore um algoritmo que leia, some e imprima o resultado da soma entre dois vetores inteiros de 50 posições (soma de vetores). Dica: para simplificação, faça a soma de um vetor de 5 elementos Estrutura de Dados Exercicio: Construa um algoritmo que preencha um vetor de 100 elementos inteiros, colocando 1 na posição correspondente a um número impar e 0 na posição correspondente a um número par. Estrutura de Dados Exercicio: Sendo o vetor V igual a: E as variaveis X=2 e Y=4, escreva o valor correspondente a: h) V [ V [X + Y] ] i) V [X + Y] j) V [8 – V [2] ] l) V [V [ 4 ] ] m) V [V [V [ 7 ] ] ] n) V [ V [1] * V [4] ] o) V [X + 4] a) V [X + 1] b) V [X + 2] c) V [X + 3] d) V [X * 4] e) V [X * 1] f) V [ X * 2] g) V [X * 3] = 8 = 3 = 10 = 21 = 6 = 3 = 9 = 33 = 9 = 6 = 8 = 6 = 9 = 9 Estrutura de Dados Exercicio: Criar um programa que efetue a leitura dos nomes de 20 pessoas e em seguida apresenta-los na mesma ordem em que foram informados. Algoritmo 1. Definir a variável i do tipo inteiro para controlar a malha de repetição; 2. Definir a matriz NOME do tipo literal para 20 elementos; 3. Iniciar o programa, fazendo a leitura dos 20 nomes; 4. Apresentar após a leitura, os 20 nomes. Estrutura de Dados Exercicio: Programa que efetue a leitura dos nomes de 20 pessoas e em seguida apresenta os nomes (em Visualg) Estrutura de Dados Tendo construído o programa de entrada e saída dos 20 nomes na matriz, seria bastante útil que, antes de apresenta-los, o programa efetuasse o processamento da classificação alfabética, apresentando os nomes em ordem, independentemente daquela em que foram informados, facilitando desta forma a localização de algum nome, quando for efetuada uma pesquisa visual. Existem vários métodos para obter a ordenação de elementos de uma matriz. O método mais simples de ordenação consiste na comparação de cada elemento com todos os elementos subseqüentes. Sendo o elemento comparado menor para ordenação decrescente, ou maior para ordenação crescente que o atual, ele será trocado de posição com o outro. A ordenação considerada é alfabética, devendo essa ser crescente, ou seja, de A até Z. Estrutura de Dados Tendo construído o programa de entrada e saída dos 20 nomes na matriz, seria bastante útil que, antes de apresenta-los, o programa efetuasse o processamento da classificação alfabética, apresentando os nomes em ordem, independentemente daquela em que foram informados, facilitando desta forma a localização de algum nome, quando for efetuada uma pesquisa visual. Estrutura de Dados Algoritmo de ordenação 1. Definir a variável i do tipo inteira para controlar a malha de repetição; 2. Definir a matriz NOME do tipo literal para 20 elementos; 3. Iniciar o programa, fazendo a leitura dos 20 nomes; 4. Colocar em ordem crescente os elementos da matriz; 5. Apresentar após a leitura, os 20 nomes ordenados. Cuidado com o passo 4!!!! Estrutura de Dados Ordenação É importante que se estabeleça adequadamente o quarto passo do algoritmo, ou seja, como fazer para colocar os elementos em ordem crescente. A principio, basta comparar um elemento com os demais subseqüentes...mas iso necessita ser feito com alguma cautela. Imagine um problema um pouco menor: “Colocar em ordem crescente 5 valores numéricos armazenados numa matriz A e apresentá-los”. Estrutura de Dados Ordenação Os valores estão armazenados na ordem: 9, 8, 7, 5 e 3 e deverão ser apresentados na ordem 3. 5, 7, 8 e 9.Para efetuar o processo de troca, é necessário aplicar o método de propriedade distributiva. Sendo assim, o elemento que estiver em A[1] deverá ser comparado com os elementos que estiverem em A[2], A[3], A[4] e A[5]. Depois, o elemento que estiver em A[2]não necessita ser comparado com o elemento que estiver em A[1], pois já foram anteriormente comparados, passando a ser comparado somente com os elementos que estiverem em A[3], A[4] e A[5]. Na seqüência, o elemento que estiver em A[3] é comparado com os elementos que estiverem em A[4] e A[5] e por fim o elemento que estiver em A[4] é comparado com elemento que estiver em A[5]. Estrutura de Dados Ordenação Seguindo este conceito, basta comparar o valor do elemento armazenado em A[1] com o valor do elemento armazenado em A[2]. Se o primeiro for maior que o segundo, então trocam-se os seus valores. Como a condição de troca é verdadeira, o elemento 9 de A[1] é maior que o elemento 8 de A[2], passa-se para A[1] o elemento 8 e para A[2] passa-se o elemento 9, desta forma os valores dentro da matriz passaram a ter a seguinte formação: Estrutura de Dados Ordenação Seguindo a regra de ordenação, o atual valor de A[1] deverá ser comparado com o próximo valor após a sua última comparação. Sendo assim, deverá ser comparado com o valor existente em A[3]. O atual valor do elemento de A[1] é maior que o valor do elemento de A[3]. Ou seja, 8 é maior que 7. Efetua-se então a sua troca, ficando A[1] com o elemento de valor 7 e A[3] com o elemento de valor 8. Assim sendo,a matriz passa a ter a seguinte formação: Estrutura de Dados Ordenação Agora deverão ser comparados os valores dos elementos armazenados nas posições A[1] e A[4]. O valor do elemento 7 de A[1] é maior que o valor do elemento 5 de A[4]. Eles são trocados, passando A[1] a possuir o elemento 5 e A[4] a possuir o elemento 7. A matriz passa a ter a seguinte formação: Estrutura de Dados Ordenação Observe que ate aqui os elementos comparados foram sendo trocados de posição, estando agora em A[1] o elemento de valor 5 e que será mudado mais uma vez por ser maior que o valor do elemento 3 armazenado em A[5]. Desta forma, a matriz passa a ter a seguinte formação: Estrutura de Dados Ordenação A partir deste ponto o elemento de valor 3 armazenado em A[1] não necessitará mais ser comparado. Assim, deverá ser pego o atual valor do elemento da posição A[2] e ser comparado sucessivamente com todos os outros elementos restantes. Desta forma, o valor do elemento armazenado em A[2] deverá ser comparado com os elementos armazenados em A[3], A[4] e A[5], segundo a regra da aplicação de propriedade distributiva. Estrutura de Dados Ordenação Comparando o valor do elemento 9 da posição A[2] com o elemento 8 da posição A[3] e efetuando a troca de forma que 8 esteja em A[2] e 9 esteja em A[3], a matriz passa a ter a seguinte formação: Estrutura de Dados Ordenação Comparando o valor do elemento 9 da posição A[2] com o elemento 8 da posição A[3] e efetuando a troca de forma que 8 esteja em A[2] e 9 esteja em A[3]. Em seguida o atual valor do elemento de A[2] deve ser comparado com o valor do elemento de A[4], ficando A[2] com 7 e A[4] com 8. O atual valor de A[2] é 7 e será comparado com o valor do elemento A[5] que é 5, passando A[2] para 5 e A[5] com 7 Estrutura de Dados Ordenação Agora será efetuada a comparação da próxima posição, A[3] com A[4] e A[5]. Sendo assim, o valor do elemento da posição A[3] será comparado com o valor da posição A[4]. Como 9 é maior que 8 eles serão trocados: O valor do A[3] é comparado com o valor A[5], trocando o valor 7 por 8 Estrutura de Dados Ordenação Tendo sido efetuadas todas as comparações de A[3] com A[4] e A[5], fica somente a última comparação que é A[4] com A[5], cujos valores são trocados, passando A[4] com o valor 8 e A[5] com o valor 9. Estrutura de Dados Ordenação. Voltando ao caso da ordenação do vetor de nomes, utiliza-se o algoritmo de troca. O algoritmo de troca, utiliza a instrução de decisão: se NOME[i] > NOME[j] então. Após a verificação desta condição, sendo o primeiro nome maior que o segundo, efetua-se então o algoritmo de troca. Estrutura de Dados Ordenação. Considere o vetor NOME[i] como o valor “Carlos” e o vetor NOME[j] com o valor “Alberto”. Ao final NOME[i] deverá estar com “Alberto” e NOME[j] deverá estar com “Carlos”. Para conseguir este efeito, é necessária a utilização de uma variável de apoio, a qual será chamada X. Para que o vetor NOME[i] fique livre para receber o valor do vetor NOME[j]. X deverá receber o valor do vetor NOME[i]. Assim sendo, X passa a ser “Carlos”. Neste momento pode-se atribuir o valor de NOME[j] em NOME[i]. Desta forma o vetor NOME[i] passa a ter o valor “Alberto”. Em seguida o vetor NOME[j] recebe o valor que está em X. Estrutura de Dados Exercicio de ordenação de nomes. Complete o algoritmo abaixo de ordenação de nomes. Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS Imagine que o vetor unidimensional seria a estrutura de um prédio, onde cada andar seria a posição de um um elemento do vetor. Isto é no prédio V, teríamos o primeiro andar V[1], o segundo V[2],etc. Se quisessemos percorrer os andares é só mudar a posição do vetor (como em um elevador). Mas e se quisessemos localizar os apartamentos deste prédio? O apartamento 1 do primerio andar, o apartamento 2 do primeiro andar,.....e assim por diante... Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS Teriamos uma estrutura multidimensional: andares e apartamentos. Seria uma matriz . É necessário definir um tipo construido e depois declararar uma ou mais variáveis, associando identificadores . Sendo que o numero de elementos é o produto do número de elementos de cada dimensão. (LF1-LI1+1) * (LF2-LI2+1)*...* (LFn-LIn+1) Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS Exemplos: Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS Manipulação: para acessar cada elemento da matriz composta multidimensional é preciso, como em um edificio, do nome, andar e apartamento. Considerando uma estrutura bidimensional (dois indices: andar e apartamento), o primeiro indice indica a linha e o segundo a coluna. Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS Exemplo: em uma matriz chamada MSALA, o elemento MSALA[2,3] se encontra na linha 2, coluna 3 Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS. Exercicio: Construa um algoritmo que efetue a leitura, a soma e a impressão do resultado entre duas matrizes inteiras que comportem 25 elementos Estrutura de Dados algoritmo "semnome" // Função : // Autor : // Data : 07/10/2017 // Seção de Declarações var maA: vetor[1..3,1..3] de inteiro maB: vetor[1..3,1..3] de inteiro maR: vetor[1..3,1..3] de inteiro i,j: inteiro inicio // Seção de Comandos Escreval("Informe os valores da Matriz A:") Para i de 1 ate 3 faca Para j de 1 ate 3 faca Escreva("Matriz A [",i ," ,",j," ] : ") Leia(maA[i,j]) Fimpara Fimpara Escreval("") Escreval("Informe os valores da Matriz B:") Para i de 1 ate 3 faca Para j de 1 ate 3 faca Escreva("Matriz B [",i ," ,",j," ] : ") Leia(maB[i,j]) Fimpara Fimpara Escreval("") Escreval("Matriz Resultante (Matriz A + Matriz B)") Para i de 1 ate 3 faca Para j de 1 ate 3 faca maR[i,j] <- ( maA[i,j] + maB[i,j] ) Escreval("Matriz R [",i ," ,",j," ] : ", maR[i,j]) Fimpara Fimpara fimalgoritmo Exercicio: CONT – em Visualg Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS Exemplo: em uma matriz tridimensional tipo M = matriz [1..3, 2..4, 3.. 4] de reais M: MAT Para matrizes com 3 dimensões, repete-se a estrutura bidimensional o mesmo numero de vezes que onumero de elementos da 3a dimensão, numerando-se de acordo com os limites especificados Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS Exemplo: MAT[1..3, 2..4, 3..4] Os elementos em destaque na Fiigura é o MAT[2,3,4] Estrutura de Dados Variaveis compostas MULTIDIMENSIONAIS Olhando mais cuidadosamente, percebe-se que uma estrutura composta multidimensional é, na realidade, um conjunto de vetores que são determinados para cada intervalo que compõe o tipo matriz. Para utilizar o vetor, utiliza-se um unico laço de repetição, fazendo com que haja variação em seu indice. Com uma estrutura multidimensional, possui mais de um indice, faz- se necessário mais de um laço de repetição, no mesmo número do número de dimensões da matriz. Estrutura de Dados Matriz MULTIDIMENSIONAL Sendo tipo MAT = matriz [0..1, 1..4, 1..3] de inteiros; MAT: M; Determine: M [0, M[0,3,1], 1]= M [ M[0,3,2] 2,3]= M [1,1, M[0,4,3]]= M [1,1,2]= M [0,3,3]= M [1,4,1]= -3 1 0 3 -1 5 Estrutura de Dados Matriz MULTIDIMENSIONAL Desenhe uma representação para as seguintes matrizes e coloque os valores determinados nos devidos lugares. a) tipo MAT1=matriz[1..4, 1..4, 1..4] de caracteres; MAT1: MA; MA[1,2,1] <- “mm”; MA[4,3,2] <- “nn”; MA[3,1,3] <- “aa”; MA[1,4,1] <- “bb”; MA[2,2,4] <- “oo”; Estrutura de Dados Matriz MULTIDIMENSIONAL Desenhe uma representação para as seguintes matrizes e coloque os valores determinados nos devidos lugares. (CONT) Estrutura de Dados Matriz MULTIDIMENSIONAL Exercicio: O tempo que um determinado avião dispensa para percorrer o trecho entre duas localidades distintas está disponivel através da seguinte tabela: Construa um algoritmo que leia a tabela e informe ao usuário o tempo necessário para percorrer duas cidades por ele fornecedias e para quando ele fornecer duas cidades iguais (origem e destino) Obs: matriz[1..4,1..4] de inteiros Estrutura de Dados Matriz MULTIDIMENSIONAL Exercicio: Tempo entre duas localidades distintas (CONT) Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS: composto por campos que especificam cada uma das informações necessárias. Uma variável do tipo registro é uma variável composta, pois engloba um conjunto de dados, e é heterogênea, pois cada campo pode ser de um tipo primitivo diferente. Exemplo, seria um bilhete de onibus com diversas informações do passageiro e da viagem Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS. Para definir um tipo registro, usa-se a seguinte estrutura: Onde: idRegistro é o nome associado ao tipo registro construido tipo primitivo é qualquer um dos tipos basicos anteriormente definidos IdCampo: nome associado a cada campo do registro Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS. Exemplo do bilhete de onibus Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS Manipulação de REGISTROS. Em determinados momentos, podemos precisar de todas as informações contidas no registro (Embarque) ou de apenas algum campo do registro (com frequência, o numero da poltrona). Acessando genericamente o registro: Acessando um campo especifico do registro (utilizar o “.” para identificar o campo: Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS Manipulação de REGISTROS. Exemplo: Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS de Conjuntos. Além dos registros possuirem campos de dados do tipo primitivo, eles podem ser compostos de outros tipos construídos. Podemos incluir vetores e matrizes no registro, como em registros de estoque semanal de um item. Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS de Conjuntos (CONT). Para definir este tipo de registro, precisamos definir um tipo construido vetor de 6 posições (semanal), e depois o tipo registro. Exemplo: Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS de Conjuntos (CONT). Exercicio: Modificar o registro de estoque de um produto a fim de que possa contar as baixas de quatro semanas, utilizando um tipo construido matriz (conforme, abaixo) Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS de Conjuntos (CONT). Exercicio de registro de estoque de um produto a com baixas de quatro semanas(CONT): Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS de Conjuntos (CONT). Exercicio de registro de estoque com baixas de quatro semanas (CONT): Como acessar quanto foi vendido do produto no terceiro dia da quarta semana? Construir o trecho do algoritmo que, usando a definição do produto, escreva o nome do produto, o código, o preço e as baixas da segunda semana. Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS de Conjuntos (CONT). Exercício do algoritmo com as baixas da segunda semana(CONT): . Estrutura de Dados Variáveis COMPOSTAS HETEROGÊNEAS REGISTROS de Conjuntos (CONT). Exercício do algoritmo que totaliza por dia de semana todos os dias do mes (CONT):
Compartilhar