Chapter 11 – 추상 자료형 Outline 11.1 소개 11.2 Ada의 추상 자료형 11.3 C++의 추상 자료형 11.1 소개 11.2 Ada의 추상 자료형 11.3 C++의 추상 자료형 11.4 Java의 추상 자료형 11.5 수학적 추상화 명세

11.1 소개 자료추상화, 자료캡슐화 추상화 자료를 연산과 함께 선언 정보 은닉 개념 도입(readability 증가) 구현종류 : class, cluster, flavor, form, modula, package, structure... 추상화 일부 속성만으로 작업/객체들을 필요한 정도만 묘사하는 방법 필수적인 속성만 표현(나머지는 숨기거나 삭제) 유사성만 표현, 차이점 삭제 관련된 사항을 묶어 하나로 표현 procedure - algorithm abstraction 연산추상화 제공(what, not how) 목적 - 추상화는 기계에서 일이 수행되는 구체적이고 상세한 것을 모르고도 컴퓨터의 수행작업을 쉽게 이해하도록 해줌

11.1 소개 자료형 자료추상화(Data abstraction) 추상 자료형(Abstract data type) 객체들의 집합 + 객체에 작용하는 연산집합 연산집합 : 실체화, 구축, 소멸, 분리 연산 자료추상화(Data abstraction) (자료형 표현 + 연산들) : 캡슐화 추상 자료형(Abstract data type)

11.1 소개 캡슐화(Encapsulation) 은닉형, 캡슐형(encapsulated type) 부적당한 사용을 배제하기 위한 보호막 창문(windows) 제공 캡슐화된 정보 사용 가능 구성 공용부(public part), 가시부(visible part) : 창문 활용 방출 전용부(private part) : 벽으로 보호 방출(export) 창문 활용한 공개 행위 도입(import) 방출된 객체를 사용할 수 있도록 연결하는 행위 사용 예) Modula, Euclid(module), Ada(package), Simula(class, 최초), CLU(cluster), ALPHARD(form)

11.1 소개 추상화 예) Queue 구조 structure queue = operations ADDQ, DELETEQ, ISEMPTYQ representation ... end rep procedure ADDQ(...) . . . end ADDQ procedure DELETEQ(...) end DELETEQ procedure ISEMPTYQ(...) end ISEMPTYQ procedure NEXT(...) end NEXT begin initialization code end end queue <queue 구조> 구성 1) 연산 이름 2) 자료형 표현 3) 연산 구현 4) 초기화 operations - 방출된 연산 : ADDQ, DELETEQ, ISEMPTYQ - 방출되지 않은 연산 : NEXT representation … end rep - 큐의 표현 정의 <queue 형 변수 선언> var x: queue

11.1 소개 완성된 queue의 정의 structure queue = operations DDQ, DELETEQ, ISEMPTYQ; representation integer array q(0:99); integer front, rear; end rep procedure NEXT(I:integer); i := (i + 1) mod 100 end NEXT; procedure ADDQ(p:queue, item:integer)； NEXT(rear) if front = rear then QUEUFULL else q(rear) := item endif end ADDQ; Procedure DELETEQ(q:queue) returns item :integer; if ISEMFTYQ(q) then QUEUEEMPTY else NEXT(front) item := q(front) endif end DELETEQ; procedure ISEMPTYQ(q：queue) returns flag : boolean; flag := front = rear end ISEMPTYQ; begin front := rear := 1 end; end queue

11.1 소개 자료 추상화 제공 시 고려 사항 자료추상화 구문 형태는 ? 영역 규칙과 생성된 객체의 생존기간은 ? 초기화 또는 최종 마무리할 코드 세그먼트 허용 여부 추상 자료형을 선언하여 여러 개의 실체 생성 여부 추상 자료형 정의에 매개 변수화 사용 여부 생성된 실체들 사이에 자료 공유 사용 여부

11.2 Ada의 추상 자료형 Ada의 단위 프로그램 종류 Package Subprogram (procedure, function) package 자료추상화 지원 task Package 구성 명세부 ① 가시부 - 자료 방출 with : 다른 package의 방출 자료 도입 use : 도입된 이름의 한정자 생략 ② 전용부 - 자료 방출 불허용 몸체부 - 연산(부프로그램) 구현 참고 명세부, 몸체부의 변수 <= own 변수 개념 (가시부의 부프로그램 호출 시 변수의 이전 값이 남아 있음)

<package BSTREES 명세 선언> 11.2 Ada의 추상 자료형 < package BSTREES 몸체부> 이진 트리 package 명세부, 몸체부 <package BSTREES 명세 선언> package body BSTREES is function HAS(I：ITEM,P：BSTREEPTR) return BOOLEAN is Q：BSTREEPTR； begin Q := P； loop if Q=null then return FALSE； elsif I < Q.DATA then Q := Q.LEFTCHILD； elsif I > Q.DATA then Q := Q.RIGHTCHILD； else return TRUE； end if； end loop； end HAS； procedure INSERT(I：ITEM,in out P：BSTREEPTR )； --프로시저 INSERT의 기술 function CBSTREE(I : ITEM) return BSTREEPTR; P : BSTREEPTR ; P := new BSTREE(I, null, null) ; return P ; end CBSTREE ; function EQUAL(P,Q：BSTREEPTR) return BOOLEAN； if P = null and Q = null then return TRUE； elsif P = null or Q = null then return FALSE； elsif P.DATA = Q.DATA then if EQUAL (P.LEFTCHILD,Q.LEFTCHILD) then return EQUAL (P.RIGHTCHILD,Q.RIGHTCHILD)； else return FALSE； end BSTREES； package BSTREES is type BSTREEPTR is private； function HAS(I：ITEM,P：BSTREEPTR) return BOOLEAN； procedure INSERT(I : ITEM,in out P：BSTREEPTR )； function EQUAL(P,Q：BSTREEPTR) return BOOLEAN； function CBSTREE(I : ITEM) return BSTREEPTR ; private type BSTREEPTR； type BSTREE is record DATA：ITEM； LEFTCHILD：BSTREESPTR； RIGHTCHILD：BSTREEPTR； end record； type BSTREEPTR is access BSTREE； end；

11.2 Ada의 추상 자료형 <BSTREES 패키지 호출> with BSTREES ; declare use BSTREES； P,Q：BSTREEPTR； begin P := CBSTREE ('A') ; INSERT('B',P)； INSERT('Z',P)； INSERT('H',P)； end；

11.2 Ada의 추상 자료형 포괄 패키지 포괄 패키지(STACK 구현) - 스택 크기와 원소형 매개변수화 연산 generic SIZE：INTEGER; type ELEM is private; package STACKS is type STACK is limited private; procedure PUSH(S：in out STACK; E：in ELEM); procedure POP(S：in out STACK; E：out ELEM); OVERFLOW, UNDERFLOW : exception; private type STACK is record SPACE：array(1 .. SIZE) of ELEM; INDEX：INTEGER range 0 .. SIZE := 0; end record; end; package body STACKS is procedure PUSH(S:in out STACK; E:in ELEM) is begin if S.INDEX = SIZE then raise OVERFLOW; endif; S.INDEX := S.INDEX + 1; S.SPACE(S.INDEX) := E; end PUSH; procedure POP(S:in out STACK; E:out ELEM) is if S.INDEX = 0 then raise UNDERFLOW; endif; E := S.SPACE(S.INDEX); S.INDEX：= S.INDEX - 1; end POP; end STACKS; 포괄 패키지(STACK 구현) - 스택 크기와 원소형 매개변수화 연산 PUSH(), POP() 예외조건 OVERFLOW, UNDERFLOW 실체화 (크기가 100인 정수형 스택 package 생성) package INTSTACK is new STACKS(SIZE =>100, ELEM=>INTEGER); 생성된 package사용 With INTSTACK declare use INTSTACK; X, Y：STACK; ... begin PUSH(X, 175); PUSH(Y, 82); POP(X, I); POP(Y, J); end;

11.3 C++의 추상 자료형 객체 지향 프로그래밍 지원 추상 자료형 지원 : 클래스(class) 제공 cf) C++의 클래스 : 자료형, Ada의 패키지, Modula-2의 모듈 : 자료형 X 클래스 개념 멤버 함수 함수의 헤더(첫번째 줄)와 몸체부(함수가 하는 일을 정의한 문장들)로 구성 클래스내에서 인라인(inline)됨 생성자 (constructor) 객체를 생성할 때 필요한 매개 변수의 제공과 초기화 기능 소멸자 (destructor) 클래스 이름 앞에 ~ 기호를 붙여서 사용 클래스 실체 소멸시 묵시적으로 호출 할당된 힙 기억 장소 해제

11.3 C++의 추상 자료형 #include <iostream.h> class stack { private : int*stack_ptr； /* 클래스 데이터 멤버(스택할당) */ int max_len； /* 클래스 데이터 멤버(스택할당) */ int top_ptr； /* 클래스 데이터 멤버(스택할당) */ public : stack( ) {stack_ptr = new int [100]； /* 힙 할당 */ max_len = 99； top_ptr = -1；} ~stack( ) {delete [ ] stack_ptr；}； void push (int number) { if (top_ptr == max_len) cout << "Error in push-stack is full\n"； else stack_ptr[++top_ptr] = number； } void pop( ) { if (top_ptr == -1) cout << "Error in pop-stack is empty\n"； else top_ptr--； int top( ) {return (stack_ptr[top_ptr])；} int empty( ) {return (top_ptr == -1)；}

11.3 C++의 추상 자료형 #include <iostream.h> template <class Type> class stack { private: Type * stack_ptr; int max_len; int top_ptr; public: stack() { stack_ptr = new Type[100]; max_len = 99; top_ptr = -1; } stack (int size) { stack_ptr = new Type[size]; max_len = size-1; top = -1; } ~stack() {delete stack_ptr;}; void push (Type number) { if (top_ptr == max_len) cout << “Error in push-stack is full\n”; else stack_ptr[++top_ptr]=number; } void pop() { if (top_ptr == -1) cout << “Error in pop-stack is empty\n”; else top_ptr--; Type top() {return (stack_ptr[top_ptr]);} int empty() {return (top_ptr == -1);}

11.4 Java의 추상 자료형 Java의 추상 자료형 C++과의 차이점 C++의 추상 자료형과 매우 유사 모든 객체들은 힙에 할당 -> 참조형 변수를 통하여 접근 Cf) C++ : 스택에 할당(멤버 데이타) 부프로그램 -> 클래스 내에서만 정의(메소드) 패키지 클래스 상위 수준에 두 번째 캡슐화 구조인 패키지가 존재 한 개 이상의 클래스 정의를 가짐 패키지 내에서 각 클래스는 다른 클래스의 부분 프렌드

11.4 Java의 추상 자료형 < 스택 클래스 예제 > import java.io.*; class Stack_class { private int [] stack_ref; private int max_len, top_index; public Stack_class() { // A Constructor stack_ref = new int [100]; max_len = 99; top_index = -1; } public void push(int number) { if (top_index == max_len) System.out.println("Error in push stack is full"); else stack_ref [++top_index] = number; } public void pop() { if (top_index == -1) System.out.println("Error in pop-stack is empty"); else --top_index; } public int top() { return (stack_ref[top_index]); } public boolean empty() { return (top_index == -1); } }

11.4 Java의 추상 자료형 < 스택 클래스 사용 예제 > public class Tst_Stack { < 스택 클래스 사용 예제 > public class Tst_Stack { public static void main(String[] args) { Stack_class myStack = new Stack_class(); myStack.push(42); myStack.push(17); System.out.println(" 17 is: " + myStack.top()); myStack.pop(); System.out.println(" 42 is: " + myStack.top()); myStack.pop(); // produces an error message }

11.5 수학적 추상화 명세 자료의 이상적인 추상화 기술 기법 자료형에 대한 일반적 형태의 정의 현존 언어에는 미 제공 구현보다 설계에 유용 새로운 언어 개발에 고무적 자료형에 대한 일반적 형태의 정의 속성(attribute)을 갖는 여러 클래스들로 구성(서로 구별) 한 클래스 : 정의하고자 하는 자료형의 객체 표현을 위한 속성들 다른 클래스들 : 이 자료형에 필요한 연산 구현을 위한 속성들 다른 객체 이용 가능 예) 스택 한 클래스 : 스택 자료형 표현(배열) 다른 클래스 : 스택 연산 구현(push, pop 등) 또 다른 클래스 - 스택 연산과 관련된 특성 기술(last in first out 등)

11.5 수학적 추상화 명세 자료 추상화 특징 수학적 명세(algebraic specification) - Guttag 강 자료형(strongly typing) 지원 객체들에 적용되는 연산들의 타당성 검증 안전한 호출보장과 비밀보장(hiding) 수학적 명세(algebraic specification) - Guttag 자료형의 일반적 형태의 정의 지원 구문 명세 - 자료형 이름, 연산, 연산의 매개 변수형 열거 의미 명세 - 연산 특성기술(대수 방정식) : 자료 표현과 독립적 제한 명세 - 연산 적용 전후의 조건들 간결성 (판독성 증가, 언어 사용 용이) 수학적 명세 사용 언어 구성 (5개의 기본 요소) 함수적 구성(function composition) 동등 관계 논리 상수(true, false) 무한개의 자유 변수 ∴새로운 자료형 정의(기본 요소 이용) 언어 확장

11.5 수학적 추상화 명세 <함수 ifthenelse() 정의> < 자료형 스택의 수학적 추상화 명세> ifthenelse(p, q, r) 의 의미 ifthenelse(true, q, r) = q ifthenelse(false, q, r) = r if p then q else r structure stack; (구문명세 ) newstack( ) → stack push(stack, item) → stack pop(stack) → stack top(stack) → item isnew(stack) → boolean declare stk：stack, i：item; (의미명세) pop(push(stk, i) = stk top(push(stk, i) = i isnew(newstack( )) = true isnew(push(stk, i) = false restrictions (제한명세) pop(newstack( )) = error top(newstack( )) = error Infix 형태

11.5 수학적 추상화 명세 < 자료형 queue의 수학적 추상화 명세> structure queue； newq( ) → queue addq(queue, item) → queue deleteq(queue) → queue frontq(queue) → item isnewq(queue) → boolean declare q, r：queue, i：item； isnewq(newq) = true isnewq(add(q, i)) = false deleteq(newq) = newq deleteq(addq(q, i)) = if isnewq(q) then newq else addq(deleteq(q) , i) frontq(addq(q, i) = if isnewq(q) then i else fromtq(q) restrictions frontq(newq) = error

슬라이드 쇼가 끝났습니다.

용 어 정리

추상 자료형 (abstract data type) 용어 국제 표준 규격 15.04.02 abstract data type (ADT) 추상자료형 A class of data structures described by a list of operations or features available in the data structures and the formal properties of these operations, with the interfaces separated from the internal implementation. 자료구조 내에서 사용 가능한 연산들 또는 특징들의 리스트와 이 연산들의 정규 특성들에 의해 기술되는 자료구조들 중의 한 부류로써, 내부적인 구현과 구분되는 인터페이스를 갖는다.

은닉형 (encapsulated type) 용어 국제 표준 규격 15.04.03 encapsulated type 은닉형 A data type with publicly defined interfaces and privately defined implementation of the internal structure and the associated operations. 공개적으로 정의된 인터페이스와, 내부구조 및 관련 연산들을 전용으로 정의한 구현을 갖는 자료형

전용부 (private part) 용어 국제 표준 규격 15.06.27 private part 전용부 That part of a package declaration that provides structural details needed by the development process but irrelevant and unaccessible to the functional users of the package. 개발 과정에서 필요하지만, 패키지의 기능을 사용하는 사람들에게는 무관하며 접근할 수 없는 구조적 세부 사항을 제공하는 패키지 선언의 한 부분

가시부 (visible part) 용어 국제 표준 규격 15.06.26 visible part 가시부 That part of a package declaration that provides details required by users of objects or services of the package. 객체의 사용자 또는 패키지의 서비스에 의해 요구되어지는 세부 사항을 제공하는 패키지 선언의 한 부분