Using C++ .. The parameter to the following two recursive routines is a pointer

Question

Using C++ ..

The parameter to the following two recursive routines is a pointer to a singly linked list of numbers, whose elements are unique (no duplicates) and unsorted. Each node 111 the list contains two members, info (a number) and next (a pointer to the next node). (a) Write a recursive value-returning function, MinLoc, that receives a pointer to a list of unsorted numbers and returns a pointer to the node that contains the minimum value in the list. (b) Write a recursive void function, Sort, that receives a pointer to an unsorted list of numbers and reorders the values in the list from smallest to largest. This function may call the recursive MinLoc function that you wrote in part (a).

Explanation / Answer

#include<bits/stdc++.h>
using namespace std;

class node
{
   int data;
   node* next;

public:
   node()//Default Constructor
  
   {
       data=0;
       next=NULL;
   }

   node(int d)//Parameter Constructor
   {
       data=d;
       next=NULL;
   }
   friend class List;
  
};

class List
{
   node* head;

   public:

   List()
   {
       head=NULL;
   }

   void insert(int d)
   {

           node* temp=new node(d);
          
       if(head==NULL)//Create node
       {
           head=temp;
           head->next=NULL;

       }
       else
       {
           node* t=head;//Insert at last of list

           while(t->next!=NULL)
           {
               t=t->next;
           }
           t->next=temp;
           temp->next=NULL;
       }
   }

   void printList()//print list
   {
       node* t=head;

           while(t!=NULL)
           {
               cout<<t->data<<" ";
               t=t->next;
           }
          
   }

   void minLoc1()//Wrapper
   {
       node* small=minLoc(head);
       cout<<" Smallest is "<<small->data;
   }

   node* minLoc(node* p)//Find minimum location of node
   {
       node* current = p;
node* next;

if (p->next == NULL) {
//The value at this node is obviously smaller than a non-existent value
return current;
} else {
//Recur to find the highest value from the rest of the LinkedList
next = minLoc(p->next);
}

//Return the highest value between this node and the end of the list
if (current->data <next->data) {
return current;
} else {
return next;
}

   }

   void Sort1() //Wrapper Function
   {

       Sort(head);
   }

   void Sort(node* head)
   {

       node* temp=head;

       while(temp->next!=NULL)
       {
           node* small=minLoc(temp->next); //Find smallest node

           //Swap with Smallest
          
               int tempData;

               tempData=small->data;
              
               small->data=temp->data;
               temp->data=tempData;
               temp=temp->next;
          

       }
   }

};

int main(int argc, char const *argv[])
{
   List l;
   l.insert(10);
   l.insert(20);
   l.insert(5);
   l.printList();
   l.minLoc1();
   l.Sort1();
   cout<<" Sorted List ";
   l.printList();
   return 0;
}

==============================================

akshay@akshay-Inspiron-3537:~/Chegg$ g++ list.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
10 20 5
Smallest is 5
Sorted List
5 10 20

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.