#include #include class Hash { static const int tableSize = 50; struct item { std::string name; std::string location; item *next; }; item *hashTable[tableSize]; public: Hash(); int hash(std::string key); void AddEntry(std::string name, std::string location); int ItemsinIndex(int index); void TableDisplay(); void DisplayItemsinIndex(int index); void LocationFinder(std::string name); void ItemRemove(std::string name); }; int main(int argc, char *argv[]) { return 0; } Hash::Hash() { for (size_t i = 0; i < tableSize; ++i) { hashTable[i] = new item; hashTable[i]->name = "empty"; hashTable[i]->location = "empty"; hashTable[i]->next = NULL; } } int Hash::hash(std::string key) { int hash = 0; int index; for (size_t i = 0; i < key.length(); ++i) { hash += ((int)key[i]) * 10; } index = hash % tableSize; return index; } void Hash::AddEntry(std::string name, std::string location) { int index = hash(name); if (hashTable[index]->name == "empty") { hashTable[index]->name = name; hashTable[index]->location = location; } else { item* ptr = hashTable[index]; item* n = new item; n->name = name; n->location = location; n->next = NULL; while (ptr->next != NULL) { ptr = ptr->next; } ptr->next = n; } } int Hash::ItemsinIndex(int index) { int ct = 0; if (hashTable[index]->name == "empty") { return ct; } else { ++ct; item* ptr = hashTable[index]; while (ptr->next != NULL) { ++ct; ptr = ptr->next; } } return ct; } void Hash::TableDisplay() { int num; for (int i = 0; i < tableSize; ++i) { num = ItemsinIndex(i); std::cout << "Index: " << i << '\n'; std::cout << hashTable[i]->name << '\n'; std::cout << hashTable[i]->location << '\n'; std::cout << "number of items: " << num << '\n'; } } void Hash::DisplayItemsinIndex(int index) { item* ptr = hashTable[index]; if (ptr->name == "empty") { std::cout << "Index: " << index << " is empty."; } else { std::cout << "Index: " << index << " contains item.\n"; while (ptr != NULL) { std::cout << ptr->name << '\n'; std::cout << ptr->location << '\n'; ptr = ptr->next; } } } void Hash::LocationFinder(std::string name) { int index = hash(name); bool nameFound = false; std::string location; item* ptr = hashTable[index]; while (ptr != NULL) { if (ptr->name == name) { nameFound = true; location = ptr->location; } ptr = ptr->next; } if (nameFound == true) { std::cout << "Location found: " << location << '\n'; } else { std::cout << name << "'s location not found.\n"; } } void Hash::ItemRemove(std::string name) { int index = hash(name); item* delPtr; item* p1; item* p2; if (hashTable[index]->name == "empty" && hashTable[index]->location == "empty") { std::cout << name << " not found.\n"; } else if(hashTable[index]->name == name && hashTable[index]->next == NULL) { hashTable[index]->name = "empty"; hashTable[index]->location = "empty"; } else if (hashTable[index]->name == name) { delPtr = hashTable[index]; hashTable[index] = hashTable[index]->next; delete delPtr; std::cout << name << " was removed.\n"; } else { p1 = hashTable[index]->next; p2 = hashTable[index]; while (p1 != NULL && p1->name != name) { p2 = p1; p1 = p1->next; } if (p1 == NULL) { std::cout << name << " not found.\n"; } else { delPtr = p1; p1 = p1->next; p2->next = p1; delete delPtr; std::cout << name << " was removed.\n"; } } }

Hash Table with Linked List