In C++. Thanks.

For this program you will be writing and testing a merge function. This function will be like the merge function that belongs to List in the STL, in that it will only work if you are working with list that are already sorted. If you were to use the function like this: list1.merge( list2 ); then all of the data from list2 would be moved into list1 in the correct places. After the merge is completed list2 should be an empty List that can be used again (in the main, I call the clear function for list2, but this should not be needed).

Note: in the merge, you must move as many nodes as possible with each "move"...meaning you can't just call insert or manually move one node at a time unless one node is all that needs to be moved with that move.

Here are the files that includes main and a simple linked list class (only part of it is finished) that you can use to learn and write your merge function. (Note: if you have problems with the link, the program files can be found on Canvas in the Course Resources section of Files). The only part of the code that you need to write is the merge function. You will also need to un-comment all the various test in main as you are ready to use them with your member function.

Here are some helper files: Merge Work sheet.pdf

Actions

Linked List Merge Example.pdf

Actions

Project Hint 1: Compile and run the given file after you download them and and add/copy them a Visual Studio project to make sure it will work before you start to change things.

I would really encourage you to use the debugger to examine data during run time and follow the execution of your code.

Project Hint 2: If you take care of the special cases like moving all the node that go before or after the target list, it will then make it easier to move the nodes that will go within the middle of the target list.

For turn in you need to turn in the code for the merge function and the output from main when you have all 8 test uncommented. Put a normal program header before the print out of your merge function.

///

#ifndef LKLIST_H

#define LKLIST_H

#include

using namespace std;

class LkList {

class Node {

public:

Node() {

next = prev = nullptr;

}

Node(int num) {

data = num; next = prev = nullptr;

}

int data;

Node *next;

Node *prev;

};

public:

LkList();

// virtual ~LkList();

// LkList(const LkList& other);

// LkList& operator=(const LkList& other);

bool insert(int num);

void insert(const initializer_list& il);

void merge(LkList & src);

void resetIterator();

bool hasMore();

int next();

int size();

void clear();

private:

Node *head, *tail, *it;

int count;

};

ostream& operator << (ostream & outStr, LkList& lst);

#endif // LKLIST_H

//////

#include "stdafx.h"

#include "LkList.h"

#include

using namespace std;

void LkList::merge(LkList & src) {

// this is what you need to write.....

} // end of merge function

LkList::LkList() {

head = nullptr;

tail = nullptr;

it = nullptr;

count = 0;

}

//LkList::~LkList(){}

//LkList::LkList(const LkList& other){}

//LkList& LkList::operator=(const LkList& rhs){}

int LkList::size() {

return count;

}

bool LkList::insert(int num) {

if (count == 0) { // empty list

head = tail = new Node(num);

}

else { // >1 count, then add back

Node* temp = new Node(num);

tail->next = temp;

temp->prev = tail;

tail = temp;

}

count++;

return true;

}

void LkList::insert(const initializer_list& il) {

for (int ele : il) {

insert(ele);

}

}

void LkList::clear() {

if (count == 0)

return;

while (tail != head) {

tail = tail->prev;

delete tail->next;

}

delete head;

head = tail = nullptr;

count = 0;

}

void LkList::resetIterator() {

it = head;

}

bool LkList::hasMore() {

return (it != nullptr);

}

int LkList::next() {

int num = it->data;

it = it->next;

return num;

}

ostream& operator << (ostream & outStr, LkList & lst) {

lst.resetIterator();

while (lst.hasMore())

outStr << lst.next() << " ";

return outStr;

}

/////

#include "stdafx.h"

#include

#include

#include "LkList.h"

using namespace std;

int main() {

LkList list, list2;

//

//list.insert( { 0, 10, 20, 30, 40} );

//list2.insert( { 1, 2, 3, 5, 11, 12, 13, 26, 27, 28, 29, 34, 35, 36, 37, 44, 45, 46, 47} );

//

//list.merge(list2);

//

//cout << "Merge #1 (source overlaps destination): " << list << endl;

//cout << "List size after merge: " << list.size() << endl;

//cout << endl << endl;

//

//list.clear();

//list2.clear();

//------------------------

//list.merge(list2);

//

//cout << "Merge #2 (empty merge): " << list << endl;

//cout << "List size after merge: " << list.size() << endl;

//cout << endl << endl;

//list.clear();

//list2.clear();

//------------------------

//list2.insert( { 0, 10, 20, 30, 40 } );

//list.merge(list2);

//cout << "Merge #3 (into an empty list): " << list << endl;

//cout << "List size after merge: " << list.size() << endl;

//cout << endl << endl;

//list.clear();

//list2.clear();

//------------------------

//

//list.insert( { 0, 5, 10, 15, 20, 25, 30, 35, 40} );

//

//

//list.merge(list2);

//

//cout << "Merge #4 (from an empty list): " << list << endl;

//cout << "List size after merge: " << list.size() << endl;

//cout << endl << endl;

//

//list.clear();

//list2.clear();

//------------------------

//list.insert( { 40, 47, 54, 61, 68 } );

//

//list2.insert( { 0, 3, 6, 9, 12, 15, 18 } );

//list.merge(list2);

//cout << "Merge #5(source before destination): " << list << endl;

//cout << "List size after merge: " << list.size() << endl;

//cout << endl << endl;

//

//list.clear();

//list2.clear();

//

//------------------------

//list.insert( { 10, 17, 21, 28 } );

//

//list2.insert( { 50, 53, 56, 59, 62, 65 } );

//

//list.merge(list2);

//

//cout << "Merge #6(source after destination): " << list << endl;

//cout << "List size after merge: " << list.size() << endl;

//cout << endl << endl;

//

//list.clear();

//list2.clear();

//------------------------

//list.insert( { 0, 9, 18, 27 } );

//

//list2.insert( { -6, -4, -2, 0, 2, 4, 6, 8, 10, 12, 16,

// 18, 20, 22, 24, 26, 28, 30, 32, 34 } );

//

//list.merge( list2 );

//

//cout << "Merge #7(source overlaps destination): " << list << endl;

//cout << "List size after merge: " << list.size() << endl;

//cout << endl << endl;

//

//list.clear();

//list2.clear();

//------------------------

//list.insert( { -6, 2, 10, 18, 26, 34 } );

//

//list2.insert( { 10, 13, 16, 19, 22, 25 } );

//

//list.merge( list2 );

//

//cout << "Merge #8(source within destination): " << list << endl;

//cout << "List size after merge: " << list.size() << endl;

//cout << endl << endl;

//

//list.clear();

//list2.clear();

//------------------------

system("pause");

return 0;

}