[14] C review < 연결리스트 - 다항식 >

연결리스트를 활용하여 다항식의 문제를 푸는 계산기를 만들어봅시다. 이때, 계수는 정수이고 지수는 양의 정수라고 가정하겠습니다. 

( 활용 예 )

 - 연결리스트를 이용하여 하나의 다항식을 표현하는 구조체 Polynomial을 정의한다. 

 - 다항식을 항들의 연결 리스트로 표현한다.

 - 항들을 차수에 대해서 내림차순으로 정렬하여 저장하며,동일 차수의 항을 2개 이상 가지지 않게 한다. 또한 계수가 0인 항이 존재하지 않게 한다. 

 - 하나의 항은 계수와 지수에 의해 정의된다. 하나의 항을 표현하기 위해 구조체 Term을 정의한다. 

 - 변수 x의 값이 주어질 때 다항식의 값을 계산하는 함수를 제공한다. 

 

우리가 원하는 다항식의 자료구조 

다항식 이름을 저장하고 , 다항식의 항의 개수, 각각의 항을 나타내는 구조체까지 포함한다. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_POLYS 100

typedef struct term
{
    int coef;
    int expo;
    struct term *next; // 다음 노드를 가리킨다.
} Term;

typedef struct polynomial
{
    char name;
    Term *frist; // 첫번째항의 주소.
    int size = 0;
} Polynomial;

Polynomial *polys[MAX_POLYS]; // polys는 다항식들에 대한 포인터의 배열.
int n = 0;

Term *create_term_instance();
Polynomial *create_polynomial_instance(char name);

int main()
{

    return 0;
}

// Term과 Polynomial을 생성하는 함수를 만들자.

Term *create_term_instance()
{
    Term *t = (Term *)malloc(sizeof(Term));
    t->coef = 0;
    t->expo = 0;
    return t;
}

Polynomial *create_polynomial_instance(char name)
{ // 다항식 객체를 생성할 때 이름을 지정해주도록 만들어 보았다.

    Polynomial *ptr_poly = (Polynomial *)malloc(sizeof(Polynomial));
    ptr_poly->name - name;
    ptr_poly->size = 0;
    ptr_poly->frist = NULL;
    return ptr_poly;
}

 

동적으로 생성된 객체를 적절하게 초기화해주지 않는 것이 종종 프로그램의 오류를 야기합니다. 이렇게 객체를 생성하고 기본값으로 초기화해주는함수를 따로 만들어 사용하는 것이 좋은 방법입니다.

 

다음으로 중요한 역할을 하는 항의 추가에 대해 살펴봅시다. 

 

void add_term(int c, int e, Polynomial *poly)
{
    if (c == 0)
        return;
    Term *p = poly->frist, *q = NULL;
    while (p != NULL && p->expo > e)
    {
        q = p;
        p = p->next;
    }
    if (p != NULL && p->expo == e) // 동일 차수 존재
    {
        p->coef += c;
        if (p->coef == 0) // 더했더니 계수가 0
        {
            if (q == NULL) // q의 다음 노드를 삭제, 단 q가 NULL이라면 첫번째 노드 삭제.
                poly->frist = p->next;
            else
                q->next = p->next;
            poly->size--;
            free(p);
        }
        return;
    }

    //동일한 차수의 항이 존재 x 노드 추가
    Term *term = create_term_instance();
    term->coef = c;
    term->expo = e;

    if (q = NULL)
    {
        term->next = poly->frist;
        poly->frist = term;
    }
    else
    {
        term->next = p;
        q->next = term;
    }
    poly->size++;
}