Aula04 Estrutura dados p1

Prévia do material em texto

Programação de Computadores
Estrutura de Dados - Parte 1
Prof. Dr. Erivelton Geraldo Nepomuceno
Depto. Engenharia Elétrica
Sala 4.23 EL – Prédio do DEPEL
http://www.ufsj.edu.br/nepomuceno 
nepomuceno@ufsj.edu.br 
1/28
Recapitulando: variáveis...
● Representação simbólica de valores
● Na matemática: incógnitas
● Nos algoritmos:
○ Valores que se modificam ao longo do tempo
○ Apenas 1 valor a cada vez
○ Correspondem uma posição/espaço na memória
○ Identificada pelo identificador
■ Ex.: cálculo da área de um retângulo: Área = base.altura, 
podemos usar os identificadores A, b, h
2/28
VARIÁVEIS ESTUDADAS: UM ÚNICO 
VALOR POR VEZ E DE APENAS UM TIPO
E QUANDO DESEJARMOS 
ARMAZENAR GRUPOS DE DADOS 
RELACIONADOS?
NOVAS ESTRUTURAS DE DADOS:
VARIÁVEIS COMPOSTAS
3/28
Comecemos com um exemplo...
Calcular a média das notas de 10 alunos e determinar o 
número de alunos com nota superior à media calculada
Algoritmo
 Declaração de variáveis
 Iniciar variáveis
 repita
 se I > 10
 então interrompa
 fim se
 leia NOTA
 Acumule NOTA
 Conte as notas lidas
 fim repita
 Calcule a média das notas
 Conte os alunos com nota superior à média
 Escreva a média e o número de alunos com média superior
fim algoritmo 4/28
Ref. Acumule NOTA
 SOMA ← SOMA + NOTA
fim ref.
Ref. Conte as notas lidas
 I ← I + 1
fim ref.
Ref. Calcule a média das notas
 MEDIA ← SOMA / 10
fim ref.
Ref. Iniciar variáveis
 I ← 0
 SOMA ← 0
 QUANTIDADE ← 0
fim ref.
Ref. Declaração de variáveis
 declare I, MEDIA, NOTA, QUANTIDADE, SOMA numérico
fim ref. 5/28
Ref. Conte os alunos com nota superior à média
se NOTA > MEDIA ??? 
COMO PROCEDER? 
É NECESSÁRIO COMPARAR CADA 
NOTA À MÉDIA CALCULADA
SOLICITA NOVAS 
ENTRADAS DO USUÁRIO!
COMO GARANTIR QUE 
NÃO HAJA ERRO?
REFAZ A LEITURA DO 
ARQUIVO DE DADOS!
COMO GARANTIR QUE 
DADOS SE MANTÊM?
OPERAÇÃO 
COMPUTACIONALMENTE 
ONEROSA!
ELE JÁ TEVE ESSE 
TRABALHO!
INC
ON
SIS
TÊN
CIA
6/28
Eis uma solução (mas não muito inteligente...)
Algoritmo
 declare MÉDIA, NOTA1, NOTA2, NOTA3, NOTA4, NOTA5,
 NOTA6, NOTA7, NOTA8, NOTA 9, NOTA10,
 QUANTIDADE, SOMA numérico
 QUANTIDADE ← 0
 leia NOTA1, NOTA2, NOTA3, NOTA4, NOTA5,
 NOTA6, NOTA7, NOTA8, NOTA 9, NOTA10
 SOMA ← NOTA1+NOTA2+NOTA3+NOTA4+NOTA5+
 NOTA6+NOTA7+NOTA8+NOTA 9,+NOTA10
 MEDIA ← SOMA/10
 se NOTA1 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 se NOTA2 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
7/28
 se NOTA3 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 se NOTA4 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 se NOTA5 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 se NOTA6 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 se NOTA7 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 se NOTA8 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
8/28
 se NOTA9 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 se NOTA10 > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 
 escreva MEDIA, QUANTIDADE
fim algoritmo
E se fossem 100 notas?
E se fossem 1000 notas?
E se fosse uma quantidade variável de notas?
9/28
Variáveis compostas homogêneas
● Correspondem a várias posições de memória
● Conjunto de posições é referenciado por um 
identificador
● Posições são referenciadas por índices
○ Ex.: NOTA[N] (n-ésima posição da variável)
○ N é uma constante ou variável numérica tipo inteiro
● Todo conteúdo é de um mesmo tipo
NOTA[3] = 90
N ← 10
NOTA[N] = 86
10/28
Sintaxe
● Declaração
● Exemplo
● Atribuição
● Exemplo
declare <identificador>[<Menor índice:Maior índice>] <nome do tipo>
declare NOTA[1:10] numérico
<identificador>[<Índice>] ← <variável ou constante>
NOTA[5] ← 99
11/28
12/28
Algoritmo
 ...
 declare NOTA[1:10] numérico
 declare SOMA, I, MEDIA numérico
 SOMA ← 0
 para I=1 até 10 faça
 leia NOTA[I];
 SOMA ← SOMA + NOTA[I]
 fim para
 MEDIA ← SOMA / 10
 escreva MEDIA
 ...
Fim algoritmo
Exemplo:
Escrever o trecho do algoritmo que leia um conjunto de 10 
notas, armazene-as na variável composta
NOTA e calcule a sua média
13/28
Calcular a média das notas de 10 alunos e determinar o 
número de alunos com nota superior à media calculada
Algoritmo
 declare NOTA[1:10] numérico
 declare SOMA, I, MEDIA, QUANTIDADE numérico
 SOMA ← 0
 QUANTIDADE ← 0
 para I=1 até 10 faça
 leia NOTA[I]
 SOMA ← SOMA + NOTA[I]
 fim para
 MEDIA ← SOMA / 10
 
 para I=1 até 10 faça
 se NOTA[I] > MEDIA
 então QUANTIDADE ← QUANTIDADE + 1
 fim se
 fim para
 escreva MEDIA, QUANTIDADE
fim algoritmo 14/28
Variáveis compostas unidimensionais
● Só necessitam de um índice
● “Vetores”
● Exemplos:
15/28
E NOS CASOS EM QUE O CONJUNTO DE 
DADOS TEM MAIS DE UMA DIMENSÃO?
POR EXEMPLO: AS NOTAS DE 10 
ALUNOS EM 3 PROVAS DISTINTAS
ESTRUTURAS DE DADOS 
MULTIDIMENSIONAIS!
16/28
Variáveis compostas multidimensionais
● Necessitam mais de um índice para referenciar suas 
posições
● Duas, três ou mais dimensões → “Matrizes”
● Sintaxe para declaração:
● Exemplo (10 alunos com 3 notas cada):
declare <identificador><[Ni1:Nf1, ... , Ni2:Nf2] 
<nome do tipo>
declare NOTAS[1:10, 1:3] numérico
17/28
Exemplos
 declare ESCANINHO[1:4,1:3] numérico
 ESCANINHO[4,3] ← 430 
 ESCANINHO[2,3] = 112
 ESCANINHO[4,4] é inválido
 declare LIVRO[1:4,1:3,1:2] numérico
 LIVRO[2,3,1] ← 15
 LIVRO[4,3,2] = 20
 LIVRO[1,2,3] é inválido
18/28
A planilha de custos
3,701015
0,4835042
1280,00135
13,5020210
17,8010102
Número do item
Quantidade do item
Custo unitário
 declare CUSTOS[1:5,1:3] numérico
 CUSTOS[4,3] ← 0,48 
 CUSTOS[2,3] = 13,50
→ Escreva um algoritmo que, lida esta 
planilha, calcule o gasto total por 
item, bem como o gasto total da obra.
→ Faça também para uma planilha 
com um número qualquer de linhas, 
com sinalizador de fim, sendo o 
número do item igual a -1
19/28
E SE FOSSE NECESSÁRIO A DESCRIÇÃO 
DO ITEM AO INVÉS DE UM NÚMERO
E SEU EU DESEJASSE INCLUIR OS 
DADOS DE POSSÍVEIS 
FORNECEDORES?
DADOS DE TIPOS DISTINTOS!
ESTRUTURA DE DADOS HETEROGÊNEA
20/28
Variáveis compostas heterogêneas
● Registros / estruturas
● Agrupamentos de dados logicamente 
relacionados
● Podem ser de tipos diferentes
● Cada dado é um componente ou campo do 
registro
<nome do identificador>.<nome do campo>
21/28
Registro: FICHA
Exemplo de dados: FICHA
22/28
Sintaxe
● Declaração
● Exemplo
● Atribuição
● Exemplo
declare <identificador> registro (<componentes>)
declare FICHA registro (INSCRICAO, NUMERO, 
CEP, CPF, HORAS numérico,
DEPENDENTE lógico
NOME, RUA, SEXO literal)
<identificador>.<campo> ← <variável ou constante>
FICHA.INSCRICAO ← 9214
23/28
Importante
● Um campo pode ser qualquer estrutura 
de dados, inclusive:
○ Variáveis simples
○ Variáveis compostas homogêneas
■ Unidimensionais
■ Multidimensionais
○ Outros registros
■ Nesse caso:
<nome do registro 1>.<nome do registro 2>.<nome do campo>
24/28
Exemplo
Declarar uma ficha de cadastro (CAD) com os seguintes campos:
Onde:
-ENDEREÇO é um registro contendo rua, 
número, e CEP 
-HT deve conter 3 valores, indicando o 
número de horas trabalhando em 3 
períodos distintos
Para acessar o CEP:
CAD.ENDERECO.CEP
Para acessar o 3º valorde HT
CAD.HT[3] 25/28
Conjunto de registros
● Agrupamento / arranjo de vários registros
● Variável composta homogênea em que cada 
“célula” (posição da memória) é todo um 
registro
● São referenciados por índices
26/28
Sintaxe
● Declaração
● Exemplo
● Atribuição
● Exemplo
declare <identificador>[<Menor índice:Maior índice>] 
<identificador do registro>
declare CLIENTE registro (NOME, RUA literal,
NUMERO, CEP, SALDO numérico)
declare CONTAS[1:5] CLIENTE
<identificador>[<índice].<campo do registro> 
← <variável ou constante>
CONTAS[3].SALDO ← -500
27/28
28/28