선형 자료구조 정리 (배열)

배열(Array)이란?

배열은 거의 모든 프로그래밍 언어에서 기본적으로 제공되는 자료형으로 많은 고급 자료구조들에서 사용된다.

배열은 주로 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다.

 

배열의 가장 기본적인 특징은 '인덱스, 요소' 쌍의 집합이라는 것이다. 즉, 인덱스가 주어지면 해당하는 요소가 대응되는 자료구조이다. 배열에서는 모든 요소가 동일한 자료형이며 인덱스를 사용하여 직접 접근 할 수 있다.

 

배열의 추상 자료형

(객체)

'인덱스, 요소' 쌍의 집합

 

(연산)

create(n) : n개의 요소를 가진 배열을 생성한다.

retrieve(i) : 배열의 i번째 요소를 반환한다.

store(i, item) : 배열의 i번째 위치에 item을 저장한다.

 

배열과 메모리

[그림 1] int형 1차원 배열과 각 요소의 주소

[그림 2] 2차원 배열의 선언

함수의 파라미터로서의 배열

배열의 이름은 포인터의 역할을 한다. 즉, 배열의 이름을 전달하면 배열의 포인터가 전달되는 것이다.

따라서 함수 안에서 파라미터로 배열을 받아서 배열의 내용을 수정하면 원래의 배열이 수정된다.

 

C나 C++에서는 파라미터로 전달 받은 배열의 길이를 알 수 있는 방법이 없다. 따라서 배열을 전달할때 반드시 배열의 길이도 함께 전달해야 한다.

 

만일 2차원 배열을 매개변수로 넘긴다면 해당 배열의 가로 값을 지정해줘야한다. 2차원 배열을 넘길때마다 가로 값을 지정해 주는 것은 번거롭기 대문에 보통은 동적 할당과 2중 포인터를 이용해서 이 문제를 해결한다.