[C++] 73. 최종 실습 - 확장 가능한 순차 배열
EhNara 프로그램에서는 EhNara 클래스, 학생 공장에서 학생 개체를 보관합니다. 그리고 장소에서는 사람 개체를 보관합니다. 여기에서는 순차적으로 보관할 수 있는 확장 가능한 배열을 템플릿으로 정의합시다.
확장 가능한 배열은 저장소가 꽉 차면 내부에서 저장소의 크기를 늘려 주어 사용하는 개발자가 저장소의 크기에 신경을 쓰지 않고 사용할 수 있는 동적 배열입니다.
여기에서는 순차 보관하는 기능과, 특정 인덱스의 요소를 제거, 특정 알고리즘이 참인 인덱스를 구하는 등의 기능을 제공하는 확장 가능한 배열을 만듭시다.
template <typename data>
class SeqArray
{
먼저 저장소와 저장소의 크기, 보관 개수를 기억하고 있어야 합니다.
data *base; //저장소
size_t capacity; //저장소 크기
size_t size; //보관 개수
public:
생성자에서는 멤버 필드의 값을 0으로 초기화합시다.
SeqArray()
{
base = 0;
capacity = 0;
size = 0;
}
소멸자에서는 저장소를 할당하였을 때 저장소를 해제하는 구문이 필요하겠죠.
~SeqArray(void)
{
if(base)//저장소가 있을 때
{
delete[] base;//저장소 해제
}
}
순차 보관하는 메서드를 구현합시다.
void PushBack(data value)//순차 보관
{
꽉 차면 저장소를 늘려주어야 합니다.
if(IsFull())//꽉차면
{
현재 저장소의 크기가 0이 아니면 두 배로 늘리고 0이면 1로 늘리기로 합시다.
if(capacity)//저장소의 개수가 참일 때
{
Reserve(capacity *2);//두 배로 확장
}
else//아닐 때(0일 때)
{
Reserve(1);//1로 확장
}
}
입력 인자로 받은 값을 순차 보관하고 보관 개수를 1 증가하세요.
base[size] = value;//보관
size++;//보관 개수 1 증가
}
특정 인덱스 요소를 삭제하는 메서드를 구현합시다.
void RemoveAt(size_t index)//특정 인덱스 요소 삭제
{
인덱스가 유효하지 않으면 메서드를 종료합니다.
if(IsAvailIndex(index)==false)//인덱스가 유효하지 않을 때
{
return;
}
인덱스가 유효하면 보관 개수를 1 감소합니다. 그리고 인덱스 뒤의 값들을 한 칸씩 앞으로 이동합니다.
size--;//보관 개수 1 감소
for( ;index<size;index++)
{
base[index] = base[index+1];//한 칸씩 앞으로 이동
}
}
특정 알고리즘이 처음으로 참인 위치를 찾는 메서드를 제공합시다. 특정 알고리즘은 find_if로 가정합시다.
template <typename find_if>
int FindIf(find_if fun)//특정 알고리즘이 처음으로 참인 위치 찾기
{
순차적으로 입력 알고리즘에 보관한 값을 적용합니다.
for(size_t i = 0; i<size; ++i)
{
if(fun(base[i]))//알고리즘에 적용하였을 때 참이면
{
만약 참인 부분을 만나며 인덱스를 반환합니다.
return i; //인덱스 반환
}
}
끝까지 반복해도 참인 부분을 만나지 못하면 -1을 반환합시다.
return -1;//-1 반환
}
인덱스 연산자를 중복 정의합시다.
data &operator[](size_t index)//인덱서
{
인덱스가 유효하지 않으면 예외를 던져줍니다.
if(IsAvailIndex(index)==false)//유효하지 않은 인덱스일 때
{
throw "유효하지 않은 인덱스를 사용하였습니다.";//예외 던짐
}
인덱스가 유효하면 해당 인덱스의 원소를 반환합니다.
return base[index];//인덱스의 원소 반환
}
유효한 인덱스인지 판별하는 메서드와 보관한 원소 개수를 반환하는 메서드를 제공합시다.
bool IsAvailIndex(size_t index)const//유효한 인덱스인지 판별
{
return (index>=0)&&(index<size);
}
size_t GetSize()const
{
return size;
}
private:
꽉 찼는지 판별하는 메서드도 구현하세요.
bool IsFull()const//꽉 찼는지 판별
{
return size == capacity;
}
저장소를 확장하는 메서드를 구현합시다.
void Reserve(int ncapacity)//저장소 확장
{
저장소의 위치를 임시 변수에 설정합니다.
data *tbuf = base;//저장소 위치를 tbuf로 설정
새로운 저장소를 동적 할당합니다.
base = new data[ncapacity];//저장소 동적 할당
저장소의 크기를 설정합니다.
capacity = ncapacity;//저장소 크기 설정
if(tbuf)//이전 저장소가 참이면
{
이전 저장소가 있었다면 원래 보관한 값을 새로운 저장소에 보관합니다.
for(size_t i=0; i<size;++i)
{
base[i] = tbuf[i];//이전 저장소에 보관한 값을 새로운 저장소로 이동
}
이전 저장소의 메모리는 해제합니다.
delete[] tbuf;//이전 저장소 메모리 해제
}
}
};
다음은 이를 테스트 하기 위한 코드를 포함한 전체 코드입니다.
73. 순차보관 컬렉션.zip//SeqArray.h
#pragma once
template <typename data>
class SeqArray
{
data *base; //저장소
size_t capacity; //저장소 크기
size_t size; //보관 개수
public:
SeqArray()
{
base = 0;
capacity = 0;
size = 0;
}
~SeqArray(void)
{
if(base)//저장소가 있을 때
{
delete[] base;//저장소 해제
}
}
void PushBack(data value)//순차 보관
{
if(IsFull())//꽉차면
{
if(capacity)//저장소의 개수가 참일 때
{
Reserve(capacity *2);//두 배로 확장
}
else//아닐 때(0일 때)
{
Reserve(1);//1로 확장
}
}
base[size] = value;//보관
size++;//보관 개수 1 증가
}
void RemoveAt(size_t index)//특정 인덱스 요소 삭제
{
if(IsAvailIndex(index)==false)//인덱스가 유효하지 않을 때
{
return;
}
size--;//보관 개수 1 감소
for( ;index<size;index++)
{
base[index] = base[index+1];//한 칸씩 앞으로 이동
}
}
template <typename find_if>
int FindIf(find_if fun)//특정 알고리즘이 처음으로 참인 위치 찾기
{
for(size_t i = 0; i<size; ++i)
{
if(fun(base[i]))//알고리즘에 적용하였을 때 참이면
{
return i; //인덱스 반환
}
}
return -1;//-1 반환
}
data &operator[](size_t index)//인덱서
{
if(IsAvailIndex(index)==false)//유효하지 않은 인덱스일 때
{
throw "유효하지 않은 인덱스를 사용하였습니다.";//예외 던짐
}
return base[index];//인덱스의 원소 반환
}
bool IsAvailIndex(size_t index)const//유효한 인덱스인지 판별
{
return (index>=0)&&(index<size);
}
size_t GetSize()const
{
return size;
}
private:
bool IsFull()const//꽉 찼는지 판별
{
return size == capacity;
}
void Reserve(int ncapacity)//저장소 확장
{
data *tbuf = base;//저장소 위치를 tbuf로 설정
base = new data[ncapacity];//저장소 동적 할당
capacity = ncapacity;//저장소 크기 설정
if(tbuf)//이전 저장소가 참이면
{
for(size_t i=0; i<size;++i)
{
base[i] = tbuf[i];//이전 저장소에 보관한 값을 새로운 저장소로 이동
}
delete[] tbuf;//이전 저장소 메모리 해제
}
}
};
//Program.cpp
#include <iostream>
using namespace std;
#include "SeqArray.h"
class FindFun
{
int value;
public:
FindFun(int value)
{
this->value = value;
}
bool operator()(int data)
{
return value == data;
}
};
int main()
{
SeqArray<int> sa;
sa.PushBack(3);
sa.PushBack(9);
sa.PushBack(2);
sa.PushBack(4);
size_t size = sa.GetSize();
for(size_t i = 0; i<size; i++)
{
cout<<sa[i]<<" ";//3 9 2 4
}
cout<<endl;
sa.RemoveAt(2);
size = sa.GetSize();
for(size_t i = 0; i<size; i++)
{
cout<<sa[i]<<" ";//3 9 4
}
cout<<endl;
FindFun ff(3);
size_t index = sa.FindIf(ff);
if(index!=-1)
{
cout<<3<<" is located at index "<<index<<endl;
cout<<"sa["<<index<<"]:"<<sa[index]<<endl;
}
return 0;
}
▷ 실행 결과
3 9 2 4
3 9 4
3 is located at index 0
sa[0]:3
'언어 자료구조 알고리즘 > 디딤돌 C++' 카테고리의 다른 글
| [C++] 78. 최종 실습 - 전체 보기 (0) | 2016.05.01 |
|---|---|
| [C++] 77. 최종 실습 - 학생 이동 (0) | 2016.05.01 |
| [C++] 76. 최종 실습 - 학생 생성 (0) | 2016.05.01 |
| [C++] 75. 최종 실습 - 초기화 및 해제화 (0) | 2016.05.01 |
| [C++] 74. 최종 실습 - 클래스 추가하기 (0) | 2016.05.01 |
| [C++] 72. 최종 실습 - 프로토 타이핑 (0) | 2016.05.01 |
| [C++] 71. 최종 실습 - EHNARA 뼈대 (0) | 2016.05.01 |
| [C++] 70. 최종 실습 - 설계1(클래스 다이어그램) (0) | 2016.05.01 |
| [C++] 69. 최종 실습 - 요구 분석 및 정의 (0) | 2016.05.01 |
| [C++] 68. 최종 실습 - 개발 공정 및 시나리오 (0) | 2016.05.01 |