자료구조와 알고리즘 - 언제나 휴일

여기에서 작성하는 배열은 동적 배열입니다. 동적 배열이란 자료를 저장하는 메모리를 프로그램 동작 중에 크기를 결정하여 동적으로 할당하는 배열을 말합니다. 즉 보관할 수 있는 원소의 개수를 개발 단계에서 결정하는 것이 아니라 실행 시간에 결정하는 것을 말합니다.

그리고 저장소에 자료를 보관한 상태가 꽉 찼을 때 다른 자료를 보관 요청하면 저장소의 크기를 확장하는 확장 가능한 동적 배열로 정의합시다. 이를 위해서 사용자 정의 배열 형식에서는 저장소의 위치 정보와 현재 저장소의 크기와 보관하고 있는 자료 개수를 멤버로 기억하고 있어야 합니다.

특히 이 책에서 작성한 배열은 동적으로 생성한 자료를 보관하기 위한 용도로 작성합시다. 어떠한 형태의 자료이든 동적으로 생성한 자료면 보관할 수 있게 합시다. 코드를 보기 쉽게 void 포인터 형식을 Element 형식으로 타입 재지정할게요.

typedef void * Element;

이를 토대로 사용자 정의 배열은 다음처럼 정의할 수 있습니다.

typedef struct _Array Array;
struct _Array
{
    Element *base;
    int capacity;
    int usage;
};

자료를 보관하거나 보관한 위치인 Element * 형식을 Iterator 형식 이름으로 지정할게요.

typedef Element *Iterator;

동적 배열을 생성하는 함수와 소멸하는 함수를 제공합니다.

Array *New_Array();
void Delete_Array(Array *arr);

동적 배열에 특정 data를 요청한 개수만큼 설정하는 메서드를 제공합시다.

void Array_SetSize(Array *arr,int capacity,Element data);

동적 배열에 자료를 보관하는 두 가지 함수를 제공합시다. 하나는 순차적으로 보관하는 함수로 마지막 보관한 다음 위치에 보관합니다. 그리고 나머지는 사용하는 개발자가 원하는 위치를 인자로 전달하여 자료를 보관하는 함수입니다.

void Array_PushBack(Array *arr,Element data);
void Array_Insert(Array *arr,Iterator pos,Element data);

그리고 특정 인덱스에 보관한 자료를 다른 자료로 설정하거나 가져오기 함수를 제공합시다.

void Array_SetAt(Array *arr,int index,Element data);
Element Array_GetAt(Array *arr,int index);

자료를 보관하는 시작 위치와 이번에 자료를 보관할 위치(마지막 자료를 보관한 다음 위치)를 반환하는 함수도 제공합니다.

Iterator Array_Begin(Array *arr);
Iterator Array_End(Array *arr);

특정 위치에 보관한 자료를 제거하는 함수도 제공합시다.

void Array_Erase(Array *arr,Iterator pos);

다음은 동적 배열을 설계한 헤더 Array.h 파일의 내용입니다.

//Array.h

#pragma once
typedef void * Element;
typedef struct _Array Array;
struct _Array
{
    Element *base;
    int capacity;
    int usage;
};
typedef Element *Iterator;

Array *New_Array();
void Delete_Array(Array *arr);
void Array_SetSize(Array *arr,int capacity,Element data);
void Array_PushBack(Array *arr,Element data);
void Array_Insert(Array *arr,Iterator pos,Element data);
void Array_SetAt(Array *arr,int index,Element data);
Element Array_GetAt(Array *arr,int index);
Iterator Array_Begin(Array *arr);
Iterator Array_End(Array *arr);
void Array_Erase(Array *arr,Iterator pos);

[카테고리:] <span>자료구조와 알고리즘</span>

5.1.1 동적 배열 설계