[Data Structure] 자료구조와 추상 자료형

Data Structure

컴퓨터에서 자료를 효율적으로 관리하고 구조화시키는 방법

<자료구조의 정의>

자료구조는 추상자료객체들의 집합, Object와 이 객체집합에 대한 처리연산들의 집합, Operation이다.

이 때 추상자료객체는 처리해야 할 현실세계의 자료 객체들을 논리적으로 추상화한 것을 의미한다.

 

예를 들어 int 형의 자료구조 정의는 다음과 같다.

int = <intObj, intOp>
intObj = {0, ±1, ±2, ... | 각 정수는 소수점을 포함하지 않음}
intOp = {+, -, *, /, %, ++, --, ...}

---

Abstract Data Type (추상 자료형)

정수(integer), 실수(real number), 문자(character)와 같은 기본 자료형은 일반적으로 많이 사용되는 기본적인 자료구조들을 미리 효율적인 방법으로 구현해서 제공한 것이다. 한편 프로그래밍 언어에서 기본적으로 제공하지 않는 자료형의 기능을 논리적으로 추상화하여 정의한 자료형을 ADT, 추상 자료형이라고 한다. 추상 자료형은 기능을 구체적으로 구현하지 않고 데이터의 형태(Object)와 연산자의 특성(Operations)을 정의한다. 이 때 연산자는 추상 자료형과 외부를 연결하는 인터페이스 역할을 한다.

프로그래밍 언어의 관점에서 보면, 자료구조는 기본으로 제공하는 자료형 이외에 추가적으로 정의할 수 있는 추상 자료형을 개발하고 효율적인 구현을 도모하는 것으로 이해할 수 있다.

 

추상 자료형은 최근 객체 지향 언어에 큰 영향을 주었다.
추상 자료형은 프로그래밍 언어에 따라 여러 방법으로 구현되는데, C언어에서는 구조체(struct), C++과 Java에서는 클래스(class)를 사용하여 추상 자료형을 구현한다.

 

ex) Natural_Number

Object: integers between 0 and INT_MAX
Operation:
    zero() ::= return 0;
    is_zero() ::= if (x = 0) return TRUE;
                   else return FALSE;
    add(x, y) ::= if((x + y) <= INT_MAX ) return x + y;
                   else return INT_MAX
    sub(x, y) ::= if (x, y) return 0;
                   else return x-y;
    equal(x,y) ::= if(x = y) return TRUE;
                   else return FALSE;
    successor(x) ::= if((x + y) <= INT_MAX )
                   return x+1;