Dynamic Array
자료구조 강의 때 가장 먼저 배웠던 동적 배열.
기존의 정적으로 할당 받는 방식의 배열은 정해진 인덱스를 초과하면 더 이상 값을 저장할 수 없다.
하지만 동적으로 할당 받는 Dynamic Array는 할당 받은 메모리를 초과하면 INCREMENT_SIZE 만큼의 메모리를 재할당 받아 저장이 가능하게 한다.
Dynamic Array는 앞으로 스택, 큐 등의 자료 구조를 만들 때 유용하게 쓰일 예정이다.
Dynamic Array는 두 개의 헤더 파일과 main.c를 포함한 C파일 두 개, 총 네 개의 파일을 갖는다.
DataType.h
#pragma once
#define TRUE 1
#define FALSE 0C++언어를 배우기 전에는 C언어에 boolean이 없는 것이 딱히 불편하지 않았는데, 배우고 나니까 0과 0이 아닌 것으로 boolean을 나타내는 것보다 확실히 의미가 눈에 잘 들어와서 매크로 상수로 선언해줬다.
typedef struct Element { // 배열 요소의 자료형 정의
int age;
char* name;
} Element;Element라는 구조체를 선언했다.
Dynamic Array에 저장되는 요소를 의미한다. 간단하게 이름과 나이로 조합해봤다.
DynamicArray.h
#include "DataType.h"
typedef struct DynamicArray {
Element** arr; // 포인터 배열의 주소 저장
int index; // 현재 인덱스 저장
int size; // 배열의 크기 저장
} DynamicArray;Dynamic Array를 실제로 정의하는 부분이다.
구조체 Dynamic Array는 데이터를 저장할 배열 arr과 현재 인덱스 index, 그리고 할당 받은 배열의 크기인 size로 구성되어 있다.
배열 arr은 Element의 이중 포인터형으로 선언되어 있다. 즉, Element의 값을 배열에 직접 저장하는게 아니라 Element의 주소 값만 저장하여 효율성을 높였다.
이어지는 아래 코드는 Dynamic Array의 추상 자료형(Abstract Data Type)이다.
DynamicArray* createDA(); // DynamicArray 생성
int DAAdd(DynamicArray* darr, Element* e); // DynamicArray의 마지막 자리에 요소 추가
int DAPut(DynamicArray* darr, int idx, Element* e); // DynamicArray의 idx 인덱스 위치에 요소 추가
Element* DAGet(DynamicArray* darr, int idx); // DynamicArray의 idx 인덱스 위치에 해당하는 요소의 주소 반환
void DAPrint(const DynamicArray* darr); // DynamicArray의 전체 요소 출력
void DADestroy(DynamicArray* darr); // DynamicArray 동적 할당 해제헤더 파일에는 함수의 프로토타입만 선언되어 있다.
크게 언급할 바는 없지만, 주목할만한 것은 데이터를 추가하는 함수가 DAAdd와 DAPut 함수로 두 가지인 것 정도이다. 하나는 배열의 가장 끝 자리에 데이터를 추가하는 것이고, 다른 하나는 index를 매개 변수로 전달받아 정확히 그 위치에 저장하는 함수이다.
DynamicArray.c
DynamicArray.c는 실제로 함수가 정의되는 소스 파일이다.
INCREMENT_SIZE
#define INCREMENT_SIZE 10 // 배열의 공간이 부족할 때 이 크기만큼 재할당 받습니다.
#include "DynamicArray.h"
#include <stdlib.h>
#include <stdio.h>본 포스팅의 초반에 설명했듯, 동적 배열은 할당 받은 메모리가 부족할 때마다 메모리를 추가로 재할당받는 자료 구조이다. INCREMENT_SIZE는 이 추가로 재할받 받을 메모리를 의미한다.
만약 구조체 ELement를 직접 저장하는 배열이라면 한 번 재할당 받을 때마다,
sizeof(Element) * INCREMENT_SIZE = 8 bytes * 10 = 80 bytes만큼의 메모리를 추가로 요구할 것이다.
하지만 Element를 직접 저장하는 배열이 아니라 그것의 주소값만을 저장하는 배열이기 때문에 추가로 요구하는 메모리는 아래와 같다.
sizeof(Element*) * INCREMENT_SIZE = 4 bytes * 10 = 40 bytes이러한 차이는 Element의 size가 커질수록 증가할 것이다.
DACheck(DynamicArray* darr)
본론으로 돌아와 이제 함수가 실제로 정의되는 영역을 살펴보자.
// DynamicArray에 요소를 추가할 때 빈 공간이 존재하지 않으면 메모리를 재할당 받는 함수
int DACheck(DynamicArray* darr)
{
if (darr->size <= darr->index + 1) {
Element** tmp = (Element**)realloc(darr->arr, sizeof(Element*) * (darr->size + INCREMENT_SIZE));
if (tmp != NULL) {
darr->arr = tmp;
darr->size += INCREMENT_SIZE;
}
else return FALSE;
}
return TRUE;
}이 함수는 헤더 파일의 ADT에는 존재하지 않는다. Java나 C++의 private 메소드처럼 내부적으로만 사용되게끔 정의한 함수이다.
용도는 메모리가 부족할 때 동적으로 재할당받는 함수이며, Dynamic Array의 핵심적인 부분이다.
곧바로 재할당받는 것이 아니라, tmp라는 변수에 재할당을 받아보고 그 후에 tmp가 NULL값을 가리키지 않고 정상적으로 재할당 받았다면 그제서야 이 주소를 DynamicArray의 배열에 저장한다.
그 이유는 메모리 누수(Memory Leak)를 방지하기 위함이다.
만약 메모리 공간이 충분하다면 아무런 문제가 발생하지 않지만, 부족하다면 realloc 함수는 NULL 값을 반환한다.
그런데 이 때 realloc 함수의 반환 값을 Dynamic Array의 배열 arr에 바로 저장하는 코드를 짰다면 arr에 NULL값이 저장되면서 더이상 arr이 가리키던 기존의 배열의 주소를 잃게 된다. 메모리 누수이다.
따라서 이런 일을 방지하기 위해 우선 tmp라는 변수에 realloc 함수의 반환 값을 받아서, 문제가 없는지 확인한 후에 tmp의 재할당 받은 주소값을 arr로 전달하는 것이다.
DynamicArray* createDA()
DynamicArray를 할당 받는 함수이다. 클래스로 따지면 생성자(Constructor)정도 되겠다.
DynamicArray* createDA()
{
DynamicArray* darr = (DynamicArray*)malloc(sizeof(DynamicArray));
if (darr != NULL) {
darr->index = -1;
darr->size = 0;
darr->arr = (Element**)malloc(sizeof(Element*) * INCREMENT_SIZE);
if (darr->arr != NULL) {
darr->size += INCREMENT_SIZE;
return darr;
}
else
free(darr);
}
return NULL;
}DynamicArray의 변수 index는 초기에 -1을 갖는다. 이것은 현재 가리키는 요소의 인덱스가 -1 즉, 아무것도 없다는 뜻이다.
int DAAdd(DynamicArray darr, Element e)
동적 배열의 마지막에 요소 e를 추가하는 함수이다.
int DAAdd(DynamicArray* darr, Element* e)
{
if (DACheck(darr)) {
darr->arr[++darr->index] = e;
return TRUE;
}
return FALSE;
}앞서 언급한 DACheck 함수를 호출하여 메모리가 부족하다면 재할당 받는다.
이후에는 그냥 데이터를 추가하고, 성공 여부에 따라 TRUE와 FALSE 값을 반환한다.
int DAPut(DynamicArray darr, int idx, Element e)
동적 배열의 특정 위치에 요소 e를 추가하는 함수이다.
int DAPut(DynamicArray* darr, int idx, Element* e)
{
if (DACheck(darr)) {
darr->index++;
for (int i = idx + 1; i <= darr->index; i++)
darr->arr[i] = darr->arr[i - 1];
darr->arr[idx] = e;
return TRUE;
}
return FALSE;
}Element* DAGet(DynamicArray* darr, int idx)
DynamicArray에서 특정 위치의 값을 반환하는 함수이다.
Element* DAGet(DynamicArray* darr, int idx)
{
if (darr->index >= 0 && darr->index >= idx)
return darr->arr[idx];
else return NULL;
}반환 성공 시에 요소의 주소값을 반환하고, 실패 시에 NULL 값을 반환한다.
void DAPrint(const DynamicArray* darr)
DynamicArray의 요소를 모두 출력하는 함수이다.
void DAPrint(const DynamicArray* darr)
{
for (int i = 0; i <= darr->index; i++)
printf("Name: %s\tAge: %d\n", darr->arr[i]->name, darr->arr[i]->age);
}void DADestroy(DynamicArray* darr)
동적 할당 받은 DynamicArray와 그 안의 Element*의 배열을 해제하는 함수이다.
void DADestroy(DynamicArray* darr)
{
if (darr != NULL) {
free(darr->arr);
free(darr);
}
}main.c
코드에 대한 간단한 설명
이제 지금까지 만든 Dynamic Array를 테스트하기 위한 main 함수를 만들 시간이다.
#include <stdio.h>
#include "DynamicArray.h"
#include "vld.h"DynamicArray의 헤더 파일을 include 해준다.
추가로 include 해준 "vld.h"는 메모리 누수가 발생하는지 검사해주는 프로그램이다. 나중에 기회가 되면 다른 포스팅에서 공유할 것 같다.
int main(void)
{
DynamicArray* darr = createDA();
if (darr == NULL) return;
Element e1 = { 24, "김철수" };
Element e2 = { 23, "박영희" };
Element e3 = { 21, "이진우" };createDA 함수로 DynamicArray를 동적 할당 받는다.
이후에 e1, e2, e3 세 개의 요소를 정의한다.
printf("\n*** 요소 세개 추가 ***\n");
DAAdd(darr, &e1);
DAAdd(darr, &e2);
DAAdd(darr, &e3);
DAPrint(darr);DAAdd 함수로 위에서 선언한 세 개의 요소를 저장한다.
printf("\n*** 2번째 인덱스에 새로운 요소 추가 ***\n");
Element e4 = { 42, "홍길동" };
DAPut(darr, 2, &e4);
DAPrint(darr);DAPut 함수로 새로 선언된 요소 e4를 동적 배열의 두 번째 위치에 삽입한다.
printf("\n*** 2번째 인덱스의 요소 조회***\n");
Element* e5 = DAGet(darr, 2);
printf("e5 = {%d, %s}\n\n", e5->age, e5->name);DAGet 함수로 방금 삽입한 두 번째 인덱스에 위치한 요소를 꺼내온 후에 출력해본다.
DADestroy(darr);
return 0;
}DynamicArray를 메모리에서 해제한 다음 프로그램을 종료시킨다.
실행 결과
Visual Leak Detector read settings from: C:\Program Files (x86)\Visual Leak Detector\vld.ini
Visual Leak Detector Version 2.5.1 installed.
*** 요소 세개 추가 ***
Name: 김철수 Age: 24
Name: 박영희 Age: 23
Name: 이진우 Age: 21
*** 2번째 인덱스에 새로운 요소 추가 ***
Name: 김철수 Age: 24
Name: 박영희 Age: 23
Name: 홍길동 Age: 42
Name: 이진우 Age: 21
*** 2번째 인덱스의 요소 조회***
e5 = {42, 홍길동}
No memory leaks detected.
Visual Leak Detector is now exiting.
C:\Users\Hotaek\Desktop\2학년 여름\DS_Review\DynamicArray\DynamicArray\Debug\DynamicArray.exe(프로세스 23600개)이(가) 종료되었습니다(코드: 0개).
이 창을 닫으려면 아무 키나 누르세요...요소 세 개가 정상적으로 추가되었고 두 번째 인덱스에 요소 e4도 삽입되었다. 또한 다시 두 번째 인덱스를 꺼내오는데 성공했고, 메모리 누수도 발생하지 않았다. 성공적이다.
질문과 이의 제기, 조언 모두 환영합니다.
