Base code:
Exercise 3. (40 points) Sparse polynomials. Many of the polynomials arising in practice are sparse, i.e., have a number of non-zero coefficients that is much smaller than the degree. In these cases using an array representation is wasteful, and such polynomials can be 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 in your program as linked lists of monomials. The template code provided in poly.c defines structures for representing polynomials as linked lists along with incomplete definitions of several functions that operate on them. Each function definition is preceded in the template code by a comment detailing the expected functionality; read this carefully and follow all stated requirements. Among others, these functions are required to dynamically allocate and free the memory needed to store polynomials and compute the sum of two given polynomials. Functions that (a) read a polynomial from standard input and build its linked list representation, and (b) print a polynomial represented as linked list to standard output are already provided. Do not modify these two functions to preserve the input/output format expected by Mimir (illustrated in the examples below). Input: The poly.c program reads from the standard input 2 lines, each representing a polynomial. For each line the first integer represents the degree of the polynomial. This 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 3 + 2x4 +210 is represented by the sequence: 10 3 0 2 4 1 10 You may assume that input polynomials are non-zero (i.e., have at least one non-zero coefficient), and that monomials of each polynomial are given in increasing order of their exponents. Coefficients are arbitrary non-zero integers; monomials with zero coefficients are always omitted. Output: The provided main() function uses printPoly() to print the two input polynomials along with their sum, as in the following examples. In case the sum is the zero polynomial the linked list representation 2 should be a list with no monomials, which gets printed by printPoly() as 0. Do not modify the main() function except for including cleanp code required to avoid memory leaks. Sample Input 1: Sample Output 2: 2 1 0 3 2 2 2 1 4 2 (1 + 3x 2) + (2x + 4x^2) = 1 + 2x + 7x2 Sample Input 2: Sample Output 2: 2 1 0 3 2 2 -1 0 -3 2 (1 + 3x^2) + (-1 - 3x^2) = 0 * i #include
2 #include 3 #include 4 5*/* 6 * Polynomial ADT. This data type uses two structures 7 * Monomial: is used to represent a term C * x^k 8 where c is the coefficient and k is the exponent. 9 * Polynomial: is used to capture an entire polynomial as a linked list 10 of monomials, in increasing exponent order. 11 * Note that the representation is sparse and monomials with a coefficient 12 * of zero should not be included in the list. For instance, the polynomial 13 * 3 - 2x^4 + x^10 would be represented by the list of three monomials 14 * [(3,0), (-2,4), (1,10)] 15 16 17-typedef struct Monomial { 18 int coeff; /* coefficient */ 19 int exp; /* exponent 20 struct Monomial *next; /* next monomial */ 21 } Mono; 22 23 24 typedef struct polynomial { 25 int deg; /* degree */ 26 Mono* first; /* first monomial */ 27 Mono* last; /* last monomial * 28 } Poly; 29 30 31 - /* 32 * This function allocates and initializes a monomial 33 * with the given coefficient and exponent. 34 * C: the coefficient 35 *k : the exponent 36 * return value : a pointer to the newly allocated monomial 37 38 Mono* newMono(int c, int k, Mono* next) 39- 40 Mono* mono = (Mono*)malloc( sizeof(Mono)); 41 if( mono == NULL) return NULL; 42 mono->coeff = c; 43 mono->exp k; 44 mono->next = next; 45 return mono; 46 } 47 48 - /* 49 * This function allocates and returns a pointer to a new 50 * polynomial with no monomials. 51 52 Poly* newPoly() 53 - { 54 Poly* poly = (Poly*) malloc( sizeof(Poly) ); 55 if(poly == NULL) return NULL; 56 poly->deg = 0; 57 poly->first poly->last = NULL; 58 return poly; 59} 60 61 - /* 62 * This function deallocates a polynomial. 63 * p : pointer to the polynomial to deallocate 64 * Requirements: 65 the function deallocates not only the polynomial but also all the 66 monomials comprising it 67 68 void freePoly(Poly* p) 69 - { 70 // TODO 71 72 } 73 74 - /* 75 * This function adds a monomial to an existing polynomial 76 *P: pointer to the polynomial to modify 77 * m : pointer to the monomial to add 78 * Requirements: 79 * - the monomial should be added at the end of the monomial list 80 81 void appendMono ( Poly* p, Mono* m) 82 - { 83 // TODO 84 85 86 } 87 88 89 - /* 90 * This function computes a new polynomial that represents the sum 91 * between two given polynomials. 92 * pl : pointer to first polynomial 93 * p2 : pointer to second polynomial 94 * returned value : pointer to a new polynomial filled with the monomials of the sum 95 * Assumptions: 96 the given polynomials have only monomials with non-zero coefficients 97 the given polynomials have the monomials linked in increasing exponent order 98 * Requirements: 99 the given polynomials remain unchanged 100 * the result polynomial has only monomials with non-zero coefficients 101 the result polynomial has the monomials linked in increasing exponent order 102 * Notes: 103 the result polynomial cannot include multiple monomials with the same exponent 104 105 Poly* addPoly Poly* pl, Poly* p2 ) 106 - { 107 // TODO 108 109 110} 111 112*/* 113 * This function reads from the standard input a polynomial 114 * in the format described in the assignment document 115 * and builds its linked list representation. 116 * return value : pointer to the constructed polynomial 117 * Assumptions: 118 the polynomial degree is given first 119 * input monomials are given in increasing exponent order 120 * Requirements: 121 only monomials with non-zero coefficients get added to the list 122 the constructed list has monomials in increasing exponent order 123 * DO NOT CHANGE THIS FUNCTION 124 125 Poly* readPoly() 126 - { 127 int n, c, k; 128 129 Poly* poly = newPoly(); 130 if(poly == NULL) return NULL; 131 132 scanf("%d", &n); 133 poly->deg = n; 134 poly->first = poly->last = NULL; 135 136 do 137 { 138 scanf("%d %d", &c, &k); 139 if( c != 0 ) appendMonopoly, newMono(c, k, NULL)); 140 } 141 while(k first == NULL ) 154 - { 155 printf(""); 156 return; 157 } 158 else 159 - { 160 Mono* m = p->first; 161- while( m != NULL) { 162 int c = m->coeff; 163 int k = m->exp; 164 assert( m->coeff != 0); 165 if( m != p->first && c> ) printf(" +"); 166 if( m != p->first && c first && c O?C: -c)); 170 if(k > 0) printf("x" ); 171 if(k> i) printf("%d", k); 172 m = m->next; 173 } 174 175 } 176 177 178 - *****************/ 179 180 int main() 181 - { 182 Poly* pl = readPoly(); 183 Poly* p2 = readPoly(); 184 Poly* sum; 185 186 if( (pl == NULL) || (p2 == NULL)) 187- { 188 fprintf(stderr, "Could not allocate memory "); 189 return l; 190 } 191 192 sum = addPoly(p1, p2); 193 194 printf(""); 195 printPoly(pl); 196 printf(") + ("); 197 printPoly(p2); 198 printf(") = "); 199 printPoly(sum); 200 printf(" "); 201 202 // TODO: add any necessary cleanup code to avoid memory leaks 203 204 205 206 207 return 0; 208 } 209 210 211./ 212 * Exercise 3. (40 points) Sparse polynomials. Many of the polynomials arising in practice are sparse, i.e., have a number of non-zero coefficients that is much smaller than the degree. In these cases using an array representation is wasteful, and such polynomials can be 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 in your program as linked lists of monomials. The template code provided in poly.c defines structures for representing polynomials as linked lists along with incomplete definitions of several functions that operate on them. Each function definition is preceded in the template code by a comment detailing the expected functionality; read this carefully and follow all stated requirements. Among others, these functions are required to dynamically allocate and free the memory needed to store polynomials and compute the sum of two given polynomials. Functions that (a) read a polynomial from standard input and build its linked list representation, and (b) print a polynomial represented as linked list to standard output are already provided. Do not modify these two functions to preserve the input/output format expected by Mimir (illustrated in the examples below). Input: The poly.c program reads from the standard input 2 lines, each representing a polynomial. For each line the first integer represents the degree of the polynomial. This 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 3 + 2x4 +210 is represented by the sequence: 10 3 0 2 4 1 10 You may assume that input polynomials are non-zero (i.e., have at least one non-zero coefficient), and that monomials of each polynomial are given in increasing order of their exponents. Coefficients are arbitrary non-zero integers; monomials with zero coefficients are always omitted. Output: The provided main() function uses printPoly() to print the two input polynomials along with their sum, as in the following examples. In case the sum is the zero polynomial the linked list representation 2 should be a list with no monomials, which gets printed by printPoly() as 0. Do not modify the main() function except for including cleanp code required to avoid memory leaks. Sample Input 1: Sample Output 2: 2 1 0 3 2 2 2 1 4 2 (1 + 3x 2) + (2x + 4x^2) = 1 + 2x + 7x2 Sample Input 2: Sample Output 2: 2 1 0 3 2 2 -1 0 -3 2 (1 + 3x^2) + (-1 - 3x^2) = 0 * i #include 2 #include 3 #include 4 5*/* 6 * Polynomial ADT. This data type uses two structures 7 * Monomial: is used to represent a term C * x^k 8 where c is the coefficient and k is the exponent. 9 * Polynomial: is used to capture an entire polynomial as a linked list 10 of monomials, in increasing exponent order. 11 * Note that the representation is sparse and monomials with a coefficient 12 * of zero should not be included in the list. For instance, the polynomial 13 * 3 - 2x^4 + x^10 would be represented by the list of three monomials 14 * [(3,0), (-2,4), (1,10)] 15 16 17-typedef struct Monomial { 18 int coeff; /* coefficient */ 19 int exp; /* exponent 20 struct Monomial *next; /* next monomial */ 21 } Mono; 22 23 24 typedef struct polynomial { 25 int deg; /* degree */ 26 Mono* first; /* first monomial */ 27 Mono* last; /* last monomial * 28 } Poly; 29 30 31 - /* 32 * This function allocates and initializes a monomial 33 * with the given coefficient and exponent. 34 * C: the coefficient 35 *k : the exponent 36 * return value : a pointer to the newly allocated monomial 37 38 Mono* newMono(int c, int k, Mono* next) 39- 40 Mono* mono = (Mono*)malloc( sizeof(Mono)); 41 if( mono == NULL) return NULL; 42 mono->coeff = c; 43 mono->exp k; 44 mono->next = next; 45 return mono; 46 } 47 48 - /* 49 * This function allocates and returns a pointer to a new 50 * polynomial with no monomials. 51 52 Poly* newPoly() 53 - { 54 Poly* poly = (Poly*) malloc( sizeof(Poly) ); 55 if(poly == NULL) return NULL; 56 poly->deg = 0; 57 poly->first poly->last = NULL; 58 return poly; 59} 60 61 - /* 62 * This function deallocates a polynomial. 63 * p : pointer to the polynomial to deallocate 64 * Requirements: 65 the function deallocates not only the polynomial but also all the 66 monomials comprising it 67 68 void freePoly(Poly* p) 69 - { 70 // TODO 71 72 } 73 74 - /* 75 * This function adds a monomial to an existing polynomial 76 *P: pointer to the polynomial to modify 77 * m : pointer to the monomial to add 78 * Requirements: 79 * - the monomial should be added at the end of the monomial list 80 81 void appendMono ( Poly* p, Mono* m) 82 - { 83 // TODO 84 85 86 } 87 88 89 - /* 90 * This function computes a new polynomial that represents the sum 91 * between two given polynomials. 92 * pl : pointer to first polynomial 93 * p2 : pointer to second polynomial 94 * returned value : pointer to a new polynomial filled with the monomials of the sum 95 * Assumptions: 96 the given polynomials have only monomials with non-zero coefficients 97 the given polynomials have the monomials linked in increasing exponent order 98 * Requirements: 99 the given polynomials remain unchanged 100 * the result polynomial has only monomials with non-zero coefficients 101 the result polynomial has the monomials linked in increasing exponent order 102 * Notes: 103 the result polynomial cannot include multiple monomials with the same exponent 104 105 Poly* addPoly Poly* pl, Poly* p2 ) 106 - { 107 // TODO 108 109 110} 111 112*/* 113 * This function reads from the standard input a polynomial 114 * in the format described in the assignment document 115 * and builds its linked list representation. 116 * return value : pointer to the constructed polynomial 117 * Assumptions: 118 the polynomial degree is given first 119 * input monomials are given in increasing exponent order 120 * Requirements: 121 only monomials with non-zero coefficients get added to the list 122 the constructed list has monomials in increasing exponent order 123 * DO NOT CHANGE THIS FUNCTION 124 125 Poly* readPoly() 126 - { 127 int n, c, k; 128 129 Poly* poly = newPoly(); 130 if(poly == NULL) return NULL; 131 132 scanf("%d", &n); 133 poly->deg = n; 134 poly->first = poly->last = NULL; 135 136 do 137 { 138 scanf("%d %d", &c, &k); 139 if( c != 0 ) appendMonopoly, newMono(c, k, NULL)); 140 } 141 while(k first == NULL ) 154 - { 155 printf(""); 156 return; 157 } 158 else 159 - { 160 Mono* m = p->first; 161- while( m != NULL) { 162 int c = m->coeff; 163 int k = m->exp; 164 assert( m->coeff != 0); 165 if( m != p->first && c> ) printf(" +"); 166 if( m != p->first && c first && c O?C: -c)); 170 if(k > 0) printf("x" ); 171 if(k> i) printf("%d", k); 172 m = m->next; 173 } 174 175 } 176 177 178 - *****************/ 179 180 int main() 181 - { 182 Poly* pl = readPoly(); 183 Poly* p2 = readPoly(); 184 Poly* sum; 185 186 if( (pl == NULL) || (p2 == NULL)) 187- { 188 fprintf(stderr, "Could not allocate memory "); 189 return l; 190 } 191 192 sum = addPoly(p1, p2); 193 194 printf(""); 195 printPoly(pl); 196 printf(") + ("); 197 printPoly(p2); 198 printf(") = "); 199 printPoly(sum); 200 printf(" "); 201 202 // TODO: add any necessary cleanup code to avoid memory leaks 203 204 205 206 207 return 0; 208 } 209 210 211./ 212 *<><>
