Adding of polynomials is a very common operation in mathematics and other science subjects. Creating a program for adding of polynomials is quite tricky. If you create a program for this common problem of mathematics, selecting the right data type to store polynomials is the most important aspect of it. The data types possible to store the array are string or array.
Using string or array to declare and store polynomials poses same limitations as that using an array or a string for storing and manipulating data. The best option for storing polynomials is a linear linked list to store terms of the polynomials and perform its operations like addition, subtraction or multiplication.
Storing Polynomial in a Linked List
The linear linked list is defined as collection of nodes having a data part (information) and link part (pointer storing address of next node). In case of the node of linked list storing a polynomial it is defined with three parts-
- COEFF to store Coefficient part of a term of a polynomial
- EXP to store Exponent part of a term of a polynomial
- LINK to store address or location of the next term of a polynomial
The POLY pointer is used for storing the address of first term of the polynomial (Just like START pointer in linear linked list). A polynomial can be created by using the insertion operation of a linear linked list.
Adding of Polynomials stored as Linear Linked Lists
The basic process of adding of polynomials involves using two pointers that keep track of corresponding terms of two polynomials. These corresponding terms are evaluated in this way-
- If the corresponding terms have same EXP, the coefficients are added and new node is created with the added coefficients and EXP. If the two coefficients cancel each other, then no node is created for this EXP. Both pointers are updated to address on next node.
- If EXP from first polynomial is larger than the corresponding term from the second polynomial, the term from the first polynomial is added as it is. The pointer of the first polynomial is updated and moved to the next term.
- If EXP from second polynomial is larger than the corresponding term from the first polynomial, the term from the second polynomial is added as it is. The pointer of the second polynomial is updated and moved to the next term.
- If one of the polynomials is exhausted by adding the coefficients or adding directly (following 1, 2 or 3), the remaining terms of the other polynomial are moved as it to the final polynomial.
Algorithm -Addition of Polynomials
Algorithm AddPoly(Poly1, Poly2, Poly3) 1. While poly1 and pol2 are not NULL, repeat step 2. 2. if EXP(poly1)=EXP(Poly2) then If COEFF(poly1)+COEFF(poly2)<>0 Create a node with COEFF(poly1)+COEFF(poly2), EXP(poly1) and add it to the end of poly3 Poly1=LINK(poly1) Poly2=LINK9poly2) Else If EXP(poly1)>EXP(Poly2) then Create a node with COEFF(poly1, EXP(poly1) and add it to the end of poly3 Poly1=LINK(poly1) Else Create a node with COEFF(poly2), EXP(poly2) and add it to the end of poly3 Poly2=LINK(poly2) 3. [Copy the remaining terms from the non empty polynomial into the poly3 polynomial] If poly1<>NULL then While poly1<>NULL Create a node with COEFF(poly1, EXP(poly1) and add it to the end of poly3 Poly1=LINK(poly1) Else While poly2<>NULL Create a node with COEFF(poly2), EXP(poly2) and add it to the end of poly3 Poly2=LINK(poly2)