...collaborate on
View   r2  >  r1  ...

Ficha8 2 - 29 Apr 2005 - Main.PedroRangelHenriques
Line: 1 to 1
 
META TOPICPARENT name="FichasPraticas"
Changed:
<
<

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

>
>

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

 

Objectivos:


Ficha8 1 - 20 Mar 2005 - Main.JoseCarlosRamalho
Line: 1 to 1
Added:
>
>
META TOPICPARENT name="FichasPraticas"

Ficha Nº8: 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...


Revision 2r2 - 29 Apr 2005 - 09:01:34 - PedroRangelHenriques
Revision 1r1 - 20 Mar 2005 - 21:19:40 - JoseCarlosRamalho
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback
Syndicate this site RSSATOM