Read Access Violation when implementing hashing ADT

0

I am working on a Hashing program where it reads a file of famous people based on date, zip code, gender, etc. I have progressed through the program quite a bit but I have been stumped on an error for hours which does not let me compile my program. Any help or guidance in the right direction to at least get my program running would be appreciated. Will post the files necessary to use the program below along with the error message I am receiving.

Exception thrown at 0x006BEE72 in Dictionary.exe: 0xC0000005: Access violation reading location 0xCDCDCE7D. Unhandled exception thrown: read access violation. endEntry was 0xCDCDCDCD.

Error Happens on Line 41 of HashedEntry.h as shown below:

   while (endEntry->nextPtr != nullptr) // <---- error gets triggered here
   {
       endEntry = endEntry->nextPtr;
   }

Client.cpp:

#include <iostream>
#include <fstream>
#include <cassert>
#include "HashedDictionary.h"

using namespace std;

struct FamousPerson {
    string id;
    char taxStatus;
    string lastname;
    string firstname;
    int age;
    string street;
    string zip;
};

void readOnePerson(istream& infile, FamousPerson& readMe);


// the insertion operator overload is just here so that the HashedDictionary
// display function can use it to print FamousPerson objects.
ostream& operator<<(ostream& out, const FamousPerson& printMe);


int main() {
    HashedDictionary<string, FamousPerson> h;
    FamousPerson tempPerson;
    ifstream infile("famous.txt");
    assert(infile);

    readOnePerson(infile, tempPerson);
    while (infile) {
        h.add(tempPerson.lastname, tempPerson);
        cout << tempPerson << endl;
        readOnePerson(infile, tempPerson);
    }

    h.display();
}





ostream& operator<<(ostream& out, const FamousPerson& printMe) {
    out << printMe.id << " ";
    out << printMe.taxStatus << " ";
    out << printMe.lastname << " ";
    out << printMe.firstname << " ";
    out << printMe.age << " ";
    out << printMe.street << " ";
    out << printMe.zip;
    return out;
}


void readOnePerson(istream& infile, FamousPerson& readMe) {
    infile >> readMe.id;
    infile >> readMe.taxStatus;
    infile >> readMe.lastname;
    infile >> readMe.firstname;
    infile >> readMe.age;
    infile >> readMe.street;
    infile >> readMe.zip;
}

HashedEntry.h:

/** A class of entry objects for a hashing implementation of the
    ADT dictionary.
 @file HashedEntry.h */

#ifndef _HASHED_ENTRY
#define _HASHED_ENTRY

#include "Entry.h"

template<class KeyType, class ItemType>
class HashedEntry : public Entry<KeyType, ItemType>
{
private:
   HashedEntry<KeyType, ItemType>* nextPtr;

public:
    HashedEntry()
    {
        nextPtr = nullptr;
    }
   HashedEntry(ItemType newEntry, KeyType itemKey):Entry<KeyType,ItemType>(newEntry, itemKey)
   {
       nextPtr = nullptr;
   }
   HashedEntry(ItemType newEntry, KeyType itemKey, HashedEntry<KeyType, ItemType>* nextEntryPtr) :Entry<KeyType, ItemType>(newEntry, itemKey)
   {
       nextPtr->setItem(newEntry);
       nextPtr->setKey(itemKey);
       nextPtr = nextEntryPtr;
   }
   void setNext(HashedEntry<KeyType, ItemType>* nextEntryPtr)
   {
       HashedEntry<KeyType, ItemType>* newEntry = nextPtr;
       HashedEntry<KeyType, ItemType>* endEntry = nextEntryPtr;

       while (endEntry->nextPtr != nullptr)
       {
           endEntry = endEntry->nextPtr;
       }
       endEntry->nextPtr = nextEntryPtr;
       endEntry = nullptr;
       nextPtr = nextEntryPtr;
   }
   HashedEntry<KeyType, ItemType>* getNext() const
   {
       return nextPtr;
   }
}; // end HashedEntry

//#include "HashedEntry.cpp"
#endif

HashedDictionary.h:

#include <string>
#include <cstdlib>
#include<iostream>

#include "DictionaryInterface.h"
#include "HashedEntry.h"

#ifndef _HASHED_DICTIONARY
#define _HASHED_DICTIONARY

using namespace std;


template< class KeyType, class ItemType>
class HashedDictionary : public DictionaryInterface<KeyType, ItemType>
{
private:
    HashedEntry<KeyType, ItemType>** hashTable;
    int itemCount; // Count of dictionary entries
    int hashTableSize; // Table size must be prime
    static const int DEFAULT_SIZE = 101;
public:

    int hFunction(const KeyType& x) const
    {
        int num = Hrule(x) % hashTableSize;
        return num;
    }

    int Hrule(const KeyType& ph) const
    {
        int numForm = 0;
        for (int i = 0; i < ph.length(); i++)
        {
            numForm = numForm * 128 + ph[i];
        }

        return numForm;
    }

    HashedDictionary()
    {
        itemCount = 0;
        hashTableSize = DEFAULT_SIZE;
        hashTable = new HashedEntry<KeyType, ItemType> * [DEFAULT_SIZE];
    }

    HashedDictionary(int newHTableSize)
    {
        hashTableSize = newHTableSize;
        itemCount = 0;
        hashTable = new HashedEntry<KeyType, ItemType> * [newHTableSize];
    }

    bool isEmpty() const
    {
        return itemCount == 0;
    }

    int getNumberOfItems() const
    {
        return itemCount;
    }


    bool add(const KeyType& searchKey, const ItemType& newItem)
    {
        // Create entry to add to dictionary
        HashedEntry<KeyType, ItemType>* entryToAddPtr =
            new HashedEntry<KeyType, ItemType>(newItem, searchKey);

        // Compute the hashed index into the array
        int itemHashIndex = getHashIndex(searchKey);

        // Add the entry to the chain at itemHashIndex
        if (hashTable[itemHashIndex] == nullptr)
        {
            hashTable[itemHashIndex] = entryToAddPtr;
        }
        else
        {
            entryToAddPtr->setNext(hashTable[itemHashIndex]);
            hashTable[itemHashIndex] = entryToAddPtr;
        }

        return true;
    }



    bool remove(const KeyType& searchKey)
    {
        bool itemFound = false;

        // Compute the hashed index into the array
        int itemHashIndex = getHashIndex(searchKey);
        if (hashTable[itemHashIndex] != nullptr)
        {
            // Special case - first node has target
            if (searchKey == hashTable[itemHashIndex]->getKey())
            {
                HashedEntry<KeyType, ItemType>* entryToRemovePtr =
                    hashTable[itemHashIndex];
                hashTable[itemHashIndex] = hashTable[itemHashIndex]->getNext();
                delete entryToRemovePtr;
                entryToRemovePtr = nullptr; // For safety
                itemFound = true;
            }
            else // Search the rest of the chain
            {
                HashedEntry<KeyType, ItemType>* prevPtr = hashTable[itemHashIndex];
                HashedEntry<KeyType, ItemType>* curPtr = prevPtr->getNext();
                while ((curPtr != nullptr) && !itemFound)
                {
                    // Found item in chain so remove that node
                    if (searchKey == curPtr->getKey())
                    {
                        prevPtr->setNext(curPtr->getNext());
                        delete curPtr;
                        curPtr = nullptr; // For safety
                        itemFound = true;
                    }
                    else // Look at next entry in chain
                    {
                        prevPtr = curPtr;
                        curPtr = curPtr->getNext();
                    }
                }
            }
        }

        return itemFound;
    }


    void clear()
    {
        for (int i = 0; i < hashTableSize; i++)
        {
            while (hashTable[i] != nullptr)
            {
                HashedEntry<KeyType,ItemType>* delPtr = hashTable[i];
                hashTable[i] = hashTable[i]->getNext();
                delete delPtr;
                delPtr= nullptr;
            }
        }
        itemCount = 0;
    }

    ItemType getItem(const KeyType& itemKey) const
    {
        assert(contains(itemKey));
        int itemHashIndex = getHashIndex(itemKey);
        HashedEntry<KeyType,ItemType>* chainPtr = hashTable[itemHashIndex];
        while((chainPtr != nullptr) && itemKey != chainPtr->getKey())
        {
            chainPtr = chainPtr->getNext();
        }
        if (chainPtr == nullptr)
        {
            return chainPtr->getItem();
        }
    }

    bool contains(const KeyType& searchKey) const
    {
        int ItemHashIndex = getHashIndex(searchKey);
        HashedEntry<KeyType, ItemType>* chainPtr = hashTable[ItemHashIndex];
        while ((chainPtr != nullptr) && (searchKey != chainPtr->getKey()))
        {
            chainPtr = chainPtr->getNext();
        }
        return (chainPtr != nullptr);
    }

    //Working on getHashIndex and display

    int getHashIndex(const KeyType& itemKey) const
    {


        return hFunction(itemKey);
        /*
        int i = 0;
        int key = itemKey[i] * 32;
        i++;

        while (isalpha(itemKey[i]))
        {
            key = (key + itemKey[i]) & DEFAULT_SIZE;
            key *= 32;
            i++;
        }

        return key % DEFAULT_SIZE;*/
    }

    void display()
    {
        int i = 0;
        while (i < hashTableSize)
        {
            if (hashTable[i] != nullptr)
            {
                HashedEntry<KeyType, ItemType>* nextEntry = hashTable[i];

                while (nextEntry != nullptr)
                {
                    cout << nextEntry->getItem() << " ";
                    nextEntry = nextEntry->getNext();
                }

                cout << endl;
                nextEntry = nullptr;
                delete nextEntry;
            }
            i++;
        }
    }
};


#endif 

Entry.h:

/** A class of entry objects for an array-based implementation of the ADT dictionary.
    Listing 18-2.
 @file Entry.h */

#ifndef _ENTRY
#define _ENTRY

template <class KeyType, class ItemType>
class Entry
{
private:
   ItemType item;
   KeyType searchKey;

protected:
    void setKey(const KeyType& itemKey)
    {
        searchKey = itemKey;
   }

public:
    Entry()
    {
        item = ItemType();
        searchKey = KeyType();
    }
   Entry(ItemType newEntry, KeyType itemKey)
   {
       item = newEntry;
       searchKey = itemKey;
   }
   ItemType getItem() const
   {
       return item;
   }
   KeyType getKey() const
   {
       return searchKey;
   }
   void setItem(const ItemType& newEntry)
   {
       item = newEntry;
   }
}; // end Entry

//#include "Entry.cpp"
#endif

DictionaryInterface.h:

#ifndef _DICTIONARY_INTERFACE
#define _DICTIONARY_INTERFACE


template<class KeyType, class ItemType>
class DictionaryInterface 
{
public:   


   /** Sees whether this dictionary is empty.
    @return True if the dictionary is empty;
       otherwise returns false. */
   virtual bool isEmpty() const = 0;

   /** Gets the number of items in this dictionary.
    @return The number of items in the dictionary. */
   virtual int getNumberOfItems() const = 0;

   /** Inserts an item into this dictionary according to the item’s search key.
    @pre  The search key of the new item differs from all search
       keys presently in the dictionary.
    @post  If the insertion is successful, newItem is in its
       proper position within the dictionary.
    @param searchKey  The search key associated with the item to be inserted.
    @param newItem  The item to add to the dictionary.
    @return  True if item was successfully added, or false if not. */
   virtual bool add(const KeyType& searchKey, const ItemType& newItem) = 0;

   /** Removes an item with the given search key from this dictionary.
    @post  If the item whose search key equals searchKey existed in the dictionary, 
       the item was removed.
    @param searchKey  The search key of the item to be removed.
    @return  True if the item was successfully removed, or false if not. */
   virtual bool remove(const KeyType& searchKey) = 0;

   /** Removes all entries from this dictionary. */
   virtual void clear() = 0;

   /** Retrieves an item with a given search key from a dictionary.
    @post  If the retrieval is successful, the item is returned.
    @param searchKey  The search key of the item to be retrieved.
    @return  The item associated with the search key.
    @throw  NotFoundException if the item does not exist. */
   virtual ItemType getItem(const KeyType& searchKey) const = 0;

   /** Sees whether this dictionary contains an item with a given
       search key.
    @post  The dictionary is unchanged.
    @param searchKey  The search key of the item to be retrieved.
    @return  True if an item with the given search key exists in the dictionary. */
   virtual bool contains(const KeyType& searchKey) const = 0;

   /** Traverses this dictionary and calls a given client function once for each item.
    @post  The given function’s action occurs once for each item in the
       dictionary and possibly alters the item.
    @param visit A client function. */
   //virtual void traverse(void visit(ItemType&)) const = 0;
}; // end DictionaryInterface

#endif
c++
class
pointers
hash
adt
asked on Stack Overflow Dec 4, 2020 by Boom • edited Dec 4, 2020 by Boom

0 Answers

Nobody has answered this question yet.


User contributions licensed under CC BY-SA 3.0