[자료구조] 배열 - 다항식 더하기

높은 차수부터 저장하기

#define MAX_DEGREE 101

typedef struct {
	int degree;
	float coef[MAX_DEGREE];
}polynomial;

polynomial a = { 5, {10, 0, 0, 0, 6, 3 } }; //차수 큰 것부터 저장

polynomial poly_add1(polynomial A, polynomial B) {
	polynomial C; //결과 다항식
	int Apos = 0, Bpos = 0, Cpos = 0; //배열 인덱스

	//지금 보고 있는 항 차수, 최대차항에서 출발
	int degree_a = A.degree; 
	int degree_b = B.degree;

	C.degree = MAX(A.degree, B.degree); //결과 다항식 차수

	while (Apos < A.degree && Bpos < B.degree) {
		if (degree_a > degree_b) { //A항 > B항 
			C.coef[Cpos++] = A.coef[Apos++];
			degree_a--;
		}
		else if (degree_a == degree_b) { //A항 == B항 
			C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
			degree_a--;
			degree_b--;
		}
		else //B항 > A항 
		{
			C.coef[Cpos++] = B.coef[Bpos++];
			degree_b--;
		}
	}
	return C;
}

---

낮은 차수부터 저장하기

poly_add1_alt(a, b): 

  C.degree = Max(a.degree, b.degree)
  
  while (index_a와 index_b가 모두 0보다 크거나 같으면)
    if (a항>b항)
      c항에 a항을 저장
      index_a, index_c --
    else if (a항==b항)  
      c항에 a항 + b항을 저장  
      index_a, index_b, index_c --
    else //a항<b항 
      c항에 b항을 저장
      index_b, index_c --
      
  return c

pseudo 코드 이렇게 쓰는 게 맞나

polynomial poly_add1_alt(polynomial A, polynomial B) {
	polynomial C; //결과 다항식
	
	C.degree = MAX(A.degree, B.degree); //결과 다항식 차수

	//지금 보고 있는 항 차수, 최대차항에서 출발
	int degree_a = A.degree;
	int degree_b = B.degree;
	int degree_c = C.degree;

	while (degree_a >= 0 && degree_b >= 0) {
		if (degree_a > degree_b) { //A항 > B항 
			C.coef[degree_c--] = A.coef[degree_a--];
		}
		else if (degree_a == degree_b) { //A항 == B항 
			C.coef[degree_c--] = A.coef[degree_a--] + B.coef[degree_b--];
		}
		else //B항 > A항 
		{
			C.coef[degree_c--] = B.coef[degree_b--];
		}
	}
	return C;
}