Code:
#include iostream
#include string
#include vector
#include cstdlib
using namespace std;
/*
* Node Class Declaration
*/
template
class BSTNode
{
private:
T value;
BSTNode *left, *right;
public:
BSTNode(T value)
{
this->value = value;
left = NULL;
right = NULL;
}
/*
* Adding element to a node
*/
void add(T& value)
{
if (value < this->value)
{
if (left)
left->add(value);
else
left = new BSTNode(value);
}
else if (this->value < value)
{
if (right)
right->add(value);
else
right = new BSTNode(value);
}
}
/*
* Check if node contains element
*/
bool contains(T& value)
{
if (value < this->value)
{
if (left)
return left->contains(value);
else
return false;
}
else if (this->value < value)
{
if (right)
return right->contains(value);
else
return false;
}
else
{
return true;
}
}
friend class BSTHashtable;
};
/*
* Table Class Declaration
*/
class BSTHashtable
{
private:
int size;
vector
int hash(string& s)
{
unsigned int hashVal = 0;
for (unsigned int i = 0; i < s.length(); i++)
hashVal ^= (hashVal << 5) + (hashVal >> 2) + s[i];
return hashVal % size;
}
public:
BSTHashtable(int vectorSize)
{
size = vectorSize;
bucket = new vector
}
/*
* Adding string in the table
*/
void add(string& s)
{
int index = hash(s);
if (bucket->at(index) == NULL)
bucket->at(index) = new BSTNode
else
bucket->at(index)->add(s);
}
/*
* Check if table contains string
*/
bool contains(string& s)
{
int index = hash(s);
if (bucket->at(index) == NULL)
return false;
cout<<"String \""<
return bucket->at(index)->contains(s);
}
/*
* Display Table
*/
void display()
{
for (unsigned int i = 0; i < bucket->size(); i++)
{
cout <<"[" << i << "] ";
if (bucket->at(i) != NULL)
{
BSTNode
display_bst(node);
}
cout << endl;
}
}
/*
* Display BST
*/
void display_bst(BSTNode
{
if (node!=NULL)
{
display_bst(node->left);
cout << node->value << " ";
display_bst(node->right);
}
}
};
/*
* Main Contains Menu
*/
int main()
{
BSTHashtable table(10);
string str;
int choice;
while (1)
{
cout<<"\n----------------------"<
cout<<"Operations on BST Hash Table"<
cout<<"\n----------------------"<
cout<<"1.Insert element into the table"<
cout<<"2.Find element in the table"<
cout<<"3.Display Table Chained with Binary Tree"<
cout<<"4.Exit"<
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter String to be inserted: ";
cin>>str;
table.add(str);
break;
case 2:
cout<<"Enter String to search: ";
cin>>str;
if (table.contains(str) == 0)
{
cout<<"String \""<
continue;
}
break;
case 3:
cout<<"Displaying Table Chained with Binary Tree: "<
table.display();
break;
case 4:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}
Output:
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 200
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
200 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 300
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
300 200 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 400
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
400 300 200 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 500
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List:
500 400 300 200 100
-------------
Operations on XOR Linked List
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 3
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
