[C언어/자료구조] 연결리스트 - 다항식

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

다항식이란 ?

• 1원다항식(일변수 다항식) : 변수가 하나인 다항식
• 단항식 : 하나의 항으로 이루어진 식
• 다항식/n항식 : 여러 개의 항으로 이루어진 식/n개의 항으로 이루어진 다항식
• 상수항 : 변수를 포함하지 않는 항
• 계수 : 변수의 거듭제곱에 곱하는 수 ( x2 - 2x + 3의 세 항의 계수는 각각 1, -2, 3 )
• 차수 : 변수를 거듭제곱한 지수 ( x2의 차수는 2 )
• 동류항 : 차수가 같은 항 ( x2 + 3x - x + 3에서 3x와 -x는 동류항 )
• 동류항이 있는 다항식 : 정리되지 않은 다항식으로, 계수를 더해 동류항들을 하나의 항으로 만들어야 한다. ( x2 + 3x - x + 3 를 정리한 다항식은 x2 + 2x + 3 ) 항의 개수나 최고차항(차수가 가장 높은 항)은 동류항이 모두 정리된 상태를 기준으로 한다.
• 일변수 다항식의 배열법 : 내림차순 - 차수가 높은 순에서 낮은 순으로 배열 / 오름차순 - 반대

출처 : https://ko.wikipedia.org/wiki/다항식

다항식 - 위키백과, 우리 모두의 백과사전

 

연결리스트 - 다항식

프로그램 개요

입출력

• 일변수 다항식(1원 다항식) 정의. 다항식의 이름은 x를 제외한 영문 소문자
• 변수는 항상 x
• 각 항의 지수는 음이 아닌 정수, 계수는 정수
• 연산자 앞뒤로 공백이 있을 수도 있고 없을 수도 있다
• 함수를 입력할 때는 내림차순이 아닐수 있고, 동류항이 존재할 수 있다
• 그러나 함수를 저장하고 출력할 때는 동류항이나 계수가 0인 항 없이 내림차순으로 정렬된 상태여야 한다
• 동일 이름의 함수를 새로 정의할 수 있고, 이 경우 기존의 함수는 지워진다

 

프로그램 기능 구현 / 자료구조

• 하나의 다항식 = 항들의 연결리스트
• 하나의 다항식을 표현하는 구조체 Polynomial 정의
• 하나의 항을 표현하는 구조체 Term 정의
• 변수 x의 값이 주어질 때 다항식의 값을 계산하는 함수 제공

 

구현하기

1) 구조체 정의하기

Polynomial 구조체
→name : 다항식의 이름
→first : 첫번째 항의 주소
→size : 항의 개수

typedef struct polynomial {
	char name;
	Term *first;
	int size = 0; 
} Polynomial; 
/* struct polynomial 정의하면서 동시에 Polynomial로 type definition */

Polynomial *polys[MAX_POLYS];
/* 다항식에 대한 포인터들의 배열 polys 선언. 여러 개의 다항식들의 주소 저장 */

int n = 0; 
/* 저장된 다항식의 개수, 현재 0개 */

 

Term 구조체
→coef : 항의 계수
→expo : 항의 지수(차수)
→next : 다음 항의 주소

struct term {
	int coef;
	int expo;
	struct term *next;
};

typedef struct term Term; /* struct term -> Term으로 type definition */

 

---

2) 다항식 객체 생성하기

동적으로 생성된 객체를 적절하게 초기화하지 않아서c 프로그램에 오류가 발생되는 경우가 종종 있다. 이러한 오류를 방지하기 위해서 객체를 생성하고 기본값으로 초기화해주는 함수를 따로 만들어 사용하는 것이 좋다.

 

create_term_instance 함수

다항식의 항 객체를 생성하고 기본값으로 초기화한 후 생성된 객체를 리턴한다.

Term *create_term_instance() {
	/* 객체 생성 */
	Term *t = (Term *)malloc(sizeof(Term));
	/* 기본값으로 초기화 */
	t->coef = 0;
	t->expo = 0;
	/* 생성된 객체 리턴 */
	return t;
}

 

create_polynomial_instance 함수

다항식 객체를 생성하면서 다항식의 이름을 지정해주고, 나머지는 기본값으로 초기화한 후 생성된 객체를 리턴한다.

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;
}

 

---

3) 다항식에 새로운 하나의 항 추가하기

동류항이 있는 경우 : 기존 항의 계수만 변경

동류항이 없는 경우 : 새로운 항 삽입 (내림차순 정렬 유지)

 

add_term 함수 (동류항이 없는 경우)

void add_term(int c, int e, Polynomial *poly) {
	/* 첫번째 항에서 시작한다 */
	Term p = first
	Term q = NULL;
	
	/* 차수가 높은 항 -> 낮은 항 순서대로 검사한다 */
	while (p != NULL & p.expo > e) {
		q = p;
		p = p.next;
	}
	
	/* 새로운 노드를 삽입할 위치는 q 다음이다 */
	add_after(q);
}

※ int c : 계수, int e : 지수, poly : 다항식

 

기존의 term 중에서 e와 동일한 expo 값을 갖는 term이 있다면(=동류항이 있다면),

해당 term의 coef += c; 로 계수만 더해준다.

 

기존의 term 중에 e와 동일한 expo 값을 갖는 term이 없다면(=동류항이 없다면),

coef = c, expo = e인 새로운 항을 삽입한다.

삽입할 위치는 이전 term의 expo < e < 다음 term의 expo인 자리이다.

삽입할 위치를 찾기 위해서는 새로운 항보다 차수가 작거나 같은 항이 나올때까지 첫 번째 항부터 순서대로 검사(순회)해야 한다.

이 때 새로운 항보다 차수가 작거나 같은 항이 나올 때까지 검사하다보면,

삽입할 위치의 다음 항에 도달하게 된다. 그런데 연결리스트에서 노드를 삽입하기 위해서는 이전 노드(이전 항)의 주소가 필요하다.

 

이런 상황을 해결하는 데 가장 많이 쓰이는 방법은

포인터 두 개(p, q)를 준비해서

p를 연결리스트의 노드들을 순회하면서 특정한 노드를 찾는 데 쓰고,

q는 p의 뒤를 쫓아가면서 p 이전 노드주소를 저장하는 데 쓰는 것이다.

 

add_term 함수 (동류항이 있는 경우, 없는 경우 모두 고려)

void add_term(int c, int e, Polynomial *poly) {
	if (c == 0)
		return;
	
	/* 첫번째 항부터 시작 */
	Term *p = poly->first, *q = NULL;

	/* 새로운 항보다 차수가 작거나 같은 항이 나올때까지 순회 */
	while (p!= NULL && p->expo > e) {
		q = p;
		p = p->next;
	}
	
	/* 동류항(차수가 같은 항)이 있는 경우 : 계수 더하기 */
	if (p!=NULL & p->expo == e) {
		p->coef += c;
		/* 계수가 0이 되었을 때 : p 삭제 */
		if(p->coef == 0) { 
			if (q==NULL) //p가 첫번째 노드일 때
				poly->first = p->next;
			else 
				q->next = p->next;
			poly->size--;
			free(p); //메모리에서 p 해제
		}
		return;
	}

	/* 동류항이 없는 경우 : 새로운 항 삽입 */
	Term *term = create_term_instance();
	term->coef = c;
	term->expo = e;
	
	if (q==NULL) { //맨 앞에 삽입하는 경우
		term->next = poly->first;
		poly->first = term;
	} 
	else { //q의 뒤, p의 앞에 삽입 (p는 NULL일 수도 있음)
		term->next = p;
		q->next = term;
	}
	poly->size++;

}

 

---

4) 다항식의 값 계산하기

eval 함수

/* 다항식의 값을 계산하는 함수 */
int eval(Polynomial *poly, int x) {
	int result = 0;
	Term *t = poly->first;
	while (t != NULL) {
		result += eval(t, x); //하나의 항의 값 계산해 결과에 더하기
		t = t->next; //다음 항으로 넘어가기
	}
	return result;
}

/* 하나의 항의 값을 계산하는 함수 */
int eval(Term *term, int x) {
	int result = term->coef;
	for (int i=0; i < term->expo; i++) {
		result *= x;
	}
	return result;
}

하나의 항 cx^e의 값을 계산하기 위해서는

계수 c에 x를 e번 곱하면 된다.

따라서 result = c (result = term→coef)로 초기화하고,

e번만큼 반복문을 돌면서 result에 x를 곱해주면 된다. (result *= x;)

 

---

5) 다항식 출력하기

print_poly 함수

void print_poly(Polynomial *p) {
	printf("%c=", p->name);
	Term *t = p->first;
	while ( t != NULL) {
		print_term(t);
		t = t->next;
	}
}

 

print_term 함수

void print_term(Term *t) {
	if(t->expo == 0) {
		if(t->coef > 0)
			printf("+%d", t->coef);
		else
			printf("%d", t->coef);
	} 
	else if(t->expo == 1) {
		if(t->coef > 0)
			printf("+%dx", t->coef);
		else
			printf("%dx", t->coef);
	} 
	else {
		if(t->coef > 0)
			printf("+%dx^%d", t->coef, t->expo);
		else
			printf("%dx^%d", t->coef, t->expo);
	}
}

 

---

6) 사용자의 명령 입력받아 처리하기

process_command 함수

void process_command() {
    char command_line[BUFFER_LENGTH];
    char copied[BUFFER_LENGTH];
    char *command, *arg1, *arg2;
    strcpy(copied, command_line);

    while (1) {
        printf("$ ");
        if (read_line(stdin, command_line, BUFFER_LENGTH) <= 0)
            continue;

        command = strtok(command_line, " ");
        if (strcmp(command, "print") == 0) {
            arg1 = strtok(NULL, " ");
            if (arg1 == NULL) {
                printf("Invalid arguments.\n");
                continue;
            }
            handle_print(arg1[0]);
        }
        else if (strcmp(command, "calc") == 0) {
            arg1 = strtok(NULL, " ");
            if (arg1 == NULL) {
                printf("Invalid arguments.\n");
                continue;
            }
            arg2 = strtok(NULL, " ");
            if (arg2 == NULL) {
                printf("Invalid arguments.\n");
                continue;
            }
            handle_calc(arg1[0], arg2);
        }
        else if (strcmp(command, "exit") == 0) {
            break;
        }
        else {
            handle_definition(copied);
        }
    }
}

라인 단위로 입력을 받은 다음, 단어 단위로 tokenizing 해서 처리한다.