Linguagens de Programação e Estruturas de Dados - Aula 2

Prévia do material em texto

Tecnologia em Análise e 
Desenvolvimento de Sistemas
Linguagem de Programação e
Estrutura de dados
Profª.Me.Merris Mozer
TA1
Alocação Sequencial
Nesta aula será relembrado o funcionamento da 
alocação sequencial e apresentado o novo conceito 
sobre alocação encadeada.
Aula 2
 Listas Estáticas (Arranjo)
 Listas Dinâmicas (Ponteiros)
Tipo de Alocação (Armazenamento)
x
1
é o primeiro nodo;
x
n
é o último nodo;
x
k
precede x
k+1
;
Nodos são alocados em vetor;
x
k
e x
k+1
ocupam posições 
contínuas no vetor.
Alocação sequencial
Vetor V
V[1] V[2] V[3] V[4]
Adriano Karen Rogério
Começo Fim
V[1] V[2] V[3] V[4]
Fila-FIFO
TopoRogério
Adriano
Karen
V[1]
V[2]
V[3]
V[4]
Pilha - LIFO
Pilha - LIFO
LISTA DE PAGAMENTOS
Prestação do carro
Cartão de crédito
Conta de luz
Condomínio
TV a cabo
Supermercado
Pilha - LIFO
1-Prestação do carro
2-Cartão de crédito
3-Conta de luz
4-Condomínio 
5-TV a cabo 
6-Supermercado
Tecnologia em Análise e 
Desenvolvimento de Sistemas
Linguagem de Programação e
Estrutura de dados
Profª.Me.Merris Mozer
TA2
Alocação Encadeada
Existe uma diferente forma de representar 
a relação de precedência independente 
dos dados estarem alocados em posições contíguas 
de memória;
Alocação Encadeada
Uso de ALOCAÇÃO ENCADEADA – Criação de cadeias 
ou ligações entre os nodos;
Vantagens: Melhor ocupação de 
memória.
O que é alocação encadeada?
Mecanismo que estabelece a relação de 
precedência entre os nodos não de forma física, 
mas sim de forma lógica. 
A cada nodo xk será acrescido um campo contendo 
o endereço de memória de xk+1.
A relação entre os nodos deixa 
de ser uma relação de 
precedência simples para ser 
uma relação funcional de 
precedência.
Qualquer relação que, para cada
registro T1 leve a no máximo um
registro do tipo T2 será chamada de
relação funcional.
Primeiro elemento
E1 E2 E3
E4Último elemento
Tecnologia em Análise e 
Desenvolvimento de Sistemas
Linguagem de Programação e
Estrutura de dados
Profª.Me.Merris Mozer
TA3
Alocação Encadeada
Alocação sequencial:
 Nodo armazena apenas uma informação;
Comparando ...
Adriano
Adriano
Alocação encadeada:
 Nodo armazena informação e endereço do nodo 
seguinte;
Adriano
Parte do endereçamento: 
Dados tipo referência, 
ou seja, um indicador
de localização do próximo
nodo a ser trabalhado;
Parte da informação: 
dados tipo string, 
integer, real, etc ....
Parte do endereçamento será então a responsável 
por gerenciar todo o processo de percorrimento
dos dados armazenados.
Sabendo-se a localização apenas de um dos nodos 
poderemos acessar todos os seus nodos 
sucessores, mesmo esses estando totalmente 
dispersos na memória.
Valor de referência inicial 407 – Alfredo
Qual a relação funcional?
Adriano 1430105
Alfredo 1023407
Paula 998565
João 616
Janaina 616714
Cláudio 714897
Rogério 998
Sandra 8971023
Karen 5651430
Paulo 4072213
Valor de referência inicial 105 - Adriano
Qual a relação funcional?
Adriano 1430105
Alfredo 1023407
Paula 998565
João 616
Janaina 616714
Cláudio 714897
Rogério 998
Sandra 8971023
Karen 5651430
Paulo 4072213
Tecnologia em Análise e 
Desenvolvimento de Sistemas
Linguagem de Programação e
Estrutura de dados
Profª.Me.Merris Mozer
TA4
Alocação Encadeada
 Flávia é filha de André e Sandra;
 André é filho de João e Maria;
 Sandra é filha de Mauro e Claudia.
Problema: Armazenar todos os 
nomes e relacionar filhos e pais.
Exemplo prático
Suponha a relação funcional:
Dados a armazenar:
João
Sandra
André
Flávia Maria
Mauro
Cláudia
Endereço
Informação
Endereço pai
Endereço mãe
Valor de referência inicial 667 – Flávia
Qual a relação funcional?
768Flávia 417
791André 602
115Sandra 744
João 
667
417
768
602
791
744
115
Maria 
Mauro 
Cláudia 
Tecnologia em Análise e 
Desenvolvimento de Sistemas
Linguagem de Programação e
Estrutura de dados
Profª.Me.Merris Mozer
TA5
Alocação Encadeada
Vamos montar um modelo simples de alocação 
encadeada com números de 1 a 10. 
A
B
C
1
2
3
Λ
A
B
A
B
D
E
F
4
5
6
G
H
I
7
8
9
J 10
R .PAI .nome = ‘André’;
R .MAE .nome = ‘Sandra’;
R .MAE . PAI . 
nome = ‘Mauro’;
Notação diferente
791André 602
115Sandra 744
417
768
744 Mauro 
R .nome = ‘Flávia’; 768Flávia 417667
Então manipular endereços de memória 
é essencial na alocação encadeada?
Não necessariamente; 
Podemos manipular o endereço de 
memória diretamente ou criar 
meios alternativos para simular a 
atuação desses;
No caso da manipulação dos endereços de memória, como 
funciona o processo de se armazenar um conteúdo e saber a 
posição de memória onde esse se encontra e ainda, quando 
não preciso mais da informação como descartar a posição 
usada e deixá-la novamente disponível?
Para armazenar um conteúdo, usa-se o comando 
aloc solicitando a alocação de uma área de memória, 
segundo a notação:
aloc P;
Onde P é um ponteiro que armazena o endereço 
de memória disponibilizado;para armazenar 
o conteúdo basta então:
P .NOME := ‘Flávia’;
Enfim, 
Quando não precisamos mais da variável 
referenciada por P usamos o comando:
lib P;
A área de memória torna-se disponível 
e poderá ser reutilizada;
Enfim, 
Uso de setas para estabelecer
a relação funcional ...Infelizmente é 
não implementável
Cláudia
Mauro
Maria
João
Sandra
André
Flávia
Λ Λ
Λ Λ
Λ Λ
Λ Λ
Tecnologia em Análise e 
Desenvolvimento de Sistemas
Linguagem de Programação e
Estrutura de dados
Profª.Me.Merris Mozer
TA6
Alocação Encadeada
 Necessário uma alteração estrutural no nodo do vetor.
…
de
para
…
V[1] V[2] V[3] V[7]
V[1] V[2] V[3] V[7]
Podemos ainda implementar listas encadeadas 
através de vetores;
V[1] V[2] V[3] V[7]
…
Comando de definição de um vetor normal:
V = array [1..7] of string;
Tipo do dado
Tamanho do vetor
Nome do vetor
V[2] V[3] V[7]
…
Comandos de definição de um vetor de 
registro:
Definição do modelo do registro:
Reg = register of (NOME : string;
PAI : pointer;
MAE : pointer;);
Definição do vetor:
V = array [1..7] of Reg;
V[1] V[2]
V[3] V[4]
V[5] V[6]
V[7]
Poderíamos ter então:
Cláudia
João
Mauro
Maria
Sandra
Flávia
André0 0
0 0
0 0
0 0
5 1
2 6
3 7
V[V[R].PAI].NOME = ‘André’;
V[V[R].MAE].NOME = ‘Sandra’;
V[V[V[R].MAE]. PAI].NOME =
‘Mauro’.
Considerando a Flávia como referência
V[R].NOME = ‘Flávia’; 768Flávia 417667
791André 602
115Sandra 744
417
768
744 Mauro 
R .nome = ‘Flávia’...................
R .PAI .nome = ‘André’ ........
R .MAE .nome = ‘Sandra’ ....
R  .MAE . PAI .nome = ‘Mauro’
V[R].NOME = ‘Flávia’
V[V[R].PAI].NOME = ‘André’
V[V[R].MAE].NOME = ‘Sandra’
V[V[V[R].MAE]. PAI].NOME = ‘Mauro’
768Flávia 417667
791André 602
115Sandra 744
417
768
744 Mauro 
A gerência de espaço disponível para alocação 
e liberação fica a cargo do próprio programador.
Detalhes quanto a utilização
dos índices como apontadores:
Não se pode ter acesso ao valor numérico 
de um apontador, muito menos realizar operações 
aritméticas sobre ele;