다항식 연결 자료구조 (다항식 삽입 연산, 덧셈 연산)
| 다항식 연결 자료구조 | 다항식에 있는 항 하나는 노드 하나로 표현하며, 각 항마다 계수와 지수를 저장하도록 자료구조를 정의한다. |
| 다항식 삽입연산 | 삽입할 새로운 항(노드) 생성하고 노드의 계수 필드 값, 지수 필드 값 할당한 다음 노드를 추가할 위치에 링크 연결하여 삽입한다. |
| 다항식 덧셈연산 | 덧셈A(x)+B(x)=C(x)를 단순 연결 리스트 자료구조를 사용하여 연산한다. 각 항을 이동하면서 지수를 비교하기 위해 포인터와 노드의 링크 필드를 이용하고 각 항을 지시하기 위해서 세 개의 포인터를 사용한다. |
단순 연결 리스트를 이용한 다항식 표현
다항식 노드의 노드 구조와 구조체 정의
다항식에 있는 항 하나는 노드 하나로 표현
각 항마다 계수 (coefficient:coef)와 지수(exponent:expo)를 저장해야 함
○ 데이터필드는 계수를 저장하는 필드와 지수를 저장하는 필드로 구성
○ 링크 필드는 다음 항을 연결하는 포인터로 구성
다항식 연결 자료구조의 항 삽입 알고리즘
다항식 리스트 포인터 PL과 coef(coefficient) 필드 값을 저장한 변수 coef, expo(exponent) 필드 값을 저장한 변수 expo, 리스트 PL의 마지막 노드의 위치를 지시하는 포인터 last를 매개변수로 사용
① 공백 리스트인 경우 : 다항식 리스트 PL이 항이 하나도 없는 경우
①-ⓐ PL ← new; 포인터 new의 값(500)을 리스트 포인터 PL에 저장하여 노드 new가 리스트 PL의 첫번째 노드가 되도록 연결
①-ⓑ last ← new; 포인터 new의 값(500)을 포인터 last가 리스트 PL의 마지막 노드 new를 가리키도록 저장
② 공백 리스트가 아닌 경우 : 다항식 리스트 PL이 공백이 아닌 경우에는 새 노드 new를 리스트 PL의 마지막 노드로 삽입
②-ⓐ last.link ← new; 포인터 new의 값(500)을 노드 last의 링크에 저장하여 노드 new를 노드 last의 다음 노드로 연결
②-ⓑ last ← new; 포인터 new의 값(500)을 포인터 last에 저장하여 노드 new를 리스트 PL의 마지막 노드로 설정
다항식끼리의 덧셈 연산과 알고리즘
덧셈 A(x) + B(x) = C(x)를 단순 연결 리스트 자료구조를 사용하여 연산
다항식 A(x)와, B(x), C(x)의 항을 지시하기 위해서 세 개의 포인터를 사용
○ 포인터 p : 다항식 A(x)에서 비교할 항을 지시
○ 포인터 q : 다항식 B(x)에서 비교할 항을 지시
○ 포인터 r : 덧셈연산 결과 만들어지는 다항식 C(x)의 항을 지시
p.expo < q.exop : 다항식 A(x) 항의 지수가 작은 경우
두 다항식의 지수가 다르면 계수를 더할 수 없다.
○ 지수가 높은 항부터 나열하는 다항식 표현 규칙에 따라서 포인터 q가 가리키는 다항식 B(x)항을 C(x)항으로 복사
○ q가 가리키는 항에 대한 처리가 끝나면 q를 다음 노드로 이동
p.expo = q.exop : 두 다항식 항의 지수가 같은 경우
두 다항식의 지수가 같으면 지수가 같은 항의 계수를 더해 C(x) 항을 만들면 된다.
○ p.coef와 q.coef를 더해 c(x)항인 r.coef에 저장하고, 지수는 p.expo(또는 q.expo)를 r.expo에 저장
○ 다음 항을 비교하기 위해 포인터 p와 q를 각각 다음 노드로 이동
p.expo > q.exop : 다항식 A(x) 항의 지수가 큰 경우
P가 가리키는 다항식 A(x) 항의 지수가 더 크면
○ 포인터 p가 가리키는 항을 C(x) 항으로 복사
○ 포인터 p가 가리키는 항에 대한 처리가 끝났으므로 p를 다음 노드로 이동
두 다항식의 덧셈 연산 알고리즘으로 정리
② 에서 다항식 A와 B에 처리 항 있는 동안, 항의 지수 비교 처리 작업 반복
②-ⓑ 수행
②-ⓐ 수행
②-ⓒ 수행
②-ⓐ 수행
○ p다항식 A의 모든 항에 대한 처리가 끝나고 포인터 p가 NULL이 되었으므로 ②의 while 문 반복 끝나고 ④수행하여 포인터 q가 NULL이 될 때까지(while (q≠NULL)), q 노드를 리스트 C의 마지막 노드로 추가
○ 마지막으로 ⑤에서 완성된 덧셈 결과 다항식 C 반환
