Dúvidas

["Alexandre Murakami" <ale_murakami@bol.com.br>]

Professor

Estou com algumas dúvidas dos exercícios da lista.

-----------------

No exercício 15.76, pede-se para montar um índice para um texto usando
"26-way DST". O exercício 15.77 pede a mesma coisa usando "26-way trie".
Qual a diferença entre as estruturas?

------------

O exercício 14.4 (hashing) pede para fazer um programa que calcula os
valores de a e de M, com o valor de M menor possível, de modo que não haja
colisões para uma certa lista de chaves. Como se faz isso? Se caísse essa
questão na prova eu faria desse jeito, mas não sei se esse jeito faz muito
sentido:

v[] = vetor de chaves
n = número de chaves

void perfectHash (int v[], int n, float *a, int *M) {
  int i;
  for (*M = n + 1; ; (*M)++)
    for (i = 0; i < 100; i++) {
      *a = rand() / RAND_MAX;
      if (!colisao (v, n, *a, *M))
        return;
    }
}

Eu começo com M = n + 1 (para deixar um espaço vazio) e vou testando valores
aleatórios de a. A função colisao() retorna true se houver colisão entre as
chaves. Se não achar um valor adequado de a após 100 tentativas, aumento o
valor de M.

------------

Obrigado
Alexandre Murakami