Linked List를 이용한 다항식 덧셈연산 (Polynomial Add)

전체 소스 및 보고서 다운받기

다항식을 Linked LIst를 이용하여 표현하기 위해 다음과 같은 node를 구성하였다.

typedef struct node { int coef; // 계수 int exp; // 지수 struct node *next; } node;

즉 2x^3 이라는 항이 있다면 node에 coef = 2; exp = 3; 이 저장되는 방식이다.

이러한 다항식을 List로 표현해 보았다.

값으로 0, 0을 가지는 header노드와 -1, -1을 가지는 tail 노드를 포함하여 List형태로 표현한다.

node* makePolynomial(int _index) { node* h = (node*)malloc(sizeof(node)); node* s; int i, rannum, ranCoef, coefNum; h->coef = 0; h->exp = 0; h->next = NULL; // header를 초기화 시켜준다. coef, exp는 0을 저장. next는 NULL로 초기화 한다. for(i=_index;i>=0;i--) { // 최고차항의 지수인 _index부터 지수가 0이 될때까지 반복해준다. rannum = (rand() % 100) + 1; // 1 - 100 까지의 Random Number 생성 // <- 70%의 확률로 항의 존재유무를 결정한다. if(rannum >= 70) // rannum 이 70이상일 경우에만 노드를 생성한다. (해당 차수의 항을 생성) { ranCoef = (rand() % 10) + 1; // 1-10 범위의 계수 생성 coefNum = SelectPlusMinus(ranCoef); // 생성된 계수를 랜덤하게 양수 또는 음수로 반환시켜 저장한다. s = newnode(coefNum,i); // 계수와 지수를 넘겨주어 node를 생성한다 LinkNode(h,s); // head와 생성된 노드를 넘겨주어 head에 연결된 Linked List에 노드를 연결한다. } else // 70보다 작을 경우 continue 시켜준다. { continue; } // 70%의 확률로 항의 존재유무를 결정한다 -> } // <- tail 생성 s = newnode(-1,-1); LinkNode(h,s); // tail 생성 -> return h; }

makePolynomial() 이라는 node* type의 함수를 이용하여 다항식을 생성해 보았다.

여기서 조건은 메인함수에서 최고차항의 지수를 입력받고, 항이 생성되는 조건은 70%의 확률로 항의 존재유무를 결정한다.

또한 SelectPlusMinus() 라는 함수를 이용하여 랜덤하게 항의 계수가 양수가 될수도있고, 음수가 될수도 있게 하였다.

이와 같은 방식으로 두개의 다항식을 생성한 뒤 두 다항식을 더해주었다.

다항식의 덧셈을 할 때에는 각각의 다항식에서 현재 위치를 저장할 포인터 변수가 필요하다.

덧셈과정은 다음과 같다.

A와 B라는 다항식이 있다면 제일먼저 P와 Q라는 포인터 변수가 제일 첫번째 항을 가르키고 있게 만든다.

그리고 P위치의 exp값과 Q위치의 exp값, 즉 각 현재위치 항의 차수를 비교하여 연산을 다르게 해준다.

1. P->exp == Q->exp 일때 (같은 차수의 항일 때)

두 계수를 더해서 0이 아니면 더한값을 새로운 다항식인 C에 저장하고, 만약 0이 된다면 항이 사라지는 것이기 때문에

P와 Q포인터를 다음 포인터로 증가시켜준다.

2. P->exp < Q->exp 일 때, 현재 P와 Q위치에서 B항의 차수가 더 클 때

Q가 가리키고 있는 항을 C에 노드로 만들어 주고 연결한다. 이후에 Q만 다음 포인터로 이동시킨다.

3. P->exp > Q->exp 일 때, 현재 P와 Q위치에서 A항의 차수가 더 클 때 

P가 가리키고 있는 항을 C에 노드로 만들어 주고 연결한다. 이후에 P만 다음 포인터로 이동시킨다.

위와 같은 과정을 통해 프로그램을 실행시켜 확인해 보면 다음과 같은 결과를 제대로 얻어 낼 수 있었다.

전체 소스 및 보고서 다운받기