Lab Exercise

Get the files:Click here To get the zipped files for this exercise

Extract all of the files to the WORKAREA. Open the WORKAREA and double click on exercise.sln. This will open up the project. There are six files used in this program:

hashtbl.cpp and hashtble.h -- contain the implementation of the hashtable class

listlnk.cpp and listlnk.h -- contain the implementation of linked lists class

login.cpp -- the main program. This contains the Password structure, which is inserted into the hashtable.

password.dat -- contains all the users and corresponding passwords.

Your primary tasks for this exercise are to edit the login.cpp to add in lines so that it does the following:

insert passwords into the Hash Table

retrieve one user's Password structure from the Hash Table

check to see if the user is in the table and compare retrieved user password to input password, print "Authentication failure" or "Authentication successful"

Steps include:

Try to run this program. You should find that it will prompt you for "Login:" and "Password:" (type in random words at these prompts). You will notice that it continuely cycles around asking you for this information.
To stop the program from running, at the "Login:" prompt, type CTRL and z (simultaneously) and then the Enter key .

Add in a line to insert passwords into the table. Hint: notice that the name of the hashtable is passwords and that you want to insert a Password structure called tempPass into the hashtable.

Add in a line to print out the hash table. Hint: the hashtable is passwords and there is a member function called showStructure.

Build and Run this program. If all is working well, you should get some output that looks like this:The Hash Table has the following entries 0: _ 1: mary 2: _ 3: _ 4: _ 5: bopeep 6: _ 7: jill 8: _ 9: jack Login: This shows the hash table that has resulted from inserting data from the password.dat file (mentioned in Section 2). Notice that mary is at index 1, just as we predicted (in Section 2).

Add lines to compare the true password to the input password and print "Authentication failure" or "Authentication successful". Hint: Compare the input password (pass) to the password within the tempPass object (which has been retrieved).

Build and Run your program. You should get results like the following:Login: mary Password: contrary Authentication successful Login: jim Password: contrary Authentication failure Login: bopeep Password: sheeplost Authentication failure

You now might want to play around with a couple of things and see what happens:

Modify the following line so that you have 8 elements in your hash table (instead of 10):HashTbl<Password, string> passwords(10); What happens to the hashtable? Why?

Edit the password.dat file. This file has been added to the project (under "Resource Files" in the Solution Explorer). Double click on it to open.
You can add usernames and passwords to test more. Try adding a username "ramy" (this has the same characters as mary, and, therefore, the same integer hash value)

Included files are as follows:
1) hashtbl.cpp

#include <stdexcept> #include <new> #include <cstring> #include <cmath> #include "hashtbl.h" using namespace std; template < class DT, class KF > HashTbl<DT,KF>:: HashTbl ( int initTableSize ) : tableSize(initTableSize) { dataTable = new List<DT>[tableSize]; } template < class DT, class KF > HashTbl<DT,KF>:: ~HashTbl () { delete[] dataTable; } template < class DT, class KF > void HashTbl<DT,KF>:: insert ( const DT &newDataItem ) throw ( bad_alloc ) { // apply two hash functions: 1. convert string (username) to integer // 2. use the division method (% tableSize) to get the index int index = newDataItem.hash(newDataItem.getKey()) % tableSize; if ( dataTable[index].isEmpty() ) dataTable[index].insert( newDataItem ); else { dataTable[index].gotoBeginning(); //if there is a linked list at that index, then cycle through the linked //list until you reach the end of the link do { //if you find the exact same username, then replace it if ( dataTable[index].getCursor().getKey() == newDataItem.getKey() ) { dataTable[index].replace( newDataItem ); return; } } while ( dataTable[index].gotoNext() ); //then insert the data (Password stuff) into the HashTable dataTable[index].insert( newDataItem ); } } template < class DT, class KF > bool HashTbl<DT,KF>:: remove ( KF searchKey ) { DT temp; int index = temp.hash( searchKey ) % tableSize; if ( dataTable[index].isEmpty() ) return false; dataTable[index].gotoBeginning(); do { if ( dataTable[index].getCursor().getKey() == searchKey ) { dataTable[index].remove(); return true; } } while ( dataTable[index].gotoNext() ); return false; } template < class DT, class KF > bool HashTbl<DT,KF>:: retrieve ( KF searchKey, DT &dataItem ) { // apply two hash functions: 1. convert string (searchkey) to integer // 2. use the division method (% tableSize) to get the index int index = dataItem.hash ( searchKey ) % tableSize; //if there is nothing at that index, then the searchkey isn't in the //table if ( dataTable[index].isEmpty() ) return false; dataTable[index].gotoBeginning(); //cycle through the linked list comparing the names (the keys) do { if ( dataTable[index].getCursor().getKey() == searchKey ) { //a match has been found, store it in dataitem so that you //can compare the password information in main dataItem = dataTable[index].getCursor(); return true; } } while ( dataTable[index].gotoNext() ); return false; } template < class DT, class KF > void HashTbl<DT,KF>:: clear () { for (int i=0; i<tableSize; i++) { dataTable[i].clear(); } } template < class DT, class KF > bool HashTbl<DT,KF>:: isEmpty () const { for (int i=0; i<tableSize; i++) { if ( ! dataTable[i].isEmpty() ) return false; } return true; } template < class DT, class KF > bool HashTbl<DT,KF>:: isFull () const { for (int i=0; i<tableSize; i++) { if ( ! dataTable[i].isFull() ) return false; } return true; } template < class DT, class KF > void HashTbl<DT,KF>:: showStructure() const { cout << "The Hash Table has the following entries" <<endl; for ( int i=0; i<tableSize; i++ ) { cout << i << ": "; if ( dataTable[i].isEmpty() ) cout << "_"; else { dataTable[i].gotoBeginning(); do { cout << dataTable[i].getCursor().getKey() << " "; } while ( dataTable[i].gotoNext() ); } cout << endl << endl; } }

//-------------------------------------------------------------------- // // Laboratory hashtbl.h // // Class declaration for the Hash Table ADT // //-------------------------------------------------------------------- #include <stdexcept> #include "listlnk.cpp" using namespace std; template < class DT, class KF > class HashTbl { public: HashTbl ( int initTableSize ); ~HashTbl (); void insert ( const DT &newDataItem) throw ( bad_alloc ); bool remove ( KF searchKey ); bool retrieve ( KF searchKey, DT &dataItem ); void clear (); bool isEmpty () const; bool isFull () const; void showStructure () const; private: int tableSize; List<DT> *dataTable; };

//-------------------------------------------------------------------- // // Laboratory listlnk.cpp // // SOLUTION: Linked list implementation of the List ADT // //-------------------------------------------------------------------- #include <new> #include <iostream> #include <stdexcept> #include "listlnk.h" using namespace std; //-------------------------------------------------------------------- template < class DT > ListNode<DT>:: ListNode ( const DT &nodeDataItem, ListNode<DT> *nextPtr ) // Creates a list node containing item elem and next pointer // nextPtr. : dataItem(nodeDataItem), next(nextPtr) {} //-------------------------------------------------------------------- template < class DT > List<DT>:: List ( int ignored ) // Creates an empty list. The argument is included for compatibility // with the array implementation and is ignored. : head(0), cursor(0) {} //-------------------------------------------------------------------- template < class DT > List<DT>:: ~List () // Frees the memory used by a list. { clear (); } //-------------------------------------------------------------------- template < class DT > void List<DT>:: insert ( const DT &newDataItem ) throw ( bad_alloc ) // Inserts newDataItem after the cursor. If the list is empty, then // newDataItem is inserted as the first (and only) item in the list. // In either case, moves the cursor to newDataItem. { if ( head == 0 ) // Empty list { head = new ListNode<DT>(newDataItem,0); cursor = head; } else // After cursor { cursor->next = new ListNode<DT>(newDataItem,cursor->next); cursor = cursor->next; } } //-------------------------------------------------------------------- template < class DT > void List<DT>:: remove () throw ( logic_error ) // Removes the item marked by the cursor from a list. Moves the // cursor to the next item in the list. Assumes that the first list // item "follows" the last list item. { ListNode<DT> *p, // Pointer to removed node *q; // Pointer to prior node // Requires that the list is not empty if ( head == 0 ) throw logic_error ("list is empty"); if ( cursor == head ) // Remove first item { p = head; head = head->next; cursor = head; } else if ( cursor->next != 0 ) // Remove middle item { p = cursor->next; cursor->dataItem = p->dataItem; cursor->next = p->next; } else // Remove last item { p = cursor; for ( q = head ; q->next != cursor ; q = q->next ); q->next = 0; cursor = head; } delete p; } //-------------------------------------------------------------------- template < class DT > void List<DT>:: replace ( const DT &newDataItem ) throw ( logic_error ) // Replaces the item marked by the cursor with newDataItem and // leaves the cursor at newDataItem. { // Requires that the list is not empty if ( head == 0 ) throw logic_error ("list is empty"); cursor->dataItem = newDataItem; } //-------------------------------------------------------------------- template < class DT > void List<DT>:: clear () // Removes all the items from a list. { ListNode<DT> *p, // Points to successive nodes *nextP; // Points to next node p = head; while ( p != 0 ) { nextP = p->next; delete p; p = nextP; } head = 0; cursor = 0; } //-------------------------------------------------------------------- template < class DT > bool List<DT>:: isEmpty () const // Returns 1 if a list is empty. Otherwise, returns 0. { return ( head == 0 ); } //-------------------------------------------------------------------- template < class DT > bool List<DT>:: isFull () const // Returns true if a list is full. Otherwise, returns false. { // This is a somewhat hacked way to test if the list is full. // If a node can be successfully allocated than the list is not // full. If the allocation fails it is implied that there is no // more free memory therefore the list is full. DT testDataItem; ListNode<DT> *p; try { p = new ListNode<DT>(testDataItem, 0); } // catch ( bad_alloc &e ) catch ( bad_alloc) { return true; } delete p; return false; } //-------------------------------------------------------------------- template < class DT > void List<DT>:: gotoBeginning () throw ( logic_error ) // If a list is not empty, then moves the cursor to the beginning of // the list { if ( head != 0 ) cursor = head; else throw logic_error ("list is empty"); } //-------------------------------------------------------------------- template < class DT > void List<DT>:: gotoEnd () throw ( logic_error ) // If a list is not empty, then moves the cursor to the end of the // list and returns 1. Otherwise, returns 0. { int result; // Result returned if ( head != 0 ) for ( ; cursor->next != 0 ; cursor = cursor->next ); else throw logic_error ("list is empty"); } //-------------------------------------------------------------------- template < class DT > bool List<DT>:: gotoNext () // If the cursor is not at the end of a list, then moves the // cursor to the next item in the list and returns 1. Otherwise, // returns 0. { bool result; // Result returned if ( cursor->next != 0 ) { cursor = cursor->next; result = true; } else result = false; return result; } //-------------------------------------------------------------------- template < class DT > bool List<DT>:: gotoPrior () // If the cursor is not at the beginning of a list, then moves the // cursor to the preceeding item in the list and returns 1. // Otherwise, returns 0. { ListNode<DT> *p; // Pointer to prior node int result; // Result returned if ( cursor != head ) { for ( p = head ; p->next != cursor ; p = p->next ); cursor = p; result = true; } else result = false; return result; } //-------------------------------------------------------------------- template < class DT > DT List<DT>:: getCursor () const throw ( logic_error ) // Returns the item marked by the cursor. { // Requires that the list is not empty if ( head == 0 ) throw logic_error("list is empty"); return cursor->dataItem; } //-------------------------------------------------------------------- template < class DT > void List<DT>:: showStructure () const // Outputs the items in a list. If the list is empty, outputs // "Empty list". This operation is intended for testing and // debugging purposes only. { ListNode<DT> *p; // Iterates through the list if ( head == 0 ) cout << "Empty list" << endl; else { for ( p = head ; p != 0 ; p = p->next ) if ( p == cursor ) cout << "[" << p->dataItem << "] "; else cout << p->dataItem << " "; cout << endl; } } //-------------------------------------------------------------------- // // In-lab operations // //-------------------------------------------------------------------- template < class DT > void List<DT>:: moveToBeginning() throw ( logic_error ) // Removes the item marked by the cursor from a list and // reinserts it at the beginning of the list. Moves the cursor to the // beginning of the list. { ListNode<DT> *p; // Pointer to prior node // Requires that the list is not empty if ( head == 0 ) throw logic_error("list is empty"); if ( cursor != head) { for ( p = head ; p->next != cursor ; p = p->next ); p->next = cursor->next; cursor->next = head; head = cursor; } } //-------------------------------------------------------------------- template < class DT > void List<DT>:: insertBefore ( const DT &newDataItem ) throw ( bad_alloc ) // Inserts newDataItem before the cursor. If the list is empty, then // newDataItem is inserted as the first (and only) item in the list. // In either case, moves the cursor to newDataItem. { if ( head == 0 ) // Empty list { head = new ListNode<DT>(newDataItem, 0); cursor = head; } else // Before cursor { cursor->next = new ListNode<DT>(cursor->dataItem, cursor->next); cursor->dataItem = newDataItem; } }

//-------------------------------------------------------------------- // // Laboratory listlnk.h // // Class declarations for the linked list implementation of the // List ADT // //-------------------------------------------------------------------- #pragma warning( disable : 4290 ) #include <new> #include <stdexcept> using namespace std; template < class DT > // Forward declaration of the List class class List; template < class DT > class ListNode // Facilitator class for the List class { private: // Constructor ListNode ( const DT &nodeData, ListNode *nextPtr ); // Data members DT dataItem; // List data item ListNode *next; // Pointer to the next list node friend class List<DT>; }; //-------------------------------------------------------------------- template < class DT > class List { public: // Constructor List ( int ignored = 0); // Destructor ~List (); // List manipulation operations void insert ( const DT &newData ) // Insert after cursor throw ( bad_alloc ); void remove () // Remove data item throw ( logic_error ); void replace ( const DT &newData ) // Replace data item throw ( logic_error ); void clear (); // Clear list // List status operations bool isEmpty () const; // List is empty bool isFull () const; // List is full // List iteration operations void gotoBeginning () // Go to beginning throw ( logic_error ); void gotoEnd () // Go to end throw ( logic_error ); bool gotoNext (); // Go to next data item bool gotoPrior (); // Go to prior item DT getCursor () const // Return item throw ( logic_error ); // Output the list structure -- used in testing/debugging void showStructure () const; // In-lab operations void moveToBeginning () // Move to beginning throw ( logic_error ); void insertBefore ( const DT &newElement ) // Insert before cursor throw ( bad_alloc ); private: // Data members ListNode<DT> *head, // Pointer to the beginning of the list *cursor; // Cursor pointer };

//-------------------------------------------------------------------- // // Laboratory login.cpp // // In-lab 1 program that reads in username/login pairs and then // performs authentication of usernames until EOF is encountered. // //-------------------------------------------------------------------- #include <string> #include <iostream> #include <fstream> #include "hashtbl.cpp" using namespace std; //This will be the data stored in the HashTbl (class DT) struct Password { void setKey ( string newKey ) { username = newKey; } string getKey () const { return username; } //this hash converts a string to an integer int hash(const string str) const { int val = 0; for (unsigned int i=0; i<str.length(); i++) val += str[i]; return val; } string username, password; }; int main() { HashTbl<Password, string> passwords(10); Password tempPass; string name, // user-supplied name pass; // user-supplied password bool userFound; // is user in table? //********************************************************* // Step 1: Read in the password file //********************************************************* ifstream passFile( "password.dat" ); if ( !passFile ) { cout << "Unable to open 'password.dat'!" << endl; return 1; } while ( passFile >> tempPass.username >> tempPass.password && ! passwords.isFull() ) { //**add line here to insert passwords into the HashTbl } //**add line here to show (print) the HashTbl //********************************************************* // Step 2: Prompt for a Login and Password and check if valid //********************************************************* cout << "Login: "; while ( cin >> name ) // to quit, type CTRL Z in Visual C++ { //**add line here to retrieve user from HashTbl cout << "Password: "; cin >> pass; //**add lines here to compare retrieved user password to //**input password and print "Authentication failure" //**or "Authentication successful" cout << "Login: "; } cout << endl; return 0; }

Output-Build.txt
1>------ Build started: Project: Hash, Configuration: Debug Win32 ------ 1> login.cpp 1>c:\users\softinstall\downloads\hash\hash\login.cpp(42): warning C4101: 'userFound': unreferenced local variable 1> listlnk.cpp 1> hashtbl.cpp 1> Generating Code... 1> Hash.vcxproj -> C:\Users\softinstall\Downloads\Hash\Hash\Debug\Hash.exe 1> Hash.vcxproj -> C:\Users\softinstall\Downloads\Hash\Hash\Debug\Hash.pdb (Full PDB) ========== Build: 1 succeeded, 0 failed, 0 up-to-date, 0 skipped ==========

//-------------------------------------------------------------------- // // Laboratory login.cpp // // In-lab 1 program that reads in username/login pairs and then // performs authentication of usernames until EOF is encountered. // //-------------------------------------------------------------------- #include <string> #include <iostream> #include <fstream> #include "hashtbl.cpp" using namespace std; //This will be the data stored in the HashTbl (class DT) struct Password { void setKey ( string newKey ) { username = newKey; } string getKey () const { return username; } //this hash converts a string to an integer int hash(const string str) const { int val = 0; for (unsigned int i=0; i<str.length(); i++) val += str[i]; return val; } string username, password; }; int main() { HashTbl<Password, string> passwords(10); Password tempPass; string name, // user-supplied name pass; // user-supplied password bool userFound; // is user in table? //********************************************************* // Step 1: Read in the password file //********************************************************* ifstream passFile( "password.dat" ); if ( !passFile ) { cout << "Unable to open 'password.dat'!" << endl; return 1; } while ( passFile >> tempPass.username >> tempPass.password && ! passwords.isFull() ) { //**add line here to insert passwords into the HashTbl } //**add line here to show (print) the HashTbl //********************************************************* // Step 2: Prompt for a Login and Password and check if valid //********************************************************* cout << "Login: "; while ( cin >> name ) // to quit, type CTRL Z in Visual C++ { //**add line here to retrieve user from HashTbl cout << "Password: "; cin >> pass; //**add lines here to compare retrieved user password to //**input password and print "Authentication failure" //**or "Authentication successful" cout << "Login: "; } cout << endl; return 0; }