[디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.2 동적 배열 구현

5.1.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

#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--;

}

---

관련 게시글

[디딤돌 자료구조와 알고리즘] 5. 선형 자료구조 - 개요

[디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.1 동적 배열 설계