using C++: Lab 6: Practicing LinkedList Applications In this lab, you will be us
ID: 3573214 • Letter: U
Question
using C++:
Lab 6: Practicing LinkedList Applications
In this lab, you will be using a vector (or array) of linked lists to implement a hash table.
A hash table is a data structure in which the location of an item is determined directly as a function of the item rather than by a sequence of trial-and-error comparisons and is used when fast searching is needed. Ideally, search time is O(1); i.e., it is constant and independent of the number of items to be searched. Here we will use the method known as chaining, in which the hash table is implemented using a vector (or array) of linked lists.
When an item is to be inserted into the table, a hashing function h is applied to the item to determine where it is to be placed in the table; for example, a common one is
h(item) = item % table-size
where the table-size is usually taken to be a prime number (to scatter ("hash") the items throughout the table. For non-numeric items, numeric codes e,g., ASCII are used. The linked list at location h(item) is searched for the item. If it is not found, the item is inserted into the linked list at this location.
Design a HashTable class for processing hash tables. Use a small prime number such as 11 or 13 for the table size. Two of the basic operations it must provide are:
1. Insert an item into the hash table as just described. It doesn't matter where in the linked list it is inserted.
2. Display each index in the hash table and a list of all the items stored at that location.
For this particular problem, the hash table is to store strings and use the following hash function:
h(str) = (sum of the ASCII codes of the first 3 characters of str) % table_size.
For strings with fewer than 3 characters, just use whatever characters there are in the string.
Assignment: Use a vector (or array) of linked lists to implement a hash table. You are only allowed to use the linklist that we learned in this Chapter. You are not allowed to use STL list library.
Write a driver program to test your class. It should read several strings, storing each in the hash table. After all the strings are input, it should display the hash table by listing the indices and for each index, a list of all the words in the linked list at that location (sort of like the diagram above).
After you have thoroughly tested your class, then use it to process the strings in the piece of text:
DEAR MARLIN
THE AARDVARKS AND THE CAMELS WERE MISTAKENLY SHIPPED TO THE AZORES
SORRY ABOUT THAT
SINCERELY JIM
PS ANTS AND BATS AND COWS AND CATS ARE ANIMALS
COWS ARE BIG BUT ANTS ARE SMALL AND BATS AND CATS ARE IN BETWEEN
Data file:
Explanation / Answer
Solution:
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int TABLE_SIZE = 128;
class HashNode
{
public:
int key;
int value;
HashNode* next;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
this->next = NULL;
}
};
class HashMap
{
private:
HashNode** htable;
public:
HashMap()
{
htable = new HashNode*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
htable[i] = NULL;
}
~HashMap()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
HashNode* entry = htable[i];
while (entry != NULL)
{
HashNode* prev = entry;
entry = entry->next;
delete prev;
}
}
delete[] htable;
}
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
// Insert an item to the Hash Table
void Insert(int key, int value)
{
int hash_val = HashFunc(key);
HashNode* prev = NULL;
HashNode* entry = htable[hash_val];
while (entry != NULL)
{
prev = entry;
entry = entry->next;
}
if (entry == NULL)
{
entry = new HashNode(key, value);
if (prev == NULL)
{
htable[hash_val] = entry;
}
else
{
prev->next = entry;
}
}
else
{
entry->value = value;
}
}
// Removes an item from the list by item key.
// Returns a NULL pointer if no match is found.
void Remove(int key)
{
int hash_val = HashFunc(key);
HashNode* entry = htable[hash_val];
HashNode* prev = NULL;
if (entry == NULL || entry->key != key)
{
cout << "No Element found at key " << key << endl;
return;
}
while (entry->next != NULL)
{
prev = entry;
entry = entry->next;
}
if (prev != NULL)
{
prev->next = entry->next;
}
delete entry;
cout << "Element Deleted" << endl;
}
// Searches for an item by its key.
// Returns a reference to first match.
// Returns a NULL pointer if no match is found.
int Search(int key)
{
bool flag = false;
int hash_val = HashFunc(key);
HashNode* entry = htable[hash_val];
while (entry != NULL)
{
if (entry->key == key)
{
cout << entry->value << " ";
flag = true;
}
entry = entry->next;
}
if (!flag)
return -1;
}
};
int main()
{
HashMap hash;
int key, value;
int choice;
while (1)
{
cout << " ----------------------" << endl;
cout << "Operations on Hash Table" << endl;
cout << " ----------------------" << endl;
cout << "1.Insert element into the table" << endl;
cout << "2.Search element from the key" << endl;
cout << "3.Delete element at a key" << endl;
cout << "4.Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;
switch (choice)
{
case 1:
cout << "Enter element to be inserted: ";
cin >> value;
cout << "Enter key at which element to be inserted: ";
cin >> key;
hash.Insert(key, value);
break;
case 2:
cout << "Enter key of the element to be searched: ";
cin >> key;
cout << "Element at key " << key << " : ";
if (hash.Search(key) == -1)
{
cout << "No element found at key " << key << endl;
continue;
}
break;
case 3:
cout << "Enter key of the element to be deleted: ";
cin >> key;
hash.Remove(key);
break;
case 4:
exit(1);
default:
cout << " Enter correct option ";
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.