Tabela de símbolos

Muitos programas precisam guardar informações para encontrá-las depois a partir de um identificador:

• o sistema acadêmico encontra o registro de um aluno (nome, curso, notas) a partir da matrícula;
• o DNS encontra o endereço IP de um site a partir do nome do site;
• um dicionário encontra a definição a partir da palavra;
• um compilador encontra o tipo e o endereço de uma variável a partir do identificador que aparece no código. É daqui que vem o nome "tabela de símbolos".

Em todos esses casos há pares (chave, valor): a chave identifica, e o valor é a informação associada a ela. A chave tem que ser única: não pode haver dois alunos com a mesma matrícula. A chave funciona como um "endereço" do valor, e a única forma de chegar ao valor é por meio dela.

Outros nomes comuns para a mesma ideia são dicionário, mapa e array associativo. Em Python é o dict; em C++, o std::map; em Java, o Map. Em C, não há uma pronta: vamos construí-la.

Interface do TAD

/* TS.h */
#ifndef TS_H
#define TS_H

#include <stdbool.h>

typedef int Chave;
typedef int Valor;
typedef struct ts TS;

TS *criaTS(void);
void liberaTS(TS *ts);

/* Se a chave já existe, troca o valor; senão, insere o par */
void insereTS(TS *ts, Chave chave, Valor valor);

/* Ponteiro para o valor associado à chave, ou NULL se ela não existe.
   O ponteiro vale até a próxima inserção ou remoção. */
Valor *buscaTS(const TS *ts, Chave chave);

/* Remove o par com essa chave (se não existe, nada acontece) */
void removeTS(TS *ts, Chave chave);

int tamanhoTS(const TS *ts);
bool vaziaTS(const TS *ts);
void imprimeTS(const TS *ts);

#endif

Algumas decisões dessa interface:

• Chave e Valor são typedefs. Aqui os dois são int, mas o resto do código só usa os nomes Chave e Valor. Para guardar, por exemplo, notas (double) indexadas por matrícula, bastaria trocar o typedef do valor. Trocar a chave por uma string exige mais cuidado, como mostra o primeiro exercício desta página.
• insereTS também atualiza. Como as chaves são únicas, inserir uma chave que já existe não cria um segundo par: substitui o valor antigo.
• buscaTS devolve um ponteiro. Com NULL para "não encontrada", não é preciso reservar um valor especial (como o -1 da pilha), que poderia ser um valor legítimo.

Valor *v = buscaTS(ts, x);
if (v != NULL)
    (*v)++;                 /* já existe: incrementa no lugar */
else
    insereTS(ts, x, 1);     /* primeira ocorrência */

A sequência abaixo mostra o efeito das operações em uma tabela inicialmente vazia. Os pares estão listados sem nenhuma ordem particular.

Implementação com lista encadeada

Uma forma simples é usar uma lista simplesmente encadeada em que cada nó guarda um par.

typedef struct no {
    Chave chave;
    Valor valor;
    struct no *proximo;
} No;

struct ts {
    No *inicio;
    int tamanho;
};

Todas as operações começam pela mesma busca sequencial: percorrer a lista até achar a chave ou chegar ao fim.

/* Busca sequencial: devolve o nó com a chave, ou NULL */
static No *procura(const TS *ts, Chave chave) {
    for (No *p = ts->inicio; p != NULL; p = p->proximo)
        if (p->chave == chave)
            return p;
    return NULL;
}

void insereTS(TS *ts, Chave chave, Valor valor) {
    No *p = procura(ts, chave);
    if (p != NULL) {                /* chave já existe: atualiza */
        p->valor = valor;
        return;
    }
    No *novo = malloc(sizeof(No));  /* chave nova: entra no início */
    novo->chave = chave;
    novo->valor = valor;
    novo->proximo = ts->inicio;
    ts->inicio = novo;
    ts->tamanho++;
}

Valor *buscaTS(const TS *ts, Chave chave) {
    No *p = procura(ts, chave);
    return p == NULL ? NULL : &p->valor;
}

Repare que até a inserção precisa da busca: antes de criar um nó, é preciso saber se a chave já existe. A remoção é a mesma da lista encadeada, guardando o nó anterior durante a busca.

  void removeTS(TS *ts, Chave chave) {
      int i = procura(ts, chave);                 /* posição da chave, ou -1 */
      if (i == -1)
          return;
      ts->pares[i] = ts->pares[ts->tamanho - 1];  /* o último ocupa o buraco */
      ts->tamanho--;
  }

Implementação com vetor ordenado

A lista é lenta porque a busca é sequencial. Com os pares em um vetor ordenado pela chave, a busca pode ser binária: compara-se a chave procurada com a do meio do vetor e descarta-se a metade em que ela não pode estar. A cada passo o intervalo cai pela metade, e a busca custa .

typedef struct {
    Chave chave;
    Valor valor;
} Par;

struct ts {
    Par *pares;         /* ordenados pela chave */
    int tamanho;
    int capacidade;
};

A busca binária abaixo devolve a posição da chave: se ela existe, é onde ela está; se não existe, é onde ela deveria entrar para manter o vetor ordenado (o número de chaves menores que ela).

static int posicao(const TS *ts, Chave chave) {
    int ini = 0, fim = ts->tamanho - 1;
    while (ini <= fim) {
        int meio = ini + (fim - ini) / 2;
        if (ts->pares[meio].chave < chave)
            ini = meio + 1;
        else if (ts->pares[meio].chave > chave)
            fim = meio - 1;
        else
            return meio;
    }
    return ini;
}

Com ela, a busca é imediata. A inserção de uma chave nova, porém, precisa abrir espaço na posição certa: todos os pares depois dela andam uma casa para a direita.

void insereTS(TS *ts, Chave chave, Valor valor) {
    int i = posicao(ts, chave);
    if (i < ts->tamanho && ts->pares[i].chave == chave) {
        ts->pares[i].valor = valor;         /* chave já existe: atualiza */
        return;
    }
    if (ts->tamanho == ts->capacidade) {    /* vetor cheio: dobra */
        ts->capacidade *= 2;
        ts->pares = realloc(ts->pares, ts->capacidade * sizeof(Par));
    }
    for (int j = ts->tamanho; j > i; j--)   /* abre espaço na posição i */
        ts->pares[j] = ts->pares[j - 1];
    ts->pares[i].chave = chave;
    ts->pares[i].valor = valor;
    ts->tamanho++;
}

Quando o vetor enche, a capacidade dobra (com realloc), e por isso a tabela não tem limite de tamanho, como a versão com lista. Dobrar custa copiar o vetor, mas isso acontece tão raramente que, distribuído entre todas as inserções, sai por cada uma. A remoção é o caminho inverso da inserção: os pares depois da posição removida andam uma casa para a esquerda.

O main.c e o TS.h abaixo são os mesmos da versão com lista. A única diferença na saída é a ordem em que imprimeTS mostra os pares: agora, sempre por chave.

Quanto a busca binária ganha da sequencial? O programa abaixo conta quantas chaves cada uma examina, em média, em vetores de tamanhos crescentes (metade das chaves buscadas não existe).

Cada vez que é multiplicado por 10, a busca sequencial examina 10 vezes mais chaves, e a binária, só cerca de 3,3 a mais (). Com um milhão de chaves, são cerca de 20 comparações contra centenas de milhares.

Comparando as implementações

Os custos são de pior caso, para uma tabela com pares. Nenhuma delas é boa em tudo:

• o vetor não ordenado e a lista inserem e removem sem deslocar nada, mas não têm como evitar a busca sequencial: para achar uma chave, só percorrendo. Os custos das duas são idênticos, porque o que importa aqui não é vetor ou lista, e sim a falta de ordem;
• o vetor ordenado busca rápido, mas paga caro para manter a ordem a cada inserção ou remoção.

O ideal seria juntar o melhor dos dois: a busca binária do vetor e a inserção sem deslocamentos da estrutura encadeada. É exatamente isso que fazem as árvores binárias de busca, assunto das próximas páginas. Elas implementam esta mesma interface, e cada uma vai acrescentar uma linha a esta tabela.

Exercícios

Encontre e corrija o erro

Programa 1

for (No *p = ts->inicio; p != NULL; p = p->proximo)
    if (p->chave == chave) {
        p->valor = valor;
        return;
    }

Programa 2

for (int j = ts->tamanho; j > i; j--)
    ts->pares[j] = ts->pares[j - 1];

Programa 3

Programa 4

for (int k = 2; k <= 8; k++) {
    insereTS(ts, k, 0);
    (*buscaTS(ts, 1))++;
}

Implemente

Frequência de palavras. Adapte a TS com lista encadeada para chaves do tipo string: em TS.h, a chave já é const char *, e o TS.c inicial é o desta página, sem mais nenhuma alteração. Ele compila, mas não funciona. Os testes contam as palavras de um texto, e todas as palavras são lidas no mesmo vetor de caracteres.

Lista auto-organizável. Em muitas aplicações, poucas chaves concentram a maior parte das buscas. Implemente a busca da TS com lista de modo que, ao encontrar uma chave, o nó dela seja movido para o início da lista (move-to-front). Assim, as chaves mais buscadas tendem a ficar perto do início. Como a busca agora altera a lista, ela deixa de receber um ponteiro const. Os testes fazem um milhão de buscas concentradas em oito chaves que foram inseridas primeiro (e por isso estão no fim da lista).

Operações ordenadas. O vetor ordenado responde rápido a perguntas que dependem da ordem das chaves, e que a lista só responderia percorrendo tudo. Implemente, em ou melhor:

• minTS e maxTS: a menor e a maior chave;
• rankTS: quantas chaves são menores que uma chave dada;
• pisoTS e tetoTS: a maior chave menor ou igual, e a menor chave maior ou igual, a uma chave dada (que não precisa estar na tabela).

Por exemplo, com as chaves 10, 20, 30 e 50, o rank de 25 é 2, o piso de 25 é 20, e o teto é 30.

Referências

• R. Sedgewick e K. Wayne. Algorithms. 4ª ed. Addison-Wesley, 2011. Capítulo 3 (Searching).
• W. Celes, R. Cerqueira e J. L. Rangel. Introdução a Estruturas de Dados: com técnicas de programação em C. 2ª ed. Grupo GEN, 2016.
• A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.