8장: 데이터 추상화

Chapter 8: Data Abstractions 8.1 데이터 구조의 기초 8.2 관련 개념 8.3 데이터 구조의 구현 8.4 사례 연구 8.5 맞춤형 데이터 타입 8.6 클래스와 객체 8.7 기계어에서의 포인터

Inserted by Jong Joon Park(http://jongp.com) 데이터 표현 컴퓨터(computer)는 문제(problems) 풀이 도구 문제의 표현이 중요 알고리즘(프로그램)과 데이터 학교 = 교수+학생+직원+건물+시설 회사 = 사장+직원+건물+시설 자동차 = 몸체+바퀴+엔진+연료 데이터(자료)의 효율적인 표현 방법 중요 속성(크기, 색, 특징 등), 관계(주종, 계열, 소속 등), 등에 따라 검색(search)과 분류(classify), 배열 등 처리 용이 Inserted by Jong Joon Park(http://jongp.com)

8.1 기본 자료 구조(Data Structure) 배열(Array) – 같은 자료형의 모임 구조체(혹은 집합체 aggregate type) – 다른 자료형의 모임 리스트(List, 목록) 스택(Stack) : LIFO(Last In First Out) 큐(Queue) : FIFO(First In First Out), 예) 대기행렬 트리(Tree) Modified by Jong Joon Park(http://jongp.com)

자료구조의 종류(https://namu.wiki/w/자료구조 참조) 혼합 자료구조(Composite Data Structure) 배열 (Array) 선형 자료구조(Linear Data Structure) 리스트 연결 리스트 (Linked List) 추상적 자료구조(Abstract Data Structure) 스택 (Stack) 큐 (Queue) 트리 (Tree) 트라이 (Trie) 그래프 (Graph) Inserted by Jong Joon Park(http://jongp.com)

자료구조의 종류(https://ko.wikipedia.org/wiki/자료_구조 참조) 1. 구현에 따라 배열, 튜플, 연결 리스트, 환형 연결 리스트, 이중 연결 리스트, 환형 이중 연결 리스트 해시 테이블 - 개체가 해시값에 따라 인덱싱된다. 2. 형태에 따라 선형 구조 스택 큐 환형 큐 덱 비선형 구조 그래프 유향 그래프, 무향 그래프 트리 이진 트리 - 자식이 최대 두 개인 트리. 힙 Inserted by Jong Joon Park(http://jongp.com)

Modified by Jong Joon Park(http://jongp.com) 그림 8.1 리스트, 스택, 큐 목록(List) Stack Queue Modified by Jong Joon Park(http://jongp.com)

Modified by Jong Joon Park(http://jongp.com) 배열 관련 용어 배열(array): 그 안의 항목들이 모두 동일한 타입인 데이터 블록 2차원 배열: 행과 열 들로 이루어짐 int arr[5][10] 3 ~ n 차원 배열: 1, 2차원의 확장, 반복 int arr[5][10][7], dim[3][6][7][11] 인덱스(index): 각 원소의 위치(색인 번호)를 표시 arr[3][4] = 100; 3, 4가 인덱스 번호 Modified by Jong Joon Park(http://jongp.com)

구조체(집합체) 관련 용어 구조체(집합체, aggregate): 타입과 크기가 다를 수도 있는 데이터 항목들의 블록 각 항목은 필드(field)라고 불린다. 필드에 대한 접근은 이름을 통해 이루어진다.

리스트 관련 용어 리스트(list): 항목을 순차적으로 배열하는 데이터 집합 헤드(head): 리스트의 시작 테일(tail): 리스트의 끝

스택 관련 용어 스택(stack): 항목들에 대한 제거와 삽입이 헤드에서만 이루어지는 리스트 LIFO: Last-in-first-out (後入先出) 상단(top): 스택의 헤드 하단(bottom 또는 base): 스택의 테일 Pop: 스택 상단에서 항목을 제거 Push: 스택 상단에 항목을 삽입

큐 관련 용어 큐(queue): 항목들에 대한 제거는 헤드에서 일어나고 삽입은 테일에서 이루어지는 리스트 FIFO: First-in-first-out (선입선출)

그림 8.2 조직도의 예

트리 관련 용어 트리(tree): 항목들이 계층적 구성을 갖는 데이터 집합 노드(node): 트리 안의 항목 루트(root) 노드: 최상단의 노드 단말(terminal 또는 leaf node): 하단의 노드

트리 관련 용어 (계속) 부모(parent): 지정된 노드 바로 위의 노드 자식(child): 지정된 노드 바로 아래 노드 조상(ancestor): 부모, 부모의 부모, … 자손(descendent): 자식, 자식의 자식, … 형제(sibling): 공통의 부모를 갖는 노드들

트리 관련 용어 (계속) 이진 트리(binary tree): 모든 노드에서 자식의 수가 둘 이하인 트리 깊이(depth): 루트에서 단말에 이르는 가장 긴 경로상의 노드 수

그림 8.3 트리 관련 용어

8.2 관련 개념 추상화(abstraction) 정적 구조와 동적 구조 포인터(pointer) 사용자(또는 응용 소프트웨어)에게서 실제 저장장치의 세부사항들을 감춘다. 정적 구조와 동적 구조 크기와 형태가 (실행 시)변할 수 있는가? 포인터(pointer) 데이터 항목이 저장되어 있는 주소를 값으로 갖는 메모리 영역 나중에 데이터 항목에 대한 접근에 사용

그림 8.4 제목순으로 배열되어 있고 저자에 따라 링크로 연결된 소설들 그림 8.4 제목순으로 배열되어 있고 저자에 따라 링크로 연결된 소설들

Modified by Jong Joon Park(http://jongp.com) 8.3 데이터 구조의 구현 배열의 저장 특정 셀의 메모리 주소를 계산할 수 있다. 행 우선 순서와 열 우선 순서 주소 다항식 Modified by Jong Joon Park(http://jongp.com)

그림 8.5 주소 x에서 시작하여 메모리에 저장된 온도 값들의 배열

그림 8.6 네 개의 행과 다섯 개의 열을 가지며 행 우선 순서로 저장된 2차원 배열 그림 8.6 네 개의 행과 다섯 개의 열을 가지며 행 우선 순서로 저장된 2차원 배열

Modified by Jong Joon Park(http://jongp.com) 구조체(집합체)의 저장 필드들을 차례대로 연속된 셀들의 블록에 저장할 수 있다: 각 필드의 메모리 셀 주소를 계산할 수 있다. 각 필드를 별도의 장소에 저장하고 이들을 포인터로 연결할 수도 있다. struct Employee { char Name[25]; int Age; real SkillRating; } … struct Employee DistManager,SalesRep1; DistManager.Age = 26; SalesRep1.SkillRating = 3.5; Modified by Jong Joon Park(http://jongp.com)

그림 8.7 집합체 타입 Employee의 저장

리스트의 저장 연속형 리스트(contiguous list): 배열에 항목들을 저장하는 리스트 연결 리스트(linked list): 항목들이 포인터로 연결되는 리스트 헤드 포인터: 리스트의 첫 번째 항목에 대한 포인터 null 포인터: 리스트의 끝을 표시하기 위해 사용되는 정상적인 포인터가 아닌 값

그림 8.8 연속형 리스트로 메모리에 저장되어 있는 이름들 그림 8.8 연속형 리스트로 메모리에 저장되어 있는 이름들

그림 8.9 연결 리스트의 구조

그림 8.10 연결 리스트에서 항목의 삭제

그림 8.11 연결 리스트에 항목 삽입

스택과 큐의 저장 스택은 대개 연속형 리스트로 저장된다 큐는 대개 순환형 큐(Circular Queue)로 저장된다 첫 번째 항목은 마지막 항목 다음에 위치하는 것으로 간주되는 연속형 블록에 저장된다 큐가 할당된 저장 공간을 벗어나지 않게 한다.

그림 8.12 메모리상의 스택

그림 8.13 헤드 포인터와 테일 포인터를 사용한 큐의 구현 그림 8.13 헤드 포인터와 테일 포인터를 사용한 큐의 구현

그림 8.14 P에서 V까지의 문자들을 담고 있는 순환형 큐

Modified by Jong Joon Park(http://jongp.com) 2진트리의 저장 연결 구조 노드 = 데이터 셀 + 두 개의 자식 포인터 루트 노드에 대한 포인터를 통해 접근 연속형 배열 구조 A = 루트 노드 B, C = A의 자식들 D, E, F, G = B와 C의 자식들 목적 : 자료의 편집(추가, 삽입, 삭제)과 검색을 빠르게 하기 위함 Modified by Jong Joon Park(http://jongp.com)

그림 8.15 2진트리에서의 노드 구조

그림 8.16 연결 구조를 사용한 2진트리의 개념적 구조와 실제 구조 그림 8.16 연결 구조를 사용한 2진트리의 개념적 구조와 실제 구조

그림 8.17 포인터를 사용하지 않고 저장된 트리

그림 8.18 엉성하고 균형을 못 갖춘 트리의 개념적 형태와 포인터를 사용하지 않는 저장 모습 그림 8.18 엉성하고 균형을 못 갖춘 트리의 개념적 형태와 포인터를 사용하지 않는 저장 모습

데이터 구조의 조작 이상적으로는, 데이터 구조에 대한 모든 조작은 사전 정의된 함수들에 의해 이루어져야 한다. 예: 대개의 경우 리스트는 대개 새로운 항목의 삽입을 위한 insert 함수를 갖는다. 이러한 함수들을 갖춘 데이터 구조는 완전한 추상적 도구를 형성한다.

그림 8.19 연결 리스트를 인쇄하기 위한 함수 def PrintList (List): 그림 8.19 연결 리스트를 인쇄하기 위한 함수 def PrintList (List): CurrentPointer = List.Head while (CurrentPointer != None): print(CurrentPointer.Value) CurrentPointer = CurrentPointer.Next

8.4 사례 연구 문제: 검색, 인쇄, 삽입 등의 기능을 갖춘 알파벳순으로 저장된 이름들의 리스트로 이루어진 추상적 도구를 구축하라.

그림 8.20 A에서 M까지의 문자들을 위한 순서 트리

그림 8.21 연결을 사용하는 2진트리로 구현된 리스트를 위한 2진 검색 그림 8.21 연결을 사용하는 2진트리로 구현된 리스트를 위한 2진 검색 def Search (Tree, TargetValue): if (Tree == None): return None # Search failed elif (TargetValue == Tree.Value): return Tree # Search succeeded elif (TargetValue < Tree.Value): # Continue search in left subtree return Search(Tree.Left, TargetValue) elif (TargetValue > Tree.Value): # Continue search in right subtree return Search(Tree.Right, TargetValue)

그림 8.22 그림 8.21의 함수로 문자 J를 검색할 때 고려되는 서브트리들

그림 8.23 검색 트리를 알파벳순으로 인쇄하기

그림 8.24 2진트리 안의 데이터를 인쇄하기 위한 함수 def PrintTree (Tree): 그림 8.24 2진트리 안의 데이터를 인쇄하기 위한 함수 def PrintTree (Tree): if (Tree != None): PrintTree(Tree.Left) print(Tree.Value) PrintTree(Tree.Right)

그림 8.25 트리로 저장된 리스트 B, E, G, H, J, K, N, P에 항목 M을 삽입하기

그림 8.26 2진트리로 저장된 리스트에 새로운 항목을 삽입하기 위한 함수 그림 8.26 2진트리로 저장된 리스트에 새로운 항목을 삽입하기 위한 함수 def Insert(Tree, NewValue): if (Tree == None): # Create a new leaf with NewValue Tree = TreeNode() Tree.Value = NewValue elif (NewValue < Tree.Value): # Insert NewValue into the left subtree Tree.Left = Insert(Tree.Left, NewValue) elif (NewValue > Tree.Value): # Insert NewValue into the right subtree Tree.Right = Insert(Tree.Right, NewValue) else: # Make no change return Tree

8.5 맞춤형 데이터 타입 사용자 정의 데이터 타입 새로운 타입 정의를 위해 집합체 구조 사용 – C 언어 예: 8.5 맞춤형 데이터 타입 사용자 정의 데이터 타입 새로운 타입 정의를 위해 집합체 구조 사용 – C 언어 예: struct EmployeeType { char Name[25]; int Age; real SkillRating; } 변수 정의에 새로운 타입 사용: struct EmployeeType DistManager, SalesRep1;

Modified by Jong Joon Park(http://jongp.com) 추상 데이터 타입 데이터(표현)와 함수(동작) 모두를 포함할 수 있는 사용자정의 데이터 타입 예: interface StackType { // 각 메소드 몸체는 implements로 구현, 그림 8.27 참조 public int pop(); public int push(int item); public boolean isEmpty(); public boolean isFull(); } … int main() { StackType StackOne, StackTwo; StackOne.push(25); Modified by Jong Joon Park(http://jongp.com)

Modified by Jong Joon Park(http://jongp.com) 8.6 클래스와 객체 클래스 : 추상 데이터 자료형의 기술(description) 추가 기능을 갖는 추상 데이터 타입 특성들에 대한 상속이 가능하다 새로운 객체를 초기화하기 위한 생성자가 존재한다 내용에 대한 캡슐화가 가능하다 Modified by Jong Joon Park(http://jongp.com)

Modified by Jong Joon Park(http://jongp.com) [6.5 객체지향 프로그래밍 참조] 객체와 클래스 객체(object): 데이터와 프로시저(메소드)를 포함하는 능동적 프로그램 단위 클래스(class): 객체 구성(생성)에 사용되는 틀(template) 인스턴스(instance): 클래스(틀)로부터 생성된 객체 Modified by Jong Joon Park(http://jongp.com)

그림 8.27 Java나 C#로 구현된 정수 스택 class StackOfIntegers implements StackType { private int[] StackEntries = new int[20]; private int StackPointer = 0;  public void push(int NewEntry) { if (StackPointer < 20) StackEntries[StackPointer++] = NewEntry; }  public int pop() { if (StackPointer > 0) return StackEntries[--StackPointer]; else return 0; } public boolean isEmpty() { return (StackPointer == 0); public boolean isFull() { return (StackPointer >= MAX);  

8.7 기계어에서의 포인터 즉석 주소지정 방식(immediate addressing): 명령 자체에 데이터를 포함한다. 직접 주소지정 방식(direct addressing): 명령 안에 데이터의 주소를 포함한다. 간접 주소지정 방식(indirect addressing): 명령 안에 데이터의 주소가 들어있는 위치를 포함한다.

그림 8.28 포인터를 이용할 수 있도록 부록 C의 기계어를 확장하려는 첫 번째 시도

그림 8.29 레지스터에 저장된 포인터가 가리키는 메모리 셀의 내용을 레지스터에 넣기 그림 8.29 레지스터에 저장된 포인터가 가리키는 메모리 셀의 내용을 레지스터에 넣기