#30 다항식을 연결리스트로 구현하기

다항식을 연결 리스트로 구현하는 방법을 알아보자. 굳이 왜 연결 리스트로 구현할까?

다음과 같은 다항식의 구조를 생각해보면 이해하기 쉽다.

A(x) 다항식엔 계수인 a와 지수인 e의 정보만 포함되면 된다. 각 항을 노드로 구성하면 쉽게 해결할 수 있다.

[계수(coef) + 지수(expon) + 포인터(link)]로 하나의 노드를 구성하는 방법을 생각해볼 수 있다.

 

 

일단 구현해보면 좋은 일이 생기지 않을까? 하는 개떡같은 마음으로 다항식을 분해해보자. 실제로 다항을 계산해야하는 복잡한 연산코드를 짜는 사람들이 아니라면 실무에서 잘 쓰이진 않는다.

꿈꾸고 사랑하고 열렬히 행하고 성공하기 위하여

---

 

 

 

다항식을 연결 리스트로 표현하기

다항식 자체를 나타내는 것은 아래와 같은 식으로 표현할 수 있다.

[계수(coef) + 지수(expon) + 포인터(link)]의 한 노드로 표현할 것이다.

typedef struct polyNode polyPointer;
typedef struct polyNode {
    int coef;
    int expon;
    polyPointer *link;
};

polyPointer *a, *b, *c

coef, expon, *link 세 가지로 구성된 연결 리스트를 만들었다.

 

다항식의 덧셈 표현하기

위 a와 b항을 더하는 프로그램을 짜 보자. 먼저 연결 리스트로 아래와 같은 구조를 만들 수 있다.

여기서 위 항의 덧셈을 시작해줘야한다.

 

여기서 덧셈 알고리즘은 다음과 같다.

    1) 항을 비교하며 새로운 c 연결 리스트 결과의 끝에 노드를 만들어 추가

    2) 두항의 지수가 같으면 그 계수를 더해 새로운 항을 c에 만듦

    3) a 현재항 지수 =/ b 현재항 지수면 큰 항을 만들어 c에 추가

    4) c의 마지막 노드를 가리키는 포인터 rear추가

 

이를 코드로 구현해보면 다음과 같다.

 

1) 새로운 항을 뒤에 붙여주는 attach 함수 만들기

void attach (float coefficient, int exponent, polyPointer *ptr) {
	polyPointer *temp = (polyPointer *) malloc (sizeof(polyPointer));
    
    temp -> coef = coefficient;
    temp -> expon = exponent;
    ptr -> link = temp; // 아래 1번
    ptr = temp; // 아래 2번
}

temp 노드를 새로 만들어 준 뒤 뒤에 ptr을 이용하여 이전 노드에 붙여주는 함수이다.

2) 동적 메모리 할당 & 동차 항을 비교해서 c에 넣어주는 함수

polyPointer* padd(polyPointer *a, polyPointer *b) {
	polyPointer *c; //결과 출력
    polyPointer *rear, *temp; //중간 값들
    int sum; //더한 값 넣어주기
    
    rear = (polyPointer*)malloc (sizeof(polyPointer));
    c = rear;
   
	while ( a&&b )
    	switch (COMPARE(a->expon, b->expon)){
        	case -1:
            	attach ( b-> coef, b->expon, rear);
                b = b -> link;
                break;
            case 0:
            	sum = a -> coef + b -> coef;
                if (sum)
                	attach ( sum, a->expon, rear);
                a = a -> link;
                b = b -> link;
                break;
            case 1:
            	attach ( a -> coef, a -> expon, rear ) ;
                a = a -> link;
            }
                
            

3) 항이 겹치지 않는 a와 b의 나머지 항을 복사

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;

4) 필요 없는 초기 노드 삭제

temp = c;
c = c -> link;
free(temp);

return c;
}

 

다항식 노드 삭제하기

마음의 안 드는 식을 만들었을 때 식을 다시 칠 수는 없는 노릇이다.

이를 위한 다항식 단순 노드 삭제는 다음과 같이 한다.

ptr이 가리키는 노드를 temp로 만들어 빼누는 식이다.

void erase(polyPointer *ptr) {
	polyPointer *temp;
    
    while (ptr) {
    	temp = ptr;
        ptr = ptr -> link;
        free(temp);
    }
}

---

 

 

 

연결 리스트로 구현하면 0인 다항식을 표현할 수 없다. 또한 함수가 복잡하기에 이보다 원형 리스트를 써주는 경우가 많다.

다음에는 조금, 아주 조그으으음 복잡한 원형 리스트로 다항식을 구현하는 방법을 알아보도록 하자!!