[자료구조] 다항식의 표현

연결리스트를 이용하여 하나의 다항식을 표현하는 구조체 Polynomial을 정의합니다. 다항식을 항들의 연결리스트로 표현하고 항들은 차수에 대해서 내림차순으로 정렬하여 저장하며, 동일 차수의 항을 2개 이상 가지지 않게 합니다. 또한 계수가 0인 항이 존재하지 않게 합니다.

 

하나의 항은 계수와 지수에 의해 정의하며 하나의 항을 표현하기 위해 구조체 Term을 정의합니다. 또한 변수 x의 값이 주어질 때 다항식 함수를 계산합니다. 

 

구조체 Polynomial을 정하여 하나의 구조체 polynomial은 이름을 저장하는 name을 만듭니다. 

출처 / 권오흠교수님 자료구조

이런 항을 연결리스트로 연결해 헤드를 Polynomial structure안에 first를 넣어서 저장하는 것입니다. 추가로 이 다항식의 항의 개수를 저장하는 size가 있습니다. 

 

아무 매개변수도 받지 않는 생성자를 default 생성자라고 합니다. 생성자가 하나라도 있는 경우에는 default 생성자도 만들어주는 것이 좋습니다. 

 

struct Term
{
	int coef;
	int expo;
	Term* next = nullptr;

	Term() {}

	Term(int c, int e): coef(c), expo(e) {}
	Term(int c, int e, Term *p): coef(c), expo(e), next(p) {}
};

생성자 중에서 두 개의 매개변수로 받는 생성자가 되어 호출이 됩니다. 

 

Term(int c, int e) 
{
	coef = c, expo = e;
}

이렇게 멤버들을 초기화하는 것을 초기화리스트입니다. 이렇게 하지 않고 생성자를 만들어서 작업을 해준 것입니다. 

 

class 혹은 struct의 이름과 동일하면서 return 타입이 없는 멤버함수를 생성자라고 합니다. 생성자는 멤버들을 초기화하는 일을 합니다. 하나의 struct는 여러 개의 생성자를 가질 수 있습니다. 

 

생성자를 이용한 노드의 생성 예

 

#include <iostream>
using namespace std;

struct Term
{
	int coef;
	int expo;
	Term* next = nullptr;

	Term() {}

	Term(int c, int e): coef(c), expo(e) {}
	Term(int c, int e, Term *p): coef(c), expo(e), next(p) {}
};

int main()
{
	//c언어 스타일
	Term* head = new Term; 
	head->coef = -2;
	head->expo = 1;
	head->next = nullptr;

	Term* q = new Term(3, 2);
	q->next = head;
	head = q;

	head = new Term(5, 4, head);

	Term* p = head;
	while(p!=nullptr)
	{
		cout << p->coef << " " << p->expo << endl;
		p = p->next;
	}
	return 0;
}

 

구조체 Polynomial

struct Polynomial
{
	char name;
	Term* first = nullptr;
	int size = 0;
	Polynomial() {}
	Polynomial(char name): name(name) {}
};

vector<Polynomial> polys;