[자료구조] Ⅰ-1,2,3,4. 용어, 자료구조 분류, 데이터 추상화

** 시험: 용어 빈칸, 코드 빈칸, 구조 그리기 등의 형태

1. 용어

● 원자데이터(Atomic data): single piece of information으로 구성되어 다른 의미있는 데이터로 분해 불가 

● 복합데이터(Composite data): 의미 있는 subfield로 분해 가능한 데이터  i.e. 전화번호

● 자료형: 두 부분(data, operation)으로 구성. 

 

● 자료구조: 원자데이터와 복합데이터를 defined relationships의 집합으로 묶어놓은 것으로, 데이터를 저장하는 일련의 규칙이다. 1) 데이터를 combine 하여 2) relating rules를 정의할 수 있는 structure로 맞출 수 있다면 자료 구조를 만들었다고 할 수 있다. 이러한 자료구조들은 nested(중첩)될 수 있는데, 예를 들면 array의 경우 homogenous sequence of data를 가지고 원소들 간 인덱스들을 통해 구분하는 반면 record는 heterogeneous combination of data 를 가지고 이는 각각 identified key를 통해 구분된다. 

각각이 데이터 유형 또는 다른 데이터 구조인 요소들의 조합 결합된 요소들 간의 관계 또는 연관성(구조)의 집합

 

2. 자료 구조

● 자료 구조는 space complexity와 time complexity를 줄이며 자료를 효율적으로 저장한 방식으로, 프로그램의 목적과 기능에 따라 자료구조를 설계해야 한다. 예를 들면 폴더 구조는 트리, 파일 목록은 리스트, 사전 프로그램은 탐색과 같이 말이다.

 

 

3. 자료 구조의 분류

(1) 단순 구조: 프로그래밍에서 제공되는 기본적 데이터 타입

(2) 선형 구조: 자료들 사이 앞 뒤 관계가 1:1

(3) 비선형 구조: 자료들 사이 앞 뒤 관계가 계층 구조(Hierarchical) 혹은 망(Network) 구조

(4) 파일 구조: 보조 기억장치(i.e. 하드디스크)에 저장되는 파일에 대한 자료구조

(5) 그 외 기본이 되는 자료 구조

● 리스트: 순서가 정해진 목록    ● 스택: LIFO   ● 큐: FIFO  

● 그래프: N:M 관계  ● 트리: 계층적 구조, 부모- 자식 관계

 

4. 데이터 추상화

● 자료형: 객체와 그 객체에 대한 연산의 집합

● 추상자료형(ADT, Abstract Data Type)이란, 객체와 그 연산에 대한 명세가 객체의 표현, 연산의 구현으로부터 분리된 데이터 타입. 이는 1) Declaration of data 2) Declaration of operations 3) Encapsulation of data and operations 필요

자료 구조 이용자의 관점에서 내부 구현 소스에 대한 분석 없이 바로 자료 구조를 이용 가능하다. 정보 은닉(Information Hiding)을 통해 자료 구조를 사용할 수 있는 인터페이스만 정의하는 것.  예시 - 정수 자료형의 ADT