1
The problem
Implement a SortedList class which stores a list of int data in ascending order.
Program requirements
The public interface of your class is as follows:
class SortedList{
public:
SortedList();
SortedList(const SortedList& aSortedList);
~SortedList();
bool sortedIsEmpty() const;
int sortedGetLength() const;
void sortedInsert(int newItem, bool& success, bool& duplicate);
void sortedRemove(int index, bool& success);
void sortedRetrieve(int index, int& dataItem, bool& success) const;
int locatePosition(int dataItem, bool& success) const;
void printList() const;
/* private and protected members here ... */
};
You may include private and protected class members as you see fit.
The function sortedIsEmpty should test whether a given list is empty, and sortedLength should return the length of a given list.
The member function sortedRetrieve should return the kth value in the list for a positive integer k. If k is out of the range of indices of the list, the flag success should be false.
The member function sortedInsert should insert a given int into the list in the correct place. DUPLICATE ENTRIES ARE NOT ALLOWED. The flag duplicate should be true when there is a duplicate entry. The flag success should be false if the item to be inserted is a duplicate or (inclusive or) the insertion is unsuccessful because there is no more room to insert an item into the list.
(Note this last case will happen in an array-based implementation if there is no more space in the array, and will happen in a pointer-based implementation if the new operator is unable to allocate space for a new node.)
printList should print the entries of the list to the screen in the correct order.
locatePosition should locate the position of a given item in the linked list. Your code should use the flag success to handle the case when the item is not found in the list.
The class declaration and implementation must all be included in one file, named sortedlist.h
Your solution must work correctly with the driver program sortedlist.cpp. You may not change the file sortedlist.cpp in order to make your solution work. Your solution must also work with other driver programs.
How to do it
Much of your code can be taken or modified from the List class. At least in the pointer-based approach, you must take some care when inserting a new node at the beginning of the list, as opposed to in the middle or at the end of the list. Be sure your code handles both cases correctly.
The output of my solution (using the driver file sortedlist.cpp):
The list is empty.
The item 6 has been successfully inserted into the list.
The list now contains 6
The item 5 has been successfully inserted into the list.
The list now contains 5 6
The item -9 has been successfully inserted into the list.
The list now contains -9 5 6
-9 is already in the list.
Insertion unsuccessful.
The list now contains -9 5 6
6 is already in the list.
Insertion unsuccessful.
The list now contains -9 5 6
The item -15 is not in the list.
The item 30 is not in the list.
The item 6 is in the 3-th position in the list.
Index 6 out of range. No item has been removed.
The list now contains -9 5 6
The item 16 has been successfully inserted into the list.
The list now contains -9 5 6 16
The item 1 has been successfully inserted into the list.
The list now contains -9 1 5 6 16
The item 4 has been successfully inserted into the list.
The list now contains -9 1 4 5 6 16
The item 9 has been successfully inserted into the list.
The list now contains -9 1 4 5 6 9 16
16 is already in the list.
Insertion unsuccessful.
The list now contains -9 1 4 5 6 9 16
The item 25 has been successfully inserted into the list.
The list now contains -9 1 4 5 6 9 16 25
The 5-th item on the list has been removed.
The list now contains -9 1 4 5 9 16 25
The item -9 is in the 1-th position in the list.
The 1-th item on the list has been removed.
The list now contains 1 4 5 9 16 25
The item 20 has been successfully inserted into the list.
The list now contains 1 4 5 9 16 20 25
The item 14 has been successfully inserted into the list.
The list now contains -9 5 6 14 16
