Linguagens e Ambientes de Programação (2017/2018)



Prática 13

Revisão para o 2º teste. Exercícios 54 e 55.


Nota: Na aula teórica do dia 7/jun, 5ª-feira, será resolvido um exercício de JavaScript, também a título de revisão para o 2º teste.
  • 54 - Neste problema vamos trabalhar com listas de inteiros ordenadas crescentemente, onde podem ocorrer valores repetidos. Para acelerar a remoção de valores, decidiu-se que os nós removidos permanecem na lista, na mesma posição, mas com uma flag a indicar que estão inativos. Para acelerar a insersão de valores, reaproveita-se o nó inativo nos casos em que por sorte esteja um nó inativo ponto de insersão.

    Vamos usar o seguinte tipo ANSI-C. Cada nó da lista contém: uma flag que indica se o nó está ativo, o valor do nó (no caso de estar ativo), um apontador para o nó que se segue. O apontador NULL marca o final da lista. A função da direita pode ser usada para criar nós inicializados.

    Pode usar a função newNode que se oferece aqui já escrita:

    NOTA: Não se esqueça: neste tipo de problemas começa-se por escrever o ciclo (inicialmente de forma tentativa), e só no final se trata da inicialização e da finalização.

  • a) Escreva em C uma função para determinar o comprimento duma lista. Para o comprimento, contam só os nós ativos.
  • b) Escreva em C uma função para remover (ou seja, para inativar) a primeira ocorrência dum dado valor numa lista. A função não deve ter ineficiências desnecessárias: concretamente, como a lista está ordenada, ao ser atingido um valor maior ou igual, não vale a pena continuar a pesquisa.
  • c) Escreva em C uma função para inserir ordenadamente um valor numa lista. De acordo com o que se disse na introdução, só é preciso intercalar um novo nó se na posição de inserção não existir já um nó inativo disponível.


  • 55 - Considere o seguinte programa escrito em GCC, uma variante do C que suporta aninhamento de funções: Mostre qual o estado da pilha de execução no momento em que a execução do programa atinge o ponto marcado com QQQ. Note que o array nodes ocupa 8 posições de memória. Não se esqueça dos registos de ativação das funções start e main.

    Use as convenções habituais das aulas: Para efeitos da criação do registo de activação inicial, imagine que cada programa em GCC está embebido numa função sem argumentos chamada start. Depois trate todas as entidades globais do programa como sendo locais à função imaginária start. Assuma também que a primeira célula da pilha de execução é identificada como posição 0, a segunda célula da pilha de execução é identificada como posição 1, etc.