I need help with C++ programming. and its name is Htable.cpp. please help ! You

Question

I need help with C++ programming. and its name is Htable.cpp. please help ! You can get my code from google doc below here:

https://docs.google.com/document/d/1NenTOwWEvxv3YaReBrJ4Yk5x22uQgny3MOS3mu0kKE8/edit?usp=sharing

(Exercise) In this part of the lab, you will be implementing the basic functions for a Hash Table, which are provided in the class declaration HTable.h (on UCMCROPS). In other words, you have to create and implement the class implementation in a file called HTable.cpp. The main file you have to use for this lab is also provided on UCMCROPS (Exercise.cpp). Do NOT modify the class declaration (HTable.h) or main file (Exercise.cpp). Looking at the class declaration, you will find that a data is defined as a structure comprised of a key of type int and a value of type string. You will also notice (under the class declaration of HTable) that an array of data (dt) with a maximum size (max size) is used as the hash table. A variable, numel, is used to keep track of the number of data stored in the hash table. Note: numel is not always the same as max size In this part of the lab, you will need to implement the following functions for the HTable class Default Constructor o Initializes the table (array) with a default size of 23 o An unoccupied space of the table will have a -1 as key and "N/A" as the value o numel is set to 0 Alternative Constructor o Initializes the table (array) with a size equal to the input parameter o An unoccupied space of the table will have a -1 as key and "N/A" as the value o numel is set to 0 hash(int &k;) o Evaluates the hash code according to the value of k o Since k is an integer, we will simply use the modulo operator to evaluate the hash code. It returns the hash code, which is the remainder of k divided by the size of the table. This hash code will be used as the index value of the hash table when storing the data int rehash(int &k;) o In an event when a collision (multiple keys result to the same hash code) happens, a rehashing of the hash code is performed. We will implement a linear probing as the rehashing function. It returns a new hash code, which is the remainder of (k+1) divided by the size of the table. This will shift the index value of the table to the next available space

Explanation / Answer

// Defination of class functions are provided after class declaration

class HTable {
data **dt; //the table to hold hashed data structs
int max_size; //max size of the table
int numel; //number of elements in table, to check if it's full
public:
HTable(); //default constructor to initialize a table of size 23
HTable (int t_size); //alternate constructor to initialize a table of size t_size
int hash(int &k); //evaluates hash code of key
int rehash(int &k); //performs linear probing if collision appears
int add(data &d); //adda a data pair into the table according to its key
int remove(data &d); //removes data pair from the table according to its key
void output(); //print out the content of the table
};
HTable::HTable()
{
dt = new HashEntry * [max_size];
for (int i = 0; i< max_size; i++)
{
dt[i] = NULL;
}
max_size = 23;
numel=0;
dt->key = -1;
dt->value = "N/A";
}
HTable::HTable (int t_size)
{
dt = new HashEntry * [max_size];
for (int i = 0; i< max_size; i++)
{
dt[i] = NULL;
}
max_size = t_size;
dt->key = -1;
dt->value = "N/A";
numel=0;
}
int HTable::hash(int &k)
{
return k%max_size;
}
int HTable::rehash(int &k)
{
return (k+1)%max_size;
}
int HTable::add(data &d)
{
int index = hash(d.key);
while (dt[index] != NULL && dt[index]->key != d.key)
index = rehash(index);
if (dt[index] != NULL)
delete dt[index];
dt[index] = new data(d.key, d.value);
}
int HTable::remove(data &d)
{
int index = hash(d.key);
while (dt[index] != NULL && dt[index]->key != d.key)
index = rehash(index);
if (dt[index] == NULL)
return -1;
else
return dt[index]->key;
}

void HTable::output()
{
cout << " Hash Table: ";
for ( int i = 0; i < max_size; i++ )
{
cout<< i + 1 << ": ";
cout<<dt[i]->value;
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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