연결리스트 - 다항식

※ 인프런 강의 "C로 배우는 자료구조 및 여러가지 예제실습(권오흠 교수님)"를 보고 개인적인 복습을 위해 정리한 내용입니다.

 

 

내림차순으로 정렬된 항에서 새로운 항을 삽입해야 하므로 두 포인터 p, q 를 이용한다.

공식처럼 외워야 할 것은 정렬된 항에서 삽입할 때에는 두 포인터를 이용하는 것이 좋다는 것이다.

그리고 이때 q는 항상 p의 한발 뒤를 따라가야 한다. addafter 가 간단하기 때문이다.

 

Term p = first;
Term q = null;

while (p != null && p.expo > e) {
 	q = p; // q는 항상 p의 한발 뒤를 따라감
 	p = p.next;
}

	add_after(q);

 

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

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

 

 

 

 

 

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;                     /* 계수를 더한다 */
 	if (p->coef == 0) {   /* 더했더니 계수가 0이 되는 경우, q의 다음 노드를 삭제 */
 		if (q==NULL)      /* q가 NULL일 경우, 첫번째 노드를 삭제 */
 			poly->first = p->next;
 		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;
 		poly->first = term;
 	}
 	else {          /* q의 뒤, p의 앞에 삽입 */
 		term->next = p;
 		q->next = term;
 	}
    
 	poly->size++;
}

 

새로운 항을 삽입할 위치를 선정하고 나서 고려해야할 상황이 있다.

 

① 동일 차수의 항이 존재한다.    =>    계수를 더한다.    =>     계수 = 0이 될 경우, p를 삭제한다. (이때, p가 첫번째 항이냐 아니냐를 고려해 삭제한다)

② 동일 차수의 항이 존재하지 않는다.    =>   create_term_instance 로 동적할당을 해서 새로운 항을 만든다.       => p가 첫번재 항이냐 아니냐를 고려해 삽입한다.

 

term을 q의 뒤, p의 앞에 삽입

 

 

 

 

 

 

다항식의 값을 계산하는 함수

 

int eval(Polynomial *poly, int x) {
 	int result = 0;
 	Term *t = poly->first;      /* 다항식 첫번째 항을 t라고 가정 */
 	while(t != NULL) {         /* t가 NULL 아닌동안 */
 		result += eval(t, x);     /* 계산, eval 함수식은 밑에 있다 */
 		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;)

 

 

 

 

 

 

다항식 출력하기

 

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

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

 

f = 2x^2 - x + 10 이렇게 출력하기 위해서 print_poly 함수를 작성한다.

 

 

 

 

 

 

명령 처리하기

 

void process_command()
{
 	char command_line[BUFFER_LENGTH];
 	char copied[BUFFER_LENGTH];    /* 입력 라인 복사 저장공간 */
 	char *command, *arg1, *arg2;
 	while(1) {
 		printf("$ ");
 		if (read_line(stdin, command_line, BUFFER_LENGTH) <= 0)    /* 라인 단위로 입력 받음 */
 			continue;
 		strcpy(copied, command_line);    /* 입력 라인을 복사해둔다 */
        
 		command = strtok(command_line, " ");   /* 명령어는 command 변수에 저장 */
        
 		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) {    /* 예: calc f 12 명령일 때 처리하는 경우 */
 		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);   /* 차례대로 f 12 처리 */
 }
 
 	else if (strcmp(command, "exit") == 0)
 		break;
 	else {
 		handle_definition(copied);    /* 다항식을 입력받아 정의하는 일을 한다 */
 		}
 	}
}

 

handle_definition(copied) 는 f = 2x^2 - 6x + 10 이런 식으로 정의할 수도 있고, 혹은 f = f + g 이런식으로 새로운 함수식으로 정의도 가능하다. 이때 아직 토크나이징이 되지 않은 상태에서 매개변수로 넘겨줘서 처리해주도록 한다.

 

 

 

 

void handle_definition(char *expression) {

 	erase_blanks(expression);    /* 먼저 모든 공백 문자들을 제거한다 */
 
 	char *f_name = strtok(expression, "=");
 	if (f_name == NULL || strlen(f_name) != 1) {
 		printf("Unsupported command.");
 		return;
 	}
    
 	char *exp_body = strtok(NULL, "=");
 	if (exp_body == NULL || strlen(exp_body) <= 0) {
 		printf("Invalid expression format.--");
 		return;
    }
    
     /* 1. 두 다항식을 더해서 새로운 다항식을 만드는 일은 다른 함수가 처리 */
    if (exp_body[0]>='a' && exp_body[0]<='z' && exp_body[0]!='x') { /* a-z이면서 x는 아님 */
 		char *former = strtok(exp_body, "+");   /* f = g + h 일때 '+'를 토크나이징 */
 		if (former==NULL || strlen(former) != 1) {    /*  g  */
 			printf("Invalid expression format.");
 			return;
		}
 		char *later = strtok(NULL, "+");
 		if (later==NULL || strlen(later) != 1) {     /*  h  */
 			printf("Invalid expression format.");
 			return;
 		}
        
		Polynomial *pol = create_by_add_two_polynomias(f_name[0], former[0], later[0]);
 
 		if (pol == NULL) {
 			printf("Invalid expression format.");
 			return;
 		}
 		insert_polynomial(pol);
        }
        
        /* 2. 함수를 새로 정의하는 경우, f = .... 과 같을 때 */
         else {    
 			Polynomial *pol = create_by_parse_polynomial(f_name[0], exp_body);
 			if (pol == NULL) {
 				printf("Invalid expression format.");
 				return;
 			}
 			insert_polynomial(pol);
 			}
}

 

이때 erase_blanks 함수는 문자배열에서 모든 공백 문자들을 제거하여 압축하는 역할(=공백을 없애고 하나씩 앞으로 땡기기)을 수행하는데 추가로 문자열 끝에 '\0' 추가해준다.

 

f = 2x^3 - 5x + 10 일때, f_name은 f 가 해당이고, exp_body는 = 뒤의 나머지 식이다.

 

strtok 함수 복습 ▼

2021.06.22 - [자료구조] - 전화번호부 v3.0 - 배열 재할당, 라인단위 입력과 문자열 tokenizing

 

 

erase_blanks 함수 (이런 식으로 작성해야 하지 않을까 싶다)

↓

char* erase_blank(char compressed[]) {
    char* str = (char*)malloc(sizeof(s));
    
    int i, k = 0;

    for (i = 0; i < strlen(compressed); i++)
        if (compressd[i] != ' ') str[k++] = compressd[i];

    str[k] = '\0';
    return str;
	}
}