Week 7 Homework – Hashing: 1. (20%) The following numbers are to be inserted into an unsorted list in the order shown: 102, 206, 3004, 400, 5009, 600, 59 The hash function is Key % 10. Linear probing...

Need whatever is required in the pdf file.


Week 7 Homework – Hashing: 1. (20%) The following numbers are to be inserted into an unsorted list in the order shown: 102, 206, 3004, 400, 5009, 600, 59 The hash function is Key % 10. Linear probing is used to resolve collisions: (Key + 1) % 10. a. (10%) Please insert the numbers to the following array (table). Note that, initially, the array is initialized with -777. In other words, -777 indicates that the spot is empty. Only overwrite the default values with your values inserted. -777 -777 -777 -777 -777 -777 -777 -777 -777 -777 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] b. (5%) Continue from part 1a, i.e., copy the table from 1a, then, please remove a number 102 from the list. Please place -999 to replace the removed number. In other words, -999 indicates that the spot was not empty. -777 -777 -777 -777 -777 -777 -777 -777 -777 -777 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] c. (5%) Continue from part 1b, i.e., copy the table from 1b, then, please add a number 299 to the list. -777 -777 -777 -777 -777 -777 -777 -777 -777 -777 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] Place the completed three (3) tables in your screenshot Word document for credit. 2. (80%) The specification of an InsertItem function is given as follows: Extend the UnsortedList class to include the member function InsertItem that add an item to an unsorted list using the given hash function. Use the given (linear) probing function to resolve any collision. (Hint: see the SearchItem() function to see how the hash function and (linear) probing function are used) a. (65%) Run the driver file to test your function b. (15%) Take screenshot(s) showing the runtime result Specification Prototype Hash Solution - Student/ItemType.cpp Hash Solution - Student/ItemType.cpp // The following definitions go into file ItemType.cpp. #include "ItemType.h" using namespace std; ItemType::ItemType() {    value = 0; } void ItemType::Initialize(int number)  {   value = number; } int ItemType::GetValue() const {     return value; } Hash Solution - Student/ItemType.h #pragma once // The following declarations go into file // ItemType.h. const int MAX_ITEMS = 10; class ItemType { public: ItemType(); void Initialize(int number); int GetValue() const; private: int value; }; Hash Solution - Student/listDriver.cpp Hash Solution - Student/listDriver.cpp // Test driver #include  #include  #include "unsorted.h" using namespace std; void IsFullMessage(bool isFull); void PrintList(UnsortedList list, string message); int main() {     int location;     int number;     ItemType item;     UnsortedList list;     bool found;     const int ARRAY_SIZE = 6;     int myList[ARRAY_SIZE] = {102, 206, 3004, 400, 5009, 600};     //PutItem     //Add numbers to the list     for(int i=0; i<><><>< endl;             break;=""         }=""     }=""     //isfull=""     //check and see if the list is full=""     isfullmessage(list.isfull());=""     //print the list=""     printlist(list, "add");=""     //getlength=""     //find the length of the list  =""><><>< endl;     //find an item with value =" 3004"     number =" 3004;"     item.initialize(number);=""     list.searchitem(item, found, location);=""><><><><><>< endl;     //find an item with value =" 123"     number =" 123;"     item.initialize(number);=""     list.searchitem(item, found, location);=""><><><><><>< endl;     //add an item with value =" 59"     if (!list.isfull())=""     {=""         number =" 59;"         item.initialize(number);=""         list.insertitem(item);=""         //print the list=""><><>< ": ";         printlist(list, "add");=""         //getlength=""         //find the length of the list  =""><><>< endl;     }=""     else=""     {=""><>< endl;     }=""     //delete an item with value =" 102"     number =" 102;"     item.initialize(number);=""     list.deleteitem(item);=""     //print the list=""><><>< ": ";     printlist(list, "delete");=""     //getlength=""     //find the length of the list  =""><><>< endl;     //add an item with value =" 299"     if (!list.isfull())=""     {=""         number =" 299;"         item.initialize(number);=""         list.insertitem(item);=""         //print the list=""><><>< ": ";         printlist(list, "add");=""         //getlength=""         //find the length of the list  =""><><>< endl;     }=""     else=""     {=""><>< endl;     }=""     //find an item with value =" 59"     number =" 59;"     item.initialize(number);=""     list.searchitem(item, found, location);=""><><><><><>< endl;     //isfull=""     //check and see if the list is full="">< endl;     isfullmessage(list.isfull());=""><><>< endl;     return 0;="" }="" void isfullmessage(bool isfull)=""  pre:  isfull has been initialized.         =""  post: message has been displayed to the screen. ="" {=""     if (isfull)=""     {=""><>< endl;     }=""     else =""     {=""><>< endl;     }="" }="" void printlist(unsortedlist list, string message)="" {=""     //print the list="">< endl;><><><>< endl;>< "list:";     list.print();="" }="" hash="" solution="" -="" student/unsorted.cpp="" hash="" solution="" -="" student/unsorted.cpp=""  implementation file for unsorted.h="" #include "unsorted.h"="" unsortedlist::unsortedlist()="" {=""   length =" 0;"   //fill the entire array with empty_item:=""   for (itemtype& value : info)=""   {=""       value.initialize(empty_item);=""   }="" }="" bool unsortedlist::isfull() const="" {=""   return (length ="= MAX_ITEMS);" }="" int unsortedlist::getlength() const="" {=""   return length;="" }="" int unsortedlist::hash(itemtype item) const="" {=""     return (item.getvalue() % max_items);="" }="" itemtype unsortedlist::searchitem(itemtype item, bool& isfound, int& location)="" {=""     int startloc;=""     bool moretosearch =" true;"     bool isemptyfound;=""     startloc =" Hash(item);"     location =" startLoc;"     do=""     {=""         isfound =" info[location].GetValue() == item.GetValue();"         isemptyfound =" info[location].GetValue() == EMPTY_ITEM;"         if (isfound || isemptyfound)=""         {=""             moretosearch =" false;"         }=""         else=""         {=""             location =" Probing(location);"         }=""     } while (location !=" startLoc && moreToSearch);"     if (isfound)=""     {=""         item =" info[location];"     }=""     else=""     {=""         location =" -1;"     }=""     return item;="" }="" void unsortedlist::insertitem(itemtype item)="" {=""     //### add your code here ###="" }="" void unsortedlist::deleteitem(itemtype item)="" {=""     bool found =" false;"     int location;=""     searchitem(item, found, location);=""     if (found)=""     {=""         info[location].initialize(deleted_item);=""         length--;=""     }="" }="" void unsortedlist::print() const="" {=""     std::string separator =" " | ";">< separator;     for (itemtype item : info)=""     {=""><>< separator;     }="">< std::endl; }="" int unsortedlist::probing(int location) const="" {=""     //linear:=""     return (location + rehash_constant) % max_items;="" }="" hash="" solution="" -="" student/unsorted.h="" #pragma="" once="" #include="" "itemtype.h"="" #include=""> // File ItemType.h must be provided by the user of this class. // ItemType.h must contain the following definitions: // MAX_ITEMS: the maximum number of items on the list // ItemType: the definition of the objects on the list const int EMPTY_ITEM = -777; const int DELETED_ITEM = -999; const int REHASH_CONSTANT = 1; class UnsortedList { public: UnsortedList(); // Constructor bool IsFull() const; // Function: Determines whether list is full. // Pre: List has been initialized. // Post: Function value = (list is full) int GetLength() const; // Function: Determines the number of elements in list. // Pre: List has been initialized. // Post: Function value = number of elements in list int Hash(ItemType item) const; // Function: Determines the location of an item. // Pre: List has been initialized. // Post: Function value = item's value % MAX_ITEMS ItemType SearchItem(ItemType item, bool& isFound, int& location); // Function: Retrieves list element whose key matches item's key (if // present). // Pre: List has been initialized. // Key member of item is initialized. // item does not equal to EMPTY_ITEM or DELETED_ITEM // Post: If there is an element someItem whose key matches // item's key, then isFound = true, someItem is returned, location (index) of someItem is returned. // otherwise isFound = false, item is returned, -1 is returned for location. // List is unchanged. void InsertItem(ItemType item); // Function: Adds item to list. // Pre: List has been initialized. // List is not full. // item is not in list. // item does not equal to EMPTY_ITEM or DELETED_ITEM // Post: item is in list. void DeleteItem(ItemType item); // Function: Deletes the element whose key matches item's key. // Pre: List has been initialized. // Key member of item is initialized. // One and only one element in list has a key matching item's key. // item does not equal to EMPTY_ITEM or DELETED_ITEM // Post: No element in list has a key matching item's key. void Print() const; // Function: Print the values of the list to console. // Pre: List has been initialized. // Post: The values of the list are printed to the console. int Probing(int location) const; // Function: Determines the location of an item with linear probing. // Pre: Valid locaion is provided // Post: Function value = location of an item private: int length; ItemType info[MAX_ITEMS]; };