[DataStructure]배열

📚배열의 정의

배열은 인덱스와 원소 값의 쌍으로 구성된 집합으로 정의된 각 인덱스는 그 인덱스와 관련된 값을 가진다.

배열은 원소들이 모두 같은 자료형의 값과 같은 크기의 기억 공간을 갖는다는 특징이 있다. 또한 각 원소의 물리적인 위치 순서(메모리 주소)가 배열의 논리적인 순서(추상화된 인덱스의 순서)와 일치한다.

따라서 배열의 첫 번째 원소가 위치하는 메모리 주소를 알면 임의의 배열 원소의 주소값을 계산할 수 있다. 인덱스 값을 알고 있으면 접근하려고 하는 배열의 원소가 저장된 순서에 따라 접근하지 않고 인덱스 값으로 직접 접근할 수 있다.

인덱스 값이 정수라도 메모리 주소값은 16진수이면서 프로그램이 실행되어야 결정되기 때문에 배열 원소에 직접 접근하는 것이 간단한 것은 아니다. 운영체제는 접근하려는 원소의 인덱스를 이용하여 실제 메모리 주소를 계산한다. 이런 특징 때문에 배열은 추상화된 의미와 구체화된 의미가 같은 자료구조라고 말할 수 있다.

📚배열의 추상 자료형

배열은 인덱스와 값의 쌍으로 이루어져 있다. 인덱스는 순서를 나타내느 원소의 유한 집합을 의미한다. 배열의 크기는 배열을 생성할 때 사용자가 정하기 때문에 배열의 인덱스 범위가 정해진다.

그리고 배열에 저장되는 값들은 같은 자료형이다. 정수형 배열을 만들 경우 배열에 저장된 값들은 모두 정수형이 되어야 한다.

추상 자료형은 저장 개체와 개체에 대한 적용 가능 연산을 함께 저장하고, 개체와 연산을 통해 프로그래머의 의도를 반영하는 자료구조를 표현하는 방법이다.(개체 정의와 연산자로 구성)

ADT Array

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

• 연산: a ∈ Array; i ∈ Index; x, item ∈ Element; n ∈ Integer인 모든 a, item, n에 대해 다음과 같은 연산 정의.(a는 0개 이상의 원소를 갖는 배열, item은 배열에 저장되는 원소, n은 배열의 최대 크기를 정의하는 정수값)

1. Array create(n) ::== 배열의 크기가 n인 빈 배열을 생성하고 공백 배열을 반환;
2. Element retrieve(a, i) ::== if(i ∈ Index)
   　　then { 배열의 i 번째에 해당하는 원소 값 e를 반환; }
   　　else { 에러 메시지 반환; }
3. Array store(a, i, e) ::== if(i ∈ Index)
   　　then { 배열 a의 i 번째 위치에 원소값 e를 저장하고 배열 a를 반환; }
   　　else { 인덱스 i가 배열 a의 크기를 벗어나면 에러 메시지 반환; }

📚배열의 연산 구현

📄배열을 공백 배열로 생성하는 연산

배열의 크기를 n으로 하고 n개의 원소를 0으로 초기화한다.

void Create(int size)
{
  int array[size];

  for(int i = 0; i < size; ++i)
  {
    a[i] = 0;
  }
}

📄배열의 원소값을 검색하는 연산

검색 연산은 배열에서 i번째 인덱스에 저장된 원소값을 반환한다.

배열의 인덱스는 0부터 시작이므로 찾고자 하는 인덱스의 범위가 0 부터 배열 크기 보다 하나 작은 수라면 검색이 가능하다. 따라서 배열에서 i번째 인덱스의 원소값을 반환한다.

만약 i가 위 유효 범위를 벗어났다면 Error 메시지를 출력하고 -1을 반환하고 검색을 종료한다.

#define ARRAY_SIZE 5

int Retrieve(int* array, int i)
{
  if(i >= 0 && i < ARRAY_SIZE)
  {
    return array[i];
  }
  else
  {
    printf("Error\n");

    return -1;
  }
}

📄배열에 원소값을 저장하는 연산

저장 연산은 i 번째 인덱스에 e 원소값을 저장하는 연산이다.

저장하고자 하는 인덱스 i의 범위가 0 부터 배열 크기 보다 하나 작은 수라면 i 번째 인덱스에 원소 e를 저장한다.

만약 i가 배열의 유효 범위를 벗어났다면 Error 메시지를 출력한다.

#define ARRAY_SIZE 5

void Store(int* a, int i, int e)
{
  if(i >= 0 && i < ARRAY_SIZE)
  {
    a[i] = e;
  }
  else
  {
    printf("Error\n");
  }
}