Question 8 of 9: Linked Lists — Polynomial Representation

Question 8: Linked Lists — Polynomial Representation (20 marks: (a) 10, (b) 10)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) A stream of (coefficient, exponent) pairs, sorted by descending exponent, terminated by a sentinel (0,0) pair that is not itself part of the polynomial. (b) Two such lists, $p_1$ and $p_2$, each already sorted by descending exponent.

Find. (a) The head pointer of a new list holding exactly the pairs read before the (0,0) sentinel. (b) The head pointer of a new list representing $p_1(x)+p_2(x)$, still sorted by descending exponent, with matching-exponent terms combined (and any that sum to zero dropped, since $c_i>0$ is required for every stored term).

Approach. (a) Read (c,e) pairs in a loop, appending each to the tail of a growing list, and stop (without appending) the moment a (0,0) pair is read. (b) Walk $p_1$ and $p_2$ together like a merge: at matching exponents, add the coefficients and keep the term only if the sum is nonzero; otherwise copy whichever term has the larger exponent (it cannot be matched by anything left in the other, still-descending list) and advance only that pointer.

(a) get_polynomial() (10 marks)

1. Write the corrected struct and the reader.

   #include <stdio.h>
   #include <stdlib.h>
   
   struct polynomial_node {
       int coefficient;
       int exponent;
       struct polynomial_node *next;
   };
   typedef struct polynomial_node polynomial_node;
   
   polynomial_node *get_polynomial(void)
   {
       polynomial_node *head = NULL, *tail = NULL, *node;
       int c, e;
   
       while (scanf("%d %d", &c, &e) == 2 && !(c == 0 && e == 0)) {
           node = (polynomial_node *) malloc(sizeof(polynomial_node));
           node->coefficient = c;
           node->exponent = e;
           node->next = NULL;
           if (head == NULL) head = node;
           else tail->next = node;
           tail = node;
       }
       return head;
   }

2. Trace it on an input stream 3 4 5 2 2 0 0 0, representing $p_1(x) = 3x^4+5x^2+2$. The loop appends nodes $(3,4)$, $(5,2)$, $(2,0)$ in order and stops before appending anything for the $(0,0)$ terminator. $$\boxed{\text{list} = (3,4)\to(5,2)\to(2,0)\to\text{NULL}}$$

(b) add_polynomials() (10 marks)

1. Write the merge-style addition.

   polynomial_node *add_polynomials(polynomial_node *p1, polynomial_node *p2)
   {
       polynomial_node dummy; dummy.next = NULL;
       polynomial_node *tail = &dummy, *node;
   
       while (p1 != NULL && p2 != NULL) {
           if (p1->exponent == p2->exponent) {
               int sum = p1->coefficient + p2->coefficient;
               if (sum != 0) {                 /* drop terms that cancel */
                   node = (polynomial_node *) malloc(sizeof(polynomial_node));
                   node->coefficient = sum;
                   node->exponent = p1->exponent;
                   node->next = NULL;
                   tail->next = node; tail = node;
               }
               p1 = p1->next; p2 = p2->next;
           } else if (p1->exponent > p2->exponent) {
               node = (polynomial_node *) malloc(sizeof(polynomial_node));
               *node = *p1; node->next = NULL;
               tail->next = node; tail = node;
               p1 = p1->next;
           } else {
               node = (polynomial_node *) malloc(sizeof(polynomial_node));
               *node = *p2; node->next = NULL;
               tail->next = node; tail = node;
               p2 = p2->next;
           }
       }
       /* copy whichever list still has terms left (already sorted correctly) */
       for (; p1 != NULL; p1 = p1->next) {
           node = (polynomial_node *) malloc(sizeof(polynomial_node));
           *node = *p1; node->next = NULL;
           tail->next = node; tail = node;
       }
       for (; p2 != NULL; p2 = p2->next) {
           node = (polynomial_node *) malloc(sizeof(polynomial_node));
           *node = *p2; node->next = NULL;
           tail->next = node; tail = node;
       }
       return dummy.next;
   }

2. Trace it on $p_1(x)=3x^4+5x^2+2$ and $p_2(x)=-3x^4+2x^3+x^2+7$. Walking both lists together: exponent 4 matches, $3+(-3)=0$, so that term is dropped entirely; exponent 3 exists only in $p_2$, copied as-is; exponent 2 matches, $5+1=6$, kept; exponent 0 matches, $2+7=9$, kept. $$\boxed{p_1+p_2 = 2x^3+6x^2+9}$$