INF 1007 Programação II  
Aula 12 Tipos Abstratos de Dados  
Edirlei Soares de Lima  
<elima@inf.puc-rio.br>  
Tipo Abstrato de Dados (TAD)  
Um TAD define:  
Um novo tipo de dado;  
O conjunto de operações para manipular dados desse tipo;  
Um TAD facilita:  
A manutenção e a reutilização de código;  
A implementação das operações de TAD não precisa ser conhecida;  
Para utilizar um TAD é necessário conhecer a sua funcionalidades, mas  
não a sua implementação;  
Um TAD possui:  
Uma interface definindo o nome e as funcionalidades do TAD;  
Uma implementação contendo a real implementação das  
funcionalidades do TAD;  
Tipo Abstrato de Dados (TAD)  
Exemplo: TAD Ponto - Tipo de dado para representar um  
ponto no R com as seguintes operações:  
2
cria - cria um ponto com coordenadas x e y;  
libera - libera a memória alocada por um ponto;  
acessa - retorna as coordenadas de um ponto;  
atribui - atribui novos valores às coordenadas de um ponto;  
distancia - calcula a distância entre dois pontos;  
Tipo Abstrato de Dados (TAD)  
Interface do TAD Ponto:  
Define o nome do tipo e os nomes das funções exportadas;  
A composição da estrutura Ponto não faz parte da interface:  
Não é exportada pelo módulo;  
Não faz parte da interface do módulo;  
Não é visível para outros módulos;  
Os módulos que utilizarem o TAD Ponto:  
Não poderão acessar diretamente os campos da estrutura Ponto;  
Só terão acesso aos dados obtidos através das funções exportadas.  
/
/
* TAD: Ponto (x,y) */  
* Tipo exportado */  
Arquivo: ponto.h (interface do TAD Ponto)  
typedef struct ponto Ponto;  
/
/
* Funções exportadas */  
* Função cria - Aloca e retorna um ponto com coordenadas (x,y) */  
Ponto* pto_cria(float x, float y);  
/
* Função libera - Libera a memória de um ponto */  
void pto_libera(Ponto* p);  
/
* Função acessa - Retorna as coordenadas de um ponto */  
void pto_acessa(Ponto* p, float* x, float* y);  
/
* Função atribui - Atribui valores às coordenadas do ponto */  
void pto_atribui(Ponto* p, float x, float y);  
/
* Função distancia - Retorna a distância entre dois pontos */  
float pto_distancia(Ponto* p1, Ponto* p2);  
Tipo Abstrato de Dados (TAD)  
Implementação do TAD Ponto:  
Inclui o arquivo de interface de Ponto;  
Define a composição da estrutura Ponto;  
Inclui a implementação das funções externas;  
#
#
#
#
include <stdlib.h>  
include <stdio.h>  
include <math.h>  
include "ponto.h"  
Arquivo: ponto.c (implementação do TAD Ponto)  
struct ponto {  
float x;  
float y;  
}
;
Ponto* pto_cria(float x, float y)  
{
Ponto* p = (Ponto*) malloc(sizeof(Ponto));  
if (p == NULL) {  
printf("Memória insuficiente!\n");  
exit(1);  
}
p->x = x;  
p->y = y;  
return p;  
}
void pto_libera(Ponto* p){  
free(p);  
}
void pto_acessa(Ponto* p, float* x, float* y){  
*
*
x = p->x;  
y = p->y;  
}
void pto_atribui(Ponto* p, float x, float y) {  
p->x = x;  
p->y = y;  
}
float pto_distancia(Ponto* p1, Ponto* p2) {  
float dx = p2->x - p1->x;  
float dy = p2->y - p1->y;  
return sqrt(dx*dx + dy*dy);  
}
Tipo Abstrato de Dados (TAD)  
Exemplo de utilização do TAD Ponto:  
#
include <stdio.h>  
include "ponto.h"  
#
int main(void)  
{
float x, y;  
Ponto* p = pto_cria(2.0,1.0);  
Ponto* q = pto_cria(3.4,2.1);  
float d = pto_distancia(p,q);  
printf("Distancia entre pontos: %f\n",d);  
pto_libera(q);  
pto_libera(p);  
return 0;  
}
Tipo Abstrato de Dados (TAD)  
Exemplo: TAD Circulo - Tipo de dado para representar um  
circulo com as seguintes operações:  
cria - cria um círculo com centro (x,y) e raio r;  
libera - libera a memória alocada por um círculo;  
area - calcula a área do círculo;  
interior - verifica se um dado ponto está dentro do círculo;  
/
/
#
* TAD: Círculo */  
Arquivo: circulo.h (interface do TAD Circulo)  
* Dependência de módulos */  
include "ponto.h"  
/
* Tipo exportado */  
typedef struct circulo Circulo;  
/
/
* Funções exportadas */  
* cria - Aloca e retorna um círculo com centro(x,y) e raio r */  
Circulo* circ_cria(float x, float y, float r);  
/
* libera - Libera a memória de um círculo previamente criado */  
void circ_libera(Circulo* c);  
/
* area - Retorna o valor da área do círculo */  
float circ_area(Circulo* c);  
/
* interior - Verifica se um ponto p está dentro do círculo */  
int circ_interior(Circulo* c, Ponto* p);  
#
#
include <stdlib.h>  
Arquivo: circulo.c (implementação do TAD Circulo)  
include "circulo.h“  
#
define PI 3.14159  
struct circulo {  
Ponto* p;  
float r;  
}
;
Circulo* circ_cria(float x, float y, float r)  
{
Circulo* c = (Circulo*)malloc(sizeof(Circulo));  
c->p = pto_cria(x,y);  
c->r = r;  
return c;  
}
void circ_libera(Circulo* c)  
{
pto_libera(c->p);  
free(c);  
}
float circ_area(Circulo* c)  
{
return PI*c->r*c->r;  
}
int circ_interior(Circulo* c, Ponto* p)  
{
float d = pto_distancia(c->p,p);  
return (d<c->r);  
}
Tipo Abstrato de Dados (TAD)  
Podemos utilizar um TAD sem precisarmos conhecer a sua  
implementação.  
Exemplo: TAD Matriz - Tipo de dado para representar  
matrizes com as seguintes operações:  
cria: operação que cria uma matriz de dimensão m por n;  
libera: operação que libera a memória alocada para a matriz;  
acessa: operação que acessa o elemento da linha i e da coluna j da  
matriz;  
atribui: operação que atribui o elemento da linha i e da coluna j da  
matriz;  
linhas: operação que devolve o número de linhas da matriz;  
colunas: operação que devolve o número de colunas da matriz.  
/
/
* TAD: matriz m por n */  
* Tipo exportado */  
Arquivo: matriz.h (interface do TAD Matriz)  
typedef struct matriz Matriz;  
/
/
* Funções exportadas */  
* cria - Aloca e retorna uma matriz de dimensão m por n */  
Matriz* mat_cria(int m, int n);  
/
* libera - Libera a memória de uma matriz previamente criada. */  
void mat_libera(Matriz* mat);  
/
* acessa - Retorna o valor do elemento da linha i e coluna j */  
float mat_acessa(Matriz* mat, int i, int j);  
/
* atribui - atribui o valor ao elemento da linha i e coluna j */  
void mat_atribui(Matriz* mat, int i, int j, float v);  
/
* linhas - Retorna o número de linhas da matriz */  
int mat_linhas(Matriz* mat);  
/
* colunas - Retorna o número de colunas da matriz */  
int mat_colunas(Matriz* mat);  
Tipo Abstrato de Dados (TAD)  
Verificar se uma matriz é simétrica: retorna 1 se verdadeiro e 0 se falso:  
Uma matriz é simétrica se ela for igual a sua transposta;  
Uma matriz transposta é o resultado da troca de linhas por colunas da matriz original;  
int simetrica(Matriz *mat)  
{
int i, j;  
for (i=0; i<mat_linhas(mat); i++)  
{
for (j=0; j<mat_colunas(mat); j++)  
{
if (mat_acessa(mat,i,j) != mat_acessa(mat,j,i))  
return 0;  
}
}
return 1;  
}
Tipo Abstrato de Dados (TAD)  
Multiplicar uma matriz por um escalar:  
Matriz *mult_matriz_escalar(Matriz *mat_a, float s)  
{
int i, j;  
Matriz *mat_b = mat_cria(mat_linhas(mat_a), mat_colunas(mat_a))  
for (i=0; i<mat_linhas(mat_a); i++)  
{
for (j=0; j<mat_colunas(mat_a); j++)  
{
mat_atribui(mat_b, i, j, s * mat_acessa(mat_a,i,j));  
}
}
return mat_b;  
}
Leitura Complementar  
Waldemar Celes, Renato Cerqueira, José Lucas  
Rangel, Introdução a Estruturas de Dados, Editora  
Campus (2004).  
Capítulo 9 Tipos Abstratos de Dados  
Exercícios  
Lista de Exercícios 11 Tipos Abstratos de Dados  
http://www.inf.puc-rio.br/~elima/prog2/