윤성우의 열혈 자료구조를 읽고 복습한 내용입니다.

추상 자료형: Abstract Data Type

'추상 자료형'에 대한 이해 없이 자료구조를 공부해서는 안된다.

자료구조에서의 추상 자료형

지갑에 대한 '추상 자료형'을 얘기해보자.

• 카드의 삽입
• 카드의 추출
• 동전의 삽입
• 동전의 추출
• 지폐의 삽입
• 지폐의 추출

위에는 지갑의 기능들이 나열되어있다. 하지만 이 기능이 어떠헌 과정을 거쳐서 완성되는지는 언급하지 않고 있다. 예를 들어 동전의 삽입은 다음의 과정을 거친다.

"지갑을 열고 동전 주머니를 찾아서 동전 주머니의 지퍼를 내린다. 그리고 동전 주머니에 동전을 넣는다. 이어서 동전 주머니의 지퍼를 올린 다음 마지막으로 지갑을 닫는다."

이렇듯 '구체적인 기능의 완성과정은 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것'을 가리켜 '추상 자료형' 또는 간단히 ADT라고 한다.

ADT에 대한 설명은 이렇게 끝을 내도 되지만, 추상 자료형이라는 이름 때문에 자료형과 관련해서 생각해 볼 필요가 있다.

구조체를 이용해서 지폐와 동전의 저장이 가능한 지갑을 정의해보자.

typedef struct _wallet // 동전 및 지폐 일부만을 대상으로 표현한 지갑
{
	int coin100Num; // 100원짜리 동전의 수
    int bill5000Num; // 5,000원짜리 지폐의 수
}

이렇게 C언어 기반으로 구조체를 정의했다면, 다음과 같이 이야기할 수 있다.

"구조체를 기반으로 지갑을 의미하는 Wallet이라는 자료형을 정의했습니다."

하지만 컴퓨터 공학적 측면에서 위의 구조체 정의만으로 Wallet이라는 자료형의 정의가 완성되는 것은 아니다. Wallet을 기반으로 하는 연산의 종류를 결정하는 것도 자료형 정의의 일부로 보아야 하고, 이러한 연산의 종류가 결정되었을 때 자료형의 정의는 완성이 된다. 여기서 말하는 연산은 Wallet을 기반으로 제공할 수 있는 기능 관련 연산을 의미한다. 예를 들면 다음의 것들과 같다.

• 돈은 꺼내는 연산: int TakeOutMoney(Wallet * pw, int coinNum, int billNum);
• 돈은 넣는 연산: void PutMoney(Wallet * pw, int coinNum, int billNum);

이렇게 C언어에서는 구조체에서 필요로 하는 연산을 함수를 이용해 정의한다. 위의 두 연산이 Wallet과 관련이 있는 연산의 전부라면, 이 둘이 더해져 Wallet에 대한 자료형의 정의가 완성된다.

결론은 '자료형'의 정의에 '기능' 혹은 '연산'과 관련된 내용을 명시할 수 있다는 것이다. 따라서 추상 자료형이라고 하더라도 그것에 기능 혹은 연산과 관련된 내용을 명시할 수 있는 것이다.

구조체 Wallet의 추상 자료형 정의

구조체 Wallet도 자료구조의 일종이다. 이는 지갑이라는 데이터를 표현한 결과이기 때문이다.

추상 자료형에 대해 다시 정리하면, "구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것"이다. 그럼 이어서 자료구조 Wallet의 ADT를 살펴보자.

Wallet의 ADT

Operation:

• int TakeOutMoney(Wallet * pw, int coinNum, int billNum)
  첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.
  두 번째 인자로 꺼낼 동전의 수, 세 번째 인자로 꺼낼 지폐의 수를 전달한다.
  꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.
• void PutMoney(Wallet * pw, int coinNum, int billNum)
  첫 번째 인자로 전달된 주소의 지갑에 돈을 넣는다.
  두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달한다.
  넣은 만큼 동전과 지폐의 수가 증가한다.

이 추상 자료형을 보고 구조체 Wallet의 정의도 ADT에 포함시켜야 하는 것이 아닌가 의문이 들 수도 있다. 물론 필요하다면 포함시켜도 좋고, 중요한 정보라면 무엇이든 추가할 수 있지만, 불필요한 것을 포함시키는 것은 바람직하지 못하다.

Wallet을 기반으로 돈을 넣고 꺼내는데 있어서, 구조체 Wallet의 멤버가 어떻게 구성이 되어 있는지를 알 필요는 없다. 따라서 위의 경우 구조체 Wallet의 정의를 ADT에 포함시키는 것은 바람직하지 못하다.

동전이나 지폐가 몇 개씩 있는지 확인하기 위해 Wallet의 멤버에 대해서 알아야하지 않겠냐고 생각할 수도 있다. 우리가 동전의 수를 확인해야 한다면, 그에 관련된 연산을 위의 ADT에 추가하는 것이 옳은 생각이다. 우리는 구조체의 멤버에 직접 접근하는 것에 익숙한데, 이 방법이 늘 옳은 것인지는 고민해봐야 한다.

우리가 C언어의 파일 입출력을 공부하면서 우리는 FILE 구조체의 내부를 궁금해하지 않는다. FILE 구조체의 내부를 몰라도 파일과 관련된 모든 연산을 처리할 수 있기 때문이다. 사실 FILE 구조체의 내부에 대한 궁금증은 불필요한 것이다.