Question
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
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 ";
}
//--- 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 ";
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++.
you can use any list of userid and passwords. they didnt provide any other lists beside all i posted.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started