The files List.h, List.cpp, and lab07.cpp have been provided with this assignmen

Question

The files List.h, List.cpp, and lab07.cpp have been provided
with this assignment. You will only modify one file, List.cpp. Look
for the comments marking where you'll be adding your code.

Please look at the methods declared in List.h.
Do not add any other methods to this file.

Modify the method insert( ) in the file List.cpp to create a new node
with the incoming string s and then insert that node in the list object.
The list should be maintained in ascending alphabetical order at all times.
List.cpp is the only file that you should change.

Use lab07.cpp, List.cpp, and List.h to test your solution.

The main program in lab07.cpp reads a series of strings until it encounters
the string "xxx" (without quotes).
The string "xxx" is not added to the list, but it is a sentinel
value that indicates that the user does not wish to add more strings to the list.

The strings need to be added to the linked list in alphabetical order.
The main program displays the list after the method insert( ) adds a
new node to the list.

For example, the input could be:

bbb
ccc
aaa
xxx <-- this indicates that no more strings are to be added

At this point the program stops adding nodes to the list, and
displays the full list:

aaa
bbb
ccc

The main program has a second loop that reads strings that the user wishes
to remove from the list. The program displays the list after the method
remove( ) removes first the node matching the incoming string.
Once again, the string "xxx" (without quotes) terminates the loop.

For example, the input could be:

yyy
aab
bbb
ccc
aaa
xxx <-- this indicates that no more strings are to be removed

If the string does not appear in the list, as in the case of the string
"yyy" in the above example, nothing should happen. That is, the list
should not change and the program should not crash.

When the program reads string "bbb", the node containing "bbb" should be
removed from the list and the node should be deleted.
Again, "xxx" indicates the end of the input.

Important: make sure you deallocate any node you remove from the list.
Otherwise you have a memory leak!

This assignment is due on the BlackBoard one week after it is assigned

Submit only the file List.cpp named as yourFAUIDhere_funcs.cpp.

No late assignments.

Please
- use braces around any block
- use blocks as we did in our class examples
- indent your code as we have used indentations in our examples
- comment your code; do not over comment your code

Penalties:
o -2 for each missing block

o -2 for each missing indentation

o -2 for nodes not being deallocate after they are removed from
the list

o no credit if your cpp file does not compile or does not run

o no credit if your cpp file does not insert the nodes in the list
in alphabetical order

HERE List CPP FILE TO MODIFY

#include "List.h"

// methods for Node

// constructor: init. a Node
Node::Node( const string &s, Node * const n, Node * const p )
{
word = s; // init. word with a copy of s
next = n; // next points to next node n
prev = p; // prev points to previous node p

if( n ) // is there a next node?
{
n->prev = this;
}

if( p ) // is there a previous node?
{
p->next = this;
}
}

// return a const ref to word
const string &Node::get_word( ) const
{
return word;
}

// return a pointer to next node
Node *Node::get_next( ) const
{
return next;
}

// return a pointer to previous node
Node *Node::get_prev( ) const
{
return prev;
}

// set and return a pointer to next node
Node *Node::set_next( Node *n )
{
next = n;
return next;
}

// set and return a pointer to previous node
Node *Node::set_prev( Node *p )
{
prev = p;
return prev;
}

// methods for List

List::List( ) // constructor: init. head and tail
{
cout << "List::List( ) ";

head = tail = 0;
}

List::~List( ) // destructor: deallocate the list
{
cout << "List::~List( ) ";

for( Node *p = head; p; )
{
Node *tmp = p; // remember current pointer
p = p->get_next( ); // advance p to the next Node
delete tmp; // deallocate tmp
cout << "deallocated " << tmp << " next is " << p << ' ';
}
}

void List::insert( const string &s )
{
   // replace the call to push_back( s ) with your code to insert
   // s in the doubly-linked list in alphabetical order

   push_back( s );
}

void List::push_back( const string &s )
{
// n points to a new node
Node *n = new Node( s, 0, tail );

if( tail == 0 ) // tail not pointing to a node yet?
{
head = tail = n; // head and tail point to new node in the list
}
else
{ // tail->next points to new node
tail->set_next( n );
tail = n; // tail points to last node in the list
}
}

void List::push_front( const string &s )
{
// n points to a new node
Node *n = new Node( s, head, 0);

if( head == 0 ) // head not pointing to a node yet?
{
head = tail = n; // head and tail point to new node in the list
}
else
{ // head->prev points to new node
head->set_prev( n );
head = n; // head points to first node in the list
}
}

void List::remove( const string &s )
{
  
for( Node *p = head; p; p = p->get_next( ) )
{
if( p->get_word( ) == s )
{
Node *tmp;
tmp = p->get_prev( );

if( tmp ) // is there a prev node?
{
tmp->set_next( p->get_next( ) );
}
else // at the beginning of the list
{
head = p->get_next( );
}

tmp = p->get_next( );
if( tmp ) // is there a next node?
{
tmp->set_prev( p->get_prev( ) );
}
else // at the end of the list
{
tail = p->get_prev( );
}

delete p; // deallocate the node containing s

break; // terminate loop after finding first occurrence of s
}
}
}

ostream &operator <<( ostream &out, const List &list )
{
for( Node *p = list.head; p; p = p->get_next( ) )
{
cout << p << ' ' << setw( 8 ) << p->get_word( )
<< ' ' << "next:" << ' ' << p->get_next( ) << ' ';
}

return out;
}

Here LAB07 CPP FILE
#include "List.h"

int main( )
{
List list; // create an object list of type List

cout << "please enter a few words (xxx to terminate list): ";

string s; // s is a string object

while( cin >> s ) // read a string into s
{
if( s == "xxx" )
{
break; // terminate loop when string is equal to "xxx"
}

list.insert( s ); // add s to list in alphabetical order

cout << " list: " << list << ' ';
}

cout << " here is the list: " << list << ' ';

cout << "please enter word words to delete from the list (xxx to terminate): ";

while( cin >> s )
{
if( s == "xxx" )
{
break; // terminate loop when string is equal to "xxx"
}

list.remove( s ); // remove first node containing string s, if any

cout << " list: " << list << ' ';
}

cout << " the final list: " << list << ' ';

return 0;
}

HERE LIST H FILE
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

class Node
{
public:
// constructor
Node( const string &, Node * const, Node * const );

const string &get_word( ) const;// get a const reference to word

Node *get_next( ) const; // get a pointer to next node
Node *get_prev( ) const; // get a pointer to previous node

Node *set_next( Node * ); // set next pointer
Node *set_prev( Node * ); // set prev pointer

private:
string word;
Node *next; // pointer to the next node
Node *prev; // pointer to the previous node

// do not generate defautl copy ctor
Node( const Node & );
// do not generate default copy assign. oper.
const Node &operator =( const Node & );
};

class List
{
public:
List( ); // constructor
~List( ); // destructor

// push a node to the back of list
void push_back( const string & );
// push a node to the front of list
void push_front( const string & );

void insert( const string & ); // insert a node in alphabetical order
void remove( const string & ); // remove a node containing string

// output a list object
friend ostream &operator <<( ostream &, const List & );

private:
Node *head;
Node *tail;
// do not generate a default copy ctor
List( const Node & );
// do not generate default copy assign. oper.
const List &operator =( const List & );
};

Explanation / Answer

void List::insert( const string &s )
{
   // replace the call to push_back( s ) with your code to insert
   // s in the doubly-linked list in alphabetical order

   Node *n = new Node(s, 0, 0);
   if(head == NULL){
       head = n;
       return;
   }
   Node *temp = head;
   Node *t;
   while(temp != NULL){
       if(temp->get_word() > s){
           if(temp == head){
               n->set_next(head);
               head->set_prev(n);
               head = n;
               return;
           }
           else{
               n->set_next(temp);
               n->set_prev(temp->get_prev());
               temp->get_prev()->set_next(n);
               temp->set_prev(n);
               return;
           }
       }
       t = temp;
       temp = temp->get_next();
   }
   t->set_next(n);
   n->set_prev(t);
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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