Using c++ I need help to solve problem two but in order to do so I need to use t

Question

Using c++ I need help to solve problem two but in order to do so I need to use the selection sort in the first problem and providing an executable program to test the program.

1. Write a function that takes a linked list of integers and rearranges the nodes so that the integers stored are sorted into the order smallest to largest, with the smallest integer in the node at the head of the list. If the original list had any integers occurring more than once, then the changed list will have the same number of each integer. For concreteness you will use lists of integers, but your function should still work if you replace the integer type with any other type for which the less-than operation is part of a total order semantics. Use the following function prototype and specification:

void sort_list(node*& head_ptr); // Precondition: head_ptr is a head pointer of // a linked list of items, and these items can be // compared with a less-than operator. // Postcondition: head_ptr points to the head // of a linked list with exactly the same entries // (including repetitions if any), but the entries // in this list are sorted from smallest to // largest. The original linked list is no longer // available.

Your procedure will implement the following algorithm (which is often called selection sort): The algorithm removes nodes one at a time from the original list and adds the nodes to a second list until all the nodes have been moved to the second list. The second list will then be sorted.

// Pseudocode for selection sort while (the first list still has some nodes) {

Find the node with the largest item of all the nodes in the first list.

Remove this node from the first list. 3. Insert this node at the head of the second list.

}

After all the nodes are moved to the second list, the pointer, head_ptr, can be moved to point to the head of the second list. Note that your function will move entire nodes, not just items, to the second list. Thus, the first list will get shorter and shorter until it is an empty list. Your function should not need to call the new operator since it is just moving nodes from one list to another (not creating new nodes).

2. Rewrite the selection sort so that it is a template function, with the template parameter specifying the type of data in each node. Your new selection sort function will use the template version of the node.test program

Explanation / Answer

#include <iostream>
using namespace std;

//a template node class representing a node in singly linked list
template <typename T>
class node
{
private:
T data;
node *next;
public:
node(T item)
{
data = item;
next = NULL;
}
node(T item, node* link)
{
data = item;
next = link;
}
T getData() const
{
return data;
}
node* getNext()
{
return next;
}
void setData(T item)
{
data = item;
}
void setNext(node *n)
{
next = n;
}
};

//sorts a singly linked list pointed by head. since head is passed by reference, the changes made to head are available in calling function
template <typename T>
void sort_list(node<T>* &head)
{
node<T> *newhead=NULL, *maxnode=NULL, *prev=NULL,*curr, *beforemax=NULL;

if(head == NULL) return;

//repeat as long as the original list is not empty
while(head!=NULL)
{
maxnode = prev = beforemax =NULL;
curr = head;

//each time get the maximum node and remove it from the original list
while(curr != NULL)
{
//if we have not yet set max node or current node is greater than max, save the previous and the max node
if(maxnode == NULL || curr->getData() > maxnode->getData())
{
beforemax = prev;
maxnode = curr;
}

prev = curr;
curr = curr->getNext();
}

//once we get the max node , remove it from original list and simply put this maxnode before the newlist's head node
if(maxnode == head) // removing original head node
{
head = head->getNext(); //update the original head to point to next
}
else //removing in between
{
beforemax->setNext(maxnode->getNext());
}

//put the maxnode infront of the new head node and then update the new head to point to this newly added node
maxnode->setNext(newhead);
newhead = maxnode;
}

head = newhead;
}

//prints a singly linked list starting at head
template <typename T>
void print_list(node<T> *head)
{
node<T>*p = head;
while(p!=NULL)
{
cout<<p->getData()<<" ";
p = p->getNext();
}
cout<<endl;
}

//adds a data item into a singly linked list pointed to by head. adds the new item to end of the existing list. head is passed by reference
template <typename T>
void add_to_list(node<T>* &head, T data)
{
node<T> *p=new node<T>(data), *q=head;
if(head == NULL)
head = p;
else
{
while( q->getNext() != NULL)
q = q->getNext();

q->setNext(p);
}

return;

}

int main()
{

int count, n;
node<int> *head=NULL;
cout<<"How many numbers do you want to add"<<endl;
cin>>count;
for(int i= 0; i <count; i++)
{
cout<<"Enter number:";
cin>>n;

add_to_list(head, n);
}

cout<<"The original list contents are "<<endl;
print_list(head);

sort_list(head);

cout<<"The list after sorting is "<<endl;
print_list(head);

return 0;
}

output

How many numbers do you want to add
5
Enter number:232
Enter number:4
Enter number:13
Enter number:43
Enter number:77
The original list contents are
232 4 13 43 77
The list after sorting is
4 13 43 77 232

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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