Question

1 Approved Answer

Posted on Sep 25, 2024

C++ project Machine Problem 7 - Hashing Write a program to do the following: loads username/password sets from the file password.txt and insert them into

C++ project

Machine Problem 7 - Hashing

Write a program to do the following:

loads username/password sets from the file password.txt and insert them into the hash table until the end of file is reached on password.txt. The password.txt file will look something like this with one username/password set per line.

mary changeMe!

The program will then present a login prompt, read one username, present a password prompt, and after looking up the username's password in the hash table, will print either "Authentication successful" or "Authentication failure". The above step will be repeated until the end of the input data (EOF) is reached on the console input stream (cin). The EOF character on the PC's is the CTRL Z character. To convert from a string to an integer, we can add the ascii value of each character together. For instance, Mary's conversion from string to integer might look something like this: 109('m') + 97('a') + 114('r') + 121('y')=441 We've converted the string to an integer, but we still need to convert the integer to an index. For an array of 10 elements we can divide by 10 and use the remainder as an index. Combining these two hash functions, we will get Mary's index to be: 441 % 10 = 1 Your primary tasks for this homework are to edit the login.cpp to replace the comments with lines so that it does the following:

Insert passwords into the Hash Table.

Retrieve one user's Password structure from the Hash Table.

Compare retrieved user password to input password and print "Authentication failure" or "Authentication successful."

//-------------------------------------------------------------------- // // listlnk.h // //-------------------------------------------------------------------- #pragma warning( disable : 4290 ) #include #include #include #include #include #include #include using namespace std; template < class T > // Forward declaration of the List class class List; template < class T > class ListNode // Facilitator class for the List class { private: ListNode(const T &nodeData, ListNode *nextPtr); T dataItem; // List data item ListNode *next; // Pointer to the next list node friend class List; }; //-------------------------------------------------------------------- template < class T > class List { public: List(int ignored = 0); ~List(); void insert(const T &newData) throw (bad_alloc); // Insert after cursor void remove() throw (logic_error); // Remove data item void replace(const T &newData) throw (logic_error); // Replace data item void clear(); bool isEmpty() const; bool isFull() const; // List iteration operations void gotoBeginning() throw (logic_error); void gotoEnd() throw (logic_error); bool gotoNext(); bool gotoPrior(); T getCursor() const throw (logic_error); // Return item void showStructure() const; void moveToBeginning() throw (logic_error); // Move to beginning void insertBefore(const T &newElement) throw (bad_alloc); // Insert before cursor private: ListNode *head, // Pointer to the beginning of the list *cursor; // Cursor pointer }; //-------------------------------------------------------------------- // // listlnk.cpp // //-------------------------------------------------------------------- template < class T > ListNode::ListNode(const T &nodeDataItem, ListNode *nextPtr) : dataItem(nodeDataItem), next(nextPtr) {} //-------------------------------------------------------------------- template < class T > List::List(int ignored) : head(0), cursor(0) {} //-------------------------------------------------------------------- template < class T > List:: ~List() { clear(); } //-------------------------------------------------------------------- template < class T > void List::insert(const T &newDataItem) throw (bad_alloc) { if (head == 0) // Empty list { head = new ListNode(newDataItem, 0); cursor = head; } else // After cursor { cursor->next = new ListNode(newDataItem, cursor->next); cursor = cursor->next; } } //-------------------------------------------------------------------- template < class T > void List::remove() throw (logic_error) { ListNode *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 T > void List::replace(const T &newDataItem) throw (logic_error) { if (head == 0) throw logic_error("list is empty"); cursor->dataItem = newDataItem; } //-------------------------------------------------------------------- template < class T > void List::clear() { ListNode *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 T > bool List::isEmpty() const { return (head == 0); } //-------------------------------------------------------------------- template < class T > bool List::isFull() const { T testDataItem; ListNode *p; try { p = new ListNode(testDataItem, 0); } catch (bad_alloc) { return true; } delete p; return false; } //-------------------------------------------------------------------- template < class T > void List::gotoBeginning() throw (logic_error) { if (head != 0) cursor = head; else throw logic_error("list is empty"); } //-------------------------------------------------------------------- template < class T > void List::gotoEnd() throw (logic_error) { if (head != 0) for (; cursor->next != 0; cursor = cursor->next) ; else throw logic_error("list is empty"); } //-------------------------------------------------------------------- template < class T > bool List::gotoNext() { bool result; // Result returned if (cursor->next != 0) { cursor = cursor->next; result = true; } else result = false; return result; } //-------------------------------------------------------------------- template < class T > bool List::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 *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 T > T List::getCursor() const throw (logic_error) { if (head == 0) throw logic_error("list is empty"); return cursor->dataItem; } //-------------------------------------------------------------------- template < class T > void List::showStructure() const { ListNode *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; } } //-------------------------------------------------------------------- template < class T > void List::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 *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 T > void List::insertBefore(const T &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(newDataItem, 0); cursor = head; } else // Before cursor { cursor->next = new ListNode(cursor->dataItem, cursor->next); cursor->dataItem = newDataItem; } } //-------------------------------------------------------------------- // hashtbl.h //-------------------------------------------------------------------- template < class T, class KF > class HashTbl { public: HashTbl(int initTableSize); ~HashTbl(); void insert(const T &newDataItem) throw (bad_alloc); bool remove(KF searchKey); bool retrieve(KF searchKey, T &dataItem); void clear(); bool isEmpty() const; bool isFull() const; void showStructure() const; private: int tableSize; List *dataTable; }; //-------------------------------------------------------------------- // hashtbl.cpp //-------------------------------------------------------------------- template < class T, class KF > HashTbl::HashTbl(int initTableSize) : tableSize(initTableSize) { dataTable = new List[tableSize]; } template < class T, class KF > HashTbl:: ~HashTbl() { delete[] dataTable; } template < class T, class KF > void HashTbl::insert(const T &newDataItem) throw (bad_alloc) { int index = 0; index = newDataItem.hash(newDataItem.getKey()) % tableSize; if (dataTable[index].isEmpty()) dataTable[index].insert(newDataItem); else { dataTable[index].gotoBeginning(); do { if (dataTable[index].getCursor().getKey() == newDataItem.getKey()) { dataTable[index].replace(newDataItem); return; } } while (dataTable[index].gotoNext()); dataTable[index].insert(newDataItem); } } template < class T, class KF > bool HashTbl::remove(KF searchKey) { T temp; int index = 0; 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 T, class KF > bool HashTbl::retrieve(KF searchKey, T &dataItem) { // apply two hash functions: // convert string (searchkey) to integer // and use the remainder method (% tableSize) to get the index int index = 0; index = dataItem.hash(searchKey) % tableSize; if (dataTable[index].isEmpty()) return false; dataTable[index].gotoBeginning(); do { if (dataTable[index].getCursor().getKey() == searchKey) { dataItem = dataTable[index].getCursor(); return true; } } while (dataTable[index].gotoNext()); return false; } template < class T, class KF > void HashTbl::clear() { for (int i = 0; i bool HashTbl::isEmpty() const { for (int i = 0; i bool HashTbl::isFull() const { for (int i = 0; i void HashTbl::showStructure() const { cout << "The Hash Table has the following entries" << endl; for (int i = 0; i passwords(10); Password tempPass; string name; // user-supplied name string pass; // user-supplied password //bool userFound; // is user in table? //********************************************************* // Step 1: Read in the password file //********************************************************* ifstream passFile("password.txt"); if (!passFile) { cout << "Unable to open 'password.txt'!" << endl; exit(0); } passFile >> tempPass.username; while (!passFile.eof() && !passwords.isFull()) { //**add line here to insert passwords into the HashTbl passFile >> tempPass.password; } cout << "Printing the hash table:..." << endl; //**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; }