(C++) Write a function that takes a linked list of integers and rearranges the n
ID: 3690674 • Letter: #
Question
(C++) 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_kist(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)
{
1.Find the node with the largest item of all the nodes in the first list.
2. 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).
Explanation / Answer
Solution: See the code below:-
-----------------------------------------------
1. function to find largest value in a linked list
//function to find largest value in a linked list
node* find_largest(node* &head_ptr)
{
node* largest_node=head_ptr; //assume head node is largest
while(largest_node->get_next() != NULL)
{
if(largest_node->get_next()->get_item() > largest_node->get_item()
{
largest_node=largest_node->get_next();
}
}
return largest_node;
}
2. function remove a given node from the list
//function remove a node from the list
void delete_node(node* &head_ptr, node* &node_ptr)
{
//if head_ptr and node_ptr are same.
if(head_ptr == node_ptr)
{
if(head_ptr->get_next() == NULL) //there is only one node in the list
{
delete head_ptr;
return;
}
//make next of head_ptr as new head_ptr of list to remove node_ptr from list
head_ptr = head_ptr->get_next();
return;
}
//if node_ptr is not head_ptr.
//find the previous node
node *prev_ptr = head_ptr;
while(prev_ptr->get_next() != NULL && prev_ptr->get_next() != node_ptr)
{
prev_ptr = prev_ptr->get_next();
}
//if node_ptr is in list or not
if(prev_ptr->get_next() == NULL)
{
cerr<<"Error deleteing node. Not present in list."<<endl;
return;
}
//Remove node_ptr from list
prev_ptr->set_next(prev_ptr->get_next()->get_next());
}
3. function to insert a given node as the head of the list
//function to insert a given node as the head of the list
void insert_node(node* &head_ptr, node* &node_ptr)
{
//if list is empty
if(head_ptr == NULL
{
head_ptr=node_ptr; //insert node_ptr as the first (head) node of list
}
else
{
node_ptr->set_next(head_ptr); //existing head_ptr will become the next of new head_ptr
head_ptr = node_ptr;
}
}
4. function to sort the list as per given algorithm
//function to sort the list as per given algorithm
//head_ptr is the head of existing unsorted list.
void sort_list(node* &head_ptr)
{
node* temp_head_ptr=NULL; //head pointer for the second list
node* curr=head_ptr;
while(curr!=NULL)
{
node* largest_node=find_largest(head_ptr);
delete_node(head_ptr,largest_node);
insert_node(temp_head_ptr,largest_node);
}
head_ptr=temp_head_ptr;
}
--------------------------------
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.