(c++)Write a function that takes a linked list of integers and rearranges the no
ID: 3667904 • Letter: #
Question
(c++)Write a function that takes a linked list of integers and rearranges the nodes so that the integers stored are sorter into the order smallest to largest, with the smallest integer inn the node at the head of the list. If the original list had any integers occuring more than once, then the changed list will have the same number of each integer. For correctness 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 partt 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 lilnked list with exaclty 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 ofte caled 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 foe 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 ths 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 t 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 mocing nodes from one list to another (not creating new nodes).
Here is the node file I already have and header file:
// FILE: node1.cxx
// IMPLEMENTS: The functions of the node class and the
// linked list toolkit (see node1.h for documentation).
// INVARIANT for the node class:
// The data of a node is stored in data_field, and the link in link_field.
#include "node1.h"
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t
#include <iostream>
using namespace std;
size_t list_length(const node *head_ptr)
// Library facilities used: cstdlib
{
const node *cursor;
size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
++answer;
return answer;
}
void list_head_insert(node *&head_ptr, const node::value_type &entry) {
head_ptr = new node(entry, head_ptr);
}
void list_insert(node *previous_ptr, const node::value_type &entry) {
node *insert_ptr;
insert_ptr = new node(entry, previous_ptr->link());
previous_ptr->set_link(insert_ptr);
}
node *list_search(node *head_ptr, const node::value_type &target)
// Library facilities used: cstdlib
{
node *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
if (target == cursor->data())
return cursor;
return NULL;
}
const node *list_search(const node *head_ptr, const node::value_type &target)
// Library facilities used: cstdlib
{
const node *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
if (target == cursor->data())
return cursor;
return NULL;
}
node *list_locate(node *head_ptr, size_t position)
// Library facilities used: cassert, cstdlib
{
node *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link();
return cursor;
}
const node *list_locate(const node *head_ptr, size_t position)
// Library facilities used: cassert, cstdlib
{
const node *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link();
return cursor;
}
void list_head_remove(node *&head_ptr) {
node *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link();
delete remove_ptr;
}
void list_remove(node *previous_ptr) {
node *remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
void list_clear(node *&head_ptr)
// Library facilities used: cstdlib
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
void list_copy(const node *source_ptr, node *&head_ptr, node *&tail_ptr)
// Library facilities used: cstdlib
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list.
if (source_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it.
list_head_insert(head_ptr, source_ptr->data());
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list.
source_ptr = source_ptr->link();
while (source_ptr != NULL) {
list_insert(tail_ptr, source_ptr->data());
tail_ptr = tail_ptr->link();
source_ptr = source_ptr->link();
}
}
void list_print(node * head_ptr)
{
for(node *i = head_ptr; i != NULL; i = i->link())
{
cout<<i->data()<<" ";
}
cout<<endl;
}
//Header file
// FILE: node1.h
// PROVIDES: A class for a node in a linked list, and list manipulation
#ifndef MAIN_SAVITCH_NODE1_H
#define MAIN_SAVITCH_NODE1_H
#include <cstdlib> // Provides size_t and NULL
class node {
public:
// TYPEDEF
typedef double value_type;
// CONSTRUCTOR
node(
const value_type &init_data = value_type(),
node *init_link = NULL
) {
data_field = init_data;
link_field = init_link;
}
// Member functions to set the data and link fields:
void set_data(const value_type &new_data) { data_field = new_data; }
void set_link(node *new_link) { link_field = new_link; }
// Constant member function to retrieve the current data:
value_type data() const { return data_field; }
// Two slightly different member functions to retreive
// the current link:
const node *link() const { return link_field; }
node *link() { return link_field; }
private:
value_type data_field;
node *link_field;
};
// FUNCTIONS for the linked list toolkit
std::size_t list_length(const node *head_ptr);
void list_head_insert(node *&head_ptr, const node::value_type &entry);
void list_insert(node *previous_ptr, const node::value_type &entry);
node *list_search(node *head_ptr, const node::value_type &target);
const node *list_search
(const node *head_ptr, const node::value_type &target);
node *list_locate(node *head_ptr, std::size_t position);
const node *list_locate(const node *head_ptr, std::size_t position);
void list_head_remove(node *&head_ptr);
void list_remove(node *previous_ptr);
void list_clear(node *&head_ptr);
void list_copy(const node *source_ptr, node *&head_ptr, node *&tail_ptr);
void list_print(node * head_ptr);
void removeDuplicates(node * head);
#endif
Explanation / Answer
main.cpp
#include <iostream>
#include <cstdlib>
#include "node1.h"
using namespace std;
using namespace main_savitch_5;
int main()
{
cout << "LIST TEST PROGRAM "
<< "~~~~~~~~~~~~~~~~~ ";
cout << "Creating a list with values 3 6 28 12 15... ";
node* list1 = new node(15);
list_head_insert(list1, 12);
list_head_insert(list1, 28); // creating and printing the list
list_head_insert(list1, 6);
list_head_insert(list1, 3);
cout << "Printing the list (testing printList(const node*) function)... ";
printList(list1); // prints list, new function
cout << " Now creating a list with all values less than 12 from the original... ";
node* list2 = splitLT(list1, 12);
cout << "Printing the new list (testing splitLT(const node*, int splittingValue)... ";
printList(list2);
cout << " Now creating a list with all values greater than or equal 12 from original... ";
node* list3 = splitGTE(list1, 12);
cout << "Printing the new list (testing splitGTE(const node*, int splittingValue)... ";
printList(list3);
cout << "This section will test the sort_list function... ";
cout << "Sorting and then printing list1... ";
sort_list(list1);
printList(list1);
cout << " Sorting and printing list2... ";
sort_list(list2);
printList(list2);
cout << " Sorting and printing list3... ";
sort_list(list3);
printList(list3);
cout << "THANK YOU! ";
cout << endl;
return EXIT_SUCCESS;
}
node1.h
// FILE: node1.h
// PROVIDES: A class for a node in a linked list, and list manipulation
// functions, all within the namespace main_savitch_5
//
// TYPEDEF for the node class:
// Each node of the list contains a piece of data and a pointer to the
// next node. The type of the data is defined as node::value_type in a
// typedef statement. The value_type may be any
// of the built-in C++ classes (int, char, ...) or a class with a copy
// constructor, an assignment operator, and a test for equality (x == y).
//
// CONSTRUCTOR for the node class:
// node(
// const value_type& init_data = value_type(),
// node* init_link = NULL
// )
// Postcondition: The node contains the specified data and link.
// NOTE: The default value for the init_data is obtained from the default
// constructor of the value_type. In the ANSI/ISO standard, this notation
// is also allowed for the built-in types, providing a default value of
// zero. The init_link has a default value of NULL.
//
// NOTE:
// Some of the functions have a return value which is a pointer to a node.
// Each of these functions comes in two versions: a non-const version (where
// the return value is node*) and a const version (where the return value
// is const node*).
// EXAMPLES:
// const node *c;
// c->link( ) activates the const version of link
// list_search(c,... calls the const version of list_search
// node *p;
// p->link( ) activates the non-const version of link
// list_search(p,... calls the non-const version of list_search
//
// MEMBER FUNCTIONS for the node class:
// void set_data(const value_type& new_data)
// Postcondition: The node now contains the specified new data.
//
// void set_link(node* new_link)
// Postcondition: The node now contains the specified new link.
//
// value_type data( ) const
// Postcondition: The return value is the data from this node.
//
// const node* link( ) const <----- const version
// node* link( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is the link from this node.
//
// FUNCTIONS in the linked list toolkit:
// size_t list_length(const node* head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The value returned is the number of nodes in the linked
// list.
//
// void list_head_insert(node*& head_ptr, const node::value_type& entry)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: A new node containing the given entry has been added at
// the head of the linked list; head_ptr now points to the head of the new,
// longer linked list.
//
// void list_insert(node* previous_ptr, const node::value_type& entry)
// Precondition: previous_ptr points to a node in a linked list.
// Postcondition: A new node containing the given entry has been added
// after the node that previous_ptr points to.
//
// const node* list_search(const node* head_ptr, const node::value_type& target)
// node* list_search(node* head_ptr, const node::value_type& target)
// See the note (above) about the const version and non-const versions:
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The pointer returned points to the first node containing
// the specified target in its data member. If there is no such node, the
// null pointer is returned.
//
// const node* list_locate(const node* head_ptr, size_t position)
// node* list_locate(node* head_ptr, size_t position)
// See the note (above) about the const version and non-const versions:
// Precondition: head_ptr is the head pointer of a linked list, and
// position > 0.
// Postcondition: The pointer returned points to the node at the specified
// position in the list. (The head node is position 1, the next node is
// position 2, and so on). If there is no such position, then the null
// pointer is returned.
//
// void list_head_remove(node*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list, with at
// least one node.
// Postcondition: The head node has been removed and returned to the heap;
// head_ptr is now the head pointer of the new, shorter linked list.
//
// void list_remove(node* previous_ptr)
// Precondition: previous_ptr points to a node in a linked list, and this
// is not the tail node of the list.
// Postcondition: The node after previous_ptr has been removed from the
// linked list.
//
// void list_clear(node*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: All nodes of the list have been returned to the heap,
// and the head_ptr is now NULL.
//
// void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
// Precondition: source_ptr is the head pointer of a linked list.
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for
// a new list that contains the same items as the list pointed to by
// source_ptr. The original list is unaltered.
// void list_piece(
// const node* start_ptr, const node* end_ptr,
// node*& head_ptr, node*& tail_ptr
// )
// Precondition: start_ptr and end_ptr are pointers to nodes on the same
// linked list, with the start_ptr node at or before the end_ptr node
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for a
// new list that contains the items from start_ptr up to but not including
// end_ptr. The end_ptr may also be NULL, in which case the new list
// contains elements from start_ptr to the end of the list.
//
//
// node* splitLT(const node* headPtr, int splittingValue)
// Precondition: headPtr points to a linked list of items that can be compared with a < operator
// Postcondition: Returns pointer to a linked list which contains
// all values from a previous linked list that are less than
// the splitting value. It does not delete the original list.
//
// node* splitGTE(const node* headPtr, int splittingValue)
// Precondition: headPtr points to linked list of items that can be compared with >= operator
// Postcondition: Returns pointer to a linked list which contains
// all values from a previous linked list that are greater than
// or equal to the splitting value. It does not delete the original list.
//
//
// void printList(const node* headPtr)
// Precondition: headPtr points to a list that can send its items to cout
// Postcondition: Prints an entire list, with a newline after each value
//
// 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.
//
// DYNAMIC MEMORY usage by the toolkit:
// If there is insufficient dynamic memory, then the following functions throw
// bad_alloc: the constructor, list_head_insert, list_insert, list_copy,
// list_piece.
#ifndef MAIN_SAVITCH_NODE1_H
#define MAIN_SAVITCH_NODE1_H
#include <cstdlib> // Provides size_t and NULL
namespace main_savitch_5
{
class node
{
public:
// TYPEDEF
typedef double value_type;
// CONSTRUCTOR
node(
const value_type& init_data = value_type( ),
node* init_link = NULL
)
{ data_field = init_data; link_field = init_link; }
// Member functions to set the data and link fields:
void set_data(const value_type& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }
// Constant member function to retrieve the current data:
value_type data( ) const { return data_field; }
// Two slightly different member functions to retreive
// the current link:
const node* link( ) const { return link_field; }
node* link( ) { return link_field; }
private:
value_type data_field;
node* link_field;
};
// FUNCTIONS for the linked list toolkit
std::size_t list_length(const node* head_ptr);
void list_head_insert(node*& head_ptr, const node::value_type& entry);
void list_insert(node* previous_ptr, const node::value_type& entry);
node* list_search(node* head_ptr, const node::value_type& target);
const node* list_search
(const node* head_ptr, const node::value_type& target);
node* list_locate(node* head_ptr, std::size_t position);
const node* list_locate(const node* head_ptr, std::size_t position);
void list_head_remove(node*& head_ptr);
void list_remove(node* previous_ptr);
void list_clear(node*& head_ptr);
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);
// newly created functions for assignment
node* splitLT(const node*, int splittingValue);
node* splitGTE(const node*, int splittingValue);
void printList(const node*);
void sort_list(node*& head_ptr);
}
#endif
node1.cpp
// FILE: node1.cpp
// IMPLEMENTS: The functions of the node class and the
// linked list toolkit (see node1.h for documentation).
// INVARIANT for the node class:
// The data of a node is stored in data_field, and the link in link_field.
#include "node1.h"
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t
#include <iostream>
using namespace std;
namespace main_savitch_5
{
size_t list_length(const node* head_ptr)
// Library facilities used: cstdlib
{
const node *cursor;
size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
++answer;
return answer;
}
void list_head_insert(node*& head_ptr, const node::value_type& entry)
{
head_ptr = new node(entry, head_ptr);
}
void list_insert(node* previous_ptr, const node::value_type& entry)
{
node *insert_ptr;
insert_ptr = new node(entry, previous_ptr->link( ));
previous_ptr->set_link(insert_ptr);
}
node* list_search(node* head_ptr, const node::value_type& target)
// Library facilities used: cstdlib
{
node *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
if (target == cursor->data( ))
return cursor;
return NULL;
}
const node* list_search(const node* head_ptr, const node::value_type& target)
// Library facilities used: cstdlib
{
const node *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
if (target == cursor->data( ))
return cursor;
return NULL;
}
node* list_locate(node* head_ptr, size_t position)
// Library facilities used: cassert, cstdlib
{
node *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link( );
return cursor;
}
const node* list_locate(const node* head_ptr, size_t position)
// Library facilities used: cassert, cstdlib
{
const node *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link( );
return cursor;
}
void list_head_remove(node*& head_ptr)
{
node *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link( );
delete remove_ptr;
}
void list_remove(node* previous_ptr)
{
node *remove_ptr;
remove_ptr = previous_ptr->link( );
previous_ptr->set_link( remove_ptr->link( ) );
delete remove_ptr;
}
void list_clear(node*& head_ptr)
// Library facilities used: cstdlib
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
// Library facilities used: cstdlib
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list.
if (source_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it.
list_head_insert(head_ptr, source_ptr->data( ));
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list.
source_ptr = source_ptr->link( );
while (source_ptr != NULL)
{
list_insert(tail_ptr, source_ptr->data( ));
tail_ptr = tail_ptr->link( );
source_ptr = source_ptr->link( );
}
}
// newly created functions for assignment ******************************
// Precondition: headPtr points to a linked list of items that can be compared with a < operator
// Postcondition: Returns pointer to a linked list which contains
// all values from a previous linked list that are less than
// the splitting value. It does not delete the original list.
node* splitLT(const node* headPtr, int splittingValue)
{
node* newLTList = NULL;
const node* cursor;
for (cursor = headPtr; cursor != NULL; cursor = cursor->link())
{
if (cursor->data() < splittingValue)
{
list_head_insert(newLTList, cursor->data());
}
}
return newLTList;
}
// Precondition: headPtr points to linked list of items that can be compared with >= operator
// Postcondition: Returns pointer to a linked list which contains
// all values from a previous linked list that are greater than
// or equal to the splitting value. It does not delete the original list.
node* splitGTE(const node* headPtr, int splittingValue)
{
node* newGTEList = NULL;
const node* cursor;
for (cursor = headPtr; cursor != NULL; cursor = cursor->link())
{
if (cursor->data() >= splittingValue)
{
list_head_insert(newGTEList, cursor->data());
}
}
return newGTEList;
}
// Precondition: headPtr points to a list that can send its items to cout
// Postcondition: Prints an entire list, with a newline after each value
void printList(const node* headPtr)
{
const node* cursor;
for (cursor = headPtr; cursor != NULL; cursor = cursor->link())
{
std::cout << cursor->data() << std::endl;
}
}
// Precondition: head_ptr is a head pointer of a linked list of INTEGERS, and these items
// can be compared with a less-than operator. (Assignment's specifications do not
// match precondition written for function, defaulting to assignment's specifications
// to create a function that handles lists of integers).
// 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.
void sort_list(node*& head_ptr)
{
/* Pseudocode for selection sort added for benefit of reviewing professor/student/etc.
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.
}
*/
int max_value;
node* max_previous = NULL;
node* max_node = NULL;
node* previous_ptr = NULL;
node* new_list = NULL;
while (head_ptr != NULL)
{
max_value = 0;
previous_ptr = head_ptr;
for (node* cursor = head_ptr; cursor != NULL; previous_ptr = cursor, cursor = cursor->link())
{
if (max_value < cursor->data())
{
max_value = cursor->data();
max_node = cursor;
max_previous = previous_ptr;
}
}
if (max_node == head_ptr)
{
list_head_remove(head_ptr);
}
else
{
max_previous->set_link(max_node->link());
delete max_node;
}
list_head_insert(new_list, max_value);
}
head_ptr = new_list; // original argument list pointer now points to sorted list
}
}
Sample output
LIST TEST PROGRAM
~~~~~~~~~~~~~~~~~
Creating a list with values 3 6 28 12 15...
Printing the list (testing printList(const node*) function)...
3
6
28
12
15
Now creating a list with all values less than 12 from the original...
Printing the new list (testing splitLT(const node*, int splittingValue)...
6
3
Now creating a list with all values greater than or equal 12 from original...
Printing the new list (testing splitGTE(const node*, int splittingValue)...
15
12
28
This section will test the sort_list function...
Sorting and then printing list1...
3
6
12
15
28
Sorting and printing list2...
3
6
Sorting and printing list3...
12
15
28
THANK YOU!
Press any key to continue . . .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.