배열의 자료구조

배열의 정의

배열은 일정한 차례나 간격에 따라 벌여 놓은 것을 말하고, 아파트 호수와 같이 호수(인덱스) 순으로 표현되는 아파트(메모리영역)라고 생각해 볼 수 있다. 즉 물리적 순서를 자료의 구조로 표현했다고 생각하면 되겠다. 배열은 인덱스와 원소값의 쌍으로 구성된 집합으로 특성으로는 원소들이 모두 같은 자료형의 값과 같은 크기의 기억공간을 갖는다는 것이다.

• 일정한 차례나 간격에 따라 벌여 놓음
• 차례(순서)와 관련된 기본적인 자료구죠
• 원소의 메모리 공간의 물리적 위치를 순서적으로 결정하는 특징

 

또한 각 원소의 물리적인 위치(실제 물리적 위치)의 순서가 배열의 논리적인 순서(추상화된 인덱스 순서)와 일치한다. 즉, 실제 물리적 위치는 개발자나 사람이 알기에는 어려운 실제주소를 뜻하고 논리적인 순서는 개발자가 알아보기 편하게 추상화된 첫 번째 배열 두 번째 배열 위치라고 생각할 수 있는데 운영체제는 개발자의 추상화된 값과 컴퓨터의 물리적인 값을 연결시켜 준다. 그리고 프로그래밍언어는 개발자와 운영체제 간의 의사소통을 위한 도구라고 생각할 수 있다.

배열의 추상 자료형

지하철 노선도처럼 배열을 추성화하는것이다.

배열 추상 자료형(ADT)의 연산 부분을 살펴보자. a는 배열의 이름, i는 인덱스, e는 원소값, n은 배열의 크기를 정의하는 정수 값이다.

 

배열 연산의 정의

배열의 객체 : i는 인덱스, e는 원소값 쌍들의 집합이고 인덱스는 순서를 나타내는 정수 값이고 원소값은 같은 자료형의 원소값.
배열은 0개 이상의 원소를 갖는 배열이고 원소값은 배열에 저장되는 원소 배열을 최댓값을 저장하는 것이 n


create(n)은 n개의 원소를 저장할 수 있는 공백 배열을 생성합니다. 배열을 생성할 때 n개의 원소들을 저장할 수 있는 공간은 만들어지지만 그 안에 채워진 원소값은 아직은 없다는 것을 의미한다.

연산 retrieve(a, i)는 배열 a와 인댁스 i를 매개 변수로 전달받아 인덱스 i위치에 대응되는 원소 값 e가 있다면 원소값 e를 반환하고 그렇지 않은 경우 에러 메시지를 반환한다.

연산 stroe(a, i, e)는 배열 a와 인덱스 i, 원소값 e를 매개 변수로 전달받아 인덱스를 검사하여 i 값이 유효할 경우 쌍이 되게 원소값을 i번째 인덱스에 저장하고 배열 a를 반환합니다.

배열의 연산의 구현

배열 추상 자료형의 연산을 간략히 요약하면, 배열을 공백 배열로 생성하는 연산, i번쨰 인덱스에 저장되어 있는 원소값을 반환하는 연산, 배열에서 원하는 위치 i번째 인덱스에 e원소값을 저장하는 연산으로 이루어져 있다.

 

	a[0]	a[1]	a[2]	a[3]	a[4]
a	10	20	30	40 35로 바낌	50

위와 같은 배열이 있다고 가정해 보자
#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 print("Error\n");
}

1. 우선 인덱스 범위를 #define 함수로 정의하고, 인덱스 i의 값이 유효 집합 안에 포함되어 있는지 확인
2. 연산 store를 쓰는 거 같네요. 배열을 가리키는 변수 a와 원소 e를 저장할 위치를 가리키는 i 배열에 저장할 원소값 e를 매개 변수로 전달을 받는다. i=3 , e는 35
3. 위치를 가리키는 i의 값이 유효집합 범위에 해당되는지 알아야 하는데 배열사이즈 5보다 작고 0보다는 커야 하고 배열 인덱스는 0부터 시작하므로 배열 사이즈보다 1 작은 값이 최댓값을 가진다.
4. 해당 코드에서는 i값이 3이고 조건문은 참이 되어 배열 a의 인덱스 i번째 값인 a [3] 위치에 35를 저장한다.

아! 결국에 우리가 실제로 int A [3]을 입력하는 것은 컴파일러가 위의 내용같이  함수를 불러와 배열을 생성한다는 것이다. 그것이 creat(int n)이고, K=a [2]를 입력한다는 것은 3번째 배열에 있는 값을 K값에 할당한다는 것으로 우리는 입력하지만 컴파일을 retrieve(int *a, int i) 함수를 불러와서 한다는 것을 가르치려는 게 목적이었음. 그리고 위예시에 store예시는 배열값을 바꾸는 것의 컴파일러가 함수를 가져오는 과정을 말하는 것

1차원배열

한 줄짜리 배열을 의미하고 인덱스는 하나입니다. 메모리 영역도 한 줄로 할당을 받게 됩니다. 이러한 배열에 물리적인 주소를 구하는 방법은 다음과 같다.

A [0]의 메모리 시작주소를 A [L]이라고 한다면 각 자료형의 크기 K를 알면 간단한 계산에 의해서 A [i]의 주소를 알 수 있다.

A [0]의 주소를 A [L]로 표현하면 A[4]의 주소는 A[L+3]으로 표현된다. A[i]는 A[0]부터 시작해 i번째 원소이고 따라서 A[i]는 배열 첫번째 원소 A[0]이 저장된 주소인 a부터 시작해서 A[0]부터 A[i-1]까지 i개의 배열 A[  ]를 지나서 저장될꺼다. A[  ]의 크기를 k라고 가정하면 (이거는 배열 하나당 뭐 4비트이거나 8비트 이거 나를 말하는 거 같다) 
A [i]의 저장 주소는 a + i * k가 된다.

배열의 확장

1차원 배열의 확장은 2차원배열입니다. 이러한 배열을 공부하는 이유는 결과적으로 배열의 특징 중 하나인 직접 접근을 활용할 수 있기 때문이다. 2차원 배열의 행우선 저장방식은 행이 모두 연속적으로 메모리 영역 할당을 받고, 그다음 행이 메모리 영역을 연속적으로 할당방는 방식이고 열 우선 저장방식은 열이 모두 연속적으로 할당을 받고 다음열이 메모리 영역을 연속적으로 할당받는 방식을 말한다. 이는 코볼, 파스칼, C 같은 언어는 행우선이고, 포트란은 열 우선을 이용하며 트로그래밍 언어에 따라 결정된다.

희소행렬의 개념

2차원 배열은 논리적으로 바둑판 형태를 띠기에 행렬을 표현하기에 적합하다. 행렬을 표현하다 보면 우너소값이 인 원소가 그렇지 않은 원소보다 상대적으로 많은데 이와 같은 행렬을 희소행려링라고 하나도. 이럴 때 불필요한 메모리의 효율성을 높이기 위해 값이 0인 원소는 저장하지 않고 0이 아닌 값만 따로 모아서  저장하는 방법이다.