Assignment:

Complete a C++ class implementation for a linked-list of sorted (ascending) positive integers. The class name for this class is LLSortedPosInt and its specification appears in the file LLSortedPosInt.h. This specification is accompanied by two other files: (1) an incomplete implementation of the class in the file LLSortedPosInt.cpp and (2) a test program called testLL.cpp. You are to complete the implementation of the LLSortedPosInt class by adding your own code to the stubbed member functions. You should NOT make any changes to the specification file.

You should develop and test your class implementation using a full-featured IDE such as Visual Studio rather than continually uploading it into this ZyLab. However, your final program submission must be executable within this ZyLab, because that is where it will be tested and graded.

Details:

Linked lists are useful data structures for storing data records, particularly in situations where the order and/or number of the items to be kept is dynamic during the course of the programs execution. In this exercise, youll complete the implementation of a linked-list. In doing so, youll not only learn how to manipulate pointers better, but you'll also learn about a new and useful data type.

To get started, examine the linked list specification in LLSortedPosInt.h. Note, this specification has 13 publicly-accessible functions. Your task is to implement these 13 functions using the comments in LLSortedPosInt.cpp and the instructions appearing below to guide you.

With 13 functions to implement, it is important that you approach the task in an orderly manner. Your instructor recommends that you work on one function at a time and immediately test each function for correctness when you complete it before moving on to the next function. We also recommend you develop the functions in the order in which they appear in the .h file. To help with testing we have provided a main program in the file testLL.cpp.

While you can upload your code to this ZyLab to test your implementation, a better way to repeatedly test your functions would be to use the Visual Studio environment and an ordinary text file with input re-direction. This method of testing will be demonstrated in class.

Linked List Functions:

The 13 functions you must add to complete the implementation are described below. The functions are described by the effect they have on a list. Lists are represented as a set of comma-separated keys enclosed in angle brackets. For example < > is an empty list, because it contains no keys. A list with the keys 3, 5, and 8 appears as <3, 5, 8>.

1. Constructors (4): Classes must have constructors to initialize instances of the objects. The constructors you will implement for this project are:

   • A default constructor: LLSortedPosInt l1; // initializes l1 to be the empty list (i.e., < >)
   • A constructor taking a single int parameter: LLSortedPosInt l2(5); // initializes l2 as <5>
   • A constructor taking an array of integers as a single parameter: int a[] = {2, 5, 8}; LLSortedPosInt l3(a, 3); // initializes l3 as <2, 5, 8>
   • A copy constructor: LLSortedPosInt l4(l3); // initializes l4 as <2, 5, 8>

2. Destructor (1): Because the class specification includes a pointer among the attributes, you will need to implement a destructor to delete (i.e., free or release) any storage allocated in the constructors or other member functions.

3. Assignment Operator (1): Because the class specification includes a pointer among the attributes, you will need to implement an assignment operator to ensure you get a deep copy of the list when you make an assignment. For example, l4 = l2; // results in l4 as a unique (non-aliased) copy of l2

4. Print Operator (1): This function provides a natural way to print your LLSortedPosInt objects, such as in the code example below: cout << "l3 = " << l3 << endl; // prints l3 = <2, 5, 8> to the terminal

5. Boolean Functions (2): You are to implement two functions which return a Boolean value

   • A function isEmpty() which returns true if the associated list contains no data elements, and returns false otherwise. For example, l1.isEmpty(); // returns true l2.isEmpty(); // returns false
   • A function containsElement(key) which returns true if key is an element in the list and returns false otherwise. For example, l3.containsElement(8); // returns true l3.containsElement(6); // returns false

6. Other Operator Member Functions (2): When a class has a pointer among its attributes not only is there a need for deep copying during assignment, but we also may need to implement a deep comparison of the objects:

   • An equality test (i.e., ==) operator. For example, l3 == l4; //returns true after copy constructor above, i.e., <2, 5, 8> == <2, 5, 8>
   • An inequality test (i.e., !=) operator. For example, l3 == l4; //returns false after assignment operator above, i.e., <2, 5, 8> != <5>

7. Other Friend Functions (2): Finally, we need a mechanism for adding and removing items from a list. The functions for these operations are:

   • A addition operator (+) to add items to the list. For example, l3 = l3 + l3; // results in l3 = <2, 2, 5, 5, 8, 8>
   • A subtraction operator (-) to remove items from the list. For example, l1 = l3 - l2; // results in l1 = <2, 2, 5, 8, 8>

//LLSortedPosInt.h // The following pattern prevents multiple inclusion of class definitions #ifndef LLSPOSINT_H #define LLSPOSINT_H #include  using namespace std; struct Node; typedef Node* NodePtr; // The key value HEAD_OF_LIST is used as a "sentinal" value const int HEAD_OF_LIST = -1; class LLSortedPosInt { public: // constructors LLSortedPosInt(); LLSortedPosInt(int key); LLSortedPosInt(int *keys, int n); LLSortedPosInt(const LLSortedPosInt &l); // destructor ~LLSortedPosInt(); // assignment operator LLSortedPosInt& operator= (const LLSortedPosInt &l); // print operator (non-member function) friend ostream& operator<<(ostream &out, const LLSortedPosInt &l); // other member functions bool isEmpty ( ) const; bool containsElement (int key) const; // other operator member functions bool operator==(const LLSortedPosInt &l) const; bool operator!=(const LLSortedPosInt &l) const; // other operator functions (non-member functions) friend LLSortedPosInt operator+ (const LLSortedPosInt &l1, const LLSortedPosInt &l2); friend LLSortedPosInt operator- (const LLSortedPosInt &l1, const LLSortedPosInt &l2); private: // helper functions void insert (int key); void remove (int key); // NOTE: see also the non-member function createNode() associated .cpp file // the data member for this class is a single item similar to the example // in ZyBook 12.21 NodePtr head; }; #endif //LLSPOSINT_H

 //LLSortedPosInt.cpp #include "LLSortedPosInt.h" // The linked-list is constructed of Node elements struct Node { int key; Node *next; }; // the following function is not a member function, it is a convenience // function which exists to make the implementation of the LLSortedPosInt // class more concise // createNode() allocates a Node and initializes it with the // given parameter values to simplify the initilization of a Node static NodePtr createNode(int key, NodePtr p) { // allocate a new Node for storing the given key value NodePtr n = new Node; // store the key value and the next pointer n->key = key; n->next = p; // return the new Node to the caller return n; } // Student implementation of LLSortedPosInt begins here // Constructors LLSortedPosInt::LLSortedPosInt() { // create the sentinal Node at the head of the list } LLSortedPosInt::LLSortedPosInt(int key) { // create the sentinal Node at the head of the list // add the single element key, as long as it is positive } LLSortedPosInt::LLSortedPosInt(int *keys, int n) { // create the sentinal node at the head of the list // add new Nodes for each positive value in keys } LLSortedPosInt::LLSortedPosInt(const LLSortedPosInt &l) { // create a deep copy of the input list l } // Destructor LLSortedPosInt::~LLSortedPosInt() { // free the Nodes in *this, including the sentinal } // Assignment Operator LLSortedPosInt& LLSortedPosInt::operator= (const LLSortedPosInt &l) { // handle self assignment if (this == &l) { return *this; } // free old elements of the list before the new elements from l are assigned // if necessary, rebuild the sentinal // build the list as a deep copy of l // return *this return *this; } // Print Operator (a non-member function) ostream& operator<< (ostream &out, const LLSortedPosInt &l) { // an empty list will be printed as <> // a singleton list (a list having one key value k) will be // printed as // a list having multiple keys such as 2, 5, 7 will be printed // as <2, 5, 7> // print the left angle bracket // print the keys in the list l // print the right angle bracket return out; } // Boolean Functions bool LLSortedPosInt::isEmpty ( ) const { // return true if only the sentinal is in the list; return false otherwise return false; } bool LLSortedPosInt::containsElement (int key) const { // return true if key is in the list; return false otherwise return false; } // Other Operator Member Functions bool LLSortedPosInt::operator==(const LLSortedPosInt &l) const { // compare the Nodes in *this with the Nodes in l // if all Node key values in *this match the cooresponding // Node key values in l, then the lists are equivalent return false; } bool LLSortedPosInt::operator!=(const LLSortedPosInt &l) const { // do the opposite of operator== return true; } // Other Operator Functions (non-member functions) LLSortedPosInt operator+ (const LLSortedPosInt &l1, const LLSortedPosInt &l2) { // create a copy of l1 and add each element of l2 to it in // the correct (sorted ascending) order, allow duplicates LLSortedPosInt sum; return sum; } LLSortedPosInt operator- (const LLSortedPosInt &l1, const LLSortedPosInt &l2) { // copy l1 and remove all of l2 from l1, taking care to // reclaim any storage -- do not to remove the sentinal Node LLSortedPosInt diff; return diff; } // The following helper functions are provide to assist you in // building the class--these helper functions are useful in // several places among the functions you will write--take time // to learn what they do // insert() inserts an element in the linked list in sorted order void LLSortedPosInt::insert(int key) { // setup pointers to walk the list NodePtr npp = head; NodePtr npc = head->next; // walk the list, searching until the given key value is exceeded while (npc != NULL && npc->key <= key) { npp = npc; npc = npc->next; } // insert the new value into the list npp->next = createNode(key, npc); } // remove() removes an element from the list (if it is present) void LLSortedPosInt::remove(int key) { // negative values should not be stored in the list if (key <= 0) { return; } // setup pointers to walk the list NodePtr npp = head; NodePtr npc = head->next; // search the list until the end (if necessary) while (npc != NULL) { // if the key value is found, then splice this Node from the list and // reclaim its storage if (npc->key == key) { npp->next = npc->next; delete npc; break; } // walk the pointers to the next Node npp = npc; npc = npc->next; } }