Follow the comments and implement INSERT, SEARCH, and REMOVE in c++ exactly as the comments suggest and NO other way! Do
Posted: Fri Jul 08, 2022 6:39 am
Follow the comments and implement INSERT, SEARCH, and REMOVE in c++ exactly as the comments suggest and NO other way!
Do NOT edit this file
main.cpp:
#include <iostream>
#include "HashTable.h"
using namespace std;
int main(){
HashTable ht1;
ht1.insert(52);
ht1.insert(20);
ht1.insert(48);
ht1.insert(36);
ht1.insert(10);
ht1.insert(92);
ht1.insert(28);
ht1.insert(72);
cout << endl;
cout << "// Hash Table ht1 (table size: 10)" << endl << endl;
ht1.print_hash_table();
cout << endl;
cout << "Search 45 in ht1: " << ht1.search(45) << endl;
cout << "Search 92 in ht1: " << ht1.search(92) << endl;
cout << endl << endl;
HashTable ht2(7);
ht2.insert(52);
ht2.insert(20);
ht2.insert(48);
ht2.insert(36);
ht2.insert(10);
ht2.insert(92);
ht2.insert(28);
ht2.insert(72);
cout << "// Hash Table ht2 (table size: 7)" << endl << endl;
ht2.print_hash_table();
cout << endl;
cout << "Search 12 in ht2: " << ht2.search(12) << endl;
cout << "Search 50 in ht2: " << ht2.search(50) << endl;
cout << endl << endl;
HashTable ht3(13);
ht3.insert(52);
ht3.insert(20);
ht3.insert(48);
ht3.insert(36);
ht3.insert(10);
ht3.insert(92);
ht3.insert(28);
ht3.insert(72);
cout << "// Hash Table ht3 (table size: 13)" << endl << endl;
ht3.print_hash_table();
cout << endl;
cout << "Search 36 in ht3: " << ht3.search(36) << endl;
cout << "Search 52 in ht3: " << ht3.search(52) << endl;
cout << endl << endl;
HashTable ht4(3);
ht4.insert(0);
ht4.insert(1);
ht4.insert(11);
ht4.insert(101);
ht4.insert(2);
ht4.insert(12);
ht4.insert(102);
ht4.insert(3);
ht4.insert(13);
ht4.insert(103);
ht4.insert(4);
ht4.remove(0);
ht4.remove(4);
cout << "// Hash Table ht4 (table size: 3)" << endl << endl;
ht4.print_hash_table();
cout << endl;
cout << "Search 101 in ht4: " << ht4.search(101) << endl;
cout << "Search 0 in ht4: " << ht4.search(0) << " (REMOVED)" << endl;
cout << endl << endl;
}
file to edit ONLY implement inside the insert, search , and remove functions: HashTable.h
#ifndef HashTable_H
#define HashTable_H
#include <iostream>
#include <string>
#include <list> // STL(Standard Template Library) list, Since lists use both forward and backward pointers, they implement doubly linked lists.
#include <algorithm> // STL algorihtms, we use the find() function to support STL list
using namespace std;
class HashTable {
private:
list<int> * table; // instead of allocating a fix size like table[10], this is allocating it in the heap memory
int size;
int hash_function(int data){ // simple modulo function, index = key MOD tableSize
return data % size;
}
public:
HashTable(){ // default constructor
this->size = 10;
table = new list<int> [this->size]; // array of list<int>
}
HashTable(int size){ // customized-size constructor
this->size = size;
table = new list<int> [this->size]; // array of list<int>
}
~HashTable() {
delete [] table;
}
// IMPLEMENT INSERT, SEARCH, and REMOVE as the comments says:
void insert(int data) {
/**
* Inserts the data into the correct index. For insertion, we want O(1) time, so we will insert in the front of the list.
*
* This function will simply do the followings:
* 1. hash the data key to get the appropriate index in the hash table
* 2. insert the data key into the appropriate index
* (for inserting the data in the beginning of the STL list, we use the .push_front() method in the list,
* the push_front() method will accept the data we want to insert)
*
* @param data, int, the data we want to insert in the hash table
*
*/
}
bool search(int data){
/**
* Searches whether the data is in the hash table, if yes return true, otherwise return false.
*
* This function will do the followings:
* 1. hash the data key to get the appropriate index in the hash table
* 2. Use the find() function from STL algorithm library to search for the data
* The syntax is as follows:
* find(first_iterator, last_iterator, x)
* This will return an iterator to the first occruence of the data in the STL list/vectpr,
* if the element is present in the list/vector, the iterator will be pointing to that data item,
* if the element is not found in the list/vector, it will point to the last address of the list/vector, that is ((name_of_vector/list).end())
*
* The iterator type should be:
* list<int>::iterator it = find(first_iterator, last_iterator, x);
* But for convience, other than writing such long and complicated type, we can replace it with auto, that is:
* auto it = find(first_iterator, last_iterator, x);
*
* If you use a STL list, the first iterator will be name_of_list.begin(), the last iterator will be name_of_list.end()
* In our case, name_of_list will be table[index], assuming index is the hash value we get from the hash function.
* 3. As mentioned in the point2, if the element is not found in the list/vector, the iterator will point to the last address of the list/vector.
* so if the iterator is the end of the list, this function will return false,
* otherwise, it will return true (because it is pointing to some found item).
*
*/
}
void remove(int data) {
/**
* Removes the data if it exists in the list, if it does not exist, end the function.
* (As we still need to find that data before we remove, so this function is pretty similiar to the search() function.)
*
* This function will do the followings:
* 1. Same as search() point 1
* 2. Same as search() point 2
* 3. If the iterator is the end of the list, it will return the function (cancel the remove),
* otherwise, if the data exists, we will use the name_of_list.erase(iterator) to remove the data in the hash table
*
*/
}
Correct output of the program:
// Hash Table ht1 (table size: 10)
| 0 | -> 10 -> 20
| 1 | ->
| 2 | -> 72 -> 92 -> 52
| 3 | ->
| 4 | ->
| 5 | ->
| 6 | -> 36
| 7 | ->
| 8 | -> 28 -> 48
| 9 | ->
Search 45 in ht1: 0
Search 92 in ht1: 1
// Hash Table ht2 (table size: 7)
| 0 | -> 28
| 1 | -> 92 -> 36
| 2 | -> 72
| 3 | -> 10 -> 52
| 4 | ->
| 5 | ->
| 6 | -> 48 -> 20
Search 12 in ht2: 0
Search 50 in ht2: 0
// Hash Table ht3 (table size: 13)
| 0 | -> 52
| 1 | -> 92
| 2 | -> 28
| 3 | ->
| 4 | ->
| 5 | ->
| 6 | ->
| 7 | -> 72 -> 20
| 8 | ->
| 9 | -> 48
| 10 | -> 10 -> 36
| 11 | ->
| 12 | ->
Search 36 in ht3: 1
Search 52 in ht3: 1
// Hash Table ht4 (table size: 3)
| 0 | -> 3 -> 102 -> 12
| 1 | -> 103 -> 13 -> 1
| 2 | -> 2 -> 101 -> 11
Search 101 in ht4: 1
Search 0 in ht4: 0 (REMOVED)
Do NOT edit this file
main.cpp:
#include <iostream>
#include "HashTable.h"
using namespace std;
int main(){
HashTable ht1;
ht1.insert(52);
ht1.insert(20);
ht1.insert(48);
ht1.insert(36);
ht1.insert(10);
ht1.insert(92);
ht1.insert(28);
ht1.insert(72);
cout << endl;
cout << "// Hash Table ht1 (table size: 10)" << endl << endl;
ht1.print_hash_table();
cout << endl;
cout << "Search 45 in ht1: " << ht1.search(45) << endl;
cout << "Search 92 in ht1: " << ht1.search(92) << endl;
cout << endl << endl;
HashTable ht2(7);
ht2.insert(52);
ht2.insert(20);
ht2.insert(48);
ht2.insert(36);
ht2.insert(10);
ht2.insert(92);
ht2.insert(28);
ht2.insert(72);
cout << "// Hash Table ht2 (table size: 7)" << endl << endl;
ht2.print_hash_table();
cout << endl;
cout << "Search 12 in ht2: " << ht2.search(12) << endl;
cout << "Search 50 in ht2: " << ht2.search(50) << endl;
cout << endl << endl;
HashTable ht3(13);
ht3.insert(52);
ht3.insert(20);
ht3.insert(48);
ht3.insert(36);
ht3.insert(10);
ht3.insert(92);
ht3.insert(28);
ht3.insert(72);
cout << "// Hash Table ht3 (table size: 13)" << endl << endl;
ht3.print_hash_table();
cout << endl;
cout << "Search 36 in ht3: " << ht3.search(36) << endl;
cout << "Search 52 in ht3: " << ht3.search(52) << endl;
cout << endl << endl;
HashTable ht4(3);
ht4.insert(0);
ht4.insert(1);
ht4.insert(11);
ht4.insert(101);
ht4.insert(2);
ht4.insert(12);
ht4.insert(102);
ht4.insert(3);
ht4.insert(13);
ht4.insert(103);
ht4.insert(4);
ht4.remove(0);
ht4.remove(4);
cout << "// Hash Table ht4 (table size: 3)" << endl << endl;
ht4.print_hash_table();
cout << endl;
cout << "Search 101 in ht4: " << ht4.search(101) << endl;
cout << "Search 0 in ht4: " << ht4.search(0) << " (REMOVED)" << endl;
cout << endl << endl;
}
file to edit ONLY implement inside the insert, search , and remove functions: HashTable.h
#ifndef HashTable_H
#define HashTable_H
#include <iostream>
#include <string>
#include <list> // STL(Standard Template Library) list, Since lists use both forward and backward pointers, they implement doubly linked lists.
#include <algorithm> // STL algorihtms, we use the find() function to support STL list
using namespace std;
class HashTable {
private:
list<int> * table; // instead of allocating a fix size like table[10], this is allocating it in the heap memory
int size;
int hash_function(int data){ // simple modulo function, index = key MOD tableSize
return data % size;
}
public:
HashTable(){ // default constructor
this->size = 10;
table = new list<int> [this->size]; // array of list<int>
}
HashTable(int size){ // customized-size constructor
this->size = size;
table = new list<int> [this->size]; // array of list<int>
}
~HashTable() {
delete [] table;
}
// IMPLEMENT INSERT, SEARCH, and REMOVE as the comments says:
void insert(int data) {
/**
* Inserts the data into the correct index. For insertion, we want O(1) time, so we will insert in the front of the list.
*
* This function will simply do the followings:
* 1. hash the data key to get the appropriate index in the hash table
* 2. insert the data key into the appropriate index
* (for inserting the data in the beginning of the STL list, we use the .push_front() method in the list,
* the push_front() method will accept the data we want to insert)
*
* @param data, int, the data we want to insert in the hash table
*
*/
}
bool search(int data){
/**
* Searches whether the data is in the hash table, if yes return true, otherwise return false.
*
* This function will do the followings:
* 1. hash the data key to get the appropriate index in the hash table
* 2. Use the find() function from STL algorithm library to search for the data
* The syntax is as follows:
* find(first_iterator, last_iterator, x)
* This will return an iterator to the first occruence of the data in the STL list/vectpr,
* if the element is present in the list/vector, the iterator will be pointing to that data item,
* if the element is not found in the list/vector, it will point to the last address of the list/vector, that is ((name_of_vector/list).end())
*
* The iterator type should be:
* list<int>::iterator it = find(first_iterator, last_iterator, x);
* But for convience, other than writing such long and complicated type, we can replace it with auto, that is:
* auto it = find(first_iterator, last_iterator, x);
*
* If you use a STL list, the first iterator will be name_of_list.begin(), the last iterator will be name_of_list.end()
* In our case, name_of_list will be table[index], assuming index is the hash value we get from the hash function.
* 3. As mentioned in the point2, if the element is not found in the list/vector, the iterator will point to the last address of the list/vector.
* so if the iterator is the end of the list, this function will return false,
* otherwise, it will return true (because it is pointing to some found item).
*
*/
}
void remove(int data) {
/**
* Removes the data if it exists in the list, if it does not exist, end the function.
* (As we still need to find that data before we remove, so this function is pretty similiar to the search() function.)
*
* This function will do the followings:
* 1. Same as search() point 1
* 2. Same as search() point 2
* 3. If the iterator is the end of the list, it will return the function (cancel the remove),
* otherwise, if the data exists, we will use the name_of_list.erase(iterator) to remove the data in the hash table
*
*/
}
Correct output of the program:
// Hash Table ht1 (table size: 10)
| 0 | -> 10 -> 20
| 1 | ->
| 2 | -> 72 -> 92 -> 52
| 3 | ->
| 4 | ->
| 5 | ->
| 6 | -> 36
| 7 | ->
| 8 | -> 28 -> 48
| 9 | ->
Search 45 in ht1: 0
Search 92 in ht1: 1
// Hash Table ht2 (table size: 7)
| 0 | -> 28
| 1 | -> 92 -> 36
| 2 | -> 72
| 3 | -> 10 -> 52
| 4 | ->
| 5 | ->
| 6 | -> 48 -> 20
Search 12 in ht2: 0
Search 50 in ht2: 0
// Hash Table ht3 (table size: 13)
| 0 | -> 52
| 1 | -> 92
| 2 | -> 28
| 3 | ->
| 4 | ->
| 5 | ->
| 6 | ->
| 7 | -> 72 -> 20
| 8 | ->
| 9 | -> 48
| 10 | -> 10 -> 36
| 11 | ->
| 12 | ->
Search 36 in ht3: 1
Search 52 in ht3: 1
// Hash Table ht4 (table size: 3)
| 0 | -> 3 -> 102 -> 12
| 1 | -> 103 -> 13 -> 1
| 2 | -> 2 -> 101 -> 11
Search 101 in ht4: 1
Search 0 in ht4: 0 (REMOVED)