This assignment calls for you to complete an implementation file for the SortedL
ID: 3865846 • Letter: T
Question
This assignment calls for you to complete an implementation file for the SortedList class using a strategy detailed below. (This class is similar, but not identical, to one described by Carrano.) For your code to be considered correct, it must provide to any client program the services contracted by the SortedList class specification. This specification is given formally in the ALL.h header file. Study the specification carefully!
A straightforward array-based "shuffle" implementation of the SortedList class is found in the file SLC.cpp. Your task is to replace this implementation with a more efficient "singly-linked list" implemention as discussed in lecture (albeit still using arrays). Your replacement implementation will be a modification of the file ALL.cpp. In that file
* The public member function (aka method) Remove() and the private member function locateNode() are incomplete; supply code to complete them.
* Use the private method locateNode() appropriately in implementing your Remove().
All.cpp
All.h
SLC.cpp
SLC.h
Sortedlisttester.cpp
Explanation / Answer
The files needed for this assignment are ALL.h , ALL.cpp and SortedListTester.cpp. While ALL.h does not need any modification, the other 2 files are modified, and given below. So just use the 3 files listed above and test.
The SortedListTester.cpp was modifed to # define ALL so that it works with the ALL.h. Also the tests for Find(5) and Find(109) will not return return 1 or 15 unlike previous simple implementation. We only need to check if they are present (i.e. position is not -1). So modified Tester file to do check if the find was successful.
Please don't forget to rate the answer if it helped. Thank you.
ALL.cpp
#include "ALL.h"
#include <iostream>
using namespace std;
const int NONE = -1; // Sentinel value indicating "no item"
// Constructors and Destructor:
SortedList::SortedList() : size(0), avail(1)
{
// Initialize "dummy" node (list[0])
list[0].next = NONE;
// Create "avail" list of empty (i.e., available) nodes
for (int subscript=avail; subscript<=MAX_LIST-1; ++subscript)
list[subscript].next = subscript+1;
list[MAX_LIST].next = NONE;
} // end (default) constructor
SortedList::SortedList(const SortedList& aList): size(aList.size), avail(aList.avail)
// IN
{
// NOTE: Because all the nodes (used and avail) have necessary
// information in them, everything must be copied.
for (int subscript = 0; subscript <= MAX_LIST; ++subscript)
list[subscript] = aList.list[subscript];
} // end copy constructor
SortedList::~SortedList()
{
// NOTE: This is just "placeholder" code. The array implementation
// of SortedList does not really need a destructor.
} // end destructor
// List Operations:
bool SortedList::IsEmpty() const
{
return (size == 0);
} // end IsEmpty
int SortedList::Length() const
{
return size;
} // end Length
void SortedList::Insert(ItemType newItem, bool& success)
// IN OUT
{
int previous, newItemSubscript, position;
bool isPresent;
newItemSubscript = PopAvail();
if (newItemSubscript == NONE)
success = false;
else
{
isPresent = locateNode(newItem, previous, position);
if (isPresent)
{
// No go: this would be a duplicate
PushAvail(newItemSubscript); // return unused slot
success = false;
}
else
{
list[newItemSubscript].item = newItem;
list[newItemSubscript].next = list[previous].next;
list[previous].next = newItemSubscript;
++size;
success = true;
}
}
} // end Insert
void SortedList::Remove(ItemType anItem, bool& success)
// IN OUT
{
int position, previous;
bool isPresent = locateNode(anItem, previous, position);
if(isPresent)
{
list[previous].next = list[position].next;
PushAvail(position);
size--;
success = true;
}
else
success = false;
} // end Remove
int SortedList::Find(ItemType anItem) const
// IN
{
int previous, position;
bool isPresent = locateNode(anItem, previous, position);
return (isPresent) ? position : NONE;
} // end Find
void SortedList::Retrieve(
int position, ItemType& dataItem, bool& success) const
// IN OUT OUT
{
success = position>=1 && position<=Length();
if (success)
{
int current = list[0].next;
for (int count = 1; count<position; ++count)
current = list[current].next;
dataItem = list[current].item;
}
} // end Retrieve
int SortedList::PopAvail()
{
int subscript = avail;
if (subscript == NONE)
return NONE;
else
{
avail = list[subscript].next;
return subscript;
}
} // end PopAvail
void SortedList::PushAvail(int subscript)
// IN
{
list[subscript].next = avail;
avail = subscript;
} // end PushAvail
bool SortedList::locateNode(
ItemType anItem, int& previous, int& position) const
// IN OUT OUT
{
previous = 0;
position = list[0].next;
int i = 0;
while(i < size )
{
//cout << "position = " << position << endl;
if(list[position].item == anItem)
{
return true;
}
else if(list[position].item < anItem)
{
previous = position;
position = list[position].next;
i++;
}
else
return false;
}
return false;
} // end locateNode
// End of implementation file.
SortedListTester.cpp
#include <iostream>
using namespace std;
#define MAXLOOP 50 // Maximum loop iterations terminator
#define ALL
#if defined DLL
#include "DLL.h" // Dynamic dummy-headed circular linked list
#define OLA "olaDLL"
#elif defined ALL
#include "ALL.h" // Array storage dummy-headed linked list
#define OLA "olaALL"
#elif defined SLC
#include "SLC.h" // Simple array-based sorted list
#define OLA "olaSLC"
#else // Default to "SLC":
#include "SLC.h" // Simple array-based sorted list
#define OLA "olaSLC"
#endif
void DisplayList(SortedList List);
int main()
{
SortedList L, LL, LLL;
ItemType dataItem;
bool success;
int position;
cerr << endl << "Starting " << OLA << " testing:" << endl;
// Assign empty list L to empty list LL, thereby checking assignment
// and "deep copy" semantics; this assignment does not appear in
// the publicly-available SortedListClient.cc code
LL = L;
// Check initial status of list L.
if ( L.IsEmpty() )
cerr << "OKAY: List is initially empty." << endl;
else
cerr << "ERROR: IsEmpty() returning bad value." << endl;
// See what happens when you try to insert one item.
dataItem = 50;
L.Insert(dataItem, success);
if (success)
cerr << "OKAY: Insert operation (seemingly) succeeded." << endl;
else
cerr << "ERROR: Insert operation failed." << endl;
if ( L.IsEmpty() )
cerr << "ERROR: IsEmpty() returning bad value." << endl;
else
cerr << "OKAY: List is not empty anymore." << endl;
cerr << "Length of list = " << L.Length() << endl;
// See what happens when you try ...
// ...these extra instructor-supplied tests for grading
// Check initial status of list LL.
if ( LL.IsEmpty() )
cerr << "OKAY: List LL is initially empty." << endl;
else
cerr << "ERROR: LL.IsEmpty() returning bad value." << endl;
// Check initial status of list LLL.
if ( LLL.IsEmpty() )
cerr << "OKAY: List LLL is initially empty." << endl;
else
cerr << "ERROR: LLL.IsEmpty() returning bad value." << endl;
// See what happens when you try to retrieve an item.
L.Retrieve(1, dataItem, success);
if (success)
{
if (dataItem == 50)
cerr << "OKAY: List item #" << 1 << " is: " << dataItem << endl;
else
cerr << "ERROR: List item #" << 1 << " is: " << dataItem << endl;
}
else
cerr << "ERROR: Retrieve operation failed." << endl;
L.Retrieve(0, dataItem, success);
if (success)
cerr << "ERROR: Retrieve operation failed." << endl;
L.Retrieve(2, dataItem, success);
if (success)
cerr << "ERROR: Retrieve operation failed." << endl;
// Fill list L with a bunch of numbers.
L.Insert(25, success);
if (!success)
cerr << "ERROR: Insert operation failed." << endl;
L.Insert(80, success);
if (!success)
cerr << "ERROR: Insert operation failed." << endl;
L.Insert(10, success);
if (!success)
cerr << "ERROR: Insert operation failed." << endl;
L.Insert( 5, success);
if (!success)
cerr << "ERROR: Insert operation failed." << endl;
L.Insert(35, success);
if (!success)
cerr << "ERROR: Insert operation failed." << endl;
L.Insert(15, success);
if (!success)
cerr << "ERROR: Insert operation failed." << endl;
L.Insert(15, success);
if (success)
cerr << "ERROR: Invalid insert of duplicate succeeded." << endl;
for (int i = 1; i <= 9; i++)
{
L.Insert(i+100, success);
if (!success)
cerr << "ERROR: Insert operation failed." << endl;
}
// Display the items on the list L.
cerr << endl;
cerr << "DisplayList( L ): should list 16 items "
<< "(starting with 5 and ending with 109):" << endl;
DisplayList( L );
cerr << endl;
// See what happens when you try to delete an item.
L.Remove(25, success);
if (!success)
cerr << "ERROR: Remove operation failed." << endl;
position = L.Find(5);
if (position == 1)
cerr << "ERROR: Find failed. Remove() error?" << endl;
position = L.Find(109);
if (position == 15)
cerr << "ERROR: Find failed. Remove() error?" << endl;
// Delete the first item.
L.Remove(5, success);
if (!success)
cerr << "ERROR: Remove operation failed." << endl;
// Delete the last item.
L.Remove(109, success);
if (!success)
cerr << "ERROR: Remove operation failed." << endl;
// Check that really gone.
position = L.Find(5);
if (position!=-1)
cerr << "ERROR: Find operation failed." << endl;
position = L.Find(109);
if (position!=-1)
cerr << "ERROR: Find operation failed." << endl;
// Check what happens with duplicates.
L.Remove(15, success);
if (!success)
cerr << "ERROR: Remove operation failed." << endl;
position = L.Find(15);
if (position!=-1)
cerr << "ERROR: Find found a duplicate." << endl;
L.Remove(15, success);
if (success)
cerr << "ERROR: Remove operation should have failed." << endl;
L.Remove(100, success);
if (success)
cerr << "ERROR: Remove operation should have failed." << endl;
{SortedList M;
M = L;
LLL = M;
// Display the items on the list M.
cerr << "DisplayList( M ): should list 12 items " <<
"(10, 35, 50, 80, 101, ..., 108):" << endl;
DisplayList( M );
cerr << endl;
}
// Display the items on the list L.
cerr << "DisplayList( L ): should list 12 items " <<
"(10, 35, 50, 80, 101, ..., 108):" << endl;
DisplayList( L );
cerr << endl;
// See what happens when you try to delete ALL items.
cerr << "Should go from List Length = 11 down to 0:" << endl;
for ( int maxLoop=MAXLOOP; ! L.IsEmpty() && maxLoop>0; maxLoop--)
{
L.Retrieve(1,dataItem,success);
if (!success)
{
cerr << "ERROR: Retrieve operation failed." << endl;
break;
}
else
{
L.Remove(dataItem,success);
if (!success)
cerr << "ERROR: Delete operation failed." << endl;
cerr << "List Length = " << L.Length() << endl;
}
}
// Display the items on the list LLL.
cerr << endl;
cerr << "DisplayList( LLL ): should list 12 items " <<
"(10, 35, 50, 80, 101, ..., 108):" << endl;
DisplayList( LLL );
// ...end extra instructor-supplied tests for grading
// Display the items on the list L.
cerr << endl << "Next line of output should say: End " << OLA << endl;
DisplayList( L );
cerr << "End " << OLA << endl;
return 0;
} // end main
void DisplayList(SortedList list)
// IN
{
ItemType dataItem;
bool success;
// Display the items on the list.
int maxLoop=MAXLOOP;
for (int pos = 1; pos <= list.Length(); pos++)
{
list.Retrieve(pos, dataItem, success);
if (success)
cerr << "List item #" << pos << " is: " << dataItem << endl;
else
cerr << "ERROR: Retrieve operation failed." << endl;
if (--maxLoop==0)
{
cerr << "ERROR: Length() failed." << endl;
break;
}
}
} // end DisplayList
output
Starting olaALL testing:
OKAY: List is initially empty.
OKAY: Insert operation (seemingly) succeeded.
OKAY: List is not empty anymore.
Length of list = 1
OKAY: List LL is initially empty.
OKAY: List LLL is initially empty.
OKAY: List item #1 is: 50
DisplayList( L ): should list 16 items
(starting with 5 and ending with 109):
List item #1 is: 5
List item #2 is: 10
List item #3 is: 15
List item #4 is: 25
List item #5 is: 35
List item #6 is: 50
List item #7 is: 80
List item #8 is: 101
List item #9 is: 102
List item #10 is: 103
List item #11 is: 104
List item #12 is: 105
List item #13 is: 106
List item #14 is: 107
List item #15 is: 108
List item #16 is: 109
DisplayList( M ): should list 12 items
(10, 35, 50, 80, 101, ..., 108):
List item #1 is: 10
List item #2 is: 35
List item #3 is: 50
List item #4 is: 80
List item #5 is: 101
List item #6 is: 102
List item #7 is: 103
List item #8 is: 104
List item #9 is: 105
List item #10 is: 106
List item #11 is: 107
List item #12 is: 108
DisplayList( L ): should list 12 items
(10, 35, 50, 80, 101, ..., 108):
List item #1 is: 10
List item #2 is: 35
List item #3 is: 50
List item #4 is: 80
List item #5 is: 101
List item #6 is: 102
List item #7 is: 103
List item #8 is: 104
List item #9 is: 105
List item #10 is: 106
List item #11 is: 107
List item #12 is: 108
Should go from List Length = 11 down to 0:
List Length = 11
List Length = 10
List Length = 9
List Length = 8
List Length = 7
List Length = 6
List Length = 5
List Length = 4
List Length = 3
List Length = 2
List Length = 1
List Length = 0
DisplayList( LLL ): should list 12 items
(10, 35, 50, 80, 101, ..., 108):
List item #1 is: 10
List item #2 is: 35
List item #3 is: 50
List item #4 is: 80
List item #5 is: 101
List item #6 is: 102
List item #7 is: 103
List item #8 is: 104
List item #9 is: 105
List item #10 is: 106
List item #11 is: 107
List item #12 is: 108
Next line of output should say: End olaALL
End olaALL