PSET5: Hash function and code not handling possessives and substrings

Question

I am having a lot of problems with pset5. I have identified more than one issue with the code but I don’t know how to fix the issues. The first is from my hash function, which is featured below and I have put it as its own program for debugging purposes. Basically I have set it up to take a string and calculate a number for 1-26 for each char and if it’s not a word but a punctuation mark it will give a 27. I have also added a lot of printf statements to determine how the program is working and what is going on. So it prints the word after I have inputed it, then it prints the number that each letter(IF) or punctuation mark(ELSE) would be given and finally the actual hash value. The code is below and sample output:

int main(int argc, char* argv[])
{

if(argc != 2)
{
    printf("fail!\n");
    return 1;
}


char* word = argv[1];
{
    printf("word:%s\n", word);
}
unsigned int hash = 0;
int n;
for (int i = 0; word[i] != '\0'; i++)
{
    // alphabet case
    if(isalpha(word[i]))
    {
        n = word[i] - 'a' + 1;
        printf("IF:%i\n", n);
    }

    else
    {
       n = 27;
       printf("Else:%i\n", n);
    }

    hash = ((hash << 3) + n) % 143091;
}
printf("%i\n", hash);
}

If I input the word zoo the output is:

  word:zoo
  IF:26
  IF:15
  IF:15
  1799

if I input zoo? The output is:

  word:zoo?
  IF:26
  IF:15
  IF:15
  Else:27
  14419

If I input zoo’ The output is;

 > ^ C… the ^ C being indicative of me having to exit the program.

My question is why can my program handle any punctuation mark except an apostrophe. Also any suggestions on how to fix this would be appreciated.

My second issue is an issues with SEG FAULTS and valgrind. So if I run my program I get a SEG FAULT. If I run cs50 check (which I know isn’t the right way to check things but I was curious about the output as I thought, it could help me figure out my issues). It says it doesn’t handle substrings or possessives correctly the latter probably being due to my hash function. When I run valgrind: The output tells me that line 89 is the problem (I have indicated where this is in my program) as I am trying to access 8 bytes of memory that isn’t mine to access.

My second question is what is wrong with what I am trying to do on line 89? I have genuinely tried to fix my program but I have hit a wall and any help at this point would be appreciated. The code for check and load is below.

typedef struct node
{ 
 char word[LENGTH +1];
 struct node *next;
}
 node;
 // Global variables to be used throughout program
 int wordcount = 0;
 int bucket;
 node* hashtable[143091];
 int hash(const char *word);



bool check(const char *word)
{

        bucket=hash(word);

        node*cursor=hashtable[bucket];

        while(cursor!= NULL)
        {
            if (strcasecmp( word, cursor -> word)==0)
            {
             return 0;    
            }

            else
            {
             cursor=cursor->next;
            }
        }

return true;       
}


/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
FILE *fp=fopen(dictionary, "r");
if (fp == NULL)
{
   fprintf(stderr, "There was no file loaded!\n");
   return 2;
}



 //initialize bucket table, where buckets point to NULL 
 for(int bucket =0; bucket < 143091 ; bucket++)
 {
  hashtable[bucket] = NULL;
 }

 //Make a new variable to make things less confusing
 char dictionary_word[LENGTH +1 ];

 //Go through dictionary one word at a time until I hit the end of sile
 while(fscanf(fp, "%s", dictionary_word) !=EOF)
 {
  node*new_node=malloc(sizeof(new_node)); 
  strcpy(new_node->word, dictionary_word);
  int bucket=hash(new_node -> word);

 //empty hashtable
 if(hashtable[bucket] == NULL)
 {
     hashtable[bucket] = new_node;
     new_node->next= NULL;//This is where the program fails on valgrind
     wordcount++;
 }
 //if there is a collision, add a new new_node
 else
 {
     new_node ->next=hashtable[bucket];
     wordcount++;
 }

 }


fclose(fp);
return true;

}

Answer 1

HASH FUNCTION

The hash function "handles any punctuation mark" because every non-alpha takes this else branch

else
    {
       n = 27;
       printf("Else:%i\n", n);
    }

This should not have to be "fixed" in the context of the assignment, because we are promised in the spec:

You may assume that any dictionary passed to your program will be structured exactly like ours, lexicographically sorted from top to bottom with one word per line, each of which ends with \n. You may also assume that dictionary will contain at least one word, that no word will be longer than LENGTH (a constant defined in dictionary.h) characters, that no word will appear more than once, and that each word will contain only lowercase alphabetical characters and possibly apostrophes.

It is not going to cause the check50 possessives failure.

---

LOAD FUNCTION

The valgrind complaint (and probably the seg fault) comes because of this (typo?) node*new_node=malloc(sizeof(new_node));.
new_node is a pointer, sizeof(a pointer) is 8. You probably meant sizeof(node).

That should get you past the seg-fault. There is at least one other problem looming here:

else
 {
     new_node ->next=hashtable[bucket];
     wordcount++;
 }

Assuming hashtable is the "head" of the linked list, nothing should ever point to it. You might want hashtable[bucket] to point to this new word, and this new word point to the "old word" (the one that hashtable[bucket] currently points to). It's a "swap".

This should get you on the road to progress, though there's bound to be other problems along the way. Remember, debug50 is your friend. (It's easier to start out with small dictionary/text files of your own making. )