Polynomial multiplication using linked list

Polynomial Multiplication

Suppose we have two polynomials:

  • P(x): represented by a linked list poly1

  • Q(x): represented by a linked list poly2

Each node contains:

  • coefficient

  • exponent

  • pointer to next node

Algorithm Steps:

Step 1: Start with two polynomials poly1 and poly2.
Create a new polynomial list result and set it as empty (NULL).

Step 2:
For each term t1 in poly1:

  • For each term t2 in poly2:

    1. Multiply the coefficients: coeff = t1.coeff * t2.coeff

    2. Add the exponents: exp = t1.exp + t2.exp

    3. Insert this term (coeff, exp) into result:

      • If there is already a term with the same exponent in result, add the coefficients.

      • Otherwise, insert a new node.

Step 3:
After multiplying all terms, rearrage terms in the order(if needed).

Step 4:
Display the result polynomial.

 Important Notes:

  • Insertion in result must check if same exponent exists → if yes, add coefficients.

  • If not, insert new node.

  • This is called term-by-term multiplication.

🔵 Multiplication Example:

  • First Polynomial: 3x^2 + 5x^1

  • Second Polynomial: 2x^1 + 4x^0

Multiply each term:

Term from Poly1    Term from Poly2    Result Term
3x²        2x¹        6x³
3x²        4x⁰    12x²
5x¹    2x¹    10x²
5x¹    4x⁰        20x¹

Now combine like terms:

  • 6x^3

  • 12x^2 + 10x^2 = 22x^2

  • 20x^1

🔵 Final Output:

Resultant Polynomial after Multiplication: 6x^3 + 22x^2 + 20x^1

C Program - Polynomial Multiplication using Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int coeff;
    int exp;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int coeff, int exp) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->coeff = coeff;
    newNode->exp = exp;
    newNode->next = NULL;
    return newNode;
}

// Function to insert at the end
struct Node* insertEnd(struct Node* head, int coeff, int exp) {
    struct Node* newNode = createNode(coeff, exp);

    if (head == NULL) {
        head = newNode;
    } else {
        struct Node* temp = head;
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = newNode;
    }
    return head;
}

// Function to display a polynomial
void display(struct Node* head) {
    if (head == NULL) {
        printf("NULL\n");
        return;
    }
    while (head != NULL) {
        printf("%dx^%d", head->coeff, head->exp);
        head = head->next;
        if (head != NULL && head->coeff >= 0)
            printf(" + ");
    }
    printf("\n");
}

// Function to search and add coefficient if exponent matches
struct Node* addTerm(struct Node* result, int coeff, int exp) {
    struct Node* temp = result;
    struct Node* prev = NULL;
    while (temp != NULL) {
        if (temp->exp == exp) {
            temp->coeff += coeff;
            return result;
        }
        prev = temp;
        temp = temp->next;
    }
    // No matching term found, insert at end
    struct Node* newNode = createNode(coeff, exp);
    if (prev == NULL)
        result = newNode;
    else
        prev->next = newNode;
    return result;
}

// Function to multiply two polynomials
struct Node* multiply(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;
    struct Node* ptr1 = poly1;
    struct Node* ptr2 = poly2;

    while (ptr1 != NULL) {
        ptr2 = poly2;
        while (ptr2 != NULL) {
            int coeff = ptr1->coeff * ptr2->coeff;
            int exp = ptr1->exp + ptr2->exp;
            result = addTerm(result, coeff, exp);
            ptr2 = ptr2->next;
        }
        ptr1 = ptr1->next;
    }
    return result;
}

// Main function
int main() {
    struct Node* poly1 = NULL;
    struct Node* poly2 = NULL;
    struct Node* result = NULL;
    int n, coeff, exp, i;

    printf("Enter number of terms in first polynomial: ");
    scanf("%d", &n);
    printf("Enter coeff and exp for each term:\n");
    for (i = 0; i < n; i++) {
        scanf("%d%d", &coeff, &exp);
        poly1 = insertEnd(poly1, coeff, exp);
    }

    printf("Enter number of terms in second polynomial: ");
    scanf("%d", &n);
    printf("Enter coeff and exp for each term:\n");
    for (i = 0; i < n; i++) {
        scanf("%d%d", &coeff, &exp);
        poly2 = insertEnd(poly2, coeff, exp);
    }

    printf("\nFirst Polynomial: ");
    display(poly1);
    printf("Second Polynomial: ");
    display(poly2);

    result = multiply(poly1, poly2);

    printf("\nResultant Polynomial after Multiplication: ");
    display(result);

    return 0;
}
Output
Enter number of terms in first polynomial: 3
Enter coeff and exp for each term:
2 2
3 1
2 0
Enter number of terms in second polynomial: 2
Enter coeff and exp for each term:
4 2
5 1

First Polynomial: 2x^2 + 3x^1 + 2x^0
Second Polynomial: 4x^2 + 5x^1

Resultant Polynomial after Multiplication: 8x^4 + 22x^3 + 23x^2 + 10x^1

C program to multiply polynomials and rearranging terms
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int coeff;
    int exp;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int coeff, int exp) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->coeff = coeff;
    newNode->exp = exp;
    newNode->next = NULL;
    return newNode;
}

// Function to insert at the end
struct Node* insertEnd(struct Node* head, int coeff, int exp) {
    struct Node* newNode = createNode(coeff, exp);

    if (head == NULL) {
        head = newNode;
    } else {
        struct Node* temp = head;
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = newNode;
    }
    return head;
}

// Function to display a polynomial
void display(struct Node* head) {
    if (head == NULL) {
        printf("NULL\n");
        return;
    }
    while (head != NULL) {
        printf("%dx^%d", head->coeff, head->exp);
        head = head->next;
        if (head != NULL && head->coeff >= 0)
            printf(" + ");
    }
    printf("\n");
}

// Function to search and add coefficient if exponent matches
struct Node* addTerm(struct Node* result, int coeff, int exp) {
    struct Node* temp = result;
    struct Node* prev = NULL;
    while (temp != NULL) {
        if (temp->exp == exp) {
            temp->coeff += coeff;
            return result;
        }
        prev = temp;
        temp = temp->next;
    }
    // No matching term found, insert at end
    struct Node* newNode = createNode(coeff, exp);
    if (prev == NULL)
        result = newNode;
    else
        prev->next = newNode;
    return result;
}

// Function to multiply two polynomials
struct Node* multiply(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;
    struct Node* ptr1 = poly1;
    struct Node* ptr2;

    while (ptr1 != NULL) {
        ptr2 = poly2;
        while (ptr2 != NULL) {
            int coeff = ptr1->coeff * ptr2->coeff;
            int exp = ptr1->exp + ptr2->exp;
            result = addTerm(result, coeff, exp);
            ptr2 = ptr2->next;
        }
        ptr1 = ptr1->next;
    }
    return result;
}

// Function to sort polynomial in descending order of exponents
struct Node* sortDescending(struct Node* head) {
    if (head == NULL || head->next == NULL)
        return head;

    struct Node* i, *j;
    for (i = head; i->next != NULL; i = i->next) {
        for (j = i->next; j != NULL; j = j->next) {
            if (i->exp < j->exp) {
                // Swap coeff
                int tempCoeff = i->coeff;
                i->coeff = j->coeff;
                j->coeff = tempCoeff;

                // Swap exp
                int tempExp = i->exp;
                i->exp = j->exp;
                j->exp = tempExp;
            }
        }
    }
    return head;
}

// Main function
int main() {
    struct Node* poly1 = NULL;
    struct Node* poly2 = NULL;
    struct Node* result = NULL;
    int n, m, coeff, exp, i;

    printf("Enter number of terms in first polynomial: ");
    scanf("%d", &n);
    printf("Enter coeff and exp for each term:\n");
    for (i = 0; i < n; i++) {
        scanf("%d%d", &coeff, &exp);
        poly1 = insertEnd(poly1, coeff, exp);
    }

    printf("Enter number of terms in second polynomial: ");
    scanf("%d", &m);
    printf("Enter coeff and exp for each term:\n");
    for (i = 0; i < m; i++) {
        scanf("%d%d", &coeff, &exp);
        poly2 = insertEnd(poly2, coeff, exp);
    }

    printf("\nFirst Polynomial: ");
    display(poly1);
    printf("Second Polynomial: ");
    display(poly2);

    result = multiply(poly1, poly2);
    result = sortDescending(result);  // Sort the result polynomial by exponent descending

    printf("\nResultant Polynomial after Multiplication: ");
    display(result);

    return 0;
}
Enter number of terms in first polynomial: 3
Enter coeff and exp for each term:
3 2
2 1
1 0
Enter number of terms in second polynomial: 3
Enter coeff and exp for each term:
5 3
2 1
2 0

First Polynomial: 3x^2 + 2x^1 + 1x^0
Second Polynomial: 5x^3 + 2x^1 + 2x^0

Resultant Polynomial after Multiplication: 15x^5 + 10x^4 + 11x^3 + 10x^2 + 6x^1 + 2x^0

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more