[Algorithm with C] 배열 Array (1)

배열

같은 자료형의 변수로 이루어진 element(요소)가 모여 직선 모양으로 줄지어 있는 자료구조이다

자료형 배열이름[요소개수];
int a[5];	// a는 요소의 자료형이 int형이고 요소 개수가 5개인 배열

요소 개수는 상수만 사용할 수 있음.

int a[5]; -> ( a[0],a[1],a[2],a[3],a[4] )

요소와 인덱스

배열의 개별 요소에 접근하기 위해 정수형 인덱스를 사용함. 첫 번째 배열 요소의 인덱스는 0부터 시작한다.

위와같이 배열 a는 int형이기 때문에 각각의 요소또한 int형이다.

 

배열의 요솟값 초기화 후 배열 선언 

배열에 각 요소에 넣을 값을 미리 알고잇으면 선언할때 초기화(initializer)할 수 있다.

#include <stdio.h>

int main(void) {
    int i;
    int a[5] = {1,2,3,4,5};
    int len_array = sizeof(a) / sizeof(a[5]);
    printf("배열 a의 요소는 모두 %d개\n",len_array);
    for(i=0;i<len_array;i++) {
        printf("a[%d] = %d\n",i,a[i]);
    }
    return 0;
}

 

배열의 요소 구하기 

배열을 선언한 후 해당 배열의 요소의 개수를 알고 싶다면 sizeof 연산자를 사용하여 구할 수 있다.

예시로 배열 a의 요소의 개수를 구하여면 sizeof(a) / sizeof(a[0]) 로 구해 변수에 대입하면 된다.

sizeof(a)로 전체 배열이 할당된 메모리 크기를 구하고 , sizeof(a[0])로 첫번째 요소가 할당된 메모리 크기를 구할 수 있다

만약 전체 배열 크기가 20바이트고 int 형이 4바이트니 20을 4로 나누면 5 , 즉 요소의 개수는 5개라는것을 알 수 있다.

 

메모리 할당 기간과 동적 객체 생성

앞서 언급했던 것 처럼 배열을 선언할때는 요소개수를 넣어야하는데 그럼 요소개수를 변수 n으로 넣고 사용자 입력값을 받아서 요소개수를 정할 수 있느냐하면 그건 불가능하다. 요소 개수는 오직 상수만 가능하기 때문. 그렇다면 필요할때 메모리 확보,불필요할때는 해제할 수 있는 배열은 어떻게 만드는가?

메모리를 확보하기 위해 사용하는 함수 calloc 과 malloc이 있다. 둘다 헤더 파일은 <stdlib.n> , 자세한 설명을 보자면 

	calloc	malloc
형식	void *calloc(size_t nmemb,size_t size);	void *malloc(size_t size);
해설	크기가 size인 자료가 nmemb개만큼 들어갈 메모리 할당. 할당된 메모리 영역은 모든 비트가 0으로 초기화	크기가 size인 메모리 할당, 할당된 메모리의 값은 정의되지 않음
return value	메모리 할당에 성공하면 할당된 영역의 첫 번째 포인터 반환, 실패하면 NULL 포인터 반환	메모리 할당에 성공하면 할당된 영역의 첫 번째 포인터 반환, 실패하면 NULL 포인터 반환

 

C 언어 메모리 구조 

Data - Stack - Heap 

Data영역은 전역 변수와 Static 변수가 할당되는 영역. 프로그램을 시작하면 할당 , 종료하면 해제함

Stack 영역은 함수 호출 시 생성되는 지역 변수,매개변수가 저장되는 영역. 함수 호출이 끝나면 사라짐

Heap 영역은 필요에 따라 동적으로 메모리 할당. 메모리 크기를 runtime때 결정해야 하면 사용함\

 

calloc,malloc으로 메모리 공간을 확보후 사용하다 더이상 필요없으면 해당 공간을 해제해야함.

이때 free함수를 사용해서 해제 가능

free
형식	void free(void *ptr);
해설	ptr이 가리키는 메모리를 해제, 이후 다시 할당할 수 있도록 함  ptr이 NULL 포인터면 아무것도 안함. ptr로 전달된 actual argument가 calloc,malloc,realloc에 의해 반환된 포인터가 아니거나 영역이 free,realloc를 호출해 이미 해제된 영역이여도 아무것도 안함
return value	없음

free 함수를 통해 프로그램을 실행하는 도중 변수를 생성하거나 제거 가능.

 

예시로 int형 변수를 calloc으로 생성하여 정수 값 대입, 출력후 free로 해제해보겠다.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int *x;
    x = calloc(1,sizeof(int));  // int형 포인터에 메모리 할당
    if (x == NULL) {
        puts("false");          // 할당 실패시 false 출력
    } else {
        *x = 57;                // 포인터로 변수 x에 57대입 
        printf("*x=%d\n",*x);
        free(x);                // 메모리 해제
    }
    return 0;
}

포인터 x가 가리키는 메모리 주소의 값은 간접 연산자 *를 사용한 *x를 사용하여 접근할 수 있다.

포인터 x가 확보한 메모리 영역을 자리키고 있으니 확보한 메모리 영역은 *x로 접근 가능하다.

따라서 *x에 값을 대입하고 그 값을 꺼내 출력한 후 free로 메모리를 해제시켜주는 코드다.

 

배열의 동적 생성

단일 int 객체 생성	calloc(1,sizeof(int));
요소 개수 n , 자료형 int인 배열	calloc(n,sizeof(int));

 

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int i;
    int *p;     //배열의 첫 반쩨 요소의 포인터
    int n;      //요소 개수 
    scanf("%d",&n);
    p = calloc(n,sizeof(int));  //요소의 개수가 n개인 배열 생성

    if(p == NULL) {
        puts("false");
    } else {
        for(i=0;i<n;i++) {
            printf("p[%d] :",i);
            scanf("%d",&p[i]);
        }
    }
    for(i=0;i<n;i++) {
        printf("p[%d] = %d\n",i,p[i]);
    }
    free(p);        // 배열 해제
    return 0;
}

void 포인터 

특정 자료형의 포인터를 주고 받을때 자료형이 서로 맞지 않으면 문제가 발생하므로 모든 형의 객체를 가리킬 수 있는 void포인터를 반환하거나 받는데 사용한다. void형의 값은 모든 자료형의 포인터에 대입 가능

포인터와 배열

포인터로 배열의 요소를 가리켜 접근할 수도 있다.  예시로 포인터 변수 p와 배열 a[5]를 선언해서 보자면

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int *p;
    int a[5] = {1,2,3,4,5};
    p = &a;
    for(int i=0;i<5;i++) {
        printf("a[%d] = %d\n",i,*(p+i));
    }
    return 0;
}

*(p+i)를 사용해 배열 a[i]에 접근할 수 있다 예시에서 i는 (0<=i<=4). 이를 응용하면 a[0]에서 a[2]에 있는 요소를 가리키고 싶다면 p + 3 , *(p+3)으로 표현할 수 있다. 반대로 *(p-i)를 사용해 p[-i]로 표기 가능.

각 요소의 포인터를 나타내는 식				메모리 (p)	각 요소에 접근하는 식
&a[0]	a+0	&p[0]	p+0	a[0]	*(a+0)	p[0]	*(p+0)
&a[1]	a+1	&p[0]	p+1	a[1]	*(a+1)	p[1]	*(p+1)
&a[i]	a+i	&p[i]	p+i	a[i]	*(a+i)	p[i]	*(p+i)

공백 포인터와 NULL

null pointer는 객체 포인터,함수 포인터와 다른 포인터다. 정수 값 0은 모든 포인터형으로 형 변환이 가능하고 그 결과가 NULL 포인터다. 공백 포인터를 나타내는 것이 공백 포인터 상수(null pointer constant)라고 하는 매크로 NULL이다.

매크로 NULL은 <stddef.h>,<locale.h>,<stdio.h>,<stdlib.h>,<time.h> 헤더에 정의 되어있음

여기서 NULL의 정의는 값 0을 갖는 모든 정수,상수 또는 상수식을 void*로 형 변환한 식이다

NULL을 정의한 예시는 다음과 같다

#define NULL 0
#define NULL(void*)0	// C++ 사용 X

배열 요소의 최댓값 구하기

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int a[6] = {50,24,30,64,13,12};
    int max = 0;
    for (int i=0; i<6;i++) {
        if(a[i] > max) max = a[i]; 
    }
    printf("max = %d",max);
    return 0; 
}

간단하게 6개의 무작위 값을 배열에 넣고 for문과 if을 사용해 배열 내부에 최댓값을 구하는 코드이다.

for문으로 i=0부터 5까지 증가시키면서 배열 a에 있는 요소들을 탐색한다. max의 초기값은 0으로 만약 a[0]이 

0보다 크다면 최댓값은 a[0]이된다 (a[0]값이 max 변수에 대입된다) 이후 a[1]이 max(a[0])보다 크지 않다면 max는 유지된다. 이런식으로 반복해서 배열의 끝까지 탐색하여 최댓값을 구한다.

 

배열의 요소를 역순으로 정렬 

0 (index)	1	2	3	4	5	6
70 (value)	34	14	52	65	91	22

 

순서를 바꾸기 위해서는 배열 a가 있을때 a[0]와 a[6]을 교환하고 a[1]과 a[5]....최종적으로 a[3]빼고는 모두 교환해준다

(요소의 개수가 홀수이면 중앙값을 바꿀 필요가 없다). 교환 횟수는 요소개수(n)/2다

 

두개의 값을 교환하기 위해서는 하나의 값을 저장하기 위한 변수가 필요하다 이를 t라고 정의하면 교환 과정은

x,y 두 값이 있을때 x 값을 t에 보관 후 y 값을 x에 대입한다. 이후 t에 저장한 x값을 y에 대입해준다.

 

역순으로 정렬할때는 a[i]와 a[n-i-1]값을 교환.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int i;
    int a[6] = {34,14,52,65,91,22};
    for(i=0;i<6/2;i++) {
        int t = a[i];
        a[i] = a[6-i-1];
        a[6-i-1] = t;
    }
    for(i=0;i<6;i++) {
        printf("%d ",a[i]);	//22 91 65 52 14 34
    } 
    return 0;
}

 

역순을 구하는 프로그램을 작성해보면

#include <stdio.h>
#include <stdlib.h>

#define swap(type,x,y) do {type t = x;x=y;y=t;} while(0)

void array_reverse(int a[],int n) {
    int i;
    for(int i=0;i<n/2;i++){
        swap(int,a[i],a[n-i-1]);
    }
}
int main(void) {
    int i;
    int *x;
    int n;

    printf("요소 개수 :");
    scanf("%d",&n);
    x = calloc(n,sizeof(int));
    for(i<0;i<n;i++) {
        printf("x[%d] :",i);
        scanf("%d",&x[i]);
    }
    array_reverse(x,n);
    for(i=0;i<n;i++) {
        printf("x[%d] = %d\n",i,x[i]);
    }
    free(x);
    return 0;

}