Chapter 4-2 : List(Polynomial)

예전에 배운 다항식 연산을 연결리스트로 구현하는 것입니다.

typedef struct poly_node* poly_pointer;
typedef struct poly_node {
	int coef;
	int expon;
	poly_pointer link;
}poly_node;

다항식을 계산하기 위한 리스트의 원형입니다.

coef 부분은 계수

expon 부분은 차수

link 부분은 다음 리스트를 가리킵니다.

---

리스트의 덧셈 부분입니다.

a = 3x^14 + 2x^8 + 1

b = 8x^14 + 4x^10 - 2x^8

이라고 가정하면

오른쪽 그림과 같은 모습이 됩니다.

 

poly_pointer padd(poly_pointer a, poly_pointer b) {
	poly_pointer front, rear, temp;
	int sum;
	rear = (poly_pointer)malloc(sizeof(poly_node));
	if (IS_FULL(rear)) {
		fprintf(stderr, "The memory is full\n");
		exit(1);
	}
	front = rear;

덧셈을 수행하는 함수 부분입니다.

그림에서 c는 front입니다

먼저 계산된 결과가 들어갈 rear노드를 먼저 만들어 줍니다.

그 다음 front도 똑같이 rear와 가리킵니다.

while(a&&b)
		switch (COMPARE(a->expon, b->expon)) {
		case -1: (a의 계수 < b의 계수)
			attach(b->coef, b->expon, &rear);
			b = b->link;
			break;
		case 0: (a의 계수 = b의 계수)
			sum = a->coef + b->coef;
			if (sum)attach(sum, a->expon, &rear);
			a = a->link;
			b = b->link;
			break;
		case 1: (a의 계수 > b의 계수)
			attach(a->coef, a->expon, &rear);
			a = a->link;
		}
        for (; a; a = a->link)attach(a->coef, a->expon, &rear); //남은 데이터 옮기기
	for (; b; b = b->link)attach(b->coef, b->expon, &rear);
	rear->link = NULL;
	temp = front;
	front = front->link;
	free(temp);
	return front;
}

다항식 a와 b를 비교해줍니다.

그 전에 먼저 계산된 다항식을 계속 뒤에 붙여주는 함수를 보겠습니다.

void attach(int coefficient, int exponent, poly_pointer* ptr) {
	poly_pointer temp;
	temp = (poly_pointer)malloc(sizeof(poly_node));
	if (IS_FULL(temp)) {
		fprintf(stderr, "The memory is full\n");
		exit(1);
	}
	temp->coef = coefficient;
	temp->expon = exponent;
	(*ptr)->link = temp;
	*ptr = temp;
}

임시 노드 temp를 만들어 그곳에 계산된 계수와 차수를 넣어줍니다.

(*ptr)은 결국 rear를 의미합니다.

(*ptr)->link는 rear가 가리키는 노드에 temp 데이터가 복사됩니다.

그리고 마지막에 *prt = temp 를 함으로써 rear가 temp 됩니다.

 

다 완성되면 다음과 같은 모습이 됩니다.

poly_pointer padd(poly_pointer a, poly_pointer b) {
	poly_pointer front, rear, temp;
	int sum;
	rear = (poly_pointer)malloc(sizeof(poly_node));
	if (IS_FULL(rear)) {
		fprintf(stderr, "The memory is full\n");
		exit(1);
	}
	front = rear;
	
	while(a&&b)
		switch (COMPARE(a->expon, b->expon)) {
		case -1:
			attatch(b->coef, b->expon, &rear);
			b = b->link;
			break;
		case 0:
			sum = a->coef + b->coef;
			if (sum)attack(sum, a->expon, &rear);
			a = a->link;
			b = b->link;
			break;
		case 1:
			attach(a->coef, a->expon, &rear);
			a = a->link;
		}
	for (; a; a = a->link)attach(a->coef, a->expon, &rear);
	for (; b; b = b->link)attach(b->coef, b->expon, &rear);
	rear->link = NULL;
	temp = front;
	front = front->link;
	free(temp);
	return front;
}

전체 코드입니다.

---

모든 다항식을 지우는 함수입니다.

void erase(poly_pointer* ptr) {
	poly_pointer temp;
	while (*ptr) {
		temp = *ptr;
		*ptr = (*ptr)->link;
		free(temp);
	}
}

 

 

---

Circularly linked list (원형 연결 리스트)

우리는 지금까지 노드 들을 한줄로 쭉 늘려서 맨 마지막 노드에 NULL을 표시하는 chain 형태의 연결리스트를 공부했습니다.

지금부터 볼 리스트는 맨 마지막 노드가 처음 노드를 가리키는 원형 리스트를 볼 예정입니다.

3x^14 + 2x^8 + 1

즉 오른쪽에 있는 그림과 같은 모양의

리스트를 구현할 것입니다.

 

 

원형 리스트로 구현하면 나중에 노드들을 삭제하는데 매우 효율적입니다.

 

get_node

사용할 노드를 제공합니다.

malloc 함수 대신에 사용합니다.

변수 avail이 가리키는 chain으로부터 하나의 node를 사용합니다.

이 때, 가리키는 chain이 비어 있으면 malloc함수를 사용합니다.

poly_pointer get_node() {
	poly_pointer node;
	if (avail) {
		node = avail;
		avail = avail->link;
	}
	else {
		node = (poly_pointer)malloc(sizeof(poly_node));
		if (IS_FULL(node)) {
			fprintf(stderr, "The memeory is full\n");
			exit(1);
		}
	}
	return node;
}

 

ret_node

free() 함수 대신 사용합니다.

삭제될 node를 변수 avail이 가리키는 chain에 첨가합니다.

void ret_node(poly_pointer ptr) {
	ptr->link = avail;
	avail = ptr;
}

 

cerase

*ptr node를 삭제하는 함수입니다.

void cerase(poly_pointer* ptr) {
	poly_pointer temp;
	if (*ptr) {
		temp = (*ptr)->link;
		(*ptr)->link = avail;
		avail = temp;
		*ptr = NULL;
	}
}

 

 

이 작업이 끝나면 *ptr = NULL 입니다.

 

 

 

이를 바탕으로 이전에 본 padd 함수를 원형리스트로 바꾸겠습니다.

우리는 리스트의 첫부분을 가리켜줄 head노드를 사용할 것입니다.

예를 들어 다항식이 3x^14 + 2x^8 + 1 이라고 할때,

다음과 같은

형상이 됩니다.

 

 

우리는 header 노드의 expon부분을 -1로 설정하여 진행합니다.

poly_pointer starta, c, lastc;
int sum, done = FALSE;
starta = a;
a = a->link;
b = b->link;
c = get_node();
c->expon = -1;
lastc = c;

do {
		switch (COMPARE(a->expon, b->expon)) {
		case -1:
			attatch(b->coef, b->expon, &lastc);
			b = b->link;
			break;
		case 0:
			if (starta == a) done = TRUE;
			else {
				sum = a->coef + b->coef;
				if (sum)attack(sum, a->expon, &lastc);
				a = a->link;
				b = b->link;
			}
			break;
		case 1:
			attach(a->coef, a->expon, &lastc);
			a = a->link;
		}
	} while (!done);
	lastc->link = c;

---

전체코드입니다.

poly_pointer cpadd(poly_pointer a, poly_pointer b) {
	poly_pointer starta, c, lastc;
	int sum, done = FALSE;
	starta = a;
	a = a->link;
	b = b->link;
	c = get_node();
	c->expon = -1;
	lastc = c;
	do {
		switch (COMPARE(a->expon, b->expon)) {
		case -1:
			attatch(b->coef, b->expon, &lastc);
			b = b->link;
			break;
		case 0:
			if (starta == a) done = TRUE;
			else {
				sum = a->coef + b->coef;
				if (sum)attack(sum, a->expon, &lastc);
				a = a->link;
				b = b->link;
			}
			break;
		case 1:
			attach(a->coef, a->expon, &lastc);
			a = a->link;
		}
	} while (!done);
	lastc->link = c;
}