* 다항식의 연결 자료구조 표현
- 단순 연결 리스트를 이용하여 다항식 표현하기
- 계수, 지수, 다음노드를 가리키는 참조 노드 세개로 구성
[다항식의 단순 연결 리스트 표현]
단순 연결 리스트를 이용하여 다항식을 표현 하였다.
단순 연결 리스트는 data, next 두개의 멤버변수로만 구성했지만
다항식을 표현한 단순연결리스트는 계수(coef)와 지수(expo), 다음노드를 가리키는 next 노드로 구성하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 |
ListNode.java
package polynomial;
public class ListNode {
int coef;
int expo;
ListNode next;
public ListNode() {
next = null;
}
public ListNode(int coef, int expo){
this.coef = coef;
this.expo = expo;
this.next = null;
}
public ListNode(int coef, int expo, ListNode next){
this.coef = coef;
this.expo = expo;
this.next = next;
}
public int getCoef() {
return this.coef;
}
public int getExpo() {
return this.expo;
}
} |
[ 다항식 항 삽입 연산 ]
- 연결 리스트의 마지막 노드 다음에 새로운 노드 추가
if 리스트가 비어있는 경우 (head==null)
삽입하는 노드가 리스트의 첫번째 노드이자 마지막노드
리스트에 새로운 노드를 추가하고, 첫번째 노드로 지정
else 리스트가 비어있지 않은 경우 (head!=null)
새로운 노드를 마지막 노드로 추가
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 |
Polynomial.java
package polynomial;
public class Polynomial {
ListNode head;
public Polynomial() {
head = null;
}
public void insertNode(int coef, int expo){
ListNode node = new ListNode(coef, expo);
if(head==null){
head = node;
}else{
ListNode current = head;
while(current.next!=null){
current = current.next;
}
current.next = node;
}
}
public void print(){
if(head==null){
System.out.println("출력할 노드가 존재하지 않습니다.");
}else{
ListNode current = head;
while(current.next!=null){
System.out.print(current.coef + "X^" + current.expo + " + ");
current = current.next;
}
System.out.print(current.coef + "X^" + current.expo);
System.out.println();
}
}
} |
[ 다항식끼리 덧셈 연산 ]
- 새로운 리스트를 만들어 더해진 값들을 저장하고 연결한다.
if 다항식 B(x) 항의 지수가 더 큰 경우 (A.expo < B.expo)
다항식 B의 현재 노드를 새로운 다항식 C의 값에 저장한다.
else if 다항식 A(x) 항의 지수가 더 큰 경우 (A.expo > B.expo)
다항식 A의 현재 노드를 새로운 다항식 C의 값에 저장한다.
else 두 항의 지수가 같은 경우 (A.expo == B.expo)
다항식 A와 B의 계수(coef)를 더한 후 새로운 다항식 C의 값에 저장한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 |
Test.java
package polynomial;
public class Test {
public static void main(String[] args) {
//다항식 A 만들기
Polynomial A = new Polynomial();
A.insertNode(4, 3);
A.insertNode(3, 2);
A.insertNode(5, 1);
A.print();
//다항식 B 만들기
Polynomial B = new Polynomial();
B.insertNode(3, 4);
B.insertNode(1, 3);
B.insertNode(2, 1);
B.insertNode(1, 0);
B.print();
Polynomial C = AddPolynomial(A, B);
C.print();
}
static Polynomial AddPolynomial(Polynomial A, Polynomial B){
ListNode a = A.head;
ListNode b = B.head;
Polynomial C = new Polynomial();
//A나 B 둘 중 하나가 모든 항에 대해 덧셈이 끝나는 경우 while 종료
while(a!=null && b!=null){
//B의 지수가 A의 지수보다 큰 경우
if(a.expo<b.expo){
C.insertNode(b.coef, b.expo);
b = b.next;
}
//A의 지수가 B의 지수보다 큰 경우
else if(a.expo>b.expo){
C.insertNode(a.coef, a.expo);
a = a.next;
}
//A의 지수와 B의 지수가 같은 경우
else{
C.insertNode(a.coef+b.coef, a.expo);
a = a.next;
b = b.next;
}
}
//A에 항이 남아 있는 경우 C에 추가
while(a!=null){
C.insertNode(a.coef, a.expo);
a = a.next;
}
//B에 항이 남아 잇는 경우 B에 추가
while(b!=null){
C.insertNode(b.coef, b.expo);
b = b.next;
}
return C;
}
} |
Test.java 에서 다항식 두개를 생성하고,
더해주는 연산을 제공해주는 AddPolynomial 메서드를 구현하였다.
[출력값]
'전산 기초 > 자료구조' 카테고리의 다른 글
| [자료구조/java] 스택의 응용 - 역순 문자열 만들기 (0) | 2015.10.31 |
|---|---|
| [자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현 (0) | 2015.10.31 |
| [자료구조/java] 이중 연결 리스트 (Doubly Linked List) (0) | 2015.10.27 |
| [자료구조/java] 원형 연결 리스트 (Circular Linked List) (0) | 2015.10.26 |
| [자료구조/java] 단순 연결 리스트 (Linked List) (0) | 2015.10.25 |
