[Data Structure] 연결 리스트의 다항식 표현

연결 리스트의 다항식 표현

연결 리스트의 각 노드가 한 개의 항을 표현하게 하면 노드를 이어 붙여 다항식을 표현할 수 있다.

Term 구조체

각 항을 나타내기 위해 구조체를 사용

• 계수
• 지수
• Set 함수: 구조체의 값을 설정

// 각 항을 나타내는 구조체
struct Term
{
    int coef; // 계수
    int exp; // 지수
    Term Set(int c, int e)
    {
        coef = c;
        exp = e;
        return *this;
    }
};

연결 리스트

단순 연결 리스트를 사용한다. 각 노드는 data(coef, exp)와 next로 구성된다.

SinglyLinkedList<Term> poly; // 다항식 => data(coef, exp), next로 구성

다항식 클래스

다항식을 표현하기 위해 LinkedPolynomial 클래스를 만든다. LinkedPolynomial 클래스는 다음과 같은 기능을 갖는다.

• 다항식 출력

// 다항식 출력 메서드
void Print()
{
    Node<Term>* current = poly.GetHead();
    bool isFirst = true;

    // 리스트의 처음부터 마지막까지 이동하며 출력
    while (current) {
        if (current->data.coef == 0) // 항의 계수가 0이면 다음 항으로 스킵
        {
            current = current->next;
            continue;
        }

        if (!isFirst && current->data.coef > 0) // 처음으로 출력하는 게 아니고, 계수가 0 이상이면 + 출력
            std::cout << "+";

        if (current->data.coef != 1 || current->data.exp == 0) // 계수가 1이거나 지수가 0이라면 계수를 출력
            std::cout << current->data.coef;

        if (current->data.exp > 0)  // 지수가 0 초과면 미지수 x를 출력하고, 1보다 큰 경우 '^지수'를 추가적으로 출력한다.
        {
            std::cout << "x";
            if (current->data.exp > 1)
                std::cout << "^" << current->data.exp;
        }

        isFirst = false; // 한 번이라도 출력하면 처음 출력 여부 false로
        current = current->next; // 다음 항으로 이동
    }

    if (isFirst) // 모든 항이 0인 경우
        std::cout << "0";

    std::cout << "\n";
}

• 항 추가

// 새로운 항을 추가하는 메서드
void AddTerm(int coef, int exp) {
    Term temp; // 새로 추가할 항
    Node<Term>* newTerm = new Node(temp.Set(coef, exp)); // 새로운 노드 생성
    poly.InsertRear(newTerm); // 다항식에 맨 뒤에 추가
}

• 사칙연산 (예제에서는 덧셈만 구현)

// 다항식 b를 poly와 더함
// 연산자 오버로딩 사용
LinkedPolynomial operator+(LinkedPolynomial& b)
{
    Term temp;
    Node<Term>* aPointer = poly.GetHead(); // 두 식의 head부터 시작
    Node<Term>* bPointer = b.poly.GetHead();
    LinkedPolynomial result;

    // aPointer와 bPointer가 모두 nullptr가 아닌 동안
    int aExp, bExp, aCoef, bCoef;
    while (aPointer && bPointer)
    {
        aExp = aPointer->data.exp;
        bExp = bPointer->data.exp;
        aCoef = aPointer->data.coef;
        bCoef = bPointer->data.coef;

        if (aExp == bExp) // 지수가 같은 경우
        {
            int coefSum = aCoef + bCoef; // 계수 더함
            if (coefSum) // 계수가 0이 아니면
            {
                Node<Term>* newTerm = new Node(temp.Set(coefSum, aExp));
                result.poly.InsertRear(newTerm); // 새롭게 항 추가
            }
            aPointer = aPointer->next; // 둘 다 다음 항으로 이동
            bPointer = bPointer->next;
        }
        else if (aExp > bExp) // a의 항이 더 크다면
        {
            Node<Term>* newTerm = new Node(temp.Set(aCoef, aExp));
            result.poly.InsertRear(newTerm); // 새롭게 항 추가
            aPointer = aPointer->next; // a만 다음 항으로 이동
        }
        else // aExp < bExp
        {
            Node<Term>* newTerm = new Node(temp.Set(bCoef, bExp));
            result.poly.InsertRear(newTerm);
            bPointer = bPointer->next;
        }
    }

    // 나머지가 있는 경우 모두 poly에 집어넣음
    while (aPointer)
    {
        aExp = aPointer->data.exp;
        aCoef = aPointer->data.coef;
        Node<Term>* newTerm = new Node(temp.Set(aCoef, aExp));
        result.poly.InsertRear(newTerm);
        aPointer = aPointer->next;
    }

    while (bPointer)
    {
        bExp = bPointer->data.exp;
        bCoef = bPointer->data.coef;
        Node<Term>* newTerm = new Node(temp.Set(bCoef, bExp));
        result.poly.InsertRear(newTerm);
        bPointer = bPointer->next;
    }

    return result; // 더한 결과를 담은 다항식 리턴
}

실행

#include <iostream>
#include "LinkedPolynomial.hpp"

using namespace std;

int main()
{
    // 첫 번째 다항식: 3x^2 + 2x + 1
    LinkedPolynomial poly1;
    poly1.AddTerm(3, 2); // 3x^2
    poly1.AddTerm(2, 1); // 2x
    poly1.AddTerm(1, 0); // 1

    cout << "첫 번째 다항식: ";
    poly1.Print();

    // 두 번째 다항식: 2x^2 - 2x + 3
    LinkedPolynomial poly2;
    poly2.AddTerm(2, 2);  // 2x^2
    poly2.AddTerm(-2, 1); // -2x
    poly2.AddTerm(3, 0);  // 3

    cout << "두 번째 다항식: ";
    poly2.Print();

    // 두 다항식의 덧셈 수행: (3x^2 + 2x + 1) + (2x^2 - 2x + 3) = 5x^2 + 4
    LinkedPolynomial result = poly1 + poly2;

    cout << "덧셈 결과: ";
    result.Print();
    
    return 0;
}

첫 번째 다항식: 3x^2+2x+1
두 번째 다항식: 2x^2-2x+3
덧셈 결과: 5x^2+4