i need some help solving this C++ problem The purpose of this is to help reinfor

Question

i need some help solving this C++ problem

The purpose of this is to help reinforce hash tables implementations in C++.

Use double hashing to reimplement the hash table.

The table1.h has been provided.

Test your program in main().

// FILE: table1.h (part of the namespace main_savitch_12A)
// TEMPLATE CLASS PROVIDED: table<RecordType> (a table of records with keys).
// 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 be any of the bulit-in C++ types (int, char, etc.), or a
// class with a default constructor, an assignment operator, and an integer
// member variable called key.
//
// MEMBER CONSTANT for the table<RecordType> class:
// static const size_type CAPACITY = ________
// table<RecordType>::CAPACITY is the maximum number of records held by a table.
//
// 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_type 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.

#ifndef TABLE1_H
#define TABLE1_H
#include <cstdlib> // Provides size_t

namespace main_savitch_12A
{
template <class RecordType>
class table
{
public:
// MEMBER CONSTANT -- See Appendix E if this fails to compile.
static const std::size_t CAPACITY = 811;
// CONSTRUCTOR
table( );
// MODIFICATION MEMBER FUNCTIONS
void insert(const RecordType& entry);
void remove(int key);
// CONSTANT MEMBER FUNCTIONS
bool is_present(int key) const;
void find(int key, bool& found, RecordType& result) const;
std::size_t size( ) const { return used; }
private:
// MEMBER CONSTANTS -- These are used in the key field of special records.
static const int NEVER_USED = -1;
static const int PREVIOUSLY_USED = -2;
// MEMBER VARIABLES
RecordType data[CAPACITY];
std::size_t used;
// HELPER FUNCTIONS
std::size_t hash(int key) const;
std::size_t next_index(std::size_t index) const;
void find_index(int key, bool& found, std::size_t& index) const;
bool never_used(std::size_t index) const;
bool is_vacant(std::size_t index) const;
};
}
#include "table1.template" // Include the implementation.
#endif

Explanation / Answer

Answer:

#include <iostream>

#include <cstdlib>
#define MINIMUM_TABLE_SIZE 10
using namespace std;

enum SourceType {Legal, Vacant, Removed};

struct HashNodeTaken
{
int entity;
enum SourceType data;
};

struct HashTable
{
int size;
HashNodeTaken *table;
};

int Hashfunction1(int key_value, int size)
{
return key_value % size;
}

int Hashfunction2(int key_value, int size)
{
return (key_value * size - 1) % size;
}

HashTable *startTable(int size)
{
HashTable *htable;
if (size < MINIMUM_TABLE_SIZE)
{
cout<<"Table Size Too Small.Please Check"<<endl;
return NULL;
}
htable = new HashTable;
if (htable == NULL)
{
cout<<"Space is not available"<<endl;
return NULL;
}
htable->size = size;
htable->table = new HashNodeTaken [htable->size];
if (htable->table == NULL)
{
cout<<"Table Size Too Small.Please Check"<<endl;
return NULL;
}
for (int i = 0; i < htable->size; i++)
{
htable->table[i].data = Vacant;
htable->table[i].entity = NULL;
}
return htable;
}
int Search(int key_value, HashTable *htable)
{
int hashvalues= Hashfunction1(key_value, htable->size);
int size_of_step= Hashfunction2(key_value, htable->size);
while (htable->table[hashvalues].data != Vacant &&
htable->table[hashvalues].entity != key_value)
{
hashvalues = hashvalues + size_of_step;
hashvalues = hashvalues % htable->size;
}
return hashvalues;
}
void push(int key_value, HashTable *htable)
{
int position = Search(key_value, htable);
if (htable->table[position].data != Legal )
{
htable->table[position].data = Legal;
htable->table[position].entity = key_value;
}
}

HashTable *rehashing(HashTable *htable)
{
int size = htable->size;
HashNodeTaken *table = htable->table;
htable = startTable(2 * size);
for (int i = 0; i < size; i++)
{
if (table[i].data == Legal)
push(table[i].entity, htable);
}
free(table);
return htable;
}

void getdata(HashTable *htable)
{
for (int i = 0; i < htable->size; i++)
{
int value = htable->table[i].entity;
if (!value)
cout<<"position: "<<i + 1<<" entity: Null"<<endl;
else
cout<<"position: "<<i + 1<<" entity: "<<value<<endl;
}

}

int main()
{
int value, size, position, i = 1;
int select;
HashTable *htable;
while(1)
{

cout<<"Functions in Double Hashing"<<endl;
  
cout<<"1.Initialize the size of table"<<endl;
cout<<"2.Make an element to push into the table"<<endl;
cout<<"3.Print HashTable"<<endl;
cout<<"4.Rehash the table"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>select;
switch(select)
{
case 1:
cout<<"Enter size of the Hash Table: ";
cin>>size;
htable = startTable(size);
break;
case 2:
if (i > htable->size)
{
cout<<"Table is under overflow rehashing the table"<<endl;
continue;
}
   cout<<"Enter element to be pushed: ";
   cin>>value;
push(value, htable);
i++;
break;
case 3:
getdata(htable);
break;
case 4:
htable = rehashing(htable);
break;
case 5:
exit(1);
default:
cout<<" Please enter correct option.Check again ";
}
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.