[C언어] 연결리스트 - 다항식(1)

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

이번 포스팅에서는 연결 리스트를 이용하여 다항식을 구현하는 방법에 대해 알아보겠습니다.

특징1

특징2

연결 리스트를 통해 구현하려는 다항식의 특성은 위와 같습니다.

 

---

struct term	// 다항식에서 차수마다 항을 구성하는 term 구조체
{
	int coef; // 계수
	int expo; // 지수, 차수
	struct term* next;
};

typedef struct term Term;

typedef struct Polynomial 	// 함수의 이름과 시작 주소를 저장하는 Polynomial 구조체
{
	char name;		// 다항식의 이름
	Term* first;	// 다항식 첫번째 항의 주소
	int size;		// 항의 개수
} Polynomial;

Polynomial* polys[MAX_POLYS];	// 다항식들에 대한 포인터의 배열
int n = 0;

우선 다항식에서 각 항을 구성하는 Term 구조체와, 다항식 전체의 이름과 첫 번째 주소를 가지고 있는 Polynomial 구조체를 만들었습니다.

동적 할당으로 객체를 생성하는 함수

연결 리스트는 동적 할당을 통해 각각의 노드를 구성합니다. 때문에 각 노드를 생성할 때마다 malloc을 통해 동적 할당을 해야 하는데, 이번 다항식 예제에서는 동적 할당을 하는 과정을 함수로 구현하여 이용하겠습니다.

---

항을 추가하는 add_term 함수의 구조

단방향 연결 리스트에서는 특정 인덱스의 이전 노드 주소를 알고 있어야 함

이전의 포스팅에서 많이 다뤘던대로, 단방향 연결 리스트에서 노드를 삽입하거나 제거하기 위해선 해당 노드 이전 노드의 주소 역시 필요합니다. 때문에 이 다항식 연결 리스트 역시 두 개의 포인터를 이용하여 하나의 노드는 삭제하거나 삽입할 노드의 위치를 탐색하고, 나머지 하나의 노드는 그 뒤에서 이전의 주소를 저장하는 방법으로 자리를 찾습니다.

void add_term(int c, int e, Polynomial* poly)
{
	if (c == 0)
		return;
	Term* p = poly->first, * q = NULL; // q가 p보다 한 칸 앞섬
	while (p != NULL && p->expo > e)
	{
		q = p;
		p = p->next;
	}
	if (p != NULL && p->expo == e)
	{
		p->coef += c;
		if (p->coef == 0)	// 두 계수를 합쳐서 0이 나옴
		{
			if (q == NULL)
				poly->first = p->next;	// 최고차항이 0일 때. p가 first, q는 NULL
			else
				q->next = p->next;	// p를 삭제하는 것이라 q의 next를 p의 next로 변경
			poly->size--;
			free(p);	// p 노드는 더 이상 필요하지 않음
		}
		return;
	}

	Term* term = create_term_instance(); // 새로운 항 생성
	term->coef = c;
	term->expo = e;

	if (q == NULL) // 맨 앞에 삽입
	{
		term->next = poly->first;
		poly->first = term;
	}
	else
	{
		term->next = p;
		q->next = term;
	}
	poly->size++;		
}