Polynomial

목적

다항식의 곱셈을 이용하는 프로그램을 작성한다.

자료구조

하나의 항은 coefficient 와 exponent 로 구성된다. 하나의 항(단항식)을 표현하는 자료구조는 다음처럼 구조체를 사용한다. (여기서는 지수와 밑모두 integer를 사용한다)

  struct Node {
   int coef; // 밑
   int exp; // 지수   
  };

다항식을 표현하는자료구조는 크게 두가지로 생각해 볼 수 있다. linked list 와 array 이다. 배열은 모두들 잘 알겠고 linked list 는 동적으로 storage를 할당받아 각 노드를 포인터로 연결한 자료구조를 말한다..(라고 우선 설명만 해둬야지 정확한 정의는 내리지 못하겠다..-_-). 물론 동적으로 할당받지 않고도 linked list 를 구현할수 있지만 그럴꺼면 배열로 하는게 낫지 그 노가다를 뭐하러 하나...-_-

배열을 사용한 방법

   Node expr_1[SIZE];  // 이와 같은 식으로 표현한다.
   Node expr_2[SIZE];

linked list 를 사용한 방법

   // 위의 정의한 구조체에 포인터 변수 두개가 더 필요하다.
   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 을 갖는 함수를 구현해야 한다. (이름은 달리해도 상관없다..)
   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

다음과 같은 자료의 합, 차, 곱을 리턴하는 프로그램을 작성하시오
    식1 : 2x^5 + 3x^2 - 2x + 10
    식2 : 2x^4 + x^3 - 5x^2 +3

잡담

다항식을 표현하는 클래스를 만들어서 operator overloading 을 사용해도 되겠지만 이는 위에 말한 내용을 이미 구현한 후 이걸 클래스로 포장하는거기때문에 지금수준에서는 무리라고 생각됨... - 임인택
이거 작년에 했다가 한명("영창이")만 겨우 풀었어요 저도 이거 하다 포기했고 1학년에게 넘 어려운 문제가 아닐런지...-재동