정처기#10 자료구조

1 ) 자료구조 분류 

• 단순 구조(Simple) : 프로그래밍 언어에서 제공하는 기본 데이터 타입, int(정수), float(실수형), double(실수), char(문자)
• 선형 구조(Liner) : 데이터들 사이의 선후 관계가 1:1 구조

종류

Stack, Queue, Deque, 선형 리스트(Linear List), Linked List※

• 비선형 구조: 데이터 사이의 선후관계가 계층 또는 그물 형태를 가지는 구조

종류

트리(Tree) 구조, 그래프

 

2 ) Stack (스택)

• 후입 선출(LIFO) 구조
• 함수를 호출하여 복귀할 때, 깊이 우선 탐색(DFS), 재귀적(Recursion) 함수, 인터럽트 수행 시, 0-주소 명령어 방법 등에서 이용

3 ) Queue (큐)

• 선입선출(FIFO) 구조
• 프린터 스풀이나 입출력 버퍼 등에서 이용

4 ) Deque (데크)

• 양쪽 모두에서 입력과 출력
• 스크롤 : 출력은 양쪽에 모두 가능하지만, 입력은 한쪽에서만 사용하는 방법
• 셀프 : 입력은 양쪽에서 모두 가능하지만, 출력은 한쪽에서만 사용하는 방법

5 ) Linear List (선형 리스트)

• 배열과 같이 연속되는 기억 공간에 저장되는 리스트 구조
• 액세스 시간이 짧고 구조가 간단
• 중간에 삽입/삭제하기 어려움

6 ) Linked List (연결 리스트)

• 각 자료의 포인터를 이용하여 연결한 구조
• 자료의 삽입과 삭제가 용이
• 기억 공간이 연속적이지 않아도 자료를 저장
• 포인터 기억 공간이 추가적으로 필요
• 포인터를 찾는 시간 때문에 선형 리스트에 비해 느림

7 ) Tree (트리)

그래프의 특수한 형태로 Node와 Branch으로 구성, 노드(정점) 사이에 사이클이 형성되어 있지 않으며, 계층 구조형식

8 ) Graph (그래프)

• 데이터의 검색, 데이터의 복잡도, 전자회로 분석 등 다양한 응용 분야에 적용

9 ) 이진트리 순회

1. 중위 순회 방법

    H-D-I-B-E-A-F-C-J-G-K

2. 전위 순회 방법

    A-B-D-H-I-E-C-F-G-J-K

3. 후위 순회 방법

    H-I-D-E-B-F-J-K-G-C-A

10 ) 폴리쉬 표기법

이해가 안 간다 ㅠㅠ