[자료구조] 2. 배열

KNOU/자료구조

[자료구조] 2. 배열

워터파슬리 2022. 11. 5. 19:38

728x90

01. 배열의 정의

✅ 배열

메모리 공간(메인 메모리, DDR)에 저장되는 원소의 물리적인 위치를 순차적으로 결정
- 배열의 순서 == 메모리 공간에 저장되는 원소값의 물리적 순서
원소들은 모두 같은 자료형과 같은 크기의 기억 공간을 가짐
인덱스와 원소값(<index, value>)의 쌍으로 구성된 집합

인덱스(index)
- 컴퓨터의 내부구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의됨(추상화된 값) → 불변
- 보통 배열의 인덱스는 0부터 시작
- 인덱스를 이용해서 원소값에 접근하기 때문에 직접 접근 가능
메모리 주소값은 실제 메모리의 물리적인 위치값(주소값)
- 실제로 연속된 메모리에 저장됨
- 주소값은 가변적임(시간이 지나거나 프로그램을 실행할 때마다 변경됨)

02. 배열의 추상 자료형

▪️ 추상자료형: 객체 및 관련된 연산의 정의
예를 들어 C언어의 printf() 처럼 C 컴파일러 개발자가 만들어 놓은 것을 다른 개발자들은 가져다 쓰기만 하면 되는...

▪️ 자료형: 메모리 저당 할당을 위한 선언
int, float, ...
'내가 프로그래밍에서 이 변수에 대해서 이러한 메모리 영역을 할당받고 싶어'라고 선언하는 것

🔸ADT Array 객체

< i∈Index, e∈Element > 쌍들의 집합
- Index: 순서를 나타내는 원소의 유한집합
- Element: 타입이 같은 원소의 집합

🔸연산

a∈Array;
i∈Index;
item∈Element;
n∈Integer;

a: 0개 이상의 원소를 갖는 배열
item: 배열에 저장되는 우너소
n: 배열의 최대 크기를 정의하는 정수값

03. 배열의 연산의 구현

※ 컴파일러 개발자의 역

▪️ 배열 생성

//① Array create(n) ::= 배열의 크기가 n인 빈 배열을 생성하고 배열을 반환;
void create(int *a, int n){	//n=5
	int i;
    for(i=0, i<n, i++){
    	a[i] = 0;
    }
}

▪️ 배열 생성 결과

▪️ 배열값 검색(retrieve 연산)

/*
	② Element retrieve(a, i) ::= if(i∈Index) then{ 
                                                    배열의 i번째에 해당하는 원소값 'e'를 반환; 
                                                 }else{  
                                                    에러 메세지 반환; 
                                                 }
*/
#define array_size5
int retrieve(int *a, int i){ //i=2
	if(i>=0 && i<array_size){
    	return a[i];
    }else{
    	printf(Error\n);
        retrun(-1);
    }
}

▪️ 배열값 검색 결과

▪️ 배열값 저장(store 연산)

/*
	③ Array store(a, i, e) ::= if(i∈Index) then{ 
    				배열 a의 i번째 위치에 원소값 'e'를 저장하고 배열 a 반환; 
        	}else{ 
                    인덱스 i가 배열 a의 크기를 벗어나면 에러메세지 반환; 
            }
*/
#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로 변경되어 저장된 모습