[Data Structure] 중간고사 정리

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

1. Abstraction

Abstraction should be between too abstract and too concrete.

Abstraction : a model of complex system that includes only the details essential to the perspective of the viewer of the system. Tells what the program must do, but not how the program does it. 

2. Abstraction Data Type

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

특정 구현에 관계없이 속성(데이터와 연산)이 지정되는 데이터 유형

 

-shape, better access and modification, organization, management, store format, same key operations (O)

-Implementation details, number of provided operations(X)

3. Information hiding = encapsulation

---

4. Data

: the way to represent information in a suitable format for communication or analysis by humans or machines. 

In programming world, it is the information that is processed, objects that are manipulated(조작되는 개체들).

5. Data Abstraction

: Seperation of a data type's logical properties / implementation

6. Data : member vatiables / Operations : member functions (methods)

7. 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 

8. Composite Data Type

: a type that stores a collection of individual data components under one variable name

ex. arrays(structured)

class(unstructured), struct(unstructured) : can contain non homogeneous elements called members(=fields)

'.' is the member selection operator

---

9. Memory Allocation - Variables

-int, float : 4bytes

-short : 2bytes

-char : 1byte

 

ex. char name[10] = 10bytes

10. One-dimensional Array

Address[index] = BaseAddress + Index * Size of Element

Base Address : the location in the memory of the first element

11. Two-demensional Array 

In memory, C++ stores arrays in row order.(저장은 일렬로 함)

int intArray[5][12];

ex) Baseaddress : 2000일때, intArray[3][7]의 주소?

4*3*12 + 4*7 = 172 -> 2172

---

Chapter 2. Unsorted/Sorted List

1. List Definitions

- Linear Relationship : Each element except the first has a unique predecessor(앞에 사람), and each element except the last has a unique successor(뒤에 사람).

 

2. Basic ADT Operations

Constructor(생성자) : A special member function of a class tha is implicitly invoked when a class object is created

- It cannot return value type

- A class have multiple constructors with different parameter sets

(Parameterless constructor = default constructor)

Transformer(변경자), Observer(관측자)

---

<Unsorted List>

3. Constructor

UnsortedType::UnsortedType(){
	length = 0;
    }

4. Size

int UnsortedType::size(){
	return length;
    }

5. isFull

bool UnsortedType::isFull(){
	return (length == MAXSIZE);
    }

6. appendItem : always 2 computations ( add item ,length ++)

7. InsertItem : depending on "length" & "pos" (근데 순서 고려 안하고 insert하면 3computations)

 

8. Time Complexity Rules

1. Ignore all coefficients (계수)

2. Ignore significantly smaller terms.

9. Big O examples

- O(1) = bounded(by a constant) time

- O(logN) = logarithmic time  

- O(N) = linear time

- O(NlogN) N*log2N time

- O(N**2) quadratic time

- O(2**N) exponential time 

 

** O(5N + 3M**2 ) : 면 N, M 중 누가 큰지 모르기때문에 O(N+ M**2) 이렇게 써야함

** Sort the array D( length = N ) : minimum item 찾는 데 n, 그다음으로 작은거 찾는데 n .. 이런식으로 해서 n**2

** 피보나치 수열의 N번째 아이템 return : Fibo(N) = Fibo(N-1) + Fibo(N-2) 이므로 2**N 

근데 , 걍 1 1 2 3 5 8 이런식으로 하면 N 아닌가

10. removeItem : O(2N+1) 이지만 순서를 고려하지 않으면 O(N+2)도 가능

11. Clear

void UnsortedType::clear(){
	length = 0;
}

data[]는 값을 가지고 있지만, appendItem이 overwrite 하기 때문에 괜찮음

---

<Sorted List>

: A list that is sorted by the value in the key; semantic(의미론적인) relationship

 

12. finditem : 찾으려는 값을 초과하면 break 하므로서 computation 줄일 수 있고, 이진 탐색으로서 더 줄일 수 있음

bool SortedType::findItem(ItemType item){
	int mid;
    int first = 0;
    int last = length -1;
    while(first <=last){
    	mid = (first + last) / 2;
        if (item < data[mid]){
        	last = mid -1;
        }
        else if (item > data[mid]){
        	first = mid + 1;
        }
        else{
        	return true;
        }
        
    }
    return false;
 }

13. Are List and Array the same ? No

List : ADT

Array : CDT(Concrete Data Type)

---

Chapter 3. Stack

1. LIFO : Last In First Out

ex) Undo, Back(browser), Stack Trace

2. Constructor

StackType::StackType(){
	top = -1;
}

-1 : To represent the stack is empty

3. Size

int StackType::size() const{
	return (top+1);
    }

4. isFull

bool StackType::isFull() const{
	return (top == MAX_SIZE -1);
    }

5. isEmpty

bool StackType::isEmpty() const{
	return (top ==-1)
    }

---

Class Template

6. class template은 cpp 파일에서 구현 X , header file 에서 구현해야함 

- in heather file

template<class ItemType>
class StackType{
	//...
}

- in c++ file 

template<class ItemType>
void StackType<ItemType>::push(ItemType value){
	//..
    }

- main file 

int main(){
	StackType<int> tempStack;
    }

---

Pointer

7. msg is a name of array and it means the base address. 

char msg[8];

 

8. To declare a pointer variable, you must specify the type of value that the pointer will point to. 

9. "*" is dereference operator.

10. It means a pointer points to nothing.

int *ptr = NULL;
* ptr = 13;

but, using nullptr is recommended to avoid ambiguous function overloading. 

---

Memory Allocation Type

11. Process Memory Map

Process Memory Map : 프로세스가 실행될 때 운영체제에 의해 할당되는 메모리 영역

밑에서부터 보면, 

CODE(TEXT) : 기계어로 코드 저장, 읽기 전용

DATA : 초기화된 전역변수, 정적변수 저장

BSS : 초기화되지 않은 전역변수, 정적변수 저장

STACK : 지역변수 

HEAP : 동적 메모리 할당 

표 매우 중요 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

12. Automatic Allocation 

Variable Type	Allocation Time	Deallocation	Location	Size Change
Local variables (지역 변수)	Function Call (함수 호출 시)	Function termination (함수 종료 시)	Stack	Fixed

 

12-1. 함수는 스택 형식으로 저장됨 -> 지역 변수도 마찬가지 

12-2. Activation Record

 

- argv , argc : 호출시 함수에 전달된 인자

- Return Address : 함수 종료 시 다시 복귀할 함수 주소

- Local Variables : 지역 변수(그림에선 c,d,e)

 

 

12-3. 다음과 같은 코드 컴파일 불가능 

cin >> cnt;
int arr[cnt];

 

지역 변수는 컴파일할 때 모두 결정되어야 하기 때문

 

컴파일 vs 런타임 

컴파일 : 코드가 올바르게 작성되었는지 확인하고 실행 파일을 만드는 단계

런타임 : 파일이 실제로 실행되면서 동작하는 단계

13. Dynamic Allocation 

Variable Type	Allocation Time	Deallocation	Location	Size Change
Variables with dynamic size	instructions : new, malloc ( 명령이 있을 떄 )	instructions : delete, free ( 명령이 있을 때 )	Heap	Flexible

 

13-1. 동적 할당은 독립적인 스택임. 

13-2. 함수가 종료된 후에도, 명령이 있지 않는 한 계속 존재

13-3. 따라서 명시적으로 메모리를 deallocated 해주어야 함. 

13-4. 명시적으로 메모리를 deallocated 하지 않으면, 그것을 가르키는 포인터가 함수가 끝난 후 사라지고, 접근을 못하면서 메모리만 차지하게 됨 => Memory leakage(메모리 누수)

13-5. 따라서, garbage를 막고 싶으면

1. delete 
2. keep the pointer using return or return by reference

14. Static Allocation 

Variable Type	Allocation Time	Deallocation	Location	Size Changed
Static/global variables	Compile Time ( Program Starts )	Program Termination	DATA segment	Fized

14-1. 표에서 컴파일 타임이 왜 프로그램이 시작할 때인지 의문이 들었는데, 아마 교수님께서 컴파일 이후에는 바꿀 수 없어서 저렇게 적어놓으신 거 같다 .. 

---

Chapter 4. Queue

1. FIFO : First In, First Out 

ex) Job Buffers, Network Buffers

2. dynamic array implementation 

template<class ItemType>
class QueueType
{
private:
	ItemType * data; //dynamic array implementation 
    int front;
    int rear;
    int maxQueue;
    
    //...//
    
    }

3. Constructor

template<class ItemType>
QueueType<ItemType>::QueueType(int maxQueue){
	maxQueue = maxQue + 1; //reserved space
    front = maxQueue -1; //reserved space is at the last location 
    rear = maxQueue -1; //reserved space is at the last location
    data = new ItemType[maxQueue];
    
    }

4. envolvement of Queue

O(n) : 하나 지우고 하나씩 다 앞으로

O(1) : 그냥 앞에걸 하나 빼는거 

O(1) : circular queue

5. front == rear + 1 <= 이게 full queue 도 될 수 있고, empty queue도 될 수 있음

=> 해결책 reserved space (front always points to it) 

=> Full Queue : (rear+1)%maxQueue == front;

=> Empty Queue : rear == front 

6. Destructor 

template<class ItemType>
QueueType<ItemType>::~QueueType(){
	delete [] data;
    }

 

7. Enqueue

template <class ItemType>
void QueueType<ItemType>::enqueue(ItemType newItem){
	rear = (rear+1)% maxQueue;
    data[rear] = newITem;
    }

8. Dequeue

template<class ItemType>
ItemType QueueType<ItemType>::dequeue(){
	ItemType ret;
    front = (front+1)% maxQueue;
    ret = data[front];
    return ret;
    }

---

4.5 . Programming Tips

Return by Reference 

1. Call by reference :  객체를 그으으으대로 주소값까지 똑같이 넘겨줌

=> share the same memory

2. return by reference 

int increment(int & a){
	a++;
    }
    
int main(){
	int main_a = 3;
    int ret = increment(main_a);
    cout << ret << endl;
    }

 

언제 사용하는가?

1. 리턴할 객체가 너무 클 때(복사하는데 오래걸림)

2. 여러개의 객체를 리턴받고 싶을때 

3. 동적할당된 객체를 리턴받고 싶을때 

---

Polymorphism 

1. Overloading 

: The abiltity to define multiple functions with the same name but different parameter lists

ex) add(int a, int b) / add(float a, float b, float c)

2. Overriding 

: The ability of a derived class to provide a specific implementation of a method that is already defined int the base class

must have the same name, parameters(numbers & types) , return type 

---

Chapter 5. Linked Structure 

Linked Stack

struct NodeType{
	ItemType value;
    NodeType *next;
    }

1. Constructor

StackType::StackType(){
	topptr = nullptr;
    }

2. push

void StackType::push(ItemType new_value){
	// Exception Handeling -> isFull 
	NodeType * newNode;
    newNode = new NodeType;
    
    newNode -> value = new_value;
    newNode -> next = topPtr;
    topPtr = newNode;
    }

3. isFull

bull StackType::isFull() const{
	NodeType *newNode;
    try{
    	newNode = new NodeType;
        delete newNode;
        return false;
        }
    catch(std::bac_alloc exception){
    	return true;
        }
    }

일단 노드를 더 만들어보고 안만들어지면 Full 인걸로

4. pop

ItemType StackType::pop(){
	//Exception Handeling - isEmpty() -> return or throw
    NodeType * tempPtr;
    tempPtr = topPtr;
    topPtr = topPtr -> next;
    
    delete tempPtr;
    }

5. isEmpty

bool StackType::isEmpty() const{
	if (topPtr == nullptr){
    	return true;
        }
        return false;
    }

6. Destructor 

StackType::~StackType(){
	NodeType * tempPtr= topPtr;
    
    while (tempPtr != nullptr){
    	topPtr = topPtr -> next;
        delete tempPtr;
        tempPtr = topPtr;
        }
    }

---

Linked Queue 

template<class ItemType>
class QueueType
{
private: 
	NodeType<ItemType> * pFront;
    NodeType<ItemType> * pRear;
    //...
    
    }

노드타입형 포인터 필요