Uma implementação de Tabelas de Dispersão
Ficheiro ED/TabelaDispersao.java
package ED;
/** Interface do TAD Tabela de Dispersão */
public interface TabelaDispersao {
/** Insere um elemento na tabela de dispersão. Não insere se já
existir outro com uma chave igual.
@param elemento elemento a inserir.
@return true sse inserir o elemento. */
boolean insere(Dispersavel elemento);
/** Remove um elemento da tabela de dispersão.
@param chave chave do elemento a remover.
@return true sse o elemento existia. */
boolean remove(Chave chave);
/** Procura um elemento na tabela de dispersão.
@param chave chave do elemento a procurar.
@return o elemento com a chave dada ou null se não
existe nenhum na tabela com a chave dada. */
Object pesquisa(Chave chave);
}
Ficheiro ED/Dispersavel.java
package ED;
/** Interface dos objectos inseríveis numa Tabela de Dispersão */
public interface Dispersavel {
/** Devolve a chave do objecto.
@return a chave do objecto. */
Chave chave();
}
Ficheiro ED/Chave.java
package ED;
/** Chave a ser usada no acesso a uma Tabela de Dispersão */
public interface Chave {
/** Calcula o valor da função de dispersão para a chave.
@param dimensao dimensão da tabela de dispersão
@return um inteiro entre 0 e dimensao-1 */
int dispersao(int dimensao);
/** Compara duas chaves.
@param chave a outra chave a comparar
@return true sse as duas chaves são iguais */
boolean igual(Chave chave);
}
Ficheiro ED/TabelaDispSondLinear.java
package ED;
/** Implementação de uma Tabela de Dispersão Fechada com Sondagem
Linear */
public class TabelaDispSondLinear implements TabelaDispersao {
/** Capacidade por omissão. */
private static final int CAPACIDADE = 101;
/** Entrada da tabela que assinala a remoção de um elemento. */
static final EntradaTabela APAGADA = new EntradaTabela(null);
/** Contentor para os elementos da tabela. */
private EntradaTabela[] elementos;
/** Ocupação da tabela. */
private int numElementos;
/** Tipo das entradas da tabela. */
private static class EntradaTabela {
Dispersavel elemento;
EntradaTabela(Dispersavel elemento)
{
this.elemento = elemento;
}
}
/** Cria uma nova tabela de dispersão. */
public TabelaDispSondLinear()
{
this(CAPACIDADE);
}
/** Cria uma nova tabela de dispersão com a capacidade dada. */
public TabelaDispSondLinear(int capacidade)
{
elementos = new EntradaTabela[capacidade];
numElementos = 0;
}
/** Procura a posição do elemento com a chave dada.
@param chave chave do elemento a procurar.
@return o índice da posição do elemento com a chave dada; se não
existir, devolve o da primeira posição livre encontrada. */
private int posicao(Chave chave)
{
int pos = chave.dispersao(elementos.length);
// percorre a tabela até encontrar o elemento com a chave
// dada ou uma posição livre
while (elementos[pos] != null &&
(elementos[pos] == APAGADA ||
!elementos[pos].elemento.chave().igual(chave)))
pos = (pos + 1) % elementos.length;
return pos;
}
/** Procura a posição onde pode inserir um elemento com a chave
dada. Permite reutilizar posições de elementos que foram
anteriormente removidos.
@param chave chave do elemento a inserir.
@return o índice da posição onde inserir o elemento; se já
existe um com a chave dada na tabela, devolve o seu índice. */
private int posicaoParaInserir(Chave chave)
{
int pos = chave.dispersao(elementos.length);
int livre;
// procura uma posição livre ou cujo conteúdo tenha sido removido
// ou que contenha o elemento com chave chave
while (elementos[pos] != null && elementos[pos] != APAGADA &&
!elementos[pos].elemento.chave().igual(chave))
pos = (pos + 1) % elementos.length;
livre = pos;
// verifica se o elemento já existe na tabela
while (elementos[pos] != null &&
(elementos[pos] == APAGADA ||
!elementos[pos].elemento.chave().igual(chave)))
pos = (pos + 1) % elementos.length;
return (elementos[pos] == null) ? livre : pos;
}
/** Insere um elemento na tabela de dispersão.
@see TabelaDispersao#insere(Dispersavel) */
public boolean insere(Dispersavel elemento)
{
int pos = posicaoParaInserir(elemento.chave());
if (elementos[pos] == null)
{
elementos[pos] = new EntradaTabela(elemento);
++numElementos;
return true;
}
else if (elementos[pos] == APAGADA)
{
elementos[pos] = new EntradaTabela(elemento);
return true;
}
else
return false;
}
/** Remove um elemento da tabela de dispersão.
@see TabelaDispersao#remove(Chave) */
public boolean remove(Chave chave)
{
int pos = posicao(chave);
if (elementos[pos] == null)
return false;
else {
elementos[pos] = APAGADA;
return true;
}
}
/** Procura um elemento na tabela de dispersão.
@see TabelaDispersao#pesquisa(Chave) */
public Object pesquisa(Chave chave)
{
EntradaTabela conteudo = elementos[posicao(chave)];
return (conteudo == null) ? null : conteudo.elemento;
}
} // fim da definição da classe TabelaDispSondLinear
Exemplo de utilização
Ficheiro PC.java
import ED.*;
/** PC's da Universidade de Évora. */
public class PC implements Dispersavel {
private int numero; // número do PC
private int sala; // sala onde o PC está
private String edificio; // edifício onde o PC está (3 maiúsculas)
private boolean funciona; // se o PC funciona
private String problema; // descrição do problema que o afecta
private String processador; // processador do PC
...
PC(int numero, int sala, String edificio, String processador, ...)
{
this.numero = numero;
this.sala = sala;
this.edificio = edificio;
// quando são adquiridos, os PC's estão em bom estado
funciona = true;
problema = null;
this.processador = processador;
...
}
// um PC é univocamente identificado pelo triplo (numero, sala, edificio)
static class ChavePC implements Chave {
private int numero, sala;
private String edificio;
ChavePC(int num, int sal, String ed)
{
numero = num;
sala = sal;
edificio = ed;
}
public int dispersao(int dimensao)
{
int disp = 0;
for (int pos = 0; pos < 3; ++pos)
disp = disp * 26 + (edificio.charAt(pos) - 'A');
return (disp * 256 + sala * numero) % dimensao;
}
public boolean igual(Chave chave)
{
ChavePC chv = (ChavePC) chave;
return numero == chv.numero && sala == chv.sala &&
edificio.equals(chv.edificio);
}
}
/** Cria e devolve uma chave com os elementos fornecidos. */
public static Chave chave(int numero, int sala, String edificio)
{
return new ChavePC(numero, sala, edificio);
}
public Chave chave()
{
return new ChavePC(numero, sala, edificio);
}
...
public void avariou(String problema)
{
funciona = false;
this.problema = problema;
}
...
}
Utilizações
import ED.*;
...
// criação de uma tabela de PC's
TabelaDispersao tabelaPCs = new TabelaDispSondLinear(2003);
PC umPC;
...
// algumas inserções
tabelaPCs.insere(new PC(1, 144, "CLV", "AMD"));
tabelaPCs.insere(new PC(2, 144, "CLV", "Pentium"));
...
// uma pesquisa
... tabelaPCs.pesquisa(PC.chave(1, 144, "CLV")) ...;
// e uma remoção
tabelaPCs.remove(PC.chave(1, 144, "CLV"));
...
// esta pesquisa falha
tabelaPCs.pesquisa(PC.chave(1, 144, "CLV"));
// mais uma inserção
tabelaPCs.insere(new PC(1, 144, "CLV", "Cyrix"));
...
// este PC avariou
umPC = (PC) tabelaPCs.pesquisa(PC.chave(1, 144, "CLV"));
umPC.avariou("rato não funciona");
...
// mais inserções
tabelaPCs.insere(new PC(12, 130, "CES", "AMD"));
tabelaPCs.insere(new PC(12, 130, "CES", "Pentium II"));
tabelaPCs.insere(new PC(4, 137, "CLV", "Pentium 3"));
tabelaPCs.insere(new PC(3, 101, "MIT", "386"));
tabelaPCs.insere(new PC(6, 175, "CLV", "286"));
...