[자료구조] 추상 데이터 타입(ADT)

컴퓨터를 이용하여 해결하려는 문제의 특징은 일반적으로 크고 복잡하다는 것이다.

이것은 문제를 해결하는 방법과 다루어야 할 데이타가 복잡하다는 뜻이다. 다행히도 이렇게 크고 복잡한 문제에 대해 우리 인간은 추상화(abstraction)라는 방법을 사용하여 문제를 단순화 시킨 다음, 보다 쉽게 그 해결 방법을 찾아내는 능력을 가지고 있다.

 

특별히 프로그램속에 표현해야 될 대량의 그리고 복잡한 관계를 가진 데이타에 대해 먼저 이 추상화 개념을 적용하여 단순화시킨 다음 문제 해결 방법을 찾는 것을 데이타 추상화라고 한다. 데이타 추상화 과정에서는 기존의 잘 정의된 개념들을 이용하여 표현하는 것이 보통이다.

 

데이타(data)란 넓은 의미로는 프로그램의 처리 대상이 되는 모든 것을 의미한다. 특별히 데이타는 값(value)자체를 의미할 때가 많다.

 

타입(type)은 어느 한 부류에 속하는 값들의 집합을 말하는데 보통 타입 이름으로 나타낸다. 예를 들어 불리언(boolean)은 두 개의 문자 상수 true와 false로 구성되고 각각 참, 거짓을 나타낸다.

 

연산(operation)은 어떤 일을 달성하는 과정으로 보통 연산자(operator)로 표현한다.

 

데이타 타입(data type)은 타입과 연산자의 집합으로 구성된다.

즉, 데이터 집합과 이 데이타에 적용할 수 있는 연산의 집합을 말한다.

 

데이타 타입의 논리적 정의 즉, 데이타의 표현이나 연산의 구현은 제외하고 데이타와 연산의 본질에 대한 명세만 정의한 데이타 타입을 추상 데이타 타입(abstract data type:ADT)이라 한다.

 

추상화와 구체화(concrete)는 대칭되는 개념이다.

추상화와 구체화의 관점에서 데이타와 연산 간의 관계를 표현한 표.

	데이타	연산
추상화(abstract)	추상 데이타 타입(ADT)	알고리즘(algorithm)
구체화(concrete)	데이타 타입(DT)	프로그램(program)

 

 

 

자연수(Natno) 추상 데이타 타입

ADT Natno    데이타 : { i | i ∈ integer, i ≥ 0 }    연산 : for all x, y ∈ Natno              zero() ::= return 0;              isZero(x) ::= if ( x = 0 ) then return true                                     else return false;              succ(x) ::= return x+1;              pred(x) ::= return x-1;              isGreat(x, y) ::= if ( x > y ) return true                                          else return false;              add(x, y) ::= return x+y;              sub(x, y) ::= if ( x < y ) then return 0                                         else return x-y;              mult(x, y) ::= return x*y;              div(x, y) ::= return x/y;              equal(x, y) ::= if (x = y ) then return true                                         else return false;    End Natno

 

추상 데이타 타입은 데이타 값의 집합과 연산, 집합에 대한 "명세"만을 포함한다.

 

명세 방법은 선언적 명세와 절차적 명세로 구분해 볼 수 있는데, 선억적 명세는 구조를 정의하는데 적절하고, 절차적 명세는 그 의미를 정의하는제 적절하다. 명세의 표현은 주로 수학적인 식을 이용하거나 기존의 잘 정의된 개념을 이용하는 것이 보통이다.

 

Natno ADT에서 데이타 명세는 정수(integer) 데이타 타입을 이용해 정의 되었지만, 그 표현에 대해서는 언급하지도 않았고 또 언급해서도 안된다.

 

추상 데이타 타입에서는 연산의 기능이 무엇(what)이라는 것에만 중점을 두고 명세를 하는 것이지, 어떻게(how) 수행하느냐 하는 내부 구현은 명세에 포함시키지 않는다.

이것이 바로 구현에 독립적인 추상 데이타 타입 정의의 특징인 것이다.