* Complete method insert() and findIndex() in header file * These methods use th
ID: 3737943 • Letter: #
Question
* Complete method insert() and findIndex() in header file
* These methods use the hash of the value given as parameter.
* In case of an error, throw a runtime_error with a message.
PLEASE ONLY PLACE CODE WHERE IT SAYS CODE HERE, DO NOT CHANGE ANY OTHER CODE
Main:
#include "hashArray.h"
int main(){
int CAPACITY = 10;
hashArray dataTable(CAPACITY);
bool found;
int index;
int data[] = {37,59,84,52,29,42,84,79,73,90,16,17,26,15,60,90,34,11,71,2};
for(int i = 0; i < CAPACITY; i++){
dataTable.insert(data[i]);
cout << "print: ";
dataTable.print();
cout << endl << endl;
}
cout << "Length: " << dataTable.size() << endl;
if(dataTable.size() != CAPACITY){
cout << "Error! Length is not correct" << endl;
}
cout << endl << "Searching element 50" << endl;
dataTable.findIndex(50, found, index);
cout << endl << "Searching element 59" << endl;
dataTable.findIndex(59, found, index);
cout << endl << "Searching element 73" << endl;
dataTable.findIndex(73, found, index);
cout << endl << "Searching element 90" << endl;
dataTable.findIndex(90, found, index);
return 0;
}
Header:
#include <iostream>
#include <stdexcept>
using namespace std;
class hashArray {
protected:
int* table;
int length;
int capacity;
public:
hashArray(int cap){
table = new int[cap];
capacity = cap;
length = 0;
for(int i = 0; i < capacity; i++){
table[i] = -1;
}
}
~hashArray(){
delete[] table;
}
int size(){
return length;
}
bool isFull(){
return length == capacity;
}
void print(){
for(int i = 0; i < capacity; i++){
if(table[i] != -1){
cout << table[i] << " ";
}
else{
cout << "_ ";
}
}
}
int hash(int entry){
return entry % capacity;
}
void insert(int entry){
if(isFull()){
/* CODE HERE */
}
else{
int count = 0;
int h, index;
/* CODE HERE */
cout << "hash(" << entry << ") = " << index << endl;
while(table[index] != -1){
count++;
cout << "Index " << index << " is occupied" << endl;
/* CODE HERE */
}
cout << "Inserted " << entry << " at " << index << endl;
/* CODE HERE */
}
}
// If a record with the indicated key is in the table,
// then found is true and index is set to index of the found record.
// Otherwise, found is false and index is garbage.
void findIndex(int entry, bool &found, int &i){
int count = 0;
int h;
/* CODE HERE */
while( /* CODE HERE */){
count++;
/* CODE HERE */
}
found = table[i] == entry;
if(found){
cout << "Found";
}
else{
cout << "Not found";
}
cout << " after " << count << " accesses" << endl;
}
};
Explanation / Answer
//Insert an element
void insert(int entry){
int hash = hash(entry); // function call to get hashvalue , here hash() is function defined
while (table[hash] != NULL && table[hash] != entry) // iterating to check if value from array is null
{
hash = hash(hash + 1);
}
if (table[hash] != NULL)
delete table[hash];
table[hash] = new hashArray(entry); //adding the element into to hash
}
/*
* Search Element
*/
void findIndex(int entry, bool &found, int &i){
int hash = HashFunc(entry);
while (table[hash] != NULL)
{
hash = hash(hash + 1);
}
if (table[hash] == NULL)
found = false;
i = -1;
else
found = table[i] == entry;
i = hash;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.