Estruturas de Dados 2004/2005
Pesquisas numa Lista Ligada simples
• Uma pesquisa é uma travessia da lista, até à identificação de um certo elemento ou até
esgotar a lista.
Por exemplo, se quisermos identificar, numa dada lista, o elemento cujo campo de
informação, info, contém estainfo, poderı́amos fazer:
antp = NULL; p = ponta;
while(p->info != estainfo){
ant = p; p = p->prox;
}
{ p aponta o elemento que contém estainfo e ant aponta o elemento anterior a este }
No entanto, se estainfo não “pertencer” à lista, ocorreria um erro: no final da lista,
p==NULL e tentar-se-ia aceder ao campo p− >info ?!!!
Este caso é facilmente corrigido em C usando, para cabeça do ciclo de pesquisa, a instrução:
antp = NULL; p = ponta;
while((p != NULL) && (p->info != estainfo)){
ant = p; p = p->prox;
}
devido à avaliação condicional da linguagem C.
1
Estruturas de Dados 2004/2005
Exemplo de aplicação: remover o elemento com estainfo da lista
/* pesquisar:
devolve um apontador para o elemento anterior ao procurado */
#define TRUE 1
#define FALSE 0
typedef int BOOL;
. . .
BOOL remover(Item estainfo, Seta *ponta){
Seta antp, p;
BOOL pesquisar(), achou = FALSE;
if(achou = pesquisar(estainfo, *ponta, &antp)){
if(antp == NULL){
// estainfo no 1o. elemento
p = ponta;
*ponta = ponta->prox;
}else{
// Caso geral
p = ant->prox;
antp->prox = p->prox;
}
Libertar(&p);
// Liberta a caixa e anula o ponteiro p
}
return achou;
}
2
Estruturas de Dados 2004/2005
Construção (Sequencial) de uma Lista Ligada
Exemplo: construir uma lista de nomes lidos a partir de um ficheiro
Hipótese 1: com inserção à cabeça
Seta
Seta
BOOL
Item
construirLista0(File fich){
novo, ponta;
fimdoficheiro();
ler info();
ponta = NULL;
while(!fimdoficheiro(fich)){
novo = (Seta) malloc(sizeof(no));
novo->val = ler_info(fich);
novo->prox = ponta;
ponta = novo;
}
return ponta;
}
3
Estruturas de Dados 2004/2005
4
Construção (Sequencial) de uma Lista Ligada
Notas sobre construirLista0():
• A inicialização de ponta a NULL serve dois propósitos:
1. coloca o NULL como valor de ”fim de lista”;
2. caso não existam nomes no ficheiro, devolve a lista vazia.
• os elementos da lista devolvida aparecem por sequência inversa daquela que
apresentam no ficheiro
Hipótese 2: com inserção no final
Seta
Seta
BOOL
Item
construirLista1(File fich){
novo, ponta, fim;
//fim, ponteiro auxiliar para o ultimo elemento
fimdoficheiro();
ler info();
if(fimdoficheiro)
ponta = NULL;
else{
// inicializar a lista com o primeiro elemento
ponta = (Seta) malloc(sizeof(no));
ponta->val = ler_info(fich);
ponta->prox = NULL;
fim = ponta;
Estruturas de Dados 2004/2005
// caso geral
while(!fimdoficheiro(fich)){
novo = (Seta) malloc(sizeof(no));
novo->val = ler_info(fich);
novo->prox = NULL;
fim = fim->prox = novo;
}
}// final do else
return ponta;
}// construirLista1
Notas sobre construirLista1():
• os elementos da lista devolvida aparecem pela mesma sequência daquela que
apresentam no ficheiro
• a pesquisa de fim de lista foi evitada usando o ponteiro auxiliar fim
• o tratamento especial do primeiro elemento (bem como do if inicial) poderia ser
evitado usando uma sentinela (nó provisório), que seria eliminado antes da
devolução da lista.
5
Estruturas de Dados 2004/2005
Hipótese 3: com inserção no final e estratégia recorrente
void JuntarNoRec(Item valor, Seta *pt){
if(*pt == NULL){
// fim de lista, colocar novo elemento
ponta = (Seta) malloc(sizeof(no));
ponta->val = valor;
ponta->prox = NULL;
}else JuntarNoRec(valor, &((*pt)->prox))
}
Seta
Seta
BOOL
Item
construirLista2(File fich){
ponta;
fimdoficheiro();
ler info();
ponta = NULL;
while(!fimdoficheiro(fich)) JuntarNoRec(ler_info(fich), &ponta);
return ponta;
}// construirLista2
Notas sobre construirLista2():
• A construção trabalha devido à passagem do parâmetro ponta por referência
• Em cada nova inserção está a ser realizada uma travessia completa da lista pelo
que esta versão é extremamente ineficiente
6