1: /** @file linked_node_functions.h
2: Specification file corresponding to the implementation file
3: linked_node_functions.cpp. 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: /**
12: The kind of data in each node.
13: */
14: typedef int DataType;
16: /**
17: The structure of a node in a sequence of linked nodes.
18: */
19: struct Node
20: {
21: DataType data;
22: Node* link;
23: };
25: /**
26: An alias for a pointer to a node.
27: */
28: typedef Node* NodePointer;
31: /*
32: Part of the documentation of each of the following functions is a list
33: of what functions are called by that function and/or what functions that
34: function calls. Unless otherwise indicated, any function missing this
35: documentation is called only by main and does not call any other functions.
36: */
39: void DescribeProgram();
40: /**<
41: Display a brief description of the program.
42: @pre None.
43: @post The program description has been displayed, and the output has
44: paused for the user to press Enter to continue.
45: */
48: void InitializeSequence
49: (
50: NodePointer& head //inout
51: );
52: /**<
53: A utility function for initializing (or re-initializing) a sequence.
54: Called by: BuildSequenceFixedSize and BuildSequenceAnySize
55: @pre None.
56: @post head has been set to 0.
57: @param head A pointer to the first node of a sequence of linked nodes
58: (after the function call).
59: */
62: void ReclaimStorage
63: (
64: NodePointer& head //in
65: );
66: /**<
67: A utility helper function for reclaiming the storage used by a sequence
68: for the free store, once that sequence is no longer needed.
69: Called by: BuildSequenceFixedSize and BuildSequenceAnySize
70: @pre head has been initialized.
71: @post All storage (if any) in the node sequence pointed to by head has
72: been returned to the free store and head itself has the value 0.
73: @param head A pointer to the first node of a sequence of linked nodes
74: (and to 0 after the function call).
75: */
78: void BuildSequenceFixedSize
79: (
80: NodePointer& head //inout
81: );
82: /**<
83: Build a sequence of fixed size.
84: @pre None.
85: @post The user has entered the number of nodes to be in a newly
86: constructed sequence, as well as the values to be inserted into
87: that sequence, the sequence has been constructed, and head points
88: at the first node. All storage in any sequence previously pointed to
89: by head has been returned to the free store.
90: @param head A pointer to the first node of a sequence of linked nodes.
91: */
94: void PrintNodeValues
95: (
96: NodePointer head //inout
97: );
98: /**<
99: Display the values in any sequence.
100: Calls: InitializeSequence and ReclainStorage
101: @pre head has been initialized.
102: @post If the sequence is empty, a message to that effect has been output.
103: Otherwise, all values in the sequence pointed to by head have been
104: displayed, ten to a line, with each one in a field width of six spaces.
105: @param head A pointer to the first node of a sequence of linked nodes.
106: */
109: void FindNodeDataValue
110: (
111: NodePointer head, //inout
112: DataType targetValue, //in
113: bool& found, //out
114: NodePointer& targetPointer, //out
115: int& targetPosition //out
116: );
117: /**<
118: A utility function called as a helper function by any function that needs
119: to find a node containing a given value.
120: Called by: FindDataValues and InsertAfterNodeWithDataValue
121: @pre head and targetValue have been initialized.
122: @post If targetValue is in the sequence, found is true and:
123: - targetPointer points to first node of sequence containing targetValue
124: - targetPosition contains number of the first node in the sequence that
125: contains targetValue
126: Otherwise, found is false and both targetPointer and targetPosition
127: are undefined.
128: @param head A pointer to the first node of a sequence of linked nodes.
129: @param targetValue The value being sought.
130: @param found A boolean indicating whether targetValue has been found.
131: @param targetPointer A pointer to the first instance of targetValue.
132: @param targetPosition The number of the position of targetValue.
133: */
136: void FindDataValueAndPrevious
137: (
138: NodePointer& head, //inout
139: DataType targetValue, //in
140: bool& found, //out
141: NodePointer& targetPointer, //out
142: NodePointer& previousPointer //out
143: );
144: /**<
145: A utility function called as a helper function by any function that needs
146: to find a node containing a given value and the preceding node.
147: Called by: InsertBeforeNodeWithDataValue and DeleteNodeWithDataValue
148: @pre head and targetValue have been initialized.
149: @post If targetValue is in the sequence, found is true and targetPointer
150: points at the first node of the sequence containing targetValue, with
151: previousPointer pointing at the previous node, unless targetPointer is
152: pointing at the first node, in which case the value of previousPointer
153: is 0. Otherwise, found is false and the values of both targetPointer
154: and previousPointer are undefined.
155: @param head A pointer to the first node of a sequence of linked nodes.
156: @param targetValue The value being sought.
157: @param found A boolean indicating whether targetValue has been found.
158: @param targetPointer A pointer to the first instance of targetValue.
159: @param previousPointer A pointer to the node before the first one
160: containing targetValue.
161: */
164: void FindDataValues
165: (
166: NodePointer head //inout
167: );
168: /**<
169: Finds a particular node via the data value in it.
170: Calls: FindNodeDataValue
171: @pre head has been initialized.
172: @post The user has entered zero or more integer values and in each case
173: a message has been displayed, indicating either the first position in
174: the sequence where that value was located, or that the value was not
175: found in the current sequence.
176: @param head A pointer to the first node of a sequence of linked nodes.
177: */
180: void InsertAfterNodeWithDataValue
181: (
182: NodePointer& head //inout
183: );
184: /**<
185: Finds a node (via the data value in it) and inserts a new node after
186: that node.
187: Calls: FindNodeDataValue
188: @pre head has been initialized.
189: @post The user has entered zero or more data value pairs, and in each
190: case the second value in the pair has been inserted into the sequence
191: after the first occurrence of the first value in the sequence, or a
192: message has been displayed, indicating that the first value of the pair
193: was not found in the current sequence.
194: @param head A pointer to the first node of a sequence of linked nodes.
195: */
198: void InsertBeforeNodeWithDataValue
199: (
200: NodePointer& head //inout
201: );
202: /**<
203: Finds a node (via the data value in it) and inserts a new node before
204: that node.
205: Calls: FindDataValueAndPrevious
206: @pre head has been initialized.
207: @post The user has entered zero or more data value pairs, and in each
208: case the second value in the pair has been inserted into the sequence
209: before the first occurrence of the first value in the sequence, or a
210: message has been displayed, indicating that the first value of the pair
211: was not found in the current sequence.
212: @param head A pointer to the first node of a sequence of linked nodes.
213: */
216: void DeleteNodeWithDataValue
217: (
218: NodePointer& head //inout
219: );
220: /**<
221: Finds a node (via the data value in it) and then deletes that node.
222: Calls: FindDataValueAndPrevious
223: @pre head has been initialized.
224: @post The user has entered zero or more data values and in each case
225: the first node of the sequence containing that value has been deleted
226: from the sequence and its storage has been returned to the free store,
227: or a message has been displayed indicating that the value was not found
228: in the current sequence.
229: @param head A pointer to the first node of a sequence of linked nodes.
230: */
233: void ReverseAllDigits
234: (
235: NodePointer& p //inout
236: );
237: /**<
238: Reverse all digits in a data value.
239: @pre p has been initialized.
240: @post The value in the node pointed to by p has had its digits reversed.
241: @param p A pointer to a node.
242: */
245: void ProcessAllNodes
246: (
247: NodePointer& head, //inout
248: void (*Process)(NodePointer& p) //function
249: );
250: /**<
251: Processes all nodes by applying to the data in each node the function
252: which it takes in as an input function parameter.
253: @pre head and Process have been initialized.
254: @post The value in each node in the sequence pointed to by head
255: has been processed by the function pointed to by Process.
256: @param head A pointer to the first node of a sequence of linked nodes.
257: @param Process A function to be applied to the data in a node.
258: */