Introdução
Estás a trabalhar num projeto para desenvolver um sistema de horários para uma rede ferroviária movimentada.
Foi-te pedido que desenvolvesses um protótipo para as rotas dos comboios no sistema de horários. Cada rota é composta por uma sequência de estações onde um determinado comboio para.
Instruções
A tua equipa decidiu usar uma lista duplamente ligada para representar cada rota de comboio no horário.
Cada estação ao longo da rota do comboio será representada por um nó na lista ligada.
Não precisas de te preocupar com as horas de chegada e de partida nas estações.
Cada estação será simplesmente representada por um número.
As rotas podem ser estendidas, acrescentando estações ao início ou ao fim de uma rota.
Também podem ser encurtadas, removendo estações do início ou do fim de uma rota.
Por vezes, uma estação é encerrada e, nesse caso, tem de ser removida da rota, mesmo que não esteja no início nem no fim da rota.
O tamanho de uma rota não se mede pela distância que o comboio percorre, mas pelo número de estações onde para.
A lista ligada é uma estrutura de dados fundamental da informática, usada frequentemente na implementação de outras estruturas de dados.
Como o nome sugere, é uma lista de nós ligados entre si.
É uma lista de "nós", em que cada nó se liga ao seu vizinho ou vizinhos.
Numa lista ligada simples, cada nó liga-se apenas ao nó que se lhe segue.
Numa lista duplamente ligada, cada nó liga-se tanto ao nó que vem antes como ao nó que vem depois.
Se quiseres aprofundar os teus conhecimentos sobre listas ligadas, espreita este artigo, que as explica com desenhos muito claros.
Como este exercício está estruturado no track de C++
Embora as listas ligadas possam ser implementadas de várias formas, com várias estruturas de dados subjacentes, pedimos-te aqui que implementes a tua lista ligada segundo o paradigma da programação orientada a objetos.
No ficheiro linked_list_test.cpp, vais ver que é chamada uma classe List com templates.
Espera-se que escrevas esta classe com as seguintes funções membro:
-
push adiciona um elemento ao fim da lista,
-
pop remove e devolve o último elemento da lista,
-
shift remove e devolve o primeiro elemento da lista,
-
unshift adiciona um elemento ao início da lista, e
-
count devolve o número total de elementos da lista atual.
Por fim, além dos métodos descritos acima, gostaríamos que implementasses também erase.
erase recebe um argumento: o valor a remover da lista ligada.
Se o valor aparecer mais do que uma vez, só a primeira ocorrência deve ser removida.
Deve devolver se um elemento foi eliminado ou não.
Embora não seja testado, podes querer lançar uma exceção se pop e shift forem chamadas numa List vazia.
Fonte
Tópico clássico da informática
