[자료구조] 2. 배열

1. 배열의 정의

💡

배열 : 일정한 차례와 간격에 따라 벌여 놓은 자료형

1.1 배열의 정의

인덱스와 원소값(index, value) 의 쌍으로 구성된 집합으로 정의된 각 인덱스는 그 인덱스와 관련된 값을 가진다.

1.2 배열의 특성

1. 원소들이 모두 같은 자료형, 즉 동질의 값과 기억 공간의 크기가 같다.

2. 배열의 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스 순서(논리적 순서) 와 일치한다.

3. 배열의 인덱스 값을 이용해서 배열의 원소값에 직접 접근(direct access) 한다.

 

→

배열의 인덱스 번호는 사람(개발자)가 이해할 수 있도록 정의한 (추상화) 값이다.

 

배열에서 인덱스 번호를 알고 있을 때 원소를 찾아내는 방법의 시간복잡도를 O(1)로 두는 이유에 대해 궁금했었는데, 이는 배열이 시작 주소로부터 일정한 간격으로 메모리 주소가 증가하기 때문에 가능한 것 이었음.

 

2. 배열 추상 자료형

ADT Array

• objects: <i$\in$ Index, e$\in$ Element> 쌍들의 집합. 여기서 Index는 순서를 나타내는 원소의 유한집합이고 Element는 타입이 같은 원소의 집합

• 배열 객체의 정의: <i$\in$ Index, e$\in$ Element> 쌍들의 집합이며, Index는 순서를 나타내는 정수값이고 Element는 같은 자료형의 원소값

• 연산: a$\in$ Array; i$\in$ Index; x, item$\in$Element; n$\in$Integer인 모든 a, item, n에 대하여 다음과 같은 연산이 정의된다.(a는 0개 이상의 원소를 갖는 배열, item은 배열에 저장되는 원소, n은 배열의 최대 크기를 정하는 정수값)
  1. Array create(n) → 배열의 크기가 n인 빈 배열을 생성 후 배열을 반환.
  2. Element retrieve(a, i)if i$\in$ Index:else 인덱스 i가 배열 a의 크기를 벗어나면 에러 메시지를 반환
  3. then 배열 a의 i번째 위치의 원소값 'e' 반환
  3. Array store(a, i, e)if i$\in$ Index:else 인덱스 i가 배열 a의 크기를 벗어나면 에러 메시지를 반환
  4.  
  5. then 배열 a의 i번째 위치에 원소값 'e'를 저장 후 배열 a를 반환

3. 배열의 연산의 구현

배열 추상 자료형의 연산을 요약

1. create: 배열을 공백 배열로 생성

2. retrieve: i 번째 인덱스에 저장되어 있는 원소값을 반환하는 연산

3. store: 원하는 위치 i번째 인덱스에 e 원소값을 저장하는 연산

 

3.1 C로 구현해보기 - create

void create(int n) {
		
		int arr[n];
		int i;
		for(i=0, i<n, i++) {
				a[i] = 0;
		}
}

3.2 C로 구현해보기 - retrieve

#define array_size 5
int retrieve(int *a, int i) {
		if(i >= 0 && i < array_size) return a[i];
		else {
				printf("Not exist index Exception");
				return -1;
		}
}

3.3 C로 구현해보기 - store

#define array_size 5
void store(int *a, int i, int e) {
		if(i >= 0 && i < array_size) a[i] = e;
		else {
				printf("Not exist index Exception");
		}

4. 1차원 배열

한 줄짜리 배열이므로 메모리 영역도 한 줄로 할당받는다. 따라서 첫 번째 원소 A[0]의 메모리 시작주소를 라고 하고 각 자료형의 크기 k를 알면 간단한 계산을 통해 A[i]의 주소를 알 수 있다.

💡

A[i] Memory address = $a+i\times k$

5. 배열의 확장

• 1차원 배열의 확장은 2차원 배열이다. 하지만 확장 방법에 있어서 차이가 있다.
  1. 행우선 (raw-major) 확장
     메모리 할당 a[0][0] → a[0][1] → ... → a[1][0] → ...
  2. 열우선 (column-major) 확장 메모리 할당 a[0][0] → a[1][0] → ... → a[0][1] → ....

 

• C언어에서는 2차원 배열 선언 시 행우선으로 할당된다.

6. 희소행렬의 개념

• 행렬 내부에 가비지 데이터가 지나치게 많을 경우 행렬을 추상화 하여 유효 데이터의 행번호, 열번호, 원소값의 형태로 새로운 행렬을 추출해낸 것0 8 9 102 0 7 11....
•  
• 8 x 9 행렬 내부에 있는 유효데이터 10개의 위치를 기록한 행렬 (나머지는 다 가비지 데이터)
• 3 2 0 11
• 1 0 4 9