Here is the link to the question (problem set)speller I find the recursion conditions correct. the problem is in the check function, according to the outputs. So when I changed it, the code worked. Here are the codes from dictionary.c (first one with recursion and the second one without it)
with recursion
- here I defined two functions of my own in order to recursively go through the lists...
// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <string.h>
#include "dictionary.h"
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH 1];
struct node *next;
}
node;
bool search(node *s, const char *wod);
void frr(node *ptr);
int sije = 0;
// TODO: Choose number of buckets in hash table
// ans - i would choose a 2d array which is [26][LENGTH 1]
const unsigned int N = 26;
// 2d Hash table
node *table[N][LENGTH];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// finding the hash for the word
int h = hash(word);
// finding the length for the word
int len = strlen(word) - 1;
// creating another pointer for the sake of iterating
node *tmp = table[h][len];
return search(tmp, word);
}
bool search(node *s, const char *wod)
{
if (s == NULL)
{
return false;
}
if (!strcasecmp(s -> word, wod))
{
return true;
}
else
{
s = s -> next;
bool c = search(s, wod);
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// TODO: Improve this hash function
return toupper(word[0]) - 'A';
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// make the hash table free of garbage values
for (int i = 0; i < 26; i )
{
for (int j = 0; j < 10; j )
{
table[i][j] = NULL;
}
}
// TODO
// open the dictionary file
FILE *dict = fopen(dictionary, "r");
if (dict == NULL)
{
return false;
}
// read the word inside a char array
char n[LENGTH 1];
while (fscanf(dict, "%s", n) != EOF)
{
// call the hash function and get the hach code
int h = hash(n);
// this will return something from 0 till 25
int len = strlen(n) - 1;
// this will have the length of the word
// let's load it to the hach table
// create a new node
node *no = malloc(sizeof(node));
if (no == NULL)
{
return false;
}
// copy the word from n to no
strcpy(no -> word, n);
// declare the pointer inside the node to null
no -> next = NULL;
// insert the node inside the hach table
if (table[h][len] == NULL)
{
table[h][len] = no;
}
// else if the spot is populated
else
{
no -> next = table[h][len];
table[h][len] = no;
}
sije = 1;
}
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// TODO
return sije;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
for (int i = 0; i < 26; i )
{
for (int j = 0; j < LENGTH; j )
{
// if table at that inces in not null,
// that means that there is a linked list at that index of the table
if (table[i][j] != NULL)
{
frr(table[i][j]);
}
}
}
return true;
}
void frr(node *ptr)
{
if (ptr == NULL)
{
return;
}
frr(ptr -> next);
free(ptr);
}
without recursion (the one which worked)
// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <string.h>
#include "dictionary.h"
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH 1];
struct node *next;
}
node;
void frr(node *ptr);
int sije = 0;
// TODO: Choose number of buckets in hash table
// ans - i would choose a 2d array which is [26][LENGTH]
const unsigned int N = 26;
// 2d Hash table
node *table[N][LENGTH];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// finding the hash of the code
int h = hash(word);
// finding the length of the code
int len = strlen(word) - 1;
// creating another pointer for the sake of iterating
node *tmp = table[h][len];
while (true)
{
if (tmp == NULL)
{
return false;
}
if (!strcasecmp(tmp -> word, word))
{
return true;
}
tmp = tmp -> next;
}
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// TODO: Improve this hash function
return toupper(word[0]) - 'A';
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// make the hash table free of garbage values
for (int i = 0; i < 26; i )
{
for (int j = 0; j < 10; j )
{
table[i][j] = NULL;
}
}
// TODO
// open the dictionary file
FILE *dict = fopen(dictionary, "r");
if (dict == NULL)
{
return false;
}
// read the word inside a char array
char n[LENGTH 1];
while (fscanf(dict, "%s", n) != EOF)
{
// call the hash function and get the hach code
int h = hash(n);
// this will return something from 0 till 25
int len = strlen(n) - 1;
// this will have the length of the word
// let's load it to the hach table
// create a new node
node *no = malloc(sizeof(node));
if (no == NULL)
{
return false;
}
// copy the word from n to no
strcpy(no -> word, n);
// declare the pointer inside the node to null
no -> next = NULL;
// insert the node inside the hach table
if (table[h][len] == NULL)
{
table[h][len] = no;
}
// else if the spot is populated
else
{
no -> next = table[h][len];
table[h][len] = no;
}
sije = 1;
}
fclose(dict);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// TODO
return sije;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
for (int i = 0; i < 26; i )
{
for (int j = 0; j < LENGTH; j )
{
// if table at that inces in not null,
// that means that there is a linked list at that index of the table
if (table[i][j] != NULL)
{
frr(table[i][j]);
}
}
}
return true;
}
void frr(node *ptr)
{
if (ptr == NULL)
{
return;
}
frr(ptr -> next);
free(ptr);
}
What could be the reason. All others are correct, only the checking part ...
CodePudding user response：
I thought I would investigate this issue further as it seemed to me that adding in a return within the "else" block should address the issue. Possibly, I was not making the answer clear enough via the comments so I went ahead and acquired the lesson code, implemented your code solution with the non-recursive check function performing some test over a select set of text files, and then trying out the code with the recursive search function along with the code tweak I had noted.
Executing the non-recursive solution over the "aca.txt" file, the following was the terminal output to be used as the baseline.
WORDS MISSPELLED: 17062
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 376904
TIME IN load: 0.08
TIME IN check: 3.61
TIME IN size: 0.00
TIME IN unload: 0.01
TIME IN TOTAL: 3.70
I then revised the program, dictionary.c, to include the check/search function calls with the code in its original state.
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// finding the hash for the word
int h = hash(word);
// finding the length for the word
int len = strlen(word) - 1;
// creating another pointer for the sake of iterating
node *tmp = table[h][len];
return search(tmp, word);
}
bool search(node *s, const char *wod)
{
if (s == NULL)
{
return false;
}
if (!strcasecmp(s -> word, wod))
{
return true;
}
else
{
s = s -> next;
bool c = search(s, wod);
}
return false;
}
Executing this version of the code did give some superfluous misspelling values when run over the same file.
WORDS MISSPELLED: 359710
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 376904
TIME IN load: 0.07
TIME IN check: 4.85
TIME IN size: 0.00
TIME IN unload: 0.01
TIME IN TOTAL: 4.93
My guess is that this is the type of behavior you were experiencing.
I then revised the search function to provide a return statement within the "else" block as I had noted in the comments. Following is the refactored code.
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// finding the hash for the word
int h = hash(word);
// finding the length for the word
int len = strlen(word) - 1;
// creating another pointer for the sake of iterating
node *tmp = table[h][len];
return search(tmp, word);
}
bool search(node *s, const char *wod)
{
if (s == NULL)
{
return false;
}
if (!strcasecmp(s -> word, wod))
{
return true;
}
else
{
s = s -> next;
return search(s, wod); /* Added this line of code */
//bool c = search(s, wod); /* Deactivated this line of code */
}
return false;
}
When the program was recompiled and executed over the same text file, the following statistical output was acquired.
WORDS MISSPELLED: 17062
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 376904
TIME IN load: 0.08
TIME IN check: 4.14
TIME IN size: 0.00
TIME IN unload: 0.01
TIME IN TOTAL: 4.23
This agrees with the values listed with the non-recursive version of the program.
I checked this refactored version against the other selected text files and all agreed with the values run using the non-recursive version of the program.
FYI, I utilized the gcc compiler. That is the compiler that I have on my system in lieu of Clang. And I will point out one other thing I needed to do to make successfully build this program. When compiling, the compiler complained about having a variable size definition for the "table" array.
const unsigned int N = 26;
To get around this issue with my compiler, I had to move the assignment/definition of "N" to the same spot as the "LENGTH" definition in the header file.
// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45
#define N 26
I don't think these additional tweaks had any bearing on the functionality of using a recursive function, but I wanted to be fully transparent.
Anyway, hopefully with this expanded explanation, you might try out the code tweaks to see if the recursive function would now work.