데이터 추상화 정리

8.1 기본 데이터 구조

 

※ 배열

 

 - 동질성 배열(homogeneous array) : 항목들이 모두 동일한 타입으로 이루어진 데이터 블록

 

 - 이질성 배열(heterogeneous array) : 유형이 다를 수도 있는 데이터 항목들의 블록 - 구성요소(component) : 이 블록들의 항목

 

※ 리스트(list) : 순차적으로 배열되어 있는 항목들의 집합

 

 - 헤드(head) : 순차적으로 배열되어 있는 항목들의 집합

 

 - 테일(tail) : 리스트의 다른 쪽 끝

 

 - 스택(stack) : 헤드에서만 항목들을 제거하거나 삽입할 수 있는 리스트의 한 유형

 

 - 상단(top) : 일상적 표현에 따라 스택의 헤드를 스택의 상단이라고 함

 

 - 하단(bottom) : 스택의 테일

 

 - LIFO(Last in, First out) : 스택에서 제거되는 항목은 항상 마지막으로 스택에 추가된 항목이며 이러한 특성을 LIFO라 부름

 

 - 백트래킹(backtracking) : 시스템에 진입하는 것과 반대 방향으로 시스템에서 빠져나오는 과정을 지칭

 - 큐(queue) : 항목에 대한 제거는 헤드에서만 이루어지며, 새로운 항목의 추가는 테일에서만 이루어지는 리스트

 

 - FIFO(First in, First out) : 저장되는 순서대로 제거됨

 

※ 트리(tree) 

 

 - 노드(node) : 트리상의 각 위치

 

 - 루트노드(root node) : 최상단의 노드

 

 - 단말노드(terminal node) : 루트의 반대쪽 끝에 있는 노드들

 

 - 깊이(depth) : 루트노드에서 단말노드에 이르는 최장 경로에 있는 노드의 개수를 트리의 깊이라함

 

 - 자식(child) : 어떤 노드의 바로 아래의 자손들

 

 - 부모(parent) : 바로 위의 조상들 노드

 

 - 형제(sibling) : 동일한 부모를 갖는 노드들

 

 - 이진트리(binary tree) : 각 부모노드가 둘 이하의 자식을 갖는 트리

 

 - 서브트리(subtree) : 임의의 노드 하나를 선택하면, 그 노드와 그 아래의 노드들이 트리 구조를 갖는데, 이러한 작은 트리를 서브트리(subtree)라고 부름

 

 - 가지(branch) : 각 서브트리는 그 부모노드로 부터 가지라고 부른다

연습문제

 

2) 리스트, 스택, 큐 사이의 차이를 요약하라

    - 스택과 큐는 특별한 유형의 리스트로 볼 수 있다. 일반 리스트의 경우 어느 위치에서나 항목을 삽입, 또는 제거할 수 있다. 스택의 경우 헤드에서만 항목을 삽입 또는 제거할 수 있다. 큐의 경우 테일에서만 항목을 삽입할 수 있고, 헤드에서만 항목을 제거할 수 있다

 

8.3 데이터 구조의 구현

 

※ 동질성배열(homegeneous array) 

 

행 우선 순서(row major order) : 배열의 첫 행의 값들을 잡아둔 브록의 첫 번째 셀에서 시작하여 연속된 메모리 셀들을 저장한 다음, 그 다음 행을 그 뒤에 저장하며, 또 그 다음 행들로 계속 진행할 것이다. 이런 저장 방식에 대해 행 우선 순서라고 말한다.

 

주소다항식(address polynomial) : 행 위치와 열 위치에 대한 참조를 실제 메모리 주소로 변환하기 위해 공식을 얻을 수 있는데  이를 주소 다항식이라고 부른다.

 

※ 리스트의 저장

연속형리스트(contiguous list) : 전체리스트가 하나의 큰 메모리 블록에 저장되며, 연속된 항목들은 인접한 메모리 셀에 차례대로 저장된다. 

 

 - 정적인 리스트를 구현하기 위한 편리한 저장구조이지만, 여러 항목들이 이동해야 하는 동적리스트의 경우에는 불리하다.

 

연결리스트(linked list) : 리스트 전체를 하나의 연속된 큰 블록에 저장하는 대신 리스트상의 개별 항목들을 각기 다른 메모리 영역에 저장한다. 그리고 각 개별항목에게 연결방식을 사용한다.

 

헤드포인터(head pointer): 연결 리스트의 시작위치를 나타내기 위한 첫번째 항목

 

NIL포인터 : 리스트에 더이상 항목이 없다는 것을 표시하기 위해 마지막 항목의 포인터 셀에 들어가는 특별한 비트 패턴

 

※ 스택과 큐의 저장

스택 : 가장 큰 상태의 스택을 수용하기에 충분한 메모리 블록을 잡아둔다.

 

스택 포인터(stack pointer) : 스택 상단의 위치는 잡아둔 메모리 셀 블록 내에서 앞뒤로 이동하게 된다. 이 위치를 나타내기 위해 그 주소가 스택 포인터라고 불리는 메모리 셀에 저장된다

 

큐 : 스택의 경우에 사용되었던 한 개의 셀 대신 두 개의 메모리 셀을 포인터로 사용하기 위해 잡아둔다.

 

헤드 포인터(head pointer) : 큐의 헤드를 나타내기 위해 사용

 

테일 포인터(tail pointer) : 큐의 테일을 나타내기 위해 사용

 

 - 항목을 큐에 삽입할 때마다 테일 포인터가 가리키는 곳에 저장되며, 테일 포인터는 사용되지 않고 있던 다음 위치를 가리키기 위해 조정된다.

 

순환형 큐(circular queue) : 큐의 문제점은 큐가 메모리에서 빙하처럼 움직인다는 것 - 따라서 큐가 정해진 메모리 블록을 벗어나지 않게 만들 메커니즘이 필요함. 큐의 테일이 블록의 끝에 도달했을 때 추가 항목들을 다시 블록의 앞에서 부터 채워나감. 마찬가지로 큐의 헤드가 블록의 마지막 항목이고 이 항목이 제거될 경우, 헤드 포인터는 다시 블록의 시작 부분을 가리키도록 조정됨 

 

※ 이진트리의 저장

기본 연결리스트와 유사하지만 두개의 요소로 이루어지는 연결리스트와 달리 노드라고 불리는 이진트리의 각 항목은 데이터, 노드의 첫번째 자식에 대한 포인터, 노드의 두 버내 자식에 대한 포인터 등의 세개의 요소로 이루어짐

 

왼쪽 자식 포인터(left child pointer) : 첫 번째 포인터를 지칭

 

오른쪽 자식 포인터(right child pointer) : 다른 포인터를 지칭

 

메모리에 트리를 저장하기 위해서는 노드들을 저장하기 위한 메모리 셀 블록을 찾는 일과 원하는 트리 구조에 따라 노드들을 연결하는 일이 필요

 

루트포인터(root pointer) 끝으로 루트 노드의 주소를 저장하는 특별한 위치인 루트 포인터를 위한 장소를 잡는다 - 트리에 접근하기 위해 사용되는 것이 바로 루트포인터

 

연결 구조를 사용하여 이진트리를 저장하는 대신 전체 트리를 하나의 연속된 메모리 셀 블록을 사용하여 저장할 수 도 있음.트리의 루트 노드를 첫번째 셀에 저장하고 일반적으로 n번 셀에 들어가는 노드의 왼쪽 자식과 오른쪽 자식을 각각 2n번 셀과 2n+1셀에 저장한다. 블록 안에서 트리가 사용하지 않는 위치를 나타내는 셀들은 데이터가 들어있지 않음을 나타내는 특별한 비트 패턴으로 표시한다.

 

 - 이 방식에서는 임의의 노드에 대해 부모나 형제를 찾을 수 있는 효율적인 방법을 제공함. 이진트리가 거의 균형을 갖추고 있고 거의 가득차 있을 경우 저장공간을 효율적으로 사용할 수 있음. 하지만 이러한 특성을 갖추지 못해을 경우 상당히 비효율 적일 수 있음.

 

 

8.5 맞춤형 데이터 타입

 

사용자정의 데이터타입(user-defined data type) : 오늘날의 많은 프로그래밍 언어들은 프로그래머가 프리미티브 타입을 기초 요소로 사용하여 추가적인 데이터 타입을 정의할 수 있도록 허용함. 이렇게 정의되는 데이터 타입 중 가장 기본 적인 형태는 사용자정의 데이터 타입이며 이것은 기본적으로 여러 개의 프리미티브 타입을 하나의 이름으로 모은 것이다.

인스턴스(instance) : 사용자정의 데이터 타입의 실제 항목을 그 타입의 인스턴스라고 부른다.

추상 데이터 타입(abstract data type) : 연산에 대한 정의를 포함하는 사용자 정의 데이터 타입

연습문제

 

1. 데이터타입과 그 타입의 인스턴스 사이의 차이는 무엇인가?

    - 타입은 틀에 해당한다. 그 타입의 인스턴스는 그 틀에서 만들어진 실제 객체에 해당한다

 

2. 사용자정의 데이터 타입과 추상 데이터 타입 사이의 차이는 무엇인가?

    - 사용자 정의 데이터 타입은 데이터 구성에 관한 기술인 반면, 추상 데이터 타입은 데이터 조작을 위한 연산을 포함한다.

8.6 클래스와 객체

 

1) 클래스는 추상 데이터 타입의 확장에 해당함

 

2) 객체지향 언어에서 클래스는 다른 클래스에서 속성들을 상속 받을 수 있음

 

3) 또한 생성되는 개별 객체들을 설정하는 생성자라는 이름의 특별한 메쏘들을 포함할 수 있음

 

4) 클래스는 여러 수준의 캡슐화를 통해 인스턴스의 내부속성을 잘못 사용하지 않도록 보호하는 기능도 존재함.

 

5) 또한 클래스는 연관된 프로시저들을 모으기 위한 수단으로 사용될 수 있음

연습문제

 

1) 추상 데이터 타입과 클래스 사이의 유사점들은 무엇인가? 차이점들은 무엇인가?

    - 추상 데이터 타입과 클래스 둘 다 타입 인스턴스 생성에 사용될 수 있는 틀이다. 그러나 클래스가 상속 기능도 갖추고 있고 프로시저만 포함할 수 도 있다는 점에서 더 일반적이라고 할 수 있다

 

2) 클래스와 객체의 차이는 무엇인가

    - 클래스는 객체 생성에 사용할 수 있는  틀이다.

8.7 기계어에서의 포인터

 

즉석 주소지정 방식(immediate addressing) : 피연산자 필드는 관련 데이터 자체를 포함한다.

 

직접 주소지정 방식(direct addressing) : 피연산자 필드는 관련 데이터가 있는 곳의 주소를 포함한다.

 

간접 주소지정 방식(indirect addressing) : 피연산자 필드는 데이터가 있는 곳의 주소가 있는 곳의 주소를 포함한다.