The goal of this assignment is to reinforce hash tables in C++

Question:

The goal of this assignment is to reinforce hash tables in C++. Specifically, the assignment is to implement the author’s table2 using the STL list class instead of the author’s list class. The table2.h and the test file testtab2.cpp will be provided for you. You do not need to implement the overloaded = function for table 2. The rest of the functions need to be implemented.

table2.h

// FILE: table2.h
// TEMPLATE CLASS PROVIDED: Table<RecordType>
// This class is a container template class for a Table of records.
// The template parameter, RecordType, is the data type of the records in the
// Table. It may any type with a default constructor, a copy constructor,
// an assignment operator, and an integer member variable called key.
//
// CONSTRUCTOR for the Table<RecordType> template class:
// Table( )
// Postcondition: The Table has been initialized as an empty Table.
//
// MODIFICATION MEMBER FUNCTIONS for the Table<RecordType> class:
// void insert(const RecordType& entry)
// Precondition: entry.key >= 0. Also if entry.key is not already a key in
// the table, then the Table has space for another record
// (i.e., size( ) < CAPACITY).
// Postcondition: If the table already had a record with a key equal to
// entry.key, then that record is replaced by entry. Otherwise, entry has
// been added as a new record of the Table.
//
// void remove(int key)
// Postcondition: If a record was in the Table with the specified key, then
// that record has been removed; otherwise the table is unchanged.
//
// CONSTANT MEMBER FUNCTIONS for the Table<RecordType> class:
// bool is_present(const Item& target) const
// Postcondition: The return value is true if there is a record in the
// Table with the specified key. Otherwise, the return value is false.
//
// void find(int key, bool& found, RecordType& result) const
// Postcondition: If a record is in the Table with the specified key, then
// found is true and result is set to a copy of the record with that key.
// Otherwise found is false and the result contains garbage.
//
// size_t size( ) const
// Postcondition: Return value is the total number of records in the
// Table.
//
// VALUE SEMANTICS for the Table<RecordType> template class:
// Assignments and the copy constructor may be used with Table objects.
//
// DYNAMIC MEMORY USAGE by the Table<RecordType> template class:
// If there is insufficient dynamic memory, then the following functions
// can call new_handler: the copy constructor, insert, the assignment
// operator.

#ifndef TABLE2_H
#define TABLE2_H
#include <cstdlib> // Provides size_t
#include <list> // Provides the STL list class

namespace main_savitch_12B

{
template <class RecordType>
class table
{
public:
// MEMBER CONSTANT -- See Appendix E if this fails to compile.
static const std::size_t TABLE_SIZE = 811;
// CONSTRUCTORS AND DESTRUCTOR
table( );
table(const table& source);
~table( );
// MODIFICATION MEMBER FUNCTIONS
void insert(const RecordType& entry);
void remove(int key);
// CONSTANT MEMBER FUNCTIONS
void find(int key, bool& found, RecordType& result) const;
bool is_present(int key) const;
std::size_t size( ) const { return total_records; }
private:
std::list<RecordType> data[TABLE_SIZE]; //
std::size_t total_records;
// HELPER MEMBER FUNCTION
std::size_t hash(int key) const;
};
}

#include "table2.template" // Include the implementation

#endif

testtab2

// FILE: table2.h
// TEMPLATE CLASS PROVIDED: Table<RecordType>
// This class is a container template class for a Table of records.
// The template parameter, RecordType, is the data type of the records in the
// Table. It may any type with a default constructor, a copy constructor,
// an assignment operator, and an integer member variable called key.
//
// CONSTRUCTOR for the Table<RecordType> template class:
// Table( )
// Postcondition: The Table has been initialized as an empty Table.
//
// MODIFICATION MEMBER FUNCTIONS for the Table<RecordType> class:
// void insert(const RecordType& entry)
// Precondition: entry.key >= 0. Also if entry.key is not already a key in
// the table, then the Table has space for another record
// (i.e., size( ) < CAPACITY).
// Postcondition: If the table already had a record with a key equal to
// entry.key, then that record is replaced by entry. Otherwise, entry has
// been added as a new record of the Table.
//
// void remove(int key)
// Postcondition: If a record was in the Table with the specified key, then
// that record has been removed; otherwise the table is unchanged.
//
// CONSTANT MEMBER FUNCTIONS for the Table<RecordType> class:
// bool is_present(const Item& target) const
// Postcondition: The return value is true if there is a record in the
// Table with the specified key. Otherwise, the return value is false.
//
// void find(int key, bool& found, RecordType& result) const
// Postcondition: If a record is in the Table with the specified key, then
// found is true and result is set to a copy of the record with that key.
// Otherwise found is false and the result contains garbage.
//
// size_t size( ) const
// Postcondition: Return value is the total number of records in the
// Table.
//
// VALUE SEMANTICS for the Table<RecordType> template class:
// Assignments and the copy constructor may be used with Table objects.
//
// DYNAMIC MEMORY USAGE by the Table<RecordType> template class:
// If there is insufficient dynamic memory, then the following functions
// can call new_handler: the copy constructor, insert, the assignment
// operator.

#ifndef TABLE2_H
#define TABLE2_H
#include <cstdlib> // Provides size_t
#include <list> // Provides the STL list class

namespace main_savitch_12B

{
template <class RecordType>
class table
{
public:
// MEMBER CONSTANT -- See Appendix E if this fails to compile.
static const std::size_t TABLE_SIZE = 811;
// CONSTRUCTORS AND DESTRUCTOR
table( );
table(const table& source);
~table( );
// MODIFICATION MEMBER FUNCTIONS
void insert(const RecordType& entry);
void remove(int key);
// CONSTANT MEMBER FUNCTIONS
void find(int key, bool& found, RecordType& result) const;
bool is_present(int key) const;
std::size_t size( ) const { return total_records; }
private:
std::list<RecordType> data[TABLE_SIZE]; //
std::size_t total_records;
// HELPER MEMBER FUNCTION
std::size_t hash(int key) const;
};
}

#include "table2.template" // Include the implementation

#endif

Answer:

// the code can be found below

// some of the requirement are not done

// check if you need the same solution or something

#include<iostream>

#include<string>
//#include <cstdlib> // Provides size_t
#include <list> // Provides the STL list class
using namespace std;
class record
{
public:
   int key;
   int value;
   record(int k, int v) :key(k), value(v)
   {

   }
};
//namespace main_savitch_12B
//{
template <class RecordType>
class table
{
public:
   // MEMBER CONSTANT -- See Appendix E if this fails to compile.
   static const std::size_t TABLE_SIZE = 811;
   // CONSTRUCTORS AND DESTRUCTOR
   table();
   table(const table& source);
   ~table();
   // MODIFICATION MEMBER FUNCTIONS
   void insert(int key,const RecordType& entry);
   void remove(int key);
   // CONSTANT MEMBER FUNCTIONS
   void find(int key, bool& found, RecordType& result) const;
   bool is_present(int key) const;
   std::size_t size() const { return total_records; }
private:
   std::list<RecordType> data[TABLE_SIZE]; //
   std::size_t total_records;
   // HELPER MEMBER FUNCTION
   std::size_t hash(int key) const;
};
//}
template <class RecordType>
table<RecordType>::table()
{
   total_records = 0;
   for (int i = 0; i < TABLE_SIZE; i++)
       data[i].push_back(0);
}
//copy constructor
template <class RecordType>
table<RecordType>::table(const table& source)
{
  

}
template <class RecordType>
void table<RecordType>::insert(int key, const RecordType& entry)
{
   if (key > 0)
   {

       list<RecordType>::iterator itr = data[key].begin();
       if (*itr == 0)
       {
           data[key].push_back(entry);
       }
       else
       {
           itr = data[key].erase(itr);
           data[key].push_back(entry);
      
       }
   }
}
template <class RecordType>
void table<RecordType>::remove(int key)
{
   list<RecordType>::iterator itr = data[key].begin();
   if (*itr != 0)
   {
       *itr = 0;
   }

}
template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const
{
   found = false;
   list<RecordType>::iterator itr = data[key].begin();
   if (*itr == result.value)
   {
       found = true;
   }


}
template <class RecordType>
bool table<RecordType>::is_present(int key) const
{
   list<RecordType>::iterator itr = data[key].begin();
   if (*itr != 0)
   {
       return true;
   }
   return false;

}
template <class RecordType>
size_t table<RecordType>::hash(int key) const
{

}
template <class RecordType>
table<RecordType>:: ~table()
{

}


int main()
{
   table<int> obj11;
   obj11.insert(1,100);
   obj11.insert(2,200);
   obj11.insert(3,300);
   obj11.insert(4,400);

}

Leave a Comment

Your email address will not be published. Required fields are marked *