Embed Size (px)
Citation preview
Lista Linear
São estruturas formadas por um conjunto de dados de
forma a preservar a relação de ordem linear entre eles;
As formas de Representação são:
Lista Sequencial
Lista Encadeada
Uma Lista Linear (LL) é uma sequência de nós
• Nós - elementos do mesmo tipo
• Relação de ordem linear (ou total)
Lista Linear
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
a b c d e
Primeiro nó Último nó
Segundo nó
Lista linear
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
• Estrutura interna é abstraída
• Pode ter uma complexidade arbitrária
• Enfatizado o conjunto de relações existente
z a c b
INFORMAÇÕES
Número RG Nome Nasc. Cargo
d
Estrutura dos nós
Lista linear
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
Uma lista linear é uma coleção de n ≥ 0 nós x1, x2, ... , xn, todos do
mesmo tipo, cujas propriedades estruturais relevantes envolvem apenas
as posições relativas lineares entre nós:
n = 0 : lista vazia, apresenta zero nós
n > 0 : x1 é o primeiro nó, xn é o último nó
1 < k < n : xk é precedido por xk-1 e sucedido por xk+1
• Lista linear : sequência de 0 ou mais nós do mesmo tipo
Definição formal
Lista linear
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
• Notas de alunos
• Cadastro de funcionários de uma empresa
• Itens em estoque em uma empresa
• Dias da semana
• Vagões de um trem
• Letras de uma palavra
• Pessoas esperando ônibus
• Cartas de baralho
• Precipitações pluviométricas em um mês/dia
Exemplos de aplicações com listas
Lista linear
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
Operações sobre listas lineares
• Criação de uma lista
• Inserção de um nó
• Exclusão de um nó
• Acesso a um nó
• Impressão de uma lista
Operações básicas:
Lista linear
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
• Contiguidade física (sequencial)
• Encadeamento
Representação física das relações existentes entre os nós e
não aquelas internas a eles
Representação física de uma lista linear
Lista linear
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
Lista Seqüencial
Explora a seqüencialidade da memória do computador, de
tal forma que os nós de uma lista sejam armazenados em
endereços seqüenciais;
Pode ser representado por um vetor na memória principal
ou um arquivo seqüencial em disco.
Lista Encadeada Esta estrutura é tida como uma seqüência de elementos
encadeados por ponteiros;
Cada elemento deve conter, além do dado propriamente dito,
uma referência para o próximo elemento da lista.
Lista Seqüencial Uma lista representada de forma seqüencial é um conjunto
de registros onde estão estabelecidas regras de precedência
entre seus elementos;
O sucessor de um elemento ocupa posição física
subseqüente.
A implementação de operações pode ser feita utilizando array
e registro, associando o elemento a(i) com o índice i
(mapeamento seqüencial).
Lista Seqüencial CARACTERÍSTICAS
Os elementos na lista estão armazenados fisicamente em
posições consecutivas;
A inserção de um elemento na posição a(i) causa o
deslocamento a direita do elemento de a(i) ao último;
A eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último;
Implementação de LL através de contiguidade física
• Utiliza a sequencialidade da memória para representar a
ordem entre os nós
• Endereços fisicamente adjacentes, nós logicamente
adjacentes
LL – contiguidade física
Lista Seqüencial
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
L2 L1 L3 L4 L5 L6
L1 L2 L3 L4 L5 L6
1 2 3 4 5 6
L L
Lista
linear
Arranjo
LL – contiguidade física
Implementação de LL sobre arranjo de 1 dimensão
Lista Seqüencial
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
Características
Todos os elementos do arranjo tem tipo igual
Cada elemento do arranjo é um nó
Tipo do nó = tipo do elemento do arranjo
Posição no arranjo representa posição na LL
Acesso direto aos nós
Natureza dinâmica – inserção / remoção de nodos
Comprimento varia durante aplicação
LL – contiguidade física
L2 L1 L3 L4 L5 L6
L1 L2 L3 L4 L5 L6
1 2 3 4 5 6
L L
Lista Seqüencial
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
TipoNodo = registro
Nome: string
Código: inteiro
Valor: real
fim registro
TipoLista = arranjo [1 .. N] de TipoNodo
Tipos de dados
Tipos de dados utilizados nos algoritmos para
LL implementada com contiguidade física:
LL – contiguidade física
Lista Seqüencial
Fonte: EDELWEISS, N.; GALANTE, R. Estruturas de Dados. Porto Alegre: Bookman, 2009.
Lista Seqüencial - inserção
10 20 30 40 50
1 2 3 4 5 6 7 8 9 10
25
A inserção de um elemento na posição a(i) causa o
deslocamento a direita do elemento de a(i) ao último;
Lista Seqüencial - inserção
10 20 30 40 50
1 2 3 4 5 6 7 8 9 10
25
A inserção de um elemento na posição a(i) causa o
deslocamento a direita do elemento de a(i) ao último;
Lista Seqüencial - inserção
10 20 30 40 50
1 2 3 4 5 6 7 8 9 10
25
A inserção de um elemento na posição a(i) causa o
deslocamento a direita do elemento de a(i) ao último;
Lista Seqüencial - inserção
10 20 30 40 50
1 2 3 4 5 6 7 8 9 10
25
A inserção de um elemento na posição a(i) causa o
deslocamento a direita do elemento de a(i) ao último;
Lista Seqüencial - inserção
10 20 25 30 40 50
1 2 3 4 5 6 7 8 9 10
A inserção de um elemento na posição a(i) causa o
deslocamento a direita do elemento de a(i) ao último;
Lista Seqüencial - remoção
10 20 25 30 40 50
1 2 3 4 5 6 7 8 9 10
Remover (20)
A eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último.
Lista Seqüencial - remoção
10 25 30 40 50
1 2 3 4 5 6 7 8 9 10
A eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último.
Lista Seqüencial - remoção
10 25 30 40 50
1 2 3 4 5 6 7 8 9 10
A eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último.
Lista Seqüencial - remoção
10 25 30 40 50
1 2 3 4 5 6 7 8 9 10
A eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último.
Lista Seqüencial - remoção
10 25 30 40 50
1 2 3 4 5 6 7 8 9 10
A eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último.
Lista Seqüencial - remoção
10 25 30 40 50
1 2 3 4 5 6 7 8 9 10
A eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último.
Lista Seqüencial Vantagens:
Acesso direto indexado a qualquer elemento da lista
Tempo constante para acessar o elemento i - dependerá somente do índice.
Desvantagem:
Movimentação quando eliminado/inserido elemento
Tamanho máximo pré-estimado
Lista Seqüencial
Quando usar:
Listas pequenas
Inserção/remoção no fim da lista
Tamanho máximo bem definido
Lista Sequencial As propriedades estruturadas da lista permitem responder a
questões como:
Se uma lista está vazia
Se uma lista está cheia
Quantos elementos existem na lista
Qual é o elemento de uma determinada posição
Qual a posição de um determinado elemento
Inserir um elemento na lista
Eliminar um elemento da lista
Interface do tipo lista sequencial
A interface é representada pelo arquivo “lstSeq.h”:
Implementação da lista sequencial
A implementação é representada pelo arquivo “lstSeq.c”:
Implementação da lista sequencial
A implementação é representada pelo arquivo “lstSeq.c”:
Implementação da lista sequencial
A implementação é representada pelo arquivo “lstSeq.c”:
Implementação da lista sequencial
A implementação é representada pelo arquivo “lstSeq.c”:
Implementação da lista sequencial
A implementação é representada pelo arquivo “lstSeq.c”:
Implementação da lista sequencial
Exemplo de utilização do tipo lista: “main.c”:
EXERCÍCIOS Acrescente ao TDA Lista as operações abaixo e implemente-
as:
Procedimento que informe quantos elementos existem na lista;
Uma função que retorna o elemento de uma dada posição;
Uma função que retorna a posição de um dado elemento;
Um procedimento que esvazie a lista.
