/ Write a function to reverse the first two elements in a // double linked list
ID: 675026 • Letter: #
Question
/ Write a function to reverse the first two elements in a
// double linked list
// The function should change pointers
//NO changing the data, i.e. the int data field inside the node
// You MUST match the output given below
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::ostream;
struct node {
int data;
node * p; // FORWARD LINK
node * rp; // REVERSE LINK
};
ostream & operator<<( ostream &, const node *); // Written
void addFront( node * & start, int); // Written
void cleanUp( node *); // Written
void reverse(node * &); //
void main()
{
node * a = NULL;
cout << "EMPTY LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,10);
cout << " ONE ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,30);
addFront(a,20);
cout << " TWO ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,60);
addFront(a,50);
addFront(a,40);
cout << " THREE ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,400);
addFront(a,300);
addFront(a,200);
addFront(a,100);
cout << " FOUR ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
}
void reverse(node * & s) // Student Writes this Function
{
}
void addFront( node * & start, int x)
{
node * t = new node;
t->data = x;
if( start != NULL )
{
t->p = start;
t->rp = NULL;
start->rp = t;
}
else
{
t->p = NULL;
t->rp = NULL;
}
start = t;
}
void cleanUp( node * s)
{
node * walker, * prev;
walker = s;
while ( walker != NULL )
{
prev = walker;
walker = walker->p;
delete prev;
}
}
ostream & operator<<(ostream & w, const node * s)
{
const node * walker = s;
const node * trailer = walker;
w << "Forward Print " << endl;
if ( s==NULL)
{
w << "EMPTY LIST";
}
else
{
while ( walker != NULL )
{
w << walker->data << ' ';
trailer = walker;
walker = walker->p;
}
}
w << endl << "Reverse Print " << endl;
if ( trailer == NULL )
{
w << "EMPTY LIST";
return w;
}
while ( trailer != NULL)
{
w << trailer->data << ' ';
trailer = trailer->rp;
}
return w;
}
/*
EMPTY LIST CASE:
BEFORE a is
Forward Print
EMPTY LIST
Reverse Print
EMPTY LIST
AFTER a is
Forward Print
EMPTY LIST
Reverse Print
EMPTY LIST
ONE ELEMENT LIST CASE:
BEFORE a is
Forward Print
10
Reverse Print
10
AFTER a is
Forward Print
10
Reverse Print
10
TWO ELEMENT LIST CASE:
BEFORE a is
Forward Print
20 30
Reverse Print
30 20
AFTER a is
Forward Print
30 20
Reverse Print
20 30
THREE ELEMENT LIST CASE:
BEFORE a is
Forward Print
40 50 60
Reverse Print
60 50 40
AFTER a is
Forward Print
50 40 60
Reverse Print
60 40 50
FOUR ELEMENT LIST CASE:
BEFORE a is
Forward Print
100 200 300 400
Reverse Print
400 300 200 100
AFTER a is
Forward Print
200 100 300 400
Reverse Print
400 300 100 200
*/
Explanation / Answer
#include "stdafx.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::ostream;
struct node
{
int data;
node * p; // FORWARD LINK
node * rp; // REVERSE LINK
};
ostream & operator<<( ostream &, const node *); // Written
void addFront( node * & start, int); // Written
void cleanUp( node *); // Written
void reverse(node *); //
int main()
{
node * a = NULL;
cout << "EMPTY LIST CASE: ";
cout << "BEFORE a is " << a << endl;
//reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,10);
cout << " ONE ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,30);
addFront(a,20);
cout << " TWO ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,60);
addFront(a,50);
addFront(a,40);
cout << " THREE ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
//reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
a = NULL;
addFront(a,400);
addFront(a,300);
addFront(a,200);
addFront(a,100);
cout << " FOUR ELEMENT LIST CASE: ";
cout << "BEFORE a is " << a << endl;
reverse(a);
cout << "AFTER a is " << a << endl;
cleanUp(a);
return 0;
system("pause");
}
void reverse(node *s) // Student Writes this Function
{
node *temp, *newtemp;
temp =s;
if(temp == NULL)
s = temp;
else
{
newtemp = temp->p;
temp->p=s->rp;
s->rp=newtemp;
}
}
void addFront( node * & start, int x)
{
node * t = new node;
t->data = x;
if( start != NULL )
{
t->p = start;
t->rp = NULL;
start->rp = t;
}
else
{
t->p = NULL;
t->rp = NULL;
}
start = t;
}
void cleanUp( node * s)
{
node * walker, * prev;
walker = s;
while ( walker != NULL )
{
prev = walker;
walker = walker->p;
delete prev;
}
}
ostream & operator<<(ostream & w, const node * s)
{
const node * walker = s;
const node * trailer = walker;
w << "Forward Print " << endl;
if ( s==NULL)
{
w << "EMPTY LIST";
}
else
{
while ( walker != NULL )
{
w << walker->data << ' ';
trailer = walker;
walker = walker->p;
}
}
w << endl << "Reverse Print " << endl;
if ( trailer == NULL )
{
w << "EMPTY LIST";
return w;
}
while ( trailer != NULL)
{
w << trailer->data << ' ';
trailer = trailer->rp;
}
return w;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.