Write the header and implementation file as a template. Also create a selection

Question

Write the header and implementation file as a template. Also create a selection sort from smallest to largest, it will remove 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.

//Header File

#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 removeDuplicates( node* head_ptr);
   void sort_list(node*&head_ptr);
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);

#endif

//CPP File

#include "node.h"

#include <cassert> // Provides assert

#include <cstdlib> // Provides NULL and size_t
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( );
   }
   }

Explanation / Answer

// FILE: .cpp file #include "node1.h" #include // Provides assert #include // Provides NULL and size_t 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 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( ); } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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