추상 데이터형

자료구조&알고리즘

추상 데이터형

CalebHong 2022. 2. 10. 12:39

컨테이너

1. 컨테이너의 개념

- 컨테이너의 정의와 기능

* 대부분의 일반적 추상형 데이터 타입(ADT: Abstract Data Type)

* 객체에 접근하고 저장하는 등의 자료의 구조를 묘사함

- 처리와 연산의 정의

[ 개체(Entity)이거나 ]

[ 컨테이너에 저장된 객체 ]

2. 연산

- 컨테이너의 연산

* 컨테이너의 생성

* 기존 컨테이너의 복사나 폐기

* 컨테이너 비움

* 컨테이너 내 객체의 개수 반환

* 컨테이너가 수용할 수 있는 최대 객체의 수 반환

* 두 컨테이너에서 합집합과 교집합 계산

- 컨테이너에 저장된 객체의 연산

* 객체의 삽입

* 객체의 접근 혹은 수정

* 객체의 삭제

* 컨테이너 내에 존재 유무 확인

* 컨테이너 내 객체 모두를 반복 (혹은 한번에 하나씩 한꺼번에 접근)

- C++ STL에서 4가지 컨테이너의 소개

	Unique Objects/Keys	Duplicate Ojbect/Keys
Simple Container	set<Type>	multiset<Type>
Associative Container	map<Key_type, Type>	multimap<Key_type, Type>

#include <iostream>
#include <set>

int main()
{
	std::set<int> ints;
    
    for (int i = -100; i <= 100; ++i)
    {
    	// Ignores duplicates: (-3)*(-3) == 3*3
        // Inserts 101 values : 0, 1, 4, 9, ..., 10000
    	ints.insert(i*i); 
    } 
    
    std::cout << "Size of 'is': " << ints.size() << std::endl; // Print 101
    
    ints.erase(50); // Does nothing
    ints.erase(9); // Removes 9
    std::cout << "Size of 'is': " << ints.size() << std::endl; // Prints 100
    
    return 0;
}

관계와 순서

1. 관계

- 정의

* 객체 간의 관계 - 관계를 기반으로 추가적 연산 수행

- 탐색

* 저장 뿐 아니라 객체의 개수에 관계없이 빠르게 처리할 수 있는 자료 구조 필요

* Hash Table은 객체의 개수가 얼마이든 같은 속도로 객체 탐색

Ex) 탐색의 예

- 12명의 직원에 대해 각 직원당 우편함 대신 각 직원의 성에 첫 자에 해당하는 24개의 통 마련

- 종류

* 선형 순서 * 단계적(계층) 순서

* 부분 순서 * 동치 관계

* 약한 관계 * 인접 순서

- 논리적 연산

* 같은가?

* 작은가?

* 나누어 지는가?

* 나머지가 같은가?

2. 순서

- 선형적) 순서

* 관계가 추이적일 때 다음 세 가지 중 하나인 경우 비대칭 관계

1) x < y

2) y < x

3) x = y

- 예시

정수 : 1, 2, 3, 4, ...

실수 : 1.2, 1.2001, 1.24, 1.35, ...

문자 : a, b, c, d, ...

메모리 : 0x00000000, 0x00000001, ..., x0FFFFFFFF

- 사전적 순서

* 순서화 된 영어 단어의 집합

* 순서는 첫 글자 비교 후 다음 글자로 차례로 비교

- 계층적 순서

* 파일 시스템에서의 디렉토리

* 피라미드 구조를 가진다.