ESTRUTURA DE DADOS
EXERCÍCIOS e MATRIZES
Professor Victor Sotero
Estrutura de Dados
1
ALGUNS EXEMPLOS DE VETOR
Fazer um algoritmo que mostre os números
pares.
algoritmo pares
vet: vetor [1..10] de inteiro
i: inteiro
inicio
para i<- 1 ate 10 faca
Escreval ("Digite um numero")
leia(vet[i])
fimpara
PARA i<- 1 ate 10 faca
se (vet[i] mod 2=0) entao
Escreval(vet[i])
fimse
fimpara
fim
Estrutura de Dados
2
EXERCÍCIOS
1-Faça um algoritmo que leia dois vetores de
seis elementos inteiros e calcule a soma de
cada elemento, armazenando em um terceiro
vetor. O primeiro elemento do vetor A deve
ser somado como primeiro elemento do vetor
B e assim sucessivamente.
Estrutura de Dados
3
RESPOSTA
Algoritmo"Soma_vetores“
Declare
i: inteiro
vetor_A: Vetor [1..6] de real
vetor_B: Vetor [1..6] de real
vetor_R: Vetor [1..6] de real
Inicio
Para i := 1 ate 6 Faca
Escreva("entre com o valor para a posição ", i ," no vetor A: ")
Leia(vetor_A[i])
Escreva ("entre com o valor para a posição ", i ,“no vetor B: ")
Leia (vetor_B[i])
Fimpara
Para i := 1 ate 6 Faca
vetor_R[i]<- vetor_A[i] + vetor_B[i]
Fimpara
Para i de 1 ate 6 faca
Escreval( i , " - " , vetor_R[ i ] )
Fimpara
Fim
Estrutura de Dados
4
MATRIZ
Os vetores, ou variáveis compostas
unidimensionais, têm como principal
característica a necessidade de apenas um
índice para endereçamento. Uma estrutura
que precise de mais de um índice, como no
caso de matrizes, será denominada estrutura
composta multidimensional.
Estrutura de Dados
5
ATRIBUIÇÃO DE MATRIZES
• A atribuição é uma das formas de qualquer
variável armazenar algum valor.
a) mat[3,4] ← 3.75
b) Para i de 1 até 5 faça
Para j de 1 até 5 faça
Se(i = j) então
x[i,j] ← 1
senão
x[i,j] ← 0
Fim_se
Fim_para
Fim_para
Estrutura de Dados
6
LEITURA DE MATRIZES
a) Para i de 1 até 20 faça
Para j de 1 até 15 faça
Leia ( mat[i,j] )
Fim_para
Fim_para
b) Escreva(“Digite números positivos:”)
Para a de 1 até 10 faça
Para b de 1 até 10 faça
Escreva(“Atenção! Positivo.”)
Leia( x )
Até ( x > 0 )
matriz[a,b] ← x
Fim_para
Fim_para
Estrutura de Dados
7
MATRIZ
Uma matriz é uma variável composta
homogênea multidimensional formada por
uma seqüência de variáveis, todas do mesmo
tipo, com o mesmo identificador (mesmo
nome) e alocadas seqüencialmente na
memória.
Estrutura de Dados
8
MATRIZ
Considerando que os andares de um prédio são
divididos em apartamentos temos uma
estrutura multidimensional. Para localizarmos
um indivíduo neste prédio precisaremos de
seu nome, o andar e o número do
apartamento. Considerando uma estrutura
bidimensional (dois índices: andar e
apartamento), o primeiro índice indica a linha
e o segundo, a coluna.
Estrutura de Dados
9
MATRIZES
Estrutura de Dados
10
EXEMPLO
algoritmo "matriz"
// Função :
// Autor :
// Data : 16/3/2007
// Seção de Declarações
var
matrizA: vetor[1..2,1..2] de inteiro
i,j: inteiro
inicio
escreval("Entre com os dados da matriz:")
para i <- 1 ate 2 faca //varre a linha da matri
para j <- 1 ate 2 faca //varre a coluna matriz
leia(matrizA[i,j])
fimpara
fimpara
escreval("A matriz digitada foi:")
para i <- 1 ate 2 faca
para j <- 1 ate 2 faca
escreva(matrizA[i,j])
fimpara
escreval("")
fimpara
// Seção de Comandos
fimalgoritmo
Estrutura de Dados
11
REGISTROS
• É uma variável composta heterogênea;
• Até então nós vimos estruturas de dados de
armazenamento de mesmo tipo. Os registros
armazenam estruturas de dados de tipos
diferentes;
• Como exemplo temos um formulário de
embarque de ônibus, onde terá informações
como horário, número da passagem, origem,
destino e etc...
Estrutura de Dados
12
REGISTROS
• Um registro é composto por campos que são
partes que especificam cada uma das
informações que o compões;
• Uma variável do tipo registro é uma variável
composto que armazena valores de diversos
tipo, logo heterogênea;
Estrutura de Dados
13
DECLARAÇÃO(REGISTROS)
• Primeiramente devemos declarar como é
construído o tipo, seguido dos campos
declarando suas variáveis com seus
respectivos tipos.
Nome associado ao tipo registro construído
• Ex.:
Representa o nome associado a
cada campo
tipo idregistro = registro
tipo primitivo : idcampo;
fimregistro;
Representa qualquer um dos
tipos básicos
Estrutura de Dados
14
EXEMPLO(REGISTRO)
• A representação da passagem de um ônibus,
usando registros seria:
//definição do tipo registro
tipo regEmbarque = registro
inteiro: Numpass, NumPoltrona, Idade;
caracter: Nome, Data, Origem, Destino;
fimregistro
//declaração da variável composta do tipo registro criado
regEmbarque: Embarque;
Estrutura de Dados
15
MANIPULAÇÃO DE REGISTROS
• Em algum momento podemos precisar especificamente de
algum campo do registro. Quando acessamos genericamente o
registro estamos referenciando obrigatoriamente todos os
campos.
Ex.: Leia(Embarque);
Escreva(Embarque);
• Para usarmos um campo específico devemos referenciar esse
campo, utilizando o ponto(.), separando o nome do registro do
nome do campo;
Ex.:Escreva(Embarque.Idade);
Se (Embarque.Idade<18) então
Escreva(Embarque.Nome, “é menor de idade”);
Fimse;
Estrutura de Dados
16
REGISTROS DE CONUNTOS
• Até então, vimos tipos de registros que aceitam diversos tipos
primitivos;
• Podemos também criar registros que aceitem tipos
construídos( vetor ou matriz);
• Entendo melhor: Digamos que temos um registro de estoque
de produto, e devemos saber a baixa do produto todo dia,
logo temos um campo numérico para isso. Podemos então
criar um vetor de 6 posições, que represente os dias da
semana.
Nome:_________________________________________________
Código:_________________________Preço:__________________
Baixa:
1
2
3
4
Estrutura de Dados
5
6
17
REGISTROS DE CONJUNTO
• Para definir o exemplo anterior, definimos um tipo de vetor;
• Inicialmente declaramos as posições(6), depois o tipo do registro,
definindo assim todos os campos que serão incluídos dentro do registro,
antes da variável composta:
//definição do vetor
tipo vDias = vetor[1..6] de inteiros;
//definição do tipo registro
tipo regProduto = registro
inteiro: codigo;
caracter: nome;
real: preco;
vdias: baixa; // tipo do vetor definido
fimregistro;
// declaração da vairável composta do tipo registro;
regproduto: Produto;
Estrutura de Dados
18
REGISTROS DE CONJUNTOS
• Registro de estoque de um produto que possa conter
as baixas referentes a 4 semanas, dessa forma
iremos utilizar uma matriz:
Nome:_________________________________________________
Código:_________________________Preço:__________________
Baixa:
1
2
3
4
1
2
3
4
Estrutura de Dados
5
6
19
REGISTRO DE CONJUNTOS
• Declaração:
//definição da matriz
tipo matDias = matriz[1..4,1..6] de inteiros;
//definição do tipo do registro
tipo regProduto = registro;
inteiro: Codigo;
caracter: Nome;
real: Preco;
matDias: Baixa; //do tipo matriz definido
fimregistro;
//declaração da variável composta do tipo registro
regProduto: Produto;
Estrutura de Dados
20
MANIPULAÇÃO (REGISTRO DE
CONJUNTOS)
• É da mesma forma que a manipulação das
estruturas de dados definidas anteriormente;
• E.: Para acessar quanto foi vendido do
produto no terceiro dia da quarta semana,
teríamos:
Produto.baixa[4,3];
Estrutura de Dados
21
MANIPULAÇÃO(REGISTRO DE
CONJUNTOS)
Estrutura de Dados
22
Estrutura de Dados
23
Estrutura de Dados
24
SUB-ROTINAS
• As subrotinas são divisões dos algoritmos, que
são utilizadas para:
• Facilitar a manutenção dos algoritmos
• Dividir as tarefas.
• Dar maior organização aos algoritmos
• Para reaproveitar os Algoritmos.
• Existem 2 tipos Basicos de Subrotinas:
Estrutura de Dados
25
TIPOS DE SUB ROTINAS
Função:
È a subrotina que executa seus procedimentos, e ao final
retorna um valor.
Procedimento:
È a subrotina que não faz retorno nenhum. Apenas executa os
procedimentos a ela associados.
Para que possamos trabalhar com as subrotinas serão
necessárias algumas alterações nos nossos algoritmos.
Estrutura de Dados
26
ARGUMENTOS
• Um argumento é um tipo especial de variável utilizada em um algoritmo.
Ele é especial porque dentro dele estará um valor predeterminado pelo
usuário que esta utilizando o algoritmo.
• Isto quer dizer que o argumento é um valor que será colocado dentro de
uma variável pelo usuário do algoritmo, que será utilizado pelo algoritmo
como uma variável comum.
• Em tempo de processamento, isto quer dizer que os argumento serão
passados como parâmetros na linha de comando da chamada do
programa.
• A única diferença do argumento para uma variável comum é que ele já
vem com um valor armazenado desde o inicio do algoritmo, enquanto que
as outras variáveis necessitam ser inicializadas antes de serem usadas.
• No decorrer do algoritmo os argumentos poderão ser utilizados e
alterados exatamente como as variáveis comuns, e inclusive deverão ser
declarados.
Estrutura de Dados
27
LISTAS
É uma estrutura de dados linear que permite
representar um conjunto de informações de forma a
preservar uma relação de ordem entre eles. Esta
estrutura deve também suportar os 4 tipos de
atualizações :
•
•
Inclusão
•
Exclusão
•
Alteração
• Atravessamento.
Estrutura de Dados
28
LISTAS (REPRESENTAÇÃO)
Exemplo
LISTA=(A,B,C,D,E)
A=>B=>C=>D=>E
Para representar as lista dentro de nossos algoritmos nós vamos
utilizar a estrutura do tipo matriz que foi vista anteriormente.
As listas podem ser alocadas segundo duas relações:
Relação de Contigüidade
Relação de Encadeamento.
Estrutura de Dados
29
RELAÇÃO DE CONTINGUIDADE
É a forma mais simples de se relacionar os elementos de uma lista.
Nela um elemento aponta sempre para o seu sucessor seqüencial.
Desta forma a nossa lista estará sempre na sua ordem física, ou seja
os elementos estarão dispostos fisicamente dentro da lista de
maneira que a ordem entre os elementos seja mantida.
Dentro de uma lista nós devemos permitir 4 operações básicas:
Inclusão
Exclusão
Alteração
Atravessamento
Estrutura de Dados
30
ATRAVESSAMENTO
A operação de atravessamentos consiste em
percorrer toda a lista, do seu começo até o
seu final, visitando todos os seus elementos.
O atravessamento começa pelo primeiro
elemento da lista, mostra este elemento e vai
sempre mostrado os próximos elementos até
chegar no ultimo(N)
Estrutura de Dados
31
EXEMPLO
Estrutura de Dados
32
INCLUSÃO EM LINHAS CONTÍGUAS
A inclusão é a operação que visa a colocação de um novo
elemento dentro da lista de maneira que a ordem entre os
elementos seja mantida.
Se a inclusão ocorre no final de lista , o seu procedimento é
fácil. Porem se a inclusão acontecer no meio da lista, será
necessário que todos os elementos após aquele que foi
incluído sejam deslocados uma casa para baixo.
Note que para que possamos fazer uma inclusão nó
devemos declarar a lista com 1 elemento a mais do que ele
já possui, para reservar lugar para o novo elemento que
será incluído.
Estrutura de Dados
33
PASSOS PARA INCLUSÃO
1-Criar um espaço em branco no final da lista
2-Aceitar a letra que será incluída (ELEMENTO_NOVO)
3-Achar a posição de inclusão da letra na lista (POS)
4-Fazer uma critica para ver se a letra já não existe na lista
5-Remanejar todos os elementos abaixo da posição de
inclusão uma posição para baixo començando de baixo para
cima.
6-Incluir o elemento na posição de inclusão.
8-N: = N + 1
Estrutura de Dados
34