[자료구조] 다항식

다항식

 - ax^e 형식의 항들의 합으로 구성된 식

    a : 계수 (coefficient)

    x : 변수(variable)

    e : 지수(exponent)

 - 지수에 따라 내림차순으로 항을 나열

 - 다항식의 차수 : 가장 큰 지수

 - 다항식 항의 최대 개수 = (차수 + 1) 개

 

다항식의 표현

 - 각 항의 지수와 계수의 쌍에 대한 선형 리스트

 ex) A(x) = 4x^3 + 3x^2 + 2 ☞ p1 = ((3, 4), (2, 3), (0, 2))

---

 - 1차원 배열 이용

 ex)

 P(x) = 4x^3 + 3x^2 + 2

차수(인덱스)	x^3	x^2	x	0
계수(값)	4	3	0	2

 - 2차원 배열 이용

 ex)

 P(x) = 4x^1000 + 3x^2 + 2

차수	계수
1000	4
2	3
0	2

---

단순 연결 리스트를 이용하여 다항식 표현

 - 다항식 항 : 단순 연결 리스트의 노드

 - 노드 구조

    ㄴ 각 항에 대해서 계수와 지수를 저장

    ㄴ 계수를 저장하는 coef와 지수를 저장하는 expo의 두 개의 필드로 구성

    ㄴ 링크 필드 : 다음 항을 연결하는 포인터로 구성

coef  (계수)

expo  (지수)

link  (링크)

// 노드에 대한 클래스 정의

public class Node {
	float coef;
    int expo;
    Node link;
}

 - 다항식의 단순 연결 리스트 표현 예

 ex) A(x) = 4x^3 + 5x +1

coef

expo

link

coef

expo

link

coef

expo

link

●

→

4

3

●

→

5

1

●

→

1

0

null

4x^3

5x

1

---

 - 다항식 연결 자료구조의 삽입 연산

① 공백 다항식에서의 항 삽입 연산

  - 포인터(new)의 값을 리스트 포인터(PL)에 저장, 노드가 리스트의 첫 번째 노드가 되도록 연결

  - 포인터(new)의 값을 포인터(last)에 저장, 포인터(last)가 리스트의 마지막 노드인 노드(new)를 가리키도록 지정

삽입 전(초기 상태)

			500번지
PL	null		coef		expo	null
			↑
			500            ●	null
			new	last

삽입 후

			500번지
PL	500        ●	→	coef		expo	null
			↑	↑
			500            ●	500            ●
			new	last

---

② 공백이 아닌 다항식에서의 항 삽입 연산

  - 포인터(new)의 값을 노드(last) 링크에 저장하여, 노드(new)를 노드(last)의 다음 노드로 연결

  - 포인터(new)의 값을 포인터(last)에 저장하여, 노드(new)를 리스트의 마지막 노드로 지정

삽입 전

			200번지(last)					500번지(new)
PL	200        ●	→	coef		expo	null		coef	expo	null
			↑					↑
			200          ●					500              ●
			last					new

삽입 후

			200번지(last)					500번지(new)
PL	200        ●	→	coef		expo	500          ●	→	coef		expo	null
								↑	↑
								500    ●	500    ●
								last	new

관련 이론 설명 글

[자료구조] 이중 연결 리스트

[자료구조] 이중 연결 리스트