Ficha Nº9: 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: Quantas letras?

Especifique um programa/função que dada uma frase/nome constrói uma lista de ocorrências das letras ordenada alfabeticamente. Pense numa solução com arrays e noutra com estruturas dinâmicas.

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...