Datastructure

SSU Datastructure Class

Summary

1. A Lead

Blog

• Data Structure?
• Abstract Data Type (ADT)
• Algorithm
• Time Complexity & Space Complexity
• Big-O Notation

2. Array & Class

Blog

• Array
• Address of an Array
• Call by Value vs Call by Reference
• Struct
• Class
• Object-Oriented Programming

Code

• 2.1 1차원, 2차원 배열 선언 및 크기 구하기
• 2.2 Call by Value vs Call by Reference
• 2.3 함수의 매개변수로 배열 전달
• 2.4 구조체 정의 및 사용
• 2.5 클래스 정의 및 사용
• 2.6 다항식 예제
• 2.7 희소 다항식 예제

3. Stack

Blog

• Stack
• Stack using Array
• Stack using LinkedList
• Stack in C++ STL
• Stack in Java library
• Check Bracket
• Infix → Postfix → Calc
• Depth First Search (DFS)

Code

• 3.1 Array를 이용한 Stack
• 3.2 LinkedList를 이용한 Stack
• 3.3 괄호검사 알고리즘 예제
• 3.4 중위표기식 -> 후위표기식 -> 계산 예제
• 3.5 미로탐색(DFS) 예제

4. Queue & Deque

Blog

• Queue
• Queue using Array
• Circular Queue
• Circular Queue using Array
• Fibonacci numbers
• Breadth First Search (BFS)

Blog

• Deque
• Circular Deque using Array
• Circular Deque using LinkedList

Code

• 4.1 Array를 이용한 Linear Queue
• 4.2 Array를 이용한 Circular Queue
• 4.3 Array를 이용한 Circular Deque
• 4.4 Singly Linked List를 이용한 Queue
• 4.5 Doubly Linked List를 이용한 Deque
• 4.6 피보나치 수열 계산 예제
• 4.7 미로탐색(BFS) 예제

5. Pointer

Blog

• Pointer
• Double·Triple Pointers
• Call by Value vs Call by Reference
• Array & Pointer
• Class object pointers and Accessing member functions

Blog

• Stack and Heap memory
• Dynamic memory allocation
• Static memory allocation
• new & delete
• Dynamically allocation a 2D Array

Code

• 5.1 포인터 기본
• 5.2 다중 포인터
• 5.3 Call by Value vs Call by Reference
• 5.4 배열과 포인터
• 5.5 객체의 멤버에 접근하는 방법
• 5.6 정적배열 vs 동적배열
• 5.7 동적메모리 할당 - new & delete
• 5.8 2차원 배열의 동적할당

6. List

Blog

• List
• Array vs List
• ArrayList
• LinkedList
• ArrayList vs LinkedList
• Singly LinkedList
• Circular LinkedList
• Doubly LinkedList
• Head pointer vs Head node

Code

• 6.1 ArrayList
• 6.2 Singly LinkedList (head pointer 사용)
• 6.3 Singly LinkedList (head node 사용)
• 6.4 Singly LinkedList 응용 (reverse, merge)
• 6.5 Doubly LinkedList (head node 사용)

7. Recursion

Blog

• Recursion
• Iteration vs Recursion
• Factorial
• Power
• Fibonacci numbers
• Tower of Hanoi
• Blob coloring

Code

• 7.1 Factorial
• 7.2 Power
• 7.3 Fibonacci
• 7.4 Tower of Hanoi
• 7.5 BW 이미지 영역채색
• 7.6 각 함수의 재귀호출 빈도 측정
• 7.7 순환을 이용하여 문자열 뒤집기

8. Tree

Blog

• Tree
• Tree Terminology and Definitions
• Binary Tree
• Encoding General tree as Binary tree
• Full Binary Tree
• Complete Binary Tree
• Properties of Binary Tree
• Binary Tree using Array
• Binary Tree using Link
• Traversal of Binary Tree

Blog

• Binary Search Tree
• Operations of BST

Blog

• Priority Queue
• Heap
• Operations of Priority Queue
• Priority Queue in C++ STL
• Heap Sort

Code

• 8.1 이진 트리
• 8.2 이진탐색 트리
• 8.3 우선순위 큐
• 8.4 우선순위 큐 (STL활용)
• 8.5 힙 정렬

9. Graph

Blog

• Graph
• Graph Terminology and Definitions
• Type of Graph
• Adjacency Materix
• Adjacency List
• Depth First Search (DFS)
• Breadth First Search (BFS)
• Connected Component
• Spanning Tree

Code

• 9.1 인접 행렬(Adjacency Matrix)을 이용한 Graph (무방향 그래프)
• 9.2 인접 리스트(Adjacency List)을 이용한 Graph (무방향 그래프)
• 9.3 Graph 깊이우선탐색(DFS) 예제 - Adjacency Matrix
• 9.4 Graph 깊이우선탐색(DFS) 예제 - Adjacency List
• 9.5 Graph 너비우선탐색(BFS) 예제 - Adjacency Matrix
• 9.6 Graph 너비우선탐색(BFS) 예제 - Adjacency List
• 9.7 Graph 최종
• 9.8 Graph 최종 (txt파일 load하여 graph 생성)
• 9.9 Connected Component(연결 성분) 탐색 프로그램 예제
• 9.10 Graph의 브리지 전체 개수 구하기 예제