Write a C++ program to validate computer user-ids and passwords. A list of valid ids and...
Write a C++ program to validate computer user-ids and passwords. A list of valid ids and passwords (unsorted) is read from a file and stored in a Binary Search Tree (BST) of UserInfo objects. When user-ids and passwords are entered during execution, this BST is searched to determine whether they are legal. Input (file): UserInfo records for valid users Input (keyboard): Ids and passwords of users logging in Output (screen): Messages indicating whether user-ids and passwords are valid, as well as an alphabetical listing of all valid ids and passwords at the end of the run. Note: you will need to overload >>, <<, ==, and < operators in the UserInfo class in order to accomplish this task. BST.h class is on Blackboard. You may ONLY modify the search function. this is the BST.h file. i need the lab done by editing the this file. /* BST.h contains the declaration of class template BST. Basic operations: Constructor: Constructs an empty BST empty: Checks if a BST is empty search: Search a BST for an item insert: Inserts a value into a BST remove: Removes a value from a BST inorder: Inorder traversal of a BST -- output the data values Private utility helper operations: search2: Used by delete inorderAux: Used by inorder Other operations: destructor copy constructor assignment operator preorder, postorder, and level-by-level traversals level finder Note: Execution terminates if memory isn't available for a new BST node. ---------------------------------------------------------------------------*/ #include using namespace std; #ifndef BINARY_SEARCH_TREE #define BINARY_SEARCH_TREE template class BST { public: /***** Function Members *****/ BST(); /*------------------------------------------------------------------------ Construct a BST object. Precondition: None. Postcondition: An empty BST has been constructed. -----------------------------------------------------------------------*/ bool empty() const; /*------------------------------------------------------------------------ Check if BST is empty. Precondition: None. Postcondition: Returns true if BST is empty and false otherwise. -----------------------------------------------------------------------*/ bool search(const DataType & item) const; /*------------------------------------------------------------------------ Search the BST for item. Precondition: None. Postcondition: Returns true if item found, and false otherwise. -----------------------------------------------------------------------*/ void insert(const DataType & item); /*------------------------------------------------------------------------ Insert item into BST. Precondition: None. Postcondition: BST has been modified with item inserted at proper position to maintain BST property. ------------------------------------------------------------------------*/ void remove(const DataType & item); /*------------------------------------------------------------------------ Remove item from BST. Precondition: None. Postcondition: BST has been modified with item removed (if present); BST property is maintained. Note: remove uses auxiliary function search2() to locate the node containing item and its parent. ------------------------------------------------------------------------*/ void inorder(ostream & out) const; /*------------------------------------------------------------------------ Inorder traversal of BST. Precondition: ostream out is open. Postcondition: BST has been inorder traversed and values in nodes have been output to out. Note: inorder uses private auxiliary function inorderAux(). ------------------------------------------------------------------------*/ private: /***** Node class *****/ class BinNode { public: DataType data; BinNode * left; BinNode * right; // BinNode constructors // Default -- data part is default DataType value; both links are null. BinNode() { left = 0; right = 0;} // Explicit Value -- data part contains item; both links are null. BinNode(DataType item) { data = item; left = 0; right = 0; } };// end of class BinNode declaration typedef BinNode * BinNodePointer; /***** Private Function Members *****/ void search2(const DataType & item, bool & found, BinNodePointer & locptr, BinNodePointer & parent) const; /*------------------------------------------------------------------------ Locate a node containing item and its parent. Precondition: None. Postcondition: locptr points to node containing item or is null if not found, and parent points to its parent.#include ------------------------------------------------------------------------*/ void inorderAux(ostream & out, BinNodePointer subtreePtr) const; /*------------------------------------------------------------------------ Inorder traversal auxiliary function. Precondition: ostream out is open; subtreePtr points to a subtree of this BST. Postcondition: Subtree with root pointed to by subtreePtr has been output to out. ------------------------------------------------------------------------*/ /***** Data Members *****/ BinNodePointer myRoot; }; // end of class template declaration //--- Definition of constructor template inline BST::BST() {myRoot = 0;} //--- Definition of empty() template inline bool BST::empty() const { return myRoot == 0; } //--- Definition of search() template bool BST::search(const DataType & item) const { BinNodePointer locptr = myRoot; bool found = false; while (!found && locptr != 0) { if (item < locptr->data) // descend left locptr = locptr->left; else if (locptr->data < item) // descend right locptr = locptr->right; else // item found found = true; } return found; } //--- Definition of insert() template inline void BST::insert(const DataType & item) { BinNodePointer locptr = myRoot, // search pointer parent = 0; // pointer to parent of current node bool found = false; // indicates if item already in BST while (!found && locptr != 0) { parent = locptr; if (item < locptr->data) // descend left locptr = locptr->left; else if (locptr->data < item) // descend right locptr = locptr->right; else // item found found = true; } if (!found) { // construct node containing item locptr = new BinNode(item); if (parent == 0) // empty tree myRoot = locptr; else if (item < parent->data ) // insert to left of parent parent->left = locptr; else // insert to right of parent parent->right = locptr; } else cout << "Item already in the tree\n"; } //--- Definition of remove() template void BST::remove(const DataType & item) { bool found; // signals if item is found BinNodePointer x, // points to node to be deleted parent; // " " parent of x and xSucc search2(item, found, x, parent); if (!found) { cout << "Item not in the BST\n"; return; } //else if (x->left != 0 && x->right != 0) { // node has 2 children // Find x's inorder successor and its parent BinNodePointer xSucc = x->right; parent = x; while (xSucc->left != 0) // descend left { parent = xSucc; xSucc = xSucc->left; } // Move contents of xSucc to x and change x // to point to successor, which will be removed. x->data = xSucc->data; x = xSucc; } // end if node has 2 children // Now proceed with case where node has 0 or 2 child BinNodePointer subtree = x->left; // pointer to a subtree of x if (subtree == 0) subtree = x->right; if (parent == 0) // root being removed myRoot = subtree; else if (parent->left == x) // left child of parent parent->left = subtree; else // right child of parent parent->right = subtree; delete x; } //--- Definition of inorder() template inline void BST::inorder(ostream & out) const { inorderAux(out, myRoot); } //--- Definition of search2() template void BST::search2(const DataType & item, bool & found, BinNodePointer & locptr, BinNodePointer & parent) const { locptr = myRoot; parent = 0; found = false; while (!found && locptr != 0) { if (item < locptr->data) // descend left { parent = locptr; locptr = locptr->left; } else if (locptr->data < item) // descend right { parent = locptr; locptr = locptr->right; } else // item found found = true; } } //--- Definition of inorderAux() template void BST::inorderAux(ostream & out, BinNodePointer subtreeRoot) const { if (subtreeRoot != 0) { inorderAux(out, subtreeRoot->left); // L operation out << subtreeRoot->data << " "; // V operation inorderAux(out, subtreeRoot->right); // R operation } } #endif and this is an extra file called recrusive BST search i think we can use it as well. //--- Definition of search2() template void BST::search2(const DataType & item, bool & found) const { searchAUX(item, found, root); //begin searching at root } template void BST::searchAUX(const DataType & item, bool & found, BinNodePointer & locptr) const { if ( locptr == null ) // Failed to find found = false; // Base case 1 else if ( item < locptr->data ) // Down left searchAUX(item, found, locptr -> left); else if ( item > locptr->data ) // Down right searchAUX(item, found, locptr -> right); else // We FOUND it! found = true; // Base case 2 } we use c++. this is the second time to post this question. please make sure to use the trees to approach the answer. its due next monday and i have almost 3 finals i cant finish it.
Homework Answers
Copyable Code:
BST.h:
#include <iostream>
using namespace std;
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
template <typename DataType>
class BST
{
public:
/***** Function Members *****/
BST();
/*------------------------------------------------------------------------
Construct a BST object.
Precondition: None.
Postcondition: An empty BST has been constructed.
----------------------------------------------------------------*/
bool empty() const;
/*------------------------------------------------------------------------
Check if BST is empty.
Precondition: None.
Postcondition: Returns true if BST is empty and false otherwise.
-----------------------------------------------------------------------*/
bool search(const DataType & item) const;
/*------------------------------------------------------------------------
Search the BST for item.
Precondition: None.
Postcondition: Returns true if item found, and false otherwise.
-----------------------------------------------------------------------*/
void insert(const DataType & item);
/*------------------------------------------------------------------------
Insert item into BST.
Precondition: None.
Postcondition: BST has been modified with item inserted at proper position to maintain BST property.
------------------------------------------------------------------------*/
void remove(const DataType & item);
/*------------------------------------------------------------------------
Remove item from BST.
Precondition: None.
Postcondition: BST has been modified with item removed (if present);
BST property is maintained.
Note: remove uses auxiliary function search2() to locate the node containing item and its parent.
------------------------------------------------------------------------*/
void inorder(ostream & out) const;
/*------------------------------------------------------------------------
Inorder traversal of BST.
Precondition: ostream out is open.
Postcondition: BST has been inorder traversed and values in nodes have been output to out.
Note: inorder uses private auxiliary function inorderAux().
------------------------------------------------------------------------*/
private:
class BinNode
{
public:
DataType data;
BinNode * left;
BinNode * right;
BinNode()
{
left = 0;
right = 0;}
// Explicit Value -- data part contains item; both links are null.
BinNode(DataType item)
{
data = item;
left = 0;
right = 0;
}
};// end of class BinNode declaration
typedef BinNode * BinNodePointer;
/***** Private Function Members *****/
void search2(const DataType & item, bool & found,BinNodePointer & locptr, BinNodePointer & parent) const;
void inorderAux(ostream & out,BinNodePointer subtreePtr) const;
/***** Data Members *****/
BinNodePointer myRoot;
}; // end of class template declaration
//--- Definition of constructor
template <typename DataType>
inline BST<DataType>::BST()
{
myRoot = 0;
}
//--- Definition of empty()
template <typename DataType>
inline bool BST<DataType>::empty() const
{ return myRoot == 0; }
//--- Definition of search()
template <typename DataType>
bool BST<DataType>::search(const DataType & item) const
{
BinNodePointer locptr = myRoot;
bool found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
return found;
}
//--- Definition of insert()
template <typename DataType>
inline void BST<DataType>::insert(const DataType & item)
{
BinNodePointer
locptr = myRoot, // search pointer
parent = 0; // pointer to parent of current node
bool found = false; // indicates if item already in BST
while (!found && locptr != 0)
{
parent = locptr;
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
if (!found)
{ // construct node containing item
locptr = new BinNode(item);
if (parent == 0) // empty tree
myRoot = locptr;
else if (item < parent->data ) // insert to left of parent
parent->left = locptr;
else // insert to right of parent
parent->right = locptr;
}
else
cout << "Item already in the tree\n";
}
//--- Definition of remove()
template <typename DataType>
void BST<DataType>::remove(const DataType & item)
{
bool found; // signals if item is found
BinNodePointer
x, // points to node to be deleted
parent; // " " parent of x and xSucc
search2(item, found, x, parent);
if (!found)
{
cout << "Item not in the BST\n";
return;
}
//else
if (x->left != 0 && x->right != 0)
{ // node has 2 children
// Find x's inorder successor and its parent
BinNodePointer xSucc = x->right;
parent = x;
while (xSucc->left != 0) // descend left
{
parent = xSucc;
xSucc = xSucc->left;
}
x->data = xSucc->data;
x = xSucc;
} // end if node has 2 children
// Now proceed with case where node has 0 or 2 child
BinNodePointer
subtree = x->left; // pointer to a subtree of x
if (subtree == 0)
subtree = x->right;
if (parent == 0) // root being removed
myRoot = subtree;
else if (parent->left == x) // left child of parent
parent->left = subtree;
else // right child of parent
parent->right = subtree;
delete x;
}
//--- Definition of inorder()
template <typename DataType>
inline void BST<DataType>::inorder(ostream & out) const
{
inorderAux(out, myRoot);
}
//--- Definition of search2()
template <typename DataType>
void BST<DataType>::search2(const DataType & item, bool & found,
BinNodePointer & locptr,
BinNodePointer & parent) const
{
locptr = myRoot;
parent = 0;
found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
{
parent = locptr;
locptr = locptr->left;
}
else if (locptr->data < item) // descend right
{
parent = locptr;
locptr = locptr->right;
}
else // item found
found = true;
}
}
//--- Definition of inorderAux()
template <typename DataType>
void BST<DataType>::inorderAux(ostream & out,
BinNodePointer subtreeRoot) const
{
if (subtreeRoot != 0)
{
inorderAux(out, subtreeRoot->left); // L operation
out << subtreeRoot->data << " "; // V operation
inorderAux(out, subtreeRoot->right); // R operation
}
}
#endif
Main.cpp:
#include "BST.h"
#include <fstream>
#include <string>
using namespace std;
class UserInfo
{
string uid, pwd;
public:
UserInfo()
{
uid = "";
pwd = "";
}
UserInfo( string newID, string newPWD ){
uid = newID;
pwd = newPWD;
}
const string get_uid() const{ return uid; }
const string get_pwd() const{ return pwd; }
void set_uid( string newID ){ uid = newID; }
void set_pwd( string newPWD ){ pwd = newPWD; }
};
const bool operator <( const UserInfo& user1, const UserInfo& user2 )
{
if( user1.get_uid() < user2.get_uid() )
{
return true;
};
if( (user1.get_uid() == user2.get_uid()) && (user1.get_pwd() < user2.get_pwd()))
{
return true;
};
return false;
};
bool operator ==( const UserInfo& user1, const UserInfo& user2 )
{
return ((user1.get_uid() == user2.get_uid()) &&
(user1.get_pwd() == user2.get_pwd()) );
};
ostream &operator <<( ostream &output, const UserInfo& user )
{
output << user.get_uid() << " " << user.get_pwd() << endl;
return output;
}
istream &operator >>( istream &input, UserInfo& user )
{
string uid,pwd;
input >> uid >> pwd;
user.set_uid( uid );
user.set_pwd( pwd );
return input;
}
int main()
{
string line;
ifstream in("./userInfo.txt");
BST<UserInfo> binaryTree;
UserInfo newInfo;
while( in >> newInfo ){
binaryTree.insert( newInfo );
}
//get the input from file
string uName,pwd;
cout << "Enter the user name : ";
cin >> uName;
cout << "Enter the Password : ";
cin >> pwd;
UserInfo input(uName, pwd);
cout << endl;
if( binaryTree.search(input))
{
cout << "The user name and password is valid" << endl;
}
else
{
cout << "The user name or password is invalid" << endl;
}
cout<<"LISTING" << endl;
binaryTree.inorder( cout );
}
userInfo.txt:
userid1 xyz
userid2 ABC
userid2 asdf
Add Answer to:
Write a C++ program to validate computer user-ids and passwords.
A list of valid ids and...
In C++ I need the printRange function, and the main.cpp program. Thanks. (Binary search tree) Write...
In C++ I need the printRange function, and the main.cpp program. Thanks. (Binary search tree) Write a function printRange that takes as input a binary search tree t and two keys, k1 and k2, which are ordered so that k1 < k2, and print all elements x in the tree such that k1 <= x <= k2. You can add this function in BinarySearchTree.h (click the link) that we used in the lecture and lab 7. public: void printRange(int k1,...
Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary...
Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary tree. Add this function to the class binaryTreeType and create a program to test this function. #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct nodeType { elemType info; nodeType<elemType> *lLink; nodeType<elemType> *rLink; }; //Definition of the class template <class elemType> class binaryTreeType { public: //Overload the assignment operator. const binaryTreeType<elemType>& operator=(const binaryTreeType<elemType>&) { if (this != &otherTree) //avoid self-copy...
Please use the linked approach implement the BST ADT, implement all the functions in the BSTree.cpp....
Please use the linked approach implement the BST ADT,
implement all the functions in the BSTree.cpp. Add the ouput of the
implementation.
use recursive functions to traverse the tree - read the
implementation notes on using helper functions.
Please use C++ programming
//////////////////////////////////////////////////////////////
#include "BSTree.h"
template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode ( const
DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode
*rightPtr )
{
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ()
{
root = 0;
}
template...
- implement the Stack ADT using array – based approach. Use C++ program language #include "StackArray.h"...
- implement the Stack ADT using array – based approach. Use C++ program language #include "StackArray.h" template <typename DataType> StackArray<DataType>::StackArray(int maxNumber) { } template <typename DataType> StackArray<DataType>::StackArray(const StackArray& other) { } template <typename DataType> StackArray<DataType>& StackArray<DataType>::operator=(const StackArray& other) { } template <typename DataType> StackArray<DataType>::~StackArray() { } template <typename DataType> void StackArray<DataType>::push(const DataType& newDataItem) throw (logic_error) { } template <typename DataType> DataType StackArray<DataType>::pop() throw (logic_error) { } template <typename DataType> void StackArray<DataType>::clear() { } template <typename DataType> bool StackArray<DataType>::isEmpty() const {...
For this computer assignment, you are to write a C++ program to implement a class for...
For this computer assignment, you are to write a C++ program to implement a class for binary trees. To deal with variety of data types, implement this class as a template. The definition of the class for a binary tree (as a template) is given as follows: template < class T > class binTree { public: binTree ( ); // default constructor unsigned height ( ) const; // returns height of tree virtual void insert ( const T& ); //...
(C++) Two stacks of the same type are the same if they have the same number...
(C++) Two stacks of the same type are the same if they have the same number of elements and their elements at the corresponding positions are the same. Overload the relational operator == for the class stackType that returns true if two stacks of the same type are the same; it returns false otherwise. Also, write the definition of the function template to overload this operator. Write a program to test the various overloaded operators and functions of classstackType. **Please...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to com...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
Using the below files, Write a program that reads a document containing endnotes indicated in this...
Using the below files, Write a program that reads a document containing endnotes indicated in this manner, collects them in a queue, and prints them on the screen. For this lab, you will create a text file called sample.txt and put the following paragraph in it. This part is the beginning. {This part is the footnote.} This part is the end. /* Queue.h contains the declaration of class Queue. Basic operations: Constructor: Constructs an empty queue empty: Checks if a...
QUESTION 8 In the _____ traversal, the root is processed first, before its subtrees. breadth first...
QUESTION 8 In the _____ traversal, the root is processed first, before its subtrees. breadth first preorder postorder inorder 0.10000 points QUESTION 9 What kind of traversal does the following algorithm (in pseudo-code) describe? Algorithm traversal (root) if (root is not null) traversal (leftSubTree) process (root) traversal (rightSubTree) end if end traversal breadth first preorder inorder postorder 0.10000 points QUESTION 10 What kind of traversal does the following algorithm (in pseudo-code) describe? Algorithm traversal (root) if...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the word...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the words in order (based on ASCII/UNICODE order) on the screen (or to output text file). Note that you may need to make some changes to BST.java. Sample test: ----jGRASP exec: java -ea removeDuplicates Original Text: a B 2 n w C q K l 0...
Please use the linked approach implement the BST ADT,
implement all the functions in the BSTree.cpp. Add the ouput of the
implementation.
use recursive functions to traverse the tree - read the
implementation notes on using helper functions.
Please use C++ programming
//////////////////////////////////////////////////////////////
#include "BSTree.h"
template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode ( const
DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode
*rightPtr )
{
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ()
{
root = 0;
}
template...
Most questions answered within 3 hours.
-
You have a 825.3 mL sample of 2.754 M HA (Ka =
4.49⋅10−4). Calculate the pH...
asked 1 hour ago -
The blues made its way into many kinds of music. Eric Clapton,
The Beatles, and Elvis...
asked 4 hours ago -
8. A wave in a string has a wave function given by: y (x, t) =...
asked 3 hours ago -
If you’re standing at the bottom of a hill and asked to evaluate
it while being...
asked 4 hours ago -
1. Which region has taken the lead in the world of
e-waste handling?
a) European Union...
asked 4 hours ago -
A 8.15- g bullet from a 9-mm pistol has a velocity of 366.0 m/s.
It strikes...
asked 6 hours ago -
The outstanding bonds of Alpha Extracts have a yield to maturity
of 7.4 percent and a...
asked 6 hours ago -
The Problem: The Case of the Harmonizing Vacations
Your CEO is exploring partnering with a European...
asked 7 hours ago -
A chemical equation is balanced by adding coefficients in front
of some formulas so that the...
asked 7 hours ago -
From the literature (reference your sources): What are the
lattice parameters of calcite and aragonite? Why...
asked 8 hours ago -
Your system is rejecting the question am asking which is
preceded by a case study. It...
asked 8 hours ago -
3. On January 2, 2000, Larry creates a trust with himself as
trustee. Larry as trustee...
asked 8 hours ago