Must implement HashTable for thumbs up

Question Parts: -Implement Hash Table ADT(most important part) -Programming Exercise 1 -Programming Exercise 2 -Programming Exercise 3

Exercise 1 Your program should load username/password sets from the file password.dat and insert them into the hash table until end of file is reached. There is one username/password set(seperated by a tab) per line as shown in the following example.

jack broken.crown jill tumblin'down mary contrary bopeep sheep!lost Your program should present a login prompt, read one username, present a password prompt, read the password, and then print either "Authentication succesfsful" or "Authentification failure" as shown in the following examples.

Login: Jack Password: broken.crown Authentication successful

Exercise 2 Develop a hash static method implementation that will produce a minimal perfect hash for the following seven C++ reserved words: double, else, if, return, switch, void, and while. Use the following class to hold the strings.

class Identifier { string ident; public: void setKey(string newIdent) ( ident = newIdent; ) string getKey() const { return ident; } static unsigned in hash( const string& key ) return... };

Exercise 3 Create a function called double standardDeviation() const that returns the standard deviation for key distribution in the table. 1. Calculate and save the average number of data items per table entry. 2.For each table entry calculate and save (number of items - average number of items)² 3. Compute the sum of all the values calculated in step 2 4. Divide the result from Step 3 by n-1, where n is the number of hash table entries. 5. Calculate the square root of the result obtained in Step 4.

Provided Files "HashTree.h"

// HashTable.h

#ifndef HASHTABLE_H

#define HASHTABLE_H

#include

#include

using namespace std;

template

class HashTable {

public:

HashTable(int initTableSize);

HashTable(const HashTable& other);

HashTable& operator=(const HashTable& other);

~HashTable();

void insert(const DataType& newDataItem);

bool remove(const KeyType& deleteKey);

bool retrieve(const KeyType& searchKey, DataType& returnItem) const;

void clear();

bool isEmpty() const;

void showStructure() const;

double standardDeviation() const;

private:

void copyTable(const HashTable& source);

int tableSize;

vector> dataTable;

};

#endif // ifndef HASHTABLE_H

"Test10.cpp"

#include

#include

using namespace std;

#include "HashTable.cpp"

class TestData {

public:

TestData();

void setKey(const string& newKey);

string getKey() const;

int getValue() const;

static unsigned int hash(const string& str);

private:

string key;

int value;

static int count;

};

int TestData::count = 0;

TestData::TestData() : value(++count) {

}

void TestData::setKey(const string& newKey) {

key = newKey;

}

string TestData::getKey() const {

return key;

}

int TestData::getValue() const {

return value;

}

unsigned int TestData::hash(const string& str) {

unsigned int val = 0;

for (int i = 0; i < str.length(); ++i) {

val += str[i];

}

return val;

}

void print_help() {

cout << endl << "Commands:" << endl;

cout << " H : Help (displays this message)" << endl;

cout << " +x : Insert (or update) data item with key x" << endl;

cout << " -x : Remove the data element with the key x" << endl;

cout << " ?x : Retrieve the data element with the key x" << endl;

cout << " E : Empty table?" << endl;

cout << " C : Clear the table" << endl;

cout << " Q : Quit the test program" << endl;

}

int main(int argc, char **argv) {

HashTable table(7);

print_help();

do {

table.showStructure();

cout << endl << "Command: ";

char cmd;

cin >> cmd;

TestData item;

if (cmd == '+' || cmd == '?' || cmd == '-') {

string key;

cin >> key;

item.setKey(key);

}

switch (cmd) {

case 'H':

case 'h':

print_help();

break;

case '+':

table.insert(item);

cout << "Inserted data item with key ("

<< item.getKey() << ") and value ("

<< item.getValue() << ")" << endl;

break;

case '-':

if (table.remove(item.getKey())) {

cout << "Removed data item with key ("

<< item.getKey() << ")" << endl;

} else {

cout << "Could not remove data item with key ("

<< item.getKey() << ")" << endl;

}

break;

case '?':

if (table.retrieve(item.getKey(), item)) {

cout << "Retrieved data item with key ("

<< item.getKey() << ") and value ("

<< item.getValue() << ")" << endl;

} else {

cout << "Could not retrieve data item with key ("

<< item.getKey() << ")" << endl;

}

break;

case 'C':

case 'c':

cout << "Clear the hash table" << endl;

table.clear();

break;

case 'E':

case 'e':

cout << "Hash table is "

<< (table.isEmpty() ? "" : "NOT")

<< " empty" << endl;

break;

case 'Q':

case 'q':

return 0;

default:

cout << "Invalid command" << endl;

}

} while (1);

return 0;

}

"Show10.cpp"

// show10.cpp: contains implementation of the HashTable showStructure function

template

void HashTable::showStructure() const {

for (int i = 0; i < tableSize; ++i) {

cout << i << ": ";

dataTable[i].writeKeys();

}

}

"example.cpp"

// lab10-example1.cpp #include #include #include "HashTable.cpp"

using namespace std;

struct Account { int acctNum; // (Key) Account number float balance; // Account balance

int getKey () const { return acctNum; } static unsigned int hash(const int& key) { return abs( key ); } };

int main() { HashTable accounts(11); // List of accounts Account acct; // A single account int searchKey; // An account key

// Read in information on a set of accounts.

cout << endl << "Enter account information (num balance) for 5 accounts: " << endl;

for ( int i = 0; i < 5; i++ ) { cin >> acct.acctNum >> acct.balance; accounts.insert(acct); }

// Checks for accounts and prints records if found

cout << endl; cout << "Enter account number ( to end): "; while ( cin >> searchKey ) { if ( accounts.retrieve(searchKey,acct) ) cout << acct.acctNum << " " << acct.balance << endl; else cout << "Account " << searchKey << " not found." << endl; }

return 0; }

"test10std.cpp"

//--------------------------------------------------------------------

//

// Laboratory 10 test10std.cpp

//

// Test program for the standard deviation operation in the Hash Table ADT

//

//--------------------------------------------------------------------

#include

#include

#include

#include

#include "HashTable.cpp"

using namespace std;

struct Data

{

public:

void setKey ( string newKey ) { key = newKey; }

string getKey () const { return key; }

static unsigned int hash(const string& str)

{

// Uncomment each of these as you try them out.

//-----------------------

// Hash Algorithm 1

//-----------------------

// return 0;

//-----------------------

// Hash Algorithm 2

//-----------------------

// return int(str[0])*10 + str.length();

//-----------------------

// Hash Algorithm 3

//-----------------------

// double val = 0;

// for (int i=0; i

// val += (val*1.1)+str[i];

// return int (val);

// Add your two hash algorithms below

//-----------------------

// Hash Algorithm 4

//-----------------------

//-----------------------

// Hash Algorithm 5

//-----------------------

}

private:

string key;

};

int main()

{

HashTable testTbl(64);

Data testData;

string key;

ifstream data("std-dev.dat");

if( ! data )

{

cerr << "Error opening 'std-dev.dat'" << endl;

}

else

{

while( data >> key )

{

testData.setKey( key );

testTbl.insert( testData );

}

testTbl.showStructure();

cout << endl << endl;

cout << "The standard deviation is "

<< testTbl.standardDeviation() << endl;

}

}