Question

(C++) All programs will be included!

This lab gives you a little practice with linked lists

·Debug insertSorted() and implement sorted() in numberlist.cpp

·Hint: insertSorted() is just missing a few parts. What is in the function can work fine once you add the right code, though you are free to rewrite it

·You need to have main.cpp, numberlist.h and numberlist.cpp in this project, and if you are using Code::Blocks, remember to set the Build Options to indicate you want to use C++11 or later. The expected output for the final program is:

Test driver to check insertSorted() and sorted() methods of NumberList class

Is empty list in ascending order? true

Displaying list first time:

3.9

5.2

Displaying list second time:

3.9

4.6

5.2

8.4

Is list in ascending order? true

3.9

4.6

5.2

8.4

7.1

Is list in ascending order? False

MAIN.CPP

#include <iostream>
#include "numberlist.h"

using namespace std;

int main()
{
    NumberList list;
    cout << "Test driver to check insertSorted() and sorted() methods of NumberList class"
         << endl << endl;

    cout << "Is empty list in ascending order? "
         << boolalpha << list.sorted() << endl;

    list.insertSorted(5.2);
    list.insertSorted(3.9);
    cout << "Displaying list first time: " << endl;
    list.displayList();
    list.insertSorted(8.4);
    list.insertSorted(4.6);
    cout << "Displaying list second time: " << endl;
    list.displayList();
    cout << "Is list in ascending order? "
         << list.sorted() << endl;
    list.appendNode(7.1);
    list.displayList();
    cout << "Is list in ascending order? "
         << list.sorted() << endl;

    return 0;
}

NUMBERLIST.CPP

#include "numberlist.h"
#include <iostream>

using namespace std;

const double NumberList::EPSILON = 0.000001;


// insert so values are in ascending order
void NumberList::insertSorted(double num) {
    ListNode * newNode = new ListNode;
    newNode->value = num;
    newNode->next = nullptr;

    if (num < head->value) {
        newNode->next = head;
        head = newNode;
    }
    // declare outside for loop so we can use iter after the loop
    ListNode * iter = head;
    for (; nullptr != iter->next; iter = iter->next) {
        if (num < iter->next->value) {
            // insert between iter and iter->next
            iter->next = newNode;
            return;
        }
    }
}


/** destructor to free memory for all elements in list */
NumberList::~NumberList()
{
    ListNode * nodePtr, * nextNode;

    nodePtr = head;
    while (nodePtr != NULL) {
        nextNode = nodePtr->next;
        delete nodePtr;
        nodePtr = nextNode;
    }
}

/** display list to console
    rewritten to show similarity to working with arrays */
void NumberList::displayList() const {
    for (ListNode *nodePtr = head;
         nodePtr != NULL;
         nodePtr = nodePtr->next)
        cout << nodePtr->value << endl;
}

void NumberList::insertNode(double num) {
    ListNode * node = new ListNode;
    node->next = head;
    node->value = num;
    head = node;
}

/** add to end of list */
void NumberList::appendNode(double num) {
    // cannot put num into list directly
    // must construct a node
    ListNode *newNode;

    // use this to go through list
    // serves same purpose as loop counter
    // for array processing
    ListNode *nodePtr;

    newNode = new ListNode;
    newNode->value = num;
    // always have to initialize the pointer
    newNode->next = NULL;

    // usually best to handle special cases
    // first
    if (!head) // like (NULL == head)
        head = newNode;
    else {
        nodePtr = head;
        /** should make sure you understand why the condition
            checks nodePtr->next instead of nodePtr */
        while (nodePtr->next)   // same as (nodePtr->head != NULL)
            nodePtr = nodePtr->next;

        // the actual appending
        nodePtr->next = newNode;
    }
}

// delete a value from the list
void NumberList::deleteNode(double num) {
    ListNode * nodePtr;
    ListNode * previousNode;

    // handle special case first
    if (head->value == num) {
        // save pointer to 2nd element
        nodePtr = head->next;
        // free first element's memory
        delete head;
        head = nodePtr;
    }
    else {
        nodePtr = head;

        while (nodePtr != NULL && nodePtr->value != num) {
            previousNode = nodePtr;
            nodePtr = nodePtr->next;
        }

        /** if nodePtr is not at the end of the list,
           (What would that mean?)
           link the previous node to the node after nodePtr,
           then delete nodePtr
           */
        if (nodePtr) {
            previousNode->next = nodePtr->next;
            delete nodePtr;
        }
    }
}

numberlist.h

// a basic linked list class from Gaddis, ch. 17.2
#ifndef NUMBERLIST_H
#define NUMBERLIST_H
// replacing NULL by nullptr -- if you are using Code::Blocks,
// remember to set the build option that you are using C++11 or later

class NumberList
{
    private:
        // adding this for double comparison
        static const double EPSILON;

        struct ListNode {
            double value;
            ListNode *next;
        };
        ListNode * head; //!< points to start of list

    public:
        /** Default constructor */
        NumberList() {
            head = nullptr;
        }
        /** Default destructor */
        ~NumberList();

        // standard list operations
        // add to end of list
        void appendNode(double);
        // inserts in order
        void insertNode(double);
        void deleteNode(double);
        // insert so values are in ascending order
        // NOTE: if we really wanted this, we should remove
        // insertNode() and appendNode()
        // deleteNode() could stay
        void insertSorted(double);
        // returns true if sorted, false if not
        bool sorted() const;

        void displayList() const;
};

#endif // NUMBERLIST_H

Answer 1

The modified code for insert sorted is shown below:
// insert so values are in ascending order
void NumberList::insertSorted(double num) {
    ListNode * newNode = new ListNode;
    newNode->value = num;
    newNode->next = nullptr;

    if (num < head->value) {
        newNode->next = head;
        head = newNode;
    }
    // declare outside for loop so we can use iter after the loop
    ListNode * iter = head;
    for (; nullptr != iter->next; iter = iter->next) {
        if (num < iter->next->value) {
            // insert between iter and iter->next
             ListNode *temp=iter->next;//temporary node to store next node of iter.
            iter->next = newNode;
            newNode->next=temp;
            return;
        }
    }
   // if the num  is largest of all then it will not be inserted in for loop.
   //So,we need to connect it at last and since iter will be at last node currently therefore
   iter->next = newNode
   return; 
}

The code given in the question have some bugs which is get fixed above with the proper comments written.

Bugs Description :-

Inside the for loop i.e. if we need to insert the node in the middle then we need to connect newNode to the next of iter and also previously the node which is iter's next must be point to newNode 's next now.

So,thats the first bug above that we are not connecting the previous next of iter to newNode's next.

And ,also suppose the newNode we need to insert at last.So,it can't get inserted at last inside the for loop.

So,we inserted at the the end of for loop.

Now ,implementation of sorted function.

bool NumberList::Sorted()
{

 ListNode *temp=head;

while(temp->next!=NULL)

{

 if(temp->value>temp->next->value)

return false;

temp=temp->next;

}

return true;

}

In this function we are simply comparing current value with its next value.

If current value is greater than next value then return false.

If we could not find any such case in the list we'll return true