03. 자료구조(선형, 비선형)

제1절 자료구조의 기본

제1항 자료구조의 개요

(１) 자료구조란?

 

그림 13. 자료구조

 

1) 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업

2) 컴퓨터에서 처리할 자료를 효율적으로 관리하고 구조화시키기 위한 학문이다. 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업을 의미한다.

3) 자료구조에 따라 저장공간의 효율성과 프로그램의 실행시간이 달라짐

 

(２) 컴퓨터 분야에서 자료구조를 배우는 이유?

1) 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 한다.

2) 자료의 특성을 이해하고 분석하여 최적의 알고리즘을 개발하는 능력이 필요

 

 

(３) 자료구조에서 다루는 내용

 

(４) 자료구조의 분류

 

1) 단순구조

① 정수, 실수, 문자, 문자열 등의 기본 자료형

 

2) 선형구조

① 자료들 간의 앞뒤 관계가 1:1의 선형관계

② 리스트, 연결리스트, 스택, 큐, 덱 등

 

3) 비선형구조

① 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계

② 트리, 그래프 등

 

4) 파일구조

① 레코드의 집합인 파일에 대한 구조

② 순차파일, 색인파일, 직접파일 등

 

기출문제) 비선형 구조와 선형 구조가 옳게 짝지어진 것은?

1. 스택(Stack)     2. 큐(Queue)

3. 트리(Tree)      4. 연결리스트(Linked List)

5. 그래프(Graph)

 

가. 비선형 구조: 1, 2, 5     선형구조: 3, 4

나. 비선형 구조: 3, 5         선형구조: 1, 2, 4

다. 비선형 구조: 1, 2, 3     선형구조 4, 5

라. 비선형 구조: 3             선형구조: 1, 2, 4, 5

 

답) 나

1.       

제2항 기본자료형

(１) 정수형

1) 십진수, 8진수, 16진수로 표현가능

2) 접미사

① l or L : long 상수

② u or U: unsigned 상수

3) 종류

 

(２) 실수형

1) 123.4, 1.234e2, 1.234E2, 1.234f, 1.234d 의 형태로 표현

2) 접미사

① f or F : float

② d or D : double

3) 종류

 

(３) 문자형

1) ‘a’, ‘A’, ‘0’ 과 같이 표현

2) Single quote 사용

3) 제어문자(Escape sequence) 표현

`

4) 종류

 

(４) 문자열형

1) “SEOUL”와 같이 double quote로 둘러싸인 일련의 문자들

2) “”: 빈 문자열

3) 문자상수 ‘a’와 문자열 상수 “a”는 구분되어야 한다.

4) 문자열은 반드시 null(‘\0’) 로 끝난다.

 

제3항 선형 구조(Linear Structure)

(１) 리스트 (List)

1) 리스트의 종류

① 선형리스트(Linear List)

ü 배열과 같이 연속되는 기억장소에 저장되는 리스트를 말한다.

ü Array(배열)

 

 

② 연결 리스트

ü 자료들이 반드시 연속적으로 배열되어 있지 않아도 노드 포인터 부분을 이용하여 서로 연결되어진 구조를 말한다.

ü 포인터

 

 

(２) 선형 리스트 (Linear List)

1) 연속적인 기억장소에 저장된 리스트

2) 순차리스트 또는 연접리스트(Dense List) 라고도 함

3) 임의의 노드에 접근을 할 때는 인덱스(Index)를 사용하므로 포인터가 없음

4) 장점

① 간단한 자료구조

② 저장 효율이 뛰어남 (기록밀도: 1)

③ 접근 속도(Access Time)가 빠름

5) 단점

① 삽입과 삭제가 어려움

② 삽입 및 삭제시 삽입하거나 삭제할 위치 이후의 모든 자료의 이동이 필요

 

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

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

 

 

2) 장점

① 자료의 삽입 및 삭제가 용이

② 비연속적 (한 리스트를 여러 개의 리스트로 분리하기 쉬움)

③ 희소행렬(행렬의 요소들 중에서 많은 부분이 0으로 되어 있는 행렬)을 연결 리스트로 표현시 기억장소 이용 효율이 좋음

 

3) 단점

① Access Time이 느림

② 기억장소 이용 효율이 나쁨(저장되지 않은 빈 공간 발생)

③ 포인터를 위한 추가 공간이 필요

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

 

4) 종류

① 단순 연결 리스트 (단순 링크드 리스트)

ü 한 방향으로만 가리키고 있다.

그림  SEQ 그림 \* ARABIC 20. single linked list

 

② 이중 연결 리스트

ü 양 방향으로 가리키고 있다.

그림  SEQ 그림 \* ARABIC 21. double linked list

 

③ 단순 환형 연결 리스트

 

 

(４) 스택 (Stack)

1) 정의

① top이라고 하는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 자료구조

② 자료의 후입선출(last-in-first-out) 방법

ü 자료의 삽입: TOP = TOP + 1

ü 자료의 삭제: TOP = TOP – 1;

ü Overflow 발생: 스택의 크기가 M일 때, TOP > M 이면 Overflow 발생

 

2) 용도

① 인터럽트의 처리

② 수식의 계산 (산술식 표현)

③ 서브루틴의 복귀번지 저장

④ 부 프로그램(sub program)의 호출 = 함수 호출의 순서 제어

 

3) 순환적 프로그램을 처리하기 위한 요소

① 스택

② 복귀주소

③ 순환에서 탈출하는 조건

 

4) 삽입 알고리즘

 

Top = Top + 1

if Top > M then

           Overflow

else

           X(Top) = item

 

5) 삭제 알고그림

 

if Top = 0 then

           Underflow

else

           item = X(Top)

Top = Top - 1

 

 

(５) 큐 (Queue)

1) 큐의 정의

① rear라고 하는 리스트의 한쪽 끝에서 삽입이 일어나고 front라 부르는 반대쪽 끝에서 삭제가 일어나는 자료구조

② FIFO(first-in-first-out) 구조

 

2) 형태

3) 용도

① 운영체제의 작업 스케쥴링 등에 응용되는 것으로 가장 적합한 자료구조

② 키보드 버퍼 이용시

③ 스풀(spool) 운용시

 

 

(６) 데크 (Deque, Double Ended Queue)

1) 데크의 정의

① 서로 다른 방향에서 입출력이 가능한 구조 (삽입과 삭제가 양쪽 끝에서 일어남)

② 입력이 한쪽에서만 발생하고, 출력은 양쪽에서 일어날 수 있는 입력제한과 입력은 양쪽에서 일어나고 출력은 한곳에서만 이루어지는 출력제한이 있음.

③ 스택과 큐를 복합한 형태

④ 양 끝에서 삽입과 삭제가 가능하게 하도록 큐를 일반화한 것

 

 

제4항 비선형 구조(Non-Linear Structure)

(１) 트리 (Tree)

1) 트리의 정의

① 트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음과 같은 조건을 만족한다.

ü 트리에는 루트(root)라고 부르는 특별한 노드가 있다.

ü 트리는 사이클이 없는 그래프 (acyclic graph) 이며, 계층 구조를 이룬다.

 

② 노드와 간선으로 구성되어져 있고, 사이클이 없다.

③ Linked List로 표현할 때 가장 효율적임

④ 계층형 구조(hierarchical structure)를 나타내기 편리함

ü 연속적

 

 

2) 트리의 용어

 

 

① Node

ü Tree의 기본 구성요소

ü A, B, C, D, E, F, G, H, I, J, K, L, M

② 근노드(Root Node)

ü 가장 상위에 위치한 노드

ü A

③ 레벨(Level)

ü 근노드를 기준으로 특정 노드까지의 경로길이

ü K, L, M의 레벨은 4

④ 조상노드(Ancestors Node)

ü 특정 노드에서 루트에 이르는 경로상의 모든 노드

ü K의 조상노드는 E, B, A

⑤ 자식노드(Son Node)

ü 특정 노드에 연결된 다음 레벨의 노드

ü E의 자식노드는 K, L

⑥ 부모노드(Parent Node)

ü 특정 노드에 연결된 이전 레벨의 노드

ü K의 부모노드는 E

⑦ 형제노드(Sibling)

ü 같은 부모를 가진 노드

ü H의 형제노드는 I, J

⑧ 깊이(Depth, Height)

ü 트리의 최대 레벨

ü 트리의 깊이는 4

⑨ 차수(Degree)

ü 특정 노드에 연결된 자식노드의 수

ü D의 차수는 3

ü B의 차수는 2

⑩ 트리의 차수(Degree)

ü 트리의 노드중 최대 차수

ü 이 트리중에서 D의 차수는 3으로 가장 많다

⑪ 단말노드(Terminal Node, Leaf Node)

ü 트리의 제일 마지막에 위치한 노드

ü K, L, F, G, M, I, G

 

 

 

3) 트리의 특징

① 연결 리스트 구조로 표현 (포인터 이용)

 

 

4) 트리의 운행법(Traversal)

① 운행법 정의

ü 컴퓨터 기억 공간에 표현된 트리의 각 노드를 중복되지 않게 정해진 순서대로 전부 검색하여 트리의 정보에 관한 사항을 알고자 함

ü 이진 트리의 운행법은 산술식의 표기법과 관련됨

 

② 운행법 종류

 

ü Preorder (전위)

• root > left > right

• a, b, d, e, c, f, h, g

 

ü Inorder (중위)

• left > root > right

• d, b, e, a, h, f, c, g

 

ü Postorder (후위)

• left > right > root

• d, e, b, h, f, g, c, a

 

③ 수식의 표기법

ü 산술식을 계산하기 위해 기억공간에 기억시키는

ü 표기법의 종류

 

 

• 전위 표기법(Prefix notation)

- 연산자 > left 피연산자 > right 피연산자

- +ab

• 중위 표기법(Infix notation)

- left 피연산자 > 연산자 > right 피연산자

- a+b

• 후위 표기법(Postfix notation, reverse Polish notation)

- left 피연산자 > right 피연산자 > 연산자

- ab+

 

 

④ 표기법 변환

ü 현재의 표기법에서 우선순위가 가장 높은 두개의 피연산자와 한 개의 연산자를 바꾸고자 하는 표기법으로 바꿈, 바뀐 연산은 하나의 피연산자로 생각하고 위의 과정 반복

ü 중위표기법->후위표기법

• 5 + 2 / 7 ▶ 5+27/ ▶ 527/+

 

ü 중위표기법->전위표기법

• 5 + 2 / 7 ▶ 5+/27 ▶ +5/27

 

ü 후위나 전위 표기법에서 중위 표기법으로 바꾸려면 산술식의 앞쪽에서부터 연속된 2개의 피연산자와 하나의 연산자를 찾아 중위 표기법으로 바꾸는 과정을 반복함

 

 

 

5) 트리의 종류

① 이진트리

ü 정의

• Degree가 2이하로 구성된 트리

 

ü 특성

• 깊이가 k인 이진 트리의 최대노드의 수 : 2^k - 1

• 이진 트리의 레벨 I 에서 최대노드의 수 : 2^(i-1)

• n0 = n2 + 1 (n0: 이진 트리의 터미널노드, n2: 차수가 2인 노드수)

 

ü 종류

• 정이진 트리(FBT, Full Binary Tree)

- Depth(k), 전체노드 수 : 2ⁱ – 1

- 레벨마다 2^(i-1) 개 노드 가득

 

 

 

• 전이진 트리(CBT, Complete Binary Tree) or 완전 이진트리

- 정이진 트리의 각 노드에 붙인 1~n의 일련번호와 1:로 대응되는 트리

- 중간에 비워 있으면 안 됨

 

 

- 힙(Heap)

¡ 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료 구조

¡ 최대 힙(max heap)

부모 노드의 키 값이 자식 노드의  키 값보다 항상 크거나 같은 크기의 관계

 

 

¡ 최소 힙(min heap)

부모 노드의 값이 자식 노드의 키 값보다 항상 작거나 같은 크기의 관계

 

 

¡ 힙이 아닌 예

 

 

• 사향 이진 트리(SBT, Skewed Binary Tree)

- 이진트리가 한쪽 방향

- 한 방향으로만 자식노드를 가지며 기억장소의 낭비 심각

 

 

 

(２) 그래프(Graph)

1) 그래프의 정의

① 노드와 간선으로 구성되어져 있고, 사이클이 있다.

② 각각의 단위 정보를 링크로 연결하여 구조화시킨 자료 구조

③ 정점(vertex) : 노드들의 집합

④ 간선(edge) : 정점들 사이의 상호 연결의 집합, 임의의 점들의 쌍을 연결

 

2) 그래프의 유형

 

① 트리는 사이클이 없는 그래프

② 사이클(cycle)은 같은 정점에서 시작과 끝이 이어지는 경로

 

3) 인접행렬(Adjacency Matrix)

 

4) 인접 리스트

5) 최소비용 신장트리

① 가중치가 가장 작은 간선들을 사이클이 이루어지지 않도록 연결시켜 만든 그래프