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



Prática 7

Estruturas ligadas em C. Exercícios de 37 a 38.



  • 37 - Copie o módulo fechado LinkedList da aula teórica 12, estude-o, e acrescente-lhe as seguintes operações, todas elas para programar sem usar recursividade mas usando iteração. A complexidade temporal das quatro primeiras funções deve ser linear (ou seja, não use a função ListPutAtEnd das aulas teóricas, que gera soluções quadráticas).

    Nestas funções vai sentir necessidade de usar todas as técnicas estudadas na aula teórica, nomeadamente a técnica do apontador para o último nó (que permite ir fazendo crescer a lista no final), e a técnica do apontador atrasado (que simplifica o código das funções que precisam de adicionar ou eliminar nós no interior da lista). [Saiba também que estas duas técnicas não são suficientes para resolver todos os problemas: problemas novos podem requerer a invenção de novas técnicas.]


  • 38 - A biblioteca standard do C oferece diversas operações úteis e interessantes: uma operação para aceder ao relógio do sistema time; um gerador de números aleatórios com operações srand e rand; uma operação de ordenação genérica qsort.

    Se tiver dúvidas sobre a passagem de vetores para funções, leia na teórica 11 a secção "Passagem de parâmetros para funções".


  • 39 - Inspire-se no módulo fechado LinkedList das aula teórica 12 para programar em C um novo módulo fechado de árvores binárias de inteiros chamado BinTree. Implemente nele as funções newTreeNode, treeSize, mais as principais funções da aula prática 3

    As operações que geram árvores novas em OCaml, devem alterar diretamente as árvores passadas por argumento (ou seja, devem ser operações "destrutivas"). Como se trata de árvores, faz sentido usar recursividade em muitas das situações.