[자료구조] 원형 연결 리스트 | 가용 리스트 - 다항식 연산(덧셈, 곱셈)(C언어)

저번 포스트에선 단순 연결 리스트를 알아보았다.

이어서 이번에는 원형 연결 리스트를 이용해 다항식 연산을 구현할 것임!

 

과제랑 개인 공부 덕분에 매우 바빠서 비교적 쉬운 이번 포스트는 빠르게 해결하자.

이번 내용이 이해가 잘 안된다면 https://joyerim.tistory.com/4를 본다면 이해가 쉬울 것이다.

 

원형 연결 리스트

사실 원형 연결 리스트는 매우 간단하다.

그냥 마지막 노드의 link가 첫번째 노드를 가리키면 된다.

가용 노드 리스트

연결 리스트를 이용해서 다항식과 같은 프로그램을 구현할 때, 노드의 할당과 삭제가 자주 일어나기 때문에 시스템 부하가 걸릴 수도 있다.

이때, malloc()과 free() 함수의 호출 빈도수를 줄이기 위해 가용 공간 리스트를 사용한다.

 

가용 노드 리스트 사용 방법 :

삭제할 노드를 가용 노드 리스트에 저장하고, 할당할 노드를 가용 노드 리스트에서 가져온다.

그리고 마지막에 가용 노드 리스트의 노드들을 free() 해주면 된다!~!

 

이제 바로 구현을 해보자.

구현

다항식의 구조체는 아래와 같다.

typedef struct polyNode* polyPointer;
typedef struct polyNode {
	float coef; // 계수
	int expon; // 지수
	polyPointer link;
} polyNode;

다항식의 형태는 아래와 같다.

첫번째 노드에는 계수와 지수에 -1를 각각 넣어 시작과 끝을 표현한다.

이번 포스트에서 구현할 함수들이다.

polyPointer getNode(); // 사용할 노드를 제공하는 함수
void retNode(polyPointer node); // 가용 리스트에 노드를 변환하는 함수
void cerase(polyPointer* ptr); // 원형 리스트의 제거하는 함수
void attach(float coefficient, int exponent, polyPointer* ptr); // 원형 연결 리스트의 끝에 노드를 첨가

polyPointer create_polynomial(); // (계수, 지수)의 쌍을 입력받아 원형 연결 리스트로 구현하는 함수
void print_polynominal(polyPointer C); // 원형 연결 리스트를 출력하는 함수

polyPointer cpadd(polyPointer A, polyPointer B); // 다항식 덧셈 함수
polyPointer cpmul(polyPointer A, polyPointer B); // 다항식 곱셈 함수
polyPointer single_cpmul(polyPointer Ai, polyPointer B); // A의 항 하나와 B의 다항식을 곱하는 함수

 

우선, 가용 노드 리스트와 관련된 함수들을 구현하자.

avail은 가용 리스트의 첫 번째 노드를 가리키는 포인터이다.

polyPointer avail = NULL;

 

1️⃣ 가용 노드 리스트에서 사용할 노드 반환하기

polyPointer getNode() {
	polyPointer node;
	if (avail) { // avail가 빈 리스트가 아니라면
		node = avail;
		avail = avail->link;
	}
	else { // avail가 빈 리스트라면
		node = (polyPointer)malloc(sizeof(polyNode));
	}
	return node;
}

 

2️⃣ 가용 리스트에 노드를 반환하기

void retNode(polyPointer node) {
	node->link = avail;
	avail = node;
}

 

3️⃣ 원형 리스트를 가용 리스트에 반환하기

void cerase(polyPointer* ptr) {
	polyPointer temp;
	if (*ptr) { // *ptr가 빈 리스트가 아니라면
		temp = (*ptr)->link; // temp는 *ptr의 두번째 노드를 가리킴
		(*ptr)->link = avail; // *ptr의 첫번째 노드의 link는 avail의 첫번째 노드를 가리킴
		avail = temp; // avail은 *ptr의 두번째 노드를 가리킴
		*ptr = NULL; // 빈 리스트를 가리킴
		// *ptr의 두번째 노드부터 첫번째 노드까지 avail의 앞 쪽 노드에 삽입되는 것임!
	}
}

 

4️⃣ 원형 연결 리스트의 끝에 노드 삽입하기

*ptr은 마지막 노드를 가리키는 포인터이다.

void attach(float coefficient, int exponent, polyPointer* ptr) {
	polyPointer temp = getNode();

	temp->coef = coefficient; 
	temp->expon = exponent;
	temp->link = (*ptr)->link; // 첫번째 노드와 연결
	(*ptr)->link = temp;
	*ptr = temp;
}

 

5️⃣ (계수, 지수)의 쌍을 입력받아 원형 연결 리스트로 구현하기

갑자기 뜬금없는 이야기인데, 포스트 작성하면서 코드의 개선을 이뤄냈다.

 

<수정 전>

polyPointer create_polynomial() {
	polyPointer head = getNode();
	polyPointer temp;
	float coef;
	int expon;

	head->coef = -1;
	head->expon = -1;
	head->link = head;

	temp = head;

	while (true) {
		printf("다항식의 항을 입력하세요. (coef expon) : ");
		scanf("%f %d", &coef, &expon);
		if (coef == -1 && expon == -1) { // -1 입력 시 종료
			temp->link = head;
			break;
		}
		attach(coef, expon, &temp);
	}
	return head;
}

 

<수정 후>

polyPointer create_polynomial() {
	polyPointer head = getNode();
	float coef;
	int expon;

	head->coef = -1;
	head->expon = -1;
	head->link = head;

	while (true) {
		printf("다항식의 항을 입력하세요. (coef expon) : ");
		scanf("%f %d", &coef, &expon);
		if (coef == -1 && expon == -1) { // -1 입력 시 종료
			break;
		}
		attach(coef, expon, &head);
	}
	return head->link;
}

 

차이점이 보이시나요?

단순 연결 리스트라면 head와 temp를 각각 다뤄야하지만

원형 연결 리스트니까 마지막 노드를 가리키는 head 하나만으로 구현 가능하다. 킼

마지막에 반환할 때, 마지막 노드의 link인 첫 번째 노드를 반환해주면 된다.

 

6️⃣ 원형 연결 리스트 출력하기

temp는 첫 번째 노드는 건너뛰고 두 번째 노드부터 쭉 출력한다.

temp가 첫 번째 노드를 가리키기 전까지!

void print_polynominal(polyPointer C) {
	polyPointer temp;
	temp = C->link;
	printf("\tcoef\texpon\n");
	while (temp != C) {
		printf("\t%.2f\t%d\n", temp->coef, temp->expon);
		temp = temp->link;
	}
}

 

6️⃣ 다항식 덧셈하기

자, 이제 본격적으로 연산을 시작해보자.

참고로 이 프로그램은 다항식이 내림차순으로 정렬된 것을 가정한다.

 

대략적인 알고리즘

1. A가 가리키는 지수와 B가 가리키는 지수를 비교한다.

2. B가 클 경우 B의 노드를 C에 더한다. 이후 B는 다음 노드로 이동한다.

3. 반대로 A가 클 경우 A의 노드를 C에 넣는다. 이후 A는 다음 노드로 이동한다.

4. A와 B가 같을 경우 A와 B의 계수를 더한 값을 C에 넣는다.

 

A가 먼저 startA로 돌아온 경우, 당연히 B는 A의 첫 번째 노드의 지수인 -1보다 크므로

B가 첫 번째 노드로 갈 때까지 case -1를 실행한다.

이후 case 0을 실행하여 done는 true가 되고 반복문은 종료한다.

 

반대로 B가 먼저 끝난 경우, 마찬가지로 A가 첫 번째 노드로 갈 때까지 case 1를 실행하며

이후 case 0을 실행하여 done는 true가 되고 반복문은 종료한다.  

polyPointer cpadd(polyPointer A, polyPointer B) { // 다항식 덧셈 함수
	polyPointer startA, C, lastC;
	int sum, done = false;

	startA = A;
	A = A->link;
	B = B->link;
	C = getNode();

	C->coef = -1;
	C->expon = -1;
	C->link = C;
	lastC = C;

	do {
		switch (COMPARE(A->expon, B->expon)) {
		case -1: // A->expon < B->expon
			attach(B->coef, B->expon, &lastC);
			B = B->link;
			break;
		case 0: // A->expon == B->expon
			if (startA == A) done = true;
			else {
				sum = A->coef + B->coef;
				if (sum) attach(sum, A->expon, &lastC);
				A = A->link; B = B->link;
			}
			break;
		case 1: // A->expon > B->expon
			attach(A->coef, A->expon, &lastC);
			A = A->link;
		}
	} while (!done);

	return C;
}

 

7️⃣ 다항식 곱셈하기

곱셈의 대략적인 알고리즘

A의 항 하나와 B 다항식을 곱한 다항식 Ci를 결과값 C에 더한다.

위의 과정을 A의 항을 다 돌 때까지 반복!

 

위의 내용을 이해하셨다면 쉽게 이해할 수 있을 것이다.

polyPointer cpmul(polyPointer A, polyPointer B) { // 다항식 곱셈 함수
	polyPointer C, startA, lastC;
	int i = 1;
	startA = A;
	A = A->link;

	C = getNode();
	C->coef = -1;
	C->expon = -1;
	C->link = C;
	lastC = C;

	while (true) {
		if (startA == A) break;
		polyPointer Ci = single_cpmul(A, B);
		A = A->link;

		printf("singul_mul - C%d(x)\n", i);
		print_polynominal(Ci);

		C = cpadd(C, Ci);

		i++;
	}
	return C;
}

polyPointer single_cpmul(polyPointer Ai, polyPointer B) { // A의 항 하나와 B의 다항식을 곱하는 함수
	polyPointer C, startB, lastC;
	
	startB = B;
	B = B->link;
	
	C = getNode();
	C->coef = -1;
	C->expon = -1;
	C->link = C;
	lastC = C;

	while (true) {
		if (startB == B) break;
		attach(Ai->coef * B->coef, Ai->expon + B->expon, &lastC);
		B = B->link;
	}

	C = lastC->link;

	return C;
}

 

전체 코드는 아래 GitHub에 있으니 필요하시다면 참고하세요 !~!

// 추가 예정

 

Reference

C로 쓴 자료구조론, 이석호