[C언어로 쉽게 풀어쓴 자료구조] 1.2 추상 자료형

자료구조 복습

 

교재 : c언어로 쉽게 풀어쓴 자료구조 (개정 3판) - 청인국, 공용해, 하상호 지음

 

 

1.2 추상 자료형

 

추상 자료형

 

자료형 (data type) : 데이터의 종류. 우리말로 자료형

자료형의 예 :

• 기초적인 자료형 : 정수, 실수, 문자형 등
• 이외 : 스택, 큐, 리스트, 트리 등

 

C언어에서 제공하는 자료형 : 

• 정수 (ex. 0, 1, 2, ...)
• 실수 (ex. 3.14)
• 문자 (ex. 'a', 'b', ...)
• 배열 ( 동일한 자료형이 여러 개 모인 것 )
• 구조체 ( 다른 자료형이 여러 개 모인 것 )

자료형
기초 자료형	파생 자료형	사용자 정의 자료형
char	배열	구조체
int	포인터	공용체
float		열거형
double

 

자료형을 작성할 때는 실행 가능한 연산에 대해서도 신경 써야 함.

데이터의 종류가 결정되면 그 데이터와 관련된 연산도 달라짐.

 

 

int 자료형의 예 : 

• 데이터 : {-INT_MIN, ..., -2, -1, 0, 1, 2, ..., INT_MAX }
• 연산 : +, -, *, /, %, ==, >, <

 

INT_MIN은 컴퓨터로 나타낼 수 있는 가장 작은 정수, INT_MAX는 컴퓨터가 나타낼 수 있는 가장 큰 수를 의미.

연산 (operation)은 정수 간의 덧셈, 뺄셈, 곱셈, 나눗셈, 나머지 연산이 있음.

2개의 정수가 같은 값인지를 검사하는 == 연산자, <, > 연산자도 추가할 수 있음. 

 

 

이제부터 자료형이라고 하면 데이터뿐만 아니라 데이터 간에 가능한 연산도 고려해야 함.

복잡한 자료형을 구현할 때는 연산이 연산자가 아니라 함수 (function) 로 작성됨.

 

 

추상 자료형 (ADT: abstract data type) : 

추상적, 수학적으로 자료형을 정의한 것.

실제적인 구현으로부터 분리되어 정의된 자료형.

자료구조는 추상 자료형을 프로그래밍 언어로 구현한 것이라 할 수 있음.

데이터나 연산이 무엇(what)인지는 정의되지만 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않음.

연산을 정의하는 추상적인 의사 코드는 주어질 수 있음.

 

예 : 

Nat_Number

객체 : 0에서 시작하여 INT_MAX까지의 순서화된 정수의 부분범위
함수 : 

    Nat_Number zero()			::= 0
    Nat_Number successor(x)		::= if( x==INT_MAX) return x
    					    		else return x+1
    Boolean is_zero(x)			::= if (x) return FALSE
    					    		else return TRUE
    Boolean equal(x, y)			::= if( x==y ) return TRUE
    					    		else FALSE
    Nat_Number add(x,y)			::= if ( (x+y) <= INT_MAX )
    					    		return x+y
                               	else return INT_MAX
    Nat_Number sub(x,y)			::= if (x<y) return 0
    					    		else return x-y;

ADT 이름부터 시작.

ADT 안에는 객체(objects)와 함수(functions)들이 정의됨.

객체는 주로 집합의 개념을 사용하여 정의.

이후 함수들이 정의.

함수는 연산을 의미.

함수의 이름, 함수의 매개변수, 함수의 반환형, 함수가 수행하는 기능의 기술 등이 포함.

'::_' 기호는 '~으로 정의된다'를 의미.

 

 

ADT가 구현될 때 보통 구현세부사항은 외부에 알리지 않고 외부와의 인터페이스만을 공개하게 됨.

ADT의 사용자는 구현세부사항이 아닌 인터페이스만 사용하기 때문에 추상 자료형의 구현 방법은 언제든지 안전하게 변경될 수 있음.

인터페이스만 정확하게 지켜진다면 ADT가 여러 가지 방법으로 구현될 수 있음.

이것이 정보은닉의 기본개념.

즉 전체 프로그램을 변경가능성이 있는 구현의 세부사항으로부터 보호하는 것.

구현으로부터의 명세의 분리가 ADT의 중심 아이디어.

프로그래밍 언어에 따라 ADT는 여러 가지 방법으로 구현됨. (ex. 객체지햐언어 - 클래스)

 

 

TV와 추상 자료형의 유사성 : 

TV

• TV의 인터페이스가 제공하는 특정한 작업만을 할 수 있다.
• 사용자는 이러한 작업들을 이해해야 한다. 즉 TV를 시청하기 위해서는 무엇을 해야 하는지를 알아야 한다.
• 사용자는 TV의 내부를 볼 수 없다.
• TV의 내부에서 무엇이 일어나고 있는지를 몰라도 이용할 수 있다.
• 누군가가 TV의 내부의 기계장치를 교환한다고 하더라도 인터페이스만 바뀌지 않는 한 그대로 사용이 가능하다.

추상 자료형 (ADT)

• 사용자들은 ADT가 제공하는 연산만을 사용할 수 있다.
• 사용자들은 ADT가 제공하는 연산들을 사용하는 방법을 알아야 한다.
• 사용자들은 ADT 내부의 데이터를 접근할 수 없다. 
• 사용자들은 ADT가 어떻게 구현되는지 모르더라도 ADT를 사용할 수 있다.
• 만약 다른 사람이 ADT의 구현을 변경하더라도 인터페이스가 변경되지 않으면 사용자들은 여전히 ADT를 같은 방식으로 사용할 수 있다.

 

Quiz

01. 자료형은 객체(object)와 이 객체간의  연산  (operation) 의 집합으로 정의된다.

02.   추상  자료형 (abstract data type)은 객체와 연산들의 명세가 구현으로부터 분리된 자료형을 말한다.

03 Nat_no 추상 자료형에 is_greater(x, y) 연산을 추가하여 보자.

    Nat_Number is_greater(x,y)		::= if (x>y) return TRUE
    					    			else return FALSE