ADT : Subtyping 과 Inheritance

inheritance

ADTs 사이의 하위 유형 관계를 표현한다.

 

IS-A 관계

의자 : 가구의 하위 유형, 사자 : 포유류의 하위 유형, 사각형 : 다각형의 하위 유형.

 

Bag과 Stack 사이의 관계

bag은 요소들이 삽입될 수 있고, 요소들이 삭제 될 수 있는 자료 구조이다.

Stack은 요소들이 삽입될 수 있고, 요소들이 삭제 될 수 있는 자료 구조이다. (한정적으로)

Stack은 bag의 하위 유형관계이다.

c++ 코드로 표현하면 아래와 같다.

base class(기본 클래스) 'Bag', derived class(파생 클래스) 'Stack'라고 부름

 

파생 클래스는 기본 클래스의 모든 멤버를 상속 받는다. (그러나 기본 클래스의 non-private 멤버에만 접근할 수 있다. public , protected)

기본 클래스의 상속된 공개 및 보호된 멤버는 기본 클래스에서와 마찬가지로 파생 클래스에서 동일한 수준의 액세스 권한을 가집니다. 

상속된 멤버 함수들은 같은 프로토타입을 가진다. (매개변수, 타입)

기본 클래스와 파생 클래스는 구현에 차이가 있다.  그래서 오버라이드 할 수 있다.

큐 또한 Bag의 subtype이다. 큐는 bag을 FIFO로 인해 제거되는 것을 요구하기 때문에 더욱 특이하게 만든 것.

큐는 Bag의 파생클래스로 구현된다. stack 보다 더 적은 연관성을 갖고 있다. 또한 많은 operation이 재정의 되고 있다.

큐는 front, rear, 다른 구현 함수(isempty, push, pop)를 필요로 한다.

 

A Mazing Problem

이차원 배열로 구현 된다. maze[i][j], 1<= i <=m and 1<=j<=p 이다.

미로의 바깥은 1로 감싸지고 있음. 그래서 배열은 [m+2][p+2]로 구현되어짐.

이동할 때 방향과 이동거리를 구현.

미로에서 움직일 때, 최근 위치와 전 움직읨의 방향을 저장해야 함. 그리고 한가지 방향을 고른다.

추가적으로 고려할 것은, 세가지 배열 maze, mark, move 사용하는 것.

세가지의 리스트를 어떻게 구현할지 명시해야 한다.

알고리즘이 가장 최근에 입력된 트리플(x, y, dir)을 먼저 제거해야 하기 때문에, 이 리스트는 스택이어야 한다.

위 세가지 배열 maze, mark, move는 전역적이라고 가정한다.

stack은 아래와 같이 Item으로 정의 된다 

<< operator를 오버로드 (한 클래스에 동일한 이름의 두가지 함수. 매개변수가 달라야 함)한다.