Nesta aula apresentamos o conceito de Tipo Abstrato de Dados (TAD), um dos pilares fundamentais da disciplina de Estruturas de Dados. Um TAD permite separar a especificação do comportamento de uma estrutura de sua implementação concreta, promovendo modularidade, reusabilidade e clareza no projeto de programas.

Veremos como definir um TAD, como especificá-lo através de suas operações, e como implementá-lo em linguagem C utilizando structs e funções. Este conceito servirá de base para todas as estruturas de dados estudadas ao longo da disciplina (pilhas, filas, listas, árvores, entre outras).

O que é um Tipo Abstrato de Dados?

Nos programas mais simples, os dados são manipulados diretamente por meio de variáveis e tipos primitivos da linguagem. À medida que os problemas crescem em complexidade, torna-se necessário organizar os dados de maneira mais estruturada e controlada.

Um Tipo Abstrato de Dados (TAD) é um modelo que descreve um conjunto de dados, acompanhado das operações definidas sobre esses dados. O TAD especifica o que as operações fazem, mas não como elas são implementadas internamente.

Essa separação entre especificação e implementação traz diversas vantagens:

• Abstração: quem usa o TAD não precisa conhecer os detalhes internos da implementação.
• Modularidade: a implementação pode ser alterada sem afetar o código que usa o TAD, desde que a interface permaneça a mesma.
• Reusabilidade: o TAD pode ser utilizado em diferentes programas e contextos.
• Encapsulamento: os dados internos ficam protegidos contra acessos e modificações indevidas.

Papéis em torno de um TAD

A ideia de abstração fica mais clara quando pensamos nos diferentes "papéis" envolvidos ao redor de um programa que utiliza um TAD:

No exemplo do TAD Ponto desta aula, quem implementa ponto.c é o programador (ou implementador) do TAD. Quem escreve main.c, incluindo ponto.h e chamando funções como pontoDistancia e pontoMover, é o cliente (ou usuário da biblioteca), que utiliza o TAD sem conhecer sua implementação interna. Já quem apenas executa o programa compilado, sem ter acesso ao código-fonte, é o usuário final. Uma mesma pessoa pode, naturalmente, desempenhar mais de um desses papéis, mas distingui-los é importante porque cada um interage com o programa em um nível de abstração diferente.

Especificação de um TAD

A especificação de um TAD é composta por três partes principais:

As operações de um TAD costumam ser classificadas em quatro categorias:

Exemplo: TAD Ponto

Para ilustrar os conceitos, consideremos o TAD Ponto, que representa um ponto no plano cartesiano com coordenadas reais. Diferente do que se costuma ver em linguagens orientadas a objetos, não vamos criar funções do tipo criar, getX ou setX — em C, como os campos da struct já são diretamente acessíveis (não existe private), basta montar e ler um Ponto diretamente pelos seus campos. O TAD se resume às operações que de fato fazem algo com os dados:

Especificação

TAD Ponto

Dados:
  Um par de números reais (x, y) representando coordenadas cartesianas.

Operações:
  distancia(p1, p2) -> real    : retorna a distância euclidiana entre p1 e p2.
  mover(p, dx, dy)              : desloca o ponto p de dx em x e dy em y.
  imprimir(p)                   : exibe as coordenadas do ponto p.

double distancia(Ponto a, Ponto b);
double distancia(Cidade a, Cidade b);           // erro: já existe "distancia"
double distancia(char *s1, char *s2); // erro: já existe "distancia" (distância de edição entre strings)

Implementação em C

Em linguagem C, implementamos o TAD utilizando uma struct para os dados e funções para as operações. O arquivo de cabeçalho (ponto.h) expõe apenas a interface do TAD:

/* ponto.h */

typedef struct {
    double x;
    double y;
} Ponto;

double pontoDistancia(Ponto p1, Ponto p2);
void   pontoMover(Ponto *p, double dx, double dy);
void   pontoImprimir(Ponto p);

O arquivo de implementação (ponto.c) contém os detalhes internos, que ficam ocultos de quem utiliza o TAD:

/* ponto.c */
#include <stdio.h>
#include <math.h>
#include "ponto.h"

double pontoDistancia(Ponto p1, Ponto p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}

void pontoMover(Ponto *p, double dx, double dy) {
    p->x += dx;
    p->y += dy;
}

void pontoImprimir(Ponto p) {
    printf("(%.2f, %.2f)\n", p.x, p.y);
}

O programa principal (main.c) usa o TAD sem conhecer seus detalhes internos. Como não existe uma função pontoCriar, um Ponto é montado diretamente, preenchendo seus campos:

#include <stdio.h>
#include "ponto.h"

int main() {
    Ponto a = {0.0, 0.0};
    Ponto b = {3.0, 4.0};

    printf("Ponto a: "); pontoImprimir(a);
    printf("Ponto b: "); pontoImprimir(b);
    printf("Distancia: %.2f\n", pontoDistancia(a, b));

    pontoMover(&a, 1.0, 1.0);
    printf("Ponto a apos mover: "); pontoImprimir(a);

    return 0;
}

Como o programa agora está dividido em mais de um arquivo-fonte (main.c e ponto.c), é preciso informar ambos ao compilador, para que ele gere um único executável a partir dos dois:

gcc -Wall main.c ponto.c -lm -o programa

A opção -Wall habilita os avisos (warnings) do compilador, ajudando a identificar erros comuns antes mesmo de executar o programa. Já a opção -lm liga a biblioteca matemática (math library), necessária aqui porque ponto.c utiliza a função sqrt().

Separação entre interface e implementação

Uma das práticas mais importantes ao implementar um TAD em C é a separação entre interface e implementação, feita através de arquivos .h e .c.

Quem utiliza o TAD inclui apenas o arquivo .h e não precisa conhecer nem modificar o arquivo .c. Isso garante o encapsulamento dos dados e a independência entre os módulos do programa.

TAD versus Estrutura de Dados

É importante distinguir dois conceitos frequentemente confundidos:

Um TAD é a especificação abstrata dos dados e das operações (o o quê), enquanto uma estrutura de dados é a forma concreta escolhida para organizar esses dados na memória (o como). Um mesmo TAD pode ter mais de uma estrutura de dados como implementação, desde que todas respeitem a mesma interface.

Resumo

Exercícios

1. Explique, com suas próprias palavras, por que um TAD especifica o que uma operação faz, mas não como ela é implementada.
2. No TAD Ponto visto em aula, identifique quais operações são construtoras, modificadoras, consultoras ou destrutoras. Note que nem toda categoria precisa estar presente — e explique por que este TAD não possui uma operação construtora.
3. Explique a diferença entre os papéis de cliente e programador de um TAD. Por que essa distinção é importante mesmo quando as duas tarefas são feitas pela mesma pessoa?
4. Por que, em C, a separação entre interface e implementação de um TAD é considerada apenas uma "convenção de projeto", e não uma restrição imposta pela linguagem?
5. Dê um exemplo (diferente do "turma de alunos" visto em aula) de um TAD que poderia ser implementado por mais de uma estrutura de dados diferente, mantendo a mesma interface.
6. Implemente um novo arquivo de cabeçalho contador.h e sua implementação contador.c para um TAD Contador, com as operações contadorCriar() (retorna um contador zerado), contadorIncrementar(Contador *c) (soma 1 ao contador) e contadorValor(Contador c) (retorna o valor atual). Escreva também um pequeno main.c que utilize esse TAD para contar de 0 a 5.

Sugestões de Respostas dos Exercícios

/* contador.h */

typedef struct {
    int valor;
} Contador;

Contador contadorCriar();
void     contadorIncrementar(Contador *c);
int      contadorValor(Contador c);

/* contador.c */
#include "contador.h"

Contador contadorCriar() {
    Contador c;
    c.valor = 0;
    return c;
}

void contadorIncrementar(Contador *c) {
    c->valor += 1;
}

int contadorValor(Contador c) {
    return c.valor;
}

/* main.c */
#include <stdio.h>
#include "contador.h"

int main() {
    Contador c = contadorCriar();

    while (contadorValor(c) < 5) {
        printf("%d\n", contadorValor(c));
        contadorIncrementar(&c);
    }

    return 0;
}