|Polynomial Addition| |polynomial addition using linked list|

  Polynomial Addition

• A = 4x10 + 3x6 + 1
• B = 3x10 – 2x8 + 6x6 + 8x4

How Polynomial addition is done?

• In the above image we perform polynomial addition using linked list

• We use two pointers i and j for pointing A and B.

• In this liked list there will be 3 parts they are COEFFICIENT , EXPONENT, LINK(the pointer that points to the next node)

• First, We compare the Exponent of first element(i) in A and the Exponent of the first element(j) in B.

• Next, if the coefficient are same then we add and store them in C in form of ( COEFFICIENT , EXPONENT, LINK)

• Second, we compare the next node as the other two nodes(node 3(i) from A and node -2(i) from B), as the Exponents are different we place the highest exponent in C.

• Now , i will be in 3 place and j gets increment by 1 because, we had stored the -2 in C as discussed above.

• i which is in 3 is compared with , j that is in 6 as their Exponents are same we add them and store them with the same Exponent(don't add the Exponent)

• Like this it gets compared now when i reaches the end the remaining elements in B gets stored in C in the same order itself.

• This way of implementation is discussed in this link in a detail manner(Merge Sort (ayyavuu.blogspot.com).

Some points to know

• A and B are 2 Polynomials
  p and q are 2 pointers to move along the terms of A and B
  Resultant Polynomial is C 
  d is a pointer to the last node in C
  C is initially given a single node with no values which is deleted at the end 
  ATTACH subroutine creates a new node and appends it to the end of C
  

  Algorithm:

  procedure PADD(A,B,C)
  1 p-A; q-B   //p, q pointers to next term of A, B//
  2 call GETNODE(C); d-C //initial node for C, returned later//
  3 while p =  0 and q = 0 do //while there are more terms in A and B//
  4 case
  5       : EXP(p) = EXP(q): //equal exponents//
  6 x       COEF(p) + COEF(q)
  7 if x  =   0 then call ATTACH(x, EXP(p),d)
  8 p        LINK(p); q      LINK(q) //advance to next terms//
  9       : EXP(p) < EXP(q):
  10 call ATTACH(COEF(q),EXP(q),d)
  11 q       LINK(q) //advance to next term//
  12    : else: call ATTACH(COEF(p),EXP(p),d)
  13 p      LINK(p) //advance to next term of A//
  14 end
  15 end
   while p = 0 do //copy remaining terms of A//

17 call ATTACH(COEF(p),EXP(p),d)

18 p -LINK(p)

19 end

20 while q = 0 do //copy remaining terms of B//

21 call ATTACH(COEF(q),EXP(q),d)

22 q-LINK(q)

23 end

24 LINK(d)- 0; t - C; C -LINK(C)   //delete extra initial node//

25 call RET(t)

26 end PADD