/* BEFORE function call - a is 10 20 30 40 50 60 70 80 90 node with 20 leaving n

Question

/*
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 <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);
}

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
   if (s == nullptr)
       return true;
   else if ()

   return false; // ONLY HERE TO GET THE PROGRAM TO COMPILE
}

Explanation / Answer

bool deleteBetween(node1 * & s, int low, int high) //   
{
   node1 *walker,*prev,*temp,*low_prev,*low_ptr,*high_ptr;
   walker = s;
   while(walker->p->data!=low) // find low position
       walker = walker->p;
   low_prev = walker;
   low_ptr = walker->p;
   while(walker->data!=high) // find high position
       walker = walker->p;
   high_ptr = walker;
   low_prev->p = high_ptr->p; // pointing prev of low to next of high
   walker=low;
   while(walker->data!=high){ // deleting low to high
       temp=walker;
       walker=walker->p;
       delete temp;
   }
   delete walker;
return false; // ONLY HERE TO GET THE PROGRAM TO COMPILE
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.