*자료구조 제 10강(연결리스트-다항식)

 

• 연결리스트를 이용하여 하나의 다항식을 표현하는 구조체 Polynomial을 정의한다.
• 다항식을 항들의 연결리스트로 표현한다.
• 항들을 차수에 대해서 내림차순으로 정렬하여 저장하며, 동일 차수의 항을 2개 이상 가지지 않게 한다. 또한 계수가 0인 항이 존재하지 않게 한다.
• 하나의 항은 계수와 지수에 의해 결정된다. 하나의 항을 표현하기 위해 구조체 Term을 정의한다.
• 변수 x의 값이 주어질 때 다항식의 값을 계산하는 함수를 제공한다.

 

• Polynomial 구조체는 name, first, size 필드로 구성되어 있다. name에는 다항식의 이름, first에는 식의 첫 항의 주소, size에는 항의 개수를 저장한다.
• Term 구조체는 coef, expo, next 필드로 구성되어있다. coef에는 계수, expo에는 지수, next에는 다음 항의 주소를 저장한다.

Poly가 가리키는 다항식에 새로운 하나의 항 (c,e)를 추가하는 함수

1. 추가하려는 항과 동일 차수의 항이 이미 있는 경우: 기존 항의 계수만 변경
2. 그렇지 않은 경우: 새로운 항을 삽입 (항들은 차수의 내림차순으로 항상 정렬 됨)

    ☞새로운 항이 삽입될 위치를 찾기 위해서는 새로운 항보다 치수가 작거나 같은 항이 나올 때까지 첫 번째 항부터 순서대로 검사해야 한다. - 연결리스트에서 노드를 삽입하기 위해서는 이전 노드의 주소가 필요하다.

 

/*
* 2022-02-25
* 연결리스트-다항식
* 1. 1원 다항식을 정의할 수 있다. 다항식의 이름은 x를 제외한 영문 소문자이다.
* 2. 변수는 항상 x이다.
* 3. 각 항의 지수는 음이 아닌 정수이고, 계수는 정수이다.
* 4. =, +, - 등의 앞뒤로 하나 이상의 공백이 있을 수도 있고 없을 수도 있다.
* 5. 항들이 반드시 차수에 대해 내림차순으로 입력되는 것은 아니며, 동일 차수의 항이 여럿 있을수도 있다.
* 6. 함수는 항상 차수에 대한 내림차순으로 정렬되어 저장되고 출력되어야 한다.
* 7. 동일 이름의 함수를 새로 정의할 수도 있다. 이 경우 기존 함수는 지워진다.
*/

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

#define MAX_POLYS 100

struct term {						//Polynomial 안의 구조체
	int coef;	//계수
	int expo;	//지수
	struct term** next;
};
typedef struct term Term;


typedef struct polynimial {		
	char name;
	Term* first;					//다항식의 첫 항의 주소 저장하는 변수
	int size;
} Polynomial;
Polynomial* polys[MAX_POLYS];		//polys는 다항식들에 대한 포인터의 배열이다.
int n = 0;							//저장된 다항식의 개수이다.



Term* create_term_instance() {		//다항식의 한 항을 만드는 함수
	Term* t = (Term*)malloc(sizeof(Term));
	t->coef = 0;					//계수 = 0
	t->expo = 0;					//지수 = 0
	return t;						//항 반환
}


//다항식 객체를 생성하여 이름을 지정하는 함수
Polynomial* create_polynomial_instance(char name) {
	Polynomial* ptr_poly = (Polynomial*)malloc(sizeof(Polynomial));
	ptr_poly->name = name;		//동적할당된 객체를 적절하게 초기화해주지 않는 것이 종종 프로그램의 오류를 야기한다.
	ptr_poly->size = 0;			//이렇게 객체를 생성하고 기본값으로 초기화해주는 함수를 따로 만들어 사용하는 것은 좋은 방법이다.
	ptr_poly->first = NULL;
	return ptr_poly;			//다항식 객체 반환
}


//항을 추가하는 함수
void add_term(int c, int e, Polynomial* poly) {			//(계수, 지수, 객체)
	if (c == 0)								//계수(c)가 0이면 값이 0인 항이므로 return함
		return;
	Term* p = poly->first, * q = NULL;		//변수 p와 q 생성. p는 다음 항 저장, q는 p값 저장
	while (p != NULL && p->expo == e) {		//끝까지 읽기 전, p의 지수가 매개변수 e와 동일할 때까지 반복
		q = p;
		p = p->next;
	}

	if (p!=NULL && p->expo == e) {			//동일 차수의 항이 존재하는 경우
		p->coef += c;						//동일 차수이므로 기존 계수에 함수의 매개변수로 받은 계수 c 합함.
		if (p->coef == 0) {					//더했더니 계수가 0이 되는 경우
			if (q == NULL)					//q의 다음 노드를 삭제한다. 단, q가 NULL이면 첫번째 노드를 삭제한다.
				poly->first = p->next;		//q가 NULL이면 다음 노드를 삭제할 수 없기 때문.
			else
				q->next = p->next;
			poly->size--;
			free(p);						//불필요해진 노드 p를 free시킨다.
		}
		return;
	}
	
	Term* term = create_term_instance();	//여기까지 실행이 된다면 동일 차수의 항이 없는 경우이므로 새로운 term 생성
	term->coef = c;
	term->expo = e;

	if (q == NULL) {						//맨 앞에 삽입하는 경우
		term->next = poly->first;			//term의 다음 항에 기존 첫 항을 저장
		poly->first = term;					//객체의 첫 항에 term 주소 저장
	}
	else {									//q의 뒤, p의 앞에 삽입(p는 null일 수도 있음)
		term->next = p;
		q->next = term;
	}
	poly->size++;							//항의 개수 1 증가
}

//body부분을 해석해서 다항식 객체를 만들고 그 주소를 리턴해주는 함수
Polynomial* create_by_parse_polynomial(char name, char* body)	//name = 다항식 이름, body = 다항식
{
	Polynomial* ptr_poly = create_polynomial_instance(name);	//name의 이름을 가진 다항식 객체 생성
	int i = 0, begin_term = 0;
	while (i < strlen(body)) {
		if (body[i] == '+' || body[i] == '-')				//+ 혹은 -의 기호를 읽음
			i++;
		while (i < strlen(body) && body[i] != '+' && body[i] != '-')	//하나의 항이 끝날때까지 전진
			i++;
		int result = parse_and_term(body, begin_term, i, ptr_poly);		//body[begin_term, i)까지가 하나의 항이다. 이 항을 인식해서 다항식에 추가한다.
		if (result == 0) {									//잘못된 항일 경우 0을 반환하고, 그런 경우 만들고 있던 다항식 자체를 destroy한다.
			destroy_polynomial(ptr_poly);
			return NULL;
		}
		begin_term = i;										//다음 항의 시작 위치는 i가 된다.
	}
	return ptr_poly;
}

Term* parse_and_term(char* expr, int begin, int end, Polynomial* p_poly)
{
	int i = begin;
	int sign_coef = 1, coef = 0, expo = 1;					//+ 혹은 - 기호로 부터 계수의 부호를 결정한다. 하지만 +혹은 -기호가 없을 수도 있다.(첫 번째 항의 경우)
	if (expr[i] == '+')
		i++;
	else if (expr[i] == '-') {
		sign_coef = -1;		//부호가 - 임을 저장
		i++;
	}

	//계수의 절댓값 읽기
	while (i < end && expr[i] >= '0' && expr[i] <= '9') {	//digit들을 읽어서 계수의 절댓값(coef)를 계산한다. 하지만 digit들이 하나도 없을 수도 있다.(1 or -1)
		coef = coef * 10 + (int)(expr[i] - '0');
		i++;
	}
	if (coef == 0)											//coef가 0인 경우 계수는 0이 아니라 1혹은 -1이다.
		coef = sign_coef;	//계수
	else
		coef *= sign_coef;
	if (i >= end) {											//더이상 항을 구성하는 문자가 없다면 상수항이라는 의미
		add_term(coef, 0, p_poly);
		return 1;
	}
	//상수항이 아니라면 x임
	if (expr[i] != 'x')										//계수 다음에 x가 아닌 다른 문자가 등장해서는 안된다.
		return 0;
	i++;
	if (i > end) {											//계수 다음에 x가 나오고 문자열이 끝난다면 1차항이라는 의미이다.
		add_term(coef, 1, p_poly);
		return 1;
	}
	if (expr[i] != '^')										//x 다음에 ^가 아닌 다른 문자가 등장해서는 안된다.
		return 0;
	i++;
	expo = 0;
	while (i < end && expr[i] >= '0' && expr[i] <= '9') {	//지수 부분을 읽는다.
		expo = expo * 10 + (int)(expr[i] - '0');
		i++;
	}
	add_term(coef, expo, p_poly);
	return 1;
}

void insert_polynomial(Polynomial* ptr_poly) {
	for (int i = 0; i < n; i++) {
		if (polys[i]->name == ptr_poly->name) {
			destroy_polynomial(polys[i]);						//다항식을 덮어쓸 경우에는 기존의 다항식 객체를 free시켜줘야 한다.
			polys[i] = ptr_poly;
			return;
		}
	}
	polys[n++] = ptr_poly;
}

void destroy_polynomial(Polynomial* ptr_poly)
{
	if (ptr_poly == NULL)
		return;
	Term* t = ptr_poly->first, * tmp;
	while (t != NULL) {
		tmp = t;
		t = t->next;					//다항식에 속한 모든 항들을 free시킨다.
		free(tmp);
	}
	free(ptr_poly);						//ptr_poly가 가리키는 다항식 객체를 free시킨다.
}

 

*Polynomial* create_by_add_two_polynomials(char name, char f, char g)

-새로운 empty 다항식을 만든 후, 두 다항식의 모든 항들을 더하는 함수

 

위의 함수를 완성하지 못함. 추후 보완 예정