I can't get the code to display in an ordered list.

// Chapter 5 - Homework Assignment

#include <iostream>
#include <cstdlib>


using namespace std;
//
// DECLARE FUNCTION HEADER FOR
// CLASS ListNode
class ListNode
{
public:
    ListNode(double v, ListNode *p)
    {
        value = v; 
        next = p;
    }
private:
    double value;
    ListNode *next;
    friend class LinkedList;
};
//
// DECLARE FUNCTION HEADER FOR
// CLASS LinkedList
class LinkedList
{
public:
    void add(double x);
    bool isMember(double x);
    LinkedList( ) { head = NULL;}
    void rPrint(){ rPrint(head);}
    ~LinkedList();
    void insert(double x, int pos);
    void sort();
private:
    ListNode * head;
    static void rPrint(ListNode *pList);
    static ListNode * insert(ListNode *item, ListNode *sortedList);

};

//****************************************************************
//                                          *
// The function sorts by successively removing the head of the   *
// remaining list and inserting the item into a sorted list.     *
// The sorted list starts out empty.                             *
//****************************************************************
//
// FOR THE LINKED LIST TO USE THE sort() FUNCTION
void LinkedList::sort()
{
  ListNode *sortedList = NULL;

 //
 // USE A while LOOP TO CONTINUE LOOPING
 // AS LONG AS HEAD IS NOT EQUAL TO NULL
while(head != NULL)
  {
    ListNode *item = head;
    //
    // TO MOVE POINTER TO NEXT
    item  -> next = head;       
    item-> next = sortedList;

    sortedList = insert(item, sortedList);
  }
  head = sortedList;
}

//***********************************************
//           insert(item, sortedList)           *
// Inserts the node item into an a sorted       *
// list and returns the resulting sorted list.  *
//***********************************************
ListNode *LinkedList::insert(ListNode *item , ListNode *sortedList)
{
  // If sortedList is empty or first member of the  sorted list
  // is greater or equal to item then item becomes the first
  // member of the augmented list

  if (sortedList == NULL || sortedList->value >= item->value)
   {
      item->next = sortedList;
      return item;
   }

  // Use recursion to insert the item at the right place in the tail
  sortedList->next = insert(item, sortedList->next);
  return sortedList;
}


//**********************************************************
//              LinkedList::insert                         *
//  Insert a given value at a specified position.          *
//**********************************************************
void LinkedList::insert(double x, int pos)
{

    if (pos == 0 || head == NULL)
    {
        //  ADD VALUE TO THE BEGINNING OF THE LIST
        head = new ListNode(x, head);
        return;
    }


    ListNode *p = head;
    int numberToSkip = 1;
    while (numberToSkip <= pos)
    {
       if (p->next == NULL || numberToSkip == pos)
       {
           p->next = new ListNode(x, p->next);
           return;
       }
       //
       // TO MOVE THE POINTER TO THE NEXT NODE
       p = p->next;
       numberToSkip++;
    }
}
//
// TO CREATE THE LinkedList DESTRUCTOR
LinkedList::~LinkedList()
{
   ListNode *p = head;
   ListNode *q;  // Next pointer
   while (p != NULL)
   {
      q = p->next;
      delete p;
      p = q;
   }
}

//******************************************************
//            Recursive print function                 *
//  Prints all elements on a list passed as parameter. *
//******************************************************
void LinkedList::rPrint(ListNode *pList)
{
  if (pList == NULL) return;
  else
   {
      cout << pList->value << "  ";
      rPrint(pList->next);
   }
}



//**********************************
//     LinkedList::add             *
// Adds a given value to the list. *
//**********************************
void LinkedList::add(double x)
{
    head = new ListNode(x, head);
}



int main( )
{
    // Explain program to user
    cout << "This program allows you to enter number in a linked list"
         << "\nby position.  It also allow the list to be sorted.\n";
    //
    cout << "\nenter your first and last name here.\n\n";

    //
    //CREATE AN EMPTY LIST
    LinkedList list1;

    // Construct a list using  insert by position
    for (int k  = 1; k <= 5; k++)
    {
       cout << "\nEnter a number followed by a position: ";
       int x, pos;
       cin >> x >> pos;
       list1.insert(x, pos);
       cout << "\nCurrent list membership is: ";
       list1.rPrint();
   }
   // Demonstrate the list sort.
   //
   // TO SORT THE LIST
   list1.sort();
   cout << "\n\nFollowing is the sorted list: \n";
   //

   list1.rPrint();
   list1.sort();
   //
   cout << "\n\n\n\n";
   system("pause");
   return 0;
}
Attachments test.png 12.06 KB

I can't get the code to display in an ordered list.

In that screenshot, at the bottom, it is sorted. What don't you like about it?

Edited 2 Years Ago by Moschops

That was how my code is supposed to look like. This is was my code looks like.

Attachments Picture1.png 128.71 KB

The problem appears to be in this function

ListNode *LinkedList::insert(ListNode *item, ListNode *sortedList)

That function is destroying the original list. It should be inserting item into SortedList and returning SortedList. Instead, it is doing just the opposite.

One way to solve the problem is for insert() to create a new node and add to sortedList, leaving item list link intact.

ListNode *LinkedList::insert(ListNode *item, ListNode *sortedList)
{
    // If sortedList is empty or first member of the  sorted list
    // is greater or equal to item then item becomes the first
    // member of the augmented list

    if (sortedList == NULL || sortedList->value >= item->value)
    {
        //item->next = sortedList;
        return new ListNode(item->value, sortedList);
    }

    // Use recursion to insert the item at the right place in the tail
    sortedList->next = insert(item, sortedList->next);
    return sortedList;
}

You also have to change this function so that it can iterate through the entire original linked list. The problem is that the last line will cause a memory leak, so before changing head = SortedList you have to delete the linked list pointed to by head.

void LinkedList::sort()
{
    ListNode *sortedList = NULL;

    //
    // USE A while LOOP TO CONTINUE LOOPING
    // AS LONG AS HEAD IS NOT EQUAL TO NULL
    ListNode *item = head;
    while (item != NULL)
    {
        //
        // TO MOVE POINTER TO NEXT
        sortedList = insert(item, sortedList);
        item = item->next;
    }
    head = sortedList;
}

Edited 2 Years Ago by Ancient Dragon

bb8e427938c71ead079384f593495744

#include <iostream>
#include <cstdlib>

using namespace std;
//
// TO DECLARE FUNCTION HEADER FOR
// CLASS ListNode
class ListNode
{
public:
    ListNode(double v, ListNode *p)
    {
        value = v; next = p;
    }
private:
    double value;
    ListNode *next;
    friend class LinkedList;
};
//
// DECLARE FUNCTION HEADER FOR
// CLASS LinkedList
class LinkedList
{
public:
    void add(double x);
    bool isMember(double x);
    LinkedList( ) { head = NULL;}
    void rPrint(){ rPrint(head);}
    ~LinkedList();
    void insert(double x, int pos);
    void sort();
private:
    ListNode * head;
    static void rPrint(ListNode *pList);
    static ListNode * insert(ListNode *item, ListNode *sortedList);

};

//****************************************************************
//                                          *
// The function sorts by successively removing the head of the   *
// remaining list and inserting the item into a sorted list.     *
// The sorted list starts out empty.                             *
//****************************************************************
//
// FOR THE LINKED LIST TO USE THE sort() FUNCTION
void LinkedList::sort()
{
  ListNode *sortedList = NULL;

 //
 // A while LOOP TO CONTINUE LOOPING
 // AS LONG AS HEAD IS NOT EQUAL TO NULL
ListNode *item = head;
   while(item != NULL)

  {
    //ListNode *item = head;
    //
    // MOVE POINTER TO NEXT
    sortedList = insert(item, sortedList);
    item = item->next;

  }
  head = item;
}

//***********************************************
//           insert(item, sortedList)           *
// Inserts the node item into an a sorted       *
// list and returns the resulting sorted list.  *
//***********************************************
ListNode *LinkedList::insert(ListNode *item , ListNode *sortedList)
{
  // If sortedList is empty or first member of the  sorted list
  // is greater or equal to item then item becomes the first
  // member of the augmented list

  if (sortedList == NULL || sortedList->value >= item->value)
   {
     //item->next = sortedList;
      return new ListNode(item->value, sortedList);
   }

  // Use recursion to insert the item at the right place in the tail
  sortedList->next = insert(item, sortedList->next);
  return sortedList;
}


//**********************************************************
//              LinkedList::insert                         *
//  Insert a given value at a specified position.          *
//**********************************************************
void LinkedList::insert(double x, int pos)
{

    if (pos == 0 || head == NULL)
    {
        // ADD VALUE TO THE BEGINNING OF THE LIST
        head = new ListNode(x, head);
        return;
    }


    ListNode *p = head;
    int numberToSkip = 1;
    while (numberToSkip <= pos)
    {
       if (p->next == NULL || numberToSkip == pos)
       {
           p->next = new ListNode(x, p->next);
           return;
       }
       //
       //MOVE THE POINTER TO THE NEXT NODE
       p = p->next;
       numberToSkip++;
    }
}
//
//CREATE THE LinkedList DESTRUCTOR
LinkedList::~LinkedList()
{
   ListNode *p = head;
   ListNode *q;  // Next pointer
   while (p != NULL)
   {
      q = p->next;
      delete p;
      p = q;
   }
}

//******************************************************
//            Recursive print function                 *
//  Prints all elements on a list passed as parameter. *
//******************************************************
void LinkedList::rPrint(ListNode *pList)
{
  if (pList == NULL) return;
  else
   {
      cout << pList->value << "  ";
      rPrint(pList->next);
   }
}



//**********************************
//     LinkedList::add             *
// Adds a given value to the list. *
//**********************************
void LinkedList::add(double x)
{
    head = new ListNode(x, head);
}



int main( )
{
    // Explain program to user
    cout << "This program allows you to enter number in a linked list"
         << "\nby position.  It also allow the list to be sorted.\n";
    //
    cout << "\nenter your first and last name here.\n\n";

    //
    // CREATE AN EMPTY LIST
    LinkedList list1;

    // Construct a list using  insert by position
    for (int k  = 1; k <= 5; k++)
    {
       cout << "\nEnter a number followed by a position: ";
       int x, pos;
       cin >> x >> pos;
       list1.insert(x, pos);
       cout << "\nCurrent list membership is: ";
       list1.rPrint();
   }
   // Demonstrate the list sort.
   //
   // SORT THE LIST
    //list1.sort();
    cout << "\n\nFollowing is the sorted list: \n";
   //

   list1.rPrint();
   list1.sort();
   //
   cout << "\n\n\n\n";
   system("pause");
   return 0;
}

Its still not sorting in order.

#include <iostream>
#include <cstdlib>

using namespace std;

// CLASS ListNode
class ListNode
{
public:
    ListNode(double v, ListNode *p)
    {
        value = v; next = p;
    }
private:
    double value;
    ListNode *next;
    friend class LinkedList;
};
//
// DECLARE FUNCTION HEADER FOR
// CLASS LinkedList
class LinkedList
{
public:
    void add(double x);
    bool isMember(double x);
    LinkedList( ) { head = NULL;}
    void rPrint(){ rPrint(head);}
    ~LinkedList();
    void insert(double x, int pos);
    void sort();
private:
    ListNode * head;
    static void rPrint(ListNode *pList);
    static ListNode * insert(ListNode *item, ListNode *sortedList);

};

//****************************************************************
//                                          *
// The function sorts by successively removing the head of the   *
// remaining list and inserting the item into a sorted list.     *
// The sorted list starts out empty.                             *
//****************************************************************
//
// THE LINKED LIST TO USE THE sort() FUNCTION
void LinkedList::sort()
{
    ListNode *sortedList = NULL;

    //
    // USE A while LOOP TO CONTINUE LOOPING
    // AS LONG AS HEAD IS NOT EQUAL TO NULL
    ListNode *item = head;
    while (item != NULL)
    {
        //
        // TO MOVE POINTER TO NEXT
        sortedList = insert(item, sortedList);
        item = item->next;
    }
    head = sortedList;
}


//***********************************************
//           insert(item, sortedList)           *
// Inserts the node item into an a sorted       *
// list and returns the resulting sorted list.  *
//***********************************************
ListNode *LinkedList::insert(ListNode *item, ListNode *sortedList)
{
    // If sortedList is empty or first member of the  sorted list
    // is greater or equal to item then item becomes the first
    // member of the augmented list

    if (sortedList == NULL || sortedList->value >= item->value)
    {
        //item->next = sortedList;
        return new ListNode(item->value, sortedList);
    }

    // Use recursion to insert the item at the right place in the tail
    sortedList->next = insert(item, sortedList->next);
    return sortedList;
}



//**********************************************************
//              LinkedList::insert                         *
//  Insert a given value at a specified position.          *
//**********************************************************
void LinkedList::insert(double x, int pos)
{

    if (pos == 0 || head == NULL)
    {
        // TO ADD VALUE TO THE BEGINNING OF THE LIST
        head = new ListNode(x, head);
        return;
    }


    ListNode *p = head;
    int numberToSkip = 1;
    while (numberToSkip <= pos)
    {
       if (p->next == NULL || numberToSkip == pos)
       {
           p->next = new ListNode(x, p->next);
           return;
       }
       //
       // TO MOVE THE POINTER TO THE NEXT NODE
       p = p->next;
       numberToSkip++;
    }
}
//
// TO CREATE THE LinkedList DESTRUCTOR
LinkedList::~LinkedList()
{
   ListNode *p = head;
   ListNode *q;  // Next pointer
   while (p != NULL)
   {
      q = p->next;
      delete p;
      p = q;
   }
}

//******************************************************
//            Recursive print function                 *
//  Prints all elements on a list passed as parameter. *
//******************************************************
void LinkedList::rPrint(ListNode *pList)
{
  if (pList == NULL) return;
  else
   {
      cout << pList->value << "  ";
      rPrint(pList->next);
   }
}



//**********************************
//     LinkedList::add             *
// Adds a given value to the list. *
//**********************************
void LinkedList::add(double x)
{
    head = new ListNode(x, head);
}



int main( )
{
    // Explain program to user
    cout << "This program allows you to enter number in a linked list"
         << "\nby position.  It also allow the list to be sorted.\n";
    //
    cout << "\nenter your first and last name here.\n\n";

    //
    // TO CREATE AN EMPTY LIST
    LinkedList list1;

    // Construct a list using  insert by position
    for (int k  = 1; k <= 5; k++)
    {
       cout << "\nEnter a number followed by a position: ";
       int x, pos;
       cin >> x >> pos;
       list1.insert(x, pos);
       cout << "\nCurrent list membership is: ";
       list1.rPrint();
   }
   // Demonstrate the list sort.
   //
   // TO SORT THE LIST
    list1.sort();
    cout << "\n\nFollowing is the sorted list: \n";
   //

   list1.rPrint();
   list1.sort();
   //
   cout << "\n\n\n\n";
   system("pause");
   return 0;
}

This is the final code the works. I want to thank you so much for all your help. If it weren't for you I'd be stuck for a long time.

Edited 2 Years Ago by Hector_2: I forgot something in the code.

This question has already been answered. Start a new discussion instead.