[자료구조] Chapter 1. Software, Data Structure, and C++

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

 

Abstract Data Type(ADT)

• data와 operations를 구체적인 구현 방법 없이 명기한 data type
• 같은 ADT가 언어에 따라서 다른 형태를 가질 수 있음, but key operations는 같음

 

Data Structure Definition

• Data Structure는 shape만을 의미하지 않는다.
• Data Structure는 data elements의 더 효율적인 수정과 접근을 허용한다.
• 결집, 관리, 저장 방식을 정의한다.
• Data Structure: 개별적인 data elements를 저장하고 계산하기 위해 사용되는 operations에 접근함으로써, 결집이 특성화된 data elements의 collection

 

- Features

• 구성 요소로 분해됨
• elements의 배치는 각 element가 접근되는 방법에 영향을 미침
• 배치와 접근되는 방법은 캡슐화된다.

 

- Information Hiding 

• public interfaces/methods를 통한 접근만 허용
• encapsulation과 유사

 

Data 

• processed된 information
• 조작되는 objects

 

- Data Abstraction

• data type의 logical properties와 implementation을 분리

Logical Properties

• 가능한 value - student ID, name, birth, ...
• 필요한 operation - add, delete, update

Implementation

• 어떤 data type이 사용될 수 있을까? - string, int, float, ...
• operation이 어떻게 동작하는가? - void add() {...}, ...

 

Composite Data Type

• 독립적인 data components의 collection을 하나의 variable name에 저장하는 data type
• arrays(structured), class(unstructured), struct(unstructured)

 

- Class/Struct

• Class, Struct는 non-homogeneous(동종이 아닌) elements를 포함 -> members / fields
• "." -> member selection operator
• Class/Struct can be used for
  • same type variable에 assignment 가능
  • function에 parameter로서 전달 가능
  • function의 return value 역할 가능

 

- One-Dimensional Array 

One-Dimensional Array (Logical)

• finite(유한한), fixed-size(고정된 크기), homogeneous(동종의) elements로 구성된 composite(복합) data type이다.
• element는 relative position을 가짐 -> 모든 element는 indexes를 사용하여 immediately direct access 가능

One-Dimensional Array (Implementation)

• Address[index] = Base Address + Index * SizeOfElement
• Base Address: first element의 memory에서의 위치 주소

 

 

 

- Two-Dimensional Array 

Two-Dimensional Array (Logical)

• finite(유한한), fixed-size(고정된 크기), homogeneous(동종의) elements
• element는 relative position을 가짐 -> 모든 element는 indexes를 사용하여 immediately direct access 가능
• 2차원으로 나눠짐
• a pair of indexes -> row and column

Two-Dimensional Array (Implementation)

• In memory, C++은 two-dimensional array를 linear structure 형태로 저장

 

• intArray[5][12]에서, intArray[3][7]의 주소는? -> base address(2000) + (12 * 4) * 3 + 7 * 4 -> 2172
• Address[row][col] = BaseAddress + row * [# of column] * SizeOfElement + column * SizeOfElement

Memory Allocation

- Computer Architecture

1. OS에 프로그램 실행 명령
2. HDD에 저장된 program(instructions set)을 memory로 이동
3. memory에 저장된 instructions를 CPU에서 하나하나 execute

 

- Memory Allocation - Variables

• program 실행 -> OS는 자동으로 프로그램 실행에 필요한 memroy를 할당 -> instructions and data

 

- Memory Allocation - Object

• Object 생성 -> members를 위한 memory space가 할당됨