1

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);
}

1 Resposta 1

1

Seu código está pronto já, acho que só faltam duas linhas pra resolver o que você pede.

1) Este tipo de dado que você está com duvida é um dado do tipo Lista. Troque o int* por::

Lista* table[M_SIZE];

Assim cada elemento de table será a primeira posição de uma lista (exceto quando o valor é NULL, é claro).

2) Todas as posições da sua table já estão iniciadas com NULL, então basta inserir os elementos com a função insereFim. Na linha abaixo de onde está seu printf, chame a função de inserir da seguinte forma:

table[hash] = insereFim(table[hash], l->word, strlen(l->word));

Qunanto a parte "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 ", a função insereFim já realiza essas duas coisas, então acredito que são apenas estas duas coias que deveriam ser feitas.

1
  • 1
    Cara, muito obrigado mesmo! Você me ajuda na outra pergunta, e me ajudou muito agora também! Seu conhecimento é incrível! Commented 28/04/2017 às 16:49

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .