# 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 * City;

char * State;

int Zip;

int Social_num ;

}

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) {

}

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"; } } ```