Estrutura de dados

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ência simples 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 ser