1. 자료구조의 분류
- 선형 구조 : 선형 리스트(배열), 연결 리스트, 스택, 데크, 큐
- 비선형 구조 : 트리, 그래프
2. 자료구조의 종류
- 배열을 기반으로 구현한 리스트이다.
2-2. 연결리스트
- 메모리 동적 할당을 기반으로 구현한 리스트이다.
- 자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조이다.
- 노드의 삽입, 삭제 작업이 용이하다.
- 접근 속도가 느리다.
- 기억 공간이 연속적으로 놓여있지 않아도 저장이 가능하다.
- 연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억공간 이용 효율이 좋지 않다.
- 연결 리스트 중에서 중간 노드의 연결이 끊어지면 다음 노드를 찾기 힘들다.
2-3. 스택(Stack)
- 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다.
- 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO; Last-In, First-Out) 방식으로 자료를 처리한다.
- TOP : Stack으로 할당된 기억공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소로 스텍 포인터라고도 한다.
- Bottom : 스택의 가장 밑바닥이다.
- PUSH : 스택에 자료를 입력하는 명령이다.
- POP : 스택에서 자료를 출력하는 명령이다.
- 부프로그램 호출 시 복귀주소를 저장할 때 이용한다.
- 함수 호출의 순서를 제어할 때 이용한다.
- 인터럽트가 발생하여 복귀주소를 저장할 때 이용한다.
- 후위 표기법(Postfix Notation)으로 표현된 산술식을 연산할 때 이용한다.
- 0 주소지정방식 명령어의 자료 저장 시 이용한다.
- 재귀(Recursive) 프로그램의 순서를 제어할 때 이용한다.
- 컴파일러를 이용한 언어 번역 시 이용한다.
2-4. 데크(Deque)
- 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.
- Double Ended Queue의 약자.
- 스택과 큐의 장점만 가져와서 구성한 것이다.
- 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과 입력은 양쪽에서 일어나고 출력은 한쪽에서만 이루어지는 출력 제한이 있다.
입력 제한 데크(Scroll)
출력 제한 데크(Shelf)
2-5. 큐(Queue)
- 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조이다.
- 시작과 끝을 표시하는 두 개의 포인터가 있다.
- 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO; First-In, First-Out) 방식으로 처리한다.
- 프런트 포인터 : 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터로, 삭제 작업을 할 때 사용한다.
- 리어 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터로, 삽입 작업을 할 때 사용한다.
- 창구 업무처럼 서비스 순서를 기다리는 등의 대기 행렬의 처리에 사용한다.
- 운영체제의 작업 스케줄링에 사용한다.
2-6. 트리(Tree)
- 정점(Node, 노드)과 간선(= edge, 엣지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태이다.
- 가족의 계보, 연산 수식, 회사의 조직 구조도, 히프(Heap) 등을 표현하기에 적합하다.
- 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것
- 근 노드(Root Node) : 트리의 맨 위에 있는 노드.
- 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수.
- 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수.
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드로 디그리가 0인 노드.
- 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드로 디그리가 0이 아닌 노드.
- 자식 노드(Son Node, Children Node) : 어떤 노드에 연결된 다음 레벨의 노드들.
- 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드.
- 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들.
- Level : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1이다
- 깊이(Depth, Height) : 어떤 Tree에서 노드가 가질 수 있는 최대의 레벨.
* 이진 트리의 운행
: 이진트리란 한 노드가 최대 2개까지 자식 노드를 가지는 트리를 말하며, 첫 번째 노드인 부모는 Root, 자식 노드는 왼쪽(Left), 오른쪽(Right)라고 불린다.
- 전위 운행(Pre-order) : Root → Left → Right 순서로 운행.
- 중위 운행(In-order) : Left → Root → Right 순으로 운행.
- 후위 운행(Post-order) : Left → Right → Root 순으로 운행.
전위 운행 순서 : A → B →D → E → G → H → C → F → I
중위 운행 순서 : D → B → G → E → H → A → C →F → I
후위 운행 순서 : D → G → H → E→ B → I → F → C → A
2-7. 그래프(Graph)
- 버텍스(Vertex, =노드)와 아크(Arc, =엣지)로 구성되어 있으며 다른 버텍스로부터 오는 아크의 개수를 In-degree, 다른 버텍스로 가는 아크의 개수를 Out-degree라고 부른다.
- 트리의 노드가 하나의 In-degree만 가지는 반면, 그래프의 버텍스는 하나 이상의 In-degree를 가질 수 있다.
댓글 없음:
댓글 쓰기