모듈1. 배열 개요
1) 데이터의 표현
(1) 고급 표현 특징
- 추상적이고 논리적인 표현
- 추후 저급의 데이터와 연산자로 구현해야 실행될 수 있음
- 연산자의 구현은 데이터의 저급 표현 방법에 의존
(2) 저급 표현 방법
- 순차 표현(sequential representation) = 배열(array)
- 연결 표현(linked representation) = 연결 리스트(linked list)
2) 배열이란?
모듈2. 배열 추상 데이터 타입
1) 배열과 인덱스
(1) 배열의 정의: 주어진 각 index에 대해 하나의 value가 연관된 <index, value> 쌍들의 집합을 "배열(array)"이라고 한다. (포인터에는 주소만!)
(2) 인덱스(index) = 메모리 안 주소
- 순서를 나타내는 원소의 유한 집합
- 집합 내에서의 상대적 위치 식별
- 원소 수가 한정되어 있고, 항상 마지막 원소가 존재
- 인덱스만으로 원하는 원소를 직접 접근
(3) 배열(array)의 특성
- 순차적 메모리 할당 방식
- <인덱스, 원소 값> 쌍의 집합
- 상기 각 쌍은, 인덱스와 그에 대응되는 원소 값(value or item)을 가지므로, 이를 대응 관계라 함
- 이러한 대응 관계를 correspondence 또는 mapping이라는 용어를 사용함 - 원소들이 모두 같은 타입, 즉 같은 크기를 가짐(eg: int, 4byte)
2) 배열 추상 데이터 타입
(1) 주요 연산자
- create(): n개의 원소 값을 저장할 수 있는 공백 배열을 생성
- retrieve(): Array와 Index를 매개변수로 받아 Index에 대응하는 원소값을 찾아 반환하고 없으면 error를 반환
- store(): Array, Index, Element를 매개 변수로 전달 받아 유효하면 <인덱스, 원소값> 쌍으로 저장하고 Array를 반환
(2) 배열 ADT 정의
- 설명에 포함되어야 하는 "데이터 & 연산들"을 명확하게 정의
- 꼭 필요한 사항만 요약해서 표현
모듈3. 배열의 표현
1) 1차원 배열
(1) 메모리 표현(memory representation)
- 연속적인 메모리 주소를 배열에 할당
- 순차사상(sequential mapping): 배열의 논리적 순서와 메모리의 물리적 순서가 같도록 표현
- 순차표현(sequential representation): 순차 사상을 이용하여 데이터를 표현(=저장), 원소는 할당된 메모리 내에서 인덱스 순서에 따라 저장
- 1차원 배열의 순차 표현
-> a[0]의 기준 주소가 x이고, 각 원소가 1 byte이면 a[i]의 주소는 x + 1 * i
-> a[0]의 기준 주소가 x이고, 각 원소가 c byte이면 a[i]의 주소는 x + c * i
(2) C언어에서의 1차원 배열 예
- 정수형(int)은 4byte의 메모리가 할당되고, 문자형(char)은 1byte가 할당됨
- int list[5] : array list는 "정수 변수(int)"를 5개만큼 연속 정의함
- int *plist[5] : "정수 변수의 주소"를 담고 있는 pointer 변수 (int *)를 5개 정의함
2) 2차원 배열
(1) 2차원 배열을 1차원 메모리로 사상
- 행 우선 순서(row major order): 일반적인 방법
- 원소를 차례로 접근 시, 항상 행보다 열(column)을 나타내는 인덱스가 먼저 변함 - 열 우선 순서(column major order): transform 하고 계산
3) 3차원 배열
4) n차원 배열
- Row major order 사용
eg) A[3][4][5]에서 A[2][1][3]의 주소는? a(시작지점) + 4*5*2 + 5*1 + 3
