CH 02 Data Design and Implementation

Data

Data

• 사람이나 기계가 분석할 수 있게 information을 표현해 놓은 것
• Daca Abstraction: 실제 데이터는 매우 복잡하기 때문에 추상화 필요
  • Logical: Data의 범위, Data가 가능한 연산
  • Implimentation: Data type이 프로그램에서 실제로 작동하는 모습
• Data Encapsulation
  • Data의 Implecation Level과 Logical Level을 분리하는 일
  • 데이터를 사용하는 응용 프로그램과 데이터 표현 분리
  • Information Hiding 실행

Abstract Data Type

• 기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열
• 구현자는 사용자가 사용할 때 꼭 필요한 정보만 제공
• 구현자와 사용자 구분
• 추상 자료형에 대한 구현은 외부로부터 숨겨져 정보 은닉이 이루어짐

Data Structure

Data Structure

• 개별 데이터를 저장, 검색, 사용하는 작업에 접근하는 것이 조직의 특징인 데이터들의 모음
• 추상적 데이터 유형으로 복합 데이터 구성원 구현

Features of Data Structure

• 하나하나의 Element로 쪼개짐
• Elements를 관리, 저장하는 방법에 따라 Access 방법 달라짐
• 데이터를 관리하고 저장하는 방법이 Encapsulation 됨

Data from 3 Different Levels

• Application Level (User): 특정 상황에서 실제 Data 모델링
• Logical Level (ADT)
• Implecation Level (Developer)

4 Basic Kinds of ADT Operation

• Constructor: ADT의 한 Instance 생성
• Transformer: 데이터 Element를 변경
• Observer: 변경 없이 값을 가져감
• Iterater: 연속적 데이터의 모든 요소를 훑어봄

Data Type

• Unit 기준
  • Simple Type: 쪼개면 더 이상 의미가 없어짐 (Primitive)
  • Composite Type: Simple Type이 엮어진 것
    • Unstructured: 다양한 Type끼리 (Class)
    • Structured: 같은 Type끼리 (Array)
• Define 기준
  • Built-in: Language에서 주어지는 것
  • User-define: 사용자가 새로 만드는 것

Unstructured Composite Data Type Record (Class)

Records at the Application Level

• Application Level에서 Record는 객체 표현
• 그 객체를 하나의 이름, 묶음으로 표현

Records at the Logical Level

• Composite Data 속 각각의 Single Data를 Member / Field라고 함
• Memeber의 Data Type이 Homogenous할 필요는 없음
• Operation
  • •: 멤버 선택 연산자
  • =: 구조체 할당 연산자
  • 함수의 Parameter로 사용 가능 (Deep Copy)

Records at the Implementation Level

• 데이터 저장을 위해 메모리 할당이 이루어짐

• 메모리 접근 방식의 결정

• Base Address: 저장 공간이 있을 때 Record의 첫 요소를 저장하기 시작하는 곳의 주소

• Member-length-offset-table (compile time)

  • 각 Member들의 Data Type이 Homogeneous하지 않기 때문에 필요

  • 각 Member에 할당되는 메모리 위치 표기

        class Mycar {
        int year;
        char Maker[10];
            float price;} 

    변수명	Length	Offset
    year	4	0
    Maker	10	4
    price	4	14

Structured Composite Data Type Record (Array)

One_Dimential Array at Application Level

• Array는 리스트 표현
• String: char형 Array

One-Dimential Array at Logical Level

• Binding Time: 변수, 함수 등에 코드, 클래스, 실제값이 연결되는 시점
  • Index는 Array Size - 1만큼 존재
  • Compile Time: 메모리에 Static (정적)dmfh rntjdehls epdlxj fpdldkdnt tjsxor
  • Finite, Fixed Size: 컴파일 시간에 크기가 결정돼 변경할 수 없음

    int a;
    intb[a]; // 불가능

  • 데이터의 순차적 저장 (요소끼리 상대적 위치 결정)
    • Index는 0부터 Array Size - 1까지 존재
      • 크기를 초과한 호출은 Compile Error가 아닌 Runtime Error로 발생
      • 순서가 있는 Data Type은 Index로 사용 가능

      int a[100];
      a['a'] = a;
      a['b'] = b; // 가능

    • Operation
      + Constructor
      • 값 저장
      • 함수 Parameter로 사용 (Passed by Reference) :첫 요소의 주소 전달

      f1 (int a[]) {
      }
      f2 (int *a) {
      }
      // f1과 f2 동일
      		+ Assign 불가 (Return 불가)
       ```c
       int a[3] = {0, 1, 2};
       int b[3];
       a = b; // 불가능

  One-Dimential Array at Implementation Level

• Address(Index) = Base Address + Index * Soze of Element
• Member-length-offset table 불필요
  • Array의 Element들은 Data Type이 동일하기 때문

Two-Dimential Array at Application Level

• 2차원 Array는 Table 표현에 많이 사용
• 첫 번째 차원: Rows
• 두 번째 차원: Columns
• 모든 Index는 0부터 시작

Two-Dimential Array at Implementation Level

• Row Majot Language
  • Row를 중심으로 2차원 배열을 1차원 메모리에 매핑
  • 첫 번째 Row 저장 -> 두 번째 Row 저장 -> 세 번째 Row 저장
  • Address [row][col] = Base Address + (col * row size + row) Size of Data

Object-Oriented Programming

Class

• Class는 Data Member과 Member Function으로 구성
• const: Member 값을 변경하지 못하도록 하는 Observe Operation
  • 변경 시도하면 Compile Error
• Object: Class의 한 실체, Instance
• Client: 객체를 사용하는 사람 (public만 사용 가능)
• Sending a Message: 객체들 사이의 함수를 실행시키는 것
• Class의 객체들은 독립적이며 각각의 메모리 공간 차지
• Scope Resoltion Operation (::) : 어떤 객체의 것인지 표현
• Inheritance (Is-a Relationship)
  +
  • Base Class: 상위 클래스
  • Derived Class: 하위 클래스
  • 객체들의 Reuse 용이
  • 상속이 복잡할 경우 Polymorphism (다형성, 어떤 상속을 따를 것인지 Runtime 시간에 결정)

LAB

다음 코드의 Member-length-offset Table 작성하기

typedef chat String[9];
struct StudentRecord {
    String firstName;
    String lastName;
    int id;
    float gpa;
    int currentHours;
    int totalHours;
};
StudentRecord student;
StudentRecord students[100];

변수명	Length	Offset
firstName	9	0
lastName	9	9
id	4	18
gpa	4	22
currentHours	4	26
totalHours	4	30

student의 Base Address가 100일 때 student.gpa의 주소

Address (student.gpa) = Base Address + Offset(gpa)
Address (student.gpa) = 100 + 22 = 122

students에 대해 컴파일러가 준비하는 메모리 공간

• StudentRecord 구조체 하나가 필요한 메모리 공간은 총 34 bytes
  하지만 컴퓨터는 메모리를 쭉 이어서 저장하는 것이 아니라, 접근하기 좋은 형태로 저장하는데, 이를 구조체 패딩이라고 한다
• 8bytes padding에 의해 8bytes보다 메모리가 큰 String은 탈락되고, 그 다음으로 큰 메모리 공간을 차지하는 int나 float에 맞춰 4의 배수로 메모리를 맞춰서 저장한다
• StudentRecord가 차지하는 34bytes보다 크면서 가장 가까운 4의 배수는 36이기 때문에 패딩 byte 2bytes를 할당하여 StudentRecord는 총 36bytes를 차지하게 된다
• students는 StudentRecord가 100개 있는 배열이기 때문에 36bytes * 100 = 3600bytes로 3600bytes의 메모리 공간을 차지한다