Tipos Abstratos de Dados em Java

Afluentes: Estrutura de Dados

Tipos Abstratos de Dados

Os Tipos Abstratos de dados, ou TADs, são definidos como uma especificação de um conjunto de dados e operações que podem ser executadas sobre esses dados. Além disso, é uma metodologia de programação que tem como proposta reduzir a informação necessária para a criação/programação de um algoritmo através da abstração das variáveis envolvidas em uma única entidade fechada com operações próprias à sua natureza.

A idéia que permeia os tipos abstratos de dados é a de que os tipos simples ou atômicos suportados diretamente pela maioria das linguagens de programação nem sempre são suficientemente expressivos para representar e manipular tipos de dados mais complexos recorrentemente requeridos por programas de computador. Desta forma, novos tipos de dados devem ser definidos. As operações lógico/matemáticas a serem executadas sobre tais tipos de dados definidos não são diretamente suportadas pelas linguagens de programação, desta forma, funções devem ser definidas para a correta e efetiva manipulação de tais tipos de dados. A agregação dos tipos de dados definidos acrescida de suas funções relacionadas especificamente desenvolvidas para manipular tais estruturas é chamada de tipo abstrato de dados.

TADs permitem o desenvolvimento modular de aplicações, fato que propicia uma maneira organizada e eficiente para a criação de programas.

Organizando TADs em Módulos

As TADs normalmente são organizados em arquivos separados do programa principal, também conhecidos como módulos. Pode-se criar um arquivo contendo todas as funções e tipos de dados necessários para a implementação da TAD.

Exemplo de TAD

public class Fracao {
	private int numerador;
	private int denominador;
	
	public Fracao(int numerador, int denominador) {
		setNumerador(numerador);
		setDenominador(denominador);
	}

	public int getNumerador() {
		return numerador;
	}

	public void setNumerador(int numerador) {
		this.numerador = numerador;
	}

	public int getDenominador() {
		return denominador;
	}

	public void setDenominador(int denominador) {
		this.denominador = denominador;
	}
	
	public double getValorReal() {
		return numerador / denominador;
	}
	
	public Fracao multiplicaFracao(Fracao f1, Fracao f2) {
		return new Fracao(
				f1.getNumerador() * f2.getNumerador(),
				f1.getDenominador() * f2.getDenominador());
	}
}

Ponto

public class Ponto {
	private double x;
	private double y;
	
	public Ponto(double d, double e) {
		setPonto(d, e);
	}
	
	public void setPonto(double x, double  y) {
		setX(x);
		setY(y);
	}

	public double getX() {
		return x;
	}

	public void setX(double x) {
		this.x = x;
	}

	public double getY() {
		return y;
	}

	public void setY(double y) {
		this.y = y;
	}
	
	public void soma(Ponto p) {
		x += p.getX();
		y += p.getY();
	}
	
	public double distancia(Ponto p) {
		double dx = p.getX() - x;
		double dy = p.getY() - y;
		return (double) Math.sqrt(dx * dx + dy * dy);
	}
	
	public String toString() {
		return "(" + x + ", " + y + ") ";
	}
}

Main (Ponto)

public class Main {
	public static void main(String[] args) {
		Ponto p1 = new Ponto(3.0, 5.0);
		System.out.println(p1);
		
		Ponto p2 = new Ponto(4.0, 1.0);
		System.out.println(p2);
		
		p1.soma(p2);
		System.out.println(p1);
	}
}

Saída

(3.0, 5.0) 
(4.0, 1.0) 
(7.0, 6.0)

Exercícios 1

1. Quais são as duas partes constituintes necessárias para a definição de uma TAD;
2. Escreva um programa que faça uso do TAD Ponto definida anteriormente;
3. Acrescente novas operações ao TAD Ponto, tais como soma e subtração de pontos;
4. Crie uma TAD para manipulação de strings;
5. Crie uma TAD para manipulação de números complexos;
6. Toda função que compõe uma TAD deve receber necessariamente pelo menos um atributo. Qual é este atributo, justifique sua resposta;

Resposta da 6: o atributo necessário é o ponteiro para o objeto da qual se quer manipular com a função. A questão é que no java isso é implícito.

Exercícios 2

Crie uma TAD para manipulação de vetores de doubles

Como estrutura de dados para esta TAD utilize:

public class Vetor {
	private int tamanho;
	private double elementos[];
	
	//...
}

• A TAD deve permitir a manipulação de vetores de tamanho variável, ou seja, o tamanho do vetor a ser manipulado deve ser informado pelo usuário e alocado dinamicamente. O constructor deve se responsabilizar por tal criação.
• Crie uma função que some todos os elementos do vetor;
• Crie a função multiplicaVetor(int n) que multiplica todos os elementos do vetor pelo elemento n;
• Crie a função quadradosVetor() que eleva todos os elementos do vetor ao quadrado;
• Crie a função vetor somaVetor(Vetor v) que deve testar se os dois vetores possuem o mesmo tamanho e em caso afirmativo somar os elementos do vetor atual aos do vetor v;