Chapter 1: Software, Data Structure, and C++

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

What is abstraction?

▶ Too abstract.

▶ Too concrete(명확한).

▶ Between too abstract and too concrete.

Abstraction

A model of a complex system that includes only the details essential to the perspective of the viewer of the system.

 

Programs are abstractions.

Tells what the program mus do, but not how the program does it.

Abstraction Data Type (ADT)

▶ ADT

 

A data type whose properties (data and operations) are specified independently(상관없이) of any particular implementation.

Example

<list> in Python

▶ Python code

• Data: values in the list
• Operations: append() and remove()

Have you ever wondered about Python's internal implementation?

 

Python <list> implementation (in C)

▶ <list> initialization (temp_list = [])

▶ <list> append (temp_list.append(1))

 

<list> remove (temp_list.remove(1)): too long codes..

Do we have to know this?

No! We don't have to.

 

Why?

• We already know what append() / remove() do.
• That's enough. We don't have to know how they do.

이게 바로 추상화이다.

Information Hiding

The practice of hiding the details of a module to control access to the details from the rest of the system.

It only allows access through public interfaces/methods.

Similar to encapsulation.

 

※ public / private

• public: 클래스를 사용해 오브젝트(인스턴스)를 만들었을 때, 오브젝트 내에 있는 변수에 외부에서 접근 가능
• private: 클래스를 사용해 오브젝트(인스턴스)를 만들었을 때, 오브젝트 내에 있는 변수에 외부에서 접근 불가능

Modifying the List

▶ <list> provides a lot of methods/interfaces (operations).

 

We can use them to modify (add/delete) items in lists.

We CANNOT directly modify **ob_item to update lists.

 

이처럼 어떤 변수가 private으로 존재할 때 외부에서 직접 접근하는 게 힘들기 때문에,

어떤 public한 함수들을 만들어 변수를 조작하거나 확인하는 것이 Information Hiding 개념이다.

Comparing Lists

Python 2 <list> vs Python 3 <list>

C++ <list> vs Python 3 <list>

Java <list> vs Python 3 <list>

 

Implementation details may be different.

The number of provided operations can be different.

However, all of them provide the same key operations.

 

언어별로 조금씩의 차이가 있더라도 전부 다 list라는 Abstract Data Type (ADT)에 속한다.

 

Same abstract data types (ADT) can be implemented in many different ways.

 

Data Abstraction

Data

In the programming world, data are:

• The information that is processed.
• The objects that are manipulated. (OOP, Object-Oriented Programming)

Data Abstraction

Separation of a data type's logical properties from its implementation.

 

Logical Properties (abstract)

• What are the possible values? (e.g., student ID, name, birth)
• What operations will be needed? (e.g., add, delete, update)

Implementation (concrete)

• What data types can be used? (e.g., string, int, float)
• How can this be done? (e.g., void add(){....})

Even though we do not understand the binary computations performed by the machine,

we still can use those operations in the program.

Data Structure

Why we Use C++?

ADT's data and operation can be easily implemented using class/objects.

• Data: Member variables
• Operations: Member functions (methods)

Data Structure

A collection of data elements whose organization is characterized by accessing operations that are used to store and retrieve(찾다) the individual data elements (recall librarian example).

 

Features:

• They are decomposed into their component elements(구성 요소) (book).
• The arrangement of the elements definess how each element is accessed.
• Both the arrangement and the way they are accessed can be encapsulated.

※ 캡슐화 = 숨김 + 제어된 접근

Composite Data Type

A composite data type is a type that stores a collection of individual data components under one variable name.

It allows the individual data components to be accessed.

 

Examples:

• Arrays (structured, 구조화된)
• Class (unstructured)
• Struct (unstructured)

※ composite: 복합이라는 의미는 여러 개의 데이터를 묶는다는 뜻이지, 반드시 다른 타입을 묶는다는 의미는 아니다.

 

※ 특정한 데이터 타입을 지정해서 만들어야 하는 것을 structured라고 한다.

• int로 array를 만들면 float은 들어갈 수 없고 int만 들어갈 수 있다.

Class/Struct

Class and Struct can contain non-homogeneous(동종이 아닌) elements called members or fields (char[], float, int).

▶ Class

 

Period(온점) "." is the member selection operator.

It is used between the variable name (of object) and the member identifier to access individual members.

 

Class and Struct can be used for:

• assignment to another variable of same type

• passing as a parameter to a function (either by value or by reference)

• returning as the value of a function

Memory Allocation

Computer Architecture

▶ Computer Architecture

• CPU: Central Processing Unit, 컴퓨터의 뇌 역할을 하는 애로 모든 계산을 담당하여 연산이 일어나는 곳
• Storage: 실제로 프로그램과 데이터가 보관되는 곳 (Nonvolitile)
  • HDD: Hard Disk Drive (테이프가 돌아가는 방식)
  • SSD: Solid State Drive (USB처럼 전기적으로 데이터를 보관하는 방식)
• (Main) Memory: 프로그램이 실행되는 곳 (Volitile)
• Program: 여러 가지 데이터와 명령어들의 집합
  • Operating System도 Program임

▶ 컴퓨터에서 프로그램이 실행되는 과정

 

메모리는 기본적으로 스토리지에 비해서 작은데,

얘가 감당할 수 없을 정도로 너무 많은 프로그램들을 동시에 키면, 즉 메모리에 때려 넣으면 죽어버린다.

 

※ 컴퓨터는 가상 메모리 시스템을 이용해 실제 물리적 메모리보단 더 많은 메모리를 사용할 수 있다.

 

※ 사용자가 인지하지 못하는 상태에서 돌아가고 있는 많은 형태의 백그라운드 프로그램들이 존재한다.

Memory Allocation

프로그램을 시행할 경우에 운영체제는 스토리지에서 프로그램을 찾아 메모리에 올리게 되는데,

이렇게 프로그램을 메모리 올리는 과정을 메모리 할당이라고 한다.

 

Variables

▶ Memory Allocation - Variables

 

When the program executes, the operating system automatically allocates the memory required to run the program (instructions and data).

 

이렇게, 실제로 프로그램에서 사용되는 모든 변수들은 메모리라는 공간에 할당이 이루어지게 된다.

 

Object

▶ Memory Allocation - Object

 

When the object is created, the memory space for members is allocated.

 

※ Object: 클래스를 가지고 만들어진 하나의 자료 구조체이다.

▶ 프로그램에서 정의해 놓은 모든 변수들은 위와 같이 메모리에 올라와서 처리가 된다.

One-Dimensional Array 

Logical

One-dimensional array is a structured composite data type made up of a finite and fixed-size collection of homogeneous elements.

 

Elements have relative positions to which there is direct access.

(= any element can be accessed immediately) using indexes.

 

array는 선언할 때 array의 크기를 함께 선언해 주어야 한다.

▶ Char Name[10]

 

Implementation

Address[index] = BaseAddress + Index * SizeOfElement

Base Address: the location in memory of the first element

▶ Example

 

array도 변수이기 때문에, 마찬가지로 메모리라는 공간에 할당이 이루어진다.

Two-Dimensional Array 

Logical

Two-dimensional array is a structured composite data type made up of a finite and fixed-size collection of homogeneous elements.

 

It is ordered in two dimensions and elements have relative positions to which there is direct access.

 

Array operations (creation, storing a value, etc.) are performed using a declaration(선언) and a pair of indexes (called row and column).

▶ int intArray[3][5]

 

Implementation

In memory, C++ stores arrays in row order (linear structure).

 

Address[row][col] = BaseAddress + row * NumCols * SizeOfElement + column * SizeOfElement

▶ Example