Estruturas de dados
had
Aula 16b:
ƒ
ADTs revisitados
Tal como os tipos pré-definidos da linguagem C (int, float, char, ...), um ADT é um tipo de dados,
(conjunto de valores e uma colecção de operações sobre esse valores). No entanto o ADT além de
ser um tipo de dados definido pelo utilizador é abstracto. O que quer dizer que a representação dos
valores não é transparente para o cliente. Diz-se pois que a interface do ADT é opaca, por esconder
a representação desses valores.
⎧
⎧conjunto de valores
⎪Tipo de dados = ⎨
ADT (abstract data type) = ⎨
⎩colecção de operações
⎪abstracto (representação dos valores escondida do cliente)
⎩
Deste modo os clientes são obrigados a manipular os ADTs apenas através das funções definidas no
seu interface o ficheiro *.h. De modo que para cada função deve estar indicado:
- Descrição em termos dos argumentos de entrada e de saída
- Pré-condições (validações de variáveis que devem ser efectuadas pelo cliente)
- Pós-condições (estado do programa - variáveis alteradas - após execução das funções)
- Excepções
Como o cliente só pode manipular os valores dos ADTs através das funções do interface, não pode
intencionalmente ou inadvertidamente deixar o ADT num estado inválido, ou seja corromper a
informação do ADT. Outra vantagem é que se for necessário (por exemplo por questões de
eficiência) alterar a representação dos valores dos dados ou a implementação de uma qualquer
função, não é necessário efectuar alterações no código cliente (desde que não se altere os
protótipos das funções).
Como um ADT é um tipo de dados, embora abstracto, deve-se comportar como qualquer tipo de
dados. Em particular deve suportar múltiplas instâncias, isto é num mesmo programa deverão
poder-se declarar múltiplas variáveis do ADT, tal como é possível para os tipos pré-definidos.
Pode-se mesmo definir algumas directrizes para desenvolver um ADT múltipla instância:
a) Se bem que não seja obrigatorio para a definição de um ADT, deve ser garantido que o
interface, e de um modo geral todos os headers (ficheiros *.h), não são incluídos mais do
que uma vez quando da compilação, usando um conjunto de directivas de compilação:
#ifndef _ADT_
#define _ADT_
/* Todo o código do interface */
#endif
Por convenção o nome da macro definida na segunda linha é o nome do ficheiro sem
extensão em maiúsculas entre underscores.
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 1/10
Estruturas de dados
had
b) Deve-se esconder do cliente o mais possível sobre a implementação, de modo que no
interface só deve estar o absolutamente necessário, mesmo em termos de definição de
macros ou de inclusão de ficheiros.
c) No interface (adt.h) existirá um ponteiro para uma estrutura que guarda os valores de cada
instância. Esta estrutura estará declarada no ficheiro de implementação (adt.c), e portanto
inacessível a manipulação por parte do cliente, mesmo que este saiba como está
definida! Os membros de dados dessa estrutura também são chamados variáveis de
instância.
d) Deverá existir uma função para criar uma nova instância bem como uma função para a
eliminar da memória. Por convenção, estas funções tem como parte do nome init (ou new)
e free (ou del).
e) De resto, por convenção todas as funções do ADT iniciam-se pelo seu nome ou por um
acrónimo em maiúsculas, por exemplo: ADTinit ( .... ).
f) Como os clientes dos ADTs não sabem e não podem aceder directamente à representação
dos valores das suas instância, é comum que os ADTs disponibilizem funções no seu
interface para se escreverem num stream (que poderá estar associado a um ficheiro ou ao
monitor - stdout) em modo de texto formatado e legível e em binário para poupar memória.
Template para ADT múltipla instância
Seguidamente é apresentado um resumo de um template que poderá ser seguido para programar
ADTs múltipla instância. A versão completa e documentada encontra-se em anexo:
interface
/* Breve descrição do ADT e identificação do autor (adt.h)
*/
#ifndef _ADT_ /* por convenção o nome do ficheiro sem extensão */
#define _ADT_
#include <stdio.h>
/* include de outros headers (*.h) ABSOLUTAMENTE necessários. */
/* Definição de Macros ABSOLUTAMENTE necessárias. */
/* ============================
ponteiro para instância do ADT
============================*/
typedef struct ADTstruct* adt; /*por conv. o nome do ponteiro em minúsculas*/
/* ============================
Declaração das funções do interface (colecção de operações)
============================*/
/*aloca nova instância do ADT*/
adt ADTnew(/* parâmetros: int x, float .... */);
/*elimina instância p*/
void ADTdel(adt p);
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 2/10
Estruturas de dados
had
/* Escreve a instância do adt apontada por p no stream f em modo texto */
int ADTprint(adt p, FILE* f);
/* Escreve a instância do adt apontada por p no stream f em modo binário */
int ADTwrite(adt p, FILE* f);
/* Retorna uma nova instância do adt lida do stream f em modo binário */
adt ADTread(FILE* f);
/* Declaração de outras funções necessárias ao ADT
...
*/
#endif
implementação
/* Breve descrição do ADT e identificação do autor (adt.c)
*/
#include "adt.h" /* include header (interface) do próprio adt */
#include <stdlib.h>
/* include de outros headers (*.h) necessários. */
/* Definição de Macros necessárias */
/* ============================
Definição da estrutura do ADT
============================*/
struct ADTstruct {
/* variáveis de instância do adt.
Podem ser de qualquer tipo (mesmo outros ADTs).
int a;
char s[35];
*/
};
/* Se necessário definir funções privadas ao ficheiro adt.c. p. ex:
static int func(int 4, ... ) {
....
}
*/
/* ============================
Definição das funções do interface
============================*/
adt ADTnew(/* parâmetros necessários: int x, float .... */) { ... };
void ADTdel(adt p) { ... };
int ADTprint(adt p, FILE* f) { ... };
int ADTwrite(adt p, FILE* f) { ... };
adt ADTread(FILE* f) { ... };
/* Implementação de outras funções declaradas no interface
...
*/
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 3/10
Estruturas de dados
had
Implementação do ADT complexo de acordo com o template
Como exemplo de implementação de um ADT segundo o template acima apresenta-se a seguir o
ADT número complexo, onde para simplificar a única operação aritmética definida é a soma de dois
complexos.
interface
/* ADT Complex interface (complex.h)
2004, 2005 had
*/
#ifndef _COMPLEX_
#define _COMPLEX_
#include <stdio.h>
/* ============================
ponteiro para instância do ADT
============================*/
typedef struct COMPstruct* complex;
/* ============================
Declaração das funções do interface (colecção de operações)
============================*/
/* Aloca memória para nova instância do ADT Complex e retorna ponteiro para ela.
Excepção: Senão houver memória suficiente para o ADT retorna NULL
*/
complex COMPinit(float re, float im);
/* Liberta memória reservada para ADT Complex
PRE: c != NULL
*/
void COMPfree(complex c);
/* Escreve a instância de complexo apontada por c no stream f
em modo texto. Retorna 1.
PRE: c != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int COMPprint(complex c, FILE* f);
/* Escreve a instância de complexo apontada por c no stream f
em modo binário. Retorna 1.
PRE: c != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int COMPwrite(complex c, FILE* f);
/* Retorna uma nova instância de complexo lida do stream f em modo binário
PRE: f != NULL
Excepção: Se ocorrer erro de leitura ou se não houver memória suficiente
para a nova instância retorna NULL
*/
complex COMPread(FILE* f);
/* Retorna o complexo soma dos argumentos c0 e c1
PRE: c0 != NULL && c1 != NULL
Excepção: Se não houver memória suficiente para a nova instância
retorna NULL
*/
complex COMPadd(complex c0, complex c1);
#endif
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 4/10
Estruturas de dados
had
implementação
/* ADT Complex (complex.c)
2004, 2005 had
*/
#include <stdlib.h>
#include "complex.h"
/* ============================
Definição da estrutura do ADT Complex
============================*/
struct COMPstruct { float re, im; };
/* ============================
Definição das funções do interface
============================*/
/* Aloca memória para nova instância do ADT Complex e retorna ponteiro para ela.
Excepção: Senão houver memória suficiente para o ADT retorna NULL
*/
complex COMPinit(float re, float im) {
complex tmp=(complex) malloc (sizeof *tmp);
if (tmp) {
tmp->re=re;
tmp->im=im;
}
return tmp;
};
/* Liberta memória reservada para ADT Complex
PRE: c != NULL
*/
void COMPfree(complex c) {
free(c);
};
/* Escreve a instância de complexo apontada por c no stream f
em modo texto. Retorna 1.
PRE: c != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int COMPprint(complex c, FILE* f){
int n0=1, n1=!EOF, n2=1;
if (c->re != 0) n0=fprintf (f, "%f", c->re);
if (c->im > 0) n1=fputc('+', f);
if (c->im != 0) n2=fprintf (f, "%fj", c->im);
return (n0<0 || n1==EOF || n2<0) ? 0 : 1;
};
/* Escreve a instância de complexo apontada por c no stream f
em modo binário. Retorna 1.
PRE: c != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int COMPwrite(complex c, FILE* f){
return fwrite (c, sizeof (*c), 1, f);
};
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 5/10
Estruturas de dados
had
/* Retorna uma nova instância de complexo lida do stream f em modo binário
PRE: f != NULL
Excepção: Se ocorrer erro de leitura ou se não houver memória suficiente
para a nova instância retorna NULL
*/
complex COMPread(FILE* f){
int n;
complex c=COMPinit(0,0);
/* inicializa instância vazia */
if (!c) return NULL;
n=fread (c, sizeof (*c), 1, f); /* lê-a do stream f */
if (n) return c;
else {COMPfree(c); return NULL;} /* e retorna-a ou NULL se erro de leitura*/
};
/* Retorna o complexo soma dos argumentos c0 e c1
PRE: c0 != NULL && c1 != NULL
Excepção: Se não houver memória suficiente para a nova instância
retorna NULL
*/
complex COMPadd(complex c0, complex c1){
return COMPinit(c0->re + c1->re, c0->im + c1->im);
};
cliente
/* testcomp.c
*/
#include "complex.h"
int main()
{
complex a = COMPinit(1,2);
complex b = COMPinit(1,3);
complex c;
FILE *f;
c=COMPadd (a, b);
/* 2+5j */
f=fopen("file.dat", "w"); COMPwrite(c, f);
f=fopen("file.dat", "r"); a=COMPread(f);
COMPprint(a, stdout);
putchar ('\n');
/*
printf("%f\n", c->re;)
c->im = 4.5;
*/
COMPfree (a); COMPfree (b); COMPfree (c);
getchar();
return 0;
}
fclose(f);
fclose(f);
Pode-se mostrar que a interface do ADT é opaca, isto é separa efectivamente a implementação do
cliente, se se tentar a partir do cliente aceder directamente aos membros de dados de uma instância
do ADT complex (as suas variáveis de instância).
Assim descomentando qualquer das linhas a vermelho o compilador retorna um erro quando tenta
compilar:
comptest.c:16: error: dereferencing pointer to incomplete type
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 6/10
Estruturas de dados
had
De facto em tempo de compilação o cliente incluí o interface (#include "complex.h") onde está
declarado o ponteiro complex para a estrutura COMPstruct. No entanto esta está definida no
ficheiro complex.c que não é incluído no cliente (é sim linkado posteriormente).
Deste modo, em tempo de compilação não é possível determinar a definição da estrutura
COMPstruct. Em particular não é conhecido que esta tem dois membros de dados tipo float,
chamados re e im, logo o compilador retorna o erro acima quando se tenta aceder a um deles
através do ponteiro, p. ex:
c->im
Aliás apenas a tentativa de saber o tamanho da variável apontada pelo ponteiro c:
sizeof (*c)
resulta no mesmo erro. Já:
sizeof (c)
retorna 4 num compilador de 32 bits, pois neste caso está-se a determinar o tamanho do ponteiro e
não da variável por este apontada.
Uma forma de aceder às variáveis de instância dos ADTs, consiste em definir funções chamadas
acessores. Estas funções são definidas no ficheiro de implementação (*.c) do ADT e declaradas no
seu interface (*.h) permitindo aceder (ler ou escrever) aos membros de dados de cada instância do
ADT.
Podia-se por exemplo ter um acessor de escrita para a parte real do complexo, a variável re:
void COMPSetReal (complex c, float r) {
c->re = r;
}
e um acessor de leitura para a mesma variável:
float COMPGetReal (complex c) {
return c->re;
}
No entanto tal deve ser evitado, e só efectuado se absolutamente necessário, pois reduz a opacidade
do interface, abrindo a implementação ao código cliente, o que de certa forma levanta a abstracção
do ADT.
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 7/10
Estruturas de dados
had
Anexo A - Template para ADT múltipla instância
Seguidamente é apresentado um template que poderá ser seguido para programar ADTs múltipla
instância:
interface
/* Breve descrição do ADT e identificação do autor (adt.h)
*/
#ifndef _ADT_ /* por convenção o nome do ficheiro sem extensão */
#define _ADT_
#include <stdio.h>
/* include de outros headers (*.h) ABSOLUTAMENTE necessários. */
/* Definição de Macros ABSOLUTAMENTE necessárias. p. ex:
#define N 10
...
*/
/* ============================
ponteiro para instância do ADT
============================*/
/* por convenção o ponteiro declara-se em minúsculas */
typedef struct ADTstruct* adt;
/* ============================
Declaração das funções do interface (colecção de operações)
============================*/
/* Aloca uma nova instância do ADT e retorna ponteiro para ela.
Excepção: Senão houver memória suficiente para o ADT retorna NULL
*/
adt ADTnew(/* parâmetros necessários: int x, float .... */);
/* Disponibiliza memória alocada a uma instância do ADT
PRE: p != NULL
*/
void ADTdel(adt p);
/* Escreve a instância do adt apontada por p no stream f
em modo texto. Retorna 1.
PRE: p != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int ADTprint(adt p, FILE* f);
/* Escreve a instância do adt apontada por pdate no stream f
em modo binário. Retorna 1.
PRE: p != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int ADTwrite(adt p, FILE* f);
/* Retorna uma nova instância do adt lida do stream f em modo binário
PRE: f != NULL
Excepção: Se ocorrer erro de leitura ou se não houver memória suficiente
para a nova instância retorna NULL
*/
adt ADTread(FILE* f);
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 8/10
Estruturas de dados
had
/* Declaração de outras funções necessárias ao ADT
...
*/
#endif
implementação
/* Breve descrição do ADT e identificação do autor (adt.c)
*/
#include "adt.h" /* include header (interface) do próprio adt */
#include <stdlib.h>
/* include de outros headers (*.h) necessários.*/
/* Definição de Macros necessárias. p. ex:
#define STR "abcdef"
*/
/* ============================
Definição da estrutura do ADT
============================*/
struct ADTstruct {
/* variáveis de instância do adt.
Podem ser de qualquer tipo (mesmo outros ADTs).
int a;
char s[35];
*/
};
/* Se necessário definir funções privadas ao ficheiro adt.c
p. ex:
static int func(int 4, ... ) {
....
}
*/
/* ============================
Definição das funções do interface
============================*/
/* Aloca uma nova instância do ADT e retorna ponteiro para ela.
Excepção: Senão houver memória suficiente para o ADT retorna NULL
*/
adt ADTnew(/* parâmetros necessários: int x, float .... */) {
adt p = (adt) malloc (sizeof *p);
if (p) {
/*
Inicializa variáveis da nova instância. p. ex.:
p->a=x;
... */
}
return p;
};
/* Disponibiliza memória alocada a uma instância do ADT
PRE: p != NULL
*/
void ADTdel(adt p) {
/* outras operações necessárias como p. ex:
libertação de estruturas de dados da memória
fecho de ficheiros, ... */
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 9/10
Estruturas de dados
had
free (p);
};
/* Escreve a instância do adt apontada por p no stream f
em modo texto. Retorna 1.
PRE: p != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int ADTprint(adt p, FILE* f){
/* usa funções como:
fprintf (FILE*, const char *, ...);
fputf (int, FILE*);
*/
return 1; /* ou 0 se erro escrita*/
};
/* Escreve a instância do adt apontada por pdate no stream f
em modo binário. Retorna 1.
PRE: p != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int ADTwrite(adt p, FILE* f) {
/* Em grande parte dos casos basta:
*/
return fwrite (p, sizeof (*p), 1, f);
};
/* Retorna uma nova instância do adt lida do stream f em modo binário
PRE: f != NULL
Excepção: Se ocorrer erro de leitura ou se não houver memória suficiente
para a nova instância retorna NULL
*/
adt ADTread(FILE* f) {
/* Em grande parte dos casos basta:
*/
adt p=ADTnew(/*...*/);
/* inicializa instância vazia */
if (!c) return NULL;
int n=fread (p, sizeof (*p), 1, f); /* lê-a do stream f */
if (n) return p;
else { ADTdel(p); return NULL; } /* e retorna-a ou NULL se erro de leitura*/
};
/* Implementação de outras funções declaradas no interface
...
*/
http://w3.ualg.pt/~hdaniel/ed
ED 2004/2005 T16b - 10/10