[자료구조 3장] - 배열과 구조체(1)

배열과 구조체(1)

 

배열

배열 : 각 원소의 위치 정보를 나타내는 인덱스와 데이터 값의 쌍으로 이루어지는 같은 자료형을 갖는 데이터들의 집합

 

학습할 개념

- 배열의 접근과 주소계산

- 배열의 연산 : 삽입, 삭제, 검색

- 배열 응용 프로그램 : 1차원, 다차원 배열

- 마방진 알고리즘 구현

 

배열의 접근과 주소계산

배열이 가지는 3가지 정보

1. 배열 항목의 자료형

2. 배열의 이름

3. 배열의 크기(한목의 개수)

ex) int a[10]

 

배열은 인덱스를 두 개 이상 사용할 수 있다 -> 인덱스 수에 따라 차원(dimension)이 정해짐

ex) a[10] : 1차원 배열, b[10][5] : 2차원 배열

 

배열의 크기는 차원 범위의 곱

ex) a[3][11][6] : 3차원 배열, 3 * 11 * 6 = 198

 

주소계산

2차원 이상의 다차원 배열에는 행 우선 순서, 열 우선 순서가 있다.

- 행 우선 순서(row major order)

첫째 행에 있는 원소 모두 먼저 저장, 순서에 의하여 기억, 한 행 내에서는 열의 순서대로 기억시킴

 

- 열 우선 순서(column major order)

첫째 열에 있는 원소 모두 먼저 저장, 순서에 의하여 기억, 한 열 내에서는 행의 순서대로 기억시킴

 

5 * 3(d1 * d2) 이차원 배열(b[i][j] = b[4][2])에서 행 우선과 열 우선 방식의 계산을 살펴보자, b[0][0] 주소 : 100, sizeof(int) : 4

행 우선 일 때 b[1][2]의 주소 : 100(시작 주소) + (1(i) * 3(d2) + 2(j)) * 4(sizeof) = 120

열 우선 일 때 b[1][2]의 주소 : 100(시작 주소) + (1(i) + 2(j) * 5(d1)) * 4(sizeof) = 144

 

- 배열의 이름은 배열의 첫 데이터로서 포인터 타입의 변수이다.

- C프로그래밍에서는 배열을 함수의 매개변수로 넘겨줄 때 배열의 이름을 전달한다.

 

배열의 연산

배열의 데이터는 배열의 인덱스에 의해 값을 넣어줄 수 있고 접근할 수 있다.

 

배열의 데이터 저장과 접근

void main()
{
    int exarray[100], k;
    
    printf("Input 10 test data: ");
    for(k = 0 k < 10; k++)
    	scanf("%d", &exarray[k]);
    for(k = 9 k >= 0; k--)
    	printf("%d", exarray[k]);
}

 

(1) 첫 for문으로 배열의 0 ~ 9 인덱스 주소에 입력데이터를 저장

(2) 두번째 for문으로 배열의 9번째 인덱스 부터 0번째까지의 데이터를 출력

 

데이터 삽입

이미 배열에 데이터가 있을 때, 데이터를 특정 인덱스에 삽입하는 방법, 인덱스 k에 데이터 삽입

i = 9;
while (i >= k) {
    exarray[i+1] = exarray[i];
    i--;
}

배열의 끝에서 k까지의 인덱스를 가지는 데이터들을 뒤로 밀어서 exarray의 공간을 늘려 확보한 다음, exarray[k]에 삽입한다.

 

데이터 삭제

i = k;
while (i < n) {
    exarray[i] = exarray[i+1];
    i++;
}

반대로 k번째 데이터를 삭제하는 방법이다.

이번에는 배열의 끝에서 k까지의 인덱스를 가지는 데이터들을 앞으로 당겨서 k인덱스 위치에 있는 데이터를 덮어쓴다.

 

데이터 검색

n명의 합격자 수험번호를 가지고 있는 배열 passdb에서 어떤 수험번호의 지원자가 합격했는지 탐색하는 함수

int pass_search(long passdb[], int n, long sid)
{
    int i;
    for(i = 0; i < n; i++)
    	if(passdb[i] = sid) return 1;
    return 0;
}

 

위 과정을 통해 배열안의 데이터 접근은 인덱스에 의하여 상수시간 O(1)에 의해 수행되고, 삽입, 삭제, 검색은 배열 안의 데이터의 수 n에 의해 좌우되는 O(n)임을 알 수 있다.