Listas lineares
Denise Guliato
Faculdade de Computação – UFU
www.facom.ufu.br/~guliato
Vários slides foram adaptados de Nina Edelwais e Renata Galante
Estrutura de Dados – Série de Livros Didáticos - Informática - UFRGS
Listas lineares
LL implementada usando
alocação estática e acesso
sequencial
Denise Guliato
Estrutura de Dados - FACOM
LL – contiguidade física
Implementação de LL usando
alocação estática e acesso
sequencial
• Utiliza a seqüencialidade da memória para representar
a ordem entre os nodos
• Endereços fisicamente adjacentes
nodos logicamente adjacentes
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
LL – contiguidade física
Implementação de LL sobre
arranjo de 1 dimensão
Lista
linear
L1
0
LL
L1
L2
L3
1
L2
2
L3
L4
3
L4
L5
L6
4
L5
5
L6
Arranjo
Crédito do slide para Nina Edelwais e Renata Galante
Denise Guliato
LL – contiguidade física
Características
 todos os elementos do arranjo tem tipo igual
 cada elemento do arranjo é um nodo
 tipo do nodo = tipo do elemento do arranjo
 posição no arranjo representa posição na LL
 acesso direto aos nodos
 natureza dinâmica – inserção / remoção de nodos
 comprimento da lista varia durante aplicação
L1
0
LL
Crédito do slide para Nina Edelwais e Renata Galante
L1
L2
1
L2
L3
2
L3
3
L4
L4
L5
4
5
L5
L6
6
L6
Denise Guliato
LL – contiguidade física
Início e final da LL
Quando início e final da LL diferentes do início e final do
arranjo
Variáveis para identificar Início e Final da Lista
0
LL
FL
IL
IA
1
2
3
4
5
6
L1
L2
L3
L4
L5
Lista
Crédito do slide para Nina Edelwais e Renata Galante
7
FA
9
9
Denise Guliato
LL – contiguidade física
Início e final da LL
Quando início e final da LL geralmente são diferentes do início
e final do arranjo
Variáveis para identificar Início e Final da Lista
Final
do Arranjo
Início
do Arranjo
IL
IA
0
LL
1
2
L1
FA
FL
3
4
5
6
L2
L3
L4
L5
Lista
Crédito do slide para Nina Edelwais e Renata Galante
7
8
9
Denise Guliato
Início e final da LL
Consideraremos neste momento que o inicio da
LL sempre coincide com o inicio do arranjo.
IL
IA
FL
0
1
2
3
4
L1
L2
L3
L4
L5
5
FA
6
7
Lista
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
Implementação de LL usando alocação
estática e acesso sequencial
Vantagens:
• acesso direto indexado a qualquer elemento da lista
• tempo constante para acessar o elemento i - dependerá somente do
índice.
Desvantagens:
• movimentação quando eliminado/inserido elemento
• tamanho máximo pré-estimado
Quando usar:
•
•
•
•
listas pequenas
inserção/remoção no fim da lista
tamanho máximo bem definido
A busca é a operação mais frequente
Denise Guliato
LL – contiguidade física
Operações sobre listas lineares
em contiguidade física
• Tamanho_lista
• Cria_lista
• E_cheia
• Libera_lista
• E_vazia
• Insere_elem
Algoritmos
• Remove_elem
• Consulta_nodo
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
Implementação do TAD Lista
Tipo de dado utilizado nos algoritmos para a
implementação da Lista com alocação estática
e acesso sequencial:
#define MAX 100
struct lista {
int FL;
int dados[MAX];
};
typedef struct lista *Lista;
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
LL – contiguidade física
Criação de uma LL vazia
• aloca área para lista
•Inicializa variável FL que guarda final da lista
FL = 0
FL
0
1
2
3
4
5
6
7
8
9
dados
Lista vazia
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
Algoritmo: cria/destroi uma lista
Lista Cria_lista(void)
Lista Cria_lista(void)
{
Lista pt;
pt = (Lista)malloc(sizeof(struct lista));
if (pt != NULL)
pt->FL = 0;
return pt;
}
Lista Libera_lista(Lista Ptl)
Lista Libera_lista(Lista Ptl)
{
free(Ptl);
Ptl = NULL;
return Ptl;
}
Denise Guliato
LL – contiguidade física
Inserção de um novo nodo
FL
LL já existente
0
dados
L1
1
2
L2
L3
3
L4
4
L5
5
6
L6
Informar:
• valor do campo de informação do novo nodo
Quando não é possível realizar a inserção:
• a lista não existe
• a lista está cheia
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
LL – contiguidade física
Inserção de um novo nodo
FL
0
No início
1
2
3
4
5
6
7
8
9
8
9
8
8
A
FL
0
No final
1
2
3
4
5
6
7
A
FL
0
No meio
1
2
3
4
5
6
7
A
Crédito do slide para Nina Edelwais e Renata Galante
Denise Guliato
LL – contiguidade física
Inserção como primeiro nodo da LL
Inserir
no início
0
dados L1
1
L2
2
3
4
5
L3
L4
L5
L6
Adaptado de Nina Edelwais e Renata Galante
FL
6
7
8
9
Denise Guliato
LL – contiguidade física
Inserção como primeiro nodo da LL
Inserir
no início
0
dados L1
0
1
L2
1
2
3
4
5
L3
L4
L5
L6
2
3
4
5
FL
6
7
8
FA
9
6
7
8
9
dados
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
LL – contiguidade física
Inserção como primeiro nodo da LL
Inserir
no início
0
dados
L1
1
2
3
4
5
L2
L3
L4
L5
L6
FL
6
7
8
9
FL
7
8
9
Novo nodo
0
dados
L1
1
2
3
4
5
6
L2
L3
L4
L5
L6
L7
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
LL – contiguidade física
Inserção como último nodo da LL
Inserir
no final
0
dados
L1
1
L2
2
L3
3
4
5
L4
L5
L6
Adaptado de Nina Edelwais e Renata Galante
FL
6
7
8
9
Denise Guliato
LL – contiguidade física
Inserção como último nodo da LL
Inserir
no final
0
dados
L1
1
L2
2
L3
3
4
5
L4
L5
L6
FL
6
7
8
9
8
9
Novo nodo
0
dados L1
1
L2
2
L3
3
4
5
6
L4
L5
L6
L7
Adaptado de Nina Edelwais e Renata Galante
FL
7
Denise Guliato
LL – contiguidade física
Inserção no meio de LL
Inserir elemento
FL
0
dados
L1
1
L2
2
L3
3
4
5
L4
L5
L6
Adaptado de Nina Edelwais e Renata Galante
6
7
8
9
Denise Guliato
LL – contiguidade física
Inserção no meio de LL
Inserir elemento
FL
0
dados
L1
1
L2
2
L3
3
4
5
L4
L5
L6
6
7
8
9
FL
0
dados L1
1
2
3
4
5
6
L2
L3
LN
L4
L5
L6
7
8
9
Novo nodo
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
Inserção de um elemento na lista
No TAD que criamos, a inserção é feita em um
dos extremos da lista.
Vamos inserir no final da lista
Denise Guliato
Algoritmo: inserir no final da lista
int Insere_elem(Lista* Ptl, int elem)
int Insere_elem(Lista* Ptl, int elem)
{
if (*Ptl == NULL)
return 0;
if ((*Ptl)->FL == MAX)
return 0;
// insere elemento no final da lista
(*Ptl)->dados[(*Ptl)->FL] = elem;
(*Ptl)->FL++;
return 1;
}
Denise Guliato
LL – contiguidade física
Remoção de um nodo
FL
LL já existente
0
dados
L1
1
2
L2
L3
3
L4
4
L5
5
L6
6
L7
Informar:
• valor do campo de informação do nodo a ser removido
Quando não é possível realizar a remoção:
• a lista não existe
• a lista está vazia
• o elemento não está na lista
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
LL – contiguidade física
Remoção de um nodo
Remover
elemento L4
FL
0
dados
L1
1
L2
2
L3
3
4
5
6
L4
L5
L6
L7
Adaptado de Nina Edelwais e Renata Galante
7
8
9
Denise Guliato
LL – contiguidade física
Remoção de um nodo
Remover
elemento L4
FL
0
dados
L1
0
dados
L1
1
L2
1
L2
2
L3
2
L3
3
4
5
6
L4
L5
L6
L7
3
4
5
L5
L6
L7
Adaptado de Nina Edelwais e Renata Galante
FL
6
7
8
9
7
8
9
Denise Guliato
Algoritmo: remove elemento com movimentação de dados
int Remove_elem(Lista* Ptl, int elem)
int Remove_elem_mov(Lista* Ptl, int elem)
{
int i,k;
if (*Ptl == NULL) // lista não existe
return 0;
// procura elemento na lista
i=0;
while(i<(*Ptl)->FL && (*Ptl-)>dados[i]!=elem)
i++;
if (i ==(*Ptl)->FL) // elemento nao encontrado ou lista vazia
return 0;
//elemento encontrado na posiçao i. Remover elemento
// com movimentaçao de dados
for (k=i; k<(*Ptl)->FL-1;k++)
(*Ptl)->dados[k]=(*Ptl)>dados[k+1];
// atualiza fim de lista
(* Ptl)->FL--;
return 1;
}
Denise Guliato
LL – contiguidade física
Remoção otimizada de um nodo
Remover
elemento L4
FL
0
dados
1
L1
2
L2
L3
3
4
5
6
L4
L5
L6
L7
7
8
9
FL
0
dados
L1
1
L2
2
L3
3
4
5
L7
L5
L6
Adaptado de Nina Edelwais e Renata Galante
6
7
8
9
Denise Guliato
Remoção de um nodo lista
No TAD que criamos, a remoção de um nodo é
feita sem movimentação de dados
Denise Guliato
Algoritmo: remove elemento sem movimentação de dados
int Remove_elem(Lista* Ptl, int elem)
int Remove_elem(Lista *Ptl, int elem)
{
int i,k;
if (*Ptl == NULL)
return 0;
// procura elemento na lista
i=0;
while(i<(*Ptl)->FL && (*Ptl)->dados[i]!=elem)
i++;
if (i == (*Ptl)->FL)
return 0;// lista vazia ou elemento nao encontrado
//elemento encontrado na posiçao i. Remover elemento
//sem movimentaçao de dados
(*Ptl)->dados[i]= (*Ptl)->dados[(*Ptl)->FL-1];
// atualiza fim de lista
(*Ptl)->FL--;
return 1;
}
Denise Guliato
Acesso a um nodo
LL – contiguidade física
Acesso a um nodo:
•Consultar a informação de um dado nodo;
•Alterar algum campo de informação de um dado nodo;
Adaptado de Nina Edelwais e Renata Galante
Denise Guliato
Acesso a um nodo
O nodo a ser acessado pode ser identificado por:
sua posição na lista
0
dados
L1
1
L2
acessar o 6o.
nodo
2
L3
3
4
5
6
7
L4
L5
L6
L7
L8
FL
8
9
por seu conteúdo. Exemplo, acesse o nodo que contém a
informação L4
Acessar nodo
valor = L4
0
dados L1
1
2
3
4
L2
L3
L4
L5
Adaptado de Nina Edelwais e Renata Galante
5
L6
6
L7
7
FL
8
9
L8
Denise Guliato
Acesso a um nodo da lista
No TAD que criamos, o acesso será feito para
consultar a informação de um dado nodo na
lista
Denise Guliato
Algoritmo: consulta um nodo, dada sua posição
int Consulta_nodo(Lista Ptl, int pos, int* info)
int Consulta_nodo(Lista Ptl, int pos int* info)
{
if ( Ptl == NULL || pos <= 0 || pos > Ptl->FL)
return 0;
*info = Ptl->dados[pos-1];
return 1;
}
Denise Guliato
Outras operações
int Tamanho_lista(Lista Ptl)
int Tamanho_lista(Lista Ptl)
{
if(Ptl == NULL)
return -1;
else return Ptl->FL;
}
int E_cheia(Lista Ptl)
int E_cheia(Lista Ptl)
{
if (Ptl == NULL)
return -1;
return (Ptl->FL == MAX);
}
int E_vazia(Lista Ptl)
int E_vazia(Lista Ptl)
{
if (Ptl == NULL)
return -1;
return(Ptl->FL == 0);
}
Denise Guliato
Arquivo llaeas.h
typedef struct lista *Lista;
Lista Cria_lista(void);
Lista Libera_lista(Lista Ptl);
int Insere_elem(Lista* Ptl, int elem);
int Remove_elem(Lista* Ptl, int elem);
Int Consulta_nodo(Lista Ptl, int pos, int *info);
int Tamanho_lista(Lista Ptl);
int E_cheia(Lista Ptl);
int E_vazia(Lista Ptl);
Denise Guliato
Arquivo llaeas.c
#include <stdio.h>
#include "llaeas.h"
#define MAX 10
struct lista{
int FL;
int dados[MAX];
};
Lista* Cria_lista(void)
{……}
Lista Libera_lista(Lista Ptl)
{…...}
int Insere_elem(Lista* Ptl, int elem)
{…….}
int Remove_elem(Lista* Ptl, int elem)
{……}
Int Consulta_nodo(Lista Ptl, int pos, int *info)
{……}
int Tamanho_lista(Lista Ptl)
{……}
int E_cheia(Lista Ptl)
{……}
int E_vazia(Lista Ptl)
{……}
Denise Guliato
Exercício de sala
a)Escreva um programa, que usando o TAD Lista,
permita a inserção de elementos em uma dada
lista. A leitura de elementos termina quando o
usuario digita Ctrl+Z. Exiba a lista apos as
inserçoes. Remova o nodo cujo valor foi fornecido
pelo usuario. Exiba a lista apos a remoção do
nodo. Grave a lista resultante em um arquivo do
tipo texto, cujo nome foi fornecido via teclado.
b)Escreva uma função que exiba os elementos de
uma dada lista.
c)Escreva uma função que grave os elementos de
uma da lista.
Exercício para entregar (dia 26/04)
Escreva o TAD lista_aluno. Cada aluno deve manter as seguintes
informaçoes: nome, nro de matricula, coef. de aproveitamento.
a)
b)
c)
Defina o TAD lista-aluno em termos do tipo de dados e das
operações (independente de implementaçao)
Implemente o TAD lista-aluno, conforme especificado no item a)
usando alocação estática e acesso sequencial
escreva um programa que disponibilize um menu de opcoes que
permitar executar as operaçoes que vc definiu na sua TDA
Obs: faça o TAD e o programa de aplicaçao de forma independente.
Lembre-se do encapsulamento da esturtura de dados