Implementation of Representing Polynomials and Adding Them Using C in Data Structures

Updated: 13/01/2024 by Computer Hope

Introduction

Polynomials are a crucial concept in mathematics and computer science, often used in solving equations, data modeling, and computational problems. This article demonstrates how to represent polynomials using a linked list in C and perform their addition. For example, consider the polynomials:

1. 6x² + 9x + 10 (coefficients: 6, 9, 10; degrees: 2, 1, 0)
2. 5x² + 7x + 10 (coefficients: 5, 7, 10; degrees: 2, 1, 0)

Adding these polynomials results in 11x² + 16x + 20.

This tutorial walks through the implementation in C, where a linked list is used to store polynomial terms, and a function is written to add two such lists.

How Polynomials Are Represented in C

Polynomials can be represented using linked lists where:

• Each node contains the coefficient and exponent of a term.
• Nodes are ordered by their exponents in decreasing order.

C Program to Represent and Add Polynomials

Below is a complete C program to implement polynomial representation and addition using linked lists:

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

struct node {
    int coef, exp;
    struct node *next;
};

struct node *s1 = NULL, *s2 = NULL, *s3 = NULL;

void append(struct node **p, int a, int b) {
    struct node *q = *p, *r;
    r = (struct node *)malloc(sizeof(struct node));
    r->coef = a;
    r->exp = b;
    r->next = NULL;

    if (*p == NULL) {
        *p = r;
        return;
    }

    if (r->exp > (*p)->exp) {
        r->next = *p;
        *p = r;
        return;
    }

    while (q->next != NULL) {
        if (q->exp == r->exp) {
            q->coef += r->coef;
            free(r);
            return;
        }
        if (q->next->exp < r->exp) {
            r->next = q->next;
            q->next = r;
            return;
        }
        q = q->next;
    }

    if (q->next == NULL && q->exp > r->exp) {
        q->next = r;
    }
}

void show(struct node *p) {
    if (p == NULL) {
        printf("No polynomial\n");
        return;
    }

    while (p != NULL) {
        printf("%dX^%d ", p->coef, p->exp);
        p = p->next;
        if (p != NULL) printf("+ ");
    }
    printf("\n");
}

void sum() {
    struct node *p = s1, *q = s2;
    while (p != NULL) {
        append(&s3, p->coef, p->exp);
        p = p->next;
    }

    while (q != NULL) {
        append(&s3, q->coef, q->exp);
        q = q->next;
    }

    printf("\nAddition of two polynomials: ");
    show(s3);
}

int main() {
    int ch, c, e;

    do {
        printf("\n1. Append to Polynomial s1");
        printf("\n2. Append to Polynomial s2");
        printf("\n3. Show Polynomial s1");
        printf("\n4. Show Polynomial s2");
        printf("\n5. Sum Polynomials s1 + s2");
        printf("\n0. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &ch);

        switch (ch) {
            case 1:
                printf("Enter coefficient and exponent: ");
                scanf("%d%d", &c, &e);
                append(&s1, c, e);
                break;
            case 2:
                printf("Enter coefficient and exponent: ");
                scanf("%d%d", &c, &e);
                append(&s2, c, e);
                break;
            case 3:
                show(s1);
                break;
            case 4:
                show(s2);
                break;
            case 5:
                sum();
                break;
            case 0:
                break;
            default:
                printf("Invalid choice!\n");
        }
    } while (ch != 0);

    return 0;
}

Explanation of the Program

1. Structure Definition: Each node in the linked list represents a term in the polynomial, containing a coefficient and exponent.
2. Append Function: Inserts a term into the linked list in sorted order by the exponent.
3. Display Function: Prints the polynomial in a human-readable format.
4. Sum Function: Merges two linked lists, adding terms with the same exponents.
5. Main Function: Provides a menu-driven interface to input, display, and add polynomials.

Conclusion

This program showcases how linked lists can be used to efficiently represent and manipulate polynomials. The addition operation is performed by combining like terms, ensuring a structured result. By implementing this, you gain insights into both data structure concepts and practical problem-solving.

Want to explore more about polynomials and data structures? Share your thoughts or reach out for further assistance!