Estruturas de dados Dinâmicas
Listas Ligadas (unidireccionais)
1
Representação esquemática de uma Lista Ligada
Info.
Prox.
Info.
Prox.
Info.
Prox.
Cabeça da lista
2
Listas Ligadas
Info.
Prox.
Info.
Prox.
Info.
Prox.
Uma lista ligada é uma colecção de registos (NÓS) em que
cada registo (NÓ) possui um campo que indica a localização
do registo seguinte na lista.
O primeiro registo é chamado a cabeça da lista .
3
Listas Ligadas
► Elementos
que compõem uma lista:
Info.
Prox.
Info.
NÓ(S)
CABEÇA DA LISTA
Prox.
Info.
Prox.
FIM DA LISTA (NULL)
4
Listas Ligadas
► Elementos
que compõem uma lista:
 NÓ(S): São o essencial das listas, contêm 2 elementos:
a informação a armazenar; a localização (o endereço)
do próximo nó.
 CABEÇA DA LISTA: É o endereço do primeiro nó da
lista.
 NULL: Indica o final da lista
5
Listas Ligadas
Lista ligada vazia:
Lista ligada com 1 nó:
Info.
Prox.
Lista ligada com 2 nós:
Info.
Prox.
Info.
Prox.
Lista ligada com 3 nós:
Info.
Prox.
Info.
Prox.
Info.
Prox.
6
Listas Ligadas
► Definição
de uma lista:
 Definição da estrutura de um nó
struct no
{
tipo_de_dados dados_a_armazenar;
struct no * noSeguinte;
};
 Criação da lista (cabeça da lista)
struct no * cabeca;
7
Listas Ligadas
► Inicialização
da lista (inicialmente temos
uma lista vazia)
cabeca = NULL;
8
Listas Ligadas
struct no
{
int num;
char nome[100];
struct no * noSeguinte;
};
Informações a
armazenar
struct no * cabeca;
main()
{
…
cabeca=NULL;
…
}
9
Listas Ligadas: inserção
Exemplo 1:
Info.
Prox.
10
Listas Ligadas: inserção
Exemplo 2:
Info.
Info.
Prox.
Info.
Prox.
Prox.
11
Listas Ligadas: inserção
void insere()
{
struct no * novoNo;
novoNo=(struct no *)malloc(sizeof(struct no));
printf("\n\tintroduza o Numero: ");
scanf("%d",&novoNo->num);
printf("\n\tIntroduza o Nome: ");
fflush(stdin);
gets(novoNo->nome);
novoNo->noSeguinte=cabeca; // (*novoNo).noSeguinte
cabeca=novoNo;
}
12
Listas Ligadas: remoção
Situação 1:
NÓ a eliminar
Info.
Prox.
Info.
Prox.
Info.
Prox.
noApagar
13
Listas Ligadas: remoção
Situação 2:
Info.
aux
NÓ a eliminar
Prox.
Info.
Prox.
Info.
Prox.
noApagar
14
Listas Ligadas: remoção
void remover(int nr) //o elemento a remover tem de existir na lista
{
struct no * aux;
struct no * noApagar;
}
if(cabeca->num==nr) //apaga à cabeça
{
noApagar =cabeca;
cabeca=cabeca->noSeguinte;
free(noApagar);
}
else
{
aux = cabeca;
while((aux->noSeguinte)->num != nr)
{
aux = aux->noSeguinte;
}
noApagar = aux->noSeguinte;
aux->noSeguinte = noApagar ->noSeguinte;
free(noApagar);
}
15
Listas Ligadas: Pesquisa
1
noSeg.
2
bb
aa
noSeg.
3
noSeg.
cc
ap
ap = cabeça
Enquanto : ap != NULL
{
SE ap->nr == nr_a_procurar
retorna ap
ap = ap->noSeguinte
}
Quando chega ao fim da lista sem encontrar a informação retorna NULL
16
Listas Ligadas: Pesquisa
struct no * pesquisa(int nr)
{
struct no * ap;
ap=cabeca;
while(ap!=NULL)
{
if(ap->num==nr)
{
return ap;
}
ap=ap->noSeguinte;
}
return NULL;
}
17
Listas Ligadas: Impressão
1
noSeg.
aa
2
bb
noSeg.
3
noSeg.
cc
ap
ap = cabeça
Enquanto : ap != NULL
{
Imprime : ap->nr e ap->nome
ap = ap->noSeguinte
}
18
Listas Ligadas: Impressão
void imprimeLista()
{
struct no * ap;
ap=cabeca;
while (ap!=NULL)
{
printf("\n\tNumero: %d\tNome: %s ", ap->num, ap->nome);
ap=ap->noseguinte;
}
}
19
Listas Ligadas
► Vantagem
das listas
 Permitem o armazenamento de dados de uma
forma completamente flexível.
20