[2과목-1장-034] 자료 구조

프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간 관계, 처리 방법 등을 연구 분석하는 것

 

= 자료의 표현과 그것과 관련된 연산

= 일련의 자료들을 조직, 구조화하는 것

- 어떤 자료 구조에서도 필요한 모든 연산들을 처리할 수 있다.

- 자료 구조에 따라 프로그램 실행시간이 달라짐

 

* 분류

* 선형 구조 (Linear Structure)

1) 배열(Array)

: 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합

- 정적인 자료 구조. 기억장소의 추가 어려움, 데이터 삭제 시 메모리 낭비 발생

- 첨자 이용하여 데이터 접근

- 반복적 데이터 처리 작업에 적합

- 데이터마다 동일한 이름의 변수 사용 > 처리 간편

- n차원 배열

 

2) 선형 리스트(Linear List)

: 일정한 순서에 의해 나열된 자료 구조

(1) 연속 리스트(Contiguous List)

: 배열과 같이 연속되는 기억장소에 저장되는 자료 구조

- 연속적으로 배정 > 기억장소 이용 효율 = 밀도가 1로서 가장 좋다.

- 중간에 데이터 삽입하기 위해서는 연속된 빈 공간이 있어야 함, 삽입/삭제 시 자료 이동이 필요

 

* 밀도가 1: 배정된 기억장소를 빈 공간없이 꽉 차게 사용한다는 의미

 

(2) 연결 리스트(Linked List)

: 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분 이용하여 서로 연결시킨 자료 구조

- 노드의 삽입/삭제 작업 용이

- 기억이 연속적으로 놓여 있지 않아도 저장 가능

- 연결을 위한 링크(포인터) 부분이 필요 > 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않음

- 포인터를 찾는 시간이 필요 > 접근 속도 느림

- 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦

 

3) 스택(Stack)

: 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조

- 후입선출(LIFO) 방식으로 자료 처리

- 오버플로우, 언더플로우 발생 가능

* TOP: 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소

* BOTTOM: 스택 가장 밑

 

4) 큐(Queue)

: 리스트의 한쪽에서는 삽입 작업 이뤄지고, 다른 한쪽에서는 삭제 작업이 이뤄지도록 구성한 자료 구조

- 선입선출(FIFO) 방식으로 처리

 

* 프런트(F) 포인터: 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터. 삭제 작업 시 사용

* 리어(R) 포인터: 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터. 삽입 작업 시 사용

 

- OS의 작업 스케줄링에 사용함.

 

 

* 비선형 구조 (Non-Linear Structure)

1) 트리(Tree)

: 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태

- 노드: 하나의 기억 공간

- 링크: 노드와 노드를 연결하는 선

- 가족의 계보, 조직도 등 표현 시 적합

 

 

** 트리 관련 용어

(1) 노드: 트리 기본 요소. 자료 항목과 다른 항목에 대한 가지를 합친 것

(2) 근 노드(Root Node): 트리 맨 위의 노드

(3) 디그리(Degree, 차수): 각 노드에서 뻗어 나온 가지 수

(4) 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 디그리가 0인 노드

(5) 자식 노드

(6) 부모 노드

(7) 형제 노드

(8) 트리의 디그리: 노드들의 디그리 중 가장 많은 수