연결 리스트의 응용 : 다항식
다항식은 단순 연결 리스트로 표현 가능한데, 이 경우에 각 항이 하나의 노드로 표현된다.
각 노드는 계수(coef)와 지수(expon) 그리고 다음 항을 가리키는 링크(link)필드로 구성되어 있다.
typedef struct ListNode {
int coef;
int expon;
struct ListNode* link;
}ListNode;각 다항식은 다항식의 첫 번째 항을 가리키는 포인터로 표현된다.
ListNode *A, *B;
다항식이 연결 리스트로 표현되어 있기 때문에 포인터 변수 p와 q를 이용하여 다항식 A와 B의 항들을 따라 순회하면서 각 항들을 더하면 된다.
p와 q가 가리키는 항의 지수에 따라 3가지 경우로 나누어 처리할 수 있다.
-
p.expon == q.expon : 두 계수를 더해서 0이 아니면 새로운 항을 만들어 다항식 C에 추가한다. 그리고 p와 q는 모두 다음 항으로 이동한다.
-
p.expon < q.expon : q가 가리키는 항을 새로운 항으로 복사하여 다항식 C에 추가한다. 그리고 q만 다음 항으로 이동한다.
-
p.expon > q.expon : p가 가리키는 항을 새로운 항으로 복사하여 다항식 C에 추가한다. 그리고 p만 다음 항으로 이동한다.
앞의 과정들을 p나 q 둘 중에서 어느 하나가 NULL이 될 때까지 되풀이한다.
p나 q중에서 어느 하나가 NULL이 되면 아직 남아 있는 항들을 C로 전부 가져오면 된다.
여기서는 하나의 연결 리스트가 두 개의 포인터 head와 tail로 표현되고 있다.
head는 첫 번째 노드를, tail은 마지막 노드를 가리킨다.
이런 식으로 효율적인 계산을 위하여 첫 번째 노드와 마지막 노드를 가리키는 포인터를 동시에 사용하는 수도 많다.
보통은 헤더 노드(Header node)라고 하는 특수한 노드가 있고 이 헤더 노드가 head와 tail포인터를 동시에 가지고 있다.
추가로 연결 리스트에 들어 있는 항목들의 개수인 length 변수도 가지는 경우가 많다.
이런 경우, 하나의 연결 리스트는 하나의 헤더 노드에 의하여 표현된다.
실제로 헤더 노드를 사용하게 되면 편리한 점이 매우 많다.
하나의 예를 들면 맨 끝에 노드를 추가하는 경우, 단순 연결 리스트의 경우 매번 추가할 때마다 처음부터 포인터를 따라서 끝까지 가야 한다.
그러나 만일 마지막 노드를 항상 가리키는 포인터가 있는 경우에는 아주 효율적으로 추가하는 것이 가능해진다.
반면, 헤더 노드의 개념을 사용하기 위해서는 항상 연결 리스트를 생성한 다음, 초기화를 해주어야 한다.
여기서는 init함수를 이용하여 초기화하였다.
여기서도 새로운 노드가 만들어질 때마다 결과 다항식의 마지막 노드를 찾는 작업을 피하기 위하여 마지막 노드를 가리키는 tail 포인터를 헤더 노드 안에서 유지한다.
insert_node_last 함수는 새로운 노드를 만들어서 다항식의 마지막에 추가하는 역할을 한다.
이때 헤더 노드를 가리키는 포인터가 함수의 매개 변수로 전달되는 것을 유의하라.
이는 헤드와 테일 포인터를 변경하기 위한 것이다.
많은 연결 리스트 연산들이 이 함수처럼 헤드 포인터에서 시작하여 노드들을 하나씩 따라가면서 처리를 하는 형식으로 되어 있다.
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 노드의 구조
typedef struct ListNode {
int coef;
int expon;
struct ListNode* link;
}ListNode;
//연결 리스트 헤더
typedef struct ListHeader {
int length;
ListNode* head;
ListNode* tail;
}ListHeader;
//초기화 함수
void init(ListHeader* plist) {
plist->length = 0;
plist->head = plist->tail = NULL;
}
//오류 처리 함수
void error(char* message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
//plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수, expon은 지수
void insert_node_last(ListHeader* plist, int coef, int expon) {
ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
if (temp == NULL)error("메모리 할당 에러");
temp->coef = coef;
temp->expon = expon;
temp->link = NULL;
if (plist->tail == NULL) {
plist->head = plist->tail = temp;
}
else {
plist->tail->link = temp;
plist->tail = temp;
}
plist->length++;
}
void poly_add(ListHeader *plist1,ListHeader *plist2, ListHeader *plist3) {
ListNode* a = plist1->head;
ListNode* b = plist2->head;
int sum;
while (a && b) {
if (a->expon == b->expon) {
sum = a->coef + b->coef;
if (sum != 0) insert_node_last(plist3, sum, a->expon);
a = a->link;
b = b->link;
}
else if (a->expon > b->expon) {
insert_node_last(plist3, a->coef, a->expon);
a = a->link;
}
else {
insert_node_last(plist3, b->coef, b->expon);
b = b->link;
}
}
for (; a != NULL; a = a->link) {
insert_node_last(plist3, a->coef, a->expon);
}
for (; b != NULL; b = b->link) {
insert_node_last(plist3, b->coef, b->expon);
}
}
void poly_print(ListHeader* plist) {
ListNode* p = plist->head;
for (; p; 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;
}
