polynomial을 표기할 두가지 방법 - dense와 sparse Expression

ploynomial은 연결 리스트를 구현하는 데 있어서 필요한 abstart입니다. 구조체를 이용해서 선언됩니다. 크게 두가지 방향을 통해 구현가능한데 먼저 Dense Expression, 그리고 Sparse Expression입니다.
다항식은 <계수, 지수> 의 쌍들로 이루어져있습니다
Dense Expression은 값을 A(X) = anX^n + a(n-1)X^n-1+...a0 이렇게 구성되어
만약 다항식이 2x^3 + 3x^2 +4 라면
4 0 3 2 로 저장됩니다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_DEGREE 100
typedef struct{
  int degree;
  int coef[MAX_DEGREE];
}polynomial;
polynomial add(polynomial, polynomial);
void polynomial_print(polynomial);
int main(void) {
  int i;
  polynomial p1,p2,p3;
  p1.degree=-1; 
  p2.degree=-1;
  p3.degree=-1;  // 코드에서 다항식의 최고차항을 -1로만들어 초기화합니다
  for(i=0;i<MAX_DEGREE;i++){
    p1.coef[i]=0; 
    p2.coef[i]=0; // 계수를 0으로 초기화시킴
  }
  p1.degree=2, p1.coef[2]=3,p1.coef[1]=2,p1.coef[0]=1; // p1 = 3x^2 + 2x + 1
  p2.degree=4, p2.coef[4]=1,p2.coef[2]=2,p2.coef[0]=3; // p2 = x^4 + 2x^2 + 3
  polynomial_print(p1);
  polynomial_print(p2);
  p3=add(p1,p2);
  polynomial_print(p3);
  return 0;
}
polynomial add(polynomial p1, polynomial p2){
  polynomial p3;
  int i, j;
  p3.degree=-1;
  if(p1.degree > p2.degree){ // p3의 최고차항값 알아내기
    p3.degree = p1.degree;
  }
  else
    p3.degree = p2.degree;
  for(i=0;i<=p3.degree;i++){ // 상수항부터 최고차항까지 반복
    p3.coef[i] = p1.coef[i] + p2.coef[i]; // 같은 항은 합합
  }
  return p3;
}
void polynomial_print(polynomial p){
  int i;
  for(i=p.degree;i>=0;i--){// 최고차항부터 상수항까지 순서로 출력
    if(i!=0){
      printf("%dx^%d + ",p.coef[i],i); 
    }
    else
      printf("%d",p.coef[i]);
  }
  printf("\n");
}

해당 프로그램은 두 다항식을 더하는 과정입니다.
결과는
3x^2 + 2x + 1
x^4 + 2x^2 + 3
x^4 + 0x^3 + 5x^2 + 2x + 4
로 출력됩니다. 왜냐하면 계수값이 0이라도 degree보다 작다면 저장되기 때문입니다.
dense expression 같은 경우는 2x^1000 + 1과 같은 다항식을 표기할 때는 메모리 누수가 심합니다. 그럴 때는 Sparse Expression을 사용합니다.
Sparse Expression은 두개의 값을 지니는 형태로 저장됩니다. 그리고 그 항이 하나하나 증가될때마다 avail을 증가시키는 방식을 사용합니다.

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define COMPARE(x,y) (((x)<(y))?-1:((x)>(y)?1:0))   
typedef struct {
  int coef;
  int expon;
} polynomial;
polynomial terms[MAX]; // 총 항의 계수 = MAX
int avail =0; // 초기의 항의 갯수 0개
void attach(int coefficient, int exponent){ // 해당문은 계수, 지수를 저장하는 함수
  if(avail >= MAX){
    fprintf(stderr, "Too many terms in the polynomial\n");
    exit(1); // 총 항의 계수가 넘어설 경우 예외처리
  }
  terms[avail].coef = coefficient;
  terms[avail].expon = exponent;
  avail++;
}
void polynomial_add(int starta, int finisha, int startb, int finishb, int *startd, int *finishd){ // 두개의 다항식을 더하는 함수
  float coefficient; // 두개의 다항식의 계수를 저장하는 변수
  *startd = avail; // 다항식의 시작 위치를 저장하는 변수
  while(starta <= finisha && startb <= finishb){ // 두개의 다항식의 시작 위치가 끝 위치를 넘어설 때까지
  switch(COMPARE(terms[starta].expon,terms[startb].expon)){ // starta와 startb의 지수를 비교합니다
  case -1: // 아닐때
    attach(terms[startb].coef,terms[startb].expon); // startb의 지수가 더 클 경우 startb의 지수를 저장합니다
    startb++; // startb의 지수의 위치를 1증가시켜 뒤에 위치시킵니다
    break;
  case 0: // 같을 때
    coefficient = terms[starta].coef + terms[startb].coef; // 더함
    if(coefficient != 0){ 
      attach(coefficient, terms[starta].expon);
    }
    starta++;
    startb++;
    break;
  case 1: // case -1 과 같음
    attach(terms[starta].coef,terms[starta].expon);
    starta++;
    break;
  }
    
}
  for(;  starta <= finisha; starta++){ // starta가 finisha를 넘어설 때까지
    attach(terms[starta].coef, terms[starta].expon); 
  }
  for(; startb <= finishb; startb++){ // startb가 finishb를 넘어설 때까지
    attach(terms[startb].coef, terms[startb].expon);
  }
  *finishd = avail -1; // 다항식의 끝 위치를 저장하는 변수
}
void polynomial_print(int start, int finish){ // 다항식을 출력하는 함수
  int i;
  for(i = start; i<=finish; i++){ // 시작점부터 끝점까지 출력
    if(i != finish){
      printf("%dx^%d + ", terms[i].coef, terms[i].expon); 
    }
    else {
        printf("%dx^%d", terms[i].coef, terms[i].expon); 
    }
  }
  printf("\n");
}
int main(void) {
  int starta, finisha, startb, finishb, startd, finishd;
  starta = avail; // 다항식의 시작 위치를 저장하는 변수
  terms[avail].expon = 100;
  terms[avail].coef = 2; // 계수와 지수 입력
  avail++; // 다음 위치로
  terms[avail].expon = 0;
  terms[avail].coef = 3;
  finisha = avail;
  avail++;
  
  startb = avail; // 다항식의 시작 위치를 저장하는 변수
  terms[avail].expon = 3;
  terms[avail].coef = 1;
  avail++;
  terms[avail].expon = 4;
  terms[avail].coef = 2;
  avail++;
  terms[avail].expon = 0;
  terms[avail].coef = 3;
  finishb = avail;
  avail++; // 
  polynomial_print(starta, finisha);
  polynomial_print(startb, finishb);
  polynomial_add(starta, finisha, startb, finishb, &startd, &finishd);
  polynomial_print(startd, finishd);
  return 0;
}

해당 프로그램은 Sparse 표현으로 두 다항식의 값을 출력하는 프로그램입니다.

typedef struct {
  int coef;
  int expon;
} polynomial;
polynomial terms[MAX]; // 총 항의 계수 = MAX
int avail =0; // 초기의 항의 갯수 0개

다음과 같이 기초적으로 선언을 합니다. terms에는 각각 하나하나의 항이 저장이 됩니다.
항에는 계수와 지수가 저장이 됩니다.

 starta = avail; // 다항식의 시작 위치를 저장하는 변수
  terms[avail].expon = 100;
  terms[avail].coef = 2; // 계수와 지수 입력
  avail++; // 다음 위치로
  terms[avail].expon = 0;
  terms[avail].coef = 3;
  finisha = avail;
  avail++;
  
  startb = avail; // 다항식의 시작 위치를 저장하는 변수
  terms[avail].expon = 3;
  terms[avail].coef = 1;
  avail++;
  terms[avail].expon = 4;
  terms[avail].coef = 2;
  avail++;
  terms[avail].expon = 0;
  terms[avail].coef = 3;
  finishb = avail;
  avail++; // 

해당 형식처럼 구조체 내부에 지수와 계수를 대입하여 선언합니다.
변수값은 (expon, coef)두개씩 필요합니다. 그러므로 해당 표현은 고차다항식과 많은 값이 0인 경우에 유리합니다