Dictionary as Hash Table w/ Linked List problems

[durker944]

Hello,

I am currently working on an assignment in which I create a Dictionary as a Hash Table with Linked List to spell check a text document.

I am suppose to do the following :

1.Display any misspelled word (A word is considered misspelled if its not in the dictionary)

2.Count the number of collisions for each cell of the Hash Table when loading the dictionary "words.txt", and store/display the data 20 per line

3.Count the number of words that are misspelled and are correct - In each case, count the number of operations performed and store/display these numbers - Also, store/display the average number of operations for a misspelled and correct word - Note : "number of operations" refers to the number of nodes visited in the linked list for each word


The source code for the HashTable class with linked list is given.
(#including -ing listtools.cpp in hashtable.cpp since it uses templates)

listtools.cpp

#include <cstddef>
#include "listtools.h"

namespace LinkedListSavitch
{
    template<class T>
    void headInsert(Node<T>*& head, const T& theData)
    {
        head = new Node<T>(theData, head);
    }

    template<class T>
    void insert(Node<T>* afterMe, const T& theData)
    {
        afterMe->setLink(new Node<T>(theData, afterMe->getLink( )));
    }

    template<class T>
    void deleteNode(Node<T>* before)
    {
        Node<T> *discard;
        discard = before->getLink( );
        before->setLink(discard->getLink( ));
        delete discard;
    }

    template<class T>
    void deleteFirstNode(Node<T>*& head)
    {
        Node<T> *discard;
        discard = head;
        head = head->getLink( );
        delete discard;
    }

    //Uses cstddef:
    template<class T>
    Node<T>* search(Node<T>* head, const T& target)
    {
        Node<T>* here = head;

        if (here == NULL) //if empty list
        {
            return NULL;
        }
        else
        {
            while (here->getData( ) != target && here->getLink( ) != NULL)
                here = here->getLink( );

            if (here->getData( ) == target)
                return here;
            else
                return NULL;
        }
    }

}//LinkedListSavitch 

hashtable.cpp

#include <iostream>
#include <string>
#include "listtools.h"
#include "listtools.cpp"
#include "hashtable.h"

using LinkedListSavitch::Node;
using LinkedListSavitch::search;
using LinkedListSavitch::headInsert;
using namespace std;

#define HASH_WEIGHT 31

namespace HashTableSavitch
{
   HashTable::HashTable()
   {
    for (int i = 0; i < SIZE; i++)
    {
     hashArray[i] = NULL;
    }
   }

   HashTable::~HashTable()
   {
     for (int i=0; i<SIZE; i++)
     {
       Node<string> *next = hashArray[i];
       while (next != NULL)
       {
         Node<string> *discard = next;
	 next = next->getLink( );
	 delete discard;
       }
     }
   }

   unsigned int HashTable::computeHash(string s) const
   {
    unsigned int hash = 0;
    for (unsigned int i = 0; i < s.length( ); i++)
    {
    	hash = HASH_WEIGHT * hash + s[i];
    }
    return hash % SIZE;
   }

   bool HashTable::containsString(string target) const
   {
    int hash = this->computeHash(target);
    Node<string>* result = search(hashArray[hash], target);
    if (result == NULL)
       return false;
    else
       return true;
   }

   void HashTable::put(string s)
   {
	   int hash = computeHash(s);
	   if (search(hashArray[hash], s) == NULL)
       {
		   // Only add the target if it's not in the list
		   headInsert(hashArray[hash], s);
       }
   }
} // HashTableSavitch 

My main.cpp file currently

#include <iostream>
#include <fstream>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <string>
#include "hashtable.h"
using namespace std;
using HashTableSavitch::HashTable;

void upToLow(string & str);
void removePunct(string & str);

int main()
{
	HashTable h;
	string currWord;
	string word;
	int countMisspelled = 0;
	int countCorrect = 0;

	//Get input from words.rtf
	ifstream dictionary("words.txt");

	//File checking
	if (dictionary.fail())
	{
		cout << "File does not exist" << endl;
		cout << "Exit program" << endl;
	}

    //Create the dictionary as a hash table
    while(dictionary >> currWord)
    {
    	h.put(currWord);
    }
    dictionary.close();

    //Get input from gettysburg_address.txt
    ifstream input("gettysburg_address.txt");

	//File checking
	if (input.fail())
	{
		cout << "File does not exist" << endl;
		cout << "Exit program" << endl;
	}

	//Spell check gettysburg_address.txt
	cout << "Misspelled words : " << endl;
	cout << endl;

	//If a word is not in the dictionary assume misspelled
	while(input >> word)
	{
		removePunct(word);
		upToLow(word);
		if(h.containsString(word) == false)
		{
			countMisspelled++; // Increment misspelled words count
			cout << word << " ";
			if(countMisspelled % 20 == 0) // Display misspelled words 20 per line
			{
				cout << endl;
			}
		}
		else
		{
			countCorrect++; // Increment correct words count
		}
	}
	input.close();

	cout << endl;
	cout << endl;

	cout << "Number of misspelled words : " << countMisspelled << endl;
	cout << "Number of correct words : " << countCorrect << endl;

	return 0;
}


/*Function to convert uppercase letters to lowercase*/
void upToLow(string & str)
{
	for (unsigned int i = 0; i < strlen(str.c_str()); i++)
		 if (str[i] >= 0x41 && str[i] <= 0x5A)
			  str[i] = str[i] + 0x20;
}


/*Function to remove punctuation from string*/
void removePunct(string & str)
{
	str.erase(remove_if(str.begin(), str.end(), static_cast<int(*)(int)>(&ispunct)),str.end());
}

I've managed so far to spell check the text file given and display the words that are misspelled and the counts for "correct" and "misspelled". But I don't really know what I should do for counting the collisions and operations. My instructor very briefly went over hash tables and linked lists so I am quite a noob at this.

For counting the number of collisions for each slot of the hash table, would I need check if different words have the same hash value and implement a counter variable? I'm a bit lost on how to do this.

For counting the "number of operations" or rather "the number of nodes visited in the linked list for each word", I have no clue where to start.

Any tips/help on how I should solve these problems is very much appreciated.

[norm b]

2.Count the number of collisions for each cell of the Hash Table when loading the dictionary "words.txt

Just create another array.

hashtable:h:
int collision[SIZE];

Initalize the array in the constructor and increment in put():

hashtable.cpp:

    
HashTable::HashTable() 
{
   for (int i = 0; i < SIZE; i++)
   {
       hashArray[i] = 0;
       collision[i] = -1; // -1 because the first increment is not a collision
   }
} 

void HashTable::put(string s)
{
    int hash = computeHash(s);
    collision[hash]+=1;  // Add this statement
    if (search(hashArray[hash], s) == NULL)
    {
        // Only add the target if it's not in the list
        headInsert(hashArray[hash], s);
    }
}

[durker944]

Thank you very much. But I'm now having troubles displaying the number of collisions at each slot. I created a void function called "printArray()" as followed :

   void HashTable::printArray()
   {
	   int number;
	   for(int i = 0; i < SIZE; i++)
	   {
		number = collisionArray[i];
		cout << "----------------\n";
	        cout << "index = " << i << endl;
		cout << "Collisions = " << number << endl;
		cout << "----------------\n";
	   }
   }

But it displays the number of collisions at each slot as 0. Am I missing something extremely simple here?

EDIT :

Never mind. Just realized I misplaced the incrementor in wrong place in put(). Thank you for the help.

[norm b]

I don't see why that wouldn't work.

Can you step through your app in a debugger?

Edit: Do you have your increment inside the if statement in HashTable::put()? Need to refresh more often.