C HashTable.h X C HashTable.h> HashTable> insert(int) 1 #ifndef HashTable_H 2 #define HashTable_H 3 4 #include
Posted: Tue Jul 12, 2022 8:17 am
- C Hashtable H X C Hashtable H Hashtable Insert Int 1 Ifndef Hashtable H 2 Define Hashtable H 3 4 Include Iostream 1 (114.53 KiB) Viewed 22 times
/*** Inserts the data into the correct index. For insertion, we wantO(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 hashtable* 2. insert the data key into the appropriate index* (for inserting the data in the beginning of the STL list, we usethe .push_front() method in the list,* the push_front() method will accept the data we want toinsert)** @param data, int, the data we want to insert in the hashtable**/
}
false. *
* * *
* * * *
The iterator type should be:list<int>::iterator it = find(first_iterator, last_iterator,x);
But for convience, other than writing such long and complicatedtype, we can replace it with auto, that is:
* otherwise, it will return true (because it is pointingto some found item). **/
}
/*** 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 thisfunction is pretty similiar
* 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 thefunction (cancel the
the data in the hash table *
*/
}
Requirements:
1) Follow the comments of the functions to complete thecode of insert(), search()and remove().
2) When you finish the insert(),search()and remove()functions, run the code in main.cpp, butdo not change the testing code in main.cpp.
3) Rename the execution file to hashing.
Correct output of the program:
| 0|->52 | 1|->92 | 2|->28 | 3|->
| 4|->| 5|->| 6|->| 7|->72->20 | 8|->
| 9|->48| 10 | -> 10 -> 36 | 11 | ->| 12 | ->
- C Hashtable H X C Hashtable H Hashtable Insert Int 1 Ifndef Hashtable H 2 Define Hashtable H 3 4 Include Iostream 2 (114.53 KiB) Viewed 22 times
C HashTable.h X C HashTable.h> HashTable> insert(int) 1 #ifndef HashTable_H 2 #define HashTable_H 3 4 #include <iostream> 5 #include <string> 6 #include <list> // STL (Standard Template Library) list, Since lists use both forward and backward pointers, they implement doubly 7 #include <algorithm> // STL algorihtms, we use the find() function to support STL list 8 using namespace std; // This means we can use all the things within the "std" namespace, e.g. std:: list 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 20 class HashTable { private: list<int> * table; 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> } // instead of allocating a fix size like table [10], this is allocating it in the heap memory HashTable(int size) { // customized-size constructor this->size = size; table = new list<int> [this->size]; // array of list<int> ~HashTable() { } delete [] table; void insert(int data) { /***** * Inserts the data into the correct index. For insertion, we want 0(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 7 incent the dots kou into the opereeristo index
C HashTable.h X C HashTable.h> HashTable> insert(int) 1 #ifndef HashTable_H 2 #define HashTable_H 3 4 #include <iostream> 5 #include <string> 6 #include <list> // STL (Standard Template Library) list, Since lists use both forward and backward pointers, they implement doubly 7 #include <algorithm> // STL algorihtms, we use the find() function to support STL list 8 using namespace std; // This means we can use all the things within the "std" namespace, e.g. std:: list 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 20 class HashTable { private: list<int> * table; 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> } // instead of allocating a fix size like table [10], this is allocating it in the heap memory HashTable(int size) { // customized-size constructor this->size = size; table = new list<int> [this->size]; // array of list<int> ~HashTable() { } delete [] table; void insert(int data) { /***** * Inserts the data into the correct index. For insertion, we want 0(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 7 incent the dots kou into the opereeristo index
C HashTable.h X C HashTable.h> HashTable > insert(int) 33 void insert(int data) { 34 /**** 35 * Inserts the data into the correct index. For insertion, we want 0(1) time, so we will insert in the front of the list. * 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 *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) { / xxx * 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_ 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 so if the iterator is the end of the list, this function will return false, *
C HashTable.h X C HashTable.h> HashTable> insert(int) DO 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 }; #endif TunC LION. funkcion In our cast, hallit_UT_LIST WILL DE Lautelanuext, assuming index is the last value we get from the hasi * 3. As mentioned in the point2, if the element is not found in the list/vector, the iterator will point to the last address 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. * */ } void print_hash_table() { int num=to_string(size-1).length(); // because 10 is one digit 0-9, 100 is two digits 0-99 for (int i = 0; i < size; i++) { printf(" %d | →> ", num, i); // variable padding for (auto it = table.begin(); it != table.end(); it++) { // as long as it is not the list.end(), then continue if (it != --(table.end())) cout << *it << " -> "'; else cout << *it ; } cout << endl;
C HashTable.h € main.cpp > ... 1 #include <iostream> 2 #include "HashTable.h" 3 using namespace std; 4 int main() { 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 G+main.cpp X 35 36 37 38 30 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; ht? print hash table(): BES sang
C HashTable.h G+ main.cpp > ... 39 40 41 42 43 44 45 46 47 48 49 50 51 52 3455 55 望 58 59 012B科56印丽的U1234 75 76 56 57 66 67 68 69 70 71 72 73 74 G+ main.cpp X 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);
C HashTable.h G+ main.cpp > ... 76 77 78 79 80 81 82 83 84 85 86 87 88 89 } G+ main.cpp x 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 :4: " << t4.search (101) << endl; cout << "Search 0 in ht4: " << ht4.search(0) << (REMOVED)" << endl; cout << endl << endl;
Posted: Tue Jul 12, 2022 8:17 am
- C Hashtable H X C Hashtable H Hashtable Insert Int 1 Ifndef Hashtable H 2 Define Hashtable H 3 4 Include Iostream 1 (114.53 KiB) Viewed 22 times
}
false. *
* * *
* * * *
The iterator type should be:list<int>::iterator it = find(first_iterator, last_iterator,x);
But for convience, other than writing such long and complicatedtype, we can replace it with auto, that is:
* otherwise, it will return true (because it is pointingto some found item). **/
}
/*** 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 thisfunction is pretty similiar
* 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 thefunction (cancel the
the data in the hash table *
*/
}
Requirements:
1) Follow the comments of the functions to complete thecode of insert(), search()and remove().
2) When you finish the insert(),search()and remove()functions, run the code in main.cpp, butdo not change the testing code in main.cpp.
3) Rename the execution file to hashing.
Correct output of the program:
| 0|->52 | 1|->92 | 2|->28 | 3|->
| 4|->| 5|->| 6|->| 7|->72->20 | 8|->
| 9|->48| 10 | -> 10 -> 36 | 11 | ->| 12 | ->
- C Hashtable H X C Hashtable H Hashtable Insert Int 1 Ifndef Hashtable H 2 Define Hashtable H 3 4 Include Iostream 2 (114.53 KiB) Viewed 22 times
C HashTable.h X C HashTable.h> HashTable> insert(int) 1 #ifndef HashTable_H 2 #define HashTable_H 3 4 #include <iostream> 5 #include <string> 6 #include <list> // STL (Standard Template Library) list, Since lists use both forward and backward pointers, they implement doubly 7 #include <algorithm> // STL algorihtms, we use the find() function to support STL list 8 using namespace std; // This means we can use all the things within the "std" namespace, e.g. std:: list 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 20 class HashTable { private: list<int> * table; 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> } // instead of allocating a fix size like table [10], this is allocating it in the heap memory HashTable(int size) { // customized-size constructor this->size = size; table = new list<int> [this->size]; // array of list<int> ~HashTable() { } delete [] table; void insert(int data) { /***** * Inserts the data into the correct index. For insertion, we want 0(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 7 incent the dots kou into the opereeristo index
C HashTable.h X C HashTable.h> HashTable > insert(int) 33 void insert(int data) { 34 /**** 35 * Inserts the data into the correct index. For insertion, we want 0(1) time, so we will insert in the front of the list. * 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 *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) { / xxx * 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_ 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 so if the iterator is the end of the list, this function will return false, *
C HashTable.h X C HashTable.h> HashTable> insert(int) DO 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 }; #endif TunC LION. funkcion In our cast, hallit_UT_LIST WILL DE Lautelanuext, assuming index is the last value we get from the hasi * 3. As mentioned in the point2, if the element is not found in the list/vector, the iterator will point to the last address 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. * */ } void print_hash_table() { int num=to_string(size-1).length(); // because 10 is one digit 0-9, 100 is two digits 0-99 for (int i = 0; i < size; i++) { printf(" %d | →> ", num, i); // variable padding for (auto it = table.begin(); it != table.end(); it++) { // as long as it is not the list.end(), then continue if (it != --(table.end())) cout << *it << " -> "'; else cout << *it ; } cout << endl;
C HashTable.h € main.cpp > ... 1 #include <iostream> 2 #include "HashTable.h" 3 using namespace std; 4 int main() { 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 G+main.cpp X 35 36 37 38 30 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; ht? print hash table(): BES sang
C HashTable.h G+ main.cpp > ... 39 40 41 42 43 44 45 46 47 48 49 50 51 52 3455 55 望 58 59 012B科56印丽的U1234 75 76 56 57 66 67 68 69 70 71 72 73 74 G+ main.cpp X 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);
C HashTable.h G+ main.cpp > ... 76 77 78 79 80 81 82 83 84 85 86 87 88 89 } G+ main.cpp x 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 :4: " << t4.search (101) << endl; cout << "Search 0 in ht4: " << ht4.search(0) << (REMOVED)" << endl; cout << endl << endl;