언어 자료구조 알고리즘/디딤돌 C언어

[C언어] 90. 동적 배열 소스 작성

언제나휴일 2016. 4. 18. 07:59
반응형



동적 배열 소스 작성


먼저 EHArr.c 소스 파일에 EHArray.h 파일과 stdlib.h 파일 포함문을 추가하세요.
#include "EHArray.h"
#include <stdlib.h>
 
동적 배열을 생성하는 NewEHArray 함수를 구현하세요.
동적으로 원하는 형식 개체를 생성할 때는 메모리를 동적으로 할당하는 부분과 초기화 부분이 필요하죠.
동적으로 생성하는 부분은 malloc 함수를 사용하고 초기화 부분은 별도의 함수로 작성하세요.
앞으로 초기화 함수 이름은 형식 이름을 쓰기로 해요.
void EHArrayEHArray(EHArray *arr,int init_capa,Element init_value);
EHArray *NewEHArray(
int init_capa,Element init_value)
{
    EHArray *arr = (EHArray *)malloc(
sizeof(EHArray));
    EHArrayEHArray(arr,init_capa,init_value);
   
return arr;
}
 
동적 배열을 초기화하는 함수에서는 EHArray 개체의 멤버를 0으로 초기화하는 것을 먼저 수행하세요.
저장소의 크기는 입력인자로 init_capa 늘려주고 저장소에 초기값이 init_value 순차적으로 보관하세요.
void EHArrayReserve(EHArray *arr,int capacity);
void EHArrayPushBacks(EHArray *arr,int n,Element value);
void EHArrayEHArray(EHArray *arr,int init_capa,Element int_value)
{
    arr->base = 0;
    arr->capacity = 0;
    arr->size = 0;
   
if(init_capa>0)
    {
        EHArrayReserve(arr,init_capa);
        EHArrayPushBacks(arr,init_capa,init_value);
    }
}

저장소의 크기를 늘리는 Reserve함수를 구현하죠.
함수는 초기에 저장소의 크기를 정할 때와 순차적으로 보관할 저장소가 꽉차서 늘릴 사용할 함수예요.
따라서 realloc 함수로 멤버 base 할당한 저장소를 재할당하세요.
void EHArrayReserve(EHArray *arr,int capacity)
{
    arr->base = (Element *)realloc(arr->base,
sizeof(Element)*capacity);
    arr->capacity = capacity;

PushBacks
함수는 n개를 순차 보관하는 함수예요
PushBack
함수를 n 호출하면 되겠죠.
void EHArrayPushBacks(EHArray *arr,int n,Element value)
{
   
int i = 0;
   
for(i=0;i<n;i++)
    {
        EHArrayPushBack(arr,value);
    }
}
 
동적인 개체를 소멸하는 함수에서는 내부에서 동적으로 생성한 부분을 해제하고 자신의 메모리를 해제하세요.
자신의 메모리를 해제하는 부분을 제외한 나머지는 별도의 함수로 작성하세요.
void EHArrayTEHArray(EHArray *arr);
void DeleteEHArray(EHArray *arr)
{
    EHArrayTEHArray(arr);
     free(arr);
}
void EHArrayTEHArray(EHArray *arr)
{
   
if(arr->base)
    {
        free(arr->base);
    }
}
 
저장소의 현재 크기와 보관한 요소 개수를 가져오기 함수에서는 단순히 멤버를 반환하면 되겠죠.
int EHArrayGetCapacity(EHArray *arr)
{
   
return arr->capacity;
}
int EHArrayGetSize(EHArray *arr)
{
   
return arr->size;
}
 
순차적으로 보관하는 PushBack 함수를 구현하기로 해요.
먼저 찼는지 확인하세요.
찼다면 저장소의 크기를 늘려줘야겠죠.
현재 저장소의 크기가 0 아닐 때는 2배로 늘려주고 0 때는 1 늘려주기로 해요.
그리고 base에서 상대적 거리 size 보관한 후에 size 1 증가하세요.
void EHArrayPushBack(EHArray *arr,Element data)
{
   
if(arr->capacity == arr->size)
    {
       
if(arr->capacity)
        {
            EHArrayReserve(arr,arr->capacity*2);
        }
       
else
        {
            EHArrayReserve(arr,1);
        }
    }
    arr->base[arr->size] = data;
    arr->size++;
}
 

보관한 데이터를 반환하는 GetAt함수에서는 입력 인자로 전달받은 index 유효한지 확인하세요.
유효하면 base에서 상대적 거리 index 보관한 요소를 반환하세요.
Element EHArrayGetAt(EHArray *arr,
int index)
{
   
if((index>=0)&&(index<arr->size))
    {
       
return arr->base[index];
    }
   
return 0;
}
 
보관한 요소를 다른 데이터로 설정하는 SetAt 함수에서도 입력 인자가 유효한지 확인하세요.
유효하면 base에서 상대적 거리 index 입력 인자로 받은 데이터로 설정하세요.
void EHArraySetAt(EHArray *arr,int index, Element data)
{
   
if((index>=0)&&(index<arr->size))
    {
        arr->base[index] = data;
    }
}
 
자료를 저장한() 위치는 base 멤버가 갖고 있어요.
그리고 마지막 위치는 base에서 상대적 위치 size에요.
이번 실습에서 마지막 위치는 저장할 위치로 마지막 보관한 데이터가 있는 다음 위치로 하기로 했었죠.
Iterator EHArrayBegin(EHArray *arr)
{
   
return arr->base;
}
Iterator EHArrayEnd(EHArray *arr)
{
   
return arr->base + arr->size;
}
 
특정 위치에 자료를 제거하는 함수를 작성하죠.
제거할 위치 뒤쪽에 있는 모든 요소를 칸씩 앞으로 이동시키세요.
그런데 현재 보관한 요소 개수가 7이고 제거할 위치가 4라면 5,6,7 있는 개의 데이터를 4,5,6 이동시켜야 하겠죠.
이를 쉽게 구현하기 위해 먼저 보관한 요소 개수인 size 1 감소 시킨 후에 하나씩 이동하세요.
이렇게 하면 입력 인자로 전달받은 위치에 다음 위치의 요소를 대입하는 것을 마지막 위치까지 수행하겠네요..
void EHArrayErase(EHArray *arr,Iterator it)
{
    Iterator end;
    arr->size--;
    end = arr->base + arr->size;
   
for(  ; it != end; it++)
    {
        (*it) = *(it+1);
    }
}

 

EHArray.c
#include "EHArray.h"
#include <stdlib.h>
 
void EHArrayEHArray(EHArray *arr,int init_capa,Element init_value);
void EHArrayReserve(EHArray *arr,int capacity);
void EHArrayPushBacks(EHArray *arr,int n,Element value);
void EHArrayTEHArray(EHArray *arr);
 
EHArray *NewEHArray(
int init_capa,Element init_value)
{
    EHArray *arr = (EHArray *)malloc(
sizeof(EHArray));
    EHArrayEHArray(arr,init_capa,init_value);
   
return arr;
}  
 
void EHArrayEHArray(EHArray *arr,int init_capa,Element init_value)
{
    arr->base = 0;
    arr->capacity = 0;
    arr->size = 0;
   
if(init_capa>0)
    {
        EHArrayReserve(arr,init_capa);
        EHArrayPushBacks(arr,init_capa,init_value);
    }
}
void EHArrayReserve(EHArray *arr,int capacity)
{
    arr->base = (Element *)realloc(arr->base,
sizeof(Element)*capacity);
    arr->capacity = capacity;
}
void EHArrayPushBacks(EHArray *arr,int n,Element value)
{
   
int i = 0;
   
for(i=0;i<n;i++)
    {
        EHArrayPushBack(arr,value);
    }
}
void DeleteEHArray(EHArray *arr)
{
    EHArrayTEHArray(arr);
    free(arr);
}  
 
void EHArrayTEHArray(EHArray *arr)
{
   
if(arr->base)
    {
        free(arr->base);
    }
}
int EHArrayGetCapacity(EHArray *arr)
{
   
return arr->capacity;
}
int EHArrayGetSize(EHArray *arr)
{
   
return arr->size;
}

 

void EHArrayPushBack(EHArray *arr,Element data)
{
   
if(arr->capacity == arr->size)
    {
       
if(arr->capacity)
        {
            EHArrayReserve(arr,arr->capacity*2);
        }
       
else
        {
            EHArrayReserve(arr,1);
        }
    }
    arr->base[arr->size] = data;
    arr->size++;
}
Element EHArrayGetAt(EHArray *arr,
int index)
{
   
if((index>=0)&&(index<arr->size))
    {
        
return arr->base[index];
    }
   
return 0;
}
void EHArraySetAt(EHArray *arr,int index, Element data)
{
   
if((index>=0)&&(index<arr->size))
    {
        arr->base[index] = data;
    }
}
Iterator EHArrayBegin(EHArray *arr)
{
   
return arr->base;  
}
Iterator EHArrayEnd(EHArray *arr)
{
   
return arr->base + arr->size;
}
void EHArrayErase(EHArray *arr,Iterator it)
{
    Iterator end;
    arr->size--;
    end = arr->base + arr->size;
   
for(  ; it != end; it++)
    {
        (*it) = *(it+1);
    }
}

반응형