Polynomial representation using Linked Lists- Evaluation -Addition and Multiplication

Representing a polynomial using a linked list is a common approach in computer science and mathematics. Each node in the linked list corresponds to a term in the polynomial, with the coefficients and exponents stored as data in each node.

Here is the node that is having a coefficient, an exponent, and a pointer (next) to the next node. Let us define the structure for this.

struct Node {
int coefficient;
int exponent;
struct Node *next;
}
This structure has a coefficient and exponent of type int and a pointer to the next node of type Node*. If the coefficient is in decimal, then you can take float also.

Example:

P(x) = 4x^3 + 9x^2 + 6^x + 7


If suppose the value of ‘x’ is 1 then,

P (x) = (4 * 1^3) + (9 * 1^2) + (6 * 1) + 7=26

The time complexity for adding a term (polynomial representation) and evaluating the polynomial is both O(n), where n is the number of terms in the polynomial.
The space complexity is O(n) as well, where n is the number of terms, due to the linked list structure.

C program Implementation- Polynomial Representation and Evaluation
/**********************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct Node {
    int coeff;
    int exp;
    struct Node * next;
}* poly = NULL;
void create() {
    struct Node * t, * last = NULL;
    int num, i;
    printf("Enter number of terms: ");
    scanf("%d", & num);
    printf("Enter each term with coeff and exp:\n");
    for (i = 0; i < num; i++) {
        t = (struct Node * ) malloc(sizeof(struct Node));
        scanf("%d%d", & t -> coeff, & t -> exp);
        t -> next = NULL;
        if (poly == NULL) {
            poly = last = t;
        } else {
            last -> next = t;
            last = t;
        }
    }
}
void Display(struct Node * p) {
    
    while (p!=NULL) {
        printf("%dx^%d ", p -> coeff, p -> exp);
        if(p->next!=NULL) printf("+");
        p = p -> next;
    }
    printf("\n");
}
long Eval(struct Node * p, int x) {
    long val = 0;
    while (p) {
        val += p -> coeff * pow(x, p -> exp);
        p = p -> next;
    }
    
    return val;
}
int main() {
    int x;
    create();
    Display(poly);
    
    printf("Enter value of x: ");
    scanf("%d", &x);
    
    printf("The value P(%d)=%ld\n",x, Eval(poly, x));
    return 0;
}

Polynomial Addition

To add two polynomials that are represented as a linked list, we will add the coefficients of variables with the degree.

We will traverse both the list and at any step, we will compare the degree of current nodes in both lists:
  • We will add their coefficients if their degree is the same and append them to the resultant list.
  • Otherwise, we will append the node with a greater node in the resultant list.
Algorithm
  • Create a new linked list, result to store the resultant list.
  • Traverse both lists until one of them is null.
  • If any list is null insert the remaining node of another list in the resultant list.
  • Otherwise compare the degree of both nodes, a (first list’s node) and b (second list’s node). Here three cases are possible:
    • If the degree of a and b is equal, we insert a new node in the resultant list with the coefficient equal to the sum of coefficients of a and b and the same degree.
    • If the degree of a is greater than b, we insert a new node in the resultant list with the coefficient and degree equal to that of a.
    • If the degree of b is greater than a, we insert a new node in the resultant list with the coefficient and degree equal to that of b
Time Complexity: 
O(m+n) is the time complexity for the polynomial addition using linked list in C, m and n being the size of the linked lists.

Space Complexity: 
O(m+n) is the space complexity for the polynomial addition using linked list in C, as in the worst case we need to allocate memory for each node in both lists.

C Program Implementation- Polynomial Addition using Linked List
/************************************************************************/
#include <stdio.h>
#include <stdlib.h>
struct Node {
    int coef;
    int expo;
    struct Node* next;
};
typedef struct Node Node;
void insert(Node** poly, int coef, int expo) {
    Node* temp = (Node*) malloc(sizeof(Node));
    temp->coef = coef;
    temp->expo = expo;
    temp->next = NULL;
    
    if (*poly == NULL) {
        *poly = temp;
        return;
    }
    
    Node* current = *poly;
    
    while (current->next != NULL) {
        current = current->next;
    }
    
    current->next = temp;
}
void print(Node* poly) {
    if (poly == NULL) {
        printf("0\n");
        return;
    }
    
    Node* current = poly;
    
    while (current != NULL) {
        printf("%dx^%d", current->coef, current->expo);
        if (current->next != NULL) {
            printf(" + ");
        }
        current = current->next;
    }
    
    printf("\n");
}
Node* add(Node* poly1, Node* poly2) {
    Node* result = NULL;
    
    while (poly1 != NULL && poly2 != NULL) {
        if (poly1->expo == poly2->expo) {
            insert(&result, poly1->coef + poly2->coef, poly1->expo);
            poly1 = poly1->next;
            poly2 = poly2->next;
        } else if (poly1->expo > poly2->expo) {
            insert(&result, poly1->coef, poly1->expo);
            poly1 = poly1->next;
        } else {
            insert(&result, poly2->coef, poly2->expo);
            poly2 = poly2->next;
        }
    }
    
    while (poly1 != NULL) {
        insert(&result, poly1->coef, poly1->expo);
        poly1 = poly1->next;
    }
    
    while (poly2 != NULL) {
        insert(&result, poly2->coef, poly2->expo);
        poly2 = poly2->next;
    }
    
    return result;
}
int main() {
    Node* poly1 = NULL;
    insert(&poly1, 5, 5); //5 x^5+3x^4+1x^2+1x^0
    insert(&poly1, 3, 4);
    insert(&poly1, 1, 2);
    insert(&poly1, 1, 0);
    Node* poly2 = NULL;
    insert(&poly2, 4, 4); // 4x^4+2x^2+1x^1
    insert(&poly2, 2, 2);
    insert(&poly2, 1, 1);
    printf("First polynomial: ");
    print(poly1);
    printf("Second polynomial: ");
    print(poly2);
    Node* result = add(poly1, poly2);
    printf("Result: ");    
    print(result);   // 5x^5 + 7x^4 + 3x^2 + 1x^1 + 1x^0
    return 0;
}

Multiplication
In multiplication we have to multiply first term of the  term of polynomial1 with all the terms of the polynomial2.
After multiplying each term the result can be added to a new polynomial

Algorithm: MultiplyPolynomials(poly1, poly2) 
Input: Two polynomials poly1 and poly2 represented as linked lists
Output: Resultant polynomial after multiplying poly1 and poly2

Initialize Result Polynomial:
    Create an empty linked list to represent the result polynomial. Let's call it resultPoly.

For each term term1 in poly1: 
    a. For each term term2 in poly2:
        Multiply the coefficients of term1 and term2 to get the new  coefficient.
        Add the exponents of term1 and term2 to get the new exponent.

Check for Existing Term in resultPoly:
    Traverse resultPoly to check if a term with the same exponent already exists:
        If found, update its coefficient by adding the new coefficient.
       If not found, insert a new term with the calculated coefficient and exponent at the correct position           to maintain the descending order of exponents.

Return resultPoly as the product of poly1 and poly2.

Time Complexity of polynomial multiplication using linked list : The time complexity of polynomial multiplication using linked list is O(n*m), where n is the total number of nodes in the first polynomial and m is the number of nodes in the second polynomial.

Space Complexity of polynomial multiplication using linked list: The space complexity of polynomial multiplication using linked list is O(n+m), we need to store all the multiplied values in the node.

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more