Tipo Abstrato de Dados

Um tipo de dado define um conjunto de valores e as operações que podem ser feitas com eles: um int guarda inteiros em uma certa faixa e pode ser somado, comparado, impresso. A linguagem C também oferece formas de estruturar dados a partir dos tipos básicos, como vetores, struct e enum.

Muitas vezes isso não basta. Um programa que lida com alunos, frações ou datas precisa de um tipo novo e de um conjunto de operações para manipulá-lo, e precisa que os valores desse tipo nunca fiquem em um estado inválido (um CR negativo, uma data 31 de abril, uma fração com denominador zero).

Quem usa um TAD só precisa conhecer as operações disponíveis, como faz com os tipos da própria linguagem: você soma dois double sem saber como os bits estão organizados. Quem implementa o TAD escolhe as estruturas e escreve as operações. Para quem usa, o TAD é uma caixa-preta.

Por que um TAD?

Considere um programa que guarda nome, matrícula e CR de um aluno. O CR deve ficar sempre entre 0 e 10, então as funções que mexem nele limitam o valor a esse intervalo:

As funções fazem o trabalho certo: alteraCR(a, 12.0) deixa o CR em 10. Mas nada impede o código que usa a struct de escrever direto nos campos, como a->cr = -999, e deixar o aluno em um estado que as funções nunca produziriam. Em um programa grande, com várias pessoas mexendo, esse tipo de atalho aparece, e o erro só é percebido muito longe de onde aconteceu.

A solução é que só as funções do TAD possam mexer nos campos. Em C, isso é feito separando o programa em arquivos.

Interface, implementação e cliente

Um TAD em C costuma ser dividido em dois arquivos, e o programa que o usa fica em um terceiro:

• Interface (Aluno.h): declara o tipo e os protótipos das operações. É tudo o que o usuário do TAD vê.
• Implementação (Aluno.c): define a struct com os campos e o código das operações. Fica escondida do usuário.
• Cliente (main.c): o programa que usa o TAD. Inclui só a interface.

Essa divisão em módulos (unidades com um propósito bem definido, que podem ser compiladas separadamente) tem várias vantagens:

• Encapsulamento: o usuário não precisa saber como o TAD funciona por dentro, só quais operações existem.
• Integridade: como os campos só são alterados pelas operações, o TAD nunca fica em um estado inválido.
• Manutenção: dá para mudar a implementação (trocar um vetor por outra estrutura, acrescentar um campo) sem mudar uma linha do cliente.
• Reutilização: o mesmo TAD pode ser usado em vários programas, sem copiar e colar código.
• Compilação separada: ao alterar um módulo, só ele precisa ser recompilado (veja Compilação e Make).

As operações variam de TAD para TAD, mas quase sempre existem operações para criar e destruir (liberar) o TAD, e para inserir, remover e consultar os dados guardados nele.

O TAD Aluno em módulos

Clique nas abas para ver cada arquivo. Execute e, depois, tire o comentário da linha a->cr = -999; em main.c e execute de novo.

Agora o acesso direto não compila:

main.c:11:6: error: invalid use of incomplete typedef 'Aluno' {aka 'struct aluno'}
   11 |     a->cr = -999;
      |      ^~

O que garante isso é a linha typedef struct aluno Aluno; em Aluno.h. Ela diz que existe uma struct aluno, mas não diz quais campos ela tem: para quem inclui só o .h, Aluno é um tipo incompleto (ou opaco). O cliente pode declarar ponteiros Aluno * e passá-los para as funções, mas não pode acessar campos, nem declarar uma variável Aluno (sem ponteiro), nem usar sizeof(Aluno). Os campos só são conhecidos dentro de Aluno.c, onde a struct aluno é definida. A ocultação deixa de ser uma convenção ("por favor, não mexa nos campos") e passa a ser garantida pelo compilador.

Repare em mais três detalhes da implementação:

• Aluno.c inclui Aluno.h. Primeiro, porque precisa do tipo Aluno. Segundo, porque assim o compilador confere se cada função implementada tem o mesmo tipo do protótipo da interface.
• limitaCR é static. Uma função static só é visível dentro do próprio arquivo. Ela é um detalhe da implementação e não aparece na interface: o cliente não pode chamá-la.
• #define MAX 50 também ficou em Aluno.c. O tamanho do vetor nome é um detalhe da implementação.

TAD Ponto

Um ponto no plano, com as operações:

• criaPonto: cria um ponto com coordenadas ;
• liberaPonto: libera a memória do ponto;
• acessaPonto: devolve as coordenadas do ponto (por meio de ponteiros);
• atribuiPonto: atribui novas coordenadas ao ponto;
• distanciaPonto: calcula a distância entre dois pontos.

Note que acessaPonto precisa devolver dois valores. Como uma função só tem um valor de retorno, ela recebe os endereços de duas variáveis do cliente e escreve nelas, como scanf faz.

Lendo só Ponto.h, não dá para saber se o ponto guarda as coordenadas em dois campos double, em um vetor de duas posições ou em coordenadas polares. A implementação poderia trocar uma representação por outra, e main.c continuaria funcionando sem nenhuma alteração.

Diretivas do pré-processador

Antes de compilar, o gcc passa cada arquivo .c pelo pré-processador, que trata as linhas que começam com #. Um #include "Ponto.h", por exemplo, é substituído pelo conteúdo inteiro de Ponto.h.

Include guard

Um mesmo cabeçalho pode acabar incluído mais de uma vez no mesmo arquivo, quase sempre de forma indireta. No TAD Círculo (próxima seção), Circulo.h inclui Ponto.h, porque uma das operações recebe um Ponto. Um cliente que usa os dois TADs inclui Ponto.h e Circulo.h, e o conteúdo de Ponto.h aparece duas vezes. Repetir protótipos não é problema, mas definições como a de uma struct não podem aparecer duas vezes, e o compilador acusa redefinition.

Para evitar isso, todo .h é cercado por um include guard:

#ifndef PONTO_H
#define PONTO_H

/* conteúdo da interface */

#endif

Na primeira vez que o arquivo é processado, o símbolo PONTO_H não está definido: o #ifndef (if not defined) é verdadeiro, o símbolo é definido e o conteúdo é considerado. Da segunda vez em diante, PONTO_H já existe, e tudo até o #endif é ignorado. O nome do símbolo pode ser qualquer um; o costume é usar o nome do arquivo em maiúsculas.

Compilação condicional

As mesmas diretivas servem para ligar e desligar trechos de código. #if 0 ... #else ... #endif desativa o primeiro trecho (troque por #if 1 para inverter). #ifdef DEBUG ... #endif só mantém o trecho se o símbolo DEBUG estiver definido, o que é útil para mensagens de depuração:

Comente a linha #define DEBUG e execute de novo: as mensagens somem, sem apagar nenhum printf. Com a linha comentada, também dá para ligar as mensagens na hora de compilar, sem mexer no código: gcc -DDEBUG debug.c define o símbolo DEBUG para aquele arquivo.

TAD Círculo

Um círculo é dado pelo centro e pelo raio, com as operações criaCirculo, liberaCirculo, areaCirculo e interiorCirculo (verifica se um ponto está dentro do círculo). Ele usa o TAD Ponto: o centro é um Ponto *, e interiorCirculo recebe um Ponto. Mesmo assim, Circulo.c não conhece os campos do ponto: ela usa criaPonto, distanciaPonto e liberaPonto, como qualquer outro cliente.

main.c inclui Ponto.h e Circulo.h, que inclui Ponto.h de novo; os include guards fazem a segunda inclusão ser ignorada. Repare também em liberaCirculo: ela libera o centro antes de liberar o círculo. Na ordem inversa, c->centro seria lido depois do free(c).

Compilando um programa com vários arquivos

Aqui na página, os botões compilam tudo para você. No terminal, a primeira tentativa costuma ser compilar só o cliente:

gcc main.c -lm -o TADPonto

/usr/bin/ld: /tmp/ccGosmEZ.o: in function `main':
main.c:(.text+0x34): undefined reference to `criaPonto'
main.c:(.text+0x4d): undefined reference to `criaPonto'
main.c:(.text+0x64): undefined reference to `distanciaPonto'
...
collect2: error: ld returned 1 exit status

(Em um sistema em português, a mensagem é referência não definida para "criaPonto".) O erro não é do compilador, é do ligador (ld). main.c compilou sem problemas: o #include "Ponto.h" trouxe os protótipos, e isso basta para compilar as chamadas. Mas o código das funções está em Ponto.c, que não foi compilado, e o ligador não tem de onde tirar criaPonto.

Um programa com vários módulos é construído em duas etapas:

1. Compilação: cada .c é compilado separadamente, gerando um arquivo objeto (.o) com o código de máquina das funções daquele arquivo. A opção -c diz ao gcc para parar aqui, sem gerar executável.
2. Ligação: o ligador junta os arquivos objeto, e o código das bibliotecas usadas (como a matemática, com -lm), em um único executável. É só nessa etapa que se confere se cada função chamada existe em algum lugar.

gcc -c Ponto.c                       # gera Ponto.o
gcc -c main.c                        # gera main.o
gcc main.o Ponto.o -lm -o TADPonto   # liga os dois e gera o executável
./TADPonto

Também dá para fazer tudo de uma vez, com gcc main.c Ponto.c -lm -o TADPonto: o gcc compila os dois arquivos e liga o resultado, sem guardar os .o.

Exercícios

Encontre e corrija o erro

Cada projeto tem um erro. Execute, leia as mensagens (de compilação, de ligação ou de execução), corrija e execute de novo.

Projeto 1

Projeto 2

Projeto 3

A saída deveria ser Distancia: 2.9155 e q = (4.5, 6.5), distancia: 5.0000.

Projeto 4

void liberaCirculo(Circulo *c) {
    liberaPonto(c->centro);
    free(c);
}

Implemente

Nos dois exercícios, a interface (.h) já está pronta e não pode ser alterada. Os campos da struct ficam no .c, e toda operação precisa deixar o TAD em um estado válido.

TAD Fração. Uma fração é guardada sempre na forma canônica: simplificada, com o denominador positivo e com o zero representado como 0/1. Por exemplo, criaFracao(4, -6) representa e criaFracao(10, 4) representa . Soma e multiplicação devolvem uma fração nova, também canônica.

TAD Data. Uma data do calendário entre 01/01/0001 e 31/12/9999. A criação recusa datas que não existem (31/04, 29/02 de um ano não bissexto, mês 13), e as operações avançam dias e contam os dias entre duas datas.

Referências

• W. Celes, R. Cerqueira e J. L. Rangel. Introdução a Estruturas de Dados: com técnicas de programação em C. 2ª ed. Grupo GEN, 2016.
• A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.
• F. Varejão. Introdução à Programação. Grupo GEN, 2014.