Universidade Federal Rural de Pernambuco
Departamento de Estatística e Informática
Tipos Abstratos de Dados
Paradigmas de Programação
Prof. Gláucya Carreiro Boechat
[email protected]
Abstração

Concentrar mais em idéias gerais do que em
detalhes específicos.



Em Análise - concentrar em aspectos essenciais
de um problema e ignorar detalhes irrelevantes.
Em Programação - distinguir entre “o que” um
trecho de programa faz e “como” foi implementado.
Sempre que um novo procedimento ou função
é inserido no programa, um novo nível de
abstração é criado.
Paradigmas de Programação prof Gláucya Carreiro Boechat
2
Abstração - Tipos Fundamentais

Abstração de Processo



Oferece uma maneira do programa especificar que algum
processo deve ser feito, sem oferecer os detalhes de como será
feito
Todos subprogramas são abstrações de processo
Exemplo



Ordena_int(lista, comp_lista);
Sort_float(array, len);
Abstração de Dados

Toda Abstração de Dado suas operações são definidas como
abstração de processo
Paradigmas de Programação prof Gláucya Carreiro Boechat
3
Tipos primitivos: exemplo de abstração
// float: abstração de um número em ponto
flutuante
float a, b, c, s;
// tipo de dados é associado a um domínio de valores
b = 1.0;
c = 2.0;
// tipo de dados é associado a conjunto de operações
a = b + c;
a+=;
c++;
// tipo de dados associado a uma representação interna
8 bits, 16 bits, 32 bits ...
Paradigmas de Programação prof Gláucya Carreiro Boechat
4
Modulos




Modulos são "containers" sintáticos contendo
subprogramas e grupos de dados relacionados
logicamente
Modularização: processo de projetar os módulos de
um programa
A compreensão do programa pelos mantenedores
seria impossível sem organização modularizada
Ponto Crítico:

Quando o projeto de um programa estende-se por milhares
de linhas, recompilá-lo totalmente a cada atualização do
código é absolutamente inviável - daí a necessidade de
modularizá-lo
Paradigmas de Programação prof Gláucya Carreiro Boechat
5
Encapsulamento




Agrupamento de subprogramas e dados que é
compilado separada/independentemente
Também chamado de unidade de compilação
Muitas vezes são colocados em bibliotecas e postos
a disposição para serem reutilizados em outros
programas
Exemplo: Linguagens que oferecem a capacidade de agrupar
subprogramas e dados pode ser colocada em um arquivo,
então compilado independentemente

C, Fortran 90, Ada, Simula 67, C++
Paradigmas de Programação prof Gláucya Carreiro Boechat
6
Abstração de Dados


Um Tipo Abstrato de Dados (TAD) é um
encapsulamento que inclui somente um tipo
específico de dado e os subprogramas que fornecem
as operações para este tipo
Detalhes desnecessários da implementação do tipo
podem ser ocultos das unidades fora do
encapsulamento que o contém
dados
operações
Paradigmas de Programação prof Gláucya Carreiro Boechat
7
Abstração de Dados


Um objeto é uma variável (instância) de um tipo
abstrato de dados, declarada por alguma unidade de
programa
Programação Orientada a Objetos consiste no uso
de objetos no desenvolvimento do software
Paradigmas de Programação prof Gláucya Carreiro Boechat
8
Tipos de Dados Abstratos Definidos
pelo Usuário



Definição do tipo e as operações sobre objetos do
tipo estão contidas numa única unidade sintática
Outras unidades de programa podem ter permissão
para criar variáveis do tipo definido
A representação de objetos do tipo não é visível
pelas unidades de programa que usam o tipo
Paradigmas de Programação prof Gláucya Carreiro Boechat
9
Tipos de Dados Abstratos Definidos
pelo Usuário

As unidades de programa que usam um TAD
específico e chamado de Cliente
cliente
cliente
cliente
usa
Paradigmas de Programação prof Gláucya Carreiro Boechat
TAD
10
Exemplo - TAD - Pilha

Operações Abstratas







Cria(pilha)
Destroi(pilha)
Vazia(pilha)
Empilha(pilha, elemento)
Desempilha(pilha)
Topo(pilha)
Cria e inicializa um objeto na pilha
Desloca o armazenamento da pilha
Retorna (true) se a pilha estiver vazia
Empilha o elemento no topo da pilha
Remove o elemento do topo da pilha
Retorna uma copia do topo da pilha
Um Cliente do tipo pilha poderia ter uma seqüência de código
...
Cria(pilha1);
Empilha(pilha1, cor1);
If ( !Vazia(pilha)
temp = Topo(pilha)
...
Paradigmas de Programação prof Gláucya Carreiro Boechat
11
TAD SIMULA 67



Primeiras facilidades de linguagem para
suporte a TAD
Oferece encapsulamento, mas não ocultacao
de informacao
Forma Sintática
Class nome_da_classe
begin
-- declarações de variáveis da classe --- definições de subprogramas da classe –
-- seção de código da classe -end nome_da_classe
Paradigmas de Programação prof Gláucya Carreiro Boechat
12
TAD C++

Os Tipos Abstratos de Dados em C++ são as
chamadas classes


Classes do C++ são baseadas



Variáveis são declaradas como instâncias de classes
SIMULA67
struct do C
Os dados definidos na classe são os membros
de dados
Paradigmas de Programação prof Gláucya Carreiro Boechat
13
Funções Membro

Funções-membro




São as funções definidas na classe
Compartilhadas por todas as instâncias de classe
Cada instância tem seu próprio conjunto de
membros de dados
Pode ter sua definição completa dentro da classe
("inlined") ou apenas seu cabeçalho

#define
Paradigmas de Programação prof Gláucya Carreiro Boechat
14
Ocultacao da Informacao em C++

Cláusula private:


Cláusula public:


para entidades ocultas na classe
para as entidades visíveis aos clientes. Descreve
a interface com objetos da classe
Cláusula protected:

relacionada com herança
Paradigmas de Programação prof Gláucya Carreiro Boechat
15
Construtores




Funções-membro usadas para inicializar os
membros de dados de um objeto recém-criado
Possue o mesmo nome da classe
Pode-se sobrecarregar construtores
Não têm tipo de retorno, não usam return
Paradigmas de Programação prof Gláucya Carreiro Boechat
16
Destrutores




Implicitamente chamados quando se encerra
o tempo de vida de um objeto
O destrutor pode conter chamadas delete
para desalocar membros de
Nome do destrutor: ~ <nome_da_classe>
Não têm tipo de retorno, não usam return
Paradigmas de Programação prof Gláucya Carreiro Boechat
17
Exemplo
#include <iostream.h>
class pilha {
private:
int *ptr_pilha;
int tam_max;
int top_ptr ;
public:
pilha( ){ //** um construtor
ptr_pilha = new int [100];
tam_max = 99;
top_ptr = -1;
}
~pilha( ){
//** um destrutor
delete [ ] ptr_pilha;
}
void Empilha ( int elem) {
if (top_ptr = = tam_max)
cout << “Erro - pilha cheia\n”;
else ptr_pilha[ + + top_ptr ] = elem;
}
void Desempilha( ) {
if (top_ptr = = -1)
cout << “Erro - pilha vazia\n”;
else top_ptr -- ;
}
int Topo {
return ( ptr_pilha[top_ptr] );
}
}
Paradigmas de Programação prof Gláucya Carreiro Boechat
18
Exemplo
Código no cliente:
void main ( ) {
int top_one;
pilha stk;
stk.Empilha(42);
stk.Empilha(17);
top_one = stk.topo( );
stk.pop( );
...
}
Paradigmas de Programação prof Gláucya Carreiro Boechat
19
“Objeto Matriz” x “Objeto Vetor”

Em qual classe essa operação deve ser definida?
class Matriz {
friend Vetor mult(const Matriz&, const Vetor&);
...}
class Vetor {
friend Vetor mult(const Matriz&, const Vetor&);
...}
//** a função q usa os objetos Matriz e Vetor
Vetor mult(const Matriz& m1, const Vetor& v1){
..}
Todos os membros privados da classe são visiveis a todos os membros da
classe amiga
Se Matriz e Vetor pudessem ser definidas num único pacote, evitaríamos esta
Paradigmas de Programação construção pouco natural. prof
20
Gláucya Carreiro Boechat

TAD JAVA




Suporte para tipos abstratos similar a C++
Todos os tipos de dados definidos pelo
usuário são classes
Todos os subprogramas (métodos) em Java
somente podem ser definidos em classes
public e private são modificadores anexados
às definições de métodos/variáveis
Paradigmas de Programação prof Gláucya Carreiro Boechat
21
Pacotes - JAVA




Pacotes podem conter mais de uma classe
public e private são os chamados modificadores
Os membros sem modificador (e os membros
public) de uma classe são visíveis a todas as
classes do mesmo pacote (escopo de pacote)
Não há, portanto, necessidade de declarações
friend explícitas em Java
Paradigmas de Programação prof Gláucya Carreiro Boechat
22
Exemplo
public void push ( int elem) {
import java.io.*
if (top_index = = tam_max)
System.out.println(“Erro”);
class Pilha {
else ref_pilha[ + + top_index ] = elem;
}
private int [ ] ref_pilha;
public void pop ( ) {
private int tam_max,
if (top_index = = -1)
top_index ;
System.out.println(“Erro”);
else --top_index ;
public Pilha( ){//construtor
}
ref_pilha = new int [100];
public int top {
tam_max = 99;
return ( ref_pilha[top_index] );
top_index = -1;
}
}
} \\** fim da classe Pilha
Paradigmas de Programação prof Gláucya Carreiro Boechat
23
Exemplo
public class Testa_Pilha {
public static void main (String [ ] args) {
Pilha p1 = new Pilha( );
p1.push(42);
p1.push(29);
p1.pop( );
p1.pop( );
p1.pop( ); // Produz msg de erro
... }


Não há destrutor eliminado pela coleta de lixo implícita em
Java)
Observe o uso de variável de referência em vez de ponteiro
Paradigmas de Programação prof Gláucya Carreiro Boechat
24
Classes Parametrizadas em C++
Exemplo: suponha que o método construtor para a
classe pilha fosse:
pilha (int size ){
ptr_pilha = new int [size];
tam_max = size-1;
top_ptr = -1;
}
No cliente:
... pilha(150) p1;

Paradigmas de Programação prof Gláucya Carreiro Boechat
25
Classes genéricas em C++
#include <iostream.h>
template < class TIPO >
class pilha {
private:
TIPO *ptr_pilha;
int tam_max;
int top_ptr ;
public:
pilha( ){ //** um construtor
ptr_pilha = new TIPO [100];
tam_max = 99;
top_ptr = -1;
}
void desempilha ( )
{ top_ptr--; }
pilha (int size ){ // construtor sobrecarregado
ptr_pilha = new TIPO [size];
tam_max = size-1;
top_ptr = -1;
}
~pilha( ) { delete ptr_pilha; }
void empilhar( TIPO elem) {
if (top_ptr = = tam_max)
cout << “Erro - pilha cheia\n”;
else ptr_pilha[ + + top_ptr ] = elem;
}
TIPO topo {
return ( ptr_pilha[top_ptr] ); }
} \\** fim da classe pilha
Paradigmas de Programação prof Gláucya Carreiro Boechat
26