Este é um resumo de parte das seções 12.4, 12.5 e 12.8 do livro do Sedgewick bem como das seções 11.1 e 11.2 do livro de Roberts. Essas partes dos dois livros tratam do tipo abstrato de dados conhecido como tabela de símbolos (= symbol table = ST) ou dicionário (= dictionary).
Uma tabela de símbolos é um conjunto de objetos, cada um dotado de uma chave (= key). As chaves podem ser números inteiros, ou cadeias de caracteres, ou qualquer outro tipo-de-dados básico que permita comparação: dadas duas chaves ch1 e ch2, deve ser possível dizer se ch1 < ch2 ou ch1 == ch2 ou ch1 > ch2. A tabela de símbolos está sujeita a duas operações:
(Às vezes é conveniente admitir também uma operação de remoção (= delete), que consiste em retirar da tabela um ou todos os objetos que tenham uma dada chave.)
A dificuldade está em organizar a tabela de símbolos de maneira que ambas as operações sejam razoavelmente eficientes. Uma organização que permite inserções rápidas impede buscas rápidas e vice-versa. Por isso, é preciso fazer compromissos.
Digamos que meus objetos são colaboradores de uma grande empresa. Para cada colaborador, quero saber em qual departamento da empresa ele trabalha. Esse tipo de objeto — que chamaremos Item — pode ser representado assim:
typedef struct {
int chave;
char departamento[50];
} Item;
A chave é o número de identificação do colaborador. Os números de identificação têm 7 dígitos decimais e variam de 0100001 e 9999999. Alguns colaboradores pode trabalhar em dois ou mais departamentos diferentes; portanto, a tabela de símbolos pode ter dois ou mais Items com a mesma chave.
Nesse exemplo, as funções de inserção e busca nesse caso poderiam ter os seguintes protótipos:
// A função insert insere um item na tabela // de símbolos. void insert(Item item) ; // A função search devolve um item tal que // item.chave == v. Se tal item não existe, // a função devolve um Item fictício com // chave nula. Item search(int v) ;
Como a tabela se símbolos desse exemplo poderia ser organizada? Como as funções insert e search poderiam ser implementadas?
A tabela pode ser implementada em um vetor. Suponhamos, por enquanto, que o vetor não é ordenado:
Item itemnulo; itemnulo.chave = 0; // Teremos no máximo 1000 Items, ocupando // o vetor tabela[0..N-1]. Item tabela[1000]; // Número de Items na tabela. (Essa variável // é global.) int N; // Inicialização da tabela. void inicializacao() { N = 0; } void insert(Item item) { tabela[N++] = item; } Item search(int v) { int i; for (i = 0; i < N; i++) if (tabela[i].chave == v) break; if (i < N) return tabela[i]; return itemnulo; }
Essa solução não é muito boa porque as buscas são muito demoradas: elas consomem tempo proprocional a N no pior caso.
Se mativéssemos o vetor tabela em ordem crescente de chaves, o tempo de busca seria reduzido para lg(N) mas o tempo de inserção subiria para N no pior caso.
Uma segunda maneira de implementar a tabela de símbolos do exemplo é uma lista encadeada. Suponhamos por enquanto que a lista não é ordenada:
// Definição de um nó da lista. typedef struct node *link; struct node { Item item; link next; } ; // Primeiro nó da lista. (Essa variável é // global.) link lista; // Item para sinalizar buscas malsucedidas. Item itemnulo; itemnulo.chave = 0; // Inicialização da tabela de símbolos. void inicializacao() { lista = NULL; } void insert(Item item) { link t = malloc(node); t->item = item; t->next = lista; lista = t; } Item search(int v) { link t; for (t = lista; t != NULL; t->next) if (t->item.chave == v) break; if (t != NULL) return t->item; return itemnulo; }
Essa solução não é muito boa pois as buscas são muito demoradas: no pior caso, uma busca consome tempo proprocional ao tamanho (ou seja, ao número de Items) da tabela de sómbolos. (Poderíamos manter as listas em ordem crescente de chaves, mas isso não melhoraria a eficiência da implementação.)
Uma terceira possibilidade de implementaqção usa endereçamento direto. A tabela de símbolos é mantida em um vetor que tem uma posição para cada um dos possíveis valores da chave: os índices da tabela vão de 0100001 a 9999999 (de cem mil mais um até dez milhões menos 1):
#define min 0100001
#define max 9999999
// tamanho da tabela: max - min + 1
#define M 9899999
Item tabela[M];
Item itemnulo;
itemnulo.chave = 0;
void inicializacao() {
int h;
for (h = 1; h < M; h++)
tabela[h] = itemnulo;
}
void insert(Item item) {
int v = item.chave;
int h = v - min;
tabela[h] = item;
}
Item search(int v) {
int h = v - min;
return tabela[h];
}
A característica mais marcante dessa implementação é o uso de chaves como índices. No exemplo acima, usei uma translação para transformar a chave v no índice h:
h = v - min;Se tivesse adotado 10000000 como valor de M, bastaria fazer h = v. Em qualquer dessas variantes, só importa que o valor de h fique no intervalo 0..M-1 e que valores diferentes de v levem a valores diferentes de h.
Com endereçamento direto, as operações de inserção e busca ficam muito rápidas: elas não mais dependem do número de Items na tabela! Apenas a operação de inicialização fica mais lenta que a das implementações anteriores. Os maiores defeitos dessa implementação são:
colisãona tabela (somente a inserção mais recente seria registrada);
As implementações de tabelas de símbolos sugeridas no exemplo acima são simples e pouco eficientes. Elas servem apenas para pequenas aplicações.
Se a tabela de símbolos é grande é preciso recorrer a implementações mais sofisticadas. Duas delas — árvores de busca e tabelas de dispersão — serão examinadas em outros capítulos.