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



Teórica 12 (18/abr/2017)

Apontadores: Criação dinâmica de variáveis.
Compilação separada e modularidade.
Módulos abertos em C.
Módulos fechados em C.
Listas ligadas em C. Usando recursividade no processamento de estruturas com apontadores.



Apontadores: Criação dinâmica de variáveis

A linguagem C não dispõe dum gestor de memória automático. Criação e a eliminação de variáveis dinâmicas são responsabilidades do programador.

Usa-se a função de biblioteca malloc para criar e eliminar variáveis dinâmicas. A função malloc recebe o número de bytes do bloco de memória a reservar e retorna um apontador (de tipo void *) para o início desse bloco. Eis o cabeçalho desta função, tal como está definido no módulo stdlib:

Exemplo de utilização:

A função malloc retorna a constante NULL no caso do gestor de memória não ter mais memória disponível.

Para libertar a memória ocupada por uma variável dinâmica que já não é mais necessária, usa-se a operação:

Interessa criar variáveis dinâmicas principalmente nas duas seguintes situações: Mais abaixo, mostra-se como se manipulam com listas em C. Uma lista é uma estrutura de dados dinâmica que só pode ser manipulada através de apontadores. Para organizar bem o nosso exemplo, vamos apresentá-lo sob a forma de módulo. Mas primeiro temos de aprender a lidar módulos em C...


Compilação separada e modularidade

A linguagem C suporta modularidade e compilação separada. O controlo de visibilidade de nomes é feito ao nível do ficheiro.

Controlo de visibilidade

Por omissão, todas as variáveis globais e funções definidas num ficheiro são públicas, isto é podem ser acedidas a partir de outros ficheiros. Consegue-se impedir esse acesso precedendo a definição dessas entidades pela palavra static. Antes de se poder aceder a uma entidade definida noutro ficheiro é preciso declarar essa entidade para o compilador a ficar a conhecer. Isso faz-se usando a palavra reservada extern. No caso da declaração das funções o atributo extern pode ser omitido, pois o compilador vê que a declaração não tem corpo e assume que se trata duma entidade externa.

Módulo

Jogando de forma disciplinada com os mecanismos de visibilidade atrás descritos, é possível implementar módulos em C.

Um módulo "fich" é tipicamente definido usando dois ficheiros:

No ficheiro de interface definem-se todas as entidades exportadas pelo módulo, o que pode incluir: funções, variáveis globais, tipos e constantes.

O cliente do módulo só precisa fazer

para ter acesso à definição dos símbolos exportados.


Módulos abertos em C

Apresenta-se uma implementação de listas ligadas, feita num módulo aberto em C. Estas listas são homogéneas e decidimos que vão conter valores de tipo double./sem usar

Este módulo diz-se aberto porque a representação das listas é pública. Veremos na secção seguinte como ocultar essa representação.

Definimos um pequeno conjunto de operações, só para exemplificar.

Ficheiro LinkedList.h

A definição do símbolo _LinkedList_, protege o ficheiro de interface relativamente à possibilidade da inclusão múltipla do mesmo ficheiro.

Uma lista ligada consiste numa sequência de nós. Cada nó contém um valor dum dado tipo Data e um apontador indicando qual o nó seguinte. O valor NULL serve para indicar que não existe nó seguinte.

É interessante comparar a utilização de listas face à utilização de vetores, para guardar sequências de valores:

Ficheiro LinkedList.c

Repare que a função auxiliar NewNode é declarada como estática para ficar privada ao módulo. A palavra reservada static, quando aplicada a uma função ou a uma variável global, torna essas entidades privadas: portanto o âmbito da sua definição é o ficheiro onde essa definição ocorre.

Repare que todas as funções deste módulo estão programadas com base em raciocínios imperativos, sem usar recursividade. Essa é a forma normal de trabalhar em C.

Algumas destas funções são complicadas de escrever, especialmente as que requerem a utilização de diversos apontadores auxiliares. Geralmente, a melhor forma de programar estas funções é assim:

Realmente, antes de escrever o ciclo principal, normalmente um pouco complicado, será difícil adivinhar quais são as suas necessidades detalhadas de inicialização.

Técnica do apontador para o último nó

A função listMakeRange ilustra uma técnica importante.

É sempre muito fácil fazer crescer as listas acrescentando nós novos à cabeça. Mas usando a técnica exemplificada, consegue-se criar uma nova lista acrescentando os novos nós no final. Repare que se usa de forma habilidosa um apontador auxiliar p que aponta sempre para o último nó da lista. Tome nota desta técnica, porque precisará de a usar muitas vezes.

Técnica do apontador atrasado

A função listFilter ilustra outra técnica importante.

De forma geral, as funções que apagam ou inserem nós precisam de alterar o campo next do nó anterior. Realmente, quando se descobre qual o ponto de inserção, o nó anterior já ficou para trás. Por isso, neste tipo de função, convém navegar na lista usando um apontador atrasado, que aponta para o nó que antecede aquele em que estamos interessados em cada momento.

Mas, levanta-se então o problema de como tratar o primeiro nó da lista, visto que ele não tem antecedente. A nossa solução foi inserir um nó auxiliar (com nome dummy) na primeira posição.

Recomendação geral para a escrita de funções sobre listas

As funções sobre listas costumam ser complicadas por envolverem vários detalhes de gestão dos apontadores.

Em primeiro lugar, é importante ir fazendo um desenho para apoiar o raciocício.

Não interessa começar por escrever a inicialização! Interessa sim começar por escrever o ciclo, imaginando que vamos a meio dele, e numa primeira fase podem-se assumir algumas simplificações que facilitem a escrita da primeira versão. Depois é preciso refinar o ciclo para tratar todas as situações possíveis. Finalmente, agora que já percebemos as necessidades do ciclo, podemos escrever a sua inicialização.


Módulos fechados em C

Os módulos fechados em C baseiam-se na possibilidade de definir um tipo apontador para um tipo estrutura que ainda não foi definido, assim: Estão, onde é que finalmente se define o tipo struct Node? Somente no interior ficheiro LinkedList.c.

Ficheiro LinkedList.h

Para o módulo ficar opaco, altera-se apenas a definição do tipo List.

Ficheiro LinkedList.c

A definição do tipo passa para dentro do ficheiro ".c", mas sem a parte "*List", que já está presente no ficheiro ".h". O resto do ficheiro fica igual.

Usando recursividade e método indutivo no processamento de estruturas com apontadores

Eis uma nova implementação do nosso módulo, agora usando recursividade e raciocínios indutivos, à maneira do OCaml.

A técnica indutiva tem a vantagem de dar origem a código mais legível, mas tem a desvantagem de ser pouco eficiente e fazer crescer muito a pilha de execução. Note que, ao contrário do OCaml, a linguagem C não está otimizada para suportar recursividade de forma económica.

Portanto a técnica recursiva é de evitar quando se processam listas.

Contudo, para processar árvores e outras estruturas não-lineares, já fará sentido usar recursividade em algumas das operações. Sem usar recursividade essas operações ficariam demasiado complicadas, além de que a complexidade espacial dos algoritmos recursivos sobre árvores é muitas vezes log N (depende da altura da árvore), o que é bastante melhor do que a complexidade espacial linear típica das listas tratadas recursivamente.


Discussão da função listFilter

No módulo de listas ligadas, a função listFilter é a mais complicada. Resolvemos o problema usando um apontador atrasado. Eis a solução novamente: Também se pode tentar resolver o problema sem inserir o nó auxiliar no início. Contudo, descobre-se que a solução fica bem mais complicada, especialmente porque surge o novo problema de descobrir qual vai ser a cabeça da lista resultado. Não gostamos desta solução, mas cá vai... Uma outra técnica possível, é usar um apontador diretamente para o campo next do nó antecede aquele em que estamos interessados em cada momento. Note que se trata dum apontador para um apontador, pois o campo next contém um apontador.

Esta técnica tem a vantagem de não necessitar de nó artificial na primeira posição, visto que se pode iniciar o ciclo atribuindo ao apontador o endereço da variável que indica a cabeça da lista. Essa variável funciona como o campo next dum primeiro nó artificial imaginário.

Esta técnica tem a desvantagem de obrigar a trabalhar com apontadores para apontadores, o que complica os raciocínios.

A conclusão é que a primeira solução, que usa um nó inicial auxiliar, parece ser a melhor.



#120