[단일 연결 리스트] [다항식의 덧셈] c구현 및 설명

목차

 

문제

다항식을 헤더 단일연결리스트 로 표현하고, 다항식의 덧셈을 구하는 프로그램을 작성하라.

입력에 대한 설명: 첫 번째 다항식의 항의 개수가 입력되고,

이후에 다항식의 각 항의 (계수, 지수) 쌍이 지수 의 내림차순으로 입력됨동일한 방식으로 두 번째 다항식의 정보가 입력됨

 

입력/출력

3 ↦ 첫 번째 다항식의 항의 개수

5 3 3 2 3 1 ↦ 5x^(3) + 3x^(2) + 3x

3 ↦ 두 번째 다항식의 항의 개수

2 6 2 3 1 0 ↦ 2x^(6) + 2x^(3) + 1

 

 

5x^(3) 3x^(2) 3x^(1)
2x^(6) 2x^(3) 1x^(0)
2x^(6) 7x^(3) 3x^(2) 3x^(1) 1x^(0)

 

 

노드의 구조

• coef: 항의 계수
• exp: 항의 차수
• next: 다음 노드를 가리키는 링크

 

함수 구현 방향

• appendTerm: 기존 다항식의 마지막 항을 표현하는 노드 k에 계수 c와 차수 e로 이루어진 새 항 추가
• Alg addPoly(x, y): 두 개의 다항식 x, y에 대한 덧셈을 수행하여 그 결과를 새로운 헤더 단일연결리스트에 저장

 

구현 방향성

나는 head노드 하나를 이용해서 접근하였다 그래서 cur을 이용해 계속 값을 추가해 주었다.

 

 

 

struct 구조

typedef struct Node {
	int coef;
	int exp;
	struct Node* next;
}Node;

typedef struct List {
	 Node* head;
	 Node* cur;
	int size;
}List;

 

초기화 함수

void init(List* list) {
	list->head = NULL;
	list->cur = NULL;
	list->size = 0;   //사이즈 0으로 초기화
}

 

appendTerm 함수

void appendTerm(List *list, int c, int e) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->coef = c;
	newNode->exp = e;
	newNode->next = NULL;  //메모리의 누수를 막기 위해 다음 값 null 추가
	if (list->head == NULL) {   //head가 null일 경우
		list->head = newNode;
		list->cur = list->head;   //cur 계속해서 갱신
	}
	else {
		list->cur->next = newNode;
		list->cur = list->cur->next;   //cur 계속해서 갱신
	}
	list->size++;  //사이즈 증가
}

 

addPoly함수

List* addPoly(List* x, List* y) {
	List* result = (List*)malloc(sizeof(List));  // 반환할 리스트
	init(result);  //리스트 초기화
	x->cur = x->head;   //cur 초기화
	y->cur = y->head;  //cur 초기화
	while (x->cur != NULL && y->cur != NULL) {  //하나라도 null이 나올 경우 중단
		if (x->cur->exp > y->cur->exp) {  //x의 지수가 더 클 경우 
			appendTerm(result, x->cur->coef, x->cur->exp);
			x->cur = x->cur->next;
		}
		else if (x->cur->exp < y->cur->exp) {   //y의 지수가 더 클 경우 
			appendTerm(result, y->cur->coef, y->cur->exp);
			y->cur = y->cur->next;
		}
		else {    //지수가 같을 경우
			int sum = y->cur->coef + x->cur->coef;   //상수 더해줌
			if(sum!=0)   //상수가 0이 아니라면
				appendTerm(result, sum, y->cur->exp);
			y->cur = y->cur->next;
			x->cur = x->cur->next;
		}
	}
	while (x->cur != NULL) {  //끝까지 안갔다면 마저 가준다.
		appendTerm(result, x->cur->coef, x->cur->exp);
		x->cur = x->cur->next;
	}
	while (y->cur != NULL) {  //끝까지 안갔다면 마저 가준다.
		appendTerm(result, y->cur->coef, y->cur->exp);
		y->cur = y->cur->next;
	}
	return result;
}

 

print함수

void print(List *list) {  //출력 함수
	if (list->size == 0)
		return 0;
	list->cur = list->head;  //cur 가르키는 값 head로 바꿔줌
	while (list->cur != NULL) {
		printf("%dx^(%d) ", list->cur->coef, list->cur->exp);
		list->cur = list->cur->next;
	}
	printf("\n");
}

 

main함수

int main() {
	List lista, listb;
	List* ans;
	init(&lista);
	init(&listb);
	int n, m, coef, exp;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &coef, &exp);
		appendTerm(&lista, coef, exp);
	}
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &coef, &exp);
		appendTerm(&listb, coef, exp);
	}
	ans = addPoly(&lista, &listb);
	print(&lista);
	print(&listb);
	print(ans);
	
}