9.9 Exercício: Implementação
da Classe Dictionary
-
A classe Dicionário em Smalltalk comporta-se como
uma lista indexada.
-
Na realidade esta é a forma como uma instância
de Dictionary se mostra para o usuário.
-
Um Dictionary é implementado internamente como uma
tabela de Hashing, para melhor tempo de acesso.
-
Você vai implementar uma Classe Dicionário
em C++ que:
-
Utilize hashing encadeado e um vetor como tabela de hashing.
-
Utilize Strings como chaves.
-
Possua uma função de hashing que utilize shift
folding sobre o string-chave e mod(k,17) sobre o resultado do
folding.
-
Seja um dicionário genérico, sendo capaz, em
teoria, de armazenar objetos de qualquer tipo, através de ponteiros
void.
Na prática você vai implementar-lo para
inteiros, floats e strings.
9.9.1 Modelagem do Dictionary
-
Você vai precisar de 2 classes:
-
O Dicionário em si, implementado como um vetor de
ponteiros para Associações
-
A Associação, que associa uma chave a um objeto.
-
A Associação conterá um campo para a
chave (ponteiro para char), um campo para o objeto associado (ponteiro
void, para objetos genéricos), um campo tipo (definido por nós
como inteiro) e um ponteiro para a próxima associação.
-
O campo tipo é necessário para que saibamos
qual é o tipo de objeto que é apontado pela associação,
já que C++ não associa informaçoes sobre pertinência
de classe a objetos.
Classe
Dicionário {
Associação
dados[17];
}
Classe Associação
{
caracter
*chave;
inteiro
tipo;
void
*valor;
Associação
*prox;
}
9.9.2 Implementação da Classe Dictionary
-
O Dicionário deverá ser capaz de:
-
Adicionar um novo objeto, lendo a chave, o tipo e o objeto
e adicionando-o.
-
Recuperar e imprimir um objeto a partir da chave. Lembre-se
que em C++ para isto é necessário que, ao imprimir, primeiro
seja verificado qual o tipo para que seja chamada a impressão correta.
-
Imprimir todas as chaves. Esta impressão deverá
ser da forma mais simples possível, sem se preocupar com a ordem.
-
Lembre-se de fazer um typecasting ao imprimir,
depois que descobrir qual é o tipo do objeto apontado pelo ponteiro
valor.
