[C언어 자료구조] 2.2 동적 배열 구현
먼저 동적 배열을 생성하는 함수를 작성합시다.
Array *New_Array()
{
동적 배열 형식 크기의 메모리를 할당합니다.
Array *arr = 0;
arr = (Array *)malloc(sizeof(Array));
자료를 보관할 저장소는 0으로 초기화합니다. 여기서 구현할 동적 배열은 저장소가 꽉 차면 내부적으로 저장소의 크기를 확장해 나갈 것입니다.
arr->base = 0;
저장소에 용량과 보관한 자료 개수를 0으로 초기화한 후 동적 배열을 반환합니다.
arr->capacity = arr->usage = 0;
return arr;
}
동적 배열을 소멸하는 함수를 작성합시다.
void Delete_Array(Array *arr)
{
만약 저장소가 유효하면 저장소를 해제합니다.
if(arr->base)
{
free(arr->base);
}
그리고 자신의 메모리를 해제합니다.
free(arr);
}
배열에 원하는 개수만큼 특정 자료로 설정하는 함수를 작성합시다.
void Array_SetSize(Array *arr,int capacity,Element data)
{
먼저 저장소의 크기를 설정하고 해당 크기만큼 자료를 보관할 수 있는 크기의 저장소를 재할당합니다. 만약 보관한 자료가 있다면 이들을 유지하고 있어야 하므로 realloc 함수를 사용합니다.
arr->capacity = capacity;
arr->base = (Element *)realloc(arr->base,sizeof(Element)*arr->capacity);
for( ;arr->usage<arr->capacity; arr->usage++)
{
arr->base[arr->usage] = data;
}
}
순차적으로 보관할 때 사용할 함수를 작성합시다.
void Array_PushBack(Array *arr,Element data)
{
마지막 보관한 다음 위치에 보관하면 순차적으로 보관할 수 있습니다. 먼저 마지막 보관한 다음 위치를 얻어오는 함수를 호출하여 추가할 위치를 구합니다.
Iterator at = Array_End(arr);
그리고 해당 위치에 자료를 보관하는 함수를 호출합니다.
Array_Insert(arr,at,data);
}
특정 위치에 자료를 보관하는 함수를 작성합시다.
void Array_Insert(Array *arr,Iterator pos,Element data)
{
먼저 입력 인자로 들어온 위치를 인덱스로 변환합니다.
int index = pos - arr->base;
해당 인덱스 뒤에 보관한 요소들을 오른쪽으로 한 칸씩 이동해야 합니다. 먼저 이동해야 할 원소 개수를 구합니다. 만약 현재 보관한 요소 개수가 6이고 추가할 인덱스가 2이면 인덱스 2, 3, 4, 5에 있는 요소를 이동해야 합니다. 따라서 배열에 보관한 요소 개수에 index를 뺀 값이 이동할 요소 개수입니다.
int mcount = arr->usage - index;
만약 저장소에 자료가 꽉 차면 공간을 늘려주어야 합니다.
if(arr->capacity == arr->usage)
{
여기에서는 저장소의 크기가 0일 때는 1로 그렇지 않을 때는 현재 크기의 두 배로 설정합시다.
if(arr->capacity)
{
arr->capacity*=2;
}
else
{
arr->capacity = 1;
}
저장소를 재할당합니다.
arr->base = (Element *)realloc(arr->base,sizeof(Element)*arr->capacity);
}
저장소의 상대적 거리 index에서 요소 크기 * 이동할 요소 개수만큼의 메모리를 다음 위치로 메모리 복사합니다. 이를 통해 index 위치부터 그 뒤에 있는 요소를 한 칸씩 오른쪽으로 보내는 것입니다.
memcpy(arr->base+index+1,arr->base+index,sizeof(Element)*mcount);
저장소의 index 위치에 자료를 보관하고 보관한 요소 개수를 1 증가합니다.
arr->base[index] = data;
arr->usage++;
}
이번에는 특정 인덱스의 요소를 변경하는 함수를 작성합시다.
void Array_SetAt(Array *arr,int index,Element data)
{
먼저 입력 인자로 전달받은 인덱스가 유효한지 확인합니다.
if((index>=0)&&(index<arr->usage))
{
유효하면 저장소의 상대적 거리 인덱스에 있는 자료를 입력 인자로 받은 값으로 설정합니다.
arr->base[index] = data;
}
}
특정 인덱스에 보관한 자료를 반환하는 함수를 작성합시다.
Element Array_GetAt(Array *arr,int index)
{
먼저 입력 인자로 전달받은 인덱스가 유효한지 확인합니다.
if((index>=0)&&(index<arr->usage))
{
유효하면 저장소의 상대적 거리 인덱스에 있는 자료를 반환합니다.
return arr->base[index];
}
유효하지 않을 때는 0을 반환하기로 합시다.
return 0;
}
저장소의 시작 위치에 마지막 자료를 보관한 다음 위치를 반환하는 함수를 작성합시다.
Iterator Array_Begin(Array *arr)
{
return arr->base;
}
Iterator Array_End(Array *arr)
{
return arr->base+arr->usage;
}
마지막으로 특정 위치의 요소를 제거하는 함수를 작성합시다.
void Array_Erase(Array *arr,Iterator pos)
{
먼저 입력 인자로 전달받은 위치를 인덱스로 변환합니다.
int index = pos - arr->base;
해당 위치 다음 요소부터 한 칸씩 왼쪽으로 이동합니다. 이를 위해 이동할 요소 개수를 구합니다.
int mcount = arr->usage - index -1;
입력 인자로 전달받은 위치에 바로 다음 위치부터 요소의 크기에 이동할 요소 개수를 곱한 메모리 크기를 복사합니다. 그리고 보관한 요소 개수를 1 감소합니다.
memcpy(pos,pos+1,sizeof(Element)*mcount);
arr->usage--;
}
다음은 Array.c 파일의 소스 코드입니다.
//Array.c
#include "Array.h"
#include <malloc.h>
#include <memory.h>
Array *New_Array()
{
Array *arr = 0;
arr = (Array *)malloc(sizeof(Array));
arr->base = 0;
arr->capacity = arr->usage = 0;
return arr;
}
void Delete_Array(Array *arr)
{
if(arr->base)
{
free(arr->base);
}
free(arr);
}
void Array_SetSize(Array *arr,int capacity,Element data)
{
arr->capacity = capacity;
arr->base = (Element *)realloc(arr->base,sizeof(Element)*arr->capacity);
for( ;arr->usage<arr->capacity; arr->usage++)
{
arr->base[arr->usage] = data;
}
}
void Array_PushBack(Array *arr,Element data)
{
Iterator at = Array_End(arr);
Array_Insert(arr,at,data);
}
void Array_Insert(Array *arr,Iterator pos,Element data)
{
int index = pos - arr->base;
int mcount = arr->usage - index;
if(arr->capacity == arr->usage)
{
if(arr->capacity)
{
arr->capacity*=2;
}
else
{
arr->capacity = 1;
}
arr->base = (Element *)realloc(arr->base,sizeof(Element)*arr->capacity);
}
memcpy(arr->base+index+1,arr->base+index,sizeof(Element)*mcount);
arr->base[index] = data;
arr->usage++;
}
void Array_SetAt(Array *arr,int index,Element data)
{
if((index>=0)&&(index<arr->usage))
{
arr->base[index] = data;
}
}
Element Array_GetAt(Array *arr,int index)
{
if((index>=0)&&(index<arr->usage))
{
return arr->base[index];
}
return 0;
}
Iterator Array_Begin(Array *arr)
{
return arr->base;
}
Iterator Array_End(Array *arr)
{
return arr->base+arr->usage;
}
void Array_Erase(Array *arr,Iterator pos)
{
int index = pos - arr->base;
int mcount = arr->usage - index -1;
memcpy(pos,pos+1,sizeof(Element)*mcount);
arr->usage--;
}
'언어 자료구조 알고리즘 > 디딤돌 자료구조 (C언어)' 카테고리의 다른 글
[C언어 자료구조] 3.2 연결리스트 구현 (0) | 2016.11.26 |
---|---|
[C언어 자료구조] 3.1 연결리스트 설계 (0) | 2016.11.26 |
[C언어 자료구조] 3. 연결리스트 (0) | 2016.11.26 |
[C언어 자료구조] 2.4 동적 배열 소스 코드 (0) | 2016.11.26 |
[C언어 자료구조] 2.3 동적 배열 테스트 (0) | 2016.11.26 |
[C언어 자료구조] 2.1 동적 배열 설계 (0) | 2016.11.26 |
[C언어 자료구조] 2. 배열(Array) (0) | 2016.11.26 |
[C언어 자료구조] 1.2 공통으로 사용할 코드 (4) | 2016.11.26 |
[C언어 자료구조] 1.1 자료구조(Data Structure) (0) | 2016.11.26 |
[C언어 자료구조] 1. 다루는 내용 (0) | 2016.11.26 |