[자료구조] 배열

배열

배열의 개념

배열은 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용된다. 예를 들어서 6개의 정수를 저장할 공간이 필요한 경우, 배열이 없다면 다음과 같이 6개의 정수형의 변수를 선언하여야 할 것이다.

int list1, list2, list3, list4, list5, list6

그러나 배열이 지원된다면 아주 간단하게 다음과 같이 선언하면 된다.

int list[6]

배열을 사용하면 "연속적인 메모리 공간"이 할당되고 인덱스(index) 번호를 사용하여 쉽게 접근이 가능하기 때문에 반복 루프를 이용하여 여러가지 작업을 손쉽게 할 수 있다.

 

배열 ADT(추상 자료형)

배열을 추상 자료형으로 정의하여 보자. 즉 배열을 단순히 "연속적인 메모리 공간"으로만 보지 말고 배열의 핵심적인 내용을 추상적으로 살펴보자. 배열은 <인덱스, 값>의 쌍으로 이루어진 집합으로 정의할 수 있다. 즉 인덱스(index)가 주어지면 해당하는 값(value)이 대응되는 자료 구조이다. 수학적으로 배열은 인덱스에서 값으로의 사상(mapping)에 해당된다. 배열에서는 어떤 연산을 생각할 수 있을까? 주어진 인덱스에 값을 저장하는 set 연산과 인덱스가 주어지면 해당되는 값을 추출하는 get 연산을 생각할 수 있다.

 

객체 : <인덱스, 값> 쌍의 집합
연산 : 
- create(size) ::= size개의 요소를 저장할 수 있는 배열 생성
- get(A, i) ::= 배열 A의 i번째 요소 반환
- set(A, i, v) ::= 배열 A의 i번째 위치에 값 v 저장

 

1차원 배열

컴파일러는 배열을 어떻게 구현할까? 컴파일러는 배열에 메모리의 연속된 위치에 할당한다. 첫 번째 배열 요소인 list[0]의 주소가 기본주소가 되고 다른 요소들의 주소는 다음과 같이 된다.

배열이 int list[6]; 일 때,

배열의 요소	메모리 주소
list[0]	기본주소 = base
list[1]	base + 1 * sizeof(int)
list[2]	base + 2 * sizeof(int)
list[3]	base + 3 * sizeof(int)
list[4]	base + 4 * sizeof(int)
list[5]	base + 5 * sizeof(int)

 

구조체

배열이 타입이 같은 데이터의 모임이라면 구조체(structure)는 타입이 다른 데이터를 묶는 방법이다.

struct studentTag
{
	char name[10];	// 문자배열로 된 이름
	int age;		// 나이를 나타내는 정수값
	double gpa;		// 평균평점을 나타내는 실수값
}

구조체는 중괄호를 사용하여 선언 시에 초기화하는 것이 가능하다.

struct studentTag s = { "Kim", 20, 4.3 };

 

 

참고

• C언어로 쉽게 풀어쓴 자료구조 책