C++ Programming. Please only answer if you can do the ENTIRE problem. DO NOT MAK
ID: 3869122 • Letter: C
Question
C++ Programming. Please only answer if you can do the ENTIRE problem. DO NOT MAKE YOUR OWN CPP FILES, VARIABLES, ETC. UPLOAD ALL OF THE EXACT .CPP AND .H FILES AS I HAVE THEM JUST COMPLETED. Reattach all files I have below even if you didn't have to edit one. Program MUST compile and all these instructions followed in order for me to give a thumbs up, thank you :-)
Parts to complete:
- Implement the Hash Table ADT (80 points)
- Programming Exercise 3 (20 points)
BSTree.cpp
#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 = NULL;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ( const BSTree<DataType,KeyType>& other )
{
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>& BSTree<DataType, KeyType>:: operator= ( const BSTree<DataType,KeyType>& other )
{
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::~BSTree ()
{
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insert ( const DataType& newDataItem )
{
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const
{
return false;
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::remove ( const KeyType& deleteKey )
{
return false;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeKeys () const
{
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clear ()
{
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::isEmpty () const
{
return false;
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeight () const
{
return -1;
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCount () const
{
return -1;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLessThan ( const KeyType& searchKey ) const
{
}
#include "show9.cpp"
BSTree.h
//--------------------------------------------------------------------
//
// Laboratory 9 BSTree.h
//
// Class declarations for the linked implementation of the Binary
// Search Tree ADT -- including the recursive helpers of the
// public member functions
//
//--------------------------------------------------------------------
#ifndef BSTREE_H
#define BSTREE_H
#include <stdexcept>
#include <iostream>
using namespace std;
template < typename DataType, class KeyType > // DataType : tree data item
class BSTree // KeyType : key field
{
public:
// Constructor
BSTree (); // Default constructor
BSTree ( const BSTree<DataType,KeyType>& other ); // Copy constructor
BSTree& operator= ( const BSTree<DataType,KeyType>& other );
// Overloaded assignment operator
// Destructor
~BSTree ();
// Binary search tree manipulation operations
void insert ( const DataType& newDataItem ); // Insert data item
bool retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const;
// Retrieve data item
bool remove ( const KeyType& deleteKey ); // Remove data item
void writeKeys () const; // Output keys
void clear (); // Clear tree
// Binary search tree status operations
bool isEmpty () const; // Tree is empty
// !! isFull() has been retired. Not very useful in a linked structure.
// Output the tree structure -- used in testing/debugging
void showStructure () const;
// In-lab operations
int getHeight () const; // Height of tree
int getCount () const; // Number of nodes in tree
void writeLessThan ( const KeyType& searchKey ) const; // Output keys < searchKey
protected:
class BSTreeNode // Inner class: facilitator for the BSTree class
{
public:
// Constructor
BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr );
// Data members
DataType dataItem; // Binary search tree data item
BSTreeNode *left, // Pointer to the left child
*right; // Pointer to the right child
};
// Recursive helpers for the public member functions -- insert
// prototypes of these functions here.
void showHelper ( BSTreeNode *p, int level ) const;
// Data member
BSTreeNode *root; // Pointer to the root node
};
#endif // define BSTREE_H
example1.cpp
// lab10-example1.cpp
#include <iostream>
#include <cmath>
#include "HashTable.cpp"
using namespace std;
struct Account
{
int acctNum; // (Key) Account number
float balance; // Account balance
int getKey () const { return acctNum; }
static unsigned int hash(const int& key) { return abs( key ); }
};
int main()
{
HashTable<Account,int> accounts(11); // List of accounts
Account acct; // A single account
int searchKey; // An account key
// Read in information on a set of accounts.
cout << endl << "Enter account information (num balance) for 5 accounts: "
<< endl;
for ( int i = 0; i < 5; i++ )
{
cin >> acct.acctNum >> acct.balance;
accounts.insert(acct);
}
// Checks for accounts and prints records if found
cout << endl;
cout << "Enter account number (<EOF> to end): ";
while ( cin >> searchKey )
{
if ( accounts.retrieve(searchKey,acct) )
cout << acct.acctNum << " " << acct.balance << endl;
else
cout << "Account " << searchKey << " not found." << endl;
}
return 0;
}
HashTable.cpp
#include "HashTable.h"
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::HashTable(int initTableSize)
{
}
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::HashTable(const HashTable& other)
{
}
template <typename DataType, typename KeyType>
HashTable<DataType,KeyType>& HashTable<DataType, KeyType>::operator=(const HashTable& other)
{
}
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::~HashTable()
{
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::insert(const DataType& newDataItem)
{
}
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::remove(const KeyType& deleteKey)
{
return false;
}
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::retrieve(const KeyType& searchKey, DataType& returnItem) const
{
return false;
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::clear()
{
}
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::isEmpty() const
{
return true;
}
#include "show10.cpp"
template <typename DataType, typename KeyType>
double HashTable<DataType, KeyType>::standardDeviation() const
{
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::copyTable(const HashTable& source)
{
}
HashTable.h
// HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <stdexcept>
#include <iostream>
using namespace std;
#include "BSTree.cpp"
template <typename DataType, typename KeyType>
class HashTable {
public:
HashTable(int initTableSize);
HashTable(const HashTable& other);
HashTable& operator=(const HashTable& other);
~HashTable();
void insert(const DataType& newDataItem);
bool remove(const KeyType& deleteKey);
bool retrieve(const KeyType& searchKey, DataType& returnItem) const;
void clear();
bool isEmpty() const;
void showStructure() const;
double standardDeviation() const;
private:
void copyTable(const HashTable& source);
int tableSize;
BSTree<DataType, KeyType>* dataTable;
};
#endif // ifndef HASHTABLE_H
show9.cpp
#include "BSTree.h"
//--------------------------------------------------------------------
//
// Laboratory 9 show9.cpp
//
// Linked implementation of the showStructure operation for the
// Binary Search Tree ADT
//
//--------------------------------------------------------------------
//--------------------------------------------------------------------
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showStructure () const
// Outputs the keys in a binary search tree. The tree is output
// rotated counterclockwise 90 degrees from its conventional
// orientation using a "reverse" inorder traversal. This operation is
// intended for testing and debugging purposes only.
{
if ( root == 0 )
cout << "Empty tree" << endl;
else
{
cout << endl;
showHelper(root,1);
cout << endl;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showHelper ( BSTreeNode *p,
int level ) const
// Recursive helper for showStructure.
// Outputs the subtree whose root node is pointed to by p.
// Parameter level is the level of this node within the tree.
{
int j; // Loop counter
if ( p != 0 )
{
showHelper(p->right,level+1); // Output right subtree
for ( j = 0 ; j < level ; j++ ) // Tab over to level
cout << " ";
cout << " " << p->dataItem.getKey(); // Output key
if ( ( p->left != 0 ) && // Output "connector"
( p->right != 0 ) )
cout << "<";
else if ( p->right != 0 )
cout << "/";
else if ( p->left != 0 )
cout << "\";
cout << endl;
showHelper(p->left,level+1); // Output left subtree
}
}
show10.cpp
#include "HashTable.h"
// show10.cpp: contains implementation of the HashTable showStructure function
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::showStructure() const {
for (int i = 0; i < tableSize; ++i) {
cout << i << ": ";
dataTable[i].writeKeys();
}
}
test10.cpp
#include <iostream>
#include <string>
using namespace std;
#include "HashTable.cpp"
class TestData {
public:
TestData();
void setKey(const string& newKey);
string getKey() const;
int getValue() const;
static unsigned int hash(const string& str);
private:
string key;
int value;
static int count;
};
int TestData::count = 0;
TestData::TestData() : value(++count) {
}
void TestData::setKey(const string& newKey) {
key = newKey;
}
string TestData::getKey() const {
return key;
}
int TestData::getValue() const {
return value;
}
unsigned int TestData::hash(const string& str) {
unsigned int val = 0;
for (unsigned int i = 0; i < str.length(); ++i) {
val += str[i];
}
return val;
}
void print_help() {
cout << endl << "Commands:" << endl;
cout << " H : Help (displays this message)" << endl;
cout << " +x : Insert (or update) data item with key x" << endl;
cout << " -x : Remove the data element with the key x" << endl;
cout << " ?x : Retrieve the data element with the key x" << endl;
cout << " E : Empty table?" << endl;
cout << " C : Clear the table" << endl;
cout << " Q : Quit the test program" << endl;
}
int main(int argc, char **argv) {
HashTable<TestData, string> table(7);
print_help();
do {
table.showStructure();
cout << endl << "Command: ";
char cmd;
cin >> cmd;
TestData item;
if (cmd == '+' || cmd == '?' || cmd == '-') {
string key;
cin >> key;
item.setKey(key);
}
switch (cmd) {
case 'H':
case 'h':
print_help();
break;
case '+':
table.insert(item);
cout << "Inserted data item with key ("
<< item.getKey() << ") and value ("
<< item.getValue() << ")" << endl;
break;
case '-':
if (table.remove(item.getKey())) {
cout << "Removed data item with key ("
<< item.getKey() << ")" << endl;
} else {
cout << "Could not remove data item with key ("
<< item.getKey() << ")" << endl;
}
break;
case '?':
if (table.retrieve(item.getKey(), item)) {
cout << "Retrieved data item with key ("
<< item.getKey() << ") and value ("
<< item.getValue() << ")" << endl;
} else {
cout << "Could not retrieve data item with key ("
<< item.getKey() << ")" << endl;
}
break;
case 'C':
case 'c':
cout << "Clear the hash table" << endl;
table.clear();
break;
case 'E':
case 'e':
cout << "Hash table is "
<< (table.isEmpty() ? "" : "NOT")
<< " empty" << endl;
break;
case 'Q':
case 'q':
return 0;
default:
cout << "Invalid command" << endl;
}
} while (1);
return 0;
}
test10std.cpp
//--------------------------------------------------------------------
//
// Laboratory 10 test10std.cpp
//
// Test program for the standard deviation operation in the Hash Table ADT
//
//--------------------------------------------------------------------
#include <cmath>
#include <string>
#include <iostream>
#include <fstream>
#include "HashTable.cpp"
using namespace std;
struct Data
{
public:
void setKey ( string newKey ) { key = newKey; }
string getKey () const { return key; }
static unsigned int hash(const string& str)
{
// Uncomment each of these as you try them out.
//-----------------------
// Hash Algorithm 1
//-----------------------
// return 0;
//-----------------------
// Hash Algorithm 2
//-----------------------
// return int(str[0])*10 + str.length();
//-----------------------
// Hash Algorithm 3
//-----------------------
// double val = 0;
// for (int i=0; i<str.length(); i++)
// val += (val*1.1)+str[i];
// return int (val);
// Add your two hash algorithms below
//-----------------------
// Hash Algorithm 4
//-----------------------
//-----------------------
// Hash Algorithm 5
//-----------------------
}
private:
string key;
};
int main()
{
HashTable<Data, string> testTbl(64);
Data testData;
string key;
ifstream data("std-dev.dat");
if( ! data )
{
cerr << "Error opening 'std-dev.dat'" << endl;
}
else
{
while( data >> key )
{
testData.setKey( key );
testTbl.insert( testData );
}
testTbl.showStructure();
cout << endl << endl;
cout << "The standard deviation is "
<< testTbl.standardDeviation() << endl;
}
}
Explanation / Answer
#include<iostream>
#include<cstdio>
#include<cstdlib>
/*
* Node Declaration
*/
using namespace std;
struct node
{
int info;
struct node *next;
struct node *prev;
}*start;
/*
Class Declaration
*/
class double_llist
{
public:
void create_list(int value);
void add_begin(int value);
void add_after(int value, int position);
void delete_element(int value);
void search_element(int value);
void display_dlist();
void count();
void reverse();
double_llist()
{
start = NULL;
}
};
/*
* Main: Conatins Menu
*/
int main()
{
int choice, element, position;
double_llist dl;
while (1)
{
cout<<endl<<"----------------------------"<<endl;
cout<<endl<<"Operations on Doubly linked list"<<endl;
cout<<endl<<"----------------------------"<<endl;
cout<<"1.Create Node"<<endl;
cout<<"2.Add at begining"<<endl;
cout<<"3.Add after position"<<endl;
cout<<"4.Delete"<<endl;
cout<<"5.Display"<<endl;
cout<<"6.Count"<<endl;
cout<<"7.Reverse"<<endl;
cout<<"8.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch ( choice )
{
case 1:
cout<<"Enter the element: ";
cin>>element;
dl.create_list(element);
cout<<endl;
break;
case 2:
cout<<"Enter the element: ";
cin>>element;
dl.add_begin(element);
cout<<endl;
break;
case 3:
cout<<"Enter the element: ";
cin>>element;
cout<<"Insert Element after postion: ";
cin>>position;
dl.add_after(element, position);
cout<<endl;
break;
case 4:
if (start == NULL)
{
cout<<"List empty,nothing to delete"<<endl;
break;
}
cout<<"Enter the element for deletion: ";
cin>>element;
dl.delete_element(element);
cout<<endl;
break;
case 5:
dl.display_dlist();
cout<<endl;
break;
case 6:
dl.count();
break;
case 7:
if (start == NULL)
{
cout<<"List empty,nothing to reverse"<<endl;
break;
}
dl.reverse();
cout<<endl;
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
return 0;
}
/*
* Create Double Link List
*/
void double_llist::create_list(int value)
{
struct node *s, *temp;
temp = new(struct node);
temp->info = value;
temp->next = NULL;
if (start == NULL)
{
temp->prev = NULL;
start = temp;
}
else
{
s = start;
while (s->next != NULL)
s = s->next;
s->next = temp;
temp->prev = s;
}
}
/*
* Insertion at the beginning
*/
void double_llist::add_begin(int value)
{
if (start == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp;
temp = new(struct node);
temp->prev = NULL;
temp->info = value;
temp->next = start;
start->prev = temp;
start = temp;
cout<<"Element Inserted"<<endl;
}
/*
* Insertion of element at a particular position
*/
void double_llist::add_after(int value, int pos)
{
if (start == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *tmp, *q;
int i;
q = start;
for (i = 0;i < pos - 1;i++)
{
q = q->next;
if (q == NULL)
{
cout<<"There are less than ";
cout<<pos<<" elements."<<endl;
return;
}
}
tmp = new(struct node);
tmp->info = value;
if (q->next == NULL)
{
q->next = tmp;
tmp->next = NULL;
tmp->prev = q;
}
else
{
tmp->next = q->next;
tmp->next->prev = tmp;
q->next = tmp;
tmp->prev = q;
}
cout<<"Element Inserted"<<endl;
}
/*
* Deletion of element from the list
*/
void double_llist::delete_element(int value)
{
struct node *tmp, *q;
/*first element deletion*/
if (start->info == value)
{
tmp = start;
start = start->next;
start->prev = NULL;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = start;
while (q->next->next != NULL)
{
/*Element deleted in between*/
if (q->next->info == value)
{
tmp = q->next;
q->next = tmp->next;
tmp->next->prev = q;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = q->next;
}
/*last element deleted*/
if (q->next->info == value)
{
tmp = q->next;
free(tmp);
q->next = NULL;
cout<<"Element Deleted"<<endl;
return;
}
cout<<"Element "<<value<<" not found"<<endl;
}
/*
* Display elements of Doubly Link List
*/
void double_llist::display_dlist()
{
struct node *q;
if (start == NULL)
{
cout<<"List empty,nothing to display"<<endl;
return;
}
q = start;
cout<<"The Doubly Link List is :"<<endl;
while (q != NULL)
{
cout<<q->info<<" <-> ";
q = q->next;
}
cout<<"NULL"<<endl;
}
/*
* Number of elements in Doubly Link List
*/
void double_llist::count()
{
struct node *q = start;
int cnt = 0;
while (q != NULL)
{
q = q->next;
cnt++;
}
cout<<"Number of elements are: "<<cnt<<endl;
}
/*
* Reverse Doubly Link List
*/
void double_llist::reverse()
{
struct node *p1, *p2;
p1 = start;
p2 = p1->next;
p1->next = NULL;
p1->prev = p2;
while (p2 != NULL)
{
p2->prev = p2->next;
p2->next = p1;
p1 = p2;
p2 = p2->prev;
}
start = p1;
cout<<"List Reversed"<<endl;
}
#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
/*
* Class Declaration
*/
class BinaryHeap
{
private:
vector <int> heap;
int left(int parent);
int right(int parent);
int parent(int child);
void heapifyup(int index);
void heapifydown(int index);
public:
BinaryHeap()
{}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void DisplayHeap();
int Size();
};
/*
* Return Heap Size
*/
int BinaryHeap::Size()
{
return heap.size();
}
/*
* Insert Element into a Heap
*/
void BinaryHeap::Insert(int element)
{
heap.push_back(element);
heapifyup(heap.size() -1);
}
/*
* Delete Minimum Element
*/
void BinaryHeap::DeleteMin()
{
if (heap.size() == 0)
{
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
/*
* Extract Minimum Element
*/
int BinaryHeap::ExtractMin()
{
if (heap.size() == 0)
{
return -1;
}
else
return heap.front();
}
/*
* Display Heap
*/
void BinaryHeap::DisplayHeap()
{
vector <int>::iterator pos = heap.begin();
cout<<"Heap --> ";
while (pos != heap.end())
{
cout<<*pos<<" ";
pos++;
}
cout<<endl;
}
/*
* Return Left Child
*/
int BinaryHeap::left(int parent)
{
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}
/*
* Return Right Child
*/
int BinaryHeap::right(int parent)
{
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}
/*
* Return Parent
*/
int BinaryHeap::parent(int child)
{
int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;
}
/*
* Heapify- Maintain Heap Structure bottom up
*/
void BinaryHeap::heapifyup(int in)
{
if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in])
{
int temp = heap[in];
heap[in] = heap[parent(in)];
heap[parent(in)] = temp;
heapifyup(parent(in));
}
}
/*
* Heapify- Maintain Heap Structure top down
*/
void BinaryHeap::heapifydown(int in)
{
int child = left(in);
int child1 = right(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
{
child = child1;
}
if (child > 0 && heap[in] > heap[child])
{
int temp = heap[in];
heap[in] = heap[child];
heap[child] = temp;
heapifydown(child);
}
}
/*
* Main Contains Menu
*/
int main()
{
BinaryHeap h;
while (1)
{
cout<<"------------------"<<endl;
cout<<"Operations on Heap"<<endl;
cout<<"------------------"<<endl;
cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Minimum Element"<<endl;
cout<<"3.Extract Minimum Element"<<endl;
cout<<"4.Print Heap"<<endl;
cout<<"5.Exit"<<endl;
int choice, element;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element to be inserted: ";
cin>>element;
h.Insert(element);
break;
case 2:
h.DeleteMin();
break;
case 3:
cout<<"Minimum Element: ";
if (h.ExtractMin() == -1)
{
cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
break;
case 4:
cout<<"Displaying elements of Hwap: ";
h.DisplayHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.