Ficha Nº7: Estruturas de Dados Dinâmicas - Listas Ligadas

Objectivos:

O objectivo principal desta ficha é familiarizar o aluno com a utilização de estruturas de dados dinâmicas.

Exercícios:

Exercício Nº1: Lista de Inteiros

Considere uma lista de inteiros (não se sabe o seu comprimento). Especifique então as seguintes funções e estruturas de dados:

1. Defina os tipos necessários para suportar uma lista ligada de inteiros.
2. Especifique uma função para inserir um valor na cabeça da lista.
3. Especifique uma função para listar os valores da lista, do início para o fim (faça também a função que lista os elementos na ordem inversa).
4. Especifique uma função para procurar um valor na lista (como resultado deverá devolver um apontador para o elemento ou NULL caso não o encontre).
5. Especifique uma função para contar os elementos da lista.
6. Especifique uma função para calcular o maior elemento na lista.
7. Especifique um programa, usando as funções definidas, que cria uma lista com os múltiplos de 3 entre 0 e 100 e os lista por ordem decrescente e crescente.

Exercício Nº2: À procura da saída ...

Suponha que existe um labirinto (pense numa representação adequada para o mesmo) que tem um ponto de entrada e um ponto de saída. Especifique um algoritmo que vai descobrir um caminho possível entre o ponto de entrada e o ponto de saída. Ajuda: modele numa lista ligada uma stack para ir guardando o caminho percorrido e as hipóteses alternativas.

Exercício Nº3: A Agenda de Contactos

Pretende-se que desenvolva uma aplicação para gerir uma agenda de contactos. Uma agenda é uma lista de entradas ou grupos de entradas. Uma entrada tem a seguinte constituição:

chave

chave única de identificação (não pode haver duas entradas com a mesma chave);

tipo

tipo da entrada: pessoa, empresa, ...

nome

nome da pessoa, empresa ou entidade;

email

contacto electrónco (é opcional)

telefone

número de telefone (obrigatório)

Um grupo pode ter entradas, referências a entradas já existentes na agenda (por chave) ou subgrupos (os grupos podem ter grupos aninhados infinitamente). O grupo tem, então, a seguinte constituição:

chave

chave única de identificação (não pode haver dois grupos com a mesma chave);

nome

nome do grupo; lista de itens: entradas e/ou grupos e/ou referências;

Por sua vez, a referência é apenas constituída pela chave da entrada ou grupo que referencia.

Desenvolva a aplicação nas seguintes etapas:

1. Defina as estruturas de dados necessárias para suportar o sistema de informação;
2. Espeifique as várias funções de inserção: inserir uma entrada na agenda, inserir um grupo na agenda, inserir uma entrada num grupo, ...
3. Especifique uma função para listar o conteúdo da agenda.
4. Especifique uma função para gravar o conteúdo da agenda num ficheiro.
5. Especifique uma função para carregar o conteúdo da agenda de um ficheiro.
6. Especifique as várias funções de remoção.

Divirta-se...