배열
- 배열은 같은 종류의 데이터를 메모리상에 일렬로 나열한 것이다.
- 하나의 변수에 여러 개의 데이터가 들어있는 구조다.
- 같은 type의 변수를 여러 개 만드는 경우에 사용된다.
- int list1, list2, list3, list4, list5, list6; -> int list[6];
배열의 구조
배열에는 배열 요소와 배열 인덱스 구조로 이루어져 있다.
일반적으로 변수는 집 주소가 하나인 단독주택과 같이, 메모리에 올라가는 주소가 하나로 할당되게 된다.
배열은 여러 개의 집이 모여서 구성된 아파트와 같다. 메모리에 올라가는 주소가 type의 크기만큼 연속하여 할당되게 된다.
배열의 다항식 표현
첫 번째 방법 : 다항식의 모든 항을 배열에 저장하는 방법
- 모든 차수에 대한 계수의 값을 배열로 저장한다.
- 하나의 다항식을 하나의 배열로 표현한다.
- 장점: 간단하고 차수의 계수를 찾기 쉽다.
- 단점: 대부분의 항의 계수가 0인 희소 다항식의 경우 공간 낭비가 된다.
#define MAX_DEGREE 101 //다항식의 최대 차수 + 1
typedef struct {
int degree;
float coef[MAX_DEGREE]
}polynomial;
polynomial a = {5, {10, 0, 0, 0, 6, 3} };두 번째 방법 : 다항식의 0이 아닌 항만을 배열에 저장하는 방법
- 다항식에서 0이 아닌 항만을 배열에 저장한다.
- (계수, 차수)형식으로 배열에 저장한다.
- 10x^5+6x+3 -> ((10,5), (6,1), (3,0))
#define MAX_TERMS 101
typedef struct {
float coef;
int expon;
}polynomial;
polynomial terms[MAX_TERMS]={ {8,3}, {7,1}, {1,0}, {10,3}, {3,2}, {1,0} };
int As = 0, Ae = 2; //배열에서 다항식 A의 시작과 끝에 대한 인덱스 정보
int Bs = 3, Be = 5; //배열에서 다항식 B의 시작과 끝에 대한 인덱스 정보
int avail = 6; //배열에서 비어 있는 인덱스배열의 희소행렬 표현
배열을 이용하여 행렬을 표현하는 두 가지 방법이 있다.
첫 번째 방법 : 2차원 배열을 이용하여 배열의 전체 요소를 저장하는 방법
- 장점: 행렬의 연산들을 간단하게 구현할 수 있다.
- 단점: 대부분의 항들이 0인 희소 행렬의 경우 메모리 공간 낭비가 심하다.
A = [2 3 0] B = [0 0 0 7 0 0]
[8 9 1] [9 0 0 0 0 8]
[7 0 5] [0 0 0 0 0 0]
[6 5 0 0 0 0]
[0 0 0 0 0 1]
[0 0 2 0 0 0]두 번째 방법 : 행렬에서 0이 아닌 요소들만 저장하는 방법
- 장점: 0이 많은 희소 행렬의 경우, 메모리 공간의 절약이 가능하다.
- 단점: 각종 행렬 연산들의 구현이 복잡하다.
B = [0 0 0 7 0 0] B = [0 3 7]
[9 0 0 0 0 8] [1 0 9]
[0 0 0 0 0 0] -> [1 5 8]
[6 5 0 0 0 0] [3 0 6]
[0 0 0 0 0 1] [3 1 5]
[0 0 2 0 0 0] [4 5 1]
[5 2 3]