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

다항식을 연결리스트로 표현해보는게 오늘 목표이다. 

다항식의 각 항 = 하나의 노드

각각의 노드-> 계수, 지수, 링크 필드(그다음항을 가리킴)로 구성한다.

다항식의 첫번째 항을 가리키는 포인터로 각각의 다항식을 표현한다.

각 노드의 구성 (그림)

tydef struct ListNode{
int num;
int exp;
struct ListNode *link;
} ListNode;

 

연결리스트로 표현한 다항식의 덧셈

노드를 구성했다면 다항식들을 덧셈할 때는 포인터 변수 p,q를 설정하여 연산하면 된다.

p,q가 가리키는 항의 지수에 따라 3가지로 나눠 각 항들을 덧셈할 수 있다.

 

1) 지수가 같은 경우

p,q를 더해서 0이 아니면 새로운 항을 만들어 -> 새로운 다항식에 추가(새로운 다항식 노드 만듦), p,q는 다음 항으로 이동

 

2) p의 지수 <q의 지수 / p의 지수 > q의 지수

p,q 둘 중 한쪽이 더 지수가 큰 경우에는 지수가 큰 쪽의 포인터변수를 그대로 새로운 다항식 노드에 추가한다.

이 때, 지수가 큰 쪽의 포인터변수만 다음 항으로 이동한다.

 

위의 과정들을 p혹은 q 둘 중에서 어느 하나가 NULL이 될때까지 되풀이 한다.

만약 어느 하나가 NULL이 될때 남아 있는 항들은 전부 새로운 다항식 노드로 가져오면 된다. 

 

보통은 head , tail을 갖고있는 헤더 노드를 이용하여 하나의 연결리스트를 표현 한다. 

새로운 노드를 맨마지막에 추가할 경우, 헤더 노드에 항상 마지막 노드를 가리키는 tail 포인터가 존재하기 때문에 효율적으로 추가가 가능하다.

다만 헤더노드 개념을 사용하기 위해서는 연결리스트 생성 후 초기화를 해야한다. 

 

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

typedef struct ListNode { // 노드 타입
	int coef; // 계수	
	int expon; // 지수 
	struct ListNode* link; // 
} ListNode;

// 연결 리스트 헤더
typedef struct ListType { // 연결리스트의 헤더 노드
	int size;
	ListNode* head;
	ListNode* tail;
} ListType;

// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

//  리스트 헤더 생성 함수
ListType* create() // 헤더 노드 초기화하기
{
	ListType* plist = (ListType*)malloc(sizeof(ListType));
	plist->size = 0;
	plist->head = plist->tail = NULL;
	return plist;
}

// plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수, 
// expon는 지수
void insert_last(ListType* 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->size++;
}

// list3 = list1 + list2
void poly_add(ListType* plist1, ListType* plist2, ListType* plist3)
{
	ListNode* a = plist1->head;
	ListNode* b = plist2->head;
	int sum;

	while (a && b) {
		if (a->expon == b->expon) {   // a의 차수 = b의 차수
			sum = a->coef + b->coef; // 만약 a의 차수가 b의 차수가 같아면 
			// a의 계수와 b의 계수를 더해서 list3에 새로운노드로 추가, 
			// 둘다 다음항으로 이동
			if (sum != 0) insert_last(plist3, sum, a->expon);
			a = a->link; b = b->link;
		}
		else if (a->expon > b->expon) {  // a의 차수 > b의 차수 
			insert_last(plist3, a->coef, a->expon);
			a = a->link;
		}// 만약 a의 차수가 b의 차수보다 높다면 
		// a의계수만 list3에 새로운 노드로 추가, a만 다음항으로 이동 , b는 그대로
		else {					// a의 차수 < b의 차수
			insert_last(plist3, b->coef, b->expon);
			b = b->link;
		}
	}// b의 계수만 list3에 새로운 노드로 추가, b만 다음항으로 이동

	// a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두 
	// 결과 다항식으로 복사
	for (; a != NULL; a = a->link)
		insert_last(plist3, a->coef, a->expon);
	for (; b != NULL; b = b->link)
		insert_last(plist3, b->coef, b->expon);
}

//
//
void poly_print(ListType* plist)
{
	ListNode* p = plist->head;

	printf("polynomial = ");
	for (; p; p = p->link) {
		printf("%d^%d + ", p->coef, p->expon);
	}
	printf("\n");
}

//
int main(void)
{
	ListType* list1, * list2, * list3;

	// 연결 리스트 헤더 생성
	list1 = create();
	list2 = create();
	list3 = create();

	// 다항식 1을 생성 
	insert_last(list1, 3, 12);
	insert_last(list1, 2, 8);
	insert_last(list1, 1, 0);

	// 다항식 2를 생성 
	insert_last(list2, 8, 12);
	insert_last(list2, -3, 10);
	insert_last(list2, 10, 6);

	poly_print(list1);
	poly_print(list2);

	// 다항식 3 = 다항식 1 + 다항식 2
	poly_add(list1, list2, list3);
	poly_print(list3);

	free(list1); free(list2); free(list3);
}