-
자료구조: 데이터의 집합
-
데이터의 추상화 (Data Abstraction)
=> Data Encapsulation
Application의 Data와 Logical 단계에서의 Data를 구분하자
Abstract Data Type (ADT)
풀이하면, 추상 데이터 형식
자료구조의 동작 방법을 표현하는 데이터 형식 즉, 자료구조가 갖춰야 할 일련의 연산 (함수 같은...)
구현 방법은 명시하지 않는데, 자료구조의 특성들과 어떤 Operation들이 있는지 설명하는 자료구조의 한 가지 형태
list를 예로 들면, Get(접근), Append(추가), Insert(삽입), Remove(삭제) 등의 기능
(좀 어려움... 잘 이해해 볼 것)
- ADT Operation의 기본 종류 4가지
- Constructor
ADT의 새로운 인스턴스를 생성 - Transformer
어떤 인스턴스의 데이터값을 변경 - Observer
데이터값을 (변경하지 않고) 관측하기만 함 - Iterator
자료구조 내 요소들을 순차적으로 가져오게 함
- Constructor
데이터 타입의 종류
-
Simple (ex. int, float)
특히 built-in simple type은 기계어 작동 측면에서 기반하여 구현됨. -
Composite
데이터 오브젝트들을 정리하기 위함
1. 각각의 데이터가 여러 개 있어야 하며
2. 각 데이터는 접근 가능해야 함.
- UNSTRUCTURED: 컴포넌트들이 서로 관련되어 구성하지 않음. ex. classes and structs
- STRUCTURED: 개별 데이터 컴포넌트에 접근하는 데 사용되는 방법을 결정함 ex. arrays -
Address (ex. pointer, reference)
Address(Index) = BaseAddress _ Index * SizeOfElement
예시) float values[5]; (element size는 4 bytes)
Record
: Members 또는 Fields라고 불리는 여러 Data type들이 유한하게 모여 이룬 Composite Data Type
꼭 동일 Data type만 담지 않아도 됨
(C++에서는 class, C에서는 struct)
- 각각의 멤버에 접근할 땐 period .가 필요
- Implementation Level에서의 Records
- Memory cell들은 데이터를 저장하기 위해 사용되어야 함
- Base address: Record의 first cell의 메모리 주소
- Member-length-offset table: 레코드의 각 멤버들이 차지하는 메모리 주소 크기들을 정리한 테이블
1차원 배열
: 동일 데이터 타입의 element들이 상대적인 위치를 가진 채 finite, fixed size로 구성된 structured composite data type
2차원 배열
: 동일 데이터 타입 element들이 finite, fixed size로 구성된 1차원 배열이 여러 개 존재
- The first dimension: rows
- The second dimension: columns
