[Data Structure] #1-5 연결리스트를 이용한 다항식의 표현

아래와 같은 다항식이 존재한다고 했을 때, 이것을 어떻게 표현할 것인가? 더욱이 A(x) 와 B(x) 연산은 어떻게 해야할까?

기본 구조체는 다음과 같다.

typedef struct ListNode{
    int coef;
    int expon;
    struct ListNode* link;
} ListNode;

 coef는 x항의 계수(coefficient)를 의미하고 expon은 x항의 승수를 의미한다. link는 다음 노드를 가리키는 포인터다. 이제 감이 올 것이다.  이 때 두 항을 더하는 논리를 생각해보자. A(x)와 B(x)가 합쳐질 때에는 먼저 x의 승수가 같은지 확인해야한다. 같다면 계수간의 계산이 가능할 것이다. 그렇지 않으면 승수의 크기에 따라 연결리스트의 구조를 짜주면 된다. 정리해 보자면 다음과 같다. A(x)를 가리키는 포인터를 p라고 하고 B(x)를 가리키는 포인터를 q라고 하고 .. C(x) = A(x) + B(x)라고 하자.

1. p.expon = q.expon

 승수가 같다. 그러면 두 계수를 더한다. 만약 0일 경우에는 해당 노드를 없앤다.

2. p.expon > q.expon

 A(x) 항의 승수가 크다. C(x)에 p가 가리키는 노드를 추가한다. 그리고 나서 p를 다음 노드로 넘어가게 한다.

3. p.expon < q.expon

 B(x) 항의 승수가 크다. C(x)에 q가 가리키는 노드를 추가한다. 그리고 q를 다음 노드로 넘어가게 한다.

 이러한 과정을 지속해서 p혹은 q가 null이 나올때까지 지속한다. 만약 null이 나오면 나머지 남은 노드들을 그냥 C(x) 에 추가시켜주면 된다..

 이제 코드를 보자.

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode{
    int coef;
    int expon;
    struct ListNode* link;
} ListNode;

// Header Structure of Linked List
typedef struct ListHeader{
    int length;
    ListNode *head;
    ListNode *tail;
} ListHeader;

void init(ListHeader *plist){
    plist->length = 0;
    plist->head = plist->tail = NULL;
}

void insert_node_last(ListHeader *plist, int coef, int expon){
    ListNode* node = (ListNode*) malloc(sizeof(ListNode));
    node->coef = coef;
    node->expon = expon;
    node->link = NULL;
    
    if (plist == NULL) return;
    
    if (plist->head==NULL) {
        plist->head = node;
        plist->tail = node;
    }else {
        plist->tail->link = node;
        plist->tail = node;
    }
    plist->length++;
}

void poly_add(ListHeader *plist, ListHeader *plist2, ListHeader *plist3){
    ListNode *p = plist->head;
    ListNode *q = plist2->head;
    
    while (p && q) {
        if (p->expon == q->expon) { // 1
            int sum = p->coef + q->coef;
            if (sum == 0) continue;
            insert_node_last(plist3, sum, p->expon);
            p = p->link; q = q->link;
        } else if (p->expon > q->expon) { // 2
            insert_node_last(plist3, p->coef, p->expon);
            p = p->link;
        } else if (p->expon < q->expon) { // 3
            insert_node_last(plist3, q->coef, q->expon);
            q = q->link;
        }
    }
    
    for (; p != NULL; p = p->link)
        insert_node_last(plist3, p->coef, p->expon);
    for (; q != NULL; q = q->link)
        insert_node_last(plist3, q->coef, q->expon);
}

void poly_print(ListHeader *plist){
    ListNode *p = plist->head;
    for (; p != NULL; p = p->link) {
        printf("%d %d\n",p->coef,p->expon);
    }
}

int main() {
    ListHeader list1, list2, list3;
    init(&list1);
    init(&list2);
    init(&list3);
    
    insert_node_last(&list1, 3, 12);
    insert_node_last(&list1, 2, 8);
    insert_node_last(&list1, 1, 0);
    
    insert_node_last(&list2, 8, 12);
    insert_node_last(&list2, -3, 10);
    insert_node_last(&list2, 10, 6);
    
    poly_add(&list1, &list2, &list3);
    poly_print(&list3);
    
    return 0;
}

 별달리 어려운게 없고, 코드 내용 또한 직관적이므로 설명을 생략한다. 다만 for (; p != NULL; p = p->link) 과 같이 포인터를 for문으로 돌리는 skill 정도는 익혀두는 것이 좋겠다.