1: //linked_node_recursion.cpp
2: //Illustrates recursion applied to a sequence of linked nodes
4: #include <iostream>
5: #include <iomanip>
6: using namespace std;
8: typedef int DataType;
9: struct Node
10: {
11: DataType data;
12: Node* link;
13: };
14: typedef Node* NodePointer;
17: void BuildNodeSequence
18: (
19: NodePointer& head //inout
20: );
22: void DisplaySequenceValues
23: (
24: NodePointer head //in
25: );
27: void DisplaySequenceValuesInReverse
28: (
29: NodePointer head //in
30: );
32: void ReverseNodeOrderRecursively
33: (
34: NodePointer& head //inout
35: );
37: //For the sake of comparison, you can also reverse the list iteratively
38: void ReverseNodeOrderIteratively
39: (
40: NodePointer& old_list //inout
41: );
44: int main()
45: {
46: cout << "\nThis program illustrates recursion in the context of "
47: "a sequence of linked\nnodes. It uses four recursive functions "
48: "to perform the following actions.";
49: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
50: cout << "\nThe program reads in a line of integers, and places "
51: "them into a sequence of \nlinked nodes. Next it displays the "
52: "contents of that sequence of linked nodes,\nfirst in their "
53: "input order, and then in the reverse of that order. Then it"
54: "\nreverses the contents of the nodes, and repeats the above "
55: "two displays.";
56: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
58: NodePointer head;
60: cout << "\nBegin by entering data values for the nodes on the "
61: "following line: \n";
62: BuildNodeSequence(head);
64: cout << "\nHere, from the linked nodes, are the values read in:\n";
65: DisplaySequenceValues(head);
66: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
68: cout << "\nHere, again from the linked nodes, are the values in "
69: "reverse order:\n";
70: DisplaySequenceValuesInReverse(head);
71: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
73: cout << "\nNext we reverse the order of the nodes themselves.";
74: ReverseNodeOrderRecursively(head);
75: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
77: cout << "\nThen we first display them in their new (reversed) order. "
78: "Here they are:\n";
79: DisplaySequenceValues(head);
80: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
82: cout << "\nFinally, we display the revised sequence in reverse order,\n"
83: "which will be the original order of the values. Here they are:\n";
84: DisplaySequenceValuesInReverse(head);
85: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
86: }
89: //Build sequence of linked nodes with values read from keyboard
90: void BuildNodeSequence
91: (
92: NodePointer& head //out
93: )
94: {
95: int value;
96: if (cin.peek() == '\n')
97: {
98: cin.ignore(80, '\n');
99: head = nullptr;
100: }
101: else
102: {
103: cin >> value;
104: BuildNodeSequence(head);
105: NodePointer next = new Node;
106: next->data = value;
107: next->link = head;
108: head = next;
109: }
110: }
113: void DisplaySequenceValues
114: (
115: NodePointer head //in
116: )
117: {
118: if (head != nullptr)
119: {
120: cout << head->data << " ";
121: DisplaySequenceValues(head->link);
122: }
123: }
126: void DisplaySequenceValuesInReverse
127: (
128: NodePointer head //in
129: )
130: {
131: if (head != nullptr)
132: {
133: DisplaySequenceValuesInReverse(head->link);
134: cout << head->data << " ";
135: }
136: }
139: void ReverseNodeOrderRecursively
140: (
141: NodePointer& head //inout
142: )
143: {
144: NodePointer current = head;
145: if (current == nullptr) return; //since the sequence is empty
147: NodePointer rest = current->link;
148: if (rest == nullptr) return; //since the sequence has only one Node
150: //Reverse the order of all nodes but the first
151: ReverseNodeOrderRecursively(rest);
153: //Make the former first Node the last Node
154: current->link->link = current;
155: current->link=nullptr;
157: //Point the original head at the reversed list
158: head = rest;
159: }
161: void ReverseNodeOrderIteratively
162: (
163: NodePointer& head //inout
164: )
165: {
166: NodePointer reversedList = nullptr;
168: while (head != nullptr)
169: {
170: //Remove Node from incoming list
171: NodePointer current = head;
172: head = head->link;
174: //Insert Node into reversed list
175: current->link = reversedList;
176: reversedList = current;
177: }
178: head = reversedList;
179: }