[자료구조] Linked list 2

Linked list 2

링크드 리스트로 연결된 bag class

• 이제 링크드 리스트를 사용하므로 capacity를 결정할 필요가 없다.
• reserve 함수가 더이상 필요없다.
• 알아서 크기 조절이 된다.

새 클래스 정의

이전장에 정의한(linked list 1) node.h, node.cpp를 그대로 이용한다.

class bag
{
	public:
		typedef std::size_t size_type;
		…
	private:
		node* head_ptr;
		size_type many_nodes;
};

새로운 클래스 구현

bag의 기능을 추가하기위해 다음 함수와 오퍼레이터를 추가한다.

• Constructors/Destructor(생성자/소멸자)
• Assignment(할당)/Self-Increment(자기 증가) Operators(=, +=)
• erase_one 함수
• count 함수
• grab 함수
• insert 함수
• • 연산자

Constructors - 생성자

1. 인자가 없는 Default constructor
   • head_ptr을 NULL로 설정
   • many_nodes를 0으로 설정

bag::bag( )
{
	head_ptr = NULL;
	many_nodes = 0;
}

1. Copy constructor
   • 객체 소스를 복사하여 bag 객체 인스턴스를 생성한다.
   • 그렇게 하기 위해 list_copy를 사용할 수 있다.

bag::bag(const bag& source)
{
	node *tail_ptr ;
	list_copy(source.head_ptr, head_ptr, tail_ptr);
	many_nodes = source.many_nodes;
}

Destructor - 소멸자

• 목록의 모든 노드를 해제하여 bag을 파괴한다.
• 이를 위해 list_clear를 사용한다.

bag::~bag( )
{
list_clear(head_ptr) ;
many_nodes = 0 ;
;// not necessary
}

Assignment (=)

• 한 가방의 내용물을 다른 가방에 할당
• bag a(2, 4) = bag b(3, 9, 5)
• bag a(3, 9,5)
• 프로세스는 다음과 같다.

1. 자기 할당인지 먼저 테스트하고 그렇다면 리턴한다.
2. 리스트를 클리어한다.
3. 소스 리스트의 복사본을 만들어 새 리스트로 만든다.

void bag::operator =(const bag& source )
{
	node* tail_ptr ;
	if (this == &source)
		return;
	list_clear(head_ptr);
	many_nodes = 0;
	list_copy(source.head_ptr, head_ptr, tail_ptr);
	many_nodes = source.many_nodes;
}

Self-Increment operator (+=)

• 한 bag의 리스트를 bag에 추가
• bag a(4, 8) += bag b(3, 9, 5)
• bag a(3, 9, 5, 4, 8)

1. 가수가 비어 있는지 먼저 테스트하고 비어 있으면 반환합니다.
2. 소스 목록의 복사본을 만듭니다.
3. 자신의 목록 끝에 복사본을 추가합니다.