[자료구조] 배열

배열의 정의

배열의 정의

• 일정한 차례나 간격에 따라 벌여놓음(사전적 정의)
• “차례” (순서) 와 관련된 기본적인 자료구조

→ 원소의 메모리 공간(메인 메모리, DDR) 의 물리적인 위치를 “순서”적으로 결정하는 특징

→ 배열의 순서는 메모리 공간에서 저장되는 “원소값의 물리적 순서”

배열의 의미

• 인덱스와 원소값(index, value) 의 쌍으로 구성된 집합

→ 원소들이 모두 같은 자료형과 같은 크기의 기억공간을 가짐

→ 배열의 인덱스 값을 이용해 원소 값에 접근하기 때문에 직접 접근이 가능

배열의 인덱스 값 : 추상화된 값 = 컴퓨터의 내부구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의 됨

→ 메모리 주소값은 실제 메모리의 물리적인 위치 값

• 배열의 (추상화된) 인덱스 값은 프로그래밍 언어와 컴파일 과정을 통해 메모리 주소 값과 연결 됨

배열의 추상 자료형

추상 자료형

• 객체 및 관련된 연산의 정의로 구성됨
• 자료구조 구현전의 설계 단계

자료형

• 메모리 저장 할당을 위한 변수 선언
• 자료구조의 구현단계 (프로그래밍 언어를 이용한 선언)

배열의 추상 자료형

• ADT Array 객체 : <i (index), e(element)> 쌍들의 집합

→ index : 순서를 나타내는 원소의 유한 집합

→ element : 자료형이 같은 원소의 집합

배열 연산의 구현

배열의 생성 (create 연산)

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

// a = [0,0,0,0,0]

→ 정수 n개를 저장 할 수 있는 배열 이 생김.

배열값의 검색 (retrieve 연산)

#define array_size 5

int retrieve(int *a, int i){ // i = 2
    if( i >= 0 && i < array_size)
                return a[i];
        else {
    printf("Error")
    return(-1);
            }
}

// a[2] 가 호출 됨

→ i번째 위치의 배열 값이 호출 됨.

배열값의 저장(store 연산)

#define array_size 5
void store(int *a, int i, int e) { // i = 3 , e = 35
    if( i >= 0 && i < array_size)
            a[i] = e;
    printf("Error")

}

// a[3] = 35 가 됨

→ i 번째 위치의 배열의 값이 e의 값으로 변경 됨

1차원 배열

1차원 배열의 정의

• a[i]는 배열의 첫 번째 원소 a[0]이 저장 된 메모리 주소인 a로 부터 시작하여 a[0] 부터 a[i-1] 개 까지 i개의 배열 a[] 를 지나서 저장 됨.
• a[]의 메모리 시작 주소를 a 라고 가정하면, a[i]의 메모리 저장 주소는 [a + i * k] 가 된다.

a[0] | a[1] | a[2] | a[3] | a[4]

a(L) | a(L+1) | a(L+2) | a(L+3) | a(U)

k. k.

배열의 확장

행렬의 배열 표현

→ 행렬을 컴퓨터에서 표현하기에는 2차원 배열이 적합함

출처) 자료구조 배열 강의

행렬의 2차원 배열 표현

출처) 자료구조 배열 강의

행 우선 배열

• 1차원 배열을 여러 개 쌓아 놓은 것이 2차원 배열

행우선 할당

• 가로의 1차원 배열 단위로 메모리 영역을 우선 할당함

열 우선 배열

• 1차원 배열을 여러개 세워 놓은 것이 2차원 배열

열우선 할당

• 세로의 1차원 배열 단위로 메모리 영역을 우선 할당함

희소 행렬의 표현

희소행렬

원소 값이 0 인 원소가 그러지 않은 원소보다 상대적으로 많음

출처) 자료구조 배열 강의

희소행렬의 효율적 배열 표현

• 0인 원소는 저장하지 않고 0이 아닌 값만 따로 모아 저장
• 메모리 낭비를 막고 효율성 향상