Tipos Abstractos de
Dados (TADs) e Java
Neste capítulo apresentamos a metodologia de desenvolvimento dos
TADs em Java, introduzimos o conceito de estrutura linear e sua
implementação utilizando a estrutura estática e dinâmica.
O QUE SÃO TADS.................................................................................................................... 1
IMPLEMENTAR TAD EM JAVA .......................................................................................... 1
ESTRUTURAS .......................................................................................................................... 2
ESTRUTURA ESTÁTICA ....................................................................................................... 3
ESTRUTURA DINÂMICA ...................................................................................................... 4
LISTAS SIMPLESMENTE LIGADAS/ENCADEADAS ....................................................................... 4
Inserir Elemento na Cabeça da Lista................................................................................. 6
Inserir Elemento na Cauda da Lista .................................................................................. 8
Remoção do nó................................................................................................................... 9
LISTAS DUPLAMENTE ENCADEADA/LIGADAS ......................................................................... 10
LISTAS CIRCULARES .............................................................................................................. 12
O que são TADs
Na noção de Tipo Abstracto de Dados (TAD) devemos especificar as
propriedades fundamentais de um tipo de dado, de um modo independente da
sua implementação numa linguagem.
Implementar TAD em Java
Implementar um tipo abstracto de dados (TAD) envolve três passos:
1. Definição de um API Java (Application Programming Interface), ou
simplesmente interface, que descreve os métodos que o TAD suporta e
como eles são declarados e usados.
2. Escolha da representação concreta do TAD para usar na implementação.
Basicamente vamos considerar dois tipos de representação:
ƒ
Footer
Estrutura estática (utilização de tabelas) ou
Page 1
T I P O S
ƒ
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
Estrutura dinâmica (utilização das listas ligadas/encadeadas, arvores,
etc.).
3. Implementação da interface através de uma classe e tendo em conta a
representação escolhida no ponto 2.
Para todo o TAD pode existir várias implementações, contudo todas as
implementações respeitam o interface definido.
Estruturas
Frequentemente precisamos agrupar vários elementos/dados num conjunto. A
partida podemos não saber o número exacto de elementos a ser agrupados. Em
cada instante podemos acrescentar ou remover elemento ao conjunto. Em
programação consideramos dois tipos de estruturas que permitem guardar uma
colecção de elementos: estrutura estática e estrutura dinâmica.
Os elementos podem ser organizados de um modo distinto. Entre as
organizações possíveis destacam-se:
ƒ
Linear. Existe uma ordem entre os elementos da colecção. O primeiro
elemento, o segundo elemento,..., o último elemento.
ƒ
Hierárquica. A organização de elementos pode ser representada em forma
de árvore.
ƒ
Grafo. A organização de elementos pode ser representada em forma de
rede.
Neste capítulo são descritos exemplos de implementação de uma estrutura
linear, utilizando uma estrutura estática e uma estrutura dinâmica. Em seguida é
apresentado a interface da estrutura linear.
interface estruturaLinear {
// verifica se a estrutura tem elementos
public boolean estaVazia();
// devolve a quantidade de elementos da estrutura
public int tamanho();
// insere um elemento no início da estrutura
public void inserir(Object p0);
// insere um elemento no fim da estrutura
public void inserirCauda(Object p0);
// remove um elemento do início da estrutura
public Object remover();
// remove um elemento do fim da estrutura
public Object removerCauda();
}
Algoritmos e Tipos Abstractos de Informação, 2003
Page 2
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
Estrutura Estática
Estrutura estática caracteriza-se por possuir um espaço alocado e inalterável
antes da sua utilização. A estrutura estática não pode conter mais elementos do
que o previsto inicialmente. A estrutura estática é representada em termos da
linguagem de programação JAVA através do uso de tabelas. Numa tabela, uma
vez alocado o espaço, este permanece inalterável, independentemente das
operações de inserção e de remoção de elementos.
Em seguida é apresentado uma implementação da interface estruturaLinear
por meio da classe ArrayCircularList. Esta implementação baseia-se no uso
de uma estrutura estática para guardar os elementos de uma colecção. Optou-se
por utilizar uma tabela circular.
public class ArrayCircularList implements estruturaLinear {
protected Object[] array;
protected int start,end,number;
public pArrayList(int maxsize){
array = new Object[maxsize];
start = end = number = 0;
}
public boolean estaVazia(){
return number == 0;
}
public boolean isFull(){
return number >= array.length;
}
public int tamanho(){
return number;
}
public void inserir(Object o){
if(number < array.length){
array[start = (++start % array.length)] = o;
number++;
}
}
public void inserirCauda (Object o){
if(number < array.length){
array[end] = o;
end = (--end + array.length) % array.length;
number++;
}
}
public Object remover(){
if(estaVazia())
return null;
number--;
int i = start;
start = (--start + array.length) % array.length;
Algoritmos e Tipos Abstractos de Informação, 2003
Page 3
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
return array[i];
}
public Object removerCauda(){
if(estaVazia())
return null;
number--;
return array[end = (++end % array.length)];
}
}
Estrutura Dinâmica
Estrutura dinâmica caracteriza-se por poder ser alterada à medida que ocorre a
sua manipulação através de inserção e remoção de elementos. A dimensão da
estrutura dinâmica não tem limitações, sendo a sua única restrição a limitação
física do espaço de memória do computador onde ocorre a execução do
algoritmo.
A estrutura dinâmica é criada com a utilização do tipo de dado Referencia
(apontador).
As estruturas dinâmicas podem ser criadas para representar colecções de
elementos com diferentes tipos de organização. A estrutura linear pode ser
implementada utilizando estruturas dinâmicas representadas pelas listas
simplesmente ligadas, listas duplamente ligadas, listas circulares, etc.
Em seguida é apresentado um exemplo de utilização destas listas na
implementação de interface estruturaLinear.
Listas simplesmente ligadas/encadeadas
Uma lista encadeada é a forma mais simples de representar uma colecção de
elementos que juntos formam uma ordenação linear. Cada elemento da
colecção é representado pelo objecto da classe No .
A ordenação é determinada armazenando num nó uma referência para um
elemento e uma referência, chamada de próximo, para o próximo nó da
colecção.
Algoritmos e Tipos Abstractos de Informação, 2003
Page 4
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
Figure 1. Lista encadeada
A referência próximo dentro de um nó pode ser vista como uma ligação ou
apontador para outro nó.
O primeiro e os últimos nós de uma lista são chamados, respectivamente, de
cabeça e cauda da lista.
A cauda é um nó que tem a referência próximo igual a null, indica o fim da
lista.
A deslocação de um nó para outro seguindo a referência próximo é conhecido
como caminhar na lista / percorrer a lista.
Uma lista encadeada definida desta maneira é conhecida como uma lista
simplesmente encadeada.
Diferente de uma tabela, uma lista simplesmente encadeada não tem tamanho
fixo pré-determinado e aloca espaço proporcionalmente ao número de
elementos.
Para implementar uma lista simplesmente encadeada em Java, é definida a
seguir uma classe No:
class No {
private Object elemento;
private No proximo;
// construtores
public No( ) {
this( null, null );
}
public No( Object e, No p ) {
elemento = e;
proximo = p; }
void setElemento( Object novoElemento ) {
elemento = novoElemento;
}
Algoritmos e Tipos Abstractos de Informação, 2003
Page 5
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
void setProximo( No novoProximo ) {
proximo = novoProximo;
}
Object getElemento( ) {
return elemento;
}
No getProximo( ) {
return proximo;
}
}
A interface estruturaLinear pode ser implementada usando uma lista
simplesmente encadeada na classe ListaEncadeada da seguinte maneira:
class ListaEncadeada implements estruturaLinear
{
// Referência para a cabeça da lista
private No cabeca;
// Referência para a cauda da lista
private No cauda;
// Número de elementos na lista
private int tamanho;
public ListaEncadeada ( ) { // Inicializa a lista
cabeca = null;
cauda = null;
tamanho = 0;
}
public int tamanho( ) { //Retorna o tamanho actual da lista
return tamanho;
}
public No getCabeca( ) { //Retorna retefencia da cabeca da
lista
return cabeca;
}
public No getCauda( ) { //Retorna retefencia da cauda da lista
return cauda;
}
public boolean estaVazia() {
return tamanho == 0;
…...
}
…
}
Inserir Elemento na Cabeça da Lista
Numa lista simplesmente encadeada podemos inserir ou remover um elemento
na cabeça da lista no tempo de execução O(1).
Algoritmos e Tipos Abstractos de Informação, 2003
Page 6
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
Figure 2. Antes da inserção
Figure 3. Criar novo nó
Figure 4. Depois da inserção
O código para esta operação é o seguinte:
public void inserir(Object obj ) {
No aux = new No (obj, cabeca);
if (estaVazia()) cauda = aux;
cabeca = aux;
tamanho ++;
}
Algoritmos e Tipos Abstractos de Informação, 2003
Page 7
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
Inserir Elemento na Cauda da Lista
Se não tiver a referencia para o último elemento da lista (cauda), o tempo de
execução desta operação é O(n). Isto porque temos que aceder ao endereço do
último elemento da lista percorrendo todos os elemento a partir da cabeça da
lista. Como no nosso exemplo a representação escolhida para a lista possui uma
variável com a referencia para o último elemento (cauda), o tempo de execução
desta operação é O(1).
Figure 5. Antes da inserção
Figure 6. Criar novo no
Figure 7. Depois da inserção
O código para esta operação é o seguinte:
public void inserirCauda(Object obj ) {
Algoritmos e Tipos Abstractos de Informação, 2003
Page 8
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
No aux = new No (obj, null);
if (estaVazia()) cabeca = aux;
else cauda.setProximo(aux);
cauda = aux;
tamanho ++;
}
Remoção do nó
Podemos remover um No de cabeça ou de cauda da lista.
O método seguinte permite remover o elemento da cabeça da lista.
public Object remover() {
Object obj = null;
if (!estaVazia())
{
obj = cabeca.getElemento();
if (cabeca == cauda) cauda = null;
cabeca = cabeca.getProximo();
tamanho --;
}
return obj;
}
A remoção do elemento de cauda da lista obriga percorrer os elementos desde a
cabeça da lista até ao penúltimo elemento.
public Object removerCauda() {
Object obj = null;
if (!estaVazia())
{
obj = cauda.getElemento();
if (tamanho() == 1) {
cabeca = null;
cauda = null;
}
else {
No aux = cabeca;
while (aux.getProximo().getProximo()!= null)
aux = aux.getProximo();
aux.setProximo(null);
cauda = aux;
}
tamanho --;
}
return obj;
}
Algoritmos e Tipos Abstractos de Informação, 2003
Page 9
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
Listas duplamente encadeada/ligadas
Cada No da lista duplamente encadeada possui uma ligação não só para o
próximo elemento, mas também para o elemento anterior da lista.
Esta variante da lista simplesmente encadeada permite a inserção e a remoção
na cabeça e na cauda da lista com o tempo de execução O(1).
Para implementação deste tipo de lista devemos especificar classe NoD
composto por elemento, referência para o elemento seguinte e referência para o
elemento anterior. O código desta classe é o seguinte:
class NoD {
private Object elemento;
private NoD prox;
private NoD prev;
public NoD(Object e) {
elemento=e;
prox=null;
prev=null;
}
public Object getElemento(){return elemento ;}
public NoD getProx(){return prox ;}
public void setProx(NoD no)
{prox=no;}
public NoD getPrev(){return prev ;}
public void setPrev(NoD no)
{prev=no;}
}
Assim o código para lista dupla é o seguinte:
class ListaDupla implements estruturaLinear{
private NoD cabeca; // guarda o inicio
private NoD cauda; // guarda o fim
int tam;
public ListaDupla() {
tam=0;
cabeca=cauda=null;
}
Algoritmos e Tipos Abstractos de Informação, 2003
Page 10
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
public NoD getCabeca() {
return cabeca;
}
public boolean estaVazia()
{
return (tam==0);
}
public int tamanho()
{
return tam;
}
public void inserir(Object e)
{
NoD novo=new NoD(e);
if(estaVazia())
cabeca=cauda=novo;
else
{
cabeca.setPrev(novo);
novo.setProx(cabeca);
cabeca=novo;
}
tam++;
}
public void inserirCauda(Object e)
{
NoD novo=new NoD(e);
if(estaVazia())
cabeca=cauda=novo;
else
{
cauda.setProx(novo);
novo.setPrev(cauda);
cauda=novo;
}
tam++;
}
public Object remover()
{
Object aux = null;
if(!estaVazia())
{aux = cabeca.getElemento();
if (tam==1) cabeca=cauda=null;
else
{
cabeca=cabeca.getProx();
cabeca.setPrev(null);
Algoritmos e Tipos Abstractos de Informação, 2003
Page 11
T I P O S
A B S T R A C T O S
D E
D A D O S
( T A D S )
E
J A V A
}
tam--;
}
return aux;
}
}
Listas circulares
Listas circulares são listas onde o primeiro e último elemento estão ligados.
Podemos utilizar a estrutura dinâmica simplesmente encadeada ou duplamente
encadeada para implementação da lista circular.
Algoritmos e Tipos Abstractos de Informação, 2003
Page 12