[ 정보처리기사 ] 2과목 - 데이터 입출력 구현 1

자료구조(Data Structure)

컴퓨터상 자료를 기억장치에 효율적으로 저장하기 위해 만들어진 논리적은 구조

▪ 분류 : 선형구조, 비선형 구조

선형 구조	데이터를 연속적으로 연결한 자료 구조	리스트, 스텍, 큐, 테크
비선형 구조	데이터를 비연속적으로 연결한 자료 구조	트리, 그래프

 

선형 구조

 

🔷 리스트(List)

선형 리스트 (Linear List)	배열과 같이 연속되는 기억 장소에 저장되는 리스트
연결 리스트 ( Linked List)	노드와 포인터 부분으로 서로 연결되는 리스트

 

🔸 선형 리스트

 

장점 

▪ 중간에 빈 기억 공간이 없음

▪ 빈공간없이 연속적으로 저장되어 기억공간의 밀도가 좋다

 

단점

▪ 삽입. 삭제 할 경우 자료 이동이 많아 힘들다.

 

종류 : 일차원 배열, 이차원 배열, 삼차원 배열

 

🔸 연결리스트

 

장점

▪  배열과 달리 삽입.삭제가 용이하며 처리하는 속도가 빠름

▪ 연속된 공간이 아닌 포인터를 통해 연결

▪ 희소행렬 표기

 

단점

▪ 위치를 기억하는 포인터의 정 보를 저장하는 공간이 따로 임음

 

종류 : 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트

 

🔷 스택 ( Stack )

: 한 방향으로만 자료를 넣고 꺼낼 수 있는 형식의 자료 구조

▪ LIFO 구조, FILO 구조

▪ 한 방향으로 PUSH, POP을 이용하여 데이터를 넣고 꺼냄

 

▪ TOP : 스택에서 가장 위에 있는 데이터, 스택 포인터(Stack Pointer)로도 불림

 

연산

▪ PUSH : 데이터를 차례대로 스택에 넣는 연산

- 저장 범위를 넘어 간 경우 : Overflow

▪ POP : 스택에서 가장 위에 있는 데이터를 하나씩 꺼내는 연산

- 저장 범위를 넘어 간 경우 : Underflow

 

🔷 큐 ( Queue )

: 한쪽 끝에서는 삽입 작업이 이뤄지고, 반대쪽 끝에서는 삭제 작업이 이뤄지는 형식의 자료 구조

▪ LILO 구조, FIFO구조

 

▪ ENQUEUE를 통해 데이터를 넣고, DEQUEUE를 이용하여 데이터를 꺼냄

 

▪ 데이터를 꺼내는 쪽 : Front

▪ 데이터를 넣는 쪽 : Rear

 

연산

▪ ENQUEUE : 데이터를 차례대로 넣는 연산

▪ DEQUEUE : 저장된 데이터를 하나씩 꺼내는 연산

 

🔷 데크 (Deque : Double Ended Queue )

: 큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조

 

▪  두 개의 포인터를 사용하여 양쪽의 삭제/ 삽입이 가능하다

▪ 스택과 큐의 구현이 가능하다

 

▪ 데크의 제약 조건을 걸어 사용 목적을 달리하는 구조

- 스크롤 ( Scroll ) : 입력 제한

- 셀프 ( Shelf ) : 출력 제한

 

비선형 구조

🔷 트리 ( Tree )

: 데이터들을 계층화시킨 자료구조

 

▪ 인덱스를 조작하는 방법으로 가장 많이 사용하는 구조

▪ 노드(Node) 와 노드를 연결하는 링크(Link)로 구성

▪ 노드들이 포인터로 연결되어 노드의 상한성이 없음

 

트리 명칭

루트 노드 ( Root Node )	부모가 없는 최상위 노드, 트리의 시작점
단말 노드 ( Leaf Node )	자식이 없는 노드, 트리의 가장 밑에 위치
래밸 (Level)	루트 노드를 기준으로 특정 노드까지의 경로 길이
조상 노드 ( Ancestor Node )	특정 노드에서 루트에 이르는 경로상의 모든 노드
자식 노드 ( Child Node )	특정 노드에서 연결된 다음 레벨의 노드
부모 노드 ( Parent Node )	특정 노드에 연결된 이전 레벨의 노드
형제 노드 ( Sibling )	같은 부모를 가진 노드
깊이 ( Depth )	루트 노드에서 특정 노드에 도달하기 위한 간선의 수
차수 ( Degree )	특정 노드에 연결된 자식 노드의 수

 

🔸 이진 트리

 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조,  차수가 2개인 트리 구조

 

종류

 

정이진 트리	전이진 트리	사향이진 트리