[자료구조] 연결리스트의 응용 - 다항식

 

 

다항식  : 계수와 차수로 이루어진 항들의 집합

 

 

단순연결 리스트를 이용하면 다항식을 구현할 수 있다

 

구조체

typeef struct ListNodeType {
  float coef;   //항(term)의 계수
  int degree;   //항(term)의 차수
  struct ListNodeType* pLink;
 }ListNode;

 

다항식의 덧셈

 

다항식 A(x) : 6x⁶ + 4x⁵  +   2x²

다항식 B(x) : 1x⁵ + 2x⁴ + 3x² +4

A(x)

B(x)

가장 마지막 노드의 pLink는 null 값을 가리킨다

차수가 높은 순으로 추가 되었다.

 

 

다항식의 생성 : 다항식의 항 추가 연산

int addPolyNodeLast(LinkedList *pList, float coef, int degree){
  int ret = FALSE, i = 0;
  
  ListNode node = {0,};
  node coef = coef;
  node degree = degree;
  
  if(pList !=NULL){
    int length = getLinkedListLength(pList);
    ret = addLLElement(pList,length, node);
  }
  
  return ret;
 }

다항식의 계산에서 고려해야 하는 사항

1. 다항식 A 의 차수 > 다항식 B의 차수

A에 있는 항만 가지고 새로운 노드를 추가하여 계산하고

A에 대해서 다음노드로 이동된다

 

2. 다항식 A의 차수 = 다항식 B의 차수

새로운 노드가 추가될때 계수를 더하여 진행하고

A,B 모두 다음노드로 이도된다

3. 다항식 A의 차수 < 다항식 B의 차수

B에 대해서만 다음 노드로 이동된다.

 

4. 남은 항을 어떻게 처리해줄 것이냐

다음 행이 null인 경우 일때까지 반복하면서 계산을 진행한다.

 

while(pNodeA != NULL && pNodeB != NULL){
  int degreeA = pNodeA -> degree;
  int degreeB = pNodeB -> degree;
  if(degreeA > degreeB) {
    coefSum = pNodeA -> coef;
    addPolyNodeList(pReturn, coefSum, degreeA);
    pNodeA = pNodeA -> pLink;
  }
  else if(degreeA == degreeB) {
    coefSum = pNodeA ->coef + pNodeB -> coef;
    addPolyNodeLast(pReturn, coefSum,degreeA);
    pNodeA = pNodeA -> pLink;
    pNodeB = pNodeB -> pLink;
   }
   else {
   coefSum = pNodeB ->coef;
   addPolyNodeLast(pReturn, coefSum, degreeB);
   pNodeB = pNodeB -> pLink;
   }
  }
  
 while(pNodeA != NULL){
  coefSum = pNodeA -> coef;
  addPolyNodeLast(pReturn, coefSum, pNodeA -> degree);
  pNodeA = pNodeA -> pLink;
 }
 while(pNodeB != NULL){
  coefSum = pNodeB ->coef;
  addPolyNodeLast(pReturn, coefSum, pNodeB ->degree);
  pNodeB = pNodeB -> pLink;
 }