ChainNode::ChainNode(T value = 0, ChainNode *pos = NULL); - 체인 노드를 새로 만들어 주는 ChainNode 객체의 메써드로써, 일반 대입만 하기 때문에 O(1)을 차지한다.
void Chain::MakeChainNodeFromList(); - 한 줄로 입력 받은 String을 띄어쓰기 기준으로 정수형 자료로 변환해 Chain을 구성하는 메써드, 입력 String의 길이가 n이라 했을 때 O(n)이다.
void Chain::MakeChainNode(T value); - Chain::MakeChainNodeFromLis()에서 쓰이며, 파라미터 값을 해당 노드에 넣어준 다음 다음 노드를 만들어 준다. O(1).
Chain::Chain(); - Type이 T인 체인 리스트를 생성한다. 처음 노드를 뜻하는 first와 마지막 노드를 뜻하는 last는 NULL로 초기화 된다. O(1).
출력 부분:
int Chain::HowManyNodes(); - Chainiterator을 이용하여 체인 리스트를 순환하며 chain의 노드가 몇 개 있는지 리턴해 주는 메써드, chain의 노드 개수가 n이라 했을 때, O(n)이다.
__int64 Chain::SmallestThing(); - Chainiterator을 이용하여 체인 리스트를 순환하며 chain의 노드에서 최솟값을 리턴해 주는 메써드, chain의 노드 개수가 n이라 했을 때, O(n)이다.
void Chain::PrintAll(); - int Chain::HowManyNodes()와 __int64 Chain::SmallestThing()의 결과 값과 함께, chain의 모든 값들을 출력해주는 메써드, g(3n)이므로 O(n)이다.
Chainiterator 부분:
Chain::Chainiterator::Chainiterator(ChainNode<T>* stratNode = NULL); - 체인을 순환하기 위하여 Chain의 class인 Chainiterator의 객체에 Chain의 객체를 저장한다.
T& Chain::Chainiterator::operator*(); - 체인의 참조를 정의한다.(비 포인터)
T* Chain::Chainiterator::operator->; - 체인의 간접참조를 정의한다.(포인터)
bool Chain::Chainiterator::operator!=; - 체인 순환에 있어서 비교를 행하기 위하여 정의한다.
Chai
n::Chainiterator::&operator++(); - 사전 ++ 반복자
Chain::Chainiterator::operator++(T); - 사후 ++ 반복자
Chain::Chainiterator::begin(); - 체인 순환에 있어서 시작을 지정해준다.
Chain::Chainiterator::end(); - 체인 순환에 있어서 마지막을 지정해준다.
main 부분:
int main(); - Chain 생성(Chain::Chain();)(O(1) ->
입력을 통한 ChainNode 생성(void Chain::MakeChainNodeFromList();)(O(n) ->
출력 (void Chain::PrintAll();)(O(n)) -> return 0;
So, 총 시간 복잡도는 O(n)이다.
Chain List의 구현에 있어서, value - key 구조를 사용하던 입장에서는 어려운 과제였다. template클래스를 제대로 사용하지 못하던 입장에서는 이에 적응하는 것 또한 문제였고, operator를 재정의 하는 것은 해 보았지만 template 클래스의 inerclass에서 재정의 하는 것 또한 어려워서 시간을 많이 쏟았다. 하지만 이러한 재 사용 가능한 Chain을 직접 구현한 것은 큰 의미가 있다고 생각했으며 유익한 과제였던 것 같다.
2017125021류동인hw05.cpp2017125021류동인hw05.cpp