Estruturas de Dados 2019/2020 (CC1007) - DCC/FCUP

Aula Prática #06 - Listas Ligadas
(semana de 25/03 a 30/03)

Conteúdos das teóricas

Nesta e nas próximas aulas práticas iremos usar listas ligadas, tal como já começou a ser dado nas aulas teóricas. Será por isso conveniente usar os os vídeos das teóricas e os slides para acompanhar melhor a matéria:

Sobre as dicas em cada problema

A partir desta aula, as dicas passaram a estar escondidas atrás de um botão do tipo "spoiler": só carregando é que aparecem. Assim, se preferirem, podem optar por primeiro pensar um pouco no problema "sozinhos" (sendo que podem também carregar logo para ver).

Exercício 1) Compreender listas ligadas

  1. Código de listas.
    Faça download do código dado nas teóricas e compile-o (precisa de ter os 3 ficheiros):
  2. Um primeiro teste.
    Abra o ficheiro TestSinglyLinkedList.java no seu editor. Execute o código desse ficheiro ($ java TestSinglyLinkedList) e procure acompanhar cada uma das linhas de código e o seu efeito.
    Abra também o ficheiro SinglyLinkedList.java para espreitar como os métodos referidos no TestSinglyLinkedList.java são implementados.
  3. Genéricos, wrappers e autoboxing.
    Tal como explicado nas aulas, a implementação de listas ligadas usa a noção de genéricos e por isso suporta qualquer qualquer tipo de objectos (não apenas inteiros). Para usar inteiros o exemplo do TestSinglyLinkedList usou o tipo Integer que é uma classe cujo objectivo é conter um inteiro (e com isso poder ser usada onde o Java espera um Objecto, como é o caso aqui).
  4. Lista de tipos customizados: um exemplo com uma lista de pares.
    Crie uma lista para conter em cada posição um par de números, adicione-lhe todas as coordenadas inteiras entre (1,1) e (3,3) e imprima a lista. O output deverá ser algo como: {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

Exercício 2) Vários exercícios de listas no Mooshak

Este exercício consiste na implementação de vários métodos para manipular listas. Todos eles são para serem integrados na classe SinglyLinkedList e estão disponíveis para submissão no Mooshak de EDados no "Volume 3 (Listas Ligadas)", problemas 188 a 193.

Para testar as implementações no seu computador deve chamar os métodos no main depois de ter criado as listas com os exemplos que quiser verificar.

  1. Resolva e submeta o problema [ED188] Devolver elemento numa dada posição

     
  2. Resolva e submeta o problema [ED189] Remover elemento numa dada posição

     
  3. Resolva e submeta o problema [ED190] Cópia de uma lista

     
  4. Resolva e submeta o problema [ED191] Duplicando elementos

     
  5. Resolva e submeta o problema [ED192] Contando elementos

     
  6. ReSolva e submeta o problema [ED193] Removendo elementos

Exercícios extra para consolidação de conhecimentos

  1. Implementando um .equals
    Experimente tentar usar o método count numa lista de pares como atrás definiiu (objectos do tipo Pair). O que acontece? Os objectos têm um .equals padrão que é equivalente ao ==. Para ter o comportamento desejado (comparar os dois números do par) é necessário implementar esse método. Faça override do método padrão e implemente um equals correcto para a sua classe Pair. Teste a sua implementação fazendo contagens e verificando a correção do resultado.
  2. Mais métodos de listas
    Implemente mais alguns métodos de listas fazendo operações que julgue serem úteis, treinando também a parte de perceber como deve ser a assinatura do método. Aqui ficam algumas sugestões para métodos:
  3. Acesso eficiente ao último elemento
    Para melhorar a eficiência dos métodos que necessitam de aceder ao final da lista (getLast e addLast) adicione um atributo private Node<T> last à sua classe de lista ligada. Faça as devidas modificações em todos os métodos implementados (no final têm que deixar correctos não só os valores de first e size, mas também de last). Este é um tradeoff típico: melhorar a eficiência tornando (ligeiramente) mais complexa a implementação.

Desafio

Para esta semana vou colocar um problema diferente dos anteriores e um pouco mais fácil, na esperança de que mais alunos voltem a tentar fazer (e a conseguir). É novamente um problema da minha autoria quefoi usado nas Olimpíadas de Informática, mas neste caso na qualificação (uma fase mais preliminar) e vários miúdos do secundário conseguiram resolvê-lo completamente:

O limite de tempo de execução para cada caso de teste é de 1 segundo, pelo que a solução só será aceite e com pontuação máxima no Mooshak se for eficiente (note que a frase pode ter um milhão de caracteres).

Para estes problemas de desafios não vou dar logo dicas, para vos deixar pensar, mas se quiserem mesmo resolver o problema e não estejam a conseguir (mesmo depois de terem realmente tentado), podem falar comigo para obter pistas, ou ter uma ideia de como os "atacar"

Pedro Ribeiro (DCC/FCUP) / Última actualização: