Slide busca sequencial

Prévia do material em texto

Profº Carlos Alberto Teixeira Batista 
E-mail: carlos.batista@facape.br 
 carlos36_batista@yahoo.com.br 
Estruturas de Dados 
 
mailto:carlos.batista@facape.br
mailto:carlos36_batista@yahoo.com.br
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çãode 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.