Olá, estou realizando um trabalho de faculdade sobre tabela Hash e estou tendo algumas dificuldades. Vou tentar não complicar muito (pra falar a verdade, a execução do meu código ajuda bem a entender o que desejo fazer).
Basicamente, tenho, por enquanto, um programa que gera strQty palavras aleatórias de tamanho aleatório 1 a 10 caracteres. Após gerar essa palavra aleatório, eu insiro no final da lista dinâmica l. Até ai não tem segredo, mas ai vem minhas dificuldades, e é onde peço a ajuda de vocês.
A função obterValoresLista recebe a lista dinamica l, e itera palavra por palavra. Para cada palavra, é iterado letra por letra. Eu faço isso para obter um valor que chamei de val, que é a soma dos valores inteiro de cada caractere de uma palavra.
Com esse valor, eu chamo a função obterValorHash (lembrando que o trabalho é sobre tabela hash). Essa função vai me retornar, de acordo com o valor de val, um valor entre 0 e 31, que é o tamanho da minha tabela hash (M_SIZE).
E agora vamos começar a brincadeira. Eu tenho uma palavra word e um valor hash. Vamos supor agora que eu tenha um vetor hashTable de tamanho M_SIZE, eu preciso verificar se a hash de hashTable (hashTable[hash]) é nulo. Se for, eu vou criar uma nova lista dinâmica de palavras.
Então, essa é uma das minhas maiores dúvidas, como eu crio listas dinâmicas dinamicamente.
Continuando, supondo que eu criei uma nova lista dinâmica. Seu primeiro elemento será a palavra word. E além disso, eu preciso salvar o endereço de memória da cabeça dessa nova lista no vetor hashTable na posição hash.
Outra dúvida importante: que tipo de vetor é esse? É um vetor de endereços? de ponteiros? E como eu crio isso?
Continuando a execução do programa, é bem simples o algoritmo. Eu vou gerar um hash para uma nova word, e checar se hashTable[hash] é nulo. Se for, eu começo uma nova lista dinâmica, se não for, é porque o seu valor é o endereço pra cabeça de uma lista dinâmica já criada, e word será adicionada no fim dela.
Minha dúvida nessa parte seria como eu faço para, a partir desse valor, que é um ponteiro ou endereço (não sei muito bem a diferença entre esses dois termos), acessar a lista dinâmica.
Eu tenho a ideia bem clara de como é o funcionamento das tabelas hash e de como meu programa deve funcionar, no entanto minhas dúvidas são meramente técnicas a respeito da codificação de tudo isso.
No mais, eu agradeço pela paciência de estar aqui me ajudando. A seguir, segue o meu código até agora.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <locale.h>
#define STRLIMIT 10
#define M_SIZE 31
#define STR_QTY 100
typedef struct lista {
char word[STRLIMIT];
struct lista* prox;
} Lista;
Lista *insereFim(Lista* l, char word[], int size) {
Lista* novo = (Lista*) malloc(sizeof(Lista));
int i;
for (i=0; i<size; i++) {
novo->word[i] = word[i];
}
novo->word[size] = '\0';
novo->prox = NULL;
if (l == NULL) {
return novo;
}
Lista* aux = l;
while (aux->prox != NULL) {
aux = aux->prox;
}
aux->prox = novo;
return l;
}
int obterValorHash(int n) {
int hash;
hash = (5 * n) % M_SIZE;
return hash;
}
void obterValoresLista(Lista* l) {
int i, val, hash;
int *table[M_SIZE];
for (i=0; i<M_SIZE; i++) {
table[i] = NULL;
}
do {
val = 0;
for (i=0; i<strlen(l->word); i++) {
val += (int)l->word[i];
}
hash = obterValorHash(val);
printf("%10s\t%d\t%d\t%p\n", l->word, val, hash, &l->word);
l = l->prox;
} while (l != NULL);
}
int main() {
srand(time(NULL));
setlocale(LC_ALL, "");
int strQty = 100;
int strLimit = 11;
int ascMin = 97;
int ascMax = 122;
// Gerando strings aleatorias
int i, j;
int size, letter;
Lista* l = NULL; //Lista encadeada
for (i=0; i<strQty; i++) {
// Tamanho da palavra words[i] -- de 1 a 10.
size = rand()%(10)+1;
char word[strLimit];
for (j=0; j<size; j++) {
letter = rand()%(ascMax-ascMin)+ascMin;
word[j] = (char)letter;
}
// Indica o fim da string
word[size] = '\0';
l = insereFim(l, word, size);
}
int *hashArray[strQty];
obterValoresLista(l);
}