Create a C++ Program: Assignment description: Implement a Hash Table of strings.
ID: 3578491 • Letter: C
Question
Create a C++ Program:
Assignment description: Implement a Hash Table of strings. The table is stored as an array of pointers to list of strings.
Tasks:
A. Write a class that implements a Hash Table of strings. The table is stored as an array of pointers to lists of strings.
Your Hash Table class should include the following functions:
- A function insert(s) that adds the string to the table, if it is not already there.
- A function remove(s) that removes the string from the table if it is there.
- A function find(s) that returns the string if the string s is in the table.
- A function size() that returns the number of words in the dictionary.
- A helper hash function to compute the hash code of a string. The function takes a string as its parameter, and adds up the ASCII values of all the characters in that string to get an integer as the hash value. You can convert the string into lowercases before the hashing just for simplicity.
Here is one possible hashing implementation using the string class in STL:
int hash( const string s )
{
int value = 0;
for (int i = 0; i < s.length(); i++ )
value += static_cast(s.[i]);
return (value % table.size);
}
- a constructor that accepts the size of the table as a parameter.
B. Write a test driver program that uses (and tests) your hash table class.
1. Build the dictionary. The program reads strings from a text file that contains the words to be inserted into the dictionary.
- Create an array of appropriate size to store these words. Try to keep load factor below 60% to avoid search inefficiency. Use the separate chaining method to resolve the collision.
- Keep a counter to save the number of collisions that occur during the building process. Print out the number of collisions and number of words at the end of building.
2. Exercise the ADT operations: It prompts the user to enter words for searching or removing. Print messages about the result of operations accordingly.
3. Example text file for testing: aberration, abhor, acquiesce, alacrity, amiable, appease, arcane, avarice, brazen, brusque, cajole, callous, candor, chide, circumspect, clandestine, coerce, coherent, complacency, confidant, connive, cumulative, debase, decry
Explanation / Answer
A
COPYABLE CODE
PROGRAM CODE
HashTable12.cpp
#include "HashTable12.h"
HashTable12::HashTable12( int tableLengthval )
{
if (tableLengthval <= 0) tableLengthval = 13;
array = new LinkedList12[ tableLengthval ];
length = tableLengthval;
}
int HashTable12::hash( string itemKeyval )
{
int value12 = 0;
for ( int k = 0; k < itemKeyval.length(); k++ )
value12 += itemKeyval[k];
return (value12 * itemKeyval.length() ) % length;
}
// Adds an item
void HashTable12::insertItemval( Item1 * newItemval )
{
int indexval = hash( newItemval -> keyval );
array[ indexval ].insertItemval( newItemval );
}
bool HashTable12::removeItemval( string itemKeyval )
{
int indexval = hash( itemKeyval );
return array[ indexval ].removeItemval( itemKeyval );
}
Item1 * HashTable12::getItemByKeyval( string itemKeyval )
{
int indexval = hash( itemKeyval );
return array[ indexval ].getItem( itemKeyval );
}
void HashTable12::printTableval()
{
cout << " Hash Table value: ";
for ( int k = 0; k < length; k++ )
{
cout << "Bucket table " << k + 1 << ": ";
array[k].printList();
}
}
void HashTable12::printHistogramval()
{
cout << " Hash Table values ";
cout << getNumberOfItems() << " Items total value ";
for ( int k = 0; k < length; k++ )
{
cout << i + 1 << ": ";
for ( int d = 0; d < array[k].getLength(); d++ )
cout << " X";
cout << " ";
}
}
int HashTable12::getLength()
{
return length;
}
int HashTable12::getNumberOfItems()
{
int itemCountval = 0;
for ( int k = 0; k < length; k++ )
{
itemCountval += array[k].getLength();
}
return itemCountval;
}
HashTable12::~HashTable12()
{
delete [] array;
}
HashTable12.h
#ifndef HashTable12_h
#define HashTable12_h
#include "LinkedList12.h"
class HashTable12
{
private:
LinkedList12 * array;
int length;
int hash( string itemKeyval );
public:
//13 length
HashTable12( int tableLengthval = 13 );
// insert item.
void insertItemval( Item1 * newItemval );
// Returns .
bool removeItemval( string itemKeyval );
Item1 * getItemByKeyval( string itemKeyval );
// Display
void printTableval();
// Prints a histogram
void printHistogramval();
// Returns
int getLength();
int getNumberOfItems();
~HashTable12();
};
#endif
LinkedList12.cpp
#include "LinkedList12.h"
LinkedList12::LinkedList12()
{
head = new Item1;
head -> next = NULL;
length = 0;
}
// Inserts
void LinkedList12::insertItemval( Item1 * newItemval )
{
if (!head -> next)
{
head -> next = newItemval;
length++;
return;
}
Item1 * p1 = head;
Item1 * q1 = head;
while (q1)
{
p1 = q1;
q1 = p1 -> next;
}
p1 -> next = newItemval;
newItemval -> next = NULL;
length++;
}
bool LinkedList12::removeItemval( string itemKeyval )
{
//return value
if (!head -> next) return false;
Item1* p1 = head;
Item1* q1 = head;
while (q1)
{
if (q1 -> keyval == itemKeyval)
{
p1 -> next = q1 -> next;
delete q1;
length--;
return true;
}
p1 = q1;
q1 = p1 -> next;
}
return false;
}
Item1 * LinkedList12::getItem( string itemKeyval )
{
Item1 * p1 = head;
Item1 * q1 = head;
while (q1)
{
p1 = q1;
if ((p1 != head) && (p1 -> keyval == itemKeyval))
return p1;
q1 = p1 -> next;
}
return NULL;
}
//print data
void LinkedList12::printList()
{
//length value
if (length == 0)
{
cout << " { } ";
return;
}
Item1 * p1 = head;
Item1 * q1 = head;
cout << " { ";
while (q1)
{
p1 = q1;
if (p1 != head)
{
cout << p1 -> keyval;
if (p1 -> next) cout << ", ";
else cout << " ";
}
q1 = p1 -> next;
}
cout << "} ";
}
int LinkedList12::getLength()
{
return length;
}
LinkedList12::~LinkedList12()
{
Item1 * p1 = head;
Item1 * q1 = head;
while (q1)
{
p1 = q1;
q1 = p1 -> next;
if (q1) delete p1;
}
}
LinkedList12.h
#ifndef LinkedList12_h
#define LinkedList12_h
#include <iostream>
#include <string>
using namespace std;
struct Item1
{
string keyval;
Item1 * next;
};
class LinkedList12
{
private:
Item1 * head;
int length;
public:
LinkedList12();
// Inserts
void insertItemval( Item1 * newItemval );
bool removeItemval( string itemKeyval );
Item1 * getItem( string itemKeyval );
void printList();
int getLength();
~LinkedList12();
};
#endif
main.cpp
#include "HashTable12.h"
#include <stddef.h>
#include <algorithm>
#include <vector>
int main()
{
// Create 26 Items
Item1 * A = new Item1 {"Apple", NULL};
Item1 * B = new Item1 {"Boy", NULL};
Item1 * C = new Item1 {"Cat", NULL};
Item1 * D = new Item1 {"Doll", NULL};
Item1 * E = new Item1 {"English", NULL};
Item1 * F = new Item1 {"Floor", NULL};
Item1 * G = new Item1 {"Good", NULL};
Item1 * H = new Item1 {"Horse", NULL};
Item1 * I = new Item1 {"Imple", NULL};
Item1 * J = new Item1 {"Juice", NULL};
Item1 * K = new Item1 {"Kanda", NULL};
Item1 * L = new Item1 {"Lion", NULL};
Item1 * M = new Item1 {"Moon", NULL};
Item1 * N = new Item1 {"Nine", NULL};
Item1 * O = new Item1 {"Ocean", NULL};
Item1 * P = new Item1 {"Pongal", NULL};
Item1 * Q = new Item1 {"Quality", NULL};
Item1 * R = new Item1 {"Random", NULL};
Item1 * S = new Item1 {"Stock", NULL};
Item1 * T = new Item1 {"Time", NULL};
Item1 * U = new Item1 {"Umbrela", NULL};
Item1 * V = new Item1 {"Vote", NULL};
Item1 * W = new Item1 {"When", NULL};
Item1 * X = new Item1 {"Xerox", NULL};
Item1 * Y = new Item1 {"Young", NULL};
Item1 * Z = new Item1 {"Zebra", NULL};
HashTable12 table1;
table1.insertItemval(A);
table1.insertItemval(B);
table1.insertItemval(C);
table1.printTableval();
table1.printHistogramval();
// Remove
table1.removeItemval("Apple");
table1.printTableval();
table1.printHistogramval();
// Add
table1.insertItemval(D);
table1.insertItemval(E);
table1.insertItemval(F);
table1.insertItemval(G);
table1.insertItemval(H);
table1.insertItemval(I);
table1.insertItemval(J);
table1.insertItemval(K);
table1.insertItemval(L);
table1.insertItemval(M);
table1.insertItemval(N);
table1.insertItemval(O);
table1.insertItemval(P);
table1.insertItemval(Q);
table1.insertItemval(R);
table1.insertItemval(S);
table1.insertItemval(T);
table1.insertItemval(U);
table1.insertItemval(V);
table1.insertItemval(W);
table1.insertItemval(X);
table1.insertItemval(Y);
table1.insertItemval(Z);
table1.printTableval();
table1.printHistogramval();
Item1 * result = table1.getItemByKeyval("Stock");
cout << result -> keyval << endl;
return 0;
}