[4] 리스트 ③ 단일 연결리스트: 다항식
단일 연결리스트의 알고리즘
단일 연결리스트의 ADT에 포함된 함수와 설명은 아래 링크를 참조한다.
[5] 리스트 ① 단일 연결리스트
추상자료형 추상자료형이란 데이터 구조의 추상형으로서 데이터가 컴퓨터에 저장되고 실행되는 기계적인 메커니즘과는 구분되어 인간이 데이터를 다루는 관점에서 데이터구조를 명세한 것을
udangtangtang-cording-oldcast1e.tistory.com
단일 연결리스트를 이용한 다항식 계산
연결리스트 2주 차: 연결리스트의 응용 2 - 다항식 덧셈 (문제 2 참고 내용)
|
1. 다항식을 표현하는 연결리스트 구조
2. 다항식에 항 추가
◦ 기존 다항식의 마지막 항을 표현하는 노드 k에 계수 c와 차수 e로 이루어진 새 항 추가 3. 다항식 덧셈
◦ 두 개의 다항식 x, y에 대한 덧셈을 수행하여 그 결과를 새로운 헤더 단일연결리스트에 저장 -예:위예의다항식a,b의덧셈결과는3x4 +11x3 +4를반환 |
알고리즘의 순서도는 아래 접은 글 [더 보기]을 확인한다.
Alg appendTerm(k, c, e)
input last term of a polynomial expression k, coefficient c, exponent e output cxe appended to k
1. t ← getnode() 2. t.coef ← c
3. t.exp ← e
4. t.next ← NULL 5. k.next ← t
6. k ← t {k advances to t} 7. return
Alg addPoly(x, y)
input polynomial expression x, y output x + y
1. result ← getnode()
2. result.next←NULL
3. i ← x.next
4. j ← y.next
{new header } {may be null }
5. k ← result
6. while ((i ≠ NULL) & (j ≠ NULL))
if (i.exp > j.exp) appendTerm(k, i.coef, i.exp) i ← i.next
else if (i.exp < j.exp) appendTerm(k, j.coef, j.exp) j ← j.next
else
sum ← i.coef + j.coef if (sum ≠ 0)
appendTerm(k, sum, i.exp) i ← i.next
j ← j.next
7. while (i ≠ NULL )
appendTerm(k, i.coef, i.exp)
i ← i.next
8. while (j ≠ NULL)
appendTerm(k, j.coef, j.exp)
j ← j.next
9. return result
[ 문제 1 ] 위의 설명과 같이 다항식을 헤더 단일연결리스트로 표현하고, 다항식의 덧셈을 구하는 프로그램을 작성하라.
- 입력에 대한 설명 (아래 입출력 예시 참조)
- 첫 번째 다항식의 항의 개수가 입력되고, 이후에 다항식의 각 항의 (계수, 지수) 쌍이 지수 - 의 내림차순으로 입력됨
- 동일한 방식으로 두 번째 다항식의 정보가 입력됨 - 출력에 대한 설명 (아래 입출력 예시 참조)
- 결과 다항식의 각 항의 (계수, 지수) 쌍을 지수의 내림차순으로 출력
알고리즘 분석
Listnode : 구조체 선언
위 문제는 다항식의 덧셈을 구하는 알고리즘으로 다항식의 차수와 계수를 나타내는 멤버가 존재 야하며, 단일 연결리스트이므로 pre 구조체 포인가 존재하지 않고 다음 노드를 가리키는 next 구조체 포인터만 존재함에 유의한다.
typedef struct node {
int coef;
int exp;
struct node* next;
}listnode;appendTerm : 리스트 선언 함수
appendTerm 함수의 논리 순서는 아래와 같다.
| Alg. appendTerm(k, c, e) input last term of a polynomial expression k, coefficient c, exponent e output cxe appended to k 1. t ← getnode() 2. t.coef ← c 3. t.exp ← e 4. t.next ← NULL 5. k.next ← t 6. k ← t {k advances to t} 7. return |
appendTerm 함수는 연결리스트를 생성하고 입력받은 다항식의 차수와 계수를 생성한 연결리스트에 저장하는 알고리즘을 실행한다.
새로 생성한 연결리스트는 list->next가 NULL이 아닐 때, 즉 맨 마지막 노드가 된다면 새로 생성한 노드를 연결한다.
따라서 위 로직에 맞춰 프로그래밍을 하면 아래 코드와 같다.
void appendTerm(listnode* list,int c,int e) {
listnode* new = (listnode*)malloc(sizeof(listnode));
new->coef = c;
new->exp = e;
new->next = NULL;
while (list->next != NULL) {
list = list->next;
}
list->next = new;
}
addPoly : 다항식 처리 함수
addPoly 함수의 논리 순서는 아래와 같다.
|
Alg. addPoly(x, y)
input polynomial expression x, y output x + y 1. result ← getnode()
2. result.next←NULL 3. i ← x.next 4. j ← y.next {new header } {may be null } 5. k ← result
6. while ((i ≠ NULL) & (j ≠ NULL)) if. (i.exp > j.exp) appendTerm(k, i.coef, i.exp) i ← i.next else. if (i.exp < j.exp) appendTerm(k, j.coef, j.exp) j ← j.next else sum ← i.coef + j.coef if (sum ≠ 0) |
addPoly 함수의 알고리즘은 다소 복잡하다. 번호를 통해 순차적으로 확인해 보자.
1. 인자로 받은 두 개의 연결리스트(구조체 포인터)를 변수에 저장
addPoly 함수는 두 개의 연결리스트를 저장하는 구조체 포인터를 인자로 가진다.
다항식 계산에 앞서, 인자로 받은 두 개의 구조체 포인터를 구조체 포인터 fir과 sec에 저장한다. 이때의 변수는 임의로 설정한다.
이는 인자로 받은 두 개의 구조체 포인터는 연결리스트의 head를 가리키므로, 이를 손상시키지 않도록 각각의 임의의 구조체 포인터에 복사하여 사용하고 next의 값을 바꿔서 값을 확인하는 것이다.
2. 결과로 출력한 rst 연결리스트 생성
출력값으로 원하는 것은 인자로 받은 두 개의 연결리스트의 계산 처리가 된 하나의 단일 연결리스트이므로 새로 생성하고 이를 결괏값을 저장할 연결리스트로서 사용한다.
연결리스트를 생성했다면 next 값을 NULL로서 초기화한다.
3. 계수의 합을 저장할 sum_coef 변수 선언
계수의 합을 바탕으로 다항식을 계산하므로 이를 위한 정수형 변수 sum_coef를 선언하여 사용한다.
4. 다항식의 계수를 바탕으로 다항식 계산 반복 처리 ⭐️⭐️⭐️⭐️⭐️
우리가 원하는 결괏값은 차수와 계수를 데이터로 가지는 두 개의 연결리스 트을 계산(사칙연산)한 연결리스트를 생성하는 것이다.
이를 위해서는 아래와 같은 로직을 생각해 볼 수 있다.
- 각각의 다항식을 저장하는 연결리스트는 차수의 순서대로 정리되어 있다. 즉 차수가 높은 순으로 정렬돼 있다.
- 각각의 연결리스트는 차수가 높은 순으로 정렬되어 있으므로 다음과 같은 경우가 발생한다.
이때 각각의 연결리스트를 편의상 fir, sec이라 지정한다.
- ( fir의 차수 > sec의 차수 )인 경우
- ( fir의 차수 < sec의 차수 )인 경우
- ( fir의 차수 = sec의 차수 ) 인 경우
차수를 가지고 조건을 파악하는 이유는 차수가 다르면 계산할 이유가 없기 때문이다!
(1)의 경우, 결과를 저장하는 연결리스트에 현재 fir가 가리키는 노드의 값을 저장하고 다음 fir가 가리키는 곳으로 이동한다.
(2)의 경우, 결과를 저장하는 연결리스트에 현재 sec가 가리키는 노드의 값을 저장하고 다음 sec가 가리키는 곳으로 이동한다.
(3)의 경우, fir와 sec의 계수의 합을 결과를 저장하는 연결리스트에 저장한다.
1~3의 경우 모두 결과를 저장하는 연결리스트에 차수와 계수를 저장하는 것을 주의한다.
각각의 연결리스트의 차수를 이용해 조건을 생성하고 결괏값을 저장하는 연결리스트에 저장했어도 끝이 난 것이 아니다.
각각의 연결리스트의 크기는 서로 다를 수 있기 때문이다. 따라서 현재 노드가 가리키는 값이 NULL이 아니라면, NULL값이 나오도록 while 반복문을 사용하여 계산을 진행해야 한다.
여기서 조금 생각해야 하는 점은, 현재 노드가 가리키는 값이 NULL이 아닌 연결리스트는 그대로 결괏값을 저장하는 연결리스트에 저장이 가능하냐는 것이다. 하지만 이미 조건문에 포함된 각각의 차수로서 비교했으므로 특정 연결리스트가 남아있다는 것은 이는 생각할 필요 없이 이미 처리된 연결리스트보다 차수가 낮다는 것을 의미한다.
위 처리가 끝났다면 결괏값을 사용할 연결리스트의 주소를 반환한다.
따라서 위 로직에 맞춰 프로그래밍을 하면 아래 코드와 같다.
listnode* addPoly(listnode* list1, listnode* list2) {
listnode* fir = list1->next;
listnode* sec = list2->next;
listnode* rst = (listnode*)malloc(sizeof(listnode));
rst->next = NULL;
int sum_coef;
while ((fir != NULL) && (sec != NULL)) {
if (fir->exp > sec->exp) {
appendTerm(rst, fir->coef, fir->exp);
fir = fir->next;
}
else if (fir->exp < sec->exp) {
appendTerm(rst, sec->coef, sec->exp);
sec = sec->next;
}
else {
sum_coef = sec->coef + fir->coef;
if ((sum_coef != 0) && (fir->exp != 0)) //계수의 합이 0이 아니고 차수가 0이 아닌 경우
appendTerm(rst, sum_coef, fir->exp);
fir = fir->next;
sec = sec->next;
}
}
while (fir != NULL) {
appendTerm(rst, fir->coef, fir->exp);
fir = fir->next;
}
while (sec != NULL) {
appendTerm(rst, sec->coef, sec->exp);
sec = sec->next;
}
return rst;
}
main : 선언 및 입출력 담당
메인 함수에서 수행하는 로직은 아래와 같다.
1. 두 개의 연결리스트를 동적할당하고 값을 입력받는다.
2. 연결리스트를 입력받을 때 appendTerm 함수를 통해 기존의 연결리스트 노드에 연결한다.
3. 결괏값을 저장할 연결리스트를 동적할당한다.
4. addPoly 함수를 이용해 두 개의 연결리스트를 계산하고 반환된 결과를 '결괏값을 저장할 연결리스트'에 저장한다.
5. 순환을 통해 '결괏값을 저장할 연결리스트'의 값을 출력한다.
답안 코드
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int coef;
int exp;
struct node* next;
}listnode;
void appendTerm(listnode* list,int c,int e) {
listnode* new = (listnode*)malloc(sizeof(listnode));
new->coef = c;
new->exp = e;
new->next = NULL;
while (list->next != NULL) {
list = list->next;
}
list->next = new;
}
void print(listnode* list) {
listnode* p = list->next;
while (p != NULL) {
printf("%d %d ", p->coef, p->exp);
p = p->next;
}
}
listnode* addPoly(listnode* list1, listnode* list2) {
listnode* fir = list1->next;
listnode* sec = list2->next;
listnode* rst = (listnode*)malloc(sizeof(listnode));
rst->next = NULL;
int sum_coef;
while ((fir != NULL) && (sec != NULL)) {
if (fir->exp > sec->exp) {
appendTerm(rst, fir->coef, fir->exp);
fir = fir->next;
}
else if (fir->exp < sec->exp) {
appendTerm(rst, sec->coef, sec->exp);
sec = sec->next;
}
else {
sum_coef = sec->coef + fir->coef;
if ((sum_coef != 0) && (fir->exp != 0)) //계수의 합이 0이 아니고 차수가 0이 아닌 경우
appendTerm(rst, sum_coef, fir->exp);
fir = fir->next;
sec = sec->next;
}
}
while (fir != NULL) {
appendTerm(rst, fir->coef, fir->exp);
fir = fir->next;
}
while (sec != NULL) {
appendTerm(rst, sec->coef, sec->exp);
sec = sec->next;
}
return rst;
}
int main(){
listnode* list1 = (listnode*)malloc(sizeof(listnode));
list1->next = NULL;
listnode* list2 = (listnode*)malloc(sizeof(listnode));
list2->next = NULL;
int c, e,N,M;
scanf("%d", &N);getchar();
for (int i = 0; i < N; i++) {
scanf("%d", &c);
scanf("%d", &e);
appendTerm(list1, c, e);
}
scanf("%d", &M);getchar();
for (int i = 0; i < M; i++) {
scanf("%d", &c);
scanf("%d", &e);
appendTerm(list2, c, e);
}
listnode* rst;
rst = addPoly(list1, list2);
print(rst);
}