Algoritmos e Estruturas de Dados [LEEC] (2024/2025)

Aulas teóricas

Artur Miguel Dias

Teórica 05 (04/abr/2025)

Listas ligadas em C.
O TAD Pilha implantado de diversas maneiras: usando lista, usando vetor, usando sequência.
O TAD Fila implantado usando lista.

Slides

Lista.h

Há duas técnicas básicas que permitem guardar uma coleção de valores:

vetores - os elementos ficam guardados em posições consecutivas dum bloco de memória e são acedidos através dum índice.
listas (listas ligadas) - os elementos ficam guardados em posições de memória não necessariamente consecutivas, mas precisam de ficar ligados entre si para o acesso a todos os elementos ser possível.

O módulo Lista define um tipo primitivo lista para representar listas genéricas (que guardam objetos genéricos).

Uma propriedade muito importante e útil das listas é que o campo seguinte seg dum nó também representa uma lista: a sublista que começa nesse ponto e vai até ao final. Por exemplo, podemos ter várias lista que partilham um segmento final.

A representação é pública, sendo também oferecidas algumas operações úteis. Não se trata dum TAD, porque a representação não é privada.

O módulo Lista oferece um conjunto de operações públicas inspirado no TAD Sequencia; mas haverá situações em que operações oferecidas não ajudam e será preciso definir livremente, fora do módulo das listas, novas operações sobre listas. É impossível prever à partida todas as funções sobre listas que vamos precisar de usar.

O tipo lista é uma ferramenta primitiva que iremos usar para definir futuros TADs.

Eis os tipos primitivos, todos escritos em minúsculas, que estamos a usar, e continuaremos a usar, para construir os nossos TADs:

bool
int
double
char
string = char *
obj = void *
vetor = obj *
lista = (struct no) *

Lista.c

Implementação das funções oferecidas pelo módulo Lista.

Para percorrer uma lista l, o padrão de base é o seguinte:

for ( ; l != NULL ; l = l->seg){
    (fazer alguma coisa com o nó correntemente apontado por l)
}

Neste caso, a parte da inicialização do ciclo for está vazia porque estamos a assumir-se que l já aponta para o primeiro nó da lista.

As funções que percorrer listas para as processar são delicadas de programar. Convém escrever o código de cada função com a ajuda dum diagrama auxiliar.

Pilha.h

Esta é a definição do TAD Pilha. As operações mais importantes são emPilha e desemPilha.

PilhaLista.c

Implementação do TAD Pilha usando uma lista.

Depois de meditar um pouco, conclui-se que o melhor será fazer os elementos entrarem e saírem sempre pela cabeça da lista - ou seja trabalhamos ao nível do índice 0.

Seria muito ineficiente adicionar e remover os elementos no final da lista, porque para chegar lá precisamos de percorrer a lista até ao final.

PilhaVetor.c

Implementação do TAD Pilha usando um vetor.

Aqui, fazemos os elementos entrarem e saírem pelo final do vetor.

Seria muito ineficiente adicionar e remover os elementos no início do vetor (índice 0), porque cada uma dessas inserções e remoções obrigaria a avançar ou recuar todos os elementos do vetor.

PilhaLentaSequencia.c

Implementação do TAD Pilha usando uma sequência.

Aqui, fazemos os elementos entrarem e saírem pelo início da sequência.

Se a sequência estiver implementada com vetor, isto é muito ineficiente - a implementação fica correta; no entanto, muito ineficiente.

PilhaRapidaSequencia.c

Implementação do TAD Pilha usando uma sequência.

Aqui, fazemos os elementos entrarem e saírem pelo final da sequência.

Se a sequência estiver implementada com vetor, esta é a forma mais eficiente.

Fila.h

Esta é a definição do TAD Pilha. As operações mais importantes são acrescentaFila e removeFila.

FilaLista.c

Implementação do TAD Fila usando uma lista.

Depois de meditar um pouco, conclui-se que há aqui um problema. Se fizermos os elementos entrar pela cabeça (eficiente), temos de remover pelo final da lista (ineficiente). Se fizermos os elementos entrar pelo final da lista (ineficiente), temos de remover pela cabeça da lista (eficiente).

A solução boa é acrescentar um apontador especial chamado ultimo que aponta permanentemente para o último nó da lista. As operações de acrescentar e remover fazem a gestão desse apontador. A gestão é delicada, obrigando a pensar um pouco.

Nesta implementação fazemos os elementos entrar pelo final da lista (eficiente, com a ajuda de ultimo), e removemos pela cabeça da lista (eficiente, porque a cabeça é logo o primeiro nó).

#50