[자료구조] L02.Data Design and Implementation

• toc {:toc}

Data Design

• 데이터(Data) : 정보를 컴퓨터가 처리할 수 있도록 가공한 것

• 데이터는 프로그래밍 세계에서의 명사이다.

  • 조작될 수 있는 객체, 처리될 수 있는 정보이다.

• Data Abstraction : 데이터의 구현으로부터 데이터 타입의 논리적인 속성의 분리

• Logical Property : What을 의미한다. 가능한 값이 무엇인지, 필요한 연산이 무엇인지

• Implementation : How를 의미한다. C++에서 어떻게 구현할 것인지, 어떻게 사용될 것인지

• Data Encapsulation : 데이터를 사용하는 프로그램으로부터 데이터의 표현을 분리

• Low-level에서 이진수로의 표현을 캡슐화하여 high-level로 표현한다.

• ADT(Abstract Data Type)

• 속성(범위와 연산)이 명시된 데이터 타입이다.

• 특정 구현 방식과 독립적으로 통틀어서 데이터 타입을 명시하는 개념적인 것을 의미한다.

Data Structure

• 자료구조(Data Structure) : 개별 데이터 요소를 저장하고 되찾는 연산을 할 수 있는 특징이 있는 데이터 요소의 모음

• ADT 개념을 바탕으로 실제 구현을 통해 만들어진다.

• Features of Data Structures

  • 구성 요소들로 분해될 수 있다.
  • 요소의 구성은 요소에 접근에 대해 영향을 준다.
  • 요소의 구성과 요소의 접근 방식은 둘 다 캡슐화될 수 있다.

• Data from 3 different levels

  • Application level : 실제 데이터를 모델링한다.
  • Logical level : 범위와 연산에 대해 추상적인 개념을 갖는다.
  • Implementation level : 구체적으로 어떻게 데이터를 지니는 구조를 표현하고 연산을 만들 것인지를 정의한다.

• Basic ADT Operation

  • Constructor : ADT의 새로운 인스턴트 객체를 만든다.
  • Transformer : 인스턴스의 데이터 값을 바꾸거나 추가한다.
  • Observer : 인스턴스의 데이터를 변화하는 것 없이 데이터를 볼 수 있도록 한다.
  • Iterator : 데이터의 모든 구성요소를 순차적으로 접근할 수 있도록 한다.

• Built-in type(int, float)의 경우 machine-level 연산의 관점에 맞게 구현되었다.

Composite Data Type

• Composite Data Type

• 하나의 변수 이름으로 개별 데이터 요소의 모음을 저장한 구조

• 개별 데이터 요소에 접근 가능

  • Unstructed(Custom) : class와 struct 같이 미리 구성되어 있지 않은 구조
  • Structed(Built-in) : array와 같이 개별 데이터 요소에 접근하는 방법을 미리 구성해놓은 구조

• C++ Built-In Data Types

  • Simple
    • Integral
      • char
      • short
      • int
      • long
      • enum
    • Floating
      • float
      • double
      • long double
  • Composite
    • array
    • struct
    • union
    • class
  • Address
    • pointer
    • reference

Records

• Records at the Logical Level

• Record(Class, Struct) : 유한한 데이터 모음, 다른 타입으로 구성된 unstructed composite data type 이다.

• Member selection operator (period .) : record type 변수의 멤버에 접근하기 위한 식별자이다.

  • ex) myCar.year

• Records at the Application Level

  • 객체를 만드는 것에 유용하다.
    • 객체에 대한 다양한 타입의 데이터를 모아둘 수 있다.
    • 전체 객체를 하나의 이름으로 참조할 수 있다.
    • 객체의 다양한 멤버들을 참조할 수 있다.
  • 다른 프로그래머가 정의한 자료 구조를 정의하는 것에 유용하다.

• Records at the Implementation Level

  • 구현을 하려면 데이터에 대한 메모리 셀 예약이 필요하다.
  • 접근 함수가 정해져야 한다.
  • Base address는 메모리 첫 번째 셀의 주소로 정해진다.
  • 멤버에 접근하기 위해 필요한 메모리 위치를 포함한 member-length-offset table을 가진다.

One-Dimensional Array

• One-Dimensional Array at the Logical Level

• Array : 유한한 크기, 동일한 데이터 타입으로 구성된 structed composite data type이다.

• 요소들은 상대적인 위치를 가지고 있어 직접적인 접근이 가능하다.

• Array의 연산 및 작동은 선언과 인덱스를 활용하여 수행된다.

• Implementation Level

• Index = BaseAddress + Index * SizeOfElement

• 동일한 데이터 타입, 자료형을 갖기 때문에 요소 하나의 자료형 크기를 곱해주면 인덱스의 위치를 설정할 수 있다.

• 인덱스는 반드시 integral type(char, short, int, long, enum)이어야 한다.

• 인덱스는 항상 0부터 시작한다.

• 배열 자체를 함수의 파라미터로 주거나 반환값으로 받을 수 없다.

  • 이를 위해 포인터를 사용한다.

Two-Dimensional Array

• Two-Dimensional Array at the Logical Level

• Array와 동일하나, 두 차원이 정렬된 상태이다.

• Array 연산 및 작동은 선언과 인덱스의 쌍(행, 열)을 통해 수행된다.

• 메모리 상에서 two-dimensional array는 각 열을 쌓아 놓은 것처럼 구성된다.

C++ class data type

• Class : 유한한 데이터 요소와 함수를 캡슐화한 unstructed composite type이다.

• 클래스 타입의 변수들은 특정 클래스의 객체 혹은 인스턴스라고 말한다.

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

• 클라이언트 코드는 클래스 객체들을 다루는 public member function을 사용한다.

• Sending a message는 public member function을 호출하는 것을 의미한다.

• Scope Resolution Operator (::)

• C++ 프로그램은 다양한 클래스 타입을 사용하기 때문에 다양한 클래스 안에 있는 멤버 함수의 이름이 동일한 경우가 생길 수 있다.

• Member selection operator(.)이 해당 클래스의 멤버 함수 호출을 결정하는데 사용된다.

• Implementation 파일에서는 클래스를 명시하기 위해 멤버 함수의 이름 앞에 scope resolution operator가 사용된다.

Object-Oriented Programming

• 3가지 공통 구조 : class, object, inheritance

• 객체는 객체 지향 시스템에서 기본적인 런타임

• 클래스는 객체의 구조를 정의한다.

• 클래스는 상속에 의해 정의된 하위 관계로 구성된다.

• Inheritance(상속) : 존재하는 클래스를 전문화한 새로운 클래스를 만들 수 있게 한다.

• 새로운 클래스는 파생 클래스, 자식 클래스라 부르고, 존재하는 클래스는 기본 클래스, 부모 클래스라고 부른다.

• 상속을 통해 이미 검증된 클래스를 재사용할 수 있고, 필요로 하는 속성을 파생 클래스와 공유할 수 있다.

• Polymorphism(다형성) : 상속 계층에서 메소드 이름을 복제하고 메소드가 적용된 객체를 위해 적합한 메소드를 적용하는 것을 말한다.

• Overloading : 하나의 클래스 내에서 같은 이름의 메소드를 여러 개 중복하여 정의한다.

• Overriding : 같은 이름의 메소드를 각 클래스의 맥락에 맞게 재정의하여 사용한다.

• Exception

• 예외 사항은 프로그램이 실행될 때 발생하는 비정상적인 상황이다.

• 예외 사항 관리

  • 오류 조건을 정의한다.
  • 가능한 오류를 포함하는 코드를 작성한다.(try)
  • 오류가 발생했다면 시스템에 알린다.(throw)
  • 시스템에 오류가 발생했다는 신호가 들어온다면 오류를 처리한다.(catch)