Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1075 palavras )
  • Download(s) : 0
  • Publicado : 18 de maio de 2011
Ler documento completo
Amostra do texto
PROFESSORA MERRIS MOZER
Pós Graduação Formação Pedagógica em Matemática Consultoria e Estratégia Empresarial Metodologia e Didática de Ensino Graduação Tecnologia em Processamento de Dados

ALGORITMO E ESTRUTURA DE DADOS Alocação Encadeada

Aula 2

Introdução Alocação simplesmente encadeada sequencial

Na alocação seqüencial: x1 é o primeiro nodo; xn é o último nodo; xk precede xk+1;Nodos são alocados em vetor; xk e xk+1 ocupam posições contínuas no vetor.

V[1]

V[2]
Amanda

V[3]
Felipe
Fim

V[4]

Fila Fernando
Começo

V[4]

Vetor V V[1] V[2] V[3] V[4]

Pilha

V[3]

Felipe

Topo

V[2] Amanda V[1] Fernando

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;Uso de ALOCAÇÃO ENCADEADA – Criação de cadeias ou ligações entre os nodos; Vantagens: Melhor ocupação de memória.

O que é a 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ênciasimples para ser uma relação funcional de precedência.

Alocação seqüencial: Qualquer relação que, para cada registro T1 leve a no máximo um registro do tipo T2 será chamada de relação funcional. Nodo armazena apenas uma informação;

Fernando
Alocação encadeada: Nodo armazena informação e endereço do nodo seguinte;

Fernando

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.

Fernando
Parte do endereçamento: Dados tipo referência, ou seja, um indicador de localização do próximo nodo a sertrabalhado;

Fernando 1430 Referência Inicial Alfredo Paula João Janaina 1023 998 Λ 616

Cláudio Felipe Sandra Amanda Paulo

714 Λ 897 565 407 Referência Inicial

105 Fernando 1430 897 Cláudio 407 Alfredo 565

714 Λ 897 565 407

1023 998 Felipe 998 1023 Sandra Λ
1430 Amanda

Paula

105 Qual a Relação Funcional ?

105 616 João Qual a Relação Funcional ? 714 Janaina

616 2213 PauloΛ é o símbolo que designa ausência da informação

Λ é o símbolo que designa ausência da informação

Fernando 1430 Referência Inicial Alfredo Paula João Janaina 1023 998 Λ 616

Cláudio Felipe Sandra Amanda Paulo

714 Λ 897 565 407 Referência Inicial

105 Fernando 1430 897 Cláudio 407 Alfredo 565

714 Λ 897 565 407

1023 998 Felipe 998 1023 Sandra Λ
1430 Amanda

Paula

407 Qual aRelação Funcional ?

407 616 João Qual a Relação Funcional ? 714 Janaina

616 2213 Paulo

Λ é o símbolo que designa ausência da informação

Λ é o símbolo que designa ausência da informação

Exemplo prático: Suponha a relação funcional: 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 filhose pais.

Dados a armazenar:

Flávia André Sandra João

Maria Mauro Cláudia

Endereço

Informação Endereço pai Endereço mãe

ATIVIDADE EM SALA

667 417 768 602

Flávia 417 768 791 André 602 791 744 Sandra 744 115 115 João
Λ Λ

Maria

Λ

Λ Λ

ATIVIDADE EM SALA A 1 2 3 Λ A B B C Λ

Mauro Λ Cláudia Λ

Λ

Λ é o símbolo que designa ausência da informação

B C

Monteum modelo simples de alocação encadeada com números de 1 a 10. (5 minutos).

Detalhes de notação: Supondo que exista um apontador R referenciando o nodo de Flávia (R=667), teremos a notação: R ↑ .nome = ‘Flávia’; 667 Flávia 417 768 R ↑ .PAI ↑ .nome = ‘André’;

Então manipular endereços de memória é essencial na alocação encadeada? Não necessariamente; podemos manipular o endereço de memória...
tracking img