자료구조 정리 for 중간고사

나중에 예쁘게 정리할게.. *^^

---

1. Software Engineering Principle

Software Engineering

: 컴퓨터 프로그램의 설계, 생산 및 유지 관리에 대한 규율화된 접근 방식

제 때, 비용 추정치 내에서 개발. product의 크기와 복잡성을 관리할 때 적절한 tool을 사용한다.

 

알고리즘이란?

: 한정된 시간 내에 계산될 수 있는 주어진 문제에 대한 완전한 해결책을 설명하는 이산적 단계의 논리적 순서

 

추상화(Abstraction)

: 시스템 뷰어의 관점에 필수적인 세부 정보만 포함하는 시스템의 모델

• Information Hiding

: 시스템의 나머지 부분으로부터 세부 정보에 대한 엑세스를 제어하기 위해서,

모듈의 세부 정보를 숨기는 작업

 

절차적 VS 객체지향 코드

“ 절차적 코드 뒤에 있으면 동사에 밑줄을 치고, 객체 지향 코드 프로그램을 지향하면 명사에 밑줄을 그어라

• Functional Decomposition : 기능 모듈을 코딩할 수 있을 때까지 문제를 쉽게 처리하는 하위 작업으로 나눈다.

• Object-Oriented Design : 문제해결을 위해 함께 사용할 수 있는 데이터와 작업으로 구성된 개체를 식별.

 

Verification(검증) VS Validation(확인)

“Are we doing the job right?”(우리가 일을 올바르게 하고 있는가?) - 검증

“Are we doing the right job?”(우리가 올바른 일을 하고 있는가?) - 확인

 

Errors

• 종류 : Specification(사양) / Design / Coding / Input

오류를 발견하는 시점이 빠르면 빠를수록, 오류에 따른 비용은 줄어든다.

• Controlling Errors

Robustness

: 오류가 발생한 후에도 해당 환경 내에서 프로그램을 복구하여 계속 운영할 수 있는 기능

Preconditions

: 작업, 기능에 진입할 때 참이어야 하는 가정

Postconditions

: 전제 조건이 참이라고 가정하고, 연산/함수가 종료될 때 예상 결과를 설명하는 문장

 

 

 

2. Data Design & Implementation

Data

: 사람이나 기계가 분석할 수 있도록 적합한 방식으로 정보를 표현한 것

객체 지향 관점 – 객체, 프로젝트 관점 – information

Simple – 기본 구현이 기게 수준 작동 측면에서 정의된 추상화

/ Composite type – 개별 데이터 구성요소의 집합을 하나의 변수 이름으로 저장, 각각에 access할지 정의

Built-In / User-define

 

ADT (Abstract Data Type) => 사용자가 코딩하기 쉬워진다.

: Data는 복잡하므로,

Application level(응용 프로그램)과 Logical level(논리적 수준)에서의 Data를 구분하여 구현

사용자 입장에서 불필요한 부분 -> Information Hiding

 

구현과 독립적으로 만들어진 properties.

어떻게 구현하는지는 관심을 두지 않는다

 

Data Structure란?

: collection of data를 어떻게 저장하고, 꺼내고, 가공할 것인가?

• 특징

그들의 elements로 decomposed 가능하다

자료구조에 따라서 접근 방식이 달라진다

elements의 배열과 접근 방식 모두 캡슐화(encapsulated) 가능하다.

 

Data의 3가지 Level

① Application (or user) level : 특정 Context에서 실제 데이터를 모델링

②의 Data를 사용, 자신의 문제에 따라서 활용한다.

② Logical (or ADT) level : 도메인 및 operation에 대한 추상적 표현 (What)

③을 추상화한 것.

③ Implementation level : 기계에서 데이터를 보관할 구체적인 표현 (HOW)

새로운 DataType를 개발하는 개발자는 ②, ③를 본다.--(자료구조->ADT)-->가져다 쓰는 사용자는 ①, ②를 본다.

① Application level	미국 의회 도서관
② Logical (or ADT) level	domain은 책의 모음. 작업에는 책 대출, 책 체크인, 책 예약 등이 포함
③ Implementation level	“books”를 보관하는 구조의 표현과 운영을 위한 코딩

 

ADT Operations

Constructor

Transformer

Observer

Iterator

 

Composite Data Type의 2가지 형식

• Unstructured

: 구성요소는 서로에 대해 구성되어 있지 않다.

classes, structs <- 프로그래밍 입장에서 record라는 표현

• Structured

: 개별 데이터 구성요소에 엑세스하는데 사용하는 방법을 결정

arrays

 

Logical Level 관점에서 Records

: not necessarily homogeneous인 composite DataType = record

record 안에 있는 데이터를 member/field 라고 부른다.

• struct CarType

not homogeneous

CarType thisCar -> CarType이라는 구조체의 하나의 인스턴스가 메모리에 만들어진다.

member selection operation(.) <- 멤버 하나하나에 접근할 방법

• class data type

fixed number of data components

객체는 assignment 가능

member selection operation(.) <- 멤버 하나하나에 접근할 방법

scope resolution operation(::) <- 어떤 객체의 것이다

객체를 만들 때, 객체를 선언하는 것과 Implementation Level③에서 어떻게 구현되는지 구분

 

Application Level① 관점에서 Records

: 여러 특성을 가진 객체를 모델링하기에 유용하다.

데이터(객체)를 모아서 하나의 이름으로 표현하겠다. -> 편해짐

 

Implementation Level③ 관점에서 Records

Base address : 데이터를 저장하는 첫 번째 주소

Member-length-offset table

 

Logical Level② 관점에서 Array

: homogeneous

데이터를 순차적으로 저장하므로 상대적인 위치가 존재한다.

크기는 컴파일할 때 결정되어야 한다.

assign이 안되기 때문에 return type도 안된다.

 

Implementation Level③ 관점에서 Array

: 2차원 배열 -> 2차원을 1차원으로 mapping한다.

 

객체 지향 언어 <= Inheritance & Polymorphism

-> 서로 다른 응용프로그램에서 재사용할 수 있는 유용한 클래스 계층 구조를 만들 수 있다.

class는 객체의 구조를 정의한다.

Object는 기본 런타임 독립체이다.

상속에 의해 정의된 “is-a”계층으로 구성된다. - 추상화(형식이나 클래스와 같은) 사이의 포함 관계

 

 

3. ADTs Unsorted List & Sorted List

Linear relationship

: 첫 번째 요소를 제외한 각 요소에는 고유한 선행 요소가 있고, 마지막 요소를 제외한 각 요소에는 고유한 후속 요소가 있다.

 

Unsorted List : 리스트 선행 및 후속 관계가 데이터 요소간의 유일한 관계.

데이터 항목이 특별한 순서로 배치되지 않았다.

 

Generic Data Type

: Data type이 무엇이던지 동작하게끔 해준다.

 

Class Constructor Rules

return value는 없다 / constructor가 여러개인 것이 가능하며, parameter로 구분한다.

/ 생성자 매개변수는 클래스의 개체 선언의 매개변수 목록에 배치된다. / 매개 변수가 없는 생성자는 기본 생성자이다. / 클래스에 하나 이상의 생성자가 있고 클래스 개체 배열이 선언된 경우,

생성자 중 하나가 배열의 각요소에 대해 호출되는 기본 생성자여야 한다

 

RetrieveItem에서 ItemType item을 왜 &로 넘겼을까?

: 구현할 때 ItemType이 너무 커서, 복사하여 넘겨주는데 너무 많은 시간이 들까봐.

 

Sorted List : 정렬이 되어 있다.

 

Big-O 비교방식

<- 어느 알고리즘이 더 좋은가?에 대해서 이 프로그램이 수행하면서 몇번 실행되는가 기준

 

 

4-1. ADTs Stack

 

스택이란 쌓여있는 것.

바닥에서부터 위로 쌓고, 위에서부터 빼낼 수 있다. => LIFO(Last In, First Out)

 

Class Template

• 클래스가 형식 매개변수를 사용하여 여러 버전의 class 유형을 생성할 수 있다

형식 매개변수(Formal parameter)는 클래스 템플릿 정의에 나타나고,

실제 매개변수(Actual parameter)는 클라이언트 코드에 나타남.<>

template<class ItemType> <- formal parameter list

 

• class template을 만들 때는 .h와 .cpp를 같은 파일에 두거나, .h가 .cpp파일을 포함해야 한다.

(왜?) C계열 언어의 컴파일러 동작 방식 때문

: 연속적이나, 서로 독립적 동작 방식 => 장점

1. #을 제거하여 이것이 없는 cpp파일을 만듬

2. cpp 컴파일러 작동하여 .obj파일을 만듬. (어느 라이브러리에 작동하려는 기능이 구현되어 있다)

3. link가 .exe파일을 만든다. 작동. <- main이 무조건 하나는 있어야 묶어서 실행할 수 있다.

 

 

컴파일러가 템플릿이라는 틀로부터 자료형의 class를 만들어낸다.

따라서 템플릿 정의와 operation 정의가 하나의 파일로 되어 있어야지만 컴파일러가 인식 가능

 

- Pointer 변수

• 주소를 저장하기 위한 변수

ex) int* ptr;

ptr = &x;

std::cout << *ptr; -> 얘가 가르키는 값에 가서, 거기에 있는 값을 출력하세요

• NULL Pointer

: NULL != memory address가 0,

pointer가 아무것도 가리키지 않게 allow한다.

 

- 메모리 할당

• static : 메모리 바인딩이 Complie time에 이루어진다. 한 번 정하면 바뀌지 않는다.

• dynamic : 메모리 바인딩이 Run time에 이루어지며, 계속 바뀔 수 있다.

 

- Program Data의 3가지 Lifetime

• Static Data : 프로그램의 시작 시점 ~ 프로그램의 끝

• Automatic Data : 함수 실행 시점 ~ 함수 끝

• Dynamic Data : new operation 실행 ~ delete operation 실행 – 변수 이름을 가지지 않는다.

(new : heap 영역 메모리가 사용 가능할 때,

연산자 new는 요청된 객체/array를 할당하고, 할당된 메모리에 포인터를 반환

int*p = new int를 하면, p는 지역변수이므로 스택에 있다.(선언된 함수가 끝나면 메모리 할당 끝)

그런데 heap영역에서 이름 없는 메모리가 할당, 해당 주소가 p에 저장된다.

4-2. ADTs Queue

 

큐란 계산대에 줄 서 있는 사람들! Front와 Rear가 존재하는.. => FIFO(First In, First Out)

 

선형 큐는 First와 rear가 계속 증가만 하게 되어, 언젠가는 배열의 끝에 도달한다.

앞부분이 비어있더라도 더 이상 삽입하지 못한다는 문제점 존재.

-> 한정된 자원에서 계속해서 재사용할 수 있게 만들어주는 원형 큐

 

원형 큐 이슈

: rear는 front보다 커야해. 그런데 rear가 max까지 가면-> rear가 맨앞으로 간다. -> full OR empty ?

=> front가 자기보다 하나 앞을 point하게 한다.(이 공간이 reserved)

rear + 1 == front -> full

rear == front -> empty

5. Linked Structures

동적 배열 구현의 약점 : 최대 크기가 매개 변수로 생성자에게 전달된다.

-> Push할 때마다 하나씩 메모리를 할당받아서 써볼까?

 

(1) Stack - LIFO

- 필요한 것 : stack의 가장 위를 가리키는 topPtr

- Push : 실행하면 Info+pointer 구성의 Node를 하나 만든다.

info는 letter ‘V’, pointer는 NULL. topPtr의 포인팅을 NULL에서 해당 노드로 바꾼다.

- Pop : 실행하면 topPtr은 다음 노드를 가리킨다.(가장 최근에 들어온 것)

다음 노드가 없다면 NULL 값을 받는다.

- Add

newItem = ‘B’;

NodeType* location;

location = new NodeType<char>;

location->info = newItem;

location->next = topPtr; location에게 맨 위의 주솟값(topPtr에게 있다)를 준다

topPtr = location; 현재 맨 위의 주솟값이 location에게 있거든요

- Delete

NodeType* tempPtr;

item = topPtr->info;

tempPtr = topPtr; top을 기억해뒀다가, 지워줘야한다.

topPtr = topPtr->next;

delete tempPtr;

 

• destructor가 필요한 이유

: 데이터 멤버 topPtr의 메모리 공간은 할당 해제. BUT topPtr이 가리키는 노드는 자동으로 할당 해제X

따라서 데이터 멤버가 가리키는 동적 메모리를 할당 해제하는데 사용한다.

 

(2) Queue – FIFO (들어갈 때는 뒤로, 나갈 때는 앞으로)

- Enqueue

NodeType<ItemType>* ptr;

ptr = new Nodetype<Itemtype>;

ptr->info = newItem;

ptr->next = NULL;

if (qRear == NULL) qRear가 NULL -> next가 존재하지X. qRear와 qfront 둘다 ptr 가리켜라

qFront = ptr;

else

qRear->next = ptr;

qRear = ptr;

 

- Dequeue

tempPtr = qFront;

item = qFront->info;

qFront = qFront->next;

if (qFront == NULL) qFront가 NULL -> qRear도 NULL

qRear = NULL;

delete tempPtr;

 

• Memory Requirements

array-based : queue size(100), strings(80 bytes), Index(2 bytes)

Total = 80 * 101(slots) + 2*2(index) = 8084

Linked-list-based : pointer(4 bytes)

Total memory per node = 80 + 4 = 84

=> queue의 elements가 너무 많아지면 array를 쓰는 것이 이득일 수도 있다

 

(3) Unsorted List – linear relationship

- InsertItem : stack의 Add와 같구만

NodeType* location;

location = new NodeType<ItemType>;

location->info = item;

location->next = listData;

listData = location;

length++;

 

- DeleteItem

NodeType<ItemType>* location = listData;

NodeType<ItemType>* tempLocation;

 

if (item == listData->info) {

tempLocation = location;

listData = listData->next;

}

else {

while (!(item == (location->next)->info))

location = location->next;

 

tempLocation = location->next;

location->next = (location->next)->next;

}

delete tempLocation;

length--;

}

 

(4) Sorted List – linear relationship

- InsertItem

NodeType<ItemType>* newNode;

NodeType<ItemType>* predLoc;

NodeType<ItemType>* location;

bool moreToSearch;

 

location = listData;

predLoc = NULL;

moreToSearch = (location != NULL);

 

while (moreToSearch)

{

if (location->info < item)

{

predLoc = location;

location = location->next;

moreToSearch = (location != NULL);

}

else

moreToSearch = false;

}

 

newNode = new NodeType<ItemType>;

newNode->info = item;

 

if (predLoc == NULL)

{

newNode->next = listData;

listData = newNode;

}

else

{

newNode->next = location;

predLoc->next = newNode;

}

length++;

}