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



Prática 13

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


Nota: Na aula teórica do dia 8/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.

    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.


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