1

This is my load function from dictionary.c.

I'm trying to create a hashtable of linked lists with separate chaining. There are 26 elements corresponding to each letter in the alphabet. My questions is if there's any way to initialize each element of the array to NULL? So that for example, when head pointer points to hashtable[0] it is NULL originally.

#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include "dictionary.h"

#define SIZE 25

typedef  struct node
{
    char word[LENGTH+1];
    struct node *next;
}node;

int hash_num = 0;
node *hashtable[SIZE];  //0-25  

node *head = NULL;


int hash_function(char *key)  //input is a string, outputs a number from 0-25
{
    int hash= toupper(key[0]) - 'A';
    return hash % SIZE;
}


 /**
* Returns true if word is in dictionary else false.
*/

bool load(const char* dictionary)
{

    int hash_index=0;

    FILE *fp = fopen(dictionary, "r");
    if(fp == NULL)
    {
        fprintf(stderr, "Couldn't open %s",dictionary);

        return false;
    }

    //dictionary 
    node *temp = malloc(sizeof(node));  //mallocing our new_node that will contain the word


    if( fscanf(fp , "%s", temp->word) == 1)   
    {
        hash_index = hash(temp->word); 

        head = hashtable[hash_index];    //head always points to first node of the linked list for each element 

        // adding word into linked list
        if(head == NULL || (strcmp(temp->word,head->word) < 0) )
        {
            temp->next = head;
            head = temp;
        }
        else
        {
            node *cur, *prev;
            for (cur = head, prev = NULL;
                 cur != NULL && (strcmp(cur->word, temp->word) < 0);  //temp->data contains our word
                 prev = cur, cur = cur->next);

            temp->next = cur;
            prev->next = temp;
        }

        hash_num++;

    }

    fclose(fp);
    return true;

}

I appreciate any tips or suggestions, maybe I'm overcomplicating things.

3

You can set each element individually to NULL using a for loop.

I see a small problem with it though. SIZE = 25, so that's elements 0 to 24. Interestingly, because of the way that the hash function is written, it will still work, but all words beginning with a or z will be hashed to 0 and placed in the same linked list. ;-)

It also looks like you're trying to create a sorted linked list. I just don't understand what value that has. Barring the creation of some complex code, the lists will only be searchable by a linear search. Since the time to find a given word, on average, likely won't matter whether the list is sorted or not, the time spent to sort it can be looked at as not gaining any advantage. In fact, the sort time is worst case because the dictionary file is already sorted, so each new word will always be sorted to the end of each linked list. The best case scenario would be to simply add each new word to the beginning of each list, completely eliminating the sort during load. Think about it. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

| improve this answer | |
  • I was thinking of implementing a binary search to search through the linked list. I thought they were asking for that in the walkthrough videos. I misunterstood it apparently. I'll go back and edit it then. Thanks. Aside from those things that you pointed, everything else looks fine right? – tadm123 Dec 26 '16 at 2:18
  • BTW, where should I put the for loop to set everything to NULL knowing that I can't modify the main function? – tadm123 Dec 26 '16 at 2:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .