Polynomial Representation

One of the problems that a linked list can deal with is manipulation of symbolic polynomials. By symbolic, we mean that a polynomial is viewed as a list of coefficients and exponents. For example, the polynomial
3×2+2x+4,
can be viewed as list of the following pairs
(3,2),(2,1),(4,0)
Therefore, we can use a linked list in which each node will have three fields, as shown in following Figure.

A polynomial 10×4 + 5×2 + 1 can be represented as shown here:

Polynomial representation.

# include <stdio.h>
# include <stdlib.h>
struct pnode {
	int exp;
	double coeff;
	struct pnode *link;
};

struct pnode *insert(struct pnode *, int, double);
void printlist(struct pnode *);
struct pnode *polyadd(struct pnode *, struct pnode *);
struct pnode *sortlist(struct pnode *);

struct pnode *insert(struct pnode *p, int e, double c) {
	struct pnode *temp;
	if (p == NULL) {
		p = (struct pnode *) malloc(sizeof(struct pnode));
		if (p == NULL) {
			printf("Error\n");
			exit(0);
		}
		p->exp = e;
		p->coeff = c;
		p->link = NULL;
	} else {
		temp = p;
		while (temp->link != NULL)
			temp = temp->link;
		temp->link = (struct pnode *) malloc(sizeof(struct pnode));
		if (temp->link == NULL) {
			printf("Error\n");
			exit(0);
		}
		temp = temp->link;
		temp->exp = e;
		temp->coeff = c;
		temp->link = NULL;
	}
	return (p);
}

/* a function to sort a list */
struct pnode *sortlist(struct pnode *p) {
	struct pnode *temp1, *temp2, *max, *prev, *q;
	q = NULL;
	while (p != NULL) {
		prev = NULL;
		max = temp1 = p;
		temp2 = p->link;
		while (temp2 != NULL) {
			if (max->exp < temp2->exp) {
				max = temp2;
				prev = temp1;
			}
			temp1 = temp2;
			temp2 = temp2->link;
		}
		if (prev == NULL)
			p = max->link;
		else
			prev->link = max->link;
		max->link = NULL;
		if (q == NULL)
			q = max; /* moves the node with highest data value in the list
			 pointed to by p to the list
			 pointed to by q as a first node*/
		else {
			temp1 = q;
			/* traverses the list pointed to by q to get pointer to its
			 last node */
			while (temp1->link != NULL)
				temp1 = temp1->link;
			temp1->link = max; /* moves the node with highest data value
			 in the list pointed to
			 by p to the list pointed to by q at the end of list pointed by
			 q*/

		}
	}
	return (q);
}
/* A function to add two polynomials */
struct pnode *polyadd(struct pnode *p, struct pnode *q) {
	struct pnode *r = NULL;
	int e;
	double c;
	while ((p != NULL) && (q != NULL)) {
		if (p->exp > q->exp) {
			r = insert(r, p->exp, p->coeff);
			p = p->link;
		} else if (p->exp < q->exp) {
			r = insert(r, q->exp, q->coeff);
			q = q->link;
		} else {
			c = p->coeff + q->coeff;
			e = q->exp;
			r = insert(r, e, c);
			p = p->link;
			q = q->link;
		}
		while (p != NULL) {
			r = insert(r, p->exp, p->coeff);
			p = p->link;
		}
		while (q != NULL) {
			r = insert(r, q->exp, q->coeff);
			q = q->link;
		}
		return (r);
	}
}

void printlist(struct pnode *p) {
	printf("The polynomial is\n");
	while (p != NULL) {
		printf("%d %lf\t", p->exp, p->coeff);
		p = p->link;
	}
}
int main() {
	int e;
	int n, i;
	double c;
	struct pnode *poly1 = NULL;
	struct pnode *poly2 = NULL;
	struct pnode *result;
	printf("Enter the terms in the polynomial1 \n");
	scanf("%d", &n);
	i = 1;
	while (n-- > 0) {
		printf("Enter the exponent and coefficient of the term number %d\n", i);
		scanf("%d %lf", &e, &c);
		poly1 = insert(poly1, e, c);
	}
	printf("Enter the terms in the polynomial2 \n");
	scanf("%d", &n);
	i = 1;
	while (n-- > 0) {
		printf("Enter the exponent and coefficient of the term number %d\n", i);
		scanf("%d %lf", &e, &c);
		poly2 = insert(poly2, e, c);
	}
	poly1 = sortlist(poly1);
	poly2 = sortlist(poly2);
	printf("The polynomial 1 is\n");
	printlist(poly1);
	printf("The polynomial 2 is\n");
	printlist(poly2);
	result = polyadd(poly1, poly2);
	printf("The result of addition is\n");
	printlist(result);
	getchar();
	return 0;
}

Explanation

1. If the polynomials to be added have n and m terms, respectively, then the linked list representation of these polynomials contains m and n terms, respectively.
2. Since polyadd traverses each of these lists, sequentially, the maximum number of iterations that polyadd will make will not be more than m + n. So the computation time of polyadd is O(m + n).