The goal of this assignment is to reinforce linked lists in C++. Specifically, t

Question

The goal of this assignment is to reinforce linked lists in C++. Specifically, the assignment is to do programming projects 2, 6, and 7 on page 287 of text. Put the required function in "main" and use node1.h and node1.cpp.
node1.cpp #include "node1.h" #include <cassert> // Provides assert #include <cstdlib> // Provides NULL and size_t
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(); } } #include "node1.h" #include <cassert> // Provides assert #include <cstdlib> // Provides NULL and size_t
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(); } }

Node1.h // 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. // // 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); }
#endif // 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. // // 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); }
#endif
Programming project 2,6,7 (2)



(6)



(7)

Write a function that takes a linked list of items and deletes all repetitions from the list. In your implementation, assume that items can be compared for equality using

Explanation / Answer

/*Original list is left as it is and two new lists big and small are ceated
where as big list contaons elements more than or equal to n and small points
to a list containing numbers smaller than n */

void split(node *&list, node::value_type n){

     node *p, *big, *small, *q;
     p = list;
     big = NULL;
     small = NULL;
     while (p!= NULL){
        if (p->data < n){
           if (small == NULL){
              list_head_insert(small,n);
           }
           else {
              q = small;
              while (q->link != NULL)
                    q = q->link
              list_insert(q,n)
           }
        }
        else{
           if (big == NULL){
              list_head_insert(big,n);
           }
           else {
              q = big;
              while (q->link != NULL)
                    q = q->link
              list_insert(q,n)
           }
        }
        p = p->link;  
     }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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