// Write a function that will delete the all nodes in a sorted linked list // th
ID: 3770641 • Letter: #
Question
// Write a function that will delete the all nodes in a sorted linked list // that fall between two given values. // // /* 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 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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.