5. 1 배열
C언어에서 제공하는 형식 배열은 원소 개수를 개발 단계에 상수로 결정하여 컴파일 시점에 할당할 메모리 크기를 결정합니다. 하지만 자료구조에서 말하는 배열은 C언어에서 제공하는 배열뿐만 아니라 같은 종류의 자료를 보관하기 위해 동적으로 메모리를 할당하여 관리하는 구조도 포함합니다.
이 책에서는 자료를 보관하는 저장소를 동적으로 할당하는 사용자 정의 배열을 구현하고 배열을 사용하는 방법을 살펴봅시다.
5.1.1 동적 배열 설계
여기에서 작성하는 배열은 동적 배열입니다. 동적 배열이란 자료를 저장하는 메모리를 프로그램 동작 중에 크기를 결정하여 동적으로 할당하는 배열을 말합니다. 즉 보관할 수 있는 원소의 개수를 개발 단계에서 결정하는 것이 아니라 실행 시간에 결정하는 것을 말합니다.
그리고 저장소에 자료를 보관한 상태가 꽉 찼을 때 다른 자료를 보관 요청하면 저장소의 크기를 확장하는 확장 가능한 동적 배열로 정의합시다. 이를 위해서 사용자 정의 배열 형식에서는 저장소의 위치 정보와 현재 저장소의 크기와 보관하고 있는 자료 개수를 멤버로 기억하고 있어야 합니다.
특히 이 책에서 작성한 배열은 동적으로 생성한 자료를 보관하기 위한 용도로 작성합시다. 어떠한 형태의 자료이든 동적으로 생성한 자료면 보관할 수 있게 합시다. 코드를 보기 쉽게 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
#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);
관련 게시글
[디딤돌 자료구조와 알고리즘] 5. 선형 자료구조 - 개요
디딤돌 C언어
[C언어] 91. 동적 배열 사용 예 - 동적 개체 정의
[C언어] 93. 동적 배열 사용 예 - 인덱스로 보관
자료구조와 STL
[자료구조와 STL] 4. vector 인덱스 연산을 통해 사용하기
[자료구조와 STL] 5. vector 인데스 연산으로 사용하기 예제 코드
[자료구조와 STL] 6.vector에 자료를 차례대로 보관하기
[자료구조와 STL] 7.vector에 자료를 차례대로 보관하기 예제 코드
[자료구조와 STL] 8. 3 vector를 이용하여 특정 키 순으로 보관하기
[자료구조와 STL] 9.vector를 이용하여 특정 키 순으로 보관하기 예제 코드
[자료구조와 STL] 11. vector 만들기 소스 코드
디딤돌 자료구조와 알고리즘 with C++
3.1 배열과 vector [디딤돌 자료구조와 알고리즘 with C++]
3.1.1 이 책에서 공통으로 사용하는 것들 [디딤돌 자료구조와 알고리즘 with C++]
3.1.2 vector에 순차적으로 보관 [디딤돌 자료구조와 알고리즘 with C++]
3.1.4 vector에 특정 키 순으로 보관 [디딤돌 자료구조와 알고리즘 with C++]
3.1.5 vector를 인덱스 연산으로 사용 [디딤돌 자료구조와 알고리즘 with C++]
4. vector 만들기 [디딤돌 자료구조와 알고리즘 with C++]
'언어 자료구조 알고리즘 > [C]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| [디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.3 연결리스트 테스트 (0) | 2016.05.16 |
|---|---|
| [디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.2 연결리스트 구현 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.1 연결리스트 설계 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.3 동적 배열 테스트 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.2 동적 배열 구현 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5. 선형 자료구조 - 개요 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 4.3.2 병합 정렬 알고리즘 구현 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 4.3 병합 정렬 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 4.2 이진 탐색 알고리즘 (0) | 2016.04.10 |
| [디딤돌 자료구조와 알고리즘 with C] 4. 분할 정복 알고리즘 (0) | 2016.04.10 |