Lógica de Programação Aula4

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):