Task: Use linked lists to represent two polynomials. Each polynomial will be an

Question

Task: Use linked lists to represent two polynomials. Each polynomial will be an object of the Polynomial class. Each node in the linked list will represent a term of the polynomial, so data members of the nodes will include coefficient and exponent.

Processing: The program should accept appropriate values (i.e., coefficient and exponent values) from the user to populate two polynomials. Simple data checking should verify that the integer exponents are non-negative and that coefficients are not zero. Polynomials may have varying numbers of terms. The terms should be stored in the linked list in decreasing order of their exponents.

For example, valid polynomials might be:

3x^7-1.5x^4+3 (stored as 3 nodes)

7.1x^2-6x (stored as 2 nodes)

12    (stored as 1 node)

The program will perform three basic operations on the polynomials:

add the two original polynomials together; output the sum

subtract one of the original polynomials from the other one; output the difference

perform monomial multiplication on one of the original polynomials (i.e., multiply each polynomial term by a given monomial term, not necessarily a scalar); output the monomial and the result

Note: do not change the original two polynomials during the addition, subtraction or multiplication operations. Include appropriate functions in the class (constructors, etc.) to produce an effective object-oriented program.

Input: Be sure the program is flexible enough that polynomial terms may be supplied by the user out of proper order, but still be stored in proper order.

Output: Test program should allow the user to input the two polynomials and the monomial multiplier. Then output the following:

each of the two original polynomials

the sum of the polynomials

the difference (first polynomial minus the second)

another difference (second polynomial minus the first)

the result for each of the two polynomials being multiplied by a (different) monomial

Make sure your program in program is well documented both internally and externally.

Explanation / Answer

#include<bits/stdc++.h>
using namespace std;

// Node structure containing power and coefficient of variable
struct Node
{
    int coeff;
    int pow;
    struct Node *next;
};
           
// Function to create new node
void create_node(int x, int y, struct Node **temp)
{
    struct Node *r, *z;
    z = *temp;
    if(z == NULL)
    {
        r =(struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        *temp = r;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
    else
    {
        r->coeff = x;
        r->pow = y;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
}

// Function Adding two polynomial numbers
void polyadd(struct Node *poly1, struct Node *poly2, struct Node *poly)
{
while(poly1->next && poly2->next)
    {
        // If power of 1st polynomial is greater then 2nd, then store 1st as it is
        // and move its pointer
        if(poly1->pow > poly2->pow)
        {
            poly->pow = poly1->pow;
            poly->coeff = poly1->coeff;
            poly1 = poly1->next;
        }
       
        // If power of 2nd polynomial is greater then 1st, then store 2nd as it is
        // and move its pointer
        else if(poly1->pow < poly2->pow)
        {
            poly->pow = poly2->pow;
            poly->coeff = poly2->coeff;
            poly2 = poly2->next;
        }
       
        // If power of both polynomial numbers is same then add their coefficients
        else
        {
            poly->pow = poly1->pow;
            poly->coeff = poly1->coeff+poly2->coeff;
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
       
        // Dynamically create new node
        poly->next = (struct Node *)malloc(sizeof(struct Node));
        poly = poly->next;
        poly->next = NULL;
    }
while(poly1->next || poly2->next)
    {
        if(poly1->next)
        {
            poly->pow = poly1->pow;
            poly->coeff = poly1->coeff;
            poly1 = poly1->next;
        }
        if(poly2->next)
        {
            poly->pow = poly2->pow;
            poly->coeff = poly2->coeff;
            poly2 = poly2->next;
        }
        poly->next = (struct Node *)malloc(sizeof(struct Node));
        poly = poly->next;
        poly->next = NULL;
    }
}

// Display Linked list
void show(struct Node *node)
{
while(node->next != NULL)
    {
    printf("%dx^%d", node->coeff, node->pow);
    node = node->next;
    if(node->next != NULL)
        printf(" + ");
    }
}

// Driver program
int main()
{
    struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
   
    // Create first list of 5x^2 + 4x^1 + 2x^0
    create_node(5,2,&poly1);
    create_node(4,1,&poly1);
    create_node(2,0,&poly1);
   
    // Create second list of 5x^1 + 5x^0
    create_node(5,1,&poly2);
    create_node(5,0,&poly2);
   
    printf("1st Number: ");
    show(poly1);
   
    printf(" 2nd Number: ");
    show(poly2);
   
    poly = (struct Node *)malloc(sizeof(struct Node));
   
    // Function add two polynomial numbers
    polyadd(poly1, poly2, poly);
   
    // Display resultant List
    printf(" Added polynomial: ");
    show(poly);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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