Kinda confused with what needs memory allocated in pset5

Question

I wanted to give hashtables a go with pset5. I've set the struct up as:

typedef struct node {
    char *data;
    struct node *next;
} node;

Every time I link a new node all of the node->data values are replaced w/the current string. Do I need to malloc for data in addition to node*whatever? Or am I missing something. thanks!

Basically the pseudocode is this for the load part....

char word[26] is "whatever the word is"
if node is null
     malloc a node
     node->data equals word 
     node->next equals null
else if new node isnt null
     create temp node and malloc
     temp->next = new node
     temp->data = next word that is put into function
     node = temp

Answer 1

well, no where to start, first see the hash tablenode* hashtable[ALPHA], is an array of pointers to node, are pointers we will use to store our words according to their index hash, to equal hash index equal pointer, for these pointers do not need malloc, your loop to check does not work, possibly segmentation fault. hashtable[k] == NULL, it is unnecessary testing, ultimately I think you need to spend some time reviewing the theoretical part, it seems that your coding is a bit hasty and confused. I recommend going step by step, you need a clear understanding of the concepts before making a relatively long program, because it will be impossible to know what's wrong. First try to understand how a hash table works, then works with linked lists, it helps me do my small test programs, to see easily how it works, is very clarifying. Good luck with pset5, is not easy

EDIT: you're still keeping in your mind a trie, you should read more about hash table, course videos are good, I recommend review them. First, The best way, in my opinion is to define the structure as

typedef struct node
{
    char word[LENGTH + 1];         // len max, plus 1 for \0
    struct node* next;
}
node;

is better than data *, then malloc, because we know in advance the size and we will avoid the mess for free memory.

 node* hashtable[HASHSIZE]; 

is an array of pointers, do not need malloc not point to any valid place (for now), they do not contain any word or will contain. CHECK:

bool check(const char* word)

Here is where the first mistake you commit, you're thinking of a trie, in a hash table we store each particular word, you should not iterate over each individual character

node2* buffer = hashtable[k];

buffer is a pointer to a node data type, like char * buffer is a pointer to a data type character, buffer is only a pointer, contains no words, in C we need to declare each data type.finally I will give the pseudocode to check, I can not elaborate any further and you need to clarify concepts before you start writing code, it is generally not possible to review an entire program and tell you everything that is wrong, because it goes against honor code and at the end you do not learn anything:

// Convert each character to lowercase on a copy, because the function gives a constant string

// Calculate the hash value of the word (every word, not every character)

// We walk the linked list searching of a match

  -declare a pointer for this node type, and assign it to the pointer for
   the "cube" pointed to our index hash:

   node* crawler = hashtable[k];
     while crawler not null
      We compare our copy with the word
       if yes return true
       if not crawler = crawler-> next
       return false

LOAD: Finally, we do not need to do if (hashtable [z] == NULL) ... else ... Although your initializes hash table to null for all possible values, is a waste of time, once we calculate a hash index word, do the necessary operations on the linked list to know where we should point list:

 new_node-> next = hashtable[k];
 hashtable[k] = new_node;

it does not matter that hashtable[k] points to null or garbage values, we have already assigned other values which are not assigned we do not care.I hope that this will begin. Finally your hash table is too simple, because it does not go against honor code I leave a hash function that I wrote for this set of problems in 2014

// Funcion hash
    unsigned int hash_function(char* word)
    {
        int salto = 6;
        // initializes the index to zero, will be the sum of the characters
        unsigned int index = 0;
        // pointer to word
        char* p = word;

        // Add ascii values with Left rotation, independently of capitalita.
        while (*p++)
        { 
            // rotation function
            unsigned int rotl = (((*p) << salto) | ((*p) >> (sizeof(*p)*CHAR_BIT - salto)));
            index = index + rotl;      
        }

        // We get the final hash value by the method of multiplication
        double factor = 0.6180339887,parte_decimal,parte_entera;
        factor = factor*index;
        //Get the decimal part of factor
        parte_decimal = modf (factor, &parte_entera); // 
        unsigned int k = (unsigned int)abs((HASHSIZE*(factor*parte_decimal)));

        // return hash index
        return k%HASHSIZE;
    }
    // End hash function