1: /** @file linked_node_functions.cpp
2: Implementation file corresponding to the specification file
3: linked_node_functions.h. The functions in this module are
4: used with the demonstration program in linked_node_main.cpp.
5: */
7: #include <iostream>
8: #include <iomanip>
9: using namespace std;
11: typedef int DataType;
12: struct Node
13: {
14: DataType data;
15: Node* link;
16: };
17: typedef Node* NodePointer;
20: void DescribeProgram()
21: {
22: cout << "\nThis is a demonstration program used to illustrate some "
23: "operations on a\nsequence of linked nodes containing integer "
24: "data values. It is best to\nrun it with pencil and paper in hand "
25: "and to draw a pictorial representation\nof what the sequence of "
26: "linked nodes will look like after you take any\nparticular action "
27: "offered by the menu."
29: "\n\nYou may display the data values in the nodes at any time for "
30: "purposes of\ncomparison. Each value is printed in six spaces, "
31: "with ten values per line.";
33: cout << "\n\nYou begin with an empty list, and a menu of options "
34: "from which to choose.\n\n\n\n\n\n\n\n\n\n\n\n";
35: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
36: }
39: void InitializeSequence
40: (
41: NodePointer& head //inout
42: )
43: {
44: head = nullptr;
45: }
48: void ReclaimStorage
49: (
50: NodePointer& head //in
51: )
52: {
53: while (head != nullptr)
54: {
55: NodePointer current = head;
56: head = head->link;
57: delete current;
58: }
59: }
63: void BuildSequenceFixedSize
64: (
65: NodePointer& head //inout
66: )
67: {
68: if (head != nullptr)
69: {
70: ReclaimStorage(head);
71: InitializeSequence(head);
72: }
73: cout << "Enter number of nodes you would like in the sequence: ";
74: int numNodes;
75: cin >> numNodes; cin.ignore(80, '\n');
76: if (numNodes <= 0)
77: {
78: cout << "\nNumber of nodes must be > 0.";
79: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
80: return;
81: }
82: cout << "\nNow enter the node values for the sequence "
83: "on the following line:\n";
85: head = new Node;
86: cin >> head->data;
87: NodePointer current = head;
88: for (int nodeCounter=2; nodeCounter<=numNodes; nodeCounter++)
89: {
90: NodePointer next = new Node;
91: cin >> next->data;
92: current->link = next;
93: current = next;
94: }
95: cin.ignore(80, '\n');
96: current->link = nullptr;
97: cout << "\nAll values have been read in and the linked sequence "
98: "has been constructed.";
99: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
100: }
103: void PrintNodeValues
104: (
105: NodePointer head //inout
106: )
107: {
108: if (head == nullptr)
109: cout << "Current sequence is empty. No values to print.\n";
110: else
111: {
112: cout << "Here are the data values in the current sequence:\n";
113: NodePointer current = head;
114: int nodeCounter = 0;
115: while (current != nullptr)
116: {
117: cout << setw(6) << current->data;
118: nodeCounter++;
119: if (nodeCounter % 10 == 0) cout << endl;
120: current = current->link;
121: }
122: if (nodeCounter % 10 != 0) cout << endl;
123: }
124: }
127: void FindNodeDataValue
128: (
129: NodePointer head, //inout
130: DataType targetValue, //in
131: bool& found, //out
132: NodePointer& targetPointer, //out
133: int& targetPosition //out
134: )
135: {
136: found = false;
137: NodePointer current = head;
138: int nodeCounter = 1;
139: while (!found && current != nullptr)
140: {
141: if (current->data == targetValue)
142: found = true;
143: else
144: {
145: current = current->link;
146: nodeCounter++;
147: }
148: }
149: if (found)
150: {
151: targetPointer = current;
152: targetPosition = nodeCounter;
153: }
154: }
157: void FindDataValueAndPrevious
158: (
159: NodePointer& head, //inout
160: DataType targetValue, //in
161: bool& found, //out
162: NodePointer& targetPointer, //out
163: NodePointer& previousPointer //out
164: )
165: {
166: found = false;
167: NodePointer current = head;
168: NodePointer previous = nullptr;
169: while (!found && current != nullptr)
170: {
171: if (current->data == targetValue)
172: found = true;
173: else
174: {
175: previous = current;
176: current = current->link;
177: }
178: }
179: if (found)
180: {
181: targetPointer = current;
182: previousPointer = previous;
183: }
184: }
187: void FindDataValues
188: (
189: NodePointer head //inout
190: )
191: {
192: if (head == nullptr)
193: {
194: cout << "\nCurrent sequence is empty. No values can be found.";
195: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
196: return;
197: }
198: cout << "Enter the data value to look for, "
199: << "or end-of-file to quit: ";
200: DataType targetValue;
201: cin >> targetValue; cin.ignore(80, '\n');
203: while (cin)
204: {
205: cout << endl;
206: bool found;
207: NodePointer targetPointer;
208: int targetPosition;
209: FindNodeDataValue(head, targetValue, found,
210: targetPointer, targetPosition);
212: cout << targetValue << " was ";
213: if (found)
214: cout << "found in node " << targetPosition << ".";
215: else
216: cout << "not found in the current sequence.";
217: cout << "\nEnter another data value to look for, "
218: << "or end-of-file to quit: ";
219: cin >> targetValue; cin.ignore(80, '\n');
220: }
221: cin.clear();
222: }
225: void InsertAfterNodeWithDataValue
226: (
227: NodePointer& head //inout
228: )
229: {
230: if (head == nullptr)
231: {
232: cout << "\nCurrent sequence is empty. Cannot find a value after "
233: "which to insert.";
234: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
235: return;
236: }
237: cout << "\nEnter data value after which to insert, "
238: << "or end-of-file to quit: ";
239: DataType targetValue;
240: cin >> targetValue; cin.ignore(80, '\n');
241: while (cin)
242: {
243: cout << endl;
244: bool found;
245: NodePointer targetPointer;
246: int targetPosition;
247: FindNodeDataValue(head, targetValue, found,
248: targetPointer, targetPosition);
249: if (found)
250: {
251: NodePointer newNode = new Node;
252: cout << "Enter the data value for the new node: ";
253: cin >> newNode->data; cin.ignore(80, '\n');
254: cout << endl;
255: newNode->link = targetPointer->link;
256: targetPointer->link = newNode;
257: cout << "The value " << newNode->data << " has been "
258: "inserted after the first occurrence of the value "
259: << targetValue << ".";
260: }
261: else
262: cout << "There is no node containing the value "
263: << targetValue << ".\n";
264: cout << "\nEnter another data value after which to insert, "
265: << "or end-of-file to quit: ";
266: cin >> targetValue; cin.ignore(80, '\n');
267: }
268: cin.clear();
269: }
272: void InsertBeforeNodeWithDataValue
273: (
274: NodePointer& head //inout
275: )
276: {
277: if (head == nullptr)
278: {
279: cout << "\nCurrent sequence is empty. Cannot find a value before "
280: "which to insert.";
281: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
282: return;
283: }
284: cout << "\nEnter the data value before which to insert, "
285: << "or end-of-file to quit: ";
286: DataType targetValue;
287: cin >> targetValue; cin.ignore(80, '\n');
289: while (cin)
290: {
291: cout << endl;
292: bool found;
293: NodePointer targetPointer;
294: NodePointer previousPointer;
295: FindDataValueAndPrevious(head, targetValue, found,
296: targetPointer, previousPointer);
297: if (found)
298: {
299: NodePointer newNode = new Node;
300: cout << "Enter the data value for the new node: ";
301: cin >> newNode->data; cin.ignore(80, '\n');
302: cout << endl;
303: newNode->link = targetPointer;
304: if (targetPointer == head)
305: head = newNode;
306: else
307: previousPointer->link = newNode;
308: cout << "The value " << newNode->data << " has been "
309: "inserted before the first occurrence of the value "
310: << targetValue << ".";
311: }
312: else
313: cout << "There is no node containing the value "
314: << targetValue << ".";
315: cout << "\nEnter another data value, before which to insert, "
316: << "or end-of-file to quit: ";
317: cin >> targetValue; cin.ignore(80, '\n');
318: }
319: cin.clear();
320: }
324: void DeleteNodeWithDataValue
325: (
326: NodePointer& head //inout
327: )
328: {
329: if (head == nullptr)
330: {
331: cout << "\nCurrent sequence is empty. No values to delete.";
332: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
333: return;
334: }
335: cout << "\nEnter data value to delete, or "
336: "end-of-file for no deletions: ";
337: DataType targetValue;
338: cin >> targetValue; cin.ignore(80, '\n');
340: while (cin)
341: {
342: cout << endl;
343: bool found;
344: NodePointer targetPointer;
345: NodePointer previousPointer;
346: FindDataValueAndPrevious(head, targetValue, found,
347: targetPointer, previousPointer);
348: if (found)
349: {
350: if (targetPointer == head)
351: head = targetPointer->link;
352: else
353: previousPointer->link = targetPointer->link;
354: delete targetPointer;
355: cout << "The first occurrence of the value " << targetValue
356: << " has been deleted.";
357: }
358: else
359: cout << "There is no node containing the value "
360: << targetValue << ".";
361: cout << "\nEnter another data value to delete, "
362: << "or end-of-file to end deletions: ";
363: cin >> targetValue; cin.ignore(80, '\n');
364: }
365: cin.clear();
366: }
369: void ReverseAllDigits
370: (
371: NodePointer& p //inout
372: )
373: {
374: int n, nr;
375: if (p->data > 9)
376: {
377: n = p->data;
378: nr = 0;
379: while (n != 0)
380: {
381: nr = 10*nr + (n%10);
382: n = n/10;
383: }
384: p->data = nr;
385: }
386: }
389: void ProcessAllNodes
390: (
391: NodePointer& head, //inout
392: void (*Process)(NodePointer& p) //function
393: )
394: {
395: if (head == nullptr)
396: {
397: cout << "\nCurrent sequence is empty. No nodes to process.";
398: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
399: return;
400: }
401: NodePointer current = head;
402: while (current != nullptr)
403: {
404: (*Process)(current);
405: current = current->link;
406: }
407: cout << "\nAll nodes have been processed.";
408: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
409: }