-
Home
-
Dictionary Homework Solution with C++
Dictionary Assignment
Modify the “Dictionary (program).txt file and must ensure to add the merge function as described as below.
A dictionary is a list of elements composed of similar data ordered by a subset of the data called a "key". For example considerer the following structure for a government database:
struct veterant {
char * Name;
char * Address;
char * City;
char * State;
int Zip[5];
int Social_num [9];
}
Since Social_num uniquely identifies each veterant, is the "key" for which the dictionary is then ordered, that is, for example, a key: 150453456 comes before key: 154567899, since the first social number is less the second one.
You must write a function called Merge
SortedChain& SortedChain:: Merge (SortedChain & S2 const) {
------- write your function
}
that does the following:
Suppose that we declare the following two dictionary objects:
main {
SortedChain Chain1;
SortedChain Chain2;
Suppose Chain1 is : 
Where 5, 8 and 9 are the keys, and suppose
Chain2 is: 
Then Chain1.Merge(Chain2) should be:
The Merge function will change Chain1, thus you must return a reference to
Chain1
That is return (*this).
Solution:
#include < iostream>
using namespace std;
struct veterant {
char * Name;
char * Address;
char * City;
char * State;
int Zip;
int Social_num;
int Key() {
return Social_num;
}
char * Value() {
return Name;
}
};
// exception is thrown if wrong input
class BadInput {
public:
BadInput() {};
};
template
struct Node {
E data;
Node *next;
};
template
class SortedChain {
public:
SortedChain() {
first = NULL;
}
~SortedChain();
bool IsEmpty() {
return ( first == NULL );
}
int Length() const {
int count = 0;
Node *current = first;
while ( current != NULL ) {
count++;
current = current->next;
}
return count;
}
// bool Search (const K& k, const E& e);
SortedChain& Delete(const K& k, E& e);
SortedChain& Insert(const K& k,const E& e);
SortedChain& Merge(const SortedChain & S2);
void Output() const;
private:
Node *first;
};
template
SortedChain::~SortedChain() {
Node *current = first;
while (first) {
current = first->next;
delete first;
first = current;
}
}
template
SortedChain& SortedChain::Delete(const K& k, E& e) {
Node *prior = first, *current = first;
while ( ( current != NULL ) && ( current->data ).Key() < k ) { // search until key = k or key > k
prior = current;
current = current->next;
}
if ( ( current != NULL ) && ( current->data ).Key() == k ) {
e = current->data;
if ( first == current ) { // delete first node
first = current->next;
} else {
prior->next = current->next;
}
delete current;
return *this;
} else {
throw BadInput();
}
}
template
SortedChain& SortedChain::Insert(const K& k, const E& e) {
Node *prior = first, *current = first;
while ( ( current != NULL ) && ( current->data ).Key() < k ) {
prior = current;
current = current->next;
}
if ( ( current != NULL ) && ( current->data ).Key() == k ) {
throw BadInput(); // another node with same key
} else {
Node *newp;
newp = new Node;
if ( first == current ) { // we like to insert on first position
first = newp;
} else {
prior->next = newp;
}
newp->next = current;
newp->data = e;
return *this;
}
}
template
SortedChain& SortedChain::Merge (const SortedChain & S2) {
Node *current_S2 = S2.first;
while ( current_S2 != NULL ) {
Insert( ( current_S2->data ).Key(), current_S2->data );
current_S2 = current_S2->next;
}
return *this;
}
template
void SortedChain::Output() const {
Node *current = first;
while ( current != NULL ) {
cout << "(" << ( current->data ).Key() << ", " << ( current->data ).Value() << ") -> ";
current = current->next;
}
cout << "END" << endl;
}
class TypeE {
public:
long key;
long value;
TypeE() {};
long Key() {
return key;
}
long Value() {
return value;
}
};
int main(int argc, char** argv) {
try {
SortedChain Chain;
SortedChain Chain_S2;
TypeE e;
SortedChain Chain_P1;
SortedChain Chain_P2;
struct veterant p;
e.key = 2;
e.value = 1000;
Chain.Insert(e.Key(),e);
e.key = 4;
e.value = 500;
Chain.Insert(e.Key(),e);
e.key = 6;
e.value = 1500;
Chain.Insert(e.Key(),e);
e.key = 1;
e.value = 3000;
Chain.Insert(e.Key(),e);
Chain.Output();
cout << Chain.Length() << endl;
Chain.Delete(2,e);
Chain.Output();
cout << Chain.Length() << endl;
e.key = 7;
e.value = 400;
Chain_S2.Insert(e.Key(), e);
e.key = 3;
e.value = 800;
Chain_S2.Insert(e.Key(), e);
e.key = 5;
e.value = 1200;
Chain_S2.Insert(e.Key(), e);
e.key = 2;
e.value = 2000;
Chain_S2.Insert(e.Key(), e);
Chain_S2.Output();
cout << Chain_S2.Length() << endl;
Chain.Merge( Chain_S2 );
Chain.Output();
cout << Chain.Length() << endl;
p.Name = (char*)"Rita R. Bateman";
p.Address = (char*)"4924 Bobcat Drive";
p.City = (char*)"Beltsville";
p.State = (char*)"Maryland";
p.Zip = 20705;
p.Social_num = 383381234;
Chain_P1.Insert(p.Social_num, p);
p.Name = (char*)"Gloria J. Hamilton";
p.Address = (char*)"762 Lindale Avenue";
p.City = (char*)"Oakland";
p.State = (char*)"California";
p.Zip = 94612;
p.Social_num = 616275678;
Chain_P1.Insert(p.Social_num, p);
p.Name = (char*)"Jill T. Smith";
p.Address = (char*)"3229 Pursglove Court";
p.City = (char*)"Dayton";
p.State = (char*)"Ohio";
p.Zip = 45402;
p.Social_num = 292248563;
Chain_P1.Insert(p.Social_num, p);
Chain_P1.Output();
cout << Chain_P1.Length() << endl;
p.Name = (char*)"Mary F. Mayfield";
p.Address = (char*)"4699 Fire Access Road";
p.City = (char*)"Asheboro";
p.State = (char*)"North Carolina";
p.Zip = 27203;
p.Social_num = 243843578;
Chain_P2.Insert(p.Social_num, p);
p.Name = (char*)"Stephen L. Dahl";
p.Address = (char*)"4437 Heliport Loop";
p.City = (char*)"New Albany";
p.State = (char*)"Indiana";
p.Zip = 47150;
p.Social_num = 310443879;
Chain_P2.Insert(p.Social_num, p);
p.Name = (char*)"Alex M. Cox";
p.Address = (char*)"2958 Rose Avenue";
p.City = (char*)"Kenner";
p.State = (char*)"Louisiana";
p.Zip = 70062;
p.Social_num = 662092991;
Chain_P2.Insert(p.Social_num, p);
Chain_P2.Output();
cout << Chain_P2.Length() << endl;
Chain_P1.Merge( Chain_P2 );
Chain_P1.Output();
cout << Chain_P1.Length() << endl;
} catch (BadInput) {
cerr << endl << "Bad Input";
}
}