CREATE A C PROGRAM USING THE TEMPLATE:

include

#include

/*

* Polynomial ADT. This data type uses two structures

* Monomial: is used to represent a term c * x^p

* where c is the coefficient and p is the power.

* Polynomial: is used to capture an entire polynomial as a list

* of monomial.

* Note that the representation is sparse. Monomials with a coefficient

* of zero should not be in the list. For instance, the polynomial:

* 3 + 2 x + 4 x^3 - 7 x^10 would be represented by:

* (10 , [(3,0), (2,1),(4,3),(-7,10)])

* Where the first 10 is the degree of the polynomial and the list

* represent the 4 monomials with non-zero coefficients.

*/

typedef struct Monomial {

int coeff; /* coefficient */

int exp; /* exponent */

struct Monomial *next; /* next monomial */

} Mono;

typedef struct Polynomial {

int deg; /* degree */

Mono * first; /* first monomial */

Mono * last; /* last monomial */

} Poly;

/*

* This function creates a new monomial with a given coefficient and power.

* c : the coefficient

* k : the power

* The function allocates a monomial and initializes its attributes.

* The return value is a pointer to the newly created monomial.

*/

Mono * newMono(int c, int k)

{

// TODO

return NULL;

}

/*

* This function creates a new (empty) polynomial with degree 0 and no

* monomials.

*/

Poly * newPoly()

{

// TODO

return NULL;

}

/*

* This function deallocates a polynomial.

* p : the polynomial to deallocate

* The function deallocates not-only the polynomials but also all the

* monomials that it refers to (since those should not be shared anyway!)

*/

void freePoly(Poly * p)

{

// TODO

if( p == NULL ) return;

}

/*

* This functions adds a monomial inside a polynomial

* p : the polynomial to modify

* m : the monomial to add

* The polynomial p is expected to be the sole owner of m.

* The new monomial should be added at the end of the list.

* The degree of the monomial should not exceed the degree of the polynomial

*/

void appendMono(Poly * p, Mono * m)

{

// TODO

}

/*

* This function allocates, reads and returns a polynomial.

* It starts by asking the highest degree

* Then it reads all the monomials (which are given in increasing

* order of powers) as pairs of integers (whitespace separated)

* and adds them to the polynomial.

* It finally returns the constructed poly.

*/

Poly * readPoly()

{

/*

Add code to read from standard input a polynomial

in the format described in the assignment document

and construct its linked list representation

*/

// TODO

return NULL;

}

/*

* This function prints the received polynomial on the standard output.

* p : the polynomial to print.

* Ouput: print the degree, then print a sequence of pairs coef power

* end with a line feed.

*/

void printPoly(Poly * p)

{

/*

Add code to print to standard output a polynomial

in the format described in the assignment document

*/

if( p == NULL || p->first == NULL ) {

printf("empty ");

return;

} else { /* print degree */

printf( "%d ", p->deg );

Mono * m = p->first;

while( m != NULL ) {

printf( "%d %d ", m->coeff, m->exp );

m = m->next;

}

/* end with newline character */

printf( " " );

}

}

/*

* The addPoly function computes a new polynomial that represent the sum of

* its inputs.

* p1 : first polynomial

* p2 : second polynomial

* Assumptions:

* - both p1 and p2 list monomials in increasing powers.

* - p1 and p2 do NOT have to have the same degree

* - p1 and p2 are NOT expected to have the same number of monomials

* - p1 and p2 are NOT expected to have monomials of matching degrees (they might)

* - The treatment is NOT destructive. p1 and p2 are untouched.

* Output:

* A new polynomial is allocated, filled and returned.

* Notes:

* - monomials of the same power from p1 and p2, should be aggregated.

* - monomials with a zero coefficient should be discarded.

* - the degree of the answer should be the highest power with a non-zero coef.

*/

Poly * addPoly(Poly * p1,Poly * p2)

{

/*

Add code to compute the sum of two polynomials

given as linked lists

*/

// TODO

return NULL;

}

/***************************************************/

int main()

{

Poly * p1 = readPoly();

Poly * p2 = readPoly();

Poly * sum;

if( (p1 == NULL) || (p2 == NULL) )

{

fprintf(stderr, "Could not allocate memory ");

return 1;

}

printPoly(p1);

printPoly(p2);

printf(" ");

printPoly( sum = addPoly( p1, p2 ) );

freePoly(p1);

freePoly(p2);

freePoly(sum);

return 0;

}

/***************************************************/

Many of the polynomials arising in practice are sparse, i.e., they have a number of non-zero coefficients that es using an array representation is wasteful, and polynomials are best represented as a linked list. In this exercise you are required to implement addition of sparse univariate polynomials with integer coefficients. Polynomials must be represented by your program as linked lists of monomials. The provided template code defines an abstract data type (structures) for and includes headers for representing monomials and polynomials several functions that operate on them Do not modify main) and printPolyOin the template. Input: Your program should read from the standard input 2 polynomials. Each polynomial starts with an integer that represents the degree of the polynomial. It is followed by a number of pairs of integers that represent the coefficient and exponent of the monomials that comprise the polynomial. For example, the polynomial