C/C++ (No classes allowed, No object-oriented programming)

ReadFile

Create a linked list from an input file (input.txt) that contains an even number of first names. The number of items in the file is unknown.

SplitMerge

Create a split function that divides the newly created linked list into two equal sublists: myList1 and myList2. For example, originally you would point to (John, Jack, Jill, Jim). After the split, myList1 would point to john and jack and myList2 would point to jill and Jim.

Traverse

Accepts a pointer and displays each of the lists (myList1 and myList2 on the screen) Note: the traverse function takes only one argument, so the function would have to be called twice, once for each of the lists.

Merge

Feed the pointer variables myList1 and myList2 into the Merge function. Create a single list. Return the list.

Traverse

Pass in the pointer variable and display the returned list from the Merge function

Summary:

You need to write at least 5 functions:

main

readFile

splitMerge

merge

traverse.

The inputs will come from one input files (input.txt). There is no output file. The program should be in a single .cpp file.

From within main call

ReadFile (Read the contents of file, create a linked list and return the list to main)

SplitAndMerge (pass list, splits into list 1 and list 2, void return)

From within splitMerge

call Traverse (Display contents of list1)

call Traverse (Display contents of list2)

call Merge (Pass list1 and list2, merge and return one list)

call Traverse (Display contents of list coming back from Merge)

Quick Summary:

• You will read a bunch of names from a file.
• Each one of the names will be stored inside of a node.
• So far in our examples, the data that we have been storing has been of type int.
• However, now we want to store data that is a string.
• You can declare your data variable for your node as a char array (The size can be 10).

• You will be using a while loop when reading from a file.
• As long as you have not reached the end, each iteration will read one name from the file and insert it into a node.
• As you are creating your nodes inside the while loop, you can have a counter that counts the number of nodes that are being created.

• Now that you have your linked list and also have a count of the number of nodes that make up the linked list, you can split it in two.
• For this you can just use a for loop and iterate up to the half-way mark in your linked list.
• The end result should give you two pointers, pointing to the beginning and the middle of your linked list.

• You can display the data contents of each of your nodes in your linked list using a while loop as long as you have not reached the end of your list.

• Those two pointers from your split function will then be sent to a merge function that will connect the last node in one linked list to the first node in the other linked list.

//HINT

int main() {

node *list;

list = read();

splitMerge(list);

}

void split(node *head){

node *list1 = head;

node *current, *list2;

}

//Split the list

traverse(list1);

traverse(list2);

merge(list1, list2);

traverse(list1);

}