Take these programs and change the code in simplepoly.cpp so that it is used by a linked list. You may only change the simplepoly.cpp file and the list_insert_sorted function in the node.cpp file. Basically, take all the files, build a project using them all. The project must be implemented using linked lists by editing the simplepoly.cpp file and the one function. Most of the things that need changed are bolded and say DO. Some other editing might be required as well.

Sample Output. Red is the input by user.

simplepoly.h file:

node.h file: // 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.

#ifndef MAIN_SAVITCH_NODE1_H #define MAIN_SAVITCH_NODE1_H #include // Provides size_t and NULL

namespace main_savitch_5 { struct term { int coeff; unsigned int exp; term () {}; // only purpose is to facilitate array declaration. term (int c, unsigned int e) : coeff(c), exp(e) {}; char sign () const {return ((coeff (const term & t2) const {return (exp > t2.exp);}; bool operator

class node { public: typedef term 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; }

// Const member function retrieves the current data: value_type data( ) const { return data_field; }

// Two slightly different member functions to retrieve the current link const node* link( ) const { return link_field; } node* link( ) { return link_field; }

private: value_type data_field; node* link_field; };

//toolkit functions 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, size_t position); const node* list_locate(const node* head_ptr, 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_insert_sorted(node*& head_ptr, const node::value_type& entry); }

#endif

FILE: node.cpp

simplepoly.cpp

This file needs to be adjusted to use a linked list

#include #include #include #include "simplepoly.h"

using namespace std;

const unsigned int SimplePoly::SIZEINCR = 5; // SIZEINCR is the size increment used in expanding the dynamic arrays as needed.

SimplePoly::SimplePoly() {// Post: A basic "zero" polynomial object is created // with zero terms. Variable is assumed to be x

//DO };

void SimplePoly::copy (const SimplePoly & p) { //p is a polynomial. //p is DEEP-COPIED into the implicit parameter. // *DO

};

SimplePoly::SimplePoly (const SimplePoly & p) { copy (p); };

void SimplePoly::free (void) { // *DO };

SimplePoly::~SimplePoly (void) { free (); };

SimplePoly & SimplePoly::operator= (const SimplePoly & p) //DEEP COPY SEMANTICS {

if (this != &p) { free (); copy (p); }; return (*this); };

void SimplePoly::read () { // Post: A new value is read into the implicit parameter polynomial, per // instructions as given out first. If needed, the old value is destroyed.

SimplePoly temp; int coeff; int exp; cout > temp.variable; do { cin >> coeff; if (coeff) { cin >> exp; if (exp >= 0) temp.InsertTermSorted() //DO; } else while (cin && (cin.peek() != ' ')) cin. ignore(); } while (coeff && (exp >= 0)); *this = temp; };

void SimplePoly::write() const { //The implicit parameter is a valid polynomial (possibly zero). //The polynomial represented by the implicit parameter is // printed out on the standard output. The variable is used as stored. // *DO if (LargestExp == -1 || terms[LargestExp].coeff == 0) { cout

for (int i = LargestExp; i >= 0; --i) { if (terms[i].coeff == 0) { continue; }

if (i != LargestExp && terms[i].sign() == '+') { cout

cout

if (i == 0) {

} else if (i == 1) { cout

cout

cout

SimplePoly SimplePoly::plus (const SimplePoly & right) const { // Pre: The implicit parameter and the parameter right are valid polynomials. // Post: The sum of the two parameters is returned by plus.

// *DO };

SimplePoly SimplePoly::minus (const SimplePoly & right) const { // *DO };

float SimplePoly::evaluate (float value) const { // Pre: The implicit parameter is a valid polynomial. // Post: The value of the polynomial with the value substituted for the variable is returned.

// *DO };

What is this better version of a polynomial? The basic concept is STILL the same: A polynomial is the sum of several terms, where each term comprises an exponent, along with its coefficient. Our first version of polynomials (in Project 2) was implemented as a dynamic array of terms, which simply contained JUST the coefficients. In the new Project 3 version, we will implement it as a linked list of terms, which now contain BOTH the coefficient and the exponent, with the list kept sorted in decreasing order of exponents, this data structure just DOES NOT STORE any term with a zero coefficient at all! Note that you will have to write new code for any member functions of simplepoly that directly depended previously on the dynamic array version (which will now be based on the linked list version), but not necessarily for all member functions of poly. I suggest that the copy constructor (but not copy), the assignment operator, destructor (but not free), and the read function are some methods that probably do not need to be re-coded; can you see why? The copy and free methods DO need to be recoded (sorry for the double negatives in the previous sentence). Available commands: ?: to print this menu H: to print this menu Rn: to read a value for polynomial n Pn: to print the value of polynomial n +ij k: to add polynomials i and j and store result in k ij k: to subtract polynomials j from i and store result in k En v: to evaluate polynomial n with its variable set to value v Q: to quit ro x 4 1 -3 2 2 0 0 po - 3x2 + 4x +2 r 1 x 50 -4 1 3 2 3 -1 pl 3x2 - 4x +5 + 0 1 2 p 2 7 9 #ifndef SIMPLEPOLY_H #define SIMPLEPOLY_H #include "node.h" using namespace main_savitch_5; class simplengly { public simplepolyo; simplepoly (const simplepoly &); -simplepoly 0); simplepoly & operator= (const simplepoly &); void read (); void write () const; simplepely plus (simplepoly) const; simplepely minus (simplepoly) const; float evaluate (float) const: private: node * terms; char variable; void copy (const simplepoly &); void free 0); void Insert Term Sorted (term); }; #endif // 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 Il typedef statement. // // CONSTRUCTOR for node class Il 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 off Il zero. The init link has a default value of NULL. // 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 Il the return value is node*) and a const version (where the return value Il is const node*). // EXAMPLES Il const node *c; Il c->link() activates the const version of link Il list search(C.... calls the const version of list search Il node *p; 11 p->link() activates the non-const version of link Il list search(p.... calls the non-const version of list search \/ FILE: node.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 "node.h" #include #include // Provides assert // Provides NULL and size_t 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 = ++answer; cursor->link() 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(); return cursor; } const node* list_locate(const node* head_ptr, size_t position) // Library facilities used: cassert, cstdlib { const node *cursor; size_t i; cursor = assert (0 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 rce_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_insert_sorted(node*& head_ptr, const node::value_type& entry) { // TO DO if (list_length(head_ptr) { list_head_insert (head_ptr, entry); } node* cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) { if (cursor->data().exp > entry.exp && entry.exp > cursor->link() ->data().exp) { list_insert(cursor, entry); } } } } // simplepolydr.cpp #include "simplepoly.h" #include using namespace std; const unsigned int MAX = 50; void main() { // Pre: None. // Post: Give the user a menu of choices. Based on what command the user inputs, take the appropriate action as guaranteed by the menu. Input is accepted in a case-insensitive manner! simplepoly P[MAX]; char command; unsigned int i, j, k; float value; void printmenu (); printmenu(); do { cin >> command; switch (command) { case '?': case 'H': case 'h': printmenu(); break; case 'R': case 'r': cin >> i; P[i].read(); break; case 'P': case 'p': cin >> i; P[i].write(); break; case '+': cin >> i j>> k; P[k] = p[i].plus(P[i]); break; case '.': cin >> i >> j >> K; P[k] = p[i].minus (P[j]); break; case 'E': case 'e': cin >> i >> value; cout using namespace std; const unsigned int MAX = 50; void main() { // Pre: None. // Post: Give the user a menu of choices. Based on what command the user inputs, take the appropriate action as guaranteed by the menu. Input is accepted in a case-insensitive manner! simplepoly P[MAX]; char command; unsigned int i, j, k; float value; void printmenu (); printmenu(); do { cin >> command; switch (command) { case '?': case 'H': case 'h': printmenu(); break; case 'R': case 'r': cin >> i; P[i].read(); break; case 'P': case 'p': cin >> i; P[i].write(); break; case '+': cin >> i j>> k; P[k] = p[i].plus(P[i]); break; case '.': cin >> i >> j >> K; P[k] = p[i].minus (P[j]); break; case 'E': case 'e': cin >> i >> value; cout link() activates the const version of link Il list search(C.... calls the const version of list search Il node *p; 11 p->link() activates the non-const version of link Il list search(p.... calls the non-const version of list search \/ FILE: node.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 "node.h" #include #include // Provides assert // Provides NULL and size_t 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 = ++answer; cursor->link() 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(); return cursor; } const node* list_locate(const node* head_ptr, size_t position) // Library facilities used: cassert, cstdlib { const node *cursor; size_t i; cursor = assert (0 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 rce_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_insert_sorted(node*& head_ptr, const node::value_type& entry) { // TO DO if (list_length(head_ptr) { list_head_insert (head_ptr, entry); } node* cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) { if (cursor->data().exp > entry.exp && entry.exp > cursor->link() ->data().exp) { list_insert(cursor, entry); } } } } // simplepolydr.cpp #include "simplepoly.h" #include using namespace std; const unsigned int MAX = 50; void main() { // Pre: None. // Post: Give the user a menu of choices. Based on what command the user inputs, take the appropriate action as guaranteed by the menu. Input is accepted in a case-insensitive manner! simplepoly P[MAX]; char command; unsigned int i, j, k; float value; void printmenu (); printmenu(); do { cin >> command; switch (command) { case '?': case 'H': case 'h': printmenu(); break; case 'R': case 'r': cin >> i; P[i].read(); break; case 'P': case 'p': cin >> i; P[i].write(); break; case '+': cin >> i j>> k; P[k] = p[i].plus(P[i]); break; case '.': cin >> i >> j >> K; P[k] = p[i].minus (P[j]); break; case 'E': case 'e': cin >> i >> value; cout using namespace std; const unsigned int MAX = 50; void main() { // Pre: None. // Post: Give the user a menu of choices. Based on what command the user inputs, take the appropriate action as guaranteed by the menu. Input is accepted in a case-insensitive manner! simplepoly P[MAX]; char command; unsigned int i, j, k; float value; void printmenu (); printmenu(); do { cin >> command; switch (command) { case '?': case 'H': case 'h': printmenu(); break; case 'R': case 'r': cin >> i; P[i].read(); break; case 'P': case 'p': cin >> i; P[i].write(); break; case '+': cin >> i j>> k; P[k] = p[i].plus(P[i]); break; case '.': cin >> i >> j >> K; P[k] = p[i].minus (P[j]); break; case 'E': case 'e': cin >> i >> value; cout