[Solved]Lab 12 Goal Assignment Reinforce Hash Tables C Specifically Lab Implement Dynamic Hash Ta Q37039834

Lab 12

The goal of this assignment is to reinforce hash tables in C++.Specifically, the lab is to

implement a dynamic hash table where the collisions are storedin an array of lists. Please

use table2.h and test_table2.cpp. You will be using ChainedHashing concept for implementing

this hash table.

Note that you will need to implement the table2 class and testyour implementation class using

the test_table2.cpp already provided for you.

// FILE: table2.h

// TEMPLATE CLASS PROVIDED: Table<RecordType>

//  This class is a container template class for aTable of records.

//  The template parameter, RecordType, is the datatype of the records in the

//  Table. It may any type with a default constructor,a copy constructor,

//  an assignment operator, and an integer membervariable called key.

//

// CONSTRUCTOR for the Table<RecordType> templateclass:

//  Table( )

//   Postcondition: The Table has beeninitialized as an empty Table.

//

// MODIFICATION MEMBER FUNCTIONS for the Table<RecordType>class:

//  void insert(const RecordType& entry)

//   Precondition: entry.key >= 0

//   Postcondition: If the table already had arecord with a key equal to

//   entry.key, then that record is replaced byentry. Otherwise, entry has

//   been added as a new record of the Table.

//

//  void remove(int key)

//   Postcondition: If a record was in the Tablewith the specified key, then

//   that record has been removed; otherwise thetable is unchanged.

//

// CONSTANT MEMBER FUNCTIONS for the Table<RecordType>class:

//  bool is_present(const Item& target) const

//   Postcondition: The return value is true ifthere is a record in the

//   Table with the specified key. Otherwise, thereturn value is false.

//

//  void find_location(int key, bool& found,

//   typenamestd::list<RecordType>::iterator& location) const

//   Postcondition: If a record is in the Tablewith the specified key, then

//   found is true and location is set to aniterator access the record.

//   Otherwise found is false and the resultcontains garbage.

//

//  size_t size( ) const

//   Postcondition: Return the total number ofrecords in the

//   Table.

//

#ifndef TABLE2_H

#define TABLE2_H

#include <cstdlib>  // Provides size_t

#include <list>

#include <iostream>

namespace main_savitch_12B

{

template <typename RecordType>

  class table

{

public:

  // MEMBER CONSTANT

  static const std::size_t NUM_BUCKETS = 10;

  // CONSTRUCTORS AND DESTRUCTOR

  table( );

  // MODIFICATION MEMBER FUNCTIONS

  void insert(const RecordType& entry);

  void remove(int key);

  // CONSTANT MEMBER FUNCTIONS

  bool is_present(int key) const;

  RecordType get_record (int key) const;

  std::size_t size( ) const;

  template <typename U>

  friend std::ostream& operator <<(std::ostream& output,

   const table<U>& t);

private:

  std::list<RecordType> data[NUM_BUCKETS];

  // HELPER MEMBER FUNCTION

  std::size_t hash(int key) const;

  void find_location(int key, bool& found,

    typenamestd::list<RecordType>::iterator&

    location);

   

};

}

#include “table2.template” // Include the implementation

#endif

===========================================================

// test_table2.cpp

#include “table2.h”

#include <cstdlib>

#include <iostream>

using namespace std;

using namespace main_savitch_12B;

// Struct definition for the test_record_type, which has a key,string

// and a double.

typedef struct struct_test_record_type

{

int key;

string s;

double data;

} test_record_type;

ostream& operator << (ostream& out, consttest_record_type& r);

// postcondition: r has been displayed on out

int main ()

{

table<test_record_type> t;

test_record_type item1 {34, “abc”, 26.1};

t.insert (item1);

test_record_type item2 {34, “hhh”, 127};

t.insert (item2);

test_record_type item3 {44, “xyz”, -14.5};

t.insert (item3);

test_record_type item4 {28, “bcd”, 0.1};

t.insert (item4);

test_record_type item5 {8, “cde”, -5.66};

t.insert (item5);

test_record_type item6 {17, “efg”, 2.5};

t.insert (item6);

test_record_type item7 {87, “fgh”, 78.3};

t.insert (item7);

test_record_type item8 {1, “ghi”, 333.78};

t.insert (item8);

test_record_type item9 {6, “hij”, 34.22};

t.insert (item9);

test_record_type item10 {84, “ijk”, 116};

t.insert (item10);

cout << t << endl;

t.remove (44);

cout << t << endl;

t.remove (17);

cout << t << endl;

t.remove (99);

cout << t << endl;

return EXIT_SUCCESS;

}

ostream& operator << (ostream& out, consttest_record_type& r)

{

out << “key: ” << r.key << ” s: ” << r.s<< ” data: ” << r.data << endl;

return out;

}

Expert Answer

---

Answer to Lab 12 The goal of this assignment is to reinforce hash tables in C++. Specifically, the lab is to implement a dynamic h… . . .