Question

In: Computer Science

[Hash Tables] Given the following code in C++, implement the functions in table2.cpp. The first 2...

[Hash Tables] Given the following code in C++, implement the functions in table2.cpp. The first 2 files (table2.h, short story text file) are all fully coded and commented for convenience.

*****I have given references that I've completed previously for the table2.cpp file, I just need help applying them. Will provide good rating, thanks******

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

table2.h (given file, do not edit):

// FILE: table2.h
//
// ABSTRACT BASE CLASS: Table
//    1. The number of records in the Table is stored in total_records
// 2. The hashcode function returns a location in the table for the
// input key. It calls hash function in functional library.
// 3. insert and print are two virtual functions to be overridden
// insert: Add a new record into the Table;
//           If key is already in the table, increment count
// print_max: print the record with the highest count
//
// DERIVED CLASS: ChainTable
//    The actual records are stored in a chained hash table.
//       datatable[i] stores a list of Records
//
// DERIVED CLASS: QuadTable
//    The actual records of the table are stored in an array.
// datatable[i] stores one Record
//

#ifndef TABLE_H
#define TABLE_H

#include <string>       // Provide string
#include <functional> // Provide hash
#include <list>        // Provide list
using namespace std;

class Table
{
public:
   // MEMBER CONSTANT
   static const unsigned int TABLE_SIZE = 5801;

   Table() { total_records = 0; }
   virtual ~Table() { }

   unsigned int get_total() { return total_records; }

   virtual void insert(string key) =0;
   virtual void print_max() =0;
  
protected:
   unsigned int total_records;

   // HELPER FUNCTION
   unsigned int hashcode(string key) const
   {
       hash<string> thishash;
       return thishash(key) % TABLE_SIZE;
   }
};

class Record
{
public:
   Record(string k="", unsigned int c=0) { key = k; count = c; }
   string key;
   unsigned int count;
};

class ChainTable : public Table
{
public:
   ChainTable() {}

   virtual void insert(string key);
   virtual void print_max();
  
private:
   list<Record> datatable[TABLE_SIZE];
};

class QuadTable : public Table
{
public:
   QuadTable() {}
  
   virtual void insert(string key);
   virtual void print_max();
   bool full() { return total_records == TABLE_SIZE; }
  
private:
   Record datatable[TABLE_SIZE];
};

#endif

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

shortstory.txt (given file, do not edit):

John Rento looked at the giant hawk in his hands and felt stressed.

He walked over to the window and reflected on his quiet surroundings. He had always loved cold Athens with its faithful, friendly fields. It was a place that encouraged his tendency to feel stressed.

Then he saw something in the distance, or rather someone. It was the figure of Georgina Rockatansky. Georgina was an intuitive god with curvy fingers and grubby eyelashes.

John gulped. He glanced at his own reflection. He was a spiteful, proud, port drinker with handsome fingers and short eyelashes. His friends saw him as a queenlike, queasy queen. Once, he had even saved a homely disabled person that was stuck in a drain.

But not even a spiteful person who had once saved a homely disabled person that was stuck in a drain, was prepared for what Georgina had in store today.

THE END

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

table2.cpp (code to complete):

// FILE: table2.cpp
// CLASS IMPLEMENTED: ChainTable and QuadTable (see table2.h for documentation)

#include <iostream>
#include "table2.h"

void ChainTable::insert(string key)
{
   //--------------------------------------------------------------
   // TO-DO: insert key into the chained hash table
   // ------
   // 1. use hashcode function to calculate bucket index i
   //   2. check if key is already in the list at datatable[i];
   //   - if yes, increment the count by 1
   //   - if no, insert key into the list, increment total_records
  
  
}


// print the Record with the highest count
void ChainTable::print_max()
{
   //-------------------------------------------------------------
   // TO-DO: go through the hash table,
   //       find the record with the highest count,
   //       and print out the information.
   // ------
   // You can use ChainTable::print() from part 1 as a reference
   // This is the Part 1 ChainTable::print() (reference)
  
   // void ChainTable::print()
   //{
   // cout << "ChainTable content: \n";
   // if (total_records==0)
   //{
   //   cout << "\t Empty!\n";
   //   return;
   //}

   // for (unsigned int i=0; i<TABLE_SIZE; i++)
   //{  
   //   if (datatable[i].empty())
   //       continue;
//
   //   cout << "\t Entry " << i << ": ";
   //   for (list<string>::iterator it = datatable[i].begin(); it != datatable[i].end(); it++)
   //   {
   //       cout << (*it) << " -> ";
   //   }
   //   cout << "NULL\n";
   // }
// }
}


//////////////////////////////////////////////////
void QuadTable::insert(string key)
{
   //--------------------------------------------------------------
   // TO-DO: insert key into the hash table using quadratic probing
   // ------
   // Modify from the implementation from part 1
   //   1. use hashcode function to calculate array index i
   //   2. check if datatable[i] is empty
   //   - if yes, insert key at datatable[i]
   //   - if no, use quadratic probing with probe function c(i)=i^2,
   //       if key is found, increment total_records;
   //       if key is not found, then look for an empty location,
   //       insert key at that location, set total_records = 1
   //   4. if datatable is full and key is new, do nothing and return

}

// print the Record with the highest count
void QuadTable::print_max()
{
   //-------------------------------------------------------------
   // TO-DO: go through the hash table,
   //       find the record with the highest count,
   //       and print out the information.
   // ------
   // You can use QuadTable::print() from part 1 as a reference
   // This is the Part 1 QuadTable::print() (reference)
  
//   void QuadTable::print()
//{
//   cout << "QuadTable content: \n";
//   if (total_records==0)
//   {
//       cout << "\t Empty!\n";
//       return;
//   }
//
//   for (unsigned int i=0; i<TABLE_SIZE; i++)
//   {  
//       if (datatable[i].empty())
//           continue;
//
//       cout << "\t Entry " << i << ": ";
//       cout << datatable[i] << endl;
//   }
//}

  
}

Solutions

Expert Solution

#include <iostream>
#include "table2.h"

void ChainTable::insert(string key)
{
   //--------------------------------------------------------------
   // TO-DO: insert key into the chained hash table
   // ------
   // 1. use hashcode function to calculate bucket index i
   //   2. check if key is already in the list at datatable[i];
   //   - if yes, increment the count by 1
   //   - if no, insert key into the list, increment total_records
    
   int index = hashcode(key);
   bool is_already_present = false;
   for(auto it = datatable[index].begin(); it != datatable[index].end(); ++it){
       if(it->key == key){
           is_already_present = true;
           it->count++;
           break;
       }
   }
   if(not is_already_present){
       datatable[index].push_back(Record(key,1));
       total_records++;
   }
  
}


// print the Record with the highest count
void ChainTable::print_max()
{
   //-------------------------------------------------------------
   // TO-DO: go through the hash table,
   //       find the record with the highest count,
   //       and print out the information.
   // ------
   // You can use ChainTable::print() from part 1 as a reference
   // This is the Part 1 ChainTable::print() (reference)
  
   // void ChainTable::print()
   //{
   // cout << "ChainTable content: \n";
   // if (total_records==0)
   //{
   //   cout << "\t Empty!\n";
   //   return;
   //}

   // for (unsigned int i=0; i<TABLE_SIZE; i++)
   //{  
   //   if (datatable[i].empty())
   //       continue;
//
   //   cout << "\t Entry " << i << ": ";
   //   for (list<string>::iterator it = datatable[i].begin(); it != datatable[i].end(); it++)
   //   {
   //       cout << (*it) << " -> ";
   //   }
   //   cout << "NULL\n";
   // }
// }
//   
    Record max_record;
    for(unsigned int i=0;i < TABLE_SIZE;i++){
        if(datatable[i].empty())continue;
        for(const auto val: datatable[i]){
            if(val.count > max_record.count){
                max_record = val;
            }
        }
    }
    cout<<"Record with max count is "<<max_record.key<<" and count is "<<max_record.count<<endl;
}


//////////////////////////////////////////////////
void QuadTable::insert(string key)
{
   //--------------------------------------------------------------
   // TO-DO: insert key into the hash table using quadratic probing
   // ------
   // Modify from the implementation from part 1
   //   1. use hashcode function to calculate array index i
   //   2. check if datatable[i] is empty
   //   - if yes, insert key at datatable[i]
   //   - if no, use quadratic probing with probe function c(i)=i^2,
   //       if key is found, increment total_records;
   //       if key is not found, then look for an empty location,
   //       insert key at that location, set total_records = 1
   //   4. if datatable is full and key is new, do nothing and return
   
    int index = hashcode(key);
    if(full() and datatable[index].key != key){   // if table is full and key does not match
        return;
    }
    if(datatable[index].key == "" and datatable[index].count == 0){  // if there is no entry at desired position
        datatable[index] = Record(key,1);
    }
    else{
        long unsigned counter = 0;
        while(true){   // apply quadratic probing
            int new_index = (index + counter*counter) % TABLE_SIZE;
            if(datatable[new_index].key == key){   // already present a key 
                datatable[new_index].count++;
                return;
            }
            else if(datatable[new_index].key == "" and datatable[new_index].count == 0){  // empty location
                datatable[new_index] = Record(key,1);
                total_records++;
                return ;
             }
            counter++;
        }
    }
}

// print the Record with the highest count
void QuadTable::print_max()
{
   //-------------------------------------------------------------
   // TO-DO: go through the hash table,
   //       find the record with the highest count,
   //       and print out the information.
   // ------
   // You can use QuadTable::print() from part 1 as a reference
   // This is the Part 1 QuadTable::print() (reference)
  
//   void QuadTable::print()
//{
//   cout << "QuadTable content: \n";
//   if (total_records==0)
//   {
//       cout << "\t Empty!\n";
//       return;
//   }
//
//   for (unsigned int i=0; i<TABLE_SIZE; i++)
//   {  
//       if (datatable[i].empty())
//           continue;
//
//       cout << "\t Entry " << i << ": ";
//       cout << datatable[i] << endl;
//   }
//}

  
    Record max_record;
    for(unsigned int i=0; i < TABLE_SIZE;i++){
        if(datatable[i].key == "" and datatable[i].count == 0){ // if there is no entry at desired position
            continue;
        }
        if(datatable[i].count > max_record.count)
            max_record = datatable[i];
        
    }
    cout<<"Record with max count is "<<max_record.key<<" and count is "<<max_record.count<<endl;
}

venereology answered 1 year ago
Next > < Previous

Related Solutions

C++ Please Fill in for the functions for the code below. The functions will implement an...
C++ Please Fill in for the functions for the code below. The functions will implement an integer list using dynamic array ONLY (an array that can grow and shrink as needed, uses a pointer an size of array). Additional public helper functions or private members/functions can be used. The List class will be instantiated via a pointer and called similar to the code below: class List { public: // Default Constructor List() {// ... } // Push integer n onto...
C++ Please Fill in for the functions for the code below. The functions will implement an...
C++ Please Fill in for the functions for the code below. The functions will implement an integer stack using deques ONLY. It is possible to use only one deque but using two deques also works. Additional public helper functions or private members/functions can be used. The Stack class will be instantiated via a pointer and called as shown below: Stack *ptr = new Stack(); ptr->push(value); int pop1 = ptr->pop(); int pop2 = ptr->pop(); bool isEmpty = ptr->empty(); class Stack{     public:...
C++ please Fill in for the functions for the code below. The functions will implement an...
C++ please Fill in for the functions for the code below. The functions will implement an integer stack using deques ONLY. It is possible to use only one deque but using two deques also works. Additional public helper functions or private members/functions can be used. The Stack class will be instantiated via a pointer and called as shown below: Stack *ptr = new Stack(); ptr->push(value); int pop1 = ptr->pop(); int pop2 = ptr->pop(); bool isEmpty = ptr->empty(); class Stack{     public:...
Implement the following functions in the given code: def babylonian_square_root(N, estimate, precision): This function is provided...
Implement the following functions in the given code: def babylonian_square_root(N, estimate, precision): This function is provided for you to use: def close_enough(x, y, maximum_allowable_difference): My biggest piece of advice to you is to go one line at a time and check your return values after each little change you make. Starter code: # There are different ways of implementing the same idea in math. # Today we will explore a simple way to calculate square roots. # # # #...
PLEASE write the code in C++. employee.h, employee.cpp, and hw09q1.cpp is given. Do not modify employee.h...
PLEASE write the code in C++. employee.h, employee.cpp, and hw09q1.cpp is given. Do not modify employee.h and answer the questions in cpp files. Array is used, not linked list. It would be nice if you could comment on the code so I can understand how you wrote it employee.h file #include <string> using namespace std; class Employee { private:    string name;    int ID, roomNumber;    string supervisorName; public:    Employee();       // constructor    void setName(string name_input);   ...
Implement a Cuckoo hash table in which two separate tables are maintained. Each table should have...
Implement a Cuckoo hash table in which two separate tables are maintained. Each table should have a fixed size of 13. Use the hash function h1(x) = x mod 13 for the first table, and h2(x)= 11 – (x mod 11) for the second table. Your program should read an input file, input.txt, consisting of one input per line, insert the input to the table in order, and print out the final content of the hash table in the provided...
Q2. Update the given code 2 to implement the following problem: Create a class triangle Use...
Q2. Update the given code 2 to implement the following problem: Create a class triangle Use dynamic memory allocation to create 10 objects of the class triangle Set default height and base of all created objects (triangle) to 5 and 10 respectively using a constructor Ask user to change only the height of the 5th triangle Print height and base of all (10) triangles to demonstrate that you did the task correctly Deallocate the 5th object Print height and base...
IN C++ Given a struct Node { int value; Node *left, *right;}; , implement the functions...
IN C++ Given a struct Node { int value; Node *left, *right;}; , implement the functions below. a) int getSmallest(Node * r); // return smallest value in the BST with root r. Assume r not null. b) int getSecondSmallest(Node * r); // return 2nd smallest value in BST with root r. Assume r not null and r has a nonnull left or right child. c) void removeSecondSmallest(Node * r); // remove 2nd smallest value in BST with root r. Assume...
in C++ We are going to implement the following scheduling algorithms 1. First-Come First-Served (FCFS) 2....
in C++ We are going to implement the following scheduling algorithms 1. First-Come First-Served (FCFS) 2. Shortest Remaining Time First (SRTF) 3. Highest Response Ratio Next (HRRN) 4. Round Robin, with di_erent quantum values (RR) We are interested to compute the following metrics, for each experiment: _ The average turnaround time _ The total throughput (number of processes done per unit time) _ The CPU utilization _ The average number of processes in the ready queue The simulator needs to...
Use double hashing and the following hash functions: hash(key) = (key % table size) and hash2(key)...
Use double hashing and the following hash functions: hash(key) = (key % table size) and hash2(key) = (16 - (key % 10)) + 1 to insert the following numbers into a dictionary's hash table: 1, 12, 14, 3, 5 and 17. The table size is 11. Show the table and where each value is inserted. No coding required for this problem.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT