As I mentioned, your program will create and manipulate a linked list of nodes of type LinkNode (already defined for you) that contains 2 pieces of data: a name, and an integer number.

The node structure is given to you as:

struct LinkNode { string name; int number; LinkNode *link; }; 

You can see this definition in the lab09_header.h file.

Your program will do the following (and in the following order, as seen in the lab09.cpp file provided for you):

create a linked list of variable length (for example, nodes A->B->C).

print that linked list.

reverse that linked list (so that A->B->C becomes C->B->A, for example).

print that linked list again.

insert a node in that list based on an insertion point position in the list (so that A->B->C becomes A->B->X->C, for example, if you chose the insertion point to be after the 2nd node).

print that linked list again.

find the largest value in your linked list (i.e. a maximum).

find the smallest value in your linked list (i.e. a minimum).

Your program must call upon 8 functions that you will have to define for this lab.

I have given you a main program to use (lab09.cpp). You have to edit the functions file (lab09_functions.cpp) that contains the definitions of all the functions used in this lab and, in the end, compile the files together. You can compile all these together using the Makefile that Ive provided for you (see section on compilation below for more details).

Your functions are declared as follows (see the lab09_headers.h file):

typedef LinkNode* LinkNodePtr; void h_insert(LinkNodePtr& head, string nom, int num); void createLL(LinkNodePtr& h); void reverseLL(LinkNodePtr& h); void insertNodeAfter(LinkNodePtr h); void findMax(LinkNodePtr h); void findMin(LinkNodePtr h); void printLL(LinkNodePtr h); 

Here are description of each of what these functions must do. Remember that all linked lists (LL) start with a header link that points to the start of the LL:

a) createLL and h_insert: createLL() is the main one of these 2 (i.e. it calls h_insert). It takes the head link (which is, at first, a NULL pointer) and starts adding nodes to it using another function called h_insert(). h_insert() is actually all defined for you and you do not need to edit it further. The program asks the user to: Enter name, then a number. To quit, enter 0 for the name AND 0 for the number:

The user then enters two inputs via cin - a name (string) and an integer number. These two variables, along with the header link, get passed on to h_insert(). This happens in a loop until 0 0 are entered.

b) reverseLL: Takes the head link and proceeds to reverse the links of the LL created by createLL(). Think carefully about how to implement this. HINT: Define links that are about the current node youre looking at, as well as what the next node is and what the previous node is.

c) findMax and findMin: These functions go thru the LL and respectively print out the largest and smallest integers in the number field that they find.

d) insertNodeAfter: Takes the head link as input. It asks the user for a node position to insert a new node after that position, by asking: Enter node position to insert new node after (enter negative number to exit): . Node positions START with the number 0. The function should then:

Quit (return) if a negative position is given.

Otherwise, it should:

Determine how many positions (i.e. how many nodes) exist in the LL.

If the position given by the user is too big, then the function should say: Position entered is illegal. Nothing inserted. (with a newline) and quit (return).

Otherwise, it should:

Ask the user for the data (i.e. name and number) for the new node by asking: Enter data (name, then number):

Create a new node with this data and (the trickiest part) insert it in the LL.

e) printLL: Takes the head link and prints out all the nodes data as follows:

Printing the list: Node #0: ,  Node #1: ,  Node #2: ...etc... 

See the sample test runs shown below.

SAMPLE RUNS

Sample Run 1: We enter data for 4 nodes, print them, reverse them, and print them again. We then ask the user to insert, but we exit from that process by entering a -1. The list is then printed (one more time) and the maximum and minimum values of the numbers in the LL are given.

Enter name, then a number. To quit, enter 0 for the name AND 0 for the number: Amy 42 Enter name, then a number. To quit, enter 0 for the name AND 0 for the number: Jim 12 Enter name, then a number. To quit, enter 0 for the name AND 0 for the number: Marty -21 Enter name, then a number. To quit, enter 0 for the name AND 0 for the number: Jojo 11 Enter name, then a number. To quit, enter 0 for the name AND 0 for the number: 0 0 Printing the list: Node #0: Jojo, 11 Node #1: Marty, -21 Node #2: Jim, 12 Node #3: Amy, 42 -------- Reversing the list... Printing the list: Node #0: Amy, 42 Node #1: Jim, 12 Node #2: Marty, -21 Node #3: Jojo, 11 -------- Enter node position to insert new node after (enter negative number to exit): -1 Printing the list: Node #0: Amy, 42 Node #1: Jim, 12 Node #2: Marty, -21 Node #3: Jojo, 11 -------- Largest number in the list is: 42 Smallest number in the list is: -21

#include "lab09_functions.cpp" int main() { // Define the node and its pointer type // Actual node structure defined in lab09_headers.h LinkNode node; LinkNodePtr head = NULL; //1 and 2. Create a linked list of variable length and then print it. createLL(head); printLL(head); //3 and 4. Reverse this linked list and then print it. reverseLL(head); printLL(head); //5 and 6. Insert a node inside this linked list, based on a position number insertNodeAfter(head); printLL(head); // 7 and 8. Find and print the largest, and then the smallest, number in the linked list data findMax(head); findMin(head); return 0; }

#include  #include  #include  using namespace std; struct LinkNode { string name; int number; LinkNode *link; }; typedef LinkNode* LinkNodePtr; // Please note the use of static type here. Don't worry about its general use. // For this project, we are using it to aid in easier compilation of the multiple files. // There is no need to delve into it any further than that... static void h_insert(LinkNodePtr& head, string nom, int num); static void printLL(LinkNodePtr h); static void createLL(LinkNodePtr& h); static void reverseLL(LinkNodePtr& h); static void findMax(LinkNodePtr h); static void findMin(LinkNodePtr h); static void insertNodeAfter(LinkNodePtr h);

/* * This file contains all the functions that are called in lab09.cpp * The student(s) have to create these functions. * Make sure to include your and your partners names in these comments! * * Please note the use of static type here for the void functions. Don't worry about its general use. * For this project, we are using it to aid in easier compilation of the multiple files. * There is no need to delve into it any further than that... */ #include "lab09_headers.h" // Used in the function createLL() // This function is given to you correctly - there is no need to change it static void h_insert(LinkNodePtr& head, string nom, int num) { LinkNodePtr tmp_ptr; tmp_ptr = new LinkNode; tmp_ptr->name = nom; tmp_ptr->number = num; tmp_ptr->link = head; head = tmp_ptr; } static void createLL(LinkNodePtr& h) { // Incomplete function - student must complete string nom = ""; int num; while(0) // THIS IS A STUB { cout << "Enter name, then a number. To quit, enter 0 for the name AND 0 for the number: "; cin >> nom >> num; // Incomplete code here... // At some point, you call: h_insert(h, nom, num); } } static void reverseLL(LinkNodePtr& h) { // Incomplete function - student must complete cout << "reverseLL "; // THIS IS A STUB } static void findMax(LinkNodePtr h) { // Incomplete function - student must complete int max(0); cout << "Largest number in the list is: " << max << endl; } static void findMin(LinkNodePtr h) { // Incomplete function - student must complete int min(0); cout << "Smallest number in the list is: " << min << endl; } static void insertNodeAfter(LinkNodePtr h) { // Incomplete function - student must complete cout << "insertNodeAfter "; // THIS IS A STUB } static void printLL(LinkNodePtr h) { // Incomplete function - student must complete cout << "printLL "; // THIS IS A STUB }

all: lab09_functions.cpp lab09.cpp lab09_headers.h g++ -c lab09_functions.cpp -o functions.o -std=c++11 g++ -c lab09.cpp -o main.o -std=c++11 g++ -o lab09 main.o functions.o -std=c++11 clean: rm -f *o lab09