자료구조 (3) 데이터 디자인과 구현

Data design and Implementation

1. 데이터 디자인

1) 자료의 추상화

- 자료의 구현에서 자료 형식의 논리적인 특징을 분리하는 방법

- Logical properties: 흐름도가 만들어져있고, 흐름도를 코드와 유사한 형태로 표현

- Implementation: 실제 코드를 구현하는 부분

 

2) 자료의 캡슐화

- 의사코드로 작성이 되어있는 부분을 문법적으로 채워넣는 것

- 논리 레벨에서 데이터를 사용하는 것으로부터 데이터의 표현을 분리하는 행위

- 코드 작성은 사람이 사용하는 언어와 가까운 형태로 기술을 하면 내부적으로는 컴퓨터가 다룰 수 있는 언어로 바뀌게 된다. 따라서 코드를 작성하는 우리는 컴퓨터가 어떤 식으로 저장되어있는지를 모두 알 필요는 없다. 이는 캡슐화덕분이다.

- int 데이터 타입은 다음과 같은 다양한 내용들이 포함되어있다. 

 

3) Abstract Data Type(ADT)

- 추상화 자료형으로 구현과의 의존성이 없이 데이터의 특징을 정의하는 것을 의미한다.

- 이는 캡슐화된 데이터나 객체의 가용한 모든 값의 집합과 데이터 생성과 유지를 위해 제공되어야할 연산의 명세를 모두 가지고 있다.

- 데이터의 특징으로는 영역과 연산이 있다.

 

(1) ADT operations의 네 가지 기본 연산(크게 중요하지는 않음)

- 생성자(constructor): ADT의 새로운 인스턴스(객체)를 생성

- 번역자(Transfomer): 인스턴스 내의 하나 이상의 데이터 값의 상태를 변경

- 관찰자(Observer): 인스턴스 내의 하데이터 값의 상태 변경없이 관찰하는 것을 허용

- 반복자(Iterator): 데이터 구조의 모든 요소들을 순서대로 연산하는 것을 허용

 

 

2. 자료구조

- 각 자료 요소(Component element)들을 저장하고 회수하는데 사용되는 접근 연산들로 인해 특정지어지는 자료 요소들의 모음 // 접근과 컴포넌트들의 모음 두 가지가 핵심적이다.

- 자료 요소들은 컴포넌트에서 분해될 수 있다.

- 요소들의 배치는 각 요소들이 어떻게 접근되는지를 나타내는 구조적인 특징이다. ex) 배열, 링크드 리스트

- 접근 연산과 자료 요소들의 모음이라는 두 가지의 특징을 더한 것이다.

 

1) Data from 3 different levels

(1) 응용 레벨

실세계에서 사용되는 자료 레벨

---

- 이 단계에서 다음 단계로 넘어가기 위해선 가공이 필요하다.

ex1) A도시부터 B도시까지의 최단 거리 구하기

ex2) 의회 도서관, 경희대학교 도서관

 

(2) 논리 레벨

자료의 범위와 연산의 추상적인 관점

---

- 응용 레벨의 자료를 정제하는 과정이 있다.

- 무엇을 다룰 것인지에 초점을 맞춘다.

ex1) 최단경로를 만들기위한 도로의 연결정도 파악, 도로의 노후화 사용 x 등 데이터의 취사선택 등을 함

ex2) 범위는 책의 모음, 동작은 책의 대출, 반납, 예약 등을 포함

 

(3) 구현 레벨

자료를 저장하기 위한 구조의 표현명세 및 연산을 위한 코딩

---

- 어떻게 자료를 구현할 것인지에 초점을 맞춘다.

ex2) 책을 나타내는 구조의 표현 및 동작을 위한 코딩

 

 

2) 복합 데이터 유형

- 개별 데이터 요소들의 집합을 하나의 변수 이름으로 저장하여 사용하는 데이터를 말한다.

- 개별 데이터 요소에 대한 접근을 허용해야한다.

- 구성요소들 간의 데이터 타입과 관련된 연관관계로 Unstructured / Structured를 나눌 수 있다.

 

(1) Unstructured

- 객체에 특성을 표현하기 위한 데이터들의 모음이지만 데이터 타입들 간의 연관관계가 성립되지 않는다.

ex) 클래스, 구조체, Union

cf) 관용적으로 멤버함수가 거의 없는 경우 구조체를 사용하고 멤버 함수가 많이 있으면 클래스를 사용함

 

(2) Structured

- 데이터 요소들 간에 연관 관계가 존재함

ex) 배열

cf) void pointer를 사용하면 배열에서도 unstructured처럼 사용할 수 있음

 

 

(3) C++ built-in data types

- array, struct, union, class가 composite(복합 자료형)에 해당한다.

 

(4) 레코드

- 멤버 혹은 필드라 불리우는 불균일한 데이터 요소들로 구성된 복합 자료형

 

(5) 구조체 멤버 접근 방법

- '.'을 사용하거나 '->'을 사용할 수 있음

 

cf) call by value vs call by reference vs call by pointer

i) call by value

- 내부에 지역변수를 따로 만듦

- 전달받은 외부의 값을 바꿀 수 없음

 

ii) call by reference

- 내부에 지역변수를 따로 만들지 않음

 

iii) call by pointer

- 내부에 지역변수를 포인터 형태로 만듦

 

 

3) 배열

(1) 배열의 특징 

- 1차원 배열은 한정적이고 고정된 크기를 가지고 있기에 런타임에는 결정되지 않는다.

 

cf) 기본적으로는 배열을 선언할 때 크기를 명시하지만 크기를 명시하지 않는 경우가 존재함

i) 파라미터 리스트에 상위차원의 인덱스에 대해서는 크기를 명시하지 않아도 됨

ex) void func(int ary[])

ii) 배열을 선언과 동시에 집합을 넣어서 초기화하는 경우에는 배열의 크기를 명시하지 않아도 됨

ex) int ary{1, 2, 3, 4}

 

- 배열은 인덱스를 통한 접근이 가능하다. 이는 랜덤액세스가 가능하다고 한다.

- 반면 리스트는 앞에 있는 내용에 접근을 해야지만 뒤에 있는 내용에 접근이 가능하다는 특징이 있다.

- 모든 구성요소가 같은 타입인 동일한 요소들의 집합인 복합 자료형이다.

- 접근 기능은 값의 인덱스로 주어진다.

- 주소(인덱스) = 기준주소 + 인덱스 + 요소의 크기

- 배열 선언을 할 때는 상수로 크기를 저장해야한다.(숫자, const 변수 등)

 

(2) C++에서의 1차원 배열

- 인덱스는 정수로 나타낼 수 있는 타입이어야만 한다. cf) 인덱스를 통해 검색이 가능한 대부분의 자료형이 이러하다.

- 인덱스의 범위는 항상 0에서부터 [배열의 크기 - 1]까지임

- 배열은 대입될 수 없으며, 함수의 반환 유형이 될 수 없다.

- 컴파일러에서 배열의 이름은 첫번째 엘리먼트의 주소값을 저장하는 포인터 상수로 인식하기에 주소가 고정된다. 이에 따라 배열을 대입하고자 하면 상수에 대입을 하는 것이 되기에 에러가 발생한다. 또한 함수의 리턴으로 들어갈수도 없다.

- 배열의 랜덤 인덱싱을 할 때는 각 데이터 타입만큼 바이트를 옮겨가며 자료를 검색할 수 있다.

 

(3) C++에서의 2차원 배열

- 메모리 상에서 행 순서로 저장되어야하는지, 열 순서로 저장되어야하는지 정해야한다. C++은 행우선이다.

- 인덱싱을 통해 접근이 가능해야하기에 행이 몇 개 인지, 혹은 열이 몇 개인지 저장된 방법에 따라 이를 파악해야지 컴퓨터 내부적으로 연산을 통한 인덱싱이 가능하다.

 

(4) 매개변수로써 배열 전달

-  함수를 호출할 때마다 지역변수르 만들어 배열의 값을 모두 복사하는 경우 메모리 사용량이나 오버헤드가 발생하는 경우가 많기 때문에 C++에서 배열은 항상 참조로 전달되며, 참조연산자(&)는 매개변수 형태의 형식에 사용되지 않는다.

- 참조형태로 전달이되는 경우에는 의도치 않은 배열 값의 변경이 발생할 수 있기에 const 접두어를 매개변수 형식과 함수의 프로토콜에서 사용하는 경우가 많다.

 

(5) typedef를 활용한 배열 사용

- 함수에서 형식상 매개변수와 실제 매개변수의 크기가 일치하지 않는 상황을 효과적으로 해결할 수 있다.

i) 실제 매개변수: 함수 호출 시 실제로 인자로 넣어주는 변수를 의미한다.

ii) 형식 매개변수: 함수 선언 시 매개변수로 정의한 변수를 의미한다.

- 일종의 코딩 스타일임

 

4) 클래스

(1) 클래스 개념

- 클래스는 데이터를 조작하는 기능(멤버 함수)을 사용하여 고정된 수의 데이터 구성요소(데이터 멤버)로 캡슐화하는 비정형데이터 구조이다.

- 클래스 형태의 변수는 해당 클래스의 객체(인스턴스)이다.

- 클래스의 객체를 선언하고 사용하는 소프트웨어는 클라이언트다.

- 클라이인트 코드는 클래스 객체를 처리하기 위해 공개 멤버 함수(OOP에서 호출되는 메소드)를 사용

- 메세지를 보내는 것은 공용 멤버 함수를 호출하는 것을 의미한다.

 

(2) 같은 형태의 객체와 멤버 함수

- 멤버 선택 연산자(.)를 통해 데이터 멤버나 멤버 함수를 선택한다.

- iostream, fstream 헤더파일은 istream, ostream, ifstream, ofstream과 같은 입출력 클래스를 선언한다.

- cin과 cout은 이미 정의되어 제공되는 클래스 객체이며, get과 ignore와 같은 멤버함수를 가진다. (console in, console out)

 

(3) 정보 은닉

- 사용자의 입장에서 구현 내역을 감추는 것을 의미한다.

- 객체 간의 인터페이스를 제공하는 역할을 하기도 한다.

 

cf) 이름공간에 정의된 멤버에 접근하는 세가지 방법

- namespace는 이름공간의 남용을 방지하기 위해서 범위 결정 연산자를 사용해 특정 변수와 함수에 접근할 수 있도록 한다.

 

i) 각 참조에 대해 자격 습득: mySpace::name

모든 참조에 대해 mySpace::name을 사용한다.

 

ii) 선언: using mySpace::name

앞으로 계속해서 참조될 mySpace::name을 선언하여 사용한다.

 

iii) 지시: using namespapce mySpace

자격의 습득 없이 mySpace의 모든 멤버들을 참조할 수 있게 하여 사용한다.