기본 자료구조; 배열의 개념과 응용(다항식 구현)

배열이란?

-> 일반적으로 같은 형의 변수를 여러 개 만드는 경우에 사용.

 

 

 

 

 

 

˙ 개념

int A[6];         //1차원 배열
char s[12] = "game over"       //문자열, terminating null character인 '\0'을 포함.
int A[4][3] = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}}       //2차원 배열, 행 우선.
int A[3][3][3];        //3차원 배열

 

 

* 2차원 배열에서의 실제 주소 구하기

: 2차원 정수 배열  A[m][n]에서 A[j][k]의 실제 주소 = base + ( j x n + k ) x sizeof(int)

 

* 3차원 배열에서의 실제 주소 구하기

: 3차원 실수 배열 A[l][m][n]에서 A[i][j][k]의 실제 주소 = base + ( i x m x n + j x n + k ) x sizeof(float)

 

 

 

 

 

 

˙ 응용

 

 

- 다항식(polynomial)

p(x) = 10x5 + 0x4 + 0x3 + 0x2 + 6x1 + 3x0

 

 

1. 다항식의 모든 항에 대한 정보를 배열에 저장

typedef struct {
	int degree;
    	int coef[MAX_DEGREE];
} polynomial;
polynomial a = {5,{10,0,0,0,6,3}}     //차수: degree - i(배열 index)

//polynomial a = {5,{3,6,0,0,0,10}}   차수: i

장점 : 다항식의 각종 연산이 간단해진다.

단점 : 대부분의 항의 계수가 0이면 공간 낭비가 심하다.

 

//예시: 다항식의 덧셈 연산

#include <stdio.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MAX_DEGREE 101

typedef struct{			//다항식 구조체 타입 선언
	int degree			//다항식의 차수
	int coef[MAX_DEGREE];		//다항식의 계수
}polynomial;

// C = A+B, A와 B는 다항식.
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{		//A항 < B항
			C.coef[Cpos++] = B.coef[Bpos++];
			degree_b--;
		}
	}
	return C;
}

//주 함수
main(){
	polynomial a = {5,{3,6,0,0,0,10}};
	polynomial b = {4,{7,0,5,0,1}};
	polynomial c;
    c = poly_add1(a,b);
}

 

 

 

2. 다항식의 0이 아닌 항만을 배열에 저장 - 희소다항식(sparse polynomial)

(계수, 차수) 형식으로 배열에 저장

struct{
	int coef;
	int exp;
} terms[MAX_TERMS] = {{10,5},{6,1},{3,0}}

장점 : 공간 낭비가 비교적 적다, 하나의 배열로 여러 개의 다항식을 나타낼 수도 있다. (별도의 index로 구분)

단점 : 연산 구현이 복잡해진다.

 

//예시: 다항식의 덧셈 연산

#include <stdio.h>
#define MAX_TERMS 101

struct{
	int coef;
	int exp;
}terms[MAX_TERMS]={{8,3},{7,1},{1,0},{10,3},{3,2},{1,0}}
int avail=6;	//빈 인덱스 중 가장 작은 값을 저장

char compare(int a, int b)		//두 개의 정수를 비교
{
	if(a>b) return '>';
	else if(a==b) return '=';
	else return '<';
}

void attach(float coef, int exp)		//새로운 항을 다항식에 추가
{
	if(avail>MAX_TERMS){
		fprintf(stderr,"항의 개수가 너무 많음\n");
        exit(1);
	}
	terms[avail].coef = coef;
    terms[avail++].exp = exp;
}

poly_add2(int As, int Ae, int Bs, int Be, int *Cs, int *Ce)		//다항식 C가 시작하는 인덱스와 끝나는 인덱스는 함수 내에서 정해지기 때문에 포인터로 받음
{
	float tempcoef;
	*Cs = avail;
    
	while(As <= Ae && Bs <= Be){
		switch(compare(terms[As].exp, terms[Bs].exp)){
			case '>':
				attach(terms[As].coef, terms[As].exp;
				As++; break;
			case '=':
				tempcoef = terms[As].coef+terms[Bs].coef;
				if(tempcoef)   //tempcoef가 0이 아닌 경우에만 추가
					attach(tempcoef, terms[As].exp);
				As++; Bs++; break;
			case '<':
				attach(terms[Bs].coef, terms[Bs].exp);
				Bs++; break;
		}
	}
    
	//A의 나머지 항들을 이동함
	for(;As<=Ae;As++)
		attach(terms[As].coef, terms[As].exp);
	//B의 나머지 항들을 이동함
	for(;Bs<=Be;Bs++)
		attach(terms[Bs].coef, terms[Bs].exp);
	*Ce = avail-1;
}

void main(){
	int Cs, Ce;
	poly_add2(0,2,3,5, &Cs, &Ce);
}

 

 

 

- 희소 행렬(대부분의 항들이 0인 행렬)을 구현하는 경우에도 위의 두가지 방법을 사용할 수 있으며, 장단점도 똑같다.