0

My code works fine when implementing a linear search on the hashtable linked list, but the time taken is pretty longer than the staff's implementation. So I decided to apply binary search algorithm on the linked list, but had a problem in traversing backwards in the linked list. Searched the web and found the following algorithm in a StackOverflow Answer :

The issue with the singly-linked list case is that if you have a pointer to the middle of the list, you can't go backwards to get back to the first quarter of the list. However, if you think about it, you don't need to start from the middle to do this. Instead, you can start at the front of the list and walk to the first quarter. This takes (essentially) the same amount of time as before: rather than going backward n / 4 steps, you can start at the front and go forwards n / 4 steps.

More generally, instead of storing a pointer to the middle of the list, store two pointers into the list: one at the front of the range where the value might be and one in the middle of the range where the value might be. If you need to advance forward in the list, update the pointer to the start of the range to be the pointer to the middle of the range, then walk the pointer to the middle of the range forward halfway to the end of the range. If you need to advance backward in the list, update the pointer to the middle of the range to be the pointer to the front of the range, then walk forwards halfway.

And hence I tried to implement the above algorithm without using doubly-linked list. But I am getting a Segmentation Fault after a few words.

I am initializing two node pointers head and ptr as the starting node of the respective linked list in which there is a possibility of finding my word. And now as per the algorithm I mentioned above, if I want to advance forward in that linked list I initialize head as ptr and then traverse further with ptr. And if I want to traverse backwards, I initialize ptr as head and then traverse forward with ptr.

last is being initialized as total number of words in that respective linked list by making use of an array hashword[] which kept track of how many words are getting stored in each linked list in load function.

Here is my code of dictionary.c :

/**
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 */

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "dictionary.h"

/**
 * Returns true if word is in dictionary else false.
 */
 
  typedef struct node
    {
        char word[LENGTH+1];
        struct node* next;
    }node;
    
    node* hashtable[705];
    node* new_node;
    int words=0;
    int hashword[703];

int hash(const char* str)
{
    int hashnum;
    char str1=*(str+1);
    if(str1=='\n'||str1=='\0')
    {
        hashnum=(((int)str[0]-97)*27)+1;
    }
    else
    {
        hashnum=(((int)str[0]-97)*27)+1+((int)str[1]-96);
    }
    return hashnum;
}
    
    
bool check(const char* word)
{
    // TODO
    node* ptr;
    node* head;
    int beg,last,mid,dif;
    int k=0,i;
    char str[LENGTH+1];
    while(*word!='\n'&&*word!='\0')
    {
        str[k++]=tolower(*word);
        word++;
    }
    str[k]='\0';
    beg=1;
    last=hashword[hash(str)];
    if(!(hashword[hash(str)]>0))
    return false;
   /* for(ptr=hashtable[hash(str)];ptr!=NULL;ptr=ptr->next)
    {
        if(strcmp(str,ptr->word)==0)
        return true;
    }*/
    head=hashtable[hash(str)];
    ptr=hashtable[hash(str)];
    mid=(beg+last)/2;
    /*printf("%d\n",hashword[hash(str)]);
    printf("%s\n",hashtable[hash(str)]->word);
    printf("%s\n\n",str);*/
    
    while(ptr!=NULL&&beg<=last)
    {
        if((int)((beg+last)/2)<mid)
        {
           dif=mid-((beg+last)/2);
           mid=(beg+last)/2;
           ptr=head;
        }
        else if((int)((beg+last)/2)>mid)
        {
            dif=((beg+last)/2)-mid;
            mid=(beg+last)/2;
            head=ptr;
        }
        else
        dif=mid;
        for(i=1;i<=dif&&ptr!=NULL;i++)
        ptr=ptr->next;
        if(strcmp(str,ptr->word)==0)
        return true;
        else if(strcmp(str,ptr->word)<0)
        beg=mid+1;
        else
        last=mid-1;
    }
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // TODO
    int i;
    char myword[LENGTH+1];
    for(i=0;i<703;i++)
    hashword[i]=0;
    for(i=0;i<705;i++)
    hashtable[i]=malloc(sizeof(node));
    for(i=0;i<705;i++)
    hashtable[i]=NULL;
    int bucket;
    FILE *file;
    file=fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }
    fseek( file, 0, SEEK_SET );
    while(fscanf(file,"%s",myword) == 1)
    {
        if(feof(file))
        break;
        new_node=malloc(sizeof(node));
        strcpy(new_node->word, myword);
        bucket=hash(new_node->word);
        if(hashtable[bucket]==NULL)
        new_node->next = NULL; 
        else
        new_node->next=hashtable[bucket];
        hashtable[bucket]=new_node;
        words++;
        hashword[bucket]++;
    }
    fclose(file);
    free(new_node);
    return true;
}


/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    // TODO
    return words;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    // TODO
    int i;
    new_node=NULL;
    free(new_node);
    for(i=0;i<705;i++)
    hashtable[i]=NULL;
    for(i=0;i<705;i++)
    free(hashtable[i]);
    return true;
}

I know that there is some fault in the unloading part of the program as my valgrind reports two errors. But I wanted to discuss regarding that in another question later.

Please note that my code works fine with a linear search.

Please help.

1

I must admit that I'm thoroughly confused about what check() is trying to do. In load, a hash number is determined for each word based on the first two letters. Based on that hash number, it is added to one of 705 linked lists. The first element or node in each linked list is pointed to by the corresponding array element in hashtable[]. Further, because each node is added to the beginning of each linked list, and the dictionary is an alpha sorted list, each linked list is in descending order. (That's best case. It's also likely that they're an unsorted list.) But, it appears that check() assumes ascending order. But this is actually a red herring. I just wanted to point it out.

The real issue, unless I completely misinterpreted the code (which may be true), is that the binary search appears to be searching between 1 and the hash number of the word, and then trying to do a binary search across the array elements of hashtable[], not across the linked list that starts at hashtable[hash(word)]. Also unless you had saved pointer data of mid and end nodes in each list, you would still have to traverse the appropriate list starting at the node pointed to by the corresponding hashtable[] element to find the middle and end elements.

Consider that arrays are great for binary searches, but linked lists work much better in linear searches. Also, by making the hashtable array larger (making the base of the tree wider), you would increase performance by shortening the average length of the linked lists.

As for the memory leak, there is a conspicuous one. Look at the following:

for(i=0;i<705;i++)
hashtable[i]=malloc(sizeof(node));
for(i=0;i<705;i++)
hashtable[i]=NULL;

These two loops first malloc memory for 705 nodes and then immediately discards the addresses without first freeing the memory. You do not have to malloc memory to create a pointer or a pointer array. The first loop can be completely discarded. The second for loop is sufficient to initialize the pointers. Don't know if there are other issues on this front.

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

2
  • I am initializing two node pointers head and ptr as the starting node of the respective linked list in which there is a possibility of finding my word. And now as per the algorithm I mentioned above, if I want to advance forward in that linked list I initialize head as ptr and then traverse further with ptr. And if I want to traverse backwards, I initialize ptr as head and then traverse forward with ptr. Yeah, my linked lists are reverse sorted and in my binary search I did use the logic for descending order(pls have a look at my strcmp statement). Hope you understood my logic. – Ayodhya Mukund Jul 5 '16 at 5:59
  • last is being initialized as total number of words in that respective linked list by making use of an array hashword[] which kept track of how many words are getting stored in each linked list in load function. I think this is the point where you misinterpreted/misunderstood the things. And another important thing is if I needn't malloc anything to initialize, then what should I do in the unload function ? – Ayodhya Mukund Jul 5 '16 at 6:07

You must log in to answer this question.

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