1: // Filename: LNODEFUN.H
2: // Purpose: Header file of definitions and functions to be used
3: // with the demonstration program in LNODEDRV.CPP.
6: #include <iostream>
7: #include <iomanip>
8: using namespace std;
10: typedef int DataType;
11: struct Node
12: {
13: DataType data;
14: Node* link;
15: };
16: typedef Node* NodePointer;
19: /*
20: Part of the documentation of each of the following functions is a
21: list of what functions are called by that function and/or what functions
22: that function calls. Unless otherwise indicated, any function missing this
23: documentation is called only by main and does not call any other functions.
24: */
28: /*
29: The following three functions form the driver "program infrastructure",
30: but have nothing to do with sequences of linked nodes.
31: */
33: void DescribeProgram();
34: // Pre: none
35: // Post: The program description has been displayed.
37: void DisplayMenu();
38: // Pre: none
39: // Post: A menu with 16 options has been displayed.
41: void GetMenuChoice(/* out */ int& menuChoice);
42: // Pre: none
43: // Post: "menuChoice" contains an integer entered by the user
44: // from the keyboard
48: /*
49: The following three functions are "utility" functions that initialize
50: a sequence, test if one is empty, and reclaim the dynamic storage alloted
51: to a sequence when that sequence is no longer needed.
52: */
54: void InitializeSequence(/* inout */ NodePointer& head);
55: // Pre: none
56: // Post: "head" has been set to NULL.
57: // Called by: BuildSequenceFixedSize, BuildSequenceAnySize
59: bool EmptySequence(/* in */ NodePointer head);
60: // Pre: "head" has been initialized.
61: // Post: The function value is true if the sequence is empty,
62: // and false otherwise.
63: // Called by: BuildSequenceFixedSize, BuildSequenceAnySize
65: void ReclaimStorage(/* in */ NodePointer head);
66: // Pre: "head" has been initialized.
67: // Post: All storage (if any) in the node sequence pointed to by
68: // "head" has been returned to the free store.
69: // Called by: BuildSequenceFixedSize, BuildSequenceAnySize
72: /*
73: The next two functions allow you to build a sequence of either
74: fixed or arbitray size.
75: */
77: void BuildSequenceFixedSize(/* inout */ NodePointer& head);
78: // Pre: none
79: // Post: The user has entered the number of nodes to be in a
80: // newly constructed sequence, as well as the values to
81: // be inserted into the sequence, the sequence has been
82: // constructed, and "head" points at the first node.
83: // All storage in any sequence previously pointed to by
84: // "head" has been returned to the free store.
87: void BuildSequenceAnySize(/* inout */ NodePointer& head);
88: // Pre: none
89: // Post: The user has entered the values to be inserted into
90: // a newly constructed sequence (terminating with an
91: // end-of-file), the sequence has been constructed, and
92: // "head" points at the first node. All storage in any
93: // sequence previously pointed to by "head" has been
94: // returned to the free store, and the standard input
95: // stream has been readied for further input.
96: // Calls: InitializeSequence, EmptySequence, ReclainStorage
100: /*
101: This function allows you to display the values in any sequence.
102: */
104: void PrintNodeValues(/* inout */ NodePointer& head);
105: // Pre: "head" has been initialized.
106: // Post: If the sequence is empty, a message to that effect has
107: // been output. Otherwise, all values in the sequence
108: // pointed to by "head" have been displayed, ten to a line,
109: // with each one in a field width of six spaces.
110: // Calls: InitializeSequence, EmptySequence, ReclainStorage
114: /*
115: The following four functions are "utility functions" that are called by
116: other functions to do part of their work.
118: The first two find (respectively) the node containing a data value, and
119: that node plus the previous node. The previous node is needed if we plan
120: to insert before a node or delete a node.
122: The next two find (respectively) the node having a given position, and
123: that node plus the previous node. Once again, the previous node is needed
124: if we plan to insert before a node or delete a node.
125: */
127: void FindNodeDataValue(/* inout */ NodePointer head,
128: /* in */ DataType targetValue,
129: /* out */ bool& found,
130: /* out */ NodePointer& targetPointer,
131: /* out */ int& targetPosition);
132: // Pre: "head" and "targetValue" have been initialized.
133: // Post: If "targetValue" is in the sequence, "found" is true and:
134: // - "targetPointer" points to the first node of the sequence
135: // containing the "targetValue"
136: // - "targetPosition" contains the number of the first node
137: // in the sequence containing the "targetValue"
138: // Otherwise, "found" is false and both "targetPointer" and
139: // "targetPosition" are undefined.
140: // Called by: FindDataValues, InsertAfterNodeWithDataValue
142: void FindDataValueAndPrevious(/* inout */ NodePointer& head,
143: /* in */ DataType targetValue,
144: /* out */ bool& found,
145: /* out */ NodePointer& targetPointer,
146: /* out */ NodePointer& previousPointer);
147: // Pre: "head" and "targetValue" have been initialized.
148: // Post: If "targetValue" is in the sequence, "found" is true and
149: // "targetPointer" points at the first node of the sequence
150: // containing "targetValue", with "previousPointer" pointing
151: // at the previous node, unless "targetPointer" is pointing at
152: // the first node, in which case the value of "previousPointer"
153: // is NULL. Otherwise, "found" is false and the values of both
154: // "targetPointer" and "previousPointer" are undefined.
155: // Called by: InsertBeforeNodeWithDataValue, DeleteNodeWithDataValue
158: void FindNodeK(/* inout */ NodePointer& head,
159: /* in */ int k,
160: /* out */ bool& found,
161: /* out */ NodePointer& targetPointer);
162: // Pre: "head" and "k" have been initialized.
163: // Post: If the sequence contains k or more nodes, "found" is true
164: // and "targetPointer" points to node k. Otherwise, "found"
165: // is false and "targetPointer" is undefined.
166: // Called by: FindPositions, InsertAfterNodeK
168: void FindNodeKAndPrevious(/* inout */ NodePointer& head,
169: /* in */ int k,
170: /* out */ bool& found,
171: /* out */ NodePointer& targetPointer,
172: /* out */ NodePointer& previousPointer);
173: // Pre: "head" and "k" have been initialized.
174: // Post: If the sequence has k or more nodes, "found" is true and
175: // "targetPointer" points at node k of the sequence, with
176: // "previousPointer" pointing at the previous node, unless
177: // node k is the first node, in which case the value of
178: // "previousPointer" is NULL. Otherwise, "found" is false
179: // and the values of both "targetPointer" and "previousPointer"
180: // are undefined.
181: // Called by: InsertBeforeNodeK, DeleteNodeK
185: /*
186: The next two functions find a particular node, either via the data value
187: in it, or the node's position.
188: */
189: void FindDataValues(/* inout */ NodePointer& head);
190: // Pre: "head" has been initialized.
191: // Post: The user has entered zero or more integer values and
192: // in each case a message has been displayed, indicating
193: // either the first position in the sequence where that
194: // value was located or that the value was not found in
195: // in the current sequence.
196: // Calls: FindNodeDataValue
198: void FindPositions(/* inout */ NodePointer& head);
199: // Pre: "head" has been initialized.
200: // Post: The user has entered zero or more integer position
201: // numbers and in each case a message has been displayed,
202: // indicating either the value found in that position or
203: // that position was not found in the current sequence.
204: // Calls: FindNodeK
207: /*
208: The next two functions find a node (via data value or position) and
209: insert a new node after that node.
210: */
211: void InsertAfterNodeWithDataValue(/* inout */ NodePointer& head);
212: // Pre: "head" has been initialized.
213: // Post: The user has entered zero or more data value pairs, and
214: // in each case the second value in the pair has been inserted
215: // into the sequence after the first occurrence of the first
216: // value in the sequence, or a message has been displayed
217: // indicating that the first value of the pair was not found
218: // in the current sequence.
219: // Calls: FindNodeDataValue
221: void InsertAfterNodeK(/* inout */ NodePointer& head);
222: // Pre: "head" has been initialized.
223: // Post: The user has entered zero or more position/value pairs,
224: // and in each case the value in the pair has been inserted
225: // into the sequence after the given position, or a message
226: // has been displayed indicating that the given position was
227: // not found in the current sequence.
228: // Calls: FindNodeK
231: /*
232: The next two functions find a node (via data value or position) and
233: insert a new node before that node.
234: */
235: void InsertBeforeNodeWithDataValue(/* inout */ NodePointer& head);
236: // Pre: "head" has been initialized.
237: // Post: The user has entered zero or more data value pairs, and
238: // in each case the second value in the pair has been inserted
239: // into the sequence before the first occurrence of the first
240: // value in the sequence, or a message has been displayed
241: // indicating that the first value of the pair was not found
242: // in the current sequence.
243: // Calls: FindDataValueAndPrevious
245: void InsertBeforeNodeK(/* inout */ NodePointer& head);
246: // Pre: "head" has been initialized.
247: // Post: The user has entered zero or more position/value pairs,
248: // and in each case the value in the pair has been inserted
249: // into the sequence before the given position, or a message
250: // has been displayed indicating that the given position was
251: // not found in the current sequence.
252: // Calls: FindeNodeKAndPrevious
256: /*
257: The next two functions find a node (via data value or position) and
258: then delete that node.
259: */
260: void DeleteNodeWithDataValue(/* inout */ NodePointer& head);
261: // Pre: "head" has been initialized.
262: // Post: The user has entered zero or more data values and in
263: // each case the first node of the sequence containing
264: // that value has been deleted from the sequence and its
265: // storage has been returned to the free store, or a
266: // message has been displayed indicating that the value
267: // was not found in the current sequence.
268: // Calls: FindDataValueAndPrevious
270: void DeleteNodeK(/* inout */ NodePointer& head);
271: // Pre: "head" has been initialized.
272: // Post: The user has entered zero or more node positions and
273: // in each case the node of the sequence having the given
274: // position has been deleted from the sequence and its
275: // storage has been returned to the free store, or a
276: // message has been displayed indicating that the given
277: // position was not found in the current sequence.
278: // Calls: FindeNodeKAndPrevious
282: /*
283: The next three functions each represent something we might want to do
284: to the integer data in one node. To do that particular thing to the
285: data in all nodes of a sequence we call the last functions and pass the
286: appropriate one of the other three as a "function parameter".
287: */
288: void Double(/* inout */ NodePointer& p);
289: // Pre: "p" has been initialized.
290: // Post: The value in the node pointed to by "p" has been doubled.
292: void Square(/* inout */ NodePointer& p);
293: // Pre: "p" has been initialized.
294: // Post: The value in the node pointed to by "p" has been squared.
296: void ReverseAllDigits(/* inout */ NodePointer& p);
297: // Pre: "p" has been initialized.
298: // Post: The value in the node pointed to by "p" has had its
299: // digits reversed.
301: void ProcessAllNodes(/* inout */ NodePointer& head,
302: /* function */ void (*Process)(NodePointer& p));
303: // Pre: "head" and "Process" have been initialized.
304: // Post: The value in each node in the sequence pointed to by "head"
305: // has been "processed" by the function pointed to by "Process".