• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 571
  • Last Modified:

Hash Table

This is kind a continuation of a project I have been working on that compares the efficiency of a binary tree, linked list, and now a hash table. Here is what I have for main()...and the HashTable. When its finished the HashTable will also display in main the same basic cout statements as the other two. What I need help with is the main() implementation and what is noted in the HashTable comments...I will raise points to whomever helps me complete it. Thanks.

-----------------------------------------
main()

#include "BST.h"
#include "LL.h"
#include "HashTable.h"
#include <iostream>
#include <ctime>

using namespace std;

int randomNumberGenerator();

void main()
{
   
    bool promptUser = true;
    char userSelection[10];
    int avgFoundBST = 0;
      int avgFoundmyList = 0;
    int avgNotFoundBST = 0;
      int avgNotFoundmyList = 0;
    int counter = 0;
    int foundBST = 0;
      int foundmyList = 0;
    int notFoundBST = 0;
      int notFoundmyList = 0;
    int compFoundBST = 0;
      int compFoundmyList = 0;
    int compNotFoundBST = 0;
      int compNotFoundmyList = 0;
    int linkedListCount = 0;
    int numCompares = 0;
    int ranNum = 0;
    int ran = 0;
   
    BST<int> myBST;
    LinkedList myList;
   
    while(promptUser)
    {    
        int i;
        //seed generator
        srand(11111111);    
        int t1 = clock();
        for (i = 0; i < 40000; i ++)
        {
            myBST.insert(rand());
        }
       
        int t2 = clock();
        srand(11111111);    
        int t3= clock();
        for (i = 0; i < 40000; i ++)
        {
            myList.insertEnd(rand());
        }
       
        int t4 = clock();
        cout << "How many tests would you like to perform? (Enter 'Q' to quit)" << endl;
       
        //test search
        cin.getline(userSelection, 10);              
       
        //Converts the selection to a number to test
        int numTests = atoi(userSelection);
        if(numTests > 0)
        {
            cout << endl << "Performing tests: " << endl << endl;
           
            srand(33333333);     // take another seed number or all numbers would be found
            for(i = 0; i < numTests; i ++)
            {
                //Search array new generated random number
                ran = rand();
                if (myBST.search(ran, numCompares))
                {
                    foundBST++;
                    compFoundBST += numCompares;
                }
                else
                {
                    notFoundBST++;
                    compNotFoundBST += numCompares;
                }
                cout << ran << endl;
                //resets the numCompares counter
                numCompares = 0;
            }
                  srand(33333333);     // take another seed number or all numbers would be found
            for(i = 0; i < numTests; i ++)
            {
                //Search array new generated random number
                ran = rand();
                if (myList.search(ran, numCompares))
                {
                    foundmyList++;
                    compFoundmyList += numCompares;
                }
                else
                {
                    notFoundmyList++;
                    compNotFoundmyList += numCompares;
                }
                cout << ran << endl;
                //resets the numCompares counter
                numCompares = 0;
            }
           
            counter = numTests;

            avgFoundBST = ((foundBST  * 100 + counter / 2)/ counter);
            avgNotFoundBST = ((notFoundBST * 100  + counter / 2)/ counter);

                  avgFoundmyList = ((foundmyList  * 100 + counter / 2)/ counter);
            avgNotFoundmyList = ((notFoundmyList * 100  + counter / 2)/ counter);
           
            cout << endl << "Binary Search Tree" << endl;
            cout << "Number Found " << foundBST << endl;
            cout << "Number Not Found " << notFoundBST << endl;
            cout << "Ttl Compares (Found) " << compFoundBST << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundBST << endl;
            cout << "Avg Compares (Found) " << avgFoundBST << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundBST << endl << endl;    
            cout << "Tree Depth        : " << myBST.depth() << endl;
            cout << "Tree Node Count   : " << myBST.count() << endl << endl;

                  cout << "Linked List" << endl;
            cout << "Number Found " << foundmyList << endl;
            cout << "Number Not Found " << notFoundmyList << endl;
            cout << "Ttl Compares (Found) " << compFoundmyList << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundmyList << endl;
            cout << "Avg Compares (Found) " << avgFoundmyList << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundmyList << endl << endl;    
                  cout << "Linked List Count : " << myList.getLength() << endl << endl;    
        }
       
        else if(toupper(userSelection[0]) == 'Q')
        {
            promptUser = false;
        }
       
        //invalid user input
        else
        {    
            cout << "Enter a number greater than zero" << endl;
            cout << "Q to quit" << endl;
            promptUser = true;
        }
    }
}
--------------------------------------------

HashTable.h

#ifndef HASH_TABLE_INCLUDED
#define HASH_TABLE_INCLUDED

//-- INCLUDES -----------------------------------------------------------------
#include <iostream>
#include <new>
using namespace std;


template <typename TYPE>
class HashTable
{
      // the possible state values that a record can be in
      enum RecordState { EMPTY, OCCUPIED, DELETED };

      // the basic hash table record
      // NEED HELP: Modify this structure so it just stores a linked list of TYPE
      struct HashRecord
      {
            TYPE        data;                  // piece of data in this record
            RecordState state;                  // state of the record

            // add a new item record with a hash entry of OCCUPIED
            HashRecord(const TYPE & newData)
            {
                  data = newData;
                  state = OCCUPIED;
            }

            // default constructor makes sure state is EMPTY
            HashRecord()
            {
                  state = EMPTY;
            }
      };

      // the actual ptr to the dynamic array
      HashRecord * array;
      unsigned     capacity;
      unsigned     count;

      // private method to find hash location
      int generateHashLocation(const TYPE & item) const
      {
            return item % capacity;            // simple mod hash function
      }

public:
      // constructor to create the hash table at a given capacity
      HashTable(unsigned maxCapacity);

      // gets for capacity and count
      unsigned getCapacity() const            { return capacity;  }
      unsigned getCount() const                  { return count;            }

      // method to add to hash table.  Returns false if no capacity remaining
      bool add(const TYPE & newItem);

      // method to remove from hash table.  Returns false if item not existing
      bool remove(const TYPE & oldItem);

      // method to retrieve from the hash table.  Returns false if not found
      bool find(TYPE & searchItem) const;

      // display prints contents of table
      void display(ostream & out);

      // copy constructor
      HashTable(const HashTable<TYPE> & oldTable);

      // assignment operator
      const HashTable<TYPE> & operator = (const HashTable<TYPE> & oldTable);

      // destructor
      ~HashTable();

};




// constructor to create the hash table at a given capacity
template <typename TYPE>
HashTable<TYPE>::HashTable(unsigned maxCapacity)
      : array(NULL), count(0), capacity(0)
{
      // will call default constructor on each record, setting them to
      // EMPTY
      array = new HashRecord[maxCapacity];

      // make sure no errors
      if(!array)
      {
            cerr << "Could not create hash table with size " << maxCapacity << endl;
      }

      else
      {
            capacity = maxCapacity;
      }
}



// method to add to hash table.  Returns false if no capacity remaining
// -----------
// NEED HELP: Update to use chaining (close addressing).   Instead of checking
// to see if the cell is occupied, insert it into the list
// at the home location if it does not already exist.
template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
      if(count < capacity)
      {
            int loc = generateHashLocation(newItem);      // natural loc

            // linear probe.  If array is occupied at hash location, increment
            // the probe.  Could also do quadratic probe here.
            while(array[loc].state == OCCUPIED)
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge
            }

            array[loc].state = OCCUPIED;
            array[loc].data  = newItem;
            count++;
            return true;
      }

      // no space found, can't insert
      return false;
}



// method to remove from hash table.  Returns false if item not existing
// -----------
// NEED HELP: Update to use chaining (close addressing).  Instead of checking
// to see if the cell is occupied, delete the item in the
// linked list if it exists.
template <typename TYPE>
bool HashTable<TYPE>::remove(const TYPE & oldItem)
{
      bool found = false;

      int homeloc = generateHashLocation(oldItem);      // natural loc
      int loc = homeloc;

      // linear probe.  If array is occupied at hash location, increment
      // the probe.  Could also do quadratic probe here.
      while((array[loc].state != EMPTY) && !found)
      {
            // check if item we want
            if((array[loc].data == oldItem)      && (array[loc].state == OCCUPIED))
            {
                  found = true;
                  array[loc].state = DELETED;
                  count--;
            }
            else
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge

                  // if we loop all the way around back to home loc, stop
                  if(loc == homeloc)
                        break;
            }
      }

      // no space found, can't insert
      return found;
}



// method to retrieve from the hash table.  Returns false if not found
// -----------
// NEED HELP: Update to use chaining (close addressing).  Search the linked list
// and return true if it is found
template <typename TYPE>
bool HashTable<TYPE>::find(TYPE & searchItem) const
{
      bool found = false;

      int homeloc = generateHashLocation(searchItem);      // natural loc
      int loc = homeloc;

      // linear probe.  If array is occupied at hash location, increment
      // the probe.  Could also do quadratic probe here.
      while((array[loc].state != EMPTY) && !found)
      {
            // check if item we want
            if((array[loc].data == searchItem) && (array[loc].state == OCCUPIED))
            {
                  found = true;
            }
            else
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge

                  // if we loop all the way around back to home location, stop
                  if(loc == homeloc)
                        break;
            }
      }

      // no space found, can't insert
      return found;
}



// display prints contents of table
// -----------
// NEED HELP: Update to use chaining (close addressing).  Print
// all linked lists in the cells with linked list size > 0
template <typename TYPE>
void HashTable<TYPE>::display(ostream & out)
{
      for(unsigned i=0; i<capacity; i++)
      {
            if(array[i].state == OCCUPIED)
            {
                  out << i << ": " << array[i].data << endl;
            }
      }
}



// copy constructor
template <typename TYPE>
HashTable<TYPE>::HashTable(const HashTable<TYPE> & oldTable)
      : array(NULL), size(0), capacity(0)
{
      array = new HashRecord[oldTable.capacity];

      // if allocation failed, print error
      if(!array)
      {
            cerr << "Could not create copy of hash table of size " 
                  << oldTable.capacity << endl;
      }

      // otherwise copy the table
      else
      {
            size = oldTable.size;
            capacity = oldTable.capacity;

            for(unsigned i = 0; i<capacity; i++)
            {
                  array[i] = oldTable.array[i];
            }
      }
}



// assignment operator
template <typename TYPE>
const HashTable<TYPE> & HashTable<TYPE>::operator = (const HashTable<TYPE> & oldTable)
{
      if(this != &oldTable)
      {
            // clear old mem
            delete [] array;
            count = capacity = 0;

            array = new HashRecord[oldTable.capacity];

            // if allocation failed, print error
            if(!array)
            {
                  cerr << "Could not create copy of hash table of size " 
                        << oldTable.capacity << endl;
            }

            // otherwise copy the table
            else
            {
                  size = oldTable.size;
                  capacity = oldTable.capacity;

                  for(unsigned i = 0; i<capacity; i++)
                  {
                        array[i] = oldTable.array[i];
                  }
            }
      }

      return *this;
}



// destructor
template <typename TYPE>
HashTable<TYPE>::~HashTable()
{
      delete [] array;
}



#endif
0
jandhb
Asked:
jandhb
  • 20
  • 13
1 Solution
 
itsmeandnobodyelseCommented:
jandhb,

the first you have todo is to turn LinkedList class to a template class. You cannot use it in template class HashTable if the data element couldn't be set arbitrarily.

I have done it, but it isn't quite an easy job. These are the steps to do:

- Remove typedef or definition of type Generic

- Change class Node (in Node.h) to a template class:

     // forward declaration
     template <typename Generic>
     class LinkedList;

     template <typename Generic>
     class Node
     {
        Generic                data;
        Node<Generic>*   next;

        friend class LinkedList<Generic>;
     };

- Move all LinkedList functions of ll.cpp to ll.h

- Add the template class specifier to class and all functions:

  //declaration of LinkedList class
  template <typename Generic>
  class LinkedList
  {
       ...
  };

- Change all Occurences of class Node to Node<Generic>, e. g.

     //first element in linked list
     Node<Generic> *first;
     //last element in linked list
     Node<Generic> *last;

- Remove ll.cpp from your project/makefile

- Change LinkedList variable in main() to

  LinkedList<int> myList;


Regards, Alex

0
 
jandhbAuthor Commented:
Alex,

I'm glad you picked this one up again. I enjoy having you help me. I'll make these changes tonight when I get home from work and get back with you.

A couple of questions first.

1. Just so I understand - Are you saying that first we need to modify the LinkedList that we currently have because in order to use this with our HashTable and implement the chaining collision resolution method? I just did not realize the LinkedList class would have to be modified, so I'm just asking for clarity. Because we will still need to output the data for the LinkedList and Binary Tree as we were doing before, just now we need to add a HashTable, make sense?

2. Once these changes are done in the LinkedList is the next step then to modify the HashTable? A couple of things that were not listed in the comments for the HashTable is that we'll need to return the number of probes it took to find the item (same one we were searching for in LinkedList and Binary Tree) in the find(). Also, we'll want to give the HashTable a capacity of 50000.

Thanks.  
0
 
itsmeandnobodyelseCommented:
1. Yes. You need to store the type you get in HashTable class to a LinkedList member object. HastTable is a template class, so you'll get arbitrary type. And the LinkedList member will be defined like that:

  template <typename TYPE>
  class HashTable
  {
        ...
        LinkedList<TYPE>*  hashArray;

        ...
  };

You see, we couldn't take LinkedList here, if LinkedList is using predefined Generic type, what is in fact an 'int' type.

2. Yes again. These will be the next steps and HashTable::search will get an numCompares argument same as the other collections. If you are done with LinkedList template, you should post ll.h, bst.h and node.h. That will allow other experts to participate.

Regards, Alex
 

0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
itsmeandnobodyelseCommented:
>> Also, we'll want to give the HashTable a capacity of 50000.

A HashTable is different to BST, as it's full capacity (number of items it can hold) couldn't be sized in advance. We have to determine the size of the hash table array (== number of different hash codes possible) that is only a fraction of the maximum capacity (e. g. 20 percent). If two or more items point to the same hash code, we will use a LinkedList at each spot to hold these items. Therefore, a HashTable hasn't a maximum capacity (same as LinkedList) but grows dynamically.

Regards, Alex


0
 
jandhbAuthor Commented:
Current files now look like this...

---------------------------------------------
ll.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

//include files
#include "Node.h"
#include <iostream>

using namespace std;

//declaration of LinkedList class
template <typename Generic>
class LinkedList
{
//public member functions
public:
      //constructor
      LinkedList();
      //destructor
      ~LinkedList();

      void insertFront(const Generic &item);
      void insertEnd(const Generic & item);
      void display(std::ostream &outStream = std::cout) const;
      void remove(const Generic &item);
      void deleteList();
      void removeFirstNode();

      int getLength() const;
      Generic getFirstValue() const;
      bool search(const Generic &item, int& numCompares) const;
      bool empty() const;
      bool full() const;

//private data members
private:
     //first element in linked list
     Node<Generic> *first;
     //last element in linked list
     Node<Generic> *last;
};

//end define
#endif

//constructor
//called when the class instance is created
//sets up initial values for the class data members
//initial first pointer to NULL
template <typename Generic>
LinkedList<Generic>::LinkedList() : first(0), last(0)
{

}

//destructor
//called when the class instance is destroyed
template <typename Generic>
LinkedList<Generic>::~LinkedList()
{
      //cleans up leftover memory
      deleteList();
}

//insertFront
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the very beginning of the list
template <typename Generic>
void LinkedList<Generic>::insertFront(const Generic &item)
{
      //create a pointer to a node
      Node *newNode;

      //allocate memory for the new node
      newNode = new Node;

      //set the newNode's value
      newNode->data = item;

      //point the new node
      //same node that is currently the beginning of the list
      newNode->next = first;

      //change the beginning of the list to point to the newNode
      first = newNode;
}

//insertEnd
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the end of the list
template <typename Generic>
void LinkedList<Generic>::insertEnd(const Generic & item)
{
    //create pointer to a node
    Node *newNode;
   
    //allocate memory for the newNode
    newNode = new Node;
   
    //initialize the node's members
    newNode->data = item;
    newNode->next = 0;
   
    //check to see if there are nodes in the list
    if (last == 0)
    {
        //set the beginning of the list to point at the new node
        first = last = newNode;
    }
    else
    {
        //set the last node's next value to the new node
        last->next = newNode;
        last       = newNode;
    }
}

//display
//accepts outStream, a file or cout stream to output data to
//always displays all of the data in the linked list
//either to a file or  to the screen
template <typename Generic>
void LinkedList<Generic>::display(ostream &outStream) const
{
      //create a pointer to a node
      Node *current = first;

      //loop through each node in the list
      while (current != 0)
      {
            //send data to the output stream
            outStream << current->data << endl;

            //move to the next node
            current = current->next;
      }
}

//remove
//accepts item, a Generic data type to search and remove from the list
//searches for the item passed to it and removes that node from the list
template <typename Generic>
void LinkedList<Generic>::remove(const Generic &item)
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node *current = first;

            //check if first item is what is being searched for
            if (current->data == item)
            {
                  //set the first node to point to the second node
                  first = current->next;

                  //deallocate first node
                  delete current;
            }
            else
            {
                  //create a pointer to a node
                  Node *previous = current;

                  //move current to the next node
                  current = current->next;

                  //loop through nodes until data is found
                  //or end of file has been reached
                  while ( (current != 0) && (current->data != item) )
                  {
                        //move each pointer to the next node
                        current = current->next;
                        previous = previous->next;
                  }

                  //check if either previous or current is null
                  if ( (current != 0) && (previous != 0) )
                  {
                        //set the previous node to point to the node following current
                        previous->next = current->next;

                        //deallocate the node searched for
                        delete current;
                  }
            }
      }
}

//deleteList
//deallocates all nodes in the list
//sets the first pointer to NULL
template <typename Generic>
void LinkedList<Generic>::deleteList()
{
      //create pointers to a node
      Node *current = first;
      Node *previous;

      //loop through all nodes in the list
      while (current != 0)
      {
            //set previous to the current node
            previous = current;

            //set current to the next node
            current = current->next;

            //deallocate the previous node
            delete previous;
      }

      //reset beginning of list to NULL
      first = 0;
}

//getLength
//counts all nodes in the list and returns the count
template <typename Generic>
int LinkedList
::getLength() const
{
      //create a pointer to a node
      Node *current = first;

      //create an int variable to hold the total
      int total = 0;

      //loop through all nodes in the list
      while (current != 0)
      {
            //increment total by 1 and move to next node
            ++total;
            current = current->next;
      }

      //return the total
      return total;
}

//search
//accepts item, a Generic data type that is searched for in the list
//searches each node in the list to see if its value matches the item passed
//a true or false is returned if the item was found or not
template <typename Generic>
bool LinkedList::search(const Generic &item, int& numCompares) const
{
      //create a pointer to a node
      Node *current = first;

      //create a flag to tell if the value was found
      bool found = false;

      //loop through each node until the end of the list or the value is found
      while ( (current != 0) && (current->data != item) )
      {
            //move to the next node
            current = current->next;
            numCompares++;
      }

      //if current is not null then the end of the list was not reached
      if (current != 0)
      {
            //value was found
            found = true;
            numCompares += 2;
      }

      //return the found flag
      return found;
}

//empty
//returns a true value if the list is empty
//false if the list has nodes in it
template <typename Generic>
bool LinkedList::empty() const
{
      //return true if the first is NULL
      return (first == 0);
}

//full
//this will always return a false value
//this linked list version has virtually unlimited memory
template <typename Generic>
bool LinkedList::full() const
{
      return false;
}

//removeFirstNode
//removes first node from the list
template <typename Generic>
void LinkedList::removeFirstNode()
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node *current = first;

            //point the beginning of the list to the second node
            first = current->next;

            //deallocate the memory for  current
            delete current;
      }
}

//getFirstValue
//returns the value of the first node in the list
template <typename Generic>
Generic LinkedList::getFirstValue() const
{
      //this will not work if list is empty
      return first->data;
}
--------------------------------------------------

bst.h

#ifndef BINARY_SEARCH_TREE_INCLUDED
#define BINARY_SEARCH_TREE_INCLUDED

///////////////////////////////////////////////////////////////////////////////
// Binary Search Tree
//
// A data structure combining the dynamic aspects of a linked list and the
// search capabilities of the binary search.
//////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <new>
using namespace std;

template <typename DataType>
class BST
{
      // this inner class represents our node.
      struct BinNode
      {
            DataType  data;
            BinNode * left;
            BinNode * right;

            BinNode() : left(NULL), right(NULL)
            {
            }

            BinNode(const DataType & item)
                  : left(NULL), right(NULL)
            {
                  data = item;
            }
      };

      // the root node is the basis for the tree
      BinNode * root;

      // these private member functions are called by the public functions
      // and used to mask the recursive nature of the data structure.  Plus,
      // they require a ptr to the current node, which we will never allow
      // the outside world to see as it could compromise the integrity of our
      // data structure.

      // recursive search used by the delete function to find both the
      // target node location and the parent of the target node
      bool recSearch(const DataType & item, BinNode * & foundLoc,
            BinNode * & parentLoc) const;

      // recursive in order traversal to print the nodes
      void recInOrder(ostream & out, BinNode * currentNode) const;

      // recusrive fxn to destroy the entire tree
      void recDestroy(BinNode * & currentNode);

      // recursive fxn to calculate the depth of the tree
      int recDepth(BinNode * currentNode) const;

      // recursive count of nodes
      int recCount(BinNode * currentNode) const;

      // recursive fxn to copy the current node and subtrees
      void recCopy(BinNode * & copiedNode, BinNode * originalNode);

public:
      // These are the actual public functions called by our data structure

      // constructor - creates empty tree
      BST();

      // copy constructor - creates copy of tree for pass-by-value
      BST(const BST<DataType> & originalTree);

      // assignment operator - creates a copy of tree for assignment op
      const BST<DataType> & operator = (const BST<DataType> & originalTree);

      // empty - tells whether the tree is empty or not
      bool empty() const;

      // search - searches for a node and returns TRUE if in the tree
      bool search(const DataType & item, int& numCompares) const;

      // insert - adds a new node in order to the BST
      void insert(const DataType & item);

      // remove - destroys a node from the tree if it exists
      void remove(const DataType & item);

      // inorder - In order traversal of the tree, prints each node
      // to the output stream passed in (for example, cout)
      void inOrder(ostream & out) const;

      // count - returns a count of the number of nodes
      int count() const;

      // depth - returns the depth of tree
      int depth() const;

      // clear - cleans out the memory
      void clear();

      // destructor - cleans up the tree, removing all items
      ~BST();
};



// recursive search used by the delete function to find both the
// target node location and the parent of the target node
template <typename DataType>
bool BST<DataType>::recSearch(const DataType & item, BinNode * & foundLoc,
      BinNode * & parentLoc) const
{
      foundLoc   = root;
      parentLoc  = NULL;

      // search left/right through tree until find node or run off
      // edge of tree
      while(foundLoc != NULL)
      {
            if(item < foundLoc->data)
            {
                  // store off parent and go left
                  parentLoc = foundLoc;
                  foundLoc = foundLoc->left;
            }
            else if(foundLoc->data < item)
            {
                  // store off parent and go right
                  parentLoc = foundLoc;
                  foundLoc = foundLoc->right;
            }
            else
            {
                  // found it!
                  return true;
            }
      }

      // if we ran off edge of tree, we didn't find it
      return false;
}


// recursive in order traversal to print the nodes
template <typename DataType>
void BST<DataType>::recInOrder(ostream & out, BinNode * currentNode) const
{
      if(currentNode != NULL)
      {
            recInOrder(out, currentNode->left);
            out << currentNode->data << "  ";
            recInOrder(out, currentNode->right);
      }
}


// recusrive fxn to destroy the entire tree
template <typename DataType>
void BST<DataType>::recDestroy(BinNode * & currentNode)
{
      // destroy the tree recursively starting at the left
      // and right subtree, then destroy current node and NULL the ptr,
      // very similar to post order traversal
      if (currentNode != NULL)
      {
            recDestroy(currentNode->left);
            recDestroy(currentNode->right);
            delete currentNode;
            currentNode = NULL;
      }
}


// recursive fxn to calculate the depth of the tree
template <typename DataType>
int BST<DataType>::recDepth(BinNode * currentNode) const
{
      // calculate the depth of the tree starting at current node
      // determine depth of left & right subtrees, pick the larger of the
      // two, add 1 to account for the current node, and that is what you
      // return
            
      if (currentNode == NULL)
      {
            return (0);
      }
      else
      {
            //compute the depth of each subtree
            int lDepth = recDepth(currentNode->left);
            int rDepth = recDepth(currentNode->right);
            //use the larger one
            if (lDepth > rDepth)
            {
                  return (lDepth + 1);
            }
            else
            {
                  return (rDepth + 1);
            }
      }
}


// recursive fxn to calculate the count of nodes in the tree
template <typename DataType>
int BST<DataType>::recCount(BinNode * currentNode) const
{
      // calculate the count of nodes in the tree by adding 1 to the recursive
      // count of nodeds in the left & right subtree
      if (currentNode == NULL)
      {
            return (0);
      }
      else
      {
            return (recCount(currentNode->left) + 1 + recCount(currentNode->right));
      }
}


// recursive fxn to copy the original tree to this tree given the
// current original node and location for the new node
template <typename DataType>
void BST<DataType>::recCopy(BinNode * & copiedNode, BinNode * originalNode)
{
      // recursively copy the original subtree to ours starting at the
      // original Node, do this by creating a node at copiedNode, copy over
      // data from original Node, then recursively call for left & right of
      // both nodes
      if(originalNode != NULL)
      {
            copiedNode = originalNode;
            recCopy(copiedNode->left, originalNode->left);
            recCopy(copiedNode->right, originalNode->right);
      }
}


// constructor - creates empty tree
template <typename DataType>
BST<DataType>::BST()
      : root(NULL)
{
      // nothing else is needed here
}


// copy constructor - creates copy of tree for pass-by-value
template <typename DataType>
BST<DataType>::BST(const BST<DataType> & originalTree)
      : root(NULL)
{
      // recursively copy the original tree to this tree starting at root
      recCopy(root, originalTree->root);
}


// assignment operator - creates a copy of tree for assignment op
template <typename DataType>
const BST<DataType> & BST<DataType>::operator = (const BST<DataType> & originalTree)
{
      // make sure not self assignment
      if(this != &originalTree)
      {
            // first destroy current tree
            recDestroy(root);

            // then copy
            recCopy(root, originalTree->root);
      }

      // return reference to the tree
      return *this;
}


// empty - tells whether the tree is empty or not
template <typename DataType>
bool BST<DataType>::empty() const
{
      return (root == NULL);
}


// search - searches for a node and returns TRUE if in the tree
template <typename DataType>
bool BST<DataType>::search(const DataType & item, int& numCompares) const
{
    BinNode * locPtr = root;
    bool found = false;
   
    // navigate the tree left/right until find node or hit end of tree
    while(!found && locPtr != NULL)
    {
        if(item < locPtr->data)
        {      
            locPtr = locPtr->left;
            numCompares++;
        }
        else if(locPtr->data < item)
        {      
            locPtr = locPtr->right;
            numCompares += 2;
        }
        else
        {
            found = true;
            numCompares += 2;
        }
    }  
    return found;
}


// insert - adds a new node in order to the BST
template <typename DataType>
void BST<DataType>::insert(const DataType & item)
{
      BinNode * locPtr = root;
      BinNode * parent = NULL;
      bool found = false;

      // search left/right through tree until we find where the item goes
      while(!found && locPtr != NULL)
      {
            parent = locPtr;

            if(item < locPtr->data)
                  locPtr = locPtr->left;
            else if(locPtr->data < item)
                  locPtr = locPtr->right;
            else
                  found = true;
      }

      // now, if it isn't already in the tree, add it
      if(!found)
      {
            locPtr = new BinNode(item);

            // if there was no parent, the tree is empty and the new node should
            // be the root
            if(parent == NULL)
                  root = locPtr;
            else if(item < parent->data)
                  parent->left = locPtr;
            else
                  parent->right = locPtr;
      }
}


// remove - destroys a node from the tree if it exists
template <typename DataType>
void BST<DataType>::remove(const DataType & item)
{
      BinNode * killLoc;            // location of node to kill
      BinNode * parentLoc;      // location of node to kill's parent

      // try to find the node.  If found, will have loc of node
      // to kill and loc of parent of node to kill
      bool found = recSearch(item, killLoc, parentLoc);
      
      // if not found, do nothing.  If found, remove the node.
      if(found)
      {
            // if both left and right children exist, promote the smallest
            // on the right side
            if(killLoc->left != NULL && killLoc->right != NULL)
            {
                  BinNode * successor = killLoc->right;
                  parentLoc = killLoc;

                  // search until hit NULL
                  while(successor->left != NULL)
                  {
                        parentLoc = successor;
                        successor = successor->left;
                  }

                  killLoc->data = successor->data;
                  killLoc = successor;
            }

            // now handle case where one or other child exists
            BinNode * subTree = killLoc->left;

            // if left subtree does not exist, use right subtree
            if(subTree == NULL)
                  subTree = killLoc->right;

            // if no parent, we are killing the root
            if(parentLoc == NULL)
                  root = subTree;

            // otherwise, if we were left of parent
            else if(parentLoc->left == killLoc)
                  parentLoc->left = subTree;

            else
                  parentLoc->right = subTree;

            delete killLoc;
      }
}


// inorder - In order traversal of the tree, prints each node
// to the output stream passed in (for example, cout)
template <typename DataType>
void BST<DataType>::inOrder(ostream & out) const
{
      // recusively traverse the tree, printing the data to the out stream
      recInOrder(out, root);
}


// depth - returns the depth of tree
template <typename DataType>
int BST<DataType>::depth() const
{
      // recursively determine the depth of the tree, starting at root
      return recDepth(root);
}


// count - returns the count of nodes in the tree
template <typename DataType>
int BST<DataType>::count() const
{
      // recurisvely determine the count of nodes starting at root
      return recCount(root);
}


// clear - destroys all nodes
template <typename DataType>
void BST<DataType>::clear()
{
      recDestroy(root);
}


// destructor - cleans up the tree, removing all items
template <typename DataType>
BST<DataType>::~BST()
{
      // destroy the tree recursively starting at the root
      clear();
}


#endif
------------------------------------------------

node.h

#ifndef NODE_H
#define NODE_H

//include files
#include <string>

//generic data type alias
//typedef std::string Generic;
template <typename Generic>
class LinkedList;

//structure of a node
template <typename Generic>
class Node                                                
{
      //data piece of node
      Generic data;
      //pointer to the next node
      Node<Generic> *next;
      friend class LinkedList<Generic>;
};

//end define
#endif
0
 
jandhbAuthor Commented:
Let me know where we go from here.

1. As you have said, I know we'll need to modify the find() in the HashTable so it returns the number of probes to find the item.
2. Do I have this line LinkedList<TYPE>*  hashArray; in the wrong place in HashTable.h? Should it be within the Struct?
2. Eventually we will have output from main that will need to look like this for the Hash Table...

            cout << "Hash Table" << endl;
            cout << "Number Found " << foundmyHashTable << endl;
            cout << "Number Not Found " << notFoundmyHashTable << endl;
            cout << "Ttl Compares (Found) " << compFoundmyHashTable << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundmyHashTable << endl;
            cout << "Avg Compares (Found) " << avgFoundmyHashTable << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundmyHashTable << endl << endl;    
            cout << "Hash Table Capacity: " << myHashTable.getCapacity() << endl;  
            cout << "Hash Table Size: " << myHashTable.getCount() << endl;
            cout << "Hash Table Load Factor: " << myHashTable.? << endl << endl;    
0
 
itsmeandnobodyelseCommented:
>>>> Change all Occurences of class Node to Node<Generic>

That isn't done properly till now. I found some statements in ll.h

     Node *newNode;

that have to be changed to

     Node<Generic> *newNode;

Compile your program by using

   LinkedList<int> myList;

and the compiler tells you where you have to change.

1.  Change

     // method to retrieve from the hash table.  Returns false if not found
     bool find(TYPE & searchItem) const;

to

     // method to retrieve from the hash table.  Returns false if not found
     bool find(const TYPE & searchItem, int& numCompares) const;

2.  I think we don't need the struct, but only the array

     LinkedList<TYPE>*  hashArray;

An empty list signals an EMPTY state or OCCUPIED if not empty. The DELETED state wasn't necessary when using LinkedList.

3. Most likely.

Regards, Alex



0
 
jandhbAuthor Commented:
HashTable.h looks like...

-----------------------------------------
#ifndef HASH_TABLE_INCLUDED
#define HASH_TABLE_INCLUDED

//-- INCLUDES -----------------------------------------------------------------
#include <iostream>
#include <new>
using namespace std;



///////////////////////////////////////////////////////////////////////////////
// HashTable
//
// The following is a basic implementation of a HashTable in C++.  A HashTable
// is a structure where lookups are near instantanious, but you pay a price
// in terms of the fact that your dataset is unordered.
//
// This table only works for basic types (int, char, double, long, etc).
///////////////////////////////////////////////////////////////////////////JMMH
template <typename TYPE>
class HashTable
{
      // the possible state values that a record can be in
      enum RecordState { EMPTY, OCCUPIED, DELETED };

      // the basic hash table record
      // TODO: Modify this structure so it just stores a linked list of TYPE
      /*struct HashRecord
      {
            TYPE        data;                  // piece of data in this record
            RecordState state;                  // state of the record

            // add a new item record with a hash entry of OCCUPIED
            HashRecord(const TYPE & newData)
            {
                  data = newData;
                  state = OCCUPIED;
            }

            // default constructor makes sure state is EMPTY
            HashRecord()
            {
                  state = EMPTY;
            }
      };*/

      // the actual ptr to the dynamic array
      //HashRecord * array;
      unsigned     capacity;
      unsigned     count;

      LinkedList<TYPE>*  hashArray;

      // private method to find hash location
      int generateHashLocation(const TYPE & item) const
      {
            return item % capacity;            // simple mod hash function
      }

public:
      // constructor to create the hash table at a given capacity
      HashTable(unsigned maxCapacity);

      // gets for capacity and count
      unsigned getCapacity() const            { return capacity;  }
      unsigned getCount() const                  { return count;            }

      // method to add to hash table.  Returns false if no capacity remaining
      bool add(const TYPE & newItem);

      // method to remove from hash table.  Returns false if item not existing
      bool remove(const TYPE & oldItem);

      // method to retrieve from the hash table.  Returns false if not found
       bool find(const TYPE & searchItem, int& numCompares) const;

      // display prints contents of table
      void display(ostream & out);

      // copy constructor
      HashTable(const HashTable<TYPE> & oldTable);

      // assignment operator
      const HashTable<TYPE> & operator = (const HashTable<TYPE> & oldTable);

      // destructor
      ~HashTable();

};




// constructor to create the hash table at a given capacity
template <typename TYPE>
HashTable<TYPE>::HashTable(unsigned maxCapacity)
      : array(NULL), count(0), capacity(0)
{
      // will call default constructor on each record, setting them to
      // EMPTY
      array = new HashRecord[maxCapacity];

      // make sure no errors
      if(!array)
      {
            cerr << "Could not create hash table with size " << maxCapacity << endl;
      }

      else
      {
            capacity = maxCapacity;
      }
}



// method to add to hash table.  Returns false if no capacity remaining
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will insert it into the list
// at the home location if it does not already exist.
template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
      if(count < capacity)
      {
            int loc = generateHashLocation(newItem);      // natural loc

            // linear probe.  If array is occupied at hash location, increment
            // the probe.  Could also do quadratic probe here.
            while(array[loc].state == OCCUPIED)
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge
            }

            array[loc].state = OCCUPIED;
            array[loc].data  = newItem;
            count++;
            return true;
      }

      // no space found, can't insert
      return false;
}



// method to remove from hash table.  Returns false if item not existing
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will delete the item in the
// linked list if it exists.
template <typename TYPE>
bool HashTable<TYPE>::remove(const TYPE & oldItem)
{
      bool found = false;

      int homeloc = generateHashLocation(oldItem);      // natural loc
      int loc = homeloc;

      // linear probe.  If array is occupied at hash location, increment
      // the probe.  Could also do quadratic probe here.
      while((array[loc].state != EMPTY) && !found)
      {
            // check if item we want
            if((array[loc].data == oldItem)      && (array[loc].state == OCCUPIED))
            {
                  found = true;
                  array[loc].state = DELETED;
                  count--;
            }
            else
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge

                  // if we loop all the way around back to home loc, stop
                  if(loc == homeloc)
                        break;
            }
      }

      // no space found, can't insert
      return found;
}



// method to retrieve from the hash table.  Returns false if not found
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Search the linked list
// and return true if it is found
template <typename TYPE>
bool HashTable<TYPE>::find(const TYPE & searchItem, int& numCompares) const
{
      bool found = false;

      int homeloc = generateHashLocation(searchItem);      // natural loc
      int loc = homeloc;

      // linear probe.  If array is occupied at hash location, increment
      // the probe.  Could also do quadratic probe here.
      while((array[loc].state != EMPTY) && !found)
      {
            // check if item we want
            if((array[loc].data == searchItem) && (array[loc].state == OCCUPIED))
            {
                  found = true;
            }
            else
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge

                  // if we loop all the way around back to home location, stop
                  if(loc == homeloc)
                        break;
            }
      }

      // no space found, can't insert
      return found;
}



// display prints contents of table
// -----------
// TODO: Update to use chaining (close addressing).  Print
// all linked lists in the cells with linked list size > 0
template <typename TYPE>
void HashTable<TYPE>::display(ostream & out)
{
      for(unsigned i=0; i<capacity; i++)
      {
            if(array[i].state == OCCUPIED)
            {
                  out << i << ": " << array[i].data << endl;
            }
      }
}



// copy constructor
template <typename TYPE>
HashTable<TYPE>::HashTable(const HashTable<TYPE> & oldTable)
      : array(NULL), size(0), capacity(0)
{
      array = new HashRecord[oldTable.capacity];

      // if allocation failed, print error
      if(!array)
      {
            cerr << "Could not create copy of hash table of size " 
                  << oldTable.capacity << endl;
      }

      // otherwise copy the table
      else
      {
            size = oldTable.size;
            capacity = oldTable.capacity;

            for(unsigned i = 0; i<capacity; i++)
            {
                  array[i] = oldTable.array[i];
            }
      }
}



// assignment operator
template <typename TYPE>
const HashTable<TYPE> & HashTable<TYPE>::operator = (const HashTable<TYPE> & oldTable)
{
      if(this != &oldTable)
      {
            // clear old mem
            delete [] array;
            count = capacity = 0;

            array = new HashRecord[oldTable.capacity];

            // if allocation failed, print error
            if(!array)
            {
                  cerr << "Could not create copy of hash table of size " 
                        << oldTable.capacity << endl;
            }

            // otherwise copy the table
            else
            {
                  size = oldTable.size;
                  capacity = oldTable.capacity;

                  for(unsigned i = 0; i<capacity; i++)
                  {
                        array[i] = oldTable.array[i];
                  }
            }
      }

      return *this;
}



// destructor
template <typename TYPE>
HashTable<TYPE>::~HashTable()
{
      delete [] array;
}



#endif
----------------------------------------------

ll.h looks like....

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

//include files
#include "Node.h"
#include <iostream>

using namespace std;

//declaration of LinkedList class
template <typename Generic>
class LinkedList
{
//public member functions
public:
      //constructor
      LinkedList();
      //destructor
      ~LinkedList();

      void insertFront(const Generic &item);
      void insertEnd(const Generic & item);
      void display(std::ostream &outStream = std::cout) const;
      void remove(const Generic &item);
      void deleteList();
      void removeFirstNode();

      int getLength() const;
      Generic getFirstValue() const;
      bool search(const Generic &item, int& numCompares) const;
      bool empty() const;
      bool full() const;

//private data members
private:
     //first element in linked list
     Node<Generic> *first;
     //last element in linked list
     Node<Generic> *last;
};

//end define
#endif

//constructor
//called when the class instance is created
//sets up initial values for the class data members
//initial first pointer to NULL
template <typename Generic>
LinkedList<Generic>::LinkedList() : first(0), last(0)
{

}

//destructor
//called when the class instance is destroyed
template <typename Generic>
LinkedList<Generic>::~LinkedList()
{
      //cleans up leftover memory
      deleteList();
}

//insertFront
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the very beginning of the list
template <typename Generic>
void LinkedList<Generic>::insertFront(const Generic &item)
{
      //create a pointer to a node
      Node<Generic> *newNode;

      //allocate memory for the new node
      newNode = new Node;

      //set the newNode's value
      newNode->data = item;

      //point the new node
      //same node that is currently the beginning of the list
      newNode->next = first;

      //change the beginning of the list to point to the newNode
      first = newNode;
}

//insertEnd
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the end of the list
template <typename Generic>
void LinkedList<Generic>::insertEnd(const Generic & item)
{
    //create pointer to a node
    Node<Generic> *newNode;
   
    //allocate memory for the newNode
    newNode = new Node;
   
    //initialize the node's members
    newNode->data = item;
    newNode->next = 0;
   
    //check to see if there are nodes in the list
    if (last == 0)
    {
        //set the beginning of the list to point at the new node
        first = last = newNode;
    }
    else
    {
        //set the last node's next value to the new node
        last->next = newNode;
        last       = newNode;
    }
}

//display
//accepts outStream, a file or cout stream to output data to
//always displays all of the data in the linked list
//either to a file or  to the screen
template <typename Generic>
void LinkedList<Generic>::display(ostream &outStream) const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //loop through each node in the list
      while (current != 0)
      {
            //send data to the output stream
            outStream << current->data << endl;

            //move to the next node
            current = current->next;
      }
}

//remove
//accepts item, a Generic data type to search and remove from the list
//searches for the item passed to it and removes that node from the list
template <typename Generic>
void LinkedList<Generic>::remove(const Generic &item)
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node<Generic> *current = first;

            //check if first item is what is being searched for
            if (current->data == item)
            {
                  //set the first node to point to the second node
                  first = current->next;

                  //deallocate first node
                  delete current;
            }
            else
            {
                  //create a pointer to a node
                  Node<Generic> *previous = current;

                  //move current to the next node
                  current = current->next;

                  //loop through nodes until data is found
                  //or end of file has been reached
                  while ( (current != 0) && (current->data != item) )
                  {
                        //move each pointer to the next node
                        current = current->next;
                        previous = previous->next;
                  }

                  //check if either previous or current is null
                  if ( (current != 0) && (previous != 0) )
                  {
                        //set the previous node to point to the node following current
                        previous->next = current->next;

                        //deallocate the node searched for
                        delete current;
                  }
            }
      }
}

//deleteList
//deallocates all nodes in the list
//sets the first pointer to NULL
template <typename Generic>
void LinkedList<Generic>::deleteList()
{
      //create pointers to a node
      Node<Generic> *current = first;
      Node<Generic> *previous;

      //loop through all nodes in the list
      while (current != 0)
      {
            //set previous to the current node
            previous = current;

            //set current to the next node
            current = current->next;

            //deallocate the previous node
            delete previous;
      }

      //reset beginning of list to NULL
      first = 0;
}

//getLength
//counts all nodes in the list and returns the count
template <typename Generic>
int LinkedList<Generic>::getLength() const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //create an int variable to hold the total
      int total = 0;

      //loop through all nodes in the list
      while (current != 0)
      {
            //increment total by 1 and move to next node
            ++total;
            current = current->next;
      }

      //return the total
      return total;
}

//search
//accepts item, a Generic data type that is searched for in the list
//searches each node in the list to see if its value matches the item passed
//a true or false is returned if the item was found or not
template <typename Generic>
bool LinkedList<Generic>::search(const Generic &item, int& numCompares) const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //create a flag to tell if the value was found
      bool found = false;

      //loop through each node until the end of the list or the value is found
      while ( (current != 0) && (current->data != item) )
      {
            //move to the next node
            current = current->next;
            numCompares++;
      }

      //if current is not null then the end of the list was not reached
      if (current != 0)
      {
            //value was found
            found = true;
            numCompares += 2;
      }

      //return the found flag
      return found;
}

//empty
//returns a true value if the list is empty
//false if the list has nodes in it
template <typename Generic>
bool LinkedList<Generic>::empty() const
{
      //return true if the first is NULL
      return (first == 0);
}

//full
//this will always return a false value
//this linked list version has virtually unlimited memory
template <typename Generic>
bool LinkedList<Generic>::full() const
{
      return false;
}

//removeFirstNode
//removes first node from the list
template <typename Generic>
void LinkedList<Generic>::removeFirstNode()
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node<Generic> *current = first;

            //point the beginning of the list to the second node
            first = current->next;

            //deallocate the memory for  current
            delete current;
      }
}

//getFirstValue
//returns the value of the first node in the list
template <typename Generic>
Generic LinkedList<Generic>::getFirstValue() const
{
      //this will not work if list is empty
      return first->data;
}
------------------------------------------

1. When compiled I get an error 'Node' : no appropriate default constructor available on this line newNode = new Node; in insertEnd of ll.h
2. We will have to use the numCompares in find().
0
 
itsmeandnobodyelseCommented:
1. Change to

         newNode = new Node<Generic>;

2. In HashTable::find(...) you have to check whether the slot the hashcode is pointing to is empty or not. If empty you are thru. If not you call LinkedList::search( ) using the LinkedList item that is located there and numCompares get properly filled. Maybe you should increment the number by 1 before returning true as the calculation of the hashcode does one additional compare.

Todo:

- Remove all occurences of HashRecord.

- Create the LinkedList hashArray in constructor:

    hashArray = new LinkedList<TYPE> [maxCapacity];

- Adopt the HashTable functions, e. g.

// method to add to hash table.
// -----------
template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
     // if(count < capacity)   // don't need as we can grow dynamically
     // {
            int loc = generateHashLocation(newItem);     // natural loc
            hashArray[loc].insertEnd(newItem);
            count++;
            return true;
     //}
}

Simple, isn't it?

Regards, Alex




0
 
jandhbAuthor Commented:
Can you show me how we would do #2 in the find().

Here is now hashTable.h and ll.h

#ifndef HASH_TABLE_INCLUDED
#define HASH_TABLE_INCLUDED

//-- INCLUDES -----------------------------------------------------------------
#include <iostream>
#include <new>
using namespace std;



///////////////////////////////////////////////////////////////////////////////
// HashTable
//
// The following is a basic implementation of a HashTable in C++.  A HashTable
// is a structure where lookups are near instantanious, but you pay a price
// in terms of the fact that your dataset is unordered.
//
// This table only works for basic types (int, char, double, long, etc).
///////////////////////////////////////////////////////////////////////////JMMH
template <typename TYPE>
class HashTable
{
      // the possible state values that a record can be in
      enum RecordState { EMPTY, OCCUPIED, DELETED };

      // the basic hash table record
      // TODO: Modify this structure so it just stores a linked list of TYPE
      /*struct HashRecord
      {
            TYPE        data;                  // piece of data in this record
            RecordState state;                  // state of the record

            // add a new item record with a hash entry of OCCUPIED
            HashRecord(const TYPE & newData)
            {
                  data = newData;
                  state = OCCUPIED;
            }

            // default constructor makes sure state is EMPTY
            HashRecord()
            {
                  state = EMPTY;
            }
      };*/

      // the actual ptr to the dynamic array
      //HashRecord * array;
      unsigned     capacity;
      unsigned     count;

      LinkedList<TYPE>*  hashArray;

      // private method to find hash location
      int generateHashLocation(const TYPE & item) const
      {
            return item % capacity;            // simple mod hash function
      }

public:
      // constructor to create the hash table at a given capacity
      HashTable(unsigned maxCapacity);

      // gets for capacity and count
      unsigned getCapacity() const            { return capacity;  }
      unsigned getCount() const                  { return count;            }

      // method to add to hash table.  Returns false if no capacity remaining
      bool add(const TYPE & newItem);

      // method to remove from hash table.  Returns false if item not existing
      bool remove(const TYPE & oldItem);

      // method to retrieve from the hash table.  Returns false if not found
       bool find(const TYPE & searchItem, int& numCompares) const;

      // display prints contents of table
      void display(ostream & out);

      // copy constructor
      HashTable(const HashTable<TYPE> & oldTable);

      // assignment operator
      const HashTable<TYPE> & operator = (const HashTable<TYPE> & oldTable);

      // destructor
      ~HashTable();

};


// constructor to create the hash table at a given capacity
template <typename TYPE>
HashTable<TYPE>::HashTable(unsigned maxCapacity)
      : array(NULL), count(0), capacity(0)
{
      // will call default constructor on each record, setting them to
      // EMPTY
      //array = new HashRecord[maxCapacity];

      hashArray = new LinkedList<TYPE> [maxCapacity];

      // make sure no errors
      if(!array)
      {
            cerr << "Could not create hash table with size " << maxCapacity << endl;
      }

      else
      {
            capacity = maxCapacity;
      }
}



// method to add to hash table.  Returns false if no capacity remaining
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will insert it into the list
// at the home location if it does not already exist.
/*template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
      if(count < capacity)
      {
            int loc = generateHashLocation(newItem);      // natural loc

            // linear probe.  If array is occupied at hash location, increment
            // the probe.  Could also do quadratic probe here.
            while(array[loc].state == OCCUPIED)
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge
            }

            array[loc].state = OCCUPIED;
            array[loc].data  = newItem;
            count++;
            return true;
      }

      // no space found, can't insert
      return false;
}*/
template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
   int loc = generateHashLocation(newItem);     // natural loc
   hashArray[loc].insertEnd(newItem);
   count++;
   return true;
}




// method to remove from hash table.  Returns false if item not existing
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will delete the item in the
// linked list if it exists.
template <typename TYPE>
bool HashTable<TYPE>::remove(const TYPE & oldItem)
{
      bool found = false;

      int homeloc = generateHashLocation(oldItem);      // natural loc
      int loc = homeloc;

      // linear probe.  If array is occupied at hash location, increment
      // the probe.  Could also do quadratic probe here.
      while((array[loc].state != EMPTY) && !found)
      {
            // check if item we want
            if((array[loc].data == oldItem)      && (array[loc].state == OCCUPIED))
            {
                  found = true;
                  array[loc].state = DELETED;
                  count--;
            }
            else
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge

                  // if we loop all the way around back to home loc, stop
                  if(loc == homeloc)
                        break;
            }
      }

      // no space found, can't insert
      return found;
}



// method to retrieve from the hash table.  Returns false if not found
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Search the linked list
// and return true if it is found
template <typename TYPE>
bool HashTable<TYPE>::find(const TYPE & searchItem, int& numCompares) const
{
      bool found = false;

      int homeloc = generateHashLocation(searchItem);      // natural loc
      int loc = homeloc;

      // linear probe.  If array is occupied at hash location, increment
      // the probe.  Could also do quadratic probe here.
      while((array[loc].state != EMPTY) && !found)
      {
            // check if item we want
            if((array[loc].data == searchItem) && (array[loc].state == OCCUPIED))
            {
                  found = true;
            }
            else
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge

                  // if we loop all the way around back to home location, stop
                  if(loc == homeloc)
                        break;
            }
      }

      // no space found, can't insert
      return found;
}



// display prints contents of table
// -----------
// TODO: Update to use chaining (close addressing).  Print
// all linked lists in the cells with linked list size > 0
template <typename TYPE>
void HashTable<TYPE>::display(ostream & out)
{
      for(unsigned i=0; i<capacity; i++)
      {
            if(array[i].state == OCCUPIED)
            {
                  out << i << ": " << array[i].data << endl;
            }
      }
}



// copy constructor
template <typename TYPE>
HashTable<TYPE>::HashTable(const HashTable<TYPE> & oldTable)
      : array(NULL), size(0), capacity(0)
{
      array = new HashRecord[oldTable.capacity];

      // if allocation failed, print error
      if(!array)
      {
            cerr << "Could not create copy of hash table of size " 
                  << oldTable.capacity << endl;
      }

      // otherwise copy the table
      else
      {
            size = oldTable.size;
            capacity = oldTable.capacity;

            for(unsigned i = 0; i<capacity; i++)
            {
                  array[i] = oldTable.array[i];
            }
      }
}



// assignment operator
template <typename TYPE>
const HashTable<TYPE> & HashTable<TYPE>::operator = (const HashTable<TYPE> & oldTable)
{
      if(this != &oldTable)
      {
            // clear old mem
            delete [] array;
            count = capacity = 0;

            array = new HashRecord[oldTable.capacity];

            // if allocation failed, print error
            if(!array)
            {
                  cerr << "Could not create copy of hash table of size " 
                        << oldTable.capacity << endl;
            }

            // otherwise copy the table
            else
            {
                  size = oldTable.size;
                  capacity = oldTable.capacity;

                  for(unsigned i = 0; i<capacity; i++)
                  {
                        array[i] = oldTable.array[i];
                  }
            }
      }

      return *this;
}



// destructor
template <typename TYPE>
HashTable<TYPE>::~HashTable()
{
      delete [] array;
}



#endif

-----------------------------------------------------------------------------------

ll.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

//include files
#include "Node.h"
#include <iostream>

using namespace std;

//declaration of LinkedList class
template <typename Generic>
class LinkedList
{
//public member functions
public:
      //constructor
      LinkedList();
      //destructor
      ~LinkedList();

      void insertFront(const Generic &item);
      void insertEnd(const Generic & item);
      void display(std::ostream &outStream = std::cout) const;
      void remove(const Generic &item);
      void deleteList();
      void removeFirstNode();

      int getLength() const;
      Generic getFirstValue() const;
      bool search(const Generic &item, int& numCompares) const;
      bool empty() const;
      bool full() const;

//private data members
private:
     //first element in linked list
     Node<Generic> *first;
     //last element in linked list
     Node<Generic> *last;
};

//end define
#endif

//constructor
//called when the class instance is created
//sets up initial values for the class data members
//initial first pointer to NULL
template <typename Generic>
LinkedList<Generic>::LinkedList() : first(0), last(0)
{

}

//destructor
//called when the class instance is destroyed
template <typename Generic>
LinkedList<Generic>::~LinkedList()
{
      //cleans up leftover memory
      deleteList();
}

//insertFront
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the very beginning of the list
template <typename Generic>
void LinkedList<Generic>::insertFront(const Generic &item)
{
      //create a pointer to a node
      Node<Generic> *newNode;

      //allocate memory for the new node
      newNode = new Node;

      //set the newNode's value
      newNode->data = item;

      //point the new node
      //same node that is currently the beginning of the list
      newNode->next = first;

      //change the beginning of the list to point to the newNode
      first = newNode;
}

//insertEnd
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the end of the list
template <typename Generic>
void LinkedList<Generic>::insertEnd(const Generic & item)
{
    //create pointer to a node
    Node<Generic> *newNode;
   
    //allocate memory for the newNode
    newNode = new Node<Generic>;
   
    //initialize the node's members
    newNode->data = item;
    newNode->next = 0;
   
    //check to see if there are nodes in the list
    if (last == 0)
    {
        //set the beginning of the list to point at the new node
        first = last = newNode;
    }
    else
    {
        //set the last node's next value to the new node
        last->next = newNode;
        last       = newNode;
    }
}

//display
//accepts outStream, a file or cout stream to output data to
//always displays all of the data in the linked list
//either to a file or  to the screen
template <typename Generic>
void LinkedList<Generic>::display(ostream &outStream) const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //loop through each node in the list
      while (current != 0)
      {
            //send data to the output stream
            outStream << current->data << endl;

            //move to the next node
            current = current->next;
      }
}

//remove
//accepts item, a Generic data type to search and remove from the list
//searches for the item passed to it and removes that node from the list
template <typename Generic>
void LinkedList<Generic>::remove(const Generic &item)
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node<Generic> *current = first;

            //check if first item is what is being searched for
            if (current->data == item)
            {
                  //set the first node to point to the second node
                  first = current->next;

                  //deallocate first node
                  delete current;
            }
            else
            {
                  //create a pointer to a node
                  Node<Generic> *previous = current;

                  //move current to the next node
                  current = current->next;

                  //loop through nodes until data is found
                  //or end of file has been reached
                  while ( (current != 0) && (current->data != item) )
                  {
                        //move each pointer to the next node
                        current = current->next;
                        previous = previous->next;
                  }

                  //check if either previous or current is null
                  if ( (current != 0) && (previous != 0) )
                  {
                        //set the previous node to point to the node following current
                        previous->next = current->next;

                        //deallocate the node searched for
                        delete current;
                  }
            }
      }
}

//deleteList
//deallocates all nodes in the list
//sets the first pointer to NULL
template <typename Generic>
void LinkedList<Generic>::deleteList()
{
      //create pointers to a node
      Node<Generic> *current = first;
      Node<Generic> *previous;

      //loop through all nodes in the list
      while (current != 0)
      {
            //set previous to the current node
            previous = current;

            //set current to the next node
            current = current->next;

            //deallocate the previous node
            delete previous;
      }

      //reset beginning of list to NULL
      first = 0;
}

//getLength
//counts all nodes in the list and returns the count
template <typename Generic>
int LinkedList<Generic>::getLength() const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //create an int variable to hold the total
      int total = 0;

      //loop through all nodes in the list
      while (current != 0)
      {
            //increment total by 1 and move to next node
            ++total;
            current = current->next;
      }

      //return the total
      return total;
}

//search
//accepts item, a Generic data type that is searched for in the list
//searches each node in the list to see if its value matches the item passed
//a true or false is returned if the item was found or not
template <typename Generic>
bool LinkedList<Generic>::search(const Generic &item, int& numCompares) const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //create a flag to tell if the value was found
      bool found = false;

      //loop through each node until the end of the list or the value is found
      while ( (current != 0) && (current->data != item) )
      {
            //move to the next node
            current = current->next;
            numCompares++;
      }

      //if current is not null then the end of the list was not reached
      if (current != 0)
      {
            //value was found
            found = true;
            numCompares += 2;
      }

      //return the found flag
      return found;
}

//empty
//returns a true value if the list is empty
//false if the list has nodes in it
template <typename Generic>
bool LinkedList<Generic>::empty() const
{
      //return true if the first is NULL
      return (first == 0);
}

//full
//this will always return a false value
//this linked list version has virtually unlimited memory
template <typename Generic>
bool LinkedList<Generic>::full() const
{
      return false;
}

//removeFirstNode
//removes first node from the list
template <typename Generic>
void LinkedList<Generic>::removeFirstNode()
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node<Generic> *current = first;

            //point the beginning of the list to the second node
            first = current->next;

            //deallocate the memory for  current
            delete current;
      }
}

//getFirstValue
//returns the value of the first node in the list
template <typename Generic>
Generic LinkedList<Generic>::getFirstValue() const
{
      //this will not work if list is empty
      return first->data;
}

0
 
jandhbAuthor Commented:
Should I comment out these lines also...

array = new HashRecord[oldTable.capacity];
0
 
jandhbAuthor Commented:
Here is what I did to the main()...

Would this be correct?

----------------------------------------------

#include "BST.h"
#include "LL.h"
#include "HashTable.h"
#include <iostream>
#include <ctime>

using namespace std;

int randomNumberGenerator();

void main()
{
   
    bool promptUser = true;
    char userSelection[10];
    int avgFoundBST = 0;
      int avgFoundmyList = 0;
      int avgFoundmyHashTable = 0;
    int avgNotFoundBST = 0;
      int avgNotFoundmyList = 0;
      int avgNotFoundmyHashTable = 0;
    int counter = 0;
    int foundBST = 0;
      int foundmyList = 0;
      int foundmyHashTable = 0;
    int notFoundBST = 0;
      int notFoundmyList = 0;
      int notFoundmyHashTable = 0;
    int compFoundBST = 0;
      int compFoundmyList = 0;
      int compFoundmyHashTable = 0;
    int compNotFoundBST = 0;
       int compNotFoundmyList = 0;
    int compNotFoundmyHashTable = 0;
    int linkedListCount = 0;
    int numCompares = 0;
    int ranNum = 0;
    int ran = 0;
   
    BST<int> myBST;
    LinkedList<int> myList;
    HashTable<int> myHashTable;
   
    while(promptUser)
    {    
        int i;
        //seed generator
        srand(11111111);    
        int t1 = clock();
        for (i = 0; i < 40000; i ++)
        {
            myBST.insert(rand());
        }
       
        int t2 = clock();
        srand(11111111);    
        int t3= clock();
        for (i = 0; i < 40000; i ++)
        {
            myList.insertEnd(rand());
        }
       
        int t4 = clock();
        cout << "How many tests would you like to perform? (Enter 'Q' to quit)" << endl;
       
        //test search
        cin.getline(userSelection, 10);              
       
        //Converts the selection to a number to test
        int numTests = atoi(userSelection);
        if(numTests > 0)
        {
            cout << endl << "Performing tests: " << endl << endl;
           
            srand(33333333);     // take another seed number or all numbers would be found
            for(i = 0; i < numTests; i ++)
            {
                //Search array new generated random number
                ran = rand();
                if (myBST.search(ran, numCompares))
                {
                    foundBST++;
                    compFoundBST += numCompares;
                }
                else
                {
                    notFoundBST++;
                    compNotFoundBST += numCompares;
                }
                cout << ran << endl;
                //resets the numCompares counter
                numCompares = 0;
            }
           srand(33333333);     // take another seed number or all numbers would be found
            for(i = 0; i < numTests; i ++)
            {
                //Search array new generated random number
                ran = rand();
                if (myList.search(ran, numCompares))
                {
                    foundmyList++;
                    compFoundmyList += numCompares;
                }
                else
                {
                    notFoundmyList++;
                    compNotFoundmyList += numCompares;
                }
                cout << ran << endl;
                //resets the numCompares counter
                numCompares = 0;
            }
             srand(33333333);     // take another seed number or all numbers would be found
            for(i = 0; i < numTests; i ++)
            {
                //Search array new generated random number
                ran = rand();
                if (myHashTable.search(ran, numCompares))
                {
                    foundmyHashTable++;
                    compFoundmyHashTable += numCompares;
                }
                else
                {
                    notFoundmyList++;
                    compNotFoundmyHashTable += numCompares;
                }
                cout << ran << endl;
                //resets the numCompares counter
                numCompares = 0;
            }
           
            counter = numTests;

            avgFoundBST = ((foundBST  * 100 + counter / 2)/ counter);
            avgNotFoundBST = ((notFoundBST * 100  + counter / 2)/ counter);

            avgFoundmyList = ((foundmyList  * 100 + counter / 2)/ counter);
            avgNotFoundmyList = ((notFoundmyList * 100  + counter / 2)/ counter);
           
            cout << endl << "Binary Search Tree" << endl;
            cout << "Number Found " << foundBST << endl;
            cout << "Number Not Found " << notFoundBST << endl;
            cout << "Ttl Compares (Found) " << compFoundBST << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundBST << endl;
            cout << "Avg Compares (Found) " << avgFoundBST << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundBST << endl << endl;    
            cout << "Tree Depth        : " << myBST.depth() << endl;
            cout << "Tree Node Count   : " << myBST.count() << endl << endl;

            cout << "Linked List" << endl;
            cout << "Number Found " << foundmyList << endl;
            cout << "Number Not Found " << notFoundmyList << endl;
            cout << "Ttl Compares (Found) " << compFoundmyList << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundmyList << endl;
            cout << "Avg Compares (Found) " << avgFoundmyList << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundmyList << endl << endl;    
            cout << "Linked List Count : " << myList.getLength() << endl << endl;

            cout << "Hash Table" << endl;
            cout << "Number Found " << foundmyHashTable << endl;
            cout << "Number Not Found " << notFoundmyHashTable << endl;
            cout << "Ttl Compares (Found) " << compFoundmyHashTable << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundmyHashTable << endl;
            cout << "Avg Compares (Found) " << avgFoundmyHashTable << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundmyHashTable << endl << endl;    
            cout << "Hash Table Capacity: " << myHashTable.getCapacity() << endl;  
            cout << "Hash Table Size: " << myHashTable.getCount() << endl;
            cout << "Hash Table Load Factor: " << myHashTable.? << endl << endl;
        }
       
        else if(toupper(userSelection[0]) == 'Q')
        {
            promptUser = false;
        }
       
        //invalid user input
        else
        {    
            cout << "Enter a number greater than zero" << endl;
            cout << "Q to quit" << endl;
            promptUser = true;
        }
    }
}
0
 
jandhbAuthor Commented:
I don't think these lines are correct in main()...

HashTable<int> myHashTable;
if (myHashTable.search(ran, numCompares))

0
 
itsmeandnobodyelseCommented:
Can you show me how we would do #2 in the find().

template <typename TYPE>
bool HashTable<TYPE>::find(const TYPE & searchItem, int& numCompares) const
{
     int loc       = generateHashLocation(searchItem);     // natural loc
     bool found = hashArray[loc].search(searchItem, numCompares);
     numCompares++;
     return found;
}

>> Should I comment out these lines also...
>> array = new HashRecord[oldTable.capacity];

Yes, HashRecord and enum recordState both are obsolete (remove them completely after you saved a version of old HashTable).

>> if (myHashTable.search(ran, numCompares))

Actually, the search function in HashTable is called 'find'. But you could (should) rename it.

Regards, Alex





0
 
jandhbAuthor Commented:
I'm getting an error...

error C2512: 'HashTable<TYPE>' : no appropriate default constructor available with [ TYPE=int ]

on this line in main()

HashTable<int> myHashTable;
0
 
jandhbAuthor Commented:
HashTable.h

------------------------------------
#ifndef HASH_TABLE_INCLUDED
#define HASH_TABLE_INCLUDED

//-- INCLUDES -----------------------------------------------------------------
#include <iostream>
#include <new>
using namespace std;



///////////////////////////////////////////////////////////////////////////////
// HashTable
//
// The following is a basic implementation of a HashTable in C++.  A HashTable
// is a structure where lookups are near instantanious, but you pay a price
// in terms of the fact that your dataset is unordered.
//
// This table only works for basic types (int, char, double, long, etc).
///////////////////////////////////////////////////////////////////////////JMMH
template <typename TYPE>
class HashTable
{
      // the possible state values that a record can be in
      //enum RecordState { EMPTY, OCCUPIED, DELETED };

      // the basic hash table record
      // TODO: Modify this structure so it just stores a linked list of TYPE
      /*struct HashRecord
      {
            TYPE        data;                  // piece of data in this record
            RecordState state;                  // state of the record

            // add a new item record with a hash entry of OCCUPIED
            HashRecord(const TYPE & newData)
            {
                  data = newData;
                  state = OCCUPIED;
            }

            // default constructor makes sure state is EMPTY
            HashRecord()
            {
                  state = EMPTY;
            }
      };*/

      // the actual ptr to the dynamic array
      //HashRecord * array;
      unsigned     capacity;
      unsigned     count;

      LinkedList<TYPE>*  hashArray;

      // private method to find hash location
      int generateHashLocation(const TYPE & item) const
      {
            return item % capacity;            // simple mod hash function
      }

public:
      // constructor to create the hash table at a given capacity
      HashTable(unsigned maxCapacity);

      // gets for capacity and count
      unsigned getCapacity() const            { return capacity;  }
      unsigned getCount() const                  { return count;            }

      // method to add to hash table.  Returns false if no capacity remaining
      bool add(const TYPE & newItem);

      // method to remove from hash table.  Returns false if item not existing
      bool remove(const TYPE & oldItem);

      // method to retrieve from the hash table.  Returns false if not found
       bool search(const TYPE & searchItem, int& numCompares) const;

      // display prints contents of table
      void display(ostream & out);

      // copy constructor
      HashTable(const HashTable<TYPE> & oldTable);

      // assignment operator
      const HashTable<TYPE> & operator = (const HashTable<TYPE> & oldTable);

      // destructor
      ~HashTable();

};


// constructor to create the hash table at a given capacity
template <typename TYPE>
HashTable<TYPE>::HashTable(unsigned maxCapacity)
      : array(NULL), count(0), capacity(0)
{
      // will call default constructor on each record, setting them to
      // EMPTY
      //array = new HashRecord[maxCapacity];

      hashArray = new LinkedList<TYPE> [maxCapacity];

      // make sure no errors
      if(!array)
      {
            cerr << "Could not create hash table with size " << maxCapacity << endl;
      }

      else
      {
            capacity = maxCapacity;
      }
}



// method to add to hash table.  Returns false if no capacity remaining
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will insert it into the list
// at the home location if it does not already exist.
/*template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
      if(count < capacity)
      {
            int loc = generateHashLocation(newItem);      // natural loc

            // linear probe.  If array is occupied at hash location, increment
            // the probe.  Could also do quadratic probe here.
            while(array[loc].state == OCCUPIED)
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge
            }

            array[loc].state = OCCUPIED;
            array[loc].data  = newItem;
            count++;
            return true;
      }

      // no space found, can't insert
      return false;
}*/
template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
   int loc = generateHashLocation(newItem);     // natural loc
   hashArray[loc].insertEnd(newItem);
   count++;
   return true;
}




// method to remove from hash table.  Returns false if item not existing
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will delete the item in the
// linked list if it exists.
template <typename TYPE>
bool HashTable<TYPE>::remove(const TYPE & oldItem)
{
      bool found = false;

      int homeloc = generateHashLocation(oldItem);      // natural loc
      int loc = homeloc;

      // linear probe.  If array is occupied at hash location, increment
      // the probe.  Could also do quadratic probe here.
      while((array[loc].state != EMPTY) && !found)
      {
            // check if item we want
            if((array[loc].data == oldItem)      && (array[loc].state == OCCUPIED))
            {
                  found = true;
                  array[loc].state = DELETED;
                  count--;
            }
            else
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge

                  // if we loop all the way around back to home loc, stop
                  if(loc == homeloc)
                        break;
            }
      }

      // no space found, can't insert
      return found;
}



// method to retrieve from the hash table.  Returns false if not found
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Search the linked list
// and return true if it is found
template <typename TYPE>
bool HashTable<TYPE>::search(const TYPE & searchItem, int& numCompares) const
{
     int loc       = generateHashLocation(searchItem);     // natural loc
     bool found = hashArray[loc].search(searchItem, numCompares);
     numCompares++;
     return found;
}


// display prints contents of table
// -----------
// TODO: Update to use chaining (close addressing).  Print
// all linked lists in the cells with linked list size > 0
template <typename TYPE>
void HashTable<TYPE>::display(ostream & out)
{
      for(unsigned i=0; i<capacity; i++)
      {
            if(array[i].state == OCCUPIED)
            {
                  out << i << ": " << array[i].data << endl;
            }
      }
}



// copy constructor
template <typename TYPE>
HashTable<TYPE>::HashTable(const HashTable<TYPE> & oldTable)
      : array(NULL), size(0), capacity(0)
{
      //array = new HashRecord[oldTable.capacity];

      // if allocation failed, print error
      if(!array)
      {
            cerr << "Could not create copy of hash table of size " 
                  << oldTable.capacity << endl;
      }

      // otherwise copy the table
      else
      {
            size = oldTable.size;
            capacity = oldTable.capacity;

            for(unsigned i = 0; i<capacity; i++)
            {
                  array[i] = oldTable.array[i];
            }
      }
}



// assignment operator
template <typename TYPE>
const HashTable<TYPE> & HashTable<TYPE>::operator = (const HashTable<TYPE> & oldTable)
{
      if(this != &oldTable)
      {
            // clear old mem
            delete [] array;
            count = capacity = 0;

            //array = new HashRecord[oldTable.capacity];

            // if allocation failed, print error
            if(!array)
            {
                  cerr << "Could not create copy of hash table of size " 
                        << oldTable.capacity << endl;
            }

            // otherwise copy the table
            else
            {
                  size = oldTable.size;
                  capacity = oldTable.capacity;

                  for(unsigned i = 0; i<capacity; i++)
                  {
                        array[i] = oldTable.array[i];
                  }
            }
      }

      return *this;
}



// destructor
template <typename TYPE>
HashTable<TYPE>::~HashTable()
{
      delete [] array;
}



#endif
----------------------------------------------

ll.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

//include files
#include "Node.h"
#include <iostream>

using namespace std;

//declaration of LinkedList class
template <typename Generic>
class LinkedList
{
//public member functions
public:
      //constructor
      LinkedList();
      //destructor
      ~LinkedList();

      void insertFront(const Generic &item);
      void insertEnd(const Generic & item);
      void display(std::ostream &outStream = std::cout) const;
      void remove(const Generic &item);
      void deleteList();
      void removeFirstNode();

      int getLength() const;
      Generic getFirstValue() const;
      bool search(const Generic &item, int& numCompares) const;
      bool empty() const;
      bool full() const;

//private data members
private:
     //first element in linked list
     Node<Generic> *first;
     //last element in linked list
     Node<Generic> *last;
};

//end define
#endif

//constructor
//called when the class instance is created
//sets up initial values for the class data members
//initial first pointer to NULL
template <typename Generic>
LinkedList<Generic>::LinkedList() : first(0), last(0)
{

}

//destructor
//called when the class instance is destroyed
template <typename Generic>
LinkedList<Generic>::~LinkedList()
{
      //cleans up leftover memory
      deleteList();
}

//insertFront
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the very beginning of the list
template <typename Generic>
void LinkedList<Generic>::insertFront(const Generic &item)
{
      //create a pointer to a node
      Node<Generic> *newNode;

      //allocate memory for the new node
      newNode = new Node;

      //set the newNode's value
      newNode->data = item;

      //point the new node
      //same node that is currently the beginning of the list
      newNode->next = first;

      //change the beginning of the list to point to the newNode
      first = newNode;
}

//insertEnd
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the end of the list
template <typename Generic>
void LinkedList<Generic>::insertEnd(const Generic & item)
{
    //create pointer to a node
    Node<Generic> *newNode;
   
    //allocate memory for the newNode
    newNode = new Node<Generic>;
   
    //initialize the node's members
    newNode->data = item;
    newNode->next = 0;
   
    //check to see if there are nodes in the list
    if (last == 0)
    {
        //set the beginning of the list to point at the new node
        first = last = newNode;
    }
    else
    {
        //set the last node's next value to the new node
        last->next = newNode;
        last       = newNode;
    }
}

//display
//accepts outStream, a file or cout stream to output data to
//always displays all of the data in the linked list
//either to a file or  to the screen
template <typename Generic>
void LinkedList<Generic>::display(ostream &outStream) const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //loop through each node in the list
      while (current != 0)
      {
            //send data to the output stream
            outStream << current->data << endl;

            //move to the next node
            current = current->next;
      }
}

//remove
//accepts item, a Generic data type to search and remove from the list
//searches for the item passed to it and removes that node from the list
template <typename Generic>
void LinkedList<Generic>::remove(const Generic &item)
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node<Generic> *current = first;

            //check if first item is what is being searched for
            if (current->data == item)
            {
                  //set the first node to point to the second node
                  first = current->next;

                  //deallocate first node
                  delete current;
            }
            else
            {
                  //create a pointer to a node
                  Node<Generic> *previous = current;

                  //move current to the next node
                  current = current->next;

                  //loop through nodes until data is found
                  //or end of file has been reached
                  while ( (current != 0) && (current->data != item) )
                  {
                        //move each pointer to the next node
                        current = current->next;
                        previous = previous->next;
                  }

                  //check if either previous or current is null
                  if ( (current != 0) && (previous != 0) )
                  {
                        //set the previous node to point to the node following current
                        previous->next = current->next;

                        //deallocate the node searched for
                        delete current;
                  }
            }
      }
}

//deleteList
//deallocates all nodes in the list
//sets the first pointer to NULL
template <typename Generic>
void LinkedList<Generic>::deleteList()
{
      //create pointers to a node
      Node<Generic> *current = first;
      Node<Generic> *previous;

      //loop through all nodes in the list
      while (current != 0)
      {
            //set previous to the current node
            previous = current;

            //set current to the next node
            current = current->next;

            //deallocate the previous node
            delete previous;
      }

      //reset beginning of list to NULL
      first = 0;
}

//getLength
//counts all nodes in the list and returns the count
template <typename Generic>
int LinkedList<Generic>::getLength() const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //create an int variable to hold the total
      int total = 0;

      //loop through all nodes in the list
      while (current != 0)
      {
            //increment total by 1 and move to next node
            ++total;
            current = current->next;
      }

      //return the total
      return total;
}

//search
//accepts item, a Generic data type that is searched for in the list
//searches each node in the list to see if its value matches the item passed
//a true or false is returned if the item was found or not
template <typename Generic>
bool LinkedList<Generic>::search(const Generic &item, int& numCompares) const
{
      //create a pointer to a node
      Node<Generic> *current = first;

      //create a flag to tell if the value was found
      bool found = false;

      //loop through each node until the end of the list or the value is found
      while ( (current != 0) && (current->data != item) )
      {
            //move to the next node
            current = current->next;
            numCompares++;
      }

      //if current is not null then the end of the list was not reached
      if (current != 0)
      {
            //value was found
            found = true;
            numCompares += 2;
      }

      //return the found flag
      return found;
}

//empty
//returns a true value if the list is empty
//false if the list has nodes in it
template <typename Generic>
bool LinkedList<Generic>::empty() const
{
      //return true if the first is NULL
      return (first == 0);
}

//full
//this will always return a false value
//this linked list version has virtually unlimited memory
template <typename Generic>
bool LinkedList<Generic>::full() const
{
      return false;
}

//removeFirstNode
//removes first node from the list
template <typename Generic>
void LinkedList<Generic>::removeFirstNode()
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node<Generic> *current = first;

            //point the beginning of the list to the second node
            first = current->next;

            //deallocate the memory for  current
            delete current;
      }
}

//getFirstValue
//returns the value of the first node in the list
template <typename Generic>
Generic LinkedList<Generic>::getFirstValue() const
{
      //this will not work if list is empty
      return first->data;
}

-------------------------------------------------------

main

#include "BST.h"
#include "LL.h"
#include "HashTable.h"
#include <iostream>
#include <ctime>

using namespace std;

int randomNumberGenerator();

void main()
{
   
    bool promptUser = true;
    char userSelection[10];
    int avgFoundBST = 0;
      int avgFoundmyList = 0;
      int avgFoundmyHashTable = 0;
    int avgNotFoundBST = 0;
      int avgNotFoundmyList = 0;
      int avgNotFoundmyHashTable = 0;
    int counter = 0;
    int foundBST = 0;
      int foundmyList = 0;
      int foundmyHashTable = 0;
    int notFoundBST = 0;
      int notFoundmyList = 0;
      int notFoundmyHashTable = 0;
    int compFoundBST = 0;
      int compFoundmyList = 0;
      int compFoundmyHashTable = 0;
    int compNotFoundBST = 0;
      int compNotFoundmyList = 0;
      int compNotFoundmyHashTable = 0;
    int linkedListCount = 0;
    int numCompares = 0;
    int ranNum = 0;
    int ran = 0;
   
    BST<int> myBST;
    LinkedList<int> myList;
      HashTable<int> myHashTable;
   
    while(promptUser)
    {    
        int i;
        //seed generator
        srand(11111111);    
        int t1 = clock();
        for (i = 0; i < 40000; i ++)
        {
            myBST.insert(rand());
        }
       
        int t2 = clock();
        srand(11111111);    
        int t3= clock();
        for (i = 0; i < 40000; i ++)
        {
            myList.insertEnd(rand());
        }
       
        int t4 = clock();
        cout << "How many tests would you like to perform? (Enter 'Q' to quit)" << endl;
       
        //test search
        cin.getline(userSelection, 10);              
       
        //Converts the selection to a number to test
        int numTests = atoi(userSelection);
        if(numTests > 0)
        {
            cout << endl << "Performing tests: " << endl << endl;
           
            srand(33333333);     // take another seed number or all numbers would be found
            for(i = 0; i < numTests; i ++)
            {
                //Search array new generated random number
                ran = rand();
                if (myBST.search(ran, numCompares))
                {
                    foundBST++;
                    compFoundBST += numCompares;
                }
                else
                {
                    notFoundBST++;
                    compNotFoundBST += numCompares;
                }
                cout << ran << endl;
                //resets the numCompares counter
                numCompares = 0;
            }
                  srand(33333333);     // take another seed number or all numbers would be found
            for(i = 0; i < numTests; i ++)
            {
                //Search array new generated random number
                ran = rand();
                if (myList.search(ran, numCompares))
                {
                    foundmyList++;
                    compFoundmyList += numCompares;
                }
                else
                {
                    notFoundmyList++;
                    compNotFoundmyList += numCompares;
                }
                cout << ran << endl;
                //resets the numCompares counter
                numCompares = 0;
            }
                  srand(33333333);     // take another seed number or all numbers would be found
            for(i = 0; i < numTests; i ++)
            {
                //Search array new generated random number
                ran = rand();
                if (myHashTable.search(ran, numCompares))
                {
                    foundmyHashTable++;
                    compFoundmyHashTable += numCompares;
                }
                else
                {
                    notFoundmyList++;
                    compNotFoundmyHashTable += numCompares;
                }
                cout << ran << endl;
                //resets the numCompares counter
                numCompares = 0;
            }
           
            counter = numTests;

            avgFoundBST = ((foundBST  * 100 + counter / 2)/ counter);
            avgNotFoundBST = ((notFoundBST * 100  + counter / 2)/ counter);

                  avgFoundmyList = ((foundmyList  * 100 + counter / 2)/ counter);
            avgNotFoundmyList = ((notFoundmyList * 100  + counter / 2)/ counter);
           
            cout << endl << "Binary Search Tree" << endl;
            cout << "Number Found " << foundBST << endl;
            cout << "Number Not Found " << notFoundBST << endl;
            cout << "Ttl Compares (Found) " << compFoundBST << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundBST << endl;
            cout << "Avg Compares (Found) " << avgFoundBST << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundBST << endl << endl;    
            cout << "Tree Depth        : " << myBST.depth() << endl;
            cout << "Tree Node Count   : " << myBST.count() << endl << endl;

                  cout << "Linked List" << endl;
            cout << "Number Found " << foundmyList << endl;
            cout << "Number Not Found " << notFoundmyList << endl;
            cout << "Ttl Compares (Found) " << compFoundmyList << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundmyList << endl;
            cout << "Avg Compares (Found) " << avgFoundmyList << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundmyList << endl << endl;    
                  cout << "Linked List Count : " << myList.getLength() << endl << endl;

                  cout << "Hash Table" << endl;
            cout << "Number Found " << foundmyHashTable << endl;
            cout << "Number Not Found " << notFoundmyHashTable << endl;
            cout << "Ttl Compares (Found) " << compFoundmyHashTable << endl;
            cout << "Ttl Compares (Not Found) " << compNotFoundmyHashTable << endl;
            cout << "Avg Compares (Found) " << avgFoundmyHashTable << endl;
            cout << "Avg Compares (Not Found) " << avgNotFoundmyHashTable << endl << endl;    
            cout << "Hash Table Capacity: " << myHashTable.getCapacity() << endl;  
            cout << "Hash Table Size: " << myHashTable.getCount() << endl;
            //cout << "Hash Table Load Factor: " << myHashTable.? << endl << endl;
        }
       
        else if(toupper(userSelection[0]) == 'Q')
        {
            promptUser = false;
        }
       
        //invalid user input
        else
        {    
            cout << "Enter a number greater than zero" << endl;
            cout << "Q to quit" << endl;
            promptUser = true;
        }
    }
}
0
 
itsmeandnobodyelseCommented:
>> HashTable(unsigned maxCapacity);

That is the (only) constructor. It takes a unsigned int. So, you have to define variables  like that:

    HashTable<int> myHashTable(5000);    // the size of the hash  table is 5000 slots

You don't need to post all code with each comment. It's easier if you only post the changes you made.

Regards, Alex
0
 
jandhbAuthor Commented:
I made those changes - HashTable<int> myHashTable(5000);

I'm getting error C2065: 'array' : undeclared identifier on this line...

if(!array) in HashTable.h constructor()


0
 
itsmeandnobodyelseCommented:
>> I'm getting error C2065: 'array' : undeclared identifier on this line...

'array' is the name of old HashRecord array. ou have to remove all occurences of HashRecord and of enum Record State (OCCUPIED, EMPTY, DELETED) as well. The new array is called 'hashArray' and its elements are LinkedList items.


0
 
jandhbAuthor Commented:
I made the changes to hashtable.h. Can you tell me if all the occurences have been changed correctly?

#ifndef HASH_TABLE_INCLUDED
#define HASH_TABLE_INCLUDED

//-- INCLUDES -----------------------------------------------------------------
#include <iostream>
#include <new>
using namespace std;



///////////////////////////////////////////////////////////////////////////////
// HashTable
//
// The following is a basic implementation of a HashTable in C++.  A HashTable
// is a structure where lookups are near instantanious, but you pay a price
// in terms of the fact that your dataset is unordered.
//
// This table only works for basic types (int, char, double, long, etc).
///////////////////////////////////////////////////////////////////////////JMMH
template <typename TYPE>
class HashTable
{
      // the possible state values that a record can be in
      //enum RecordState { EMPTY, OCCUPIED, DELETED };

      // the basic hash table record
      // TODO: Modify this structure so it just stores a linked list of TYPE
      /*struct HashRecord
      {
            TYPE        data;                  // piece of data in this record
            RecordState state;                  // state of the record

            // add a new item record with a hash entry of OCCUPIED
            HashRecord(const TYPE & newData)
            {
                  data = newData;
                  state = OCCUPIED;
            }

            // default constructor makes sure state is EMPTY
            HashRecord()
            {
                  state = EMPTY;
            }
      };*/

      // the actual ptr to the dynamic array
      //HashRecord * array;
      unsigned     capacity;
      unsigned     count;

      LinkedList<TYPE>*  hashArray;

      // private method to find hash location
      int generateHashLocation(const TYPE & item) const
      {
            return item % capacity;            // simple mod hash function
      }

public:
      // constructor to create the hash table at a given capacity
      //takes an unsigned int
      HashTable(unsigned maxCapacity);

      // gets for capacity and count
      unsigned getCapacity() const            { return capacity;  }
      unsigned getCount() const                  { return count;            }

      // method to add to hash table.  Returns false if no capacity remaining
      bool add(const TYPE & newItem);

      // method to remove from hash table.  Returns false if item not existing
      bool remove(const TYPE & oldItem);

      // method to retrieve from the hash table.  Returns false if not found
       bool search(const TYPE & searchItem, int& numCompares) const;

      // display prints contents of table
      void display(ostream & out);

      // copy constructor
      HashTable(const HashTable<TYPE> & oldTable);

      // assignment operator
      const HashTable<TYPE> & operator = (const HashTable<TYPE> & oldTable);

      // destructor
      ~HashTable();

};


// constructor to create the hash table at a given capacity
template <typename TYPE>
HashTable<TYPE>::HashTable(unsigned maxCapacity)
      : hashArray(NULL), count(0), capacity(0)
{
      // will call default constructor on each record, setting them to
      // EMPTY
      //array = new HashRecord[maxCapacity];

      hashArray = new LinkedList<TYPE> [maxCapacity];

      // make sure no errors
      if(!hashArray)
      {
            cerr << "Could not create hash table with size " << maxCapacity << endl;
      }

      else
      {
            capacity = maxCapacity;
      }
}



// method to add to hash table.  Returns false if no capacity remaining
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will insert it into the list
// at the home location if it does not already exist.
/*template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
      if(count < capacity)
      {
            int loc = generateHashLocation(newItem);      // natural loc

            // linear probe.  If array is occupied at hash location, increment
            // the probe.  Could also do quadratic probe here.
            while(array[loc].state == OCCUPIED)
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge
            }

            array[loc].state = OCCUPIED;
            array[loc].data  = newItem;
            count++;
            return true;
      }

      // no space found, can't insert
      return false;
}*/
template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
   int loc = generateHashLocation(newItem);     // natural loc
   hashArray[loc].insertEnd(newItem);
   count++;
   return true;
}




// method to remove from hash table.  Returns false if item not existing
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will delete the item in the
// linked list if it exists.
template <typename TYPE>
bool HashTable<TYPE>::remove(const TYPE & oldItem)
{
      bool found = false;

      int homeloc = generateHashLocation(oldItem);      // natural loc
      int loc = homeloc;

      // linear probe.  If array is occupied at hash location, increment
      // the probe.  Could also do quadratic probe here.
      while((hashArray[loc].state != EMPTY) && !found)
      {
            // check if item we want
            if((hashArray[loc].data == oldItem)      && (hashArray[loc].state == OCCUPIED))
            {
                  found = true;
                  hashArray[loc].state = DELETED;
                  count--;
            }
            else
            {
                  loc = (loc+1) % capacity;      // wrap around if goes off edge

                  // if we loop all the way around back to home loc, stop
                  if(loc == homeloc)
                        break;
            }
      }

      // no space found, can't insert
      return found;
}



// method to retrieve from the hash table.  Returns false if not found
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Search the linked list
// and return true if it is found
template <typename TYPE>
bool HashTable<TYPE>::search(const TYPE & searchItem, int& numCompares) const
{
     int loc       = generateHashLocation(searchItem);     // natural loc
     bool found = hashArray[loc].search(searchItem, numCompares);
     numCompares++;
     return found;
}


// display prints contents of table
// -----------
// TODO: Update to use chaining (close addressing).  Print
// all linked lists in the cells with linked list size > 0
template <typename TYPE>
void HashTable<TYPE>::display(ostream & out)
{
      for(unsigned i=0; i<capacity; i++)
      {
            if(hashArray[i].state == OCCUPIED)
            {
                  out << i << ": " << hashArray[i].data << endl;
            }
      }
}



// copy constructor
template <typename TYPE>
HashTable<TYPE>::HashTable(const HashTable<TYPE> & oldTable)
      : hashArray(NULL), size(0), capacity(0)
{
      //array = new HashRecord[oldTable.capacity];

      // if allocation failed, print error
      if(!hashArray)
      {
            cerr << "Could not create copy of hash table of size " 
                  << oldTable.capacity << endl;
      }

      // otherwise copy the table
      else
      {
            size = oldTable.size;
            capacity = oldTable.capacity;

            for(unsigned i = 0; i<capacity; i++)
            {
                  hashArray[i] = oldTable.hashArray[i];
            }
      }
}



// assignment operator
template <typename TYPE>
const HashTable<TYPE> & HashTable<TYPE>::operator = (const HashTable<TYPE> & oldTable)
{
      if(this != &oldTable)
      {
            // clear old mem
            delete [] hashArray;
            count = capacity = 0;

            //array = new HashRecord[oldTable.capacity];

            // if allocation failed, print error
            if(!hashArray)
            {
                  cerr << "Could not create copy of hash table of size " 
                        << oldTable.capacity << endl;
            }

            // otherwise copy the table
            else
            {
                  size = oldTable.size;
                  capacity = oldTable.capacity;

                  for(unsigned i = 0; i<capacity; i++)
                  {
                        hashArray[i] = oldTable.hashArray[i];
                  }
            }
      }

      return *this;
}



// destructor
template <typename TYPE>
HashTable<TYPE>::~HashTable()
{
      delete [] hashArray;
}



#endif
0
 
jandhbAuthor Commented:
I ran the program and did three tests. The output for the HashTable is 0 besides the count. Here is the output....What needs to be changed so that we get accurate output for the HashTable?

How many tests would you like to perform? (Enter 'Q' to quit)
3

Performing tests:

30150
16855
13384
30150
16855
13384
30150
16855
13384

Binary Search Tree
Number Found 2
Number Not Found 1
Ttl Compares (Found) 41
Ttl Compares (Not Found) 26
Avg Compares (Found) 67
Avg Compares (Not Found) 33

Tree Depth        : 34
Tree Node Count   : 23072

Linked List
Number Found 2
Number Not Found 4
Ttl Compares (Found) 36781
Ttl Compares (Not Found) 40000
Avg Compares (Found) 67
Avg Compares (Not Found) 133

Linked List Count : 40000

Hash Table
Number Found 0
Number Not Found 0
Ttl Compares (Found) 0
Ttl Compares (Not Found) 3
Avg Compares (Found) 0
Avg Compares (Not Found) 0

Hash Table Capacity: 5000
Hash Table Size: 0
How many tests would you like to perform? (Enter 'Q' to quit)
0
 
itsmeandnobodyelseCommented:
>> Ttl Compares (Not Found) 3

The Hashtable contains no entries.

You have to insert the same set of numbers to HashTable as you did it for the other collections.

        ...
        int t4 = clock();
        srand(11111111);    
        int t5= clock();
        for (i = 0; i < 40000; i ++)
        {
            myHashTable.add(rand());
        }
       
        int t6 = clock();
        ...


Regards, Alex
0
 
jandhbAuthor Commented:
Does this now seem like accurate output?


How many tests would you like to perform? (Enter 'Q' to quit)
3

Performing tests:

30150
16855
13384
30150
16855
13384
30150
16855
13384

Binary Search Tree
Number Found 2
Number Not Found 1
Ttl Compares (Found) 41
Ttl Compares (Not Found) 26
Avg Compares (Found) 67
Avg Compares (Not Found) 33

Tree Depth        : 34
Tree Node Count   : 23072

Linked List
Number Found 2
Number Not Found 2
Ttl Compares (Found) 36781
Ttl Compares (Not Found) 40000
Avg Compares (Found) 67
Avg Compares (Not Found) 67

Linked List Count : 40000

Hash Table
Number Found 2
Number Not Found 0
Ttl Compares (Found) 13
Ttl Compares (Not Found) 5
Avg Compares (Found) 67
Avg Compares (Not Found) 0

Hash Table Capacity: 5000
Hash Table Size: 40000
How many tests would you like to perform? (Enter 'Q' to quit)
0
 
jandhbAuthor Commented:
Can you help me to understand a couple of things:

1. How can the capacity be 5000 and the size 40000? Maybe I have it backwards, but isn't the capacity the max amount it can hold?

2. How would I get the load factor #? In other words, say if the capacity was 40000 and the size 30500 then the load capacity would be 76.25 %. I need to display this number after the size.

Thanks.
0
 
itsmeandnobodyelseCommented:
>> How can the capacity be 5000 and the size 40000? Maybe I have it backwards, but isn't the capacity the max amount it can hold?

Capacity maybe is the wrong word after we moved from HashRecord to LinkedList. 5000 is the number of 'slots' our HashTable has, but any slot contains a LinkedList that had an unlimited capacity.

>> How would I get the load factor #

No, as there is no maximum capacity there is no load factor. You haven't a load factor for LInkedList and BST. You could only measure how many slots are occupied or free.

Regards, Alex
0
 
jandhbAuthor Commented:
>> You could only measure how many slots are occupied or free.

This is what I would like to do.

Would this be done in the main() or within some other function?  
0
 
itsmeandnobodyelseCommented:
I would add a member variable 'int usedSlots' to HashTable. Initialize it to 0 in constructor. Increment it in HashTable::add whenever hashArray[loc].empty() before inserting the new value. In HashTable::remove you have to decrement the value if hashArray[loc].empty() after removing the value.

Note, the relation between ocuupied slots and free slots give you a measure how good the hash algorithm works. In case of int and rand() numbers it is most likely that nearly all of your slots are occupied when inserting 8 times more integers than available slots. A bad hash algorithm for strings may result much different. Compared with BST a HashTable needs more space, as you have to count all empty slots where in a BST all nodes are occupied. But, a BST must be balanced to be faster than a HashTable of equivalent size while a HashTable using a good hash algorithm ( a algorithm is good if all slots have same statistical chance to get used ) is 'balanced' automatically. A BST is balanced if the depth of the tree is about log2 of the number of nodes. If you would add the sequence 1, 2, ... n to a BST you would get a most unbalanced tree that is equivalent to a linked list, as only the right pointer of all nodes points to the 'next' node.

Regards, Alex
0
 
jandhbAuthor Commented:
Can you show me how to implement this, please...

My goal is to have a statement in main() that says...

cout << "Hash Table Load Factor: " << myHashTable.? << endl << endl;
0
 
itsmeandnobodyelseCommented:
As i told you a 'Load Factor' made sense when using a HashTable with a maximum capacity as it was with HashRecord. When a slot was occupied, old HashTable had to use one of the other free slots (though these 'belonged' to a different hash code). You could add entries as long there were still free slots. However, when there were only a few free slots, 'adding' a new item could last very long as it was most likely that most checks of emptyness would fail.

A HashTable using LinkedList array was much different. Here a slot will only be shared to items that have the same hash code. In case of 40000 random numbers and 5000 slots, each slot will have at least one entry and an average of 8 entries. The maximum entries wouldn't be greater than 16 entries, normally. A 'Load Factor'  should always show 100 % as any slot was used. So, either you have to give a new definition what 'Load' is for a dynamically growing HashTable (e. g.  a  slot is 'loaded' if it contains 5 items or more) or you have to decrease the relation between count() and capacity(). If - for example - you are inserting only 10000 numbers, there is a good chance that there are some slots unused (in fact it is 14% unused, see below).

1. I made changes in main:

- decreased number of entries
- output of LoadFactor

   ....
        int i;
        //seed generator
        srand(11111111);    
        int t1 = clock();
        for (i = 0; i < 10000; i ++)
        {
            myBST.insert(rand());
        }
       
        int t2 = clock();
        srand(11111111);    
        int t3= clock();
        for (i = 0; i < 10000; i ++)
        {
            myList.insertEnd(rand());
        }
       
        int t4 = clock();
        srand(11111111);    
        int t5= clock();
        for (i = 0; i < 10000; i ++)
        {
            myHashTable.add(rand());
        }
       
        int t6 = clock();

        ...
    cout << "Hash Table Load Factor: " 
          << ((myHashTable.getUsedSlots()*100)/myHashTable.getCapacity())  
          << endl << endl;


2.  I made changes in HashTable:

- added member slotsUsed
- added member function getUsedSlots
- made corrections for remove, copy constructor and operator =
- implemented decrementin and incrementing of slotsUsed member

#ifndef HASH_TABLE_INCLUDED
#define HASH_TABLE_INCLUDED

//-- INCLUDES -----------------------------------------------------------------
#include <iostream>
#include <new>
using namespace std;

///////////////////////////////////////////////////////////////////////////////
// HashTable
//
// The following is a basic implementation of a HashTable in C++.  A HashTable
// is a structure where lookups are near instantanious, but you pay a price
// in terms of the fact that your dataset is unordered.
//
// This table only works for basic types (int, char, double, long, etc).
///////////////////////////////////////////////////////////////////////////JMMH
template <typename TYPE>
class HashTable
{
     // the possible state values that a record can be in
     //enum RecordState { EMPTY, OCCUPIED, DELETED };

     unsigned     capacity;
     unsigned     count;
     unsigned     slotsUsed;

     // array of LinkedList items
     LinkedList<TYPE>*  hashArray;

     // private method to find hash location
     int generateHashLocation(const TYPE & item) const
     {
          return item % capacity;          // simple mod hash function
     }

public:
     // constructor to create the hash table at a given capacity
     //takes an unsigned int
     HashTable(unsigned maxCapacity);

     // gets for capacity and count
     unsigned getCapacity() const          { return capacity;  }
     unsigned getCount() const             { return count;     }
     unsigned getUsedSlots() const         { return slotsUsed; }

     // method to add to hash table.  Returns false if no capacity remaining
     bool add(const TYPE & newItem);

     // method to remove from hash table.  Returns false if item not existing
     bool remove(const TYPE & oldItem);

     // method to retrieve from the hash table.  Returns false if not found
      bool search(const TYPE & searchItem, int& numCompares) const;

     // display prints contents of table
     void display(ostream & out);

     // copy constructor
     HashTable(const HashTable<TYPE> & oldTable);

     // assignment operator
     const HashTable<TYPE> & operator = (const HashTable<TYPE> & oldTable);

     // destructor
     ~HashTable();

};


// constructor to create the hash table at a given capacity
template <typename TYPE>
HashTable<TYPE>::HashTable(unsigned maxCapacity)
     : hashArray(NULL), count(0), capacity(0), slotsUsed(0)
{
     // will call default constructor on each record, setting them to
     // EMPTY
     //array = new HashRecord[maxCapacity];

     hashArray = new LinkedList<TYPE> [maxCapacity];

     // make sure no errors
     if(!hashArray)
     {
          cerr << "Could not create hash table with size " << maxCapacity << endl;
     }

     else
     {
          capacity = maxCapacity;
     }
}



// method to add to hash table.  Returns false if no capacity remaining
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will insert it into the list
// at the home location if it does not already exist.
/*template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
     if(count < capacity)
     {
          int loc = generateHashLocation(newItem);     // natural loc

          // linear probe.  If array is occupied at hash location, increment
          // the probe.  Could also do quadratic probe here.
          while(array[loc].state == OCCUPIED)
          {
               loc = (loc+1) % capacity;     // wrap around if goes off edge
          }

          array[loc].state = OCCUPIED;
          array[loc].data  = newItem;
          count++;
          return true;
     }

     // no space found, can't insert
     return false;
}*/
template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
    int loc = generateHashLocation(newItem);     // natural loc
    // increment used slots if list was empty before
    if (hashArray[loc].empty())
        slotsUsed++;
    hashArray[loc].insertEnd(newItem);
    count++;
    return true;
}




// method to remove from hash table.  Returns false if item not existing
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Instead of checking
// to see if the cell is occupied, you will delete the item in the
// linked list if it exists.
template <typename TYPE>
bool HashTable<TYPE>::remove(const TYPE & oldItem)
{
     int loc = generateHashLocation(oldItem);     // natural loc

     bool found = hashArray[loc].remove(oldItem);

     // decrement used slots if found and list got empty
     if (found && hashArray[loc].empty())
         slotsUsed--;
     
     return found;
}



// method to retrieve from the hash table.  Returns false if not found
// -----------
// TODO: Update to use chaining (close addressing).  This means that the
// home location is the law and where it must go.  Search the linked list
// and return true if it is found
template <typename TYPE>
bool HashTable<TYPE>::search(const TYPE & searchItem, int& numCompares) const
{
     int loc       = generateHashLocation(searchItem);     // natural loc
     bool found = hashArray[loc].search(searchItem, numCompares);
     numCompares++;
     return found;
}


// display prints contents of table
// -----------
// TODO: Update to use chaining (close addressing).  Print
// all linked lists in the cells with linked list size > 0
template <typename TYPE>
void HashTable<TYPE>::display(ostream & out)
{
     for(unsigned i=0; i<capacity; i++)
     {
          if(hashArray[i].state == OCCUPIED)
          {
               out << i << ": " << hashArray[i].data << endl;
          }
     }
}



// copy constructor
template <typename TYPE>
HashTable<TYPE>::HashTable(const HashTable<TYPE> & oldTable)
     : hashArray(NULL), size(0), capacity(0)
{
     //array = new HashRecord[oldTable.capacity];

     // if allocation failed, print error
     if(!hashArray)
     {
          cerr << "Could not create copy of hash table of size " 
               << oldTable.capacity << endl;
     }

     // otherwise copy the table
     else
     {
          size = oldTable.size;
          capacity = oldTable.capacity;

          for(unsigned i = 0; i<capacity; i++)
          {
               if (!oldTable.hashArray[i].empty())
               {
                   hashArray[i] = oldTable.hashArray[i];
                   slotsUsed++;
               }
          }
     }
}



// assignment operator
template <typename TYPE>
const HashTable<TYPE> & HashTable<TYPE>::operator = (const HashTable<TYPE> & oldTable)
{
     if(this != &oldTable)
     {
          // clear old mem
          delete [] hashArray;
          count = capacity = slotsUsed = 0;

          hashArray = new LinkedList[oldTable.capacity];

          // if allocation failed, print error
          if(!hashArray)
          {
               cerr << "Could not create copy of hash table of size " 
                    << oldTable.capacity << endl;
          }

          // otherwise copy the table
          else
          {
               size = oldTable.size;
               capacity = oldTable.capacity;

               for(unsigned i = 0; i<capacity; i++)
               {
                   if (!oldTable.hashArray[i].empty())
                   {
                       hashArray[i] = oldTable.hashArray[i];
                       slotsUsed++;
                   }
               }
          }
     }
     return *this;
}

// destructor
template <typename TYPE>
HashTable<TYPE>::~HashTable()
{
     delete [] hashArray;
}

#endif


3. I made changes to LinkedList:

- changed 'void remove' to 'bool remove' as i needed information whether remove(..)
  did find an item to remove or not
- added operator= () function to correct copy constructor and operator= of HashTable
  (before, the pointers of nodes of LinkedList were copied physically, so if you would
   delete a node, there could be another HashTable that still had a pointer to an already
   deleted node, what leads to an access violation).

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

//include files
#include <iostream>

using namespace std;

template <typename Generic>
class LinkedList;

template <typename Generic>
class Node
{
    Generic          data;
    Node<Generic>*   next;

    friend class LinkedList<Generic>;
};

//declaration of LinkedList class
template <typename Generic>
class LinkedList
{
//public member functions
public:
     //constructor
     LinkedList();
     //destructor
     ~LinkedList();

     void insertFront(const Generic &item);
     void insertEnd(const Generic & item);
     void display(std::ostream &outStream = std::cout) const;
     bool remove(const Generic &item);
     void deleteList();
     void removeFirstNode();

     int getLength() const;
     Generic getFirstValue() const;
     bool search(const Generic &item, int& numCompares) const;
     bool empty() const;
     bool full() const;

     LinkedList& operator= (const LinkedList& ll);

//private data members
private:
     //first element in linked list
     Node<Generic> *first;
     //last element in linked list
     Node<Generic> *last;
};


//constructor
//called when the class instance is created
//sets up initial values for the class data members
//initial first pointer to NULL
template <typename Generic>
LinkedList<Generic>::LinkedList() : first(0), last(0)
{

}

//destructor
//called when the class instance is destroyed
template <typename Generic>
LinkedList<Generic>::~LinkedList()
{
     //cleans up leftover memory
     deleteList();
}

//insertFront
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the very beginning of the list
template <typename Generic>
void LinkedList<Generic>::insertFront(const Generic &item)
{
     //create a pointer to a node
     Node *newNode;

     //allocate memory for the new node
     newNode = new Node;

     //set the newNode's value
     newNode->data = item;

     //point the new node
     //same node that is currently the beginning of the list
     newNode->next = first;

     //change the beginning of the list to point to the newNode
     first = newNode;
}

//

//display
//accepts outStream, a file or cout stream to output data to
//always displays all of the data in the linked list
//either to a file or  to the screen
template <typename Generic>
void LinkedList<Generic>::display(ostream &outStream) const
{
     //create a pointer to a node
     Node *current = first;

     //loop through each node in the list
     while (current != 0)
     {
          //send data to the output stream
          outStream << current->data << endl;

          //move to the next node
          current = current->next;
     }
}

//remove
//accepts item, a Generic data type to search and remove from the list
//searches for the item passed to it and removes that node from the list
template <typename Generic>
bool LinkedList<Generic>::remove(const Generic &item)
{
     bool found = false;
     //check if the list is empty
     if (!empty())
     {
          //create a pointer to a node
          Node *current = first;

          //check if first item is what is being searched for
          if (current->data == item)
          {
               //set the first node to point to the second node
               first = current->next;

               //deallocate first node
               delete current;
               found = true;
          }
          else
          {
               //create a pointer to a node
               Node *previous = current;

               //move current to the next node
               current = current->next;

               //loop through nodes until data is found
               //or end of file has been reached
               while ( (current != 0) && (current->data != item) )
               {
                    //move each pointer to the next node
                    current = current->next;
                    previous = previous->next;
               }

               //check if either previous or current is null
               if ( (current != 0) && (previous != 0) )
               {
                    //set the previous node to point to the node following current
                    previous->next = current->next;

                    //deallocate the node searched for
                    delete current;
                    found = true;
               }
          }
     }
     return found;
}

//deleteList
//deallocates all nodes in the list
//sets the first pointer to NULL
template <typename Generic>
void LinkedList<Generic>::deleteList()
{
     //create pointers to a node
     Node<Generic> *current = first;
     Node<Generic> *previous;

     //loop through all nodes in the list
     while (current != 0)
     {
          //set previous to the current node
          previous = current;

          //set current to the next node
          current = current->next;

          //deallocate the previous node
          delete previous;
     }

     //reset beginning of list to NULL
     first = 0;
}

//getLength
//counts all nodes in the list and returns the count
template <typename Generic>
int LinkedList<Generic>::getLength() const
{
     //create a pointer to a node
     Node<Generic> *current = first;

     //create an int variable to hold the total
     int total = 0;

     //loop through all nodes in the list
     while (current != 0)
     {
          //increment total by 1 and move to next node
          ++total;
          current = current->next;
     }

     //return the total
     return total;
}


//empty
//returns a true value if the list is empty
//false if the list has nodes in it
template <typename Generic>
bool LinkedList<Generic>::empty() const
{
     //return true if the first is NULL
     return (first == 0);
}

//full
//this will always return a false value
//this linked list version has virtually unlimited memory
template <typename Generic>
bool LinkedList<Generic>::full() const
{
     return false;
}

//removeFirstNode
//removes first node from the list
template <typename Generic>
void LinkedList<Generic>::removeFirstNode()
{
     //check if the list is empty
     if (!empty())
     {
          //create a pointer to a node
          Node *current = first;

          //point the beginning of the list to the second node
          first = current->next;

          //deallocate the memory for  current
          delete current;
     }
}

//getFirstValue
//returns the value of the first node in the list
template <typename Generic>
Generic LinkedList<Generic>::getFirstValue() const
{
     //this will not work if list is empty
     return first->data;
}

//insertEnd
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the end of the list
template <typename Generic>
void LinkedList<Generic>::insertEnd(const Generic & item)
{
    //create pointer to a node
    Node<Generic>* newNode;
   
    //allocate memory for the newNode
    newNode = new Node<Generic>;
   
    //initialize the node's members
    newNode->data = item;
    newNode->next = 0;
   
    //check to see if there are nodes in the list
    if (last == 0)
    {
        //set the beginning of the list to point at the new node
        first = last = newNode;
    }
    else
    {
        //set the last node's next value to the new node
        last->next = newNode;
        last       = newNode;
    }
}



template <typename Generic>
bool LinkedList<Generic>::search(const Generic &item, int& numCompares) const
{
     //create a pointer to a node
     Node<Generic> *current = first;

     //create a flag to tell if the value was found
     bool found = false;

     //loop through each node until the end of the list or the value is found
     while ( (current != 0) && (current->data != item) )
     {
          //move to the next node
          current = current->next;
          numCompares++;
     }

     //if current is not null then the end of the list was not reached
     if (current != 0)
     {
          //value was found
          found = true;
          numCompares++;
     }

     //return the found flag
     return found;
}

template <typename Generic>
LinkedList<Generic>& LinkedList<Generic>::operator= (const LinkedList<Generic>& ll)
{
    if (&ll != this)
    {
        deleteList();
        Node<Generic>* node = ll.first;
        while (node != NULL)
        {
            insertEnd(node->data);
            node = node->next;
        }
    }
    return *this;
}

//end define
#endif

Regards, Alex
0
 
jandhbAuthor Commented:
For output of 3 numbers would this be correct? My only question is for Ttl Compares (Not Found) 6 for Hash Table. If the number onot found was 0 how can the number of compares for this number be 6?


How many tests would you like to perform? (Enter 'Q' to quit)
3

Performing tests:

30150
16855
13384
30150
16855
13384
30150
16855
13384

Binary Search Tree
Number Found 1
Number Not Found 2
Ttl Compares (Found) 20
Ttl Compares (Not Found) 36
Avg Compares (Found) 33
Avg Compares (Not Found) 67

Tree Depth        : 30
Tree Node Count   : 8633

Linked List
Number Found 1
Number Not Found 4
Ttl Compares (Found) 5875
Ttl Compares (Not Found) 20000
Avg Compares (Found) 33
Avg Compares (Not Found) 133

Linked List Count : 10000

Hash Table
Number Found 1
Number Not Found 0
Ttl Compares (Found) 3
Ttl Compares (Not Found) 6
Avg Compares (Found) 33
Avg Compares (Not Found) 0

Hash Table Capacity: 5000
Hash Table Size: 10000
Hash Table Load Factor: 86

How many tests would you like to perform? (Enter 'Q' to quit)
0
 
jandhbAuthor Commented:
Thank you for your help.
0
 
itsmeandnobodyelseCommented:
>> If the number onot found was 0 how can the number of compares for this number be 6?

You are incrementing

         notFoundmyList++;

and *not*

        notFoundmyHashTable++;

Regards, Alex
0
 
jandhbAuthor Commented:
Alex,

I just posted a question here http://experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_21225656.html
on Comparing Sorts. I would like your help if you have the time, thanks.
0

Featured Post

Prep for the ITIL® Foundation Certification Exam

December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.

  • 20
  • 13
Tackle projects and never again get stuck behind a technical roadblock.
Join Now