개발새발

선형구조는 지난 포스팅 참조

자료구조란?

자료의 표현, 연산을 의미한다

크게 선형구조 와 비선형 구조로 나뉘며,

세부적으로 선형 구조의 종류에는 리스트, 스택, 큐, 데큐 (데크)

비선형 구조의 종류에는 트리와 그래프가 있다

트리 Tree

트리구조는 나무의 뿌리처럼 이미지상으로는 아래를 향하지만 가지처럼 뻗어나가는 구조이다

갭탭으로 이미지 그려 수정예정**

차수는 가지수를 의미한다

이미지에서 뿌리 노드 root node 에서 뻗어나온 가지 수는 3

ex) C 의 차수 : 2

차수가 0 인 노드는 단말노드 leaf node 라 한다

왼쪽 라인을 보면 뿌리부터 1,2,3,4...레벨로 깊이를 나타낸다

관계에 따라 부모, 자식, 형제, 조상 노드로 불린다

이진트리

갭탭으로 이미지 그려 수정예정**

그래프 Graph

정점 vertex, 간선 edge 의 모음

트리도 그래프라고 볼수 있는데, 다른 점은 사이클이 존재한다

그래프의 탐색 방법으로 깊이 우선 탐색 DFS(Depth-First Search) 과 너비 우선 탐색 BFS(Breadth-First Search)이 있다

정보처리기사를 공부하려던 계기중 하나인 자료구조 파트!

중요하니까 적어두자

필기 제 2과목 소프트웨어 개발

데이터 입출력 구현 A

자료구조란?

자료의 표현, 연산을 의미한다

크게 선형구조 와 비선형 구조로 나뉘며,

세부적으로 선형 구조의 종류에는 리스트, 스택, 큐, 데큐 (데크)

비선형 구조의 종류에는 트리와 그래프가 있다

먼저 선형구조부터 살펴 보겠다

리스트 Linear List

리스트 안에서도 선형 리스트와 연결 리스트로 나뉜다

이미지 갤탭 이용해 삽입하기

스택 Stack

이미지 삽입 예정

한쪽으로 들어와 한쪽으로 나가는 구조이며

상단을 Top, 하단을 Bottom 이라한다

입력은 push, 출력은 pop 이라 명칭하며

입력은 ABCD, 출력은 DCBA 순서로 진행된다

LIFO, FILO 구조라고도 한다

입력 (삽입) 알고리즘

Top = Top + 1
if (Top>n) then overflow;
else 삽입

출력 (삽입삭제) 알고리즘

if (Top=0) then underflow;
else {삭제 Top = Top - 1
}

=> 산술식 표현, 함수, 인터럽트 복귀 주소에서 활용한다

큐 Queue

이미지 삽입 예정

오른쪽으로 들어와 왼쪽으로 나가는 구조이다

입력이 되는 오른쪽을 Rear

출력이 되는 왼쪽을 Front 라 한다

입력, 출력이 ABCD 동일순서로 진행된다

LILO, FIFO 구조라고도 한다

입력 (삽입) 알고리즘

r=r+1

출력 (삽입 삭제) 알고리즘

f=f+1

=> 작업 스케줄링, 버퍼관리에서 활용한다

데큐 (데크) Deque (Double-ended Queue)

이미지 삽입 예정

큐와 동일한 구조면서

양방향에서 출력과 입력이 들어올수 있는 구조이다

입력 제한 데크 스크롤 Scroll

한쪽에서만 입력이 가능하도록 한쪽 방향의 입력을 막는다 (출력을 양방향 가능하다)

출력 제한 데크 쉘프 Shelf

한쪽에서만 출력이 가능하도록 한쪽 방향의 출력을 막는다 (출력을 양방향 가능하다)