[Data Structure] CHAP 8. Polynomials using Linked List (연결리스트로 다항식 쓰기) - C언어 ver.

저번 챕터에서 했던 스택과 큐 구현에 이어, 이번 챕터에서는 다항식을 연결리스트로 구현하는 방법을 작성할 예정이다. 작성은 다음과 같은 순서로 진행할 것이다.

• 왜 연결리스트( linked list )로 구현할까?
• 구현방법과 소스코드

그럼 스타-트!

---

1. 왜 연결리스트로 구현할까?

다항식은 말 그대로 여러개의 단항식이 연결된 구조를 띈다. 이러한 다항식의 특성상 항의 개수 변동이 심하기 때문에 미리 크기를 정해둬야하는 배열은 효율성이 떨어진다. 따라서 배열보다는 linked list로 짜는 것이 더 효율적이다 😎

---

2. linked list를 이용한 다항식 구현방법

구현방법을 보이기 위해 c = a + b 를 예시로 보여주려고 한다. 이때,
a = 6x^6 + 2x^3 + 2 , b = 2x^6 + 7x^4 + 5x 이다.

변수 a, b는 각각 맨 앞 노드를 가리킨다. c는 a+b이다.

가장 먼저 할 일은 a와 b 노드의 차수를 비교하는 일이다. 위 상황에서는 차수가 같기 때문에 a,b의 계수를 더해주고, 차수도 그대로 내려준다. 그 후 a,b는 원래 가리키던 노드의 다음 노드를 가리킨다. 그 후에는 같은 과정을 반복하면 된다.

차수를 비교해보면 a는 3, b는 4임을 알 수 있다. 차수가 더 큰 항의 계수와 차수를 c에 생성한다.

이후 차수가 더 큰 b는 다음 노드를 가리키게 한다. 이 과정을 다음 노드가 없을 때까지 계속 반복한다.

🌟소스코드

두 다항식의 합을 구하는 소스코드는 다음과 같다.

 polyPointer padd(polyPointer a, polyPointer b)
 {
 	polyPointer c,rear,temp;
    int sum;
    MALLOC(rear, sizef(*rear));
    c = rear;
    while (a && b)
    	switch (COMPARE(a -> expon, b -> expon)) {	//차수비교
        	case -1 :      // a차수 < b차수
            	attach(b->coef, b->expon, &rear);	  //b의 계수,차수 쓰기
                b = b -> link;		// 다음노드로 이동
                break;
            case 0:		   // a차수 = b차수
            	sum = a -> coef + b -> coef;	//a,b계수 합
                if (sum)  attach(sum, a -> expon, &rear);   //합이 0이 아니면 계수 차수 쓰기
                a = a -> link; b = b -> link; break;	//a,b 다음노드로
            case 1:			// a차수 > b차수
            	attach(a -> coef, a -> expon, &rear); 	//a의 계수, a의 차수 쓰기
                a = a -> link;	// 다음노드로 이동
        }
   for (; a; a = a -> link)   attach(a -> coef, a -> expon, &rear);	
   for (; b; b = b -> link)   attach(b -> coef, b -> expon, &rear);  //처리 안된거 쓰기
   rear -> link = NULL;
   
   temp-c; c = c -> link; free(temp);
   return c;
}