The strcasecmp in my check()-function (top of the code) does not work as it should. When I run the code, it does NOT act caseinsensitively. I think it's something about the types that I compare but I couldn't figure it out yet... PS: It's from CS50 but I already submitted the problem, so no cheating here ;)
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// Number of buckets in hash table
const unsigned int N = 1000; //CHANGE THIS ACCORDING TO HASH ALGORITHM
// Hash table
node *table[N];
// used for size() to keep track of dictionary size
int dict_size = 0;
// Returns true if word is in dictionary (case-insensitive), else false
bool check(const char *word)
{
//1: hash word to obtain hash value
//2: access linked list at that index in hash table
//cursor = first item of linked list
node *cursor = table[hash(word)];
//then move the cursor until it's NULL
//use cursor (cursor = cursor->next) to traverse through linked list
//true if word found
while(cursor != NULL)
{
//has to be ZERO! strcasecmp returns numbers if the words differ, not true or false
if (strcasecmp(cursor->word, word) == 0)
{
return true;
}
cursor = cursor->next;
}
//false if reached NULL and word has not been found
return false;
}
//Hashes word to a number
//takes word as input
//outputs a number corresponding to which "bucket" (index in an array) to store the word
//could do first letter, first two letters, MATH??? ---> SEARCH ONLINE AND GIVE THE SOURCE
unsigned int hash(const char *word)
{
//make it deterministic
//use SDBM Hash Function from source
unsigned hashval;
for (hashval = 0; *word != '\0'; word++)
{
hashval = *word + 31 * hashval;
}
return hashval % N;
//SOURCE: https://stackoverflow.com/questions/7666509/hash-function-for-string
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
//1: open dict file
FILE *dict = fopen(dictionary, "r");
char expression[LENGTH + 1];
//check for return value NULL
if (dict == NULL)
{
printf("Could not open file!");
return false;
}
//FOR EVERY WORD IN DICT!
//2: read strings ("expression") from file one at a time
//do until fscanf returns EOF
while (fscanf(dict, "%s", expression) != EOF)
{
//count words (in global variable) to determine size of dict
dict_size++;
//3: create a new node for each word
//use malloc to make new node
//check for NULL
//strcpy word into node
node *new_node = malloc(sizeof(node));
if (new_node == NULL)
{
printf("Not enough memory for malloc");
return false;
}
strcpy(new_node->word, expression);
new_node->next = NULL;
//4: hash word to obtain a hash value
//use hash function
//this will return an index (alphabet-index)
//5: insert node into hash table at that locatíon
//index into hashtable to get linkedlist that you want to add word into
//set pointers to correct order!!!
//first point from new_node to node-number1 and then from head to new_node to not "lose" the list
new_node->next = table[hash(expression)];
table[hash(expression)] = new_node;
}
//first: allocate memory for new node
// node *n = malloc(sizeof(node));
// strcpy(n->word, "HELLO") --> change to different from hello
// n->next = NULL
//load all words from dict into a hash table
//stop when node->next == NULL
//array of linked lists (each of which represents an char (a,b,c,d, ...))
//need to use datatype "node"
//needs hash function
//takes word (e.g. "apple") and outputs, which is the starting char
// return true if successfully loaded into memory
fclose(dict);
return true;
}
