I need help completing the following part of my assignment. I need help modifyin
ID: 3714450 • Letter: I
Question
I need help completing the following part of my assignment. I need help modifying the following code called program 1. Please someone help this is due tomorrow.
1. Copy Program 1 (say Program1.cpp) and save it as a new file, say Program2.cpp
2. In Program 2, modify the definitions of hashtable class and account class. Instead of using
linkedlist as the chaining collision resolution method, replace it with binary search tree.
3. In the binary search tree, only the account number is used as the key to construct and search
the tree.
4. Your program should contain at least two classes: account class, which is the node in the
binary search tree, and hashtable class, which is an array of pointers to account.
5. The structure of your hash table should look like this.
6. The constructor of your hashtable class should take one parameter n and create a table of size N, as described before. The signature of the constructor is:
hashtable(int n);
7. Your hashtable class should also support the following operations
? Insert an account: map an account to the table (array) index and then insert the account into the binary search tree of the located array index. The signature of this method is:
void insert(int account_number, string name, double balance);
? Remove an account: map an account to the table (array) index and then perform binary search by account_number on the binary search tree in the located array index and delete the found account. You should de-allocate space for the removed account. The signature of this method is:
void remove(int account_number, string name);
? Search an account: map an account to the table (array) index and then perform a binary search by account_number on the binary search tree in the located array index. It should return a pointer to the found account. If the account could not be found, return NULL. The signature of this method is:
account * search(int account_number, string name);
8. You might want to add more methods in your hashtable class, in order to make your program easy to read and implement.
9. Test your program to make sure it is implemented correctly.
Here is Program 1:
#include <iostream>
#include <string>
#include<malloc.h>
using namespace std;
bool findPrime(int n);
int getPrime(int);
int hash_code_map(int act, string name);
class node
{
public:
int account_number;
string name;
double balance;
node * next;
public:
node(int v, string n, double b);
node() {
this->next = NULL;
}
};
node::node(int v, string n, double b)
{
this->account_number = v;
this->name = n;
this->balance = b;
this->next = NULL;
}
class hashtable
{
public:
node **array;
int size;
public:
hashtable(int n);
void insert(int act, string n, double b);
void remove(int act, string name);
node * search(int act, string name);
};
hashtable::hashtable(int n)
{
{
node *nd = new node();
array[i] = nd;
}
}
void hashtable::insert(int act, string n, double b)
{
node *newNode = new node(act, n, b);
int index = hash_code_map(act, n);
index = index % (this->size);
if (array[index]->next == NULL)
{
array[index][0].account_number = newNode->account_number;
array[index][0].balance = newNode->balance;
array[index][0].name = newNode->name;
array[index][0].next = newNode->next;
}
else
{
int i = 0;
while (array[index][i].next != NULL)
{
i++;
}
array[index][i] = *newNode;
array[index][i-1].next = newNode;
}
}
void hashtable::remove(int act, string n)
{
int index = hash_code_map(act, n);
index = index % (this->size);
if (array[index] != NULL)
{
int i = 0;
if (array[index][i].account_number == act && array[index][i].name == n)
{
array[index] = NULL;
return;
}
i++;
while (array[index][i-1].next != NULL)
{
if (array[index][i].account_number == act && array[index][i].name == n)
{
array[index][i - 1].next = array[index][i + 1].next;
break;
}
i++;
}
}
}
node * hashtable::search(int act, string name)
{
int index = hash_code_map(act, name);
index = index % (this->size);
if (array[index] != NULL)
{
int i = 0;
if (array[index][i].account_number == act && array[index][i].name == name)
return (array[index]);
while (array[index][i].next != NULL)
{
if (array[index][i].account_number == act && array[index][i].name == name)
{
return (array[index]);
break;
}
i++;
}
}
return NULL;
}
int getPrime(int n)
{
while (true)
{
if (findPrime(++n))
break;
}
return n;
}
bool findPrime(int n)
{
if (n <= 1) return false;
// Check from 2 to n-1
for (int i = 2; i<n; i++)
if (n%i == 0)
return false;
return true;
}
int hash_code_map(int act, string name)
{
int n = act;
for (int i = 0; i < name.size(); i++)
{
n += int(name[i]);
}
return n;
}
int main()
{
hashtable ht(100);
ht.insert(2002, "Janet Smith", 100.99);
ht.insert(1001, "Alex Bush", 99.88);
ht.insert(3003, "John Rosa", 5.55);
node * n;
n = ht.search(1001, "Alex Bush");
if (n != NULL) cout << "the balalnc of account 1001 is " << n->balance
<< endl;
else cout << "could not find account 1001";
ht.remove(1001, "Alex Bush");
n = ht.search(1001, "Alex Bush");
if (n != NULL) cout << "the balalnc of account 1001 is " << n->balance
<< endl;
else cout << "could not find account 1001" << endl;
system("pause");
return 1;
}
Explanation / Answer
#include <iostream>
#include <string>
#include<malloc.h>
using namespace std;
bool findPrime(int n);
int getPrime(int);
int hash_code_map(int act, string name);
class node
{
public:
int account_number;
string name;
double balance;
node * next;
public:
node(int v, string n, double b);
node() {
this->next = NULL;
}
};
node::node(int v, string n, double b)
{
this->account_number = v;
this->name = n;
this->balance = b;
this->next = NULL;
}
class hashtable
{
public:
node **array;
int size;
public:
hashtable(int n);
void insert(int act, string n, double b);
void remove(int act, string name);
node * search(int act, string name);
};
hashtable::hashtable(int n)
{
{
node *nd = new node();
array[i] = nd;
}
}
void hashtable::insert(int act, string n, double b)
{
node *newNode = new node(act, n, b);
int index = hash_code_map(act, n);
index = index % (this->size);
if (array[index]->next == NULL)
{
array[index][0].account_number = newNode->account_number;
array[index][0].balance = newNode->balance;
array[index][0].name = newNode->name;
array[index][0].next = newNode->next;
}
else
{
int i = 0;
while (array[index][i].next != NULL)
{
i++;
}
array[index][i] = *newNode;
array[index][i-1].next = newNode;
}
}
void hashtable::remove(int act, string n)
{
int index = hash_code_map(act, n);
index = index % (this->size);
if (array[index] != NULL)
{
int i = 0;
if (array[index][i].account_number == act && array[index][i].name == n)
{
array[index] = NULL;
return;
}
i++;
node * hashtable::search(int act, string name)
{
int index = hash_code_map(act, name);
index = index % (this->size);
if (array[index] != NULL)
{
int i = 0;
if (array[index][i].account_number == act && array[index][i].name == name)
return (array[index]);
while (array[index][i].next != NULL)
{
if (array[index][i].account_number == act && array[index][i].name == name)
{
return (array[index]);
break;
}
i++;
}
}
return NULL;
}
int getPrime(int n)
{
while (true)
{
if (findPrime(++n))
break;
}
return n;
}
bool findPrime(int n)
{
if (n <= 1) return false;
for (int i = 2; i<n; i++)
if (n%i == 0)
return false;
return true;
}
int hash_code_map(int act, string name)
{
int n = act;
for (int i = 0; i < name.size(); i++)
{
n += int(name[i]);
}
return n;
}
int main()
{
hashtable ht(100);
ht.insert(2002, "Janet Smith", 100.99);
ht.insert(1001, "Alex Bush", 99.88);
ht.insert(3003, "John Rosa", 5.55);
node * n;
n = ht.search(1001, "Alex Bush");
if (n != NULL) cout << "the balalnc of account 1001 is " << n->balance
<< endl;
else cout << "could not find account 1001";
ht.remove(1001, "Alex Bush");
n = ht.search(1001, "Alex Bush");
if (n != NULL) cout << "the balalnc of account 1001 is " << n->balance
<< endl;
else cout << "could not find account 1001" << endl;
system("pause");
return 1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.