[자료구조] 단순 연결리스트를 이용한 다항식과 계산 구현

단순 연결리스트를 이용한 다항식과 계산 구현

8x^12 + (-3x^10) + 10x^6과 같이 여러개인 수식을 다항식이라 부릅니다. 단순 연결리스트를 통해서 다항식을 구현할 수 있습니다.

 

다항식 구현에는 특수한 헤더 노드가 추가로 사용됩니다. 헤더 노드의 헤드는 리스트의 앞부분을, 테일은 리스트의 끝부분을 가리키도록 합니다.

 

#include <stdio.h>
#include <malloc.h>

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

// 리스트 헤더의 타입
typedef struct {
	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;
			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;
		}
		else {				// a의 차수 < b의 차수
			insert_last(plist3, b->coef, b->expon);
			b = b->link;
		}
	}
	for (; a != NULL; a = a->link)  // a중 남아있는 항들을 모두 결과 다항식으로 복사
		insert_last(plist3, a->coef, a->expon);
	for (; b != NULL; b = b->link)  // b중 남아있는 항들을 모두 결과 다항식으로 복사
		insert_last(plist3, b->coef, b->expon);
}
// 리스트 출력
void poly_print(ListType* plist)
{
	ListNode* p;

	printf("polynomial = ");
	for (p = plist->head; p != NULL; 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);
}

/* 실행결과
polynomial = 3^12 + 2^8 + 1^0 +
polynomial = 8^12 + -3^10 + 10^6 +
polynomial = 11^12 + -3^10 + 2^8 + 10^6 + 1^0 +
*/

 

다항식 구현에 관련된 문제입니다. 문제를 먼저 풀어보시고 풀이를 확인해보시기 바랍니다

특정한 실수 x에 대하여 다항식의 값을 계산하는 함수를 작성하라

double poly_eval(ListType* plist, int x)
{
	ListNode* p;
	double result = 0;

	for (p = plist->head; p != NULL; p = p->link) {
		double temp = p->coef * pow(x, p->expon);
		result += temp;
	}
	return result;
}

plist를 도는 p의 계수와 특정 x값에서의 차수를 거듭제곱한 값을 곱해서 임시 변수에 넣고 그 값을 결괏값에 더해주면서 p가 NULL을 만날때까지 반복합니다. 반복이 끝나면 더한 결괏값을 반환합니다.