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

Lista de exercícios

Prática 07 (24/abr/2025)

Exercícios com listas.

Exercício 12 [H]: Antes e depois em listas

Escreva um pequeno programa que use o módulo Lista e que tenha as seguintes três funções:


/***********************************************
existeLista - Testa se objeto ocorre na lista
Parametros: l - lista; a - objeto
Retorno: true - se ocorre; false - se nao
Precondicao: a != NULL
***********************************************/
bool existeLista(lista l, obj a);

/***********************************************
depoisLista - Acrescenta b depois de cada a.
Parametros: l - lista; a, b - objetos
Retorno: lista modificada
Precondicao: a != NULL && b != NULL
***********************************************/
lista depoisLista(lista l, obj a, obj b);

/***********************************************
antesLista - Acrescenta a antes de cada b.
Parametros: l - lista; a, b - objetos
Retorno: lista modificada
Precondicao: a != NULL && b != NULL
***********************************************/
lista antesLista(lista l, obj a, obj b);

Trata-se duma pequena experiência e por isso escrevemos o programa todo num único ficheiro. Está aqui um ponto de partida: MainAntesDepoisLista.c.

Vai precisar de incluir a biblioteca no seu projeto.

Para programar uma função complicada que percorre uma lista, eis uma metodologia que funciona:

Começar por escrever o percurso básico:
Desenhar uma lista (com retângulos e setas) em papel ou no quadro, para ajudar nos raciocínios.
Pensar no que é preciso fazer quando se está a meio da lista - escrever o código.
Pensar se funciona para o último elemento da lista.
Pensar no que é preciso fazer para a cabeça da lista. Em alguns casos, a cabeça tem de ser tratada de forma especial - escrever o código.
Rever a inicialização. De forma geral, a inicialização serve os interesses do processamento principal. O contrário não é realista.
Rever a finalização.

Exercício 13 [I]: Implementação do TAD Dicionario usando listas

Nas aulas teóricas implementámos o TAD Dicionario usando vetores, no ficheiro "DicionarioVetor.c". Também implementámos o TAD Pilha usando listas, no ficheiro "PilhaLista.c", e implementámos o TAD Fila usando listas, no ficheiro "FilaLista.c".

Agora queremos que você implemente o TAD Dicionario usando listas, num ficheiro "DicionarioLista.c".

Está aqui um ponto de partida: DicionarioLista.c.

O programa principal já está feito e resume-se a isto: MainDicionarioLista.c.

Relembre o conceito de dicionário e o conceito de chave. Os dicionários têm uma interface mais simples do que as sequências. As operações essenciais são: testar existência, obter elemento, adicionar e remover.

Internamente a implementação precisa de usar pares (chave, elemento). Para acrescentar elementos novos, acrescente na cabeça da lista. A operação de remoção é a mais complicada.