[자료구조] 다항식 연산 방법에 대한 해설

 

 

다항식 연산 방법에 대한 해설을 진행하도록 하겠습니다.

 

 

 

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

typedef struct ListNode {
	int coef;
	int expon;
	struct ListNode *link;
} ListNode;

 

 

먼저 연결리스트의 노드 형태를 정의합니다. 노드 형태는 두개의 값이 들어가고 (coef, expon) 하나의 링크로 구성되어있습니다. 즉 단순연결리스트입니다.

 

기본적인 단순연결리스트와 구조는 동일하지만 데이터가 하나더 추가되었기 때문에 노드에 추가하였습니다.

 

만약 담아야할 데이터가 많다면 구조체로 묶어서 관리하는 것이 수월합니다.

 

typedef struct ListHeader {
	int length;
	ListNode *head;
	ListNode *tail;
} ListHeader;

 

여기서는 ListHeader를 정의하여 연결리스트를 구현합니다. 위의 형태는 큐의 연결된 형태와 동일하기 때문에 어렵지 않게 이해하실 수 있습니다. 추가적으로 길이에 대한 부분은 length라는 변수를 만들어 사용하였습니다. 만약에 기본적인 연결리스트에 길이에 대한 정보가 필요하다면 위 처럼 작업하시면 도움이 됩니다.

 

// 초기화 함수
void init(ListHeader *plist)
{
	plist->length = 0;
	plist->head = plist->tail = NULL;
}

 

리스트 초기화 함수입니다. C언어의 구조체는 초기화가 불가능하기 때문에 따로 초기화 함수를 만들어서 사용하셔야 합니다. 그렇기 때문에 초기화 함수에서 길이를 초기화 시키고 head와 tail을 NULL 로 초기화 시켰습니다. 

 

또한 당연히 main에 있는 지역변수를 간접 참조해서 초기화 해야하는 부분이기 때문에 매개변수는 포인터로 작성해야 합니다.

 

// plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수, expon는 지수
void insert_node_last(ListHeader *plist, int coef, int expon)
{
	ListNode *temp = (ListNode *)malloc(sizeof(ListNode));
	if( temp == NULL ){
		fprintf(stderr,"메모리 할당 에러\n");
		exit(1);
	}
	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->length++;
}

 

연결리스트에 데이터를 추가하는 함수입니다. 여기서는 노드에 데이터가 하나 많아졌기 때문에 새롭게 노드를 삽입하는 함수를 제작하셔야 합니다. 전체적인 형태는 큐의 연결된 형태에서 tail 부분에 데이터를 추가시키는 것과 동일한 것을 확인해보실 수 있습니다. 

 

만얀 연결리스트가 공백상태일 경우에는 연결리스트의 head와 tail을 동시에 세팅시켜주셔야하고, 만약 공백리스트가 아닐 경우에는 tail에만 추가시키면 됩니다.

 

 

void poly_add(ListHeader *plist1, ListHeader *plist2, ListHeader *plist3 )
{
 ListNode *a = plist1->head;
 ListNode *b = plist2->head;
 int sum;
 while(a && b){
   if( a->expon == b->expon ){
	sum = a->coef + b-> coef;
    if( sum != 0 ) insert_node_last(plist3, sum, a->expon);
	a=a->link; b=b->link; 
   }
   else if( a->expon > b->expon ){
    insert_node_last(plist3, a->coef, a->expon);
	a=a->link;
   }
   else {
	insert_node_last(plist3, b->coef, b->expon);
	b=b->link; 
   }
 }
  // a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두 
  // 결과 다항식으로 복사
 for( ; a != NULL; a=a->link) 
   insert_node_last(plist3, a->coef, a->expon);
 for( ; b != NULL; b=b->link) 
   insert_node_last(plist3, b->coef, b->expon);
}

 

poly_add 함수가 실질적으로 리스트를 연산하고 연산 결과를 도출해내는 함수입니다.

상단에 나와있는 조건들을 if문 코드로 옮긴 것을 확인해보실 수 있습니다. 여기서는 링크의 이동에서만 신경써주시면 됩니다. 1번의 경우에는 두개 리스트 모두 다음 노드로 이동하셔야 하고, 2번은 후자의 리스트만 다음 노드로 이동해야 하며, 3번의 경우는 전자의 리스트만 다음 노드로 이동하여야 합니다. 또한 둘중에 하나라도 리스트가 먼저 끝난다면, 나머지 남은 데이터들을 결과리스트로 이동해주셔야 합니다.

 

void poly_print(ListHeader *plist)
{
	ListNode *p=plist->head;
	for(;p;p=p->link){
		printf("%d %d\n", p->coef, p->expon);
	}
}

 

다항식을 출력하는 구문이기 때문에 추가 설명은 진행하지 않도록 하겠습니다.

 

 

 

main()
{
	ListHeader list1, list2, list3;
		
	init(&list1);
	init(&list2);
	init(&list3);


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

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

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

 

 

 

여기까지 다항식 연산 관련 해설을 마치도록 하겠습니다.