I need BOTH parts or no points will be awarded. Suppose that I have a hash table

Question

I need BOTH parts or no points will be awarded.

Suppose that I have a hash table data[CAPACITY]. The hash table uses open addressing with linear probing. The table size is a global constant called CAPACITY. Locations of the table that have NEVER been used will contain the key -1. Locations of the table that were once used but are now vacant will contain the key -2. All valid keys will be non-negative, and the hash function is:
int hash(int key)
{
return (key % CAPACITY);
}
Complete the implementation of the following functions. There is no need to check the precondition, but your code must be as efficient as possible.

Part 1: Implement the following functions.
1. int hash(int key)
2. void hashInsert(int data[], int key)
3. bool key_occurs(const int data[ ], int search_key)
// Precondition: data[0]...data[CAPACITY-1] is an open address hash
// table as described above.
// Postcondition: If search_key occurs as a key of a record in the
// table, then the function returns true; otherwise the function //
// returns false.
4. Insert keys {5, 28, 19, 17, 20} with CAPACITY = 10.
5. Test your key_occurs function with search keys 19 and 10.

Part 2: Insert keys {10, 22, 31, 4, 15, 28, 17, 88, 59} into an empty hash table with CAPACITY = 10. Modify your code generated in Part 1 to resolve collision by linear probing.

Explanation / Answer

#include<iostream>
using namespace std;
const int CAPACITY = 10;
//1. int hash(int key)
int hash(int key)
{
return (key % CAPACITY);
}
//2. void hashInsert(int data[], int key)
void hashInsert(int data[], int key)
{
int index = hash(key);
while(data[index]!=0)
{
index = index+1;
}
data[index] = key;
}
//3. bool key_occurs(const int data[ ], int search_key)
// Precondition: data[0]...data[CAPACITY-1] is an open address hash
// table as described above.
// Postcondition: If search_key occurs as a key of a record in the
// table, then the function returns true; otherwise the function //
// returns false.
bool key_occurs(const int data[ ], int search_key)
{
if(data[hash(search_key)] == search_key)return true;
return false;
}
//4. Insert keys {5, 28, 19, 17, 20} with CAPACITY = 10.
//5. Test your key_occurs function with search keys 19 and 10.
int main()
{
int data[CAPACITY]={0};
/*
below code is for part 1
hashInsert(data,5);
hashInsert(data,28);
hashInsert(data,19);
hashInsert(data,17);
hashInsert(data,20);
if(key_occurs(data,19)) cout <<"19 found in table" << endl;
else cout <<"19 not found in table" << endl;
if(key_occurs(data,10)) cout <<"10 found in table" << endl;
else cout <<"10 not found in table" << endl;
*/

/*
BELOW CODE IS FOR PART 2
*/

//: Insert keys {10, 22, 31, 4, 15, 28, 17, 88, 59} into an empty hash table with CAPACITY = 10.
// Modify your code generated in Part 1 to resolve collision by linear probing.
hashInsert(data,10);
hashInsert(data,22);
hashInsert(data,31);
hashInsert(data,4);
hashInsert(data,15);
hashInsert(data,28);
hashInsert(data,17);
hashInsert(data,88);
hashInsert(data,59);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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