Let xHead, yHead and zHead be the head pointers of 3 linked lists of integers (called X-list, Y-list and Z-list, respectively, from here). X-list and Y-list are each sorted (in non-decreasing order) in itself and each may be empty. Z-list is initially empty (i.e., zHead initially contains the null pointer). Develop and test a recursive C++ function called Merge2AscListsRecur that combines the nodes in X-list and Y-list into Z-list such that, after calling the function, Z-list is a sorted list (in non-decreasing order) containing all the nodes initially contained in X-list and Y-list – X-list and Y-list should both be empty after the call. Other specifications/requirements: ● Each node of the list has the following structure: struct Node { int data; Node *link; }; ● The function should: ► Have only three parameters (each a pointer-to-Node) and no return value (be a void function). ► Not use any global variables or static local variables. ► Not use any looping constructs (for, while, do-while, ...). ► Be directly (not indirectly) recursive. ► Not create any new nodes, destroy any existing nodes or copy/replace the data item of any node. ► Not make temporary copies of the data involved using any other storage structures (arrays, stacks, queues, etc.). ► Use (if ever needed) no more than a small number of pointers to hold certain link addresses. ○ Not make temporary copies of the entire list's link addresses wholesale. ● Z-list should be sorted at all times as it "grows" from an empty list to one that contains all the nodes originally contained in X-list and Y-list. ► What this means is that you should not, for instance, attempt to first append all the nodes in X-list to Z-list, then append all the nodes in Y-list to Z-list, and finally use a sorting algorithm of some kind to sort the nodes in Z-list.

Let xHead, yHead and zHead be the head pointers of 3 linked lists of integers (called X-list, Y-list and Z-list, respectively, from here). X-list and Y-list are each sorted (in non-decreasing order) in itself and each may be empty. Z-list is initially empty (i.e., zHead initially contains the null pointer). Develop and test a recursive C++ function called Merge2AscListsRecur that combines the nodes in X-list and Y-list into Z-list such that, after calling the function, Z-list is a sorted list (in non-decreasing order) containing all the nodes initially contained in X-list and Y-list – X-list and Y-list should both be empty after the call. Other specifications/requirements: ● Each node of the list has the following structure: struct Node { int data; Node *link; }; ● The function should: ► Have only three parameters (each a pointer-to-Node) and no return value (be a void function). ► Not use any global variables or static local variables. ► Not use any looping constructs (for, while, do-while, ...). ► Be directly (not indirectly) recursive. ► Not create any new nodes, destroy any existing nodes or copy/replace the data item of any node. ► Not make temporary copies of the data involved using any other storage structures (arrays, stacks, queues, etc.). ► Use (if ever needed) no more than a small number of pointers to hold certain link addresses. ○ Not make temporary copies of the entire list's link addresses wholesale. ● Z-list should be sorted at all times as it "grows" from an empty list to one that contains all the nodes originally contained in X-list and Y-list. ► What this means is that you should not, for instance, attempt to first append all the nodes in X-list to Z-list, then append all the nodes in Y-list to Z-list, and finally use a sorting algorithm of some kind to sort the nodes in Z-list.

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

Let xHead, yHead and zHead be the head pointers of 3 linked lists of integers (called X-list, Y-list and Z-list, respectively, from here). X-list and Y-list are each sorted (in non-decreasing order) in itself and each may be empty. Z-list is initially empty (i.e., zHead initially contains the null pointer). Develop and test a recursive C++ function called Merge2AscListsRecur that combines the nodes in X-list and Y-list into Z-list such that, after calling the function, Z-list is a sorted list (in non-decreasing order) containing all the nodes initially contained in X-list and Y-list – X-list and Y-list should both be empty after the call.

Other specifications/requirements:

●

Each node of the list has the following structure:

struct Node
{
int data;
Node *link;
};

●

The function should:

►

Have only three parameters (each a pointer-to-Node) and no return value (be a void function).

►

Not use any global variables or static local variables.

►

Not use any looping constructs (for, while, do-while, ...).

►

Be directly (not indirectly) recursive.

►

Not create any new nodes, destroy any existing nodes or copy/replace the data item of any node.

►

Not make temporary copies of the data involved using any other storage structures (arrays, stacks, queues, etc.).

►

Use (if ever needed) no more than a small number of pointers to hold certain link addresses.

○

Not make temporary copies of the entire list's link addresses wholesale.

●

Z-list should be sorted at all times as it "grows" from an empty list to one that contains all the nodes originally contained in X-list and Y-list.

►

What this means is that you should not, for instance, attempt to first append all the nodes in X-list to Z-list, then append all the nodes in Y-list to Z-list, and finally use a sorting algorithm of some kind to sort the nodes in Z-list.

#ifndef LLCP_INT_H
#define LLCP_INT_H

#include <iostream>

struct Node
{
int data;
Node *link;
};

int FindListLength(Node* headPtr);
bool IsSortedUp(Node* headPtr);
void InsertAsHead(Node*& headPtr, int value);
void InsertAsTail(Node*& headPtr, int value);
void InsertSortedUp(Node*& headPtr, int value);
bool DelFirstTargetNode(Node*& headPtr, int target);
bool DelNodeBefore1stMatch(Node*& headPtr, int target);
void ShowAll(std::ostream& outs, Node* headPtr);
void FindMinMax(Node* headPtr, int& minValue, int& maxValue);
double FindAverage(Node* headPtr);
void ListClear(Node*& headPtr, int noMsg = 0);

// prototype of Merge2AscListsRecur

#endif

HAMAROCH========
1
2
3
4
5
6
7
// definition of Merge2AsclistsRecur
8 // (put here to facilitate grading)
9
10
12
11 int FindList Length (Node* headptr)
int length = 0;
{
while (headPtr != 0)
13
14
15
16
17
18
19
20
92122232425 26 27 2829381323435367839481 2 3 4 45 6 7 84958515284556驭85960
30
40
42
44
46
#include <iostream>
#include <cstdlib>
#include "11cpInt.h"
using namespace std;
47
53
43 }
57
{
bool Is SortedUp (Node* headptr)
{
++length;
headPtr = headPtr->link;
return length;
{
if (headPtr == 0 || headPtr->link == 0) // empty or 1-node
return true;
while (headPtr->link != 0) // not at Last node
}
void InsertAsHead (Node* & headPtr, int value)
if (headPtr->link->data < headPtr->data)
return false;
headPtr = headPtr->link;
return true;
Node *newNodePtr = new Node;
newNodePtr->data = value;
newNodePtr->link = headPtr;
headPtr = newNodePtr;
void InsertAsTail (Node* & headPtr, int value)
Node *newNodePtr = new Node;
= value;
= 0;
newNodePtr->data
newNodePtr->link
if (headPtr == 0)
headPtr = newNodePtr;
else
{
Node *cursor= headPtr;
while (cursor->link != 0) // not at last node
cursor = cursor->link;
cursor->link = newNodePtr;

132 bool DelFirstTargetNode (Node*& headPtr, int target)
133 {
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
184
185
Node *precursor = 0,
186
187
199
*cursor= headPtr;
while (cursor != 0 && cursor->data != target)
precursor = cursor;
cursor = cursor->link;
if (cursor ==
cout << target << " not found." << endl;
return false;
if (cursor == headPtr) //OR precursor == 0
headPtr = headPtr->link;
else
precursor->link = cursor->link;
delete cursor;
return true;
}
bool DelNodeBefore1stMatch (Node* & headPtr, int target)
{
if (headPtr == 0 || headPtr->link == 0 || headPtr->data == target) return false;
Node *cur = headPtr->link, *pre = headPtr, *prepre = 0;
while (cur != 0 && cur->data != target)
prepre=pre;
pre = cur;
cur = cur->link;
}
if (cur == 0) return false;
if (cur == headPtr->link)
headPtr = cur;
delete pre;
}
else
175
176
177 }
178
179 void ShowAll (ostream& outs, Node* headptr)
180 {
181
182
183
prepre->link = cur;
delete pre;
return true;
while (headPtr != 0)
outs <<headPtr->data << "
headPtr = headPtr->link;
}
outs << endl;

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 3 images

SEE SOLUTION Check out a sample Q&A here