Dynamically creating lists and saving their addresses (top of list)

Question

Hi, I’m doing a college paper on Hash table and I’m having some difficulties. I will try not to complicate too much (to tell you the truth, the execution of my code helps me to understand what I wish to do).

Basically, I have, for now, a program that generates strQty random words of random size 1 to 10 characters. After generating this random word, I enter at the end of the dynamic list l. So far there is no secret, but here comes my difficulties, and this is where I ask for your help.

The function get ValoresList receives the dynamic list l, and iterates word by word. For each word, it’s iterated letter by letter. I do this to get a value I called val, which is the sum of the integer values of each character of a word.

With this value, I call the function get (remembering that the work is about table hash). This function will return me, according to the value of val, a value between 0 and 31, which is the size of my hash table (M_SIZE).

And now let’s start the joke. I have a word word and a value hash. Let’s assume now that I have a vector hashTable size M_SIZE, i need to check the hash of hashTable (hashTable[hash]) is null. If it is, I will create a new dynamic list of words.

So this is one of my biggest questions, how I create dynamic lists dynamically.

Continuing, assuming I have created a new dynamic list. Your first element will be the word word. And besides, I need to save the memory address of head of that new list in the hashTable vector at the hash position.

Another important question: what kind of vector is this? Is it an array of addresses? pointers? And how do I create this?

Continuing the execution of the program, it is quite simple the algorithm. I will generate a hash to a new word, and check whether hashTable[hash] is null. If it is, I start a new dynamic list, if it is not, it is because its value is the address to the head of an already created dynamic list, and word will be added at the end of it.

My doubt on that part would be how do I do, from that value, which is a pointer or address (I don’t really know the difference between those two terms), access the dynamic list.

I have a very clear idea of how the hash tables work and how my program should work, however my doubts are merely technical regarding the coding of all this.

Plus, I appreciate the patience of being here to help me. Next, follow my code so far.

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

Answer 1

Your code is ready now, I think there are only two lines left to solve what you ask.

1) This type of data you are doubting is a List type data. Exchange int* for::

Lista* table[M_SIZE];

So each table element will be the first position of a list (except when the value is NULL, of course).

2) All positions in your table are already started with NULL, so just insert the elements with the function insereFim. On the line below where your printf, call insert function as follows:

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

When "If it is, I start a new dynamic list, if it is not, it is because its value is the address to the head of an already created dynamic list, and word will be added at the end of it ", the function insereFim already accomplishes these two things, so I believe that it is only these two things that should be done.