자료구조 ¶
하나의 항은 coefficient 와 exponent 로 구성된다. 하나의 항(단항식)을 표현하는 자료구조는 다음처럼 구조체를 사용한다. (여기서는 지수와 밑모두 integer를 사용한다)
다항식을 표현하는자료구조는 크게 두가지로 생각해 볼 수 있다. linked list 와 array 이다. 배열은 모두들 잘 알겠고 linked list 는 동적으로 storage를 할당받아 각 노드를 포인터로 연결한 자료구조를 말한다..(라고 우선 설명만 해둬야지 정확한 정의는 내리지 못하겠다..-_-). 물론 동적으로 할당받지 않고도 linked list 를 구현할수 있지만 그럴꺼면 배열로 하는게 낫지 그 노가다를 뭐하러 하나...-_-
~cpp
struct Node {
int coef; // 밑
int exp; // 지수
};
다항식을 표현하는자료구조는 크게 두가지로 생각해 볼 수 있다. linked list 와 array 이다. 배열은 모두들 잘 알겠고 linked list 는 동적으로 storage를 할당받아 각 노드를 포인터로 연결한 자료구조를 말한다..(라고 우선 설명만 해둬야지 정확한 정의는 내리지 못하겠다..-_-). 물론 동적으로 할당받지 않고도 linked list 를 구현할수 있지만 그럴꺼면 배열로 하는게 낫지 그 노가다를 뭐하러 하나...-_-
- 배열을 사용한 방법
~cpp Node expr_1[SIZE]; // 이와 같은 식으로 표현한다. Node expr_2[SIZE];
- linked list 를 사용한 방법
~cpp // 위의 정의한 구조체에 포인터 변수 두개가 더 필요하다. struct Node { int coef; int exp; Node *prev; Node *next; }; Node *n1 = new Node; Node *n2 = new Node; n1->next = n2; n1->prev = NULL; n2->next = NULL; n2->prev = n1;
이 방법을 사용할때 발생할수 있는 문제점은 memory leakage (메모리 누수)이다. Java같은 경우는 쓰레기 수집기가 있지만 c 는 코더(-_-)가 일일이 사용되지 않는 자원을 회수해줘야 한다. 그렇지 않으면 그 자원을 다시 사용할 수 없게 된다.
specification ¶
다음과 같은 prototype 을 갖는 함수를 구현해야 한다. (이름은 달리해도 상관없다..)
~cpp Node* mul(Node *n1, Node *n2); // 두 다항식의 곱을 표현하는 새로운 다항식을 리턴한다. Node* add(Node *n1, Node *n2); // 두 다항식의 합을 표현하는 새로운 다항식을 리턴한다. Node* add(Node *n1, Node *n2); // 두 다항식의 차를 표현하는 새로운 다항식을 리턴한다. /* 문제점 : 다음과 같은 경우는 어떻게 처리해야 할까? n1 = mul(n1, n2); // n1 이 중복 사용되었다.. */ Node* input(); // 사용자에게 값을 입력받아 새로운 다항식을 생성하여 리턴한다. void delete(Node *node) // 다항식을 삭제한다. void sort(Node *node) // 다항식을 내림차순으로 정리한다.
input data ¶
다음과 같은 자료의 합, 차, 곱을 리턴하는 프로그램을 작성하시오
~cpp
식1 : 2x^5 + 3x^2 - 2x + 10
식2 : 2x^4 + x^3 - 5x^2 +3
