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:
- Defina os tipos necessários para suportar uma lista ligada de inteiros.
- Especifique uma função para inserir um valor na cabeça da lista.
- 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).
- 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).
- Especifique uma função para contar os elementos da lista.
- Especifique uma função para calcular o maior elemento na lista.
- 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:
- Defina as estruturas de dados necessárias para suportar o sistema de informação;
- Espeifique as várias funções de inserção: inserir uma entrada na agenda, inserir um grupo na agenda, inserir uma entrada num grupo, ...
- Especifique uma função para listar o conteúdo da agenda.
- Especifique uma função para gravar o conteúdo da agenda num ficheiro.
- Especifique uma função para carregar o conteúdo da agenda de um ficheiro.
- Especifique as várias funções de remoção.
Divirta-se...