Question

//BEGIN--TABLE.H--

#ifndef TABLE_H
#define TABLE_H

#include        // Provide string
#include // Provide hash
#include        // 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 thishash;
       return thishash(key) % TABLE_SIZE;
   }
};

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

   virtual void insert(string key);
   virtual void print();
  
private:
   list 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 TABLE.H--

//BEGIN_TABLE1.CPP---

#include
#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

   //   2. check if key is already in the list at datatable[i];
   //   - if yes, do nothing
   //   - if no, insert key into the list, increment 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    {  
       if (datatable[i].empty())
           continue;

       cout << "\t Entry " << i << ": ";
       for (list::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
   //   2. use hashcode function to calculate array index i
   //   3. 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,
   //       until an empty location is found, insert key at that location
   //   4. increment total_records
  
  
  
}

// 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    {  
       if (datatable[i].empty())
           continue;

       cout << "\t Entry " << i << ": ";
       cout << datatable[i] << endl;
   }
}

//End Table1.cpp--

Answer 1

Chain table insert function .. append these lines in insert function.

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=hashcode(key)
   //   2. check if key is already in the list at datatable[i];
   //   - if yes, do nothing
   if(datatable[index])
        return ;
   //   - if no, insert key into the list, increment total_records
   else
   {
       datatable[index]=key;
       total_records++;
   }
}

Quad table insert function. Plugin these lines ..

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;
   //   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
    table_records++;
    return;  
}