★ 012 데이터 입출력 구현[자료구조]

1. 자료 구조의 정의

- 효율적인 프로그램을 작성할 때 가장 우선적으로 고려해야 할 사항이 저장 공간의 효율성과 실행시간의 신속성

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

- 자료구조는 자료의 표현과 그것과 관련된 연산

- 자료구조는 일련의 자료들을 조직하고 구조화하는 것

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

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

 

2. 자료구조의 분류

1) 선형 구조

- 배열

- 선형 리스트: 연속 리스트, 연결 리스트

- 스택/큐/테크

 

2) 비선형 구조

- 트리/그래프

 

3. 선형구조

1) 배열(Array)

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

- 정적인 자료구조로, 기억장소의 추가가 어렵고, 데이터 삭제 시 데이터가 저장되어 있던 기억장소는 빈 공간으로 남아 메모리 낭비가 발생

- 데이터마다 동일한 이름의 변수를 사용하고, 첨자(Index, 인덱스)를 이용하여 데이터에 간편하게 접근

- 반복적인 데이터 처리 작업에 적합한 구조

- 사용하는 첨자의 개수에 따라 n차원 배열이라고 부름

 

2) 선형 리스트(Linear List)

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

 

* 연속 리스트(Contiuous List)

- 배열을 이용하는 리스트로, 연속되는 기억장소에 저장되는 자료구조

- 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율 밀도가 1로, 가장 좋다

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

* 연결 리스트(Linked List)

- 포인터를 이용하는 리스트로, 자료들을 반드시 연속적으로 배열시키지 않고, 임의의 기억공간에 기억.

- 이 때, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결

- 여기서 노드는 자료를 저장하는 데이터 부분과 다음 노드를 가리키는 링크 부분으로 구성된 기억 공간을 뜻함

- 기억 공간이 연속적이지 않아도 되기 때문에 노드의 삽입/삭제가 용이

- 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간 효율성이 좋지 않고, 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.

- 중간 노드 연결이 끊어지면 그 다음 노드를 찾기가 어려워진다.

 

3) 스택(Stack)

- 리스트의 한쪽 끝에서만 자료의 삽입/삭제 작업이 이루어지는 자료구조

- 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO: Last In First Out) 방식으로 자료를 처리

- 스택의 모든 기억 공간이 꽉찬 상태에서 데이터 삽입이 진행되면 오버플로가 발생되고, 데이터가 없는 상태에서 데이터를 삭제하면 언더플로가 발생한다.

- TOP: 스택 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소

- BOTTOM : 스택의 가장 밑바닥 부분

 

4) 큐(Queue)

- 리스트의 한쪽에서 삽입, 다른 한쪽에서삭제 작업이 이루어지는 자료구조

- 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FiFo: First In First Out) 방식으로 처리

- 프런트(Front) 포인터: 가장 먼저 삽입된 자료의 위치를 가리키는 포인터, 삭제 작업을 할 때 사용

- 리어(Rear) 포인터: 가장 마지막에 삽입된 자료의 위치를 가리키는 포인터, 삽입 작업을 할 때 사용

 

4. 비선형 구조

1) 트리(Tree)

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

- 하나의 기억 공간을 노드. 노드와 노드를 연결한 선을 링크.

- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것

- 근 노드(Root Node): 트리의 맨 위에 있는 노드

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

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

- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들

- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들

- 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들

- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수