[연결리스트] 단일연결리스트로 다항식 계산 구현하기

의사코드:

 

 

 

입력 예시 1	출력 예시 1
3 ↦ 첫 번째 다항식의 항의 개수 5 3 3 2 3 1 ↦ 5x3 + 3x2 + 3x 3 ↦ 두 번째 다항식의 항의 개수 2 6 2 3 1 0 ↦ 2x6 + 2x3 + 1	□2 6 7 3 3 2 3 1 1 0 ↦ 2x6+7x3+3x2+3x+1

입력 예시 2	출력 예시 2
2 ↦ 첫 번째 다항식의 항의 개수 2 7 3 0 ↦ 2x7 + 3 3 ↦ 두 번째 다항식의 항의 개수 -3 10 3 7 -3 0 ↦ -3x10 + 3x7 -3	□-3 10 5 7 ↦ -3x10 + 5x7

 

코드:

 

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef struct listnode {// 노드
	int coef;// 항의 계수
	int exp;// 항의 차수
	struct listnode* next;// 다음 노드의 주소 저장
}node;

typedef struct listhead {// 리스트
	node* head;
}listhead;

void appendTerm(node *head, int coef, int exp) {// 기존 다항식에 항 추가
	node* newnode = (node*)malloc(sizeof(node));
	newnode->coef = coef;
	newnode->exp = exp;
	newnode->next = NULL;
	while (head->next != NULL) {
		head = head->next;
	}
	head->next = newnode;
}

node* addPoly(node* firstpolynomial, node* secondpolynomial) {
	node* first = firstpolynomial->next;
	node* second = secondpolynomial->next;
	node* sumpolynomial = (node*)malloc(sizeof(node));
	sumpolynomial->next = NULL;

	int check;
	while ((first != NULL) && (second != NULL)) {
		if (first->exp > second->exp) {//첫번째 다항식의 차수가 두번째 다항식의 차수보다 크다면
			appendTerm(sumpolynomial, first->coef, first->exp);
			first = first->next;
		}
		else if (first->exp < second->exp) {//첫번째 다항식의 차수가 두번째 다항식의 차수보다 크다면
			appendTerm(sumpolynomial, second->coef, second->exp);
			second = second->next;
		}
		else {// 두 다항식의 차수가 같다면
			check = first->coef + second->coef;
			if (check != 0) {
				appendTerm(sumpolynomial, check, first->exp);
			}
			first = first->next;
			second = second->next;
		}
	}

	while (first != NULL) {
		appendTerm(sumpolynomial, first->coef, first->exp);
		first = first->next;
	}
	while (second != NULL) {
		appendTerm(sumpolynomial, second->coef, second->exp);
		second = second->next;
	}
	return sumpolynomial;
}

void printPolynomial(node *header) {// 다항식 출력
	node* p = header->next;
	
	while (p != NULL) {
		printf(" %d %d", p->coef, p->exp);// 출력
		p = p->next;// 다음 노드로 연결해주기
	}
}

void freePolynomial(node* header) {
	node* p = header;// p에 헤더 연결
	while (p != NULL) {
		header = header->next;// 다음 노드로 연결
		free(p);// 해제해주기
		p = header;// p에 빈 헤더 연결
	}
}

int main() {
	int num, coef, exp;// 항의 갯수, 계수, 차수
	node* firstpolynomial = (node*)malloc(sizeof(node));
	node* secondpolynomial = (node*)malloc(sizeof(node));
	node* sumpolynomial;

	firstpolynomial->next = NULL;// 초기화
	secondpolynomial->next = NULL;

	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		scanf("%d", &coef);
		scanf("%d", &exp);
		appendTerm(firstpolynomial, coef, exp);
	}// 첫번째 다항식 입력받기

	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		scanf("%d", &coef);
		scanf("%d", &exp);
		appendTerm(secondpolynomial, coef, exp);
	}// 두번째 다항식 입력받기

	sumpolynomial = addPoly(firstpolynomial, secondpolynomial);

	printPolynomial(sumpolynomial);// 출력

	freePolynomial(firstpolynomial);
	freePolynomial(secondpolynomial);
	freePolynomial(sumpolynomial);

	return 0;
}

 

점점 연결리스트랑 친해지고 있는듯.. 더 친해지자 우리......(┬┬﹏┬┬)