IN C++ please

This lesson covers recursion. At first read, recursion is not all that intuitive. So please take your time with the material and work through the examples yourself. Then, I am sure it will make sense to you. Also, drawing diagrams can be very helpful.

For the assignment, we will add material to the programming assignment from chapter 18. ( If you did not complete that work, then uses the NumberList class as discussed in chapter 20. But you will still have to build the menu-driven program from before.)

One thing that I did not like about the material from this chapter is that it had mutator and accessor functions displaying directly to the screen. Remember, we only do that to notify of an exit_failure. All other information should be passed back and handled through the higher-level calling functions.

Using the Programming Assignment from Chapter 18 (Linked List) as a place to start, please complete the following: 1. Fix any errors that you had in Chapter 18 (Linked List) the first time. 2. Add the following functionality to your menu: Count Number of Nodes. Display the Largest Node in the list. Programming Rules: 1. Review the grading notes for your Chapter 18 (Linked List) submission. FIX ALL ERRORS AND SUGGESTIONS. 2. Modify your menu to add these two items: Count Number of Nodes and Display Largest Node. 3. Add the following to your NumberList class: numNodes which returns the number of nodes in the linked list, and maxNode which should return the largest value** stored in the list. **Note, assume Z has a higher value than A. 4. In both cases, use recursion in the function to traverse the list. If you do not use recursion to traverse the list then you will lose 25 points on this assignment. This is not me kidding around. Since the code for numNodes and it's associated private member function, countNodes, is written in the book, this is not a terribly taxing assignment. ---------------------- ----------------------

Demo the program as follows:

append node

append node

append node

append node

append node

print list

insert at position

display list

display number of nodes

display max node

delete at position

print list

display number of nodes

display max node

----------------

Submit to me:

1. all of your .cpp and .h files

Should be 3 files

main.cpp // for your menu driving function

.cpp // for member function implementation

.h // Where your class declaration is stored

------------------------------------------------------

Chapter 18 Reference code

The class declaration, which is saved in NumberList.h , is shown here:

1 // Specification file for the NumberList class 2 #ifndef NUMBERLIST_H 3 #define NUMBERLIST_H 4 5 class NumberList 6 { 7 private: 8 // Declare a structure for the list 9 struct ListNode 10 { 11 double value; //The value in this node 12 struct ListNode *next; // To point to the next node 13 }; 14 15 ListNode *head; // List head pointer 16 17 // Private member functions 18 int countNodes(ListNode *) const; 19 void showReverse(ListNode *) const; 20 21 public: 22 // Constructor 23 NumberList() 24 { head = nullptr; } 25 26 // Destructor 27 ~NumberList(); 28 29 // Linked List Operations 30 void appendNode(double); 31 void insertNode(double); 32 void deleteNode(double); 33 void displayList() const; 34 int numNodes() const 35 { return countNodes(head); } 36 void displayBackwards() const 37 { showReverse(head); } 38 }; 39 #endif

Appending a Node

Here is the actual C++ code for the function: 11 void NumberList::appendNode(double num) 12 { 13 ListNode *newNode; // To point to a new node 14 ListNode *nodePtr; // To move through the list 15 16 // Allocate a new node and store num there. 17 newNode = new ListNode; 18 newNode->value = num; 19 newNode->next = nullptr; 20 21 // If there are no nodes in the list 22 // make newNode the first node. 23 if (!head) 24 head = newNode; 25 else // Otherwise, insert newNode at end. 26 { 27 // Initialize nodePtr to head of list. 28 nodePtr = head; 29 30 // Find the last node in the list. 31 while (nodePtr->next) 32 nodePtr = nodePtr->next; 33 34 // Insert newNode as the last node. 35 nodePtr->next = newNode; 36 } 37 } Traversing a Linked list

45 void NumberList::displayList() const 46 { 47 ListNode *nodePtr; // To move through the list 48 49 // Position nodePtr at the head of the list. 50 nodePtr = head; 51 52 // While nodePtr points to a node, traverse 53 // the list. 54 while (nodePtr) 55 { 56 // Display the value in this node. 57 cout << nodePtr->value << endl; 58 59 // Move to the next node. 60 nodePtr = nodePtr->next; 61 } 62 }

Inderting a Node

69 void NumberList::insertNode(double num) 70 { 71 ListNode *newNode; // A new node 72 ListNode *nodePtr; // To traverse the list 73 ListNode *previousNode = nullptr; // The previous node 74 75 // Allocate a new node and store num there. 76 newNode = new ListNode; 77 newNode->value = num; 78 79 // If there are no nodes in the list 80 // make newNode the first node 81 if (!head) 82 { 83 head = newNode; 84 newNode->next = nullptr; 85 } 86 else // Otherwise, insert newNode 87 { 88 // Position nodePtr at the head of list. 89 nodePtr = head; 90 91 // Initialize previousNode to nullptr. 92 previousNode = nullptr; 93 94 // Skip all nodes whose value is less than num. 95 while (nodePtr != nullptr && nodePtr->value < num) 96 { 97 previousNode = nodePtr; 98 nodePtr = nodePtr->next; 99 } 100 101 // If the new node is to be the 1st in the list, 102 // insert it before all other nodes. 103 if (previousNode == nullptr) 104 { 105 head = newNode; 106 newNode->next = nodePtr; 107 } 108 else // Otherwise insert after the previous node. 109 { 110 previousNode->next = newNode; 111 newNode->next = nodePtr; 112 } 113 } 114 }

Deleting a Node

122 void NumberList::deleteNode(double num) 123 { 124 ListNode *nodePtr; // To traverse the list 125 ListNode *previousNode; // To point to the previous node 126 127 // If the list is empty, do nothing. 128 if (!head) 129 return; 130 131 // Determine if the first node is the one. 132 if (head->value == num) 133 { 134 nodePtr = head->next; 135 delete head; 136 head = nodePtr; 137 } 138 else 139 { 140 // Initialize nodePtr to head of list 141 nodePtr = head; 142 143 // Skip all nodes whose value member is 144 // not equal to num. 145 while (nodePtr != nullptr && nodePtr->value != num) 146 { 147 previousNode = nodePtr; 148 nodePtr = nodePtr->next; 149 } 150 151 // If nodePtr is not at the end of the list, 152 // link the previous node to the node after 153 // nodePtr, then delete nodePtr. 154 if (nodePtr) 155 { 156 previousNode->next = nodePtr->next; 157 delete nodePtr; 158 } 159 } 160 }

Destroying the list

167 NumberList::~NumberList() 168 { 169 ListNode *nodePtr; // To traverse the list 170 ListNode *nextNode; // To point to the next node 171 172 // Position nodePtr at the head of the list. 173 nodePtr = head; 174 175 // While nodePtr is not at the end of the list... 176 while (nodePtr != nullptr) 177 { 178 // Save a pointer to the next node. 179 nextNode = nodePtr->next; 180 181 // Delete the current node. 182 delete nodePtr; 183 184 // Position nodePtr at the next node. 185 nodePtr = nextNode; 186 } 187 }

Chapter 20 Reference code:

Counting the Nodes in the List

173 int NumberList::countNodes(ListNode *nodePtr) const 174 { 175 if (nodePtr != nullptr) 176 return 1 + countNodes(nodePtr->next); 177 else 178 return 0; 179 }

Displaying List Nodes in Reverse Order

187 void NumberList::showReverse(ListNode *nodePtr) const 188 { 189 if (nodePtr != nullptr) 190 { 191 showReverse(nodePtr->next); 192 cout << nodePtr->value << " "; 193 } 194 }

There are more details on this code in the book here is a reference to the book if your interested:

http://www.allitebooks.in/starting-c-control-structures-objects-9th-edition/