Scribd
Upload
483 views4 pages

Polynomial Representation and Addition

1. The document discusses representing polynomials using linked lists, where each node stores an exponent-coefficient pair. 2. It provides code to add two polynomials represented as linked lists by traversing both lists simultaneously and inserting summed terms into a new list. 3. The time complexity of adding two polynomials using this linked list representation is O(m+n) where the polynomials have m and n terms respectively, since the addition algorithm traverses each list once.

Uploaded by

Programmer009
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
483 views4 pages

Polynomial Representation and Addition

1. The document discusses representing polynomials using linked lists, where each node stores an exponent-coefficient pair. 2. It provides code to add two polynomials represented as linked lists by traversing both lists simultaneously and inserting summed terms into a new list. 3. The time complexity of adding two polynomials using this linked list representation is O(m+n) where the polynomials have m and n terms respectively, since the addition algorithm traverses each list once.

Uploaded by

Programmer009
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

POLYNOMIAL REPRESENTATION

Introduction
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 3x2+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 Figure 20.10.

The procedure to add these two polynomials using the linked list is in the following program. Program
# 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; } } void 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 ); }

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).

You might also like