I am taking a c++ data structures class, and I need help with this assignment. P
ID: 664663 • Letter: I
Question
I am taking a c++ data structures class, and I need help with this assignment.
PLEASE NOTE: You may not use any STL collection classes when implementing this programming project. You must use the code discussed in class.
Working With Singly-Linked Lists
Complete the following exercises using the cs20::List class presented in class.
1. Without using a ListIterator, define and implement a new operation called insert_back which takes a single template Object and inserts the Object at the end of the list. A brute force version of this method would walk down the list to find the end, and therefore would run in linear time, O(n), for a list with n elements. Think carefully about the running time of this operation, T(n). Without changing the meaning of this operation or any other, modify the representation of a List and alter whatever methods are necessary to make insert_back run in constant time: O(1).
HINT: Your List class will need to continually maintain a pointer to the last (tail) ListNode on the List, and all of List's methods will have to ensure that this member stays current even as the list changes.
This new operation should have the signature:
void List<Object>::insert_back( const Object& data );
TESTING HINT:
Run the methods: insert( 3 ); insert( 2 ); insert( 1 ); Print the list. What should it look like? Run the methods: insert_back( 5 ); Print the list. What should it look like? Run the methods: remove( 5 ); Print the list. What should it look like? Run the methods: insert_back( 7 ); insert( 8 ); Print the list. What should it look like? Run the methods: remove( 3 ); remove( 2 ); remove( 1 ); Run the methods: remove( 7 ); remove( 8 ); Print the list. What should it look like? Run the methods: insert_back( 5 ); Print the list. What should it look like?
2. Create a new method on a List that determines whether the list contains an item that is duplicated. Recall that you can compare values against one another using == operator. For example, for a list containing head-() (11) (8) (15) (3), isDuplicated( 1 ) should return false. However, it would return true when working on a list containing head- () (7) (1) (9) (15) (1).
This new operation should have the signature:
bool List<Object>::isDuplicated( const Object& o ) const;
Because it has been marked const, this method is saying that it is read-only. When your implementation runs, you won't be able to actually change any data members of the List passed to your method. Because the Object parameter is marked const, this parameter is being marked read-only and cannot be changed. Create a test driver program that exercises each of these exercises to satisfy yourself that your implementation is correct. For example, you should print the List before and after invoking the operation.
TESTING HINT:
Run the methods: insert( 3 ); insert( 2 ); insert( 1 ); insert( 1 ); Print the list. What should it look like? Call: isDuplicated( 1 ); What should it return? Print the list. What should it look like? Run the methods: remove( 3 ); remove( 2 ); Print the list. What should it look like? Call: isDuplicated( 3 ); What should it return? Print the list. What should it look like? Run the methods: remove( 1 ); Run the methods: insert( 7 ); insert( 9 ); insert( 11 ); Print the list. What should it look like? Call: isDuplicated( 1 ); What should it return? Print the list. What should it look like?
Explanation / Answer
LIST.H
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "ListNode.h"
#include "ListIterator.h"
namespace cs20
{
template <class Object>
class List
{
public:
List();
List( const List& righths );
~List();
bool LisEmpty() const;
bool LisIncreasing() const;
void LmakeEmpty();
ListIterator<Object> Lzeroth() const;
ListIterator<Object> Lfirst() const;
void Listinsert( const Object& data, const ListIterator<Object> &iter );
void Listinsert( const Object& data );
void Listinsert_back( const Object& data );
ListIterator<Object> ListfindPrevious( const Object& data ) const;
void Listremove( const Object& data );
const List& operator =( const List& righths );
const List& operator <<( const List& righths );
private:
ListNode<Object> * Nhead;
ListNode<Object> * Ntail;
};
}
#endif
LIST.CPP
#ifndef LIST_CPP
#define LIST_CPP
#include "List.h"
namespace cs20
{
template <class Object> List<Object>::List()
{
Nhead = new ListNode<Object>;
Ntail->nextIsNull();
}
template <class Object>
List<Object>::List( const List<Object>& righths )
{
Nhead = new ListNode<Object>;
Ntail->nextIsNull();
*this = righths;
}
template <class Object> List<Object>::~List()
{
LmakeEmpty();
delete Nhead;
}
template <class Object> bool List<Object>::LisEmpty() const
{
return( Nhead->nextIsNull() );
}
template <class Object> void List<Object>::LmakeEmpty()
{
while (!LisEmpty())
{
Listremove( Lfirst().retrieve() );
}
Ntail = NULL;
}
template <class Object> ListIterator<Object> List<Object>::Lzeroth() const
{
return( ListIterator<Object>( Nhead ) );
}
template <class Object> ListIterator<Object> List<Object>::Lfirst() const
{
return( ListIterator<Object>( Nhead->getNext() ) );
}
template <class Object> void List<Object>::Listinsert( const Object& data, const ListIterator<Object> &iter )
{
if (iter.isValid()) {
ListNode<Object>* newnode = new ListNode<Object>( data, iter.current->getNext() );
iter.current->setNext( newnode );
}
}
template <class Object> void List<Object>::Listinsert( const Object& data )
{
ListNode<Object>* newnode = new ListNode<Object>( data, Nhead->getNext() );
Nhead->setNext( newnode );
}
template <class Object> void List<Object>::Listinsert_back( const Object& data )
{
ListNode<Object>* lastNode = Nhead;
while (lastNode->getNext())
lastNode = lastNode->getNext();
lastNode->setNext( newnode );
}
template <class Object> ListIterator<Object> List<Object>::ListfindPrevious( const Object& data ) const
{
ListNode<Object>* node = Nhead;
while( node->getNext() != NULL && node->getNext()->getElement() != data )
{
node = node->getNext();
}
if (node->getNext() == NULL)
{
node = NULL;
}
return ListIterator<Object>( node );
}
template <class Object> bool List<Object>::LisIncreasing() const
{
ListNode<Object>* node= Nhead;
while (node->getNext() != NULL)
{
if (node->getNext()->getElement() <= node->getElement())
return false;
node = node->getNext();
}
return true;
}
template <class Object> void List<Object>::Listremove( const Object& data )
{
ListIterator<Object> iter = ListfindPrevious( data );
if (iter.isValid())
{
ListNode<Object>* node = ListfindPrevious( data ).current;
if (node->getNext() != NULL) {
ListNode<Object> *oldNode = node->getNext();
node->setNext( node->getNext()->getNext() ); // Skip oldNode
delete oldNode;
}
}
}
template <class Object> const List<Object>& List<Object>::operator =( const List<Object>& righths )
{
if (this != &righths)
{
LmakeEmpty();
ListIterator<Object> rightiter = righths.Lfirst( );
ListIterator<Object> myiterator = Lzeroth();
while( rightiter.isValid() )
{
Listinsert( rightiter.retrieve(), myiterator );
rightiter.advance();
myiterator.advance();
}
}
return( *this );
}
}
#endif
Menu.cpp
#include <iostream>
#include "List.h"
#include "ListNode.h"
#include "ListIterator.h"
#include "List.cpp"
#include "ListNode.cpp"
#include "ListIterator.cpp"
using namespace std;
using namespace cs20;
enum OPTION {MAKEEMPTY, REMOVE, ISEMPTY, FINDPREVIOUS, INSERT, QUIT, PRINT };
OPTION menu();
void printList( const List<int>& l );
int main(int argc, char* argv[])
{
int value;
List<int> listobj;
ListIterator<int> iter;
OPTION choice;
do {
choice = menu();
switch( choice )
{
case MAKEEMPTY:
listobj.LmakeEmpty();
break;
case ISEMPTY:
if (listobj.LisEmpty()) {
cout << "list is empty" << endl;
}
else {
cout << "list is not empty" << endl;
}
break;
case REMOVE:
cout << "Please provide int to remove: ";
cin >> value;
listobj.Listremove( value );
break;
case INSERT:
cout << "Please provide int to insert: ";
cin >> value;
listobj.Listinsert( value );
break;
case FINDPREVIOUS:
cout << "Please provide int to find: ";
cin >> value;
iter = listobj.ListfindPrevious( value );
if (iter.isValid()) {
cout << "previous element = " << iter.retrieve() << endl;
}
else {
cout << "data element was not found!" << endl;
}
break;
case PRINT:
printList( listobj );
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
int sample()
{
cout << "Forming Lists" << endl;
int two = 2;
List<int> l1 = List<int>();
List<int> l2 = List<int>();
l1.Listinsert( one );
l1.Listinsert( two );
cout << "print l1" << endl;
printList( l1 );
cout << "l2 = l1" << endl;
l2 = l1;
cout << "print l2" << endl;
printList( l2 );
cout << "l1.remove(one)" << endl;
l1.Listremove( one );
cout << "print l1" << endl;
printList( l1 );
cout << "print l2" << endl;
printList( l2 );
cout << "findPrevious 1 in l2" << endl;
ListIterator<int> iter = l2.ListfindPrevious( one );
if (iter.isValid())
{
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else
{
cout << "--iter not valid" << endl;
}
cout << "findPrevious 2 in l2" << endl;
iter = l2.ListfindPrevious( two );
if (iter.isValid())
{
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else {
cout << "--iter not valid" << endl;
}
cout << "findPrevious 1 in l1" << endl;
iter = l1.ListfindPrevious( one );
if (iter.isValid())
{
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else
{
cout << "--iter not valid" << endl;
}
cout << "findPrevious 2 in l1" << endl;
iter = l1.ListfindPrevious( two );
if (iter.isValid())
{
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else
{
cout << "--iter not valid" << endl;
}
cout << "print l1" << endl;
printList( l1 );
cout << "l1.remove(one)" << endl;
l1.Listremove( one );
cout << "print l1" << endl;
printList( l1 );
return( 0 );
}
void printList( const List<int>& l )
{
if (l.LisEmpty())
cout << "Empty list" << endl;
else
{
ListIterator<int> iter = l.Lfirst();
while (iter.isValid())
{
cout << iter.retrieve() << " -> ";
iter.advance();
}
cout << "NULL";
cout << endl;
}
}
OPTION menu()
{
char choice;
OPTION result;
cout << "(M)akeEmpty I(s)Empty (R)emove (I)nsert (F)indPrevious (P)rint (Q)uit: " << endl;
cin >> choice;
switch( choice )
{
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'R':
case 'r':
result = REMOVE;
break;
case 'I':
case 'i':
result = INSERT;
break;
case 'F':
case 'f':
result = FINDPREVIOUS;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'P':
case 'p':
result = PRINT;
break;
}
return( result );
}
LISTNODE.cpp
#ifndef LISTNODE_CPP
#define LISTNODE_CPP
#include "ListNode.h"
namespace cs20
{
template <class Object>
ListNode<Object>::ListNode( const Object& theElement, ListNode<Object> * node )
{
element = theElement;
next = node;
}
template <class Object> bool ListNode<Object>::nextIsNull() const
{
return( next == NULL );
}
template <class Object> const Object& ListNode<Object>::getElement() const
{
return( element );
}
template <class Object> ListNode<Object>* ListNode<Object>::getNext() const
{
return( next );
}
template <class Object> void ListNode<Object>::setNext( ListNode<Object> * node )
{
next = node;
}
}
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.