배열

학습목표

1. 배열의 추상 자료형을 이해한다.

2. 배열의 원소의 순서와 저장 위치에 대해서 이해한다.

3. 1차원 배열이 확장된 2차원 배열의 메인 메모리의 연속 할당을 이해한다.

4. 희소행렬의 구조와 장점을 이해한다.

 

 

1. 배열의 정의

- 일정한 차례나 간격에 따라 벌여 놓음 (사전적 정의)

- '차례'(순서)와 관련된 기본적인 자료구조

 

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

 

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

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

 

배열의 의미

- ‘호수’(인덱스)로 표현되는 순서를 갖는 ’아파트’(메모리 영역,원소값을 위한 저장소)

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

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

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

- 메모리 주소값은 실제 메모리의 물리적인 위치값(주소값)

- 인덱스와 주소값의 관계(보통 배열의 인덱스는 0부터 시작)

 

 

2. 배열 추상 자료형

추상자료형 : 객체 및 관련된 연산의 정의

 

자료형 : 메모리 저장 할당을 위한 선언

 

ADT Array 객체 : < i ∈ index, e ∈ Element > 쌍들의 집합

- Index : 순서를 나타내는 원소의 유한집합

- Element : 타입이 같은 원소의 집합

 

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

 

연산 :

a ∈ Array; i ∈ Index; item ∈ Element; n∈Integer 인 모든 a, item, n 에 대해여 다음과 같은 연산이 정의됨

- a : 0개 이상의 원소를 갖는 배열

- item : 배열에 저장되는 원소

- n : 배열의 최대 크기를 정의하는 정수값

① Array create(n) ::= 배열의 크기가 n인 빈 배열을 생성하고 배열을 반환한다;

② Element retrieve(a,i) ::= if (i ∈ Index)

     then { 배열의 i번째에 해당하는 원소값 ‘e’를 반환한다; }

     else { 에러 메시지를 반환한다; }

③ Array store(a,i,e) ::= if ( i ∈ Index )

    then { 배열 a의 i번째 위치에 원소값 ‘e’를 저장하고 배열 a를 반환한다; }

    else { 인덱스 i가 배열 a의 크기를 벗어나면 에러 메시지를 변환한다; }

 

 

3. 배열의 연산의 구현

배열의 생성

voidcreate(int *a,int n){	//n=5
	Int i;
	for(i=0,i<n,i++){
		a[i]=0; }
}

생성 결과

배열값의 검색(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\n”);
		return(-1); } 
}

배열값의 검색 결과

- 다음과 같은 원소값이 저장되어있다고 가정하며, ‘30’이 출력됨

 

배열값의 저장(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;
	else printf(“Error\n”); 
}

배열의 연산의 구현

- a[3]의 값이 35로 변경되어 저장된 모습