Question

// FILE: table1.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, do nothing
// print: print table contents
//
// DERIVED CLASS: ChainTable
//    The actual records are stored in a chained hash table.
//       datatable[i] stores a list of strings
//
// DERIVED CLASS: QuadTable
//    The actual records are stored in an array.
// datatable[i] stores one string
//

#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 = 13;

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

   unsigned int get_total() { return total_records; }

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

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

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

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

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

#endif

//------END TABLE1.H-------------------

//------------------BEGIN TABLE1.CPP---------------------

// FILE: table1.cpp

// CLASS IMPLEMENTED: ChainTable and QuadTable (see table1.h for documentation)

#include <iostream>

#include "table1.h"

void ChainTable::insert(string key)

{

    //-----------------------------------------------

    // TO-DO: insert key into the chained hash table

    // ------

    // 1. use hashcode function to calculate bucket index i

    unsigned int index_i = hashcode(key);

    //   2. check if key is already in the linkedlist at datatable[i];

    //   - if yes, do nothing

/* if (!datatable[index_i].empty())

        return;*/ incorrect! -3pts: if the linkedlist at the table entry is not empty, should first see if the key is in the list or not; then if not, insert into the list

    // - if no, insert key into the list, increment total_records

    else

    {

//datatable[index_i].push_back(key); Incorrect! use the linkedlist! Reveiw the table1.h code --> list<string> datatable[TABLE_SIZE]

        total_records++;

    }

}

// print table contents visually

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

    // ------

    // 1. if hash table is full, do nothing and return

// ALMOST! -2 pts: lines 70-71: if no collision, should return from the function directly after incrementing total_records.

    if (get_total() == TABLE_SIZE)

    {

        return;

    }

    // 2. use hashcode function to calculate array index i

    unsigned int index = hashcode(key);

    // 3. check if datatable[i] is empty

    if (datatable[index].empty())

        // - if yes, insert key at datatable[i]

        datatable[index] = key;

    // - if no, use quadratic probing with probe function c(i)=i^2,

    // until an empty location is found, insert key at that location

    for (int i = 0; i < TABLE_SIZE; i++)

    {

        int t = (index + i * i) % TABLE_SIZE;

        if (!datatable[t].empty())

        {

            datatable[t] = key;

            break;

        }

    }

    // 4. increment total_records

    total_records++;

    return;

}

// print table contents visually

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;

    }

}

I need help fixing the errors in the ChainTable::insert, and QuadTable::insert functions. My implementations are above, but my professor has stated the errors in comments.

for the ChainTable::insert, if the linkedlist at the table entry is not empty, I should first check if the key is in the list or not; then if not, insert into the list using the linkedlist method defined in the private section of the ChainTable class in the table.h file i.e list<string> datatable[TABLE_SIZE]; I cannot figure it out.

for the QuadTable:insert, if no collision, then I should return from the function directly after incrementing total_records. I thought that was already coded properly, but i guess not.

I was also told that  For both tables, a duplicate key should not be inserted.

PLEASE HELP!

Answer 1

Hi, Please find the new code highlighted. Please follow

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

void ChainTable::insert(string key)
{
  
// use hashcode function to calculate bucket index i
unsigned int index_i = hashcode(key);
  
  
// Checks if the List is not empty , then checks for each element in the list and returns if match is found else adds the element in the back.
   if (!datatable[index_i].empty())
   {
       list <string> :: iterator it;
           for(it = datatable.begin(); it != datatable.end(); ++it) {
               if(*it.compare(key)==0)
                   return;
           }
           datatable.push_back(key);
          
   }
  
// If the list is empty at the calculated address then, checks for the emptiness of the list, if size is full return , else adds the element at the given size
  
else  
{
      
       //First we need to declare a list that has to be inserted into the datatable.Push the value in this list and then put value list into datatable[index_i]
      
       list<string> value;
       value.push_back(key);
       datatable[index_i].splice(datatable[index_i].begin(),value);
total_records++;
       }
}

// print table contents visually
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
// ------
// 1. if hash table is full, do nothing and return

if (get_total() == TABLE_SIZE)
return;
  
// Use hashcode function to calculate array index i
unsigned int index = hashcode(key);
  
// Check if datatable[i] is empty, if yes, insert key at datatable[i]
if (datatable[index].empty()){
datatable[index] = key;
       total_records++;
       return;
   }
  
// - if no, use quadratic probing with probe function c(i)=i^2,
// until an empty location is found, insert key at that location
for (int i = 0; i < TABLE_SIZE; i++)
{
int t = (index + i * i) % TABLE_SIZE;
if (!datatable[t].empty())
{
datatable[t] = key;
break;
}
}
}

// print table contents visually
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;
}
}