/* output BEFORE function call - a is 10 20 30 40 50 60 70 80 90 node with 20 le
ID: 3770747 • Letter: #
Question
/*
output
BEFORE function call - a is 10 20 30 40 50 60 70 80 90
node with 20 leaving
node with 30 leaving
node with 40 leaving
node with 50 leaving
node with 60 leaving
node with 70 leaving
node with 80 leaving
AFTER function call - a is 10 90
node with 10 leaving
node with 90 leaving
Press any key to continue
*/
#include
using std::cout;
using std::cin;
using std::endl;
using std::ostream;
struct node1 {
int data;
node1 * p;
~node1() { cout << "node with " << data << " leaving ";}
};
bool deleteBetween(node1 * &, int low, int high);
// YOU CAN MAKE THE FOLLOWING ASSUMPTIONS
// 1. - the list is not empty
// 2. - the list is sorted
// 3. - the first node in the list is smaller than low
// 4. - the last node in the list is larger than high
// 5. - the parameter low is smaller than the parameter high
// NOTE: YOUR FUNCTION SHOULD RETURN ALL DELETED MEMORY TO THE HEAP
// REQUIREMENTS:
// 1. - NO MORE THAN 3 LOOPS
// 2. - NO NESTED LOOPS
void addFront1( node1 * & start, int);
void cleanUp1( node1 *);
ostream & operator<<( ostream &, const node1 *);
void build1( node1 * & );
void q1()
{
cout << " QUESTION 1 STARTING **********" << endl;
node1 * a = NULL;
build1(a);
cout << "BEFORE function call - a is " << a << endl;
deleteBetween(a,15,85);
cout << "AFTER function call - a is " << a << endl;
cleanUp1(a);
}
void addFront( node1 * & start, int x)
{
node1 * t = new node1;
t->data = x;
if( start != NULL ) // NOT NECESSARY
t->p = start;
else
t->p = NULL;
start = t;
}
void cleanUp1( node1 * s)
{
node1 * walker, * prev;
walker = s;
while ( walker != NULL )
{
prev = walker;
walker = walker->p;
delete prev;
}
}
ostream & operator<<(ostream & w, const node1 * s)
{
if ( s==NULL)
{
w << "EMPTY LIST ";
return w;
}
const node1 * walker = s;
while ( walker != NULL )
{
w << walker->data << ' ';
walker = walker->p;
}
return w;
}
void build1(node1 * & a)
{
addFront(a,90);
addFront(a,80);
addFront(a,70);
addFront(a,60);
addFront(a,50);
addFront(a,40);
addFront(a,30);
addFront(a,20);
addFront(a,10);
}
bool deleteBetween(node1 * & s, int low, int high) // STUDENT WRITTEN
{
// YOU CAN MAKE THE FOLLOWING ASSUMPTIONS
// 1. - the list is not empty
// 2. - the list is sorted
// 3. - the first node in the list is smaller than low
// 4. - the last node in the list is larger than high
// 5. - the parameter low is smaller than the parameter high
// NOTE: YOUR FUNCTION SHOULD RETURN ALL DELETED MEMORY TO THE HEAP
// REQUIREMENTS:
// 1. - NO MORE THAN 3 LOOPS
// 2. - NO NESTED LOOPS
Explanation / Answer
#include<iostream>
using std::cout;
using std::cin;
using std::endl;
using std::ostream;
struct node1 {
int data;
node1 * p;
~node1() {
cout << "node with " << data << " leaving ";
}
};
bool deleteBetween(node1 * &, int low, int high);
// YOU CAN MAKE THE FOLLOWING ASSUMPTIONS
// 1. - the list is not empty
// 2. - the list is sorted
// 3. - the first node in the list is smaller than low
// 4. - the last node in the list is larger than high
// 5. - the parameter low is smaller than the parameter high
// NOTE: YOUR FUNCTION SHOULD RETURN ALL DELETED MEMORY TO THE HEAP
// REQUIREMENTS:
// 1. - NO MORE THAN 3 LOOPS
// 2. - NO NESTED LOOPS
void addFront1(node1 * & start, int);
void cleanUp1(node1 *);
ostream & operator<<(ostream &, const node1 *);
void build1(node1 * &);
void q1() {
cout << " QUESTION 1 STARTING **********" << endl;
node1 * a = NULL;
build1(a);
cout << "BEFORE function call - a is " << a << endl;
deleteBetween(a, 15, 85);
cout << "AFTER function call - a is " << a << endl;
cleanUp1(a);
}
void addFront(node1 * & start, int x) {
node1 * t = new node1;
t->data = x;
if (start != NULL) // NOT NECESSARY
t->p = start;
else
t->p = NULL;
start = t;
}
void cleanUp1(node1 * s) {
node1 * walker, *prev;
walker = s;
while (walker != NULL) {
prev = walker;
walker = walker->p;
delete prev;
}
}
ostream & operator<<(ostream & w, const node1 * s) {
if (s == NULL) {
w << "EMPTY LIST ";
return w;
}
const node1 * walker = s;
while (walker != NULL) {
w << walker->data << ' ';
walker = walker->p;
}
return w;
}
void build1(node1 * & a) {
addFront(a, 90);
addFront(a, 80);
addFront(a, 70);
addFront(a, 60);
addFront(a, 50);
addFront(a, 40);
addFront(a, 30);
addFront(a, 20);
addFront(a, 10);
}
// YOU CAN MAKE THE FOLLOWING ASSUMPTIONS
// 1. - the list is not empty
// 2. - the list is sorted
// 3. - the first node in the list is smaller than low
// 4. - the last node in the list is larger than high
// 5. - the parameter low is smaller than the parameter high
// NOTE: YOUR FUNCTION SHOULD RETURN ALL DELETED MEMORY TO THE HEAP
// REQUIREMENTS:
// 1. - NO MORE THAN 3 LOOPS
// 2. - NO NESTED LOOPS
bool deleteBetween(node1 * & s, int low, int high) // STUDENT WRITTEN
{
node1 * walker = s;
node1 *prev = NULL, *curNode = NULL;
bool discard = false;
while (walker != NULL) {
discard = false;
if(walker->data >= low && walker->data <= high) {
//cout << " Node : " << walker->data << endl;
curNode = walker;
if(prev == NULL)
walker = walker->p;
else {
prev->p = walker->p;
walker = walker->p;
}
discard = true;
} else {
prev = walker;
walker = walker->p;
}
if(discard == true)
delete curNode;
}
return false;
}
int main() {
q1();
return 0;
}
-------output------------
QUESTION 1 STARTING **********
BEFORE function call - a is 10 20 30 40 50 60 70 80 90
node with 20 leaving
node with 30 leaving
node with 40 leaving
node with 50 leaving
node with 60 leaving
node with 70 leaving
node with 80 leaving
AFTER function call - a is 10 90
node with 10 leaving
node with 90 leaving
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.