PROBLEM BACKGROUND: Recall that an abstract data type, or ADT, is a set of data values together with a collection of allowable operations on those data values. When done properly, the implementation of the allowable operations (we often call them methods) is of no concern to users of the ADT. Thus we can change the implementation without affecting any client programs.

PROBLEM DESCRIPTION: This assignment calls for you to again provide an implementation file for the SortedList class (loosely based on the description given in the Carrano textbook pages 133-134). This time, however, the implementation will use a dummy-headed circular singly-linked list using dynamically allocated nodes to store the list items. For your code to be considered correct, it must provide to any client program the services contracted by the SortedList class specification. The specification for this SortedList is given formally in the DLL.h header file found in $PUB/SortedList.

IMPLEMENTATION NOTES: Do all your work in a directory ~/OLA/olaDLL that you will create. Copy these six files found in the directory $PUB/SortedList/: DLL.cpp, DLL.h, SLC.cpp, SLC.h, SortedListTester.cpp, and DLL.makefile. Rename your copy of DLL.makefile to simply makefile in your directory. You may NOT alter the file DLL.h; this class definition constitutes a contract between you and the users of the class; You can not alter the contract on your own. Several member functions (or methods) in DLL.cpp are incomplete; your assignment is to supply code to complete them. Be sure to

Use deep copy semantics in your copyList() implementation

Properly implement the private method locateNode()

Use the private method locateNode() appropriately in implementing your Insert()

Use the private method locateNode() appropriately in implementing your Remove()

// ID: DLL.cpp / Implementation file for the class SortedList // AUTHOR: student name // INSTALLATION: MIDDLE TENNESSEE STATE UNIVERSITY // RCS: $Revision$ $Date$ // REMARKS: Implementation file for the class SortedList. // Pointer-based dummy-headed circular singly-linked list implementation. #include  using namespace std; #include "DLL.h" // Constructors and Destructor: SortedList::SortedList() : size(0) { head = new tNode; head->next = head; } // end Constructor SortedList::SortedList(const SortedList& sList) { size = sList.size; copyList(sList.head, head); } // end Copy Constructor SortedList::~SortedList() { // *** ... substitute your code for this comment ... *** } // end Destructor // Overloaded Operator: SortedList& SortedList::operator=(const SortedList& sList) { tNodePtr future, cur; // Is there any work to be done? Check if target same as sList. if ( this != &sList ) { // Deallocate anything the assignment target might have allocated. // *** ... substitute your code for this comment ... *** // Now "copy" the object size = sList.size; copyList(sList.head, head); } return *this; } // end operator= // List Operations: bool SortedList::IsEmpty() const { return (size == 0); } // end IsEmpty int SortedList::Length() const { return size; } // end Length // *** ... place Insert and Remove code here ... *** int SortedList::Find(ItemType anItem) const // IN { tNodePtr prev; // Pointer to predecessor of found node int position; // Item's list position bool isPresent = locateNode(anItem, prev, position); return (isPresent) ? position : -1; } // end Find // *** ... place Retrieve code here ... *** // Private functions: void SortedList::copyList(const tNodePtr& original, tNodePtr& duplicate) // IN OUT { // *** ... substitute your code for this comment ... *** } // end copyList bool SortedList::locateNode (ItemType anItem, tNodePtr& previous, int& position) const // IN OUT OUT { // *** ... substitute your code for this comment ... *** } // end locateNode // End of implementation file. 

// ID: DLL.h / Header file for the class SortedList // RCS: $Revision$ $Date$ // AUTHOR: CSCI 2170 instructor // INSTALLATION: MTSU // REMARKS: Class and type definitions for the SortedList. // Items are in strict ascending order; duplicates are not allowed. // Dynamic storage dummy-headed circular singly-linked list implementation. #ifndef DLL_h_ // To prevent problems from multiple inclusions #define DLL_h_ typedef int ItemType; // data type of list items class SortedList { public: // Constructors and Destructor: SortedList(); // (default) constructor SortedList(const SortedList& sList); // copy constructor ~SortedList(); // destructor // Overloaded Operator: SortedList& operator=(const SortedList& sList); // assignment // List Operations: bool IsEmpty() const; // Determines whether a sorted list is empty. // Pre: None. // Post: Returns true if list is empty, otherwise returns false. int Length() const; // Returns the number of items that are in a sorted list. // Pre: None. // Post: Returns the number of items currently on the list. void Insert(ItemType newItem, bool& success); // IN OUT // Inserts newItem into its proper sorted position in a sorted // list. Duplicates are not allowed and attempts to insert // duplicates should be unsuccessful. The success flag indicates // whether the insertion was successful. // Pre: newItem is defined. // Post: If insertion is successful, newItem is in its proper // sorted position in the list and success is true; otherwise // success is false. void Remove(ItemType anItem, bool& success); // IN OUT // Deletes anItem from a sorted list. The success flag indicates // whether the deletion was successful. // Pre: anItem is defined. // Post: If anItem was in the sorted list, it is removed and // success is true; otherwise success is false. int Find(ItemType anItem) const; // IN // Returns the position (in the range 1<= position<= Length()) where // anItem exists in a sorted list or -1 if anItem is not in the list. // Pre: anItem is defined. // Post: Returns the position in the sorted list where anItem resides // or -1 if anItem is not in the sorted list. // The item anItem and the list are unchanged. void Retrieve(int position, ItemType& dataItem, bool& success) const; // IN OUT OUT // Sets dataItem to the item at "position" of the sorted list. // The success flag indicates whether the retrieval was successful. // Pre: position is defined and is the number of the item to be retrieved. // Post: If 1 <= position <= Length(), then dataItem is the value // of the desired item and success is true; otherwise success is // false. The list is left unchanged by this operation. private: struct tNode; typedef tNode* tNodePtr; // pointer to list node struct tNode { ItemType item; tNodePtr next; }; void copyList(const tNodePtr& original, tNodePtr& duplicate); // IN OUT // Make a deep copy of a list. // Pre: original points to an existing list. // Post: duplicate points to a duplicate copy of the "original" list. bool locateNode(ItemType anItem, tNodePtr& previous, int& position) const; // IN OUT OUT // Returns true if anItem exists in the list, a pointer to the previous // (i.e., predecessor) node in the list and and anItem's list position. // Returns false if anItem is not in the list and a pointer to what would // have been the previous node if anItem had been in the list; the value // of position is that of what anItem's would have been if it were in the // list. // Pre: anItem is defined. // Post: See above. Note that the value of position lies in the range // 1 <= position <= Length()+1. The pointer "previous" points to // the last node on the list whose value was less than that of // anItem or to the dummy node if the position==1. int size; // number of items on list. tNodePtr head; // pointer to the dummy node of the // dummy headed circular singly-linked list. }; // end SortedList class #endif 

# makefile for "SortedListTester (olaDLL & olaALL & olaSLC)" program(s) # CXX = g++ -std=c++11 CXXFLAGS = -pedantic -g # Create linked-list version (olaDLL) of "SortedListTester" program olaDLL: DLLtester.o DLL.o $(CXX) $(CXXFLAGS) DLLtester.o DLL.o -o olaDLL DLLtester.o: SortedListTester.cpp DLL.h $(CXX) $(CXXFLAGS) -c -DDLL SortedListTester.cpp -o DLLtester.o DLL.o: DLL.cpp DLL.h $(CXX) $(CXXFLAGS) -c DLL.cpp # Create linked-list version (olaALL) of "SortedListTester" program olaALL: ALLtester.o ALL.o $(CXX) $(CXXFLAGS) ALLtester.o ALL.o -o olaALL ALLtester.o: SortedListTester.cpp ALL.h $(CXX) $(CXXFLAGS) -c -DALL SortedListTester.cpp -o ALLtester.o ALL.o: ALL.cpp ALL.h $(CXX) $(CXXFLAGS) -c ALL.cpp # Create simple array-based version (olaSLC) of "SLCtester" program olaSLC: SLCtester.o SLC.o $(CXX) $(CXXFLAGS) SLCtester.o SLC.o -o olaSLC SLCtester.o: SortedListTester.cpp SLC.h $(CXX) $(CXXFLAGS) -c -DSLC SortedListTester.cpp -o SLCtester.o SLC.o: SLC.cpp SLC.h $(CXX) $(CXXFLAGS) -c SLC.cpp # Remove object and executable files clean: rm -f *.o olaDLL olaALL olaSLC