이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 구조체와 함수)

[연결 리스트]

1. 여러가지 연결 리스트 개념과 코드 : hello70825.tistory.com/158

2. 여러가지 연결 리스트를 이용한 알고리즘 문제 풀이: hello70825.tistory.com/159

3. 이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 구조체와 함수): hello70825.tistory.com/160

4. 이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 클래스와 operator): hello70825.tistory.com/219

5. 원형 연결 리스트 - 다항식의 연산(덧셈, 곱셈: 클래스와 operator, 반복자): hello70825.tistory.com/223

 

[참고]

기능 참조 - kwondongju.tistory.com/19

==================================================================

 

코드 정리(맨 아래에 전체 코드 있음)

typedef struct Node -> 단항식 구조체

typedef struct Polynomial -> 다항식 구조체

Node* create_node -> 단항식 구조체 생성

Polynomial* create_poly -> 다항식 구조체 생성

void insert_node -> Polynomial에 Node를 넣을 때, 내림차순으로 넣을 수 있도록 하는 함수

void push_back -> Polynomial에 Node를 넣을 때, 넣는 Node는 무조건 Polynomial이 가지고 있는 최소 차수의 단항식보다 작은 차수의 단항식을 넣을 때(= Node가 무조건 꼬리노드일 때) 쓰이는 함수

void addition -> 다항식끼리의 덧셈에 쓰이는 함수

void multiplication -> 다항식끼리의 곱셈에 쓰이는 함수

void print -> 다항식 출력

 

int main -> 단항식 값 입력, 각각 다항식 출력, 다항식끼리 덧셈과 곱셈을 적용하여 새로 만들어진 다항식 출력

===================================================================

 

 

 

 

2번까지 했으면 다항식의 연산은 쉽습니다.

1번, 2번에 나온 코드와 다른점은 class대신 struct를 사용해볼 것입니다.

class로 만들고 싶으면 struct랑 따로 함수 구현한 것을 필요한 것끼리 나눠서 class에 전부 넣으면 되니까 별 상관은 없을 것 같아요.

 

먼저 다항식을 여러개 만들 것이므로 Polynomial이라는 구조체를 만들어줍니다. 그리고 이 구조체 안에 머리노드(head)와 꼬리노드(tail)의 주소를 저장할 포인터 변수를 만들어줍니다.

 

 

그리고 다항식은 단항식들의 모임이므로 단항식 구조체를 만들어주면 됩니다. 단항식(Node)에 들어가는 값은 단항식의 계수를 넣어야하므로 coef(coefficient)를 넣어주고, 단항식의 지수를 넣어줘야하므로 expo(exponential)를 넣어주고, 다음 단항식의 주소인 next를 넣어주면 됩니다.

 

여기까지는 기본 구조체의 설명인데 여기까지 코드로 구현하면 아래와 같습니다.

 

각 구조체를 새로 만들어주는 함수도 만들어줍니다.

 

 

 

 

이제 다항식과 단항식 구조체를 만들어줬으니 단항식을 다항식에 넣는 함수를 만들어봅시다

단항식을 다항식에 넣는 방법은 아래 사진과 같습니다.

 

 

이 부분은 연결 리스트의 insert 함수와 비슷합니다. 다만 다항식은 차수가 내림차순으로 적혀져 있으므로 코드를 거기에 맞게 함수를 짜야해요

 

먼저 다항식에 단항식을 넣는 방법은 2가지로 나뉩니다.

다항식 구조체에 단항식이 없거나, 다항식 구조체에 이미 단항식이 있거나로 나뉘어요

단항식이 없다면 다항식의 머리노드와 꼬리노드는 무조건 지금 넣는 단항식이기 떄문에 head = tail = new_node가 됩니다.

다항식에 단항식 노드들이 있다면 일단 머리노드부터 꼬리노드까지 훑어주는 while문을 만들어줍니다.

 

그리고 다항식안에서 같은 차수의 단항식이 이미 있는지, 같은 차수의 단항식이 없는지 확인합니다.

같은 차수의 단항식의 차수가 현재노드의 차수(dest -> expo)와 같다면 다항식에 있던 같은 차수의 노드에 다항식에 넣으려는 단항식의 차수를 더해줍니다.

하지만 다항식의 노드에 없는 차수라면 while문을 돌려서 노드를 추가해야합니다.

 

다른 블로그들 보니까 입력값을 내림차순으로 받아서 맨 뒤에 노드를 변경해서 꼬리노드만 업데이트하는 방식이던데, 이러면 재미가 없으니 단항식의 차수를 뒤죽박죽으로 받아도 상관이 없도록 만들어 보았습니다.

이렇게 구현을 한다면 이중 연결 리스트는 상관없겠지만, 일반 연결 리스트는 헤드노드보다 차수가 큰지, 헤드노드보다 차수가 낮은지 확인 후 각각 따로 구현해야합니다.

 

왜냐하면

 

위와 같은 사진에서 x²을 넣을 때는 이미 다항식들이 내림차순으로 정렬되어 있으므로 현재 훑고 있는 노드(dest)와 dest의 다음노드 사이에 있는지 확인하면 되는데, 이러면 헤드노드보다 차수가 큰지 비교하지 못하고 넘어가기 때문에 while문으로 훑기전에 if문으로 확인을 해줘야하기 때문이에요.

 

코드를 짤때는 아래 그림처럼 나옵니다.

평소에 if문을 연속으로 4개나 쓸 일이 없어서 꺼림칙한데 이거보다 더 나은게 없는 것 같습니다.

아래 그림에서는 if문이 3개 나오는 것 같지만 현재 노드가 꼬리노드인지 확인해서 꼬리노드를 업데이트해야 하므로 if문을 하나 더 사용합니다.

이대로 만들면 아래 코드처럼 나옵니다.

 

Head랑 Tail은 코드가 너무 길어보이길래 좀 짧게하려고 만들었습니다.

 

다항식 구조체에 단항식 구조체를 다 넣었으면, 이제 다항식끼리의 합을 구현할 차례입니다.

 

예시 그림을 이용하여 어떻게 다항식의 합을 구현할지 생각해봅시다

 

출발은 다음과 같이 시작합니다.

now 변수는 각 다항식의 머리노드의 주소값으로 시작합니다.

 

now1의 차수 > now2의 차수이므로 2x^5를 넣어준다음, now1을 다음 단항식의 주소로 넘깁니다.

 

now1의 차수 < now2의 차수이므로 3x^4를 넣어 준다음, now2를 다음 단항식으로 넘깁니다.

 

now1의 차수 > now2의 차수이므로 4x^3을 넣어 주고, now1을 다음 단항식으로 넘깁니다.

 

now1의 차수 == now2의 차수이고 6x^2 + 5x^2 = 11x^2이므로 11x^2를 넣어주고, now1과 now2를 각각 다음 단항식으로 넘깁니다.

 

 

이제 now1의 차수 > now2의 차수이므로 8x를 넣어주고, now1을 다음 단항식으로 넘깁니다. now1는 꼬리노드였는데 다음 단항식으로 넘긴다면 now1의 값은 nullptr이 되겠죠

 

now1 = nullptr이고, now2의 주소값만 있는데, 여기서는 for문을 이용하여 now2가 nullptr이 나올때까지 다항식에 넣습니다.

만약 now2 = nullptr일 경우 now1의 주소값만 남아있으므로 마찬가지로 for문을 이용하여 now1이 nullptr이 나올때까지 다항식에 넣습니다.

 

이걸 순서도로 그려보면 아래 그림과 같습니다.

 

여기는 그냥 다항식 맨 끝에 단항식을 계속 추가하는 방식이므로 push_back 함수를 따로 구현하였습니다.

 

위 사진을 토대로 만든 코드가 아래 코드입니다.

 

 

다항식끼리 더하는 코드는 다 만들었으므로 이제 다항식끼리 곱셈을 하는 코드를 만들어봅시다

다항식의 곱셈은 더하기와 다르게 now1과 now2로 내림차순으로 넣게 구현하면 now1과 now2를 오른쪽이 아닌 왼쪽으로 되돌려야할 경우가 있어서 굉장히 까다로울 것 같아요

여기서는 insert_node를 만들었으니 2중 for문 혹은 2중 while문을 사용하여 만들면 될 것 같습니다.

전 while문이 편하니까 while문으로 만들거에요.

 

구현하는데 필요한 지식은 5x² * 6x³ = 30x⁵ 처럼 계수끼리의 곱은 곱하기로, 지수의 곱은 지수끼리 더하는 것과 같습니다.

이것만 필요합니다.

dest1은 Poly1의 머리노드부터 꼬리노드까지 지나가는 포인터이고, dest2는 Poly2의 머리노드부터 꼬리노드까지 지나가는 포인터입니다.

 

코드는 아래와 같습니다.

 

 

그리고 다항식을 출력할 함수가 필요하므로 print함수를 만듭니다.

이건 이미 알고리즘 풀이글에 코드가 나왔었고, 코드도 그냥 출력하는거라 설명은 패스할게요

 

 

 

마지막으로 main함수

단항식들을 입력받고, 각 다항식을 출력한 후에 다항식끼리 더하여 새롭게 만든 다항식을 출력하고 있습니다.

Poly3은 Poly1 + Poly2 이고, Poly4는 Poly1 * Poly2입니다.

 

 

이 코드들을 모조리 합하면 아래 코드와 같이 나옵니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef struct Node{
    int coef;
    int expo;
    Node *next;
} Node;
 
typedef struct Polynomial{
    Node *head;
    Node *tail;
} Polynomial;
 
Node *create_node(int c, int e){
    Node *new_node = new Node;
    new_node -> coef = c;
    new_node -> expo = e;
    new_node -> next = nullptr;
    return new_node;
}
 
Polynomial *create_poly(){
    Polynomial *new_poly = new Polynomial;
    new_poly -> head = nullptr;
    new_poly -> tail = nullptr;
    return new_poly;
}
 
 
void insert_node(Polynomial *poly, int c, int e){
    Node *new_node = create_node(c,e);
    Node *Head = poly -> head;
    Node *Tail = poly -> tail;
    if(Head == nullptr)
        poly -> head = poly -> tail = new_node;
    else{
        if(new_node -> expo > Head -> expo){
            new_node -> next = Head;
            poly -> head = new_node;
        }
        else {
            Node *dest = Head;
            while(dest != Tail){ //꼬리노드전까지 while문을 돌리고 노드를 추가했으면 break로 나옴
                Node *next_dest = dest -> next;
                if(new_node -> expo == dest -> expo) {
                    dest -> coef += new_node -> coef;
                    break;
                }
                else if(next_dest -> expo < new_node -> expo && new_node -> expo < dest -> expo){
                    new_node -> next = dest -> next;
                    dest -> next = new_node;
                    break;
                }
                dest = next_dest;
            }
            if(new_node -> expo == Tail -> expo){ //while문을 다 훑었는데 노드를 추가하지 않았으므로 추가할 노드가 꼬리노드로 바뀜
                Tail -> coef += new_node -> coef;
            }
            else if(new_node -> expo < Tail -> expo){
                Tail -> next = new_node;
                poly -> tail = new_node;
            }
        }
    }
}
 
void push_back(Polynomial *Poly, int c, int e){
    Node *new_node = create_node(c,e);
    if(Poly -> head == nullptr)
        Poly -> head = Poly -> tail = new_node;
    else{
        Poly -> tail -> next = new_node;
        Poly -> tail = new_node;
    }
}
 
void addition(Polynomial* Poly1, Polynomial* Poly2, Polynomial* Poly3){
    Node* now1 = Poly1 -> head;
    Node* now2 = Poly2 -> head;
    while(1){
        if(now1 == nullptr || now2 == nullptr) break;
        if(now1 -> expo > now2 -> expo){
            push_back(Poly3, now1 -> coef, now1 -> expo);
            now1 = now1 -> next;
        }
        else if(now1 -> expo == now2 -> expo){
            int sum_now = now1 -> coef + now2 -> coef;
            push_back(Poly3, sum_now, now1 -> expo);
            now1 = now1 -> next;
            now2 = now2 -> next;
        }
        else{
            push_back(Poly3, now2 -> coef, now2 -> expo);
            now2 = now2 -> next;
        }
    }
    for(now1; now1 != nullptr; now1 = now1 -> next)
        push_back(Poly3, now1 -> coef, now1 -> expo);
    for(now2; now2 != nullptr; now2 = now2 -> next)
        push_back(Poly3, now2 -> coef, now2 -> expo);
}
 
void multiplication(Polynomial* Poly1, Polynomial* Poly2, Polynomial* Poly3){
    Node* dest1 = Poly1 -> head;
    while(dest1 != nullptr){
        Node* dest2 = Poly2 -> head;
        while(dest2 != nullptr){
            int c = dest1 -> coef * dest2 -> coef;
            int e = dest1 -> expo + dest2 -> expo;
            insert_node(Poly3, c, e);
            dest2 = dest2 -> next;
        }
        dest1 = dest1 -> next;
    }
}
 
void print(Polynomial *poly){
    Node *dest = poly -> head;
    while(dest != nullptr){
        cout << dest -> coef << "x^" << dest -> expo;
        if(dest != poly -> tail) cout << " + ";
        dest = dest -> next;
    }
    cout << endl;
}
 
int main(){
    Polynomial *Poly1 = create_poly(), *Poly2 = create_poly(), *Poly3 = create_poly(), *Poly4 = create_poly();
 
    int n,m,x,y;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> x >> y;
        insert_node(Poly1, x, y);
    }
    cout << "Poly1 출력: ";
    print(Poly1);
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> x >> y;
        insert_node(Poly2, x, y);
    }
 
    cout << "Poly2 출력: ";
    print(Poly2);
 
    cout << "Poly1 + Poly2 출력: ";
    addition(Poly1, Poly2, Poly3);
    print(Poly3);
 
    cout << "Poly1 * Poly2 출력: ";
    multiplication(Poly1, Poly2, Poly4);
    print(Poly4);
 
    return 0;
}

 

입력 값은 다항식끼리의 덧셈을 구현을 설명할 때 나온 다항식 2개를 이용하였습니다.

 

 

이 두 개의 다항식을 순차적으로 넣지않고 다항식안에 있는 단항식들을 섞어서 입력했습니다.

 

 

다항식의 뺄셈은 덧셈에서 계수를 서로 빼기만 하면 끝나는거라 코드만 살짝 바꾸면 됩니다.