자료구조 자료구조의 개요 배열 선형 리스트 스택 큐 트리.

Presentation on theme: "자료구조 자료구조의 개요 배열 선형 리스트 스택 큐 트리."— Presentation transcript:

1 자료구조 자료구조의 개요 배열 선형 리스트 스택 큐 트리

2 자료구조에 대해 살펴본다. 배열 구조에 대해 살펴본다. 연결 리스트 구조에 대해 살펴본다. 스택 구조에 대해 살펴본다. 큐 구조에 대해 살펴본다. 트리 구조에 대해 살펴본다.

3 자료구조 대표적인 데이터 구조 적절한 데이터 구조 프로그램에 의해 쉽게 이용되도록 구성된 데이터들간의 논리적 관계 배열
연결 리스트 스택 큐 트리 적절한 데이터 구조 데이터의 추가, 삭제, 검색을 효율적으로 수행하고, 데이터 구조를 간결하게 표현할 수 있는 것

4 배열 크기가 n인 배열 arr (C 언어인 경우) 연결 리스트
같은 데이터 형의 요소들이 동일한 크기로 순서를 갖고 나열되어 있는 집합 크기가 n인 배열 arr (C 언어인 경우)  연결 리스트 배열이름과 첨자 배열은 첨자의 수에 따라 구분되는데, 첨자를 1개 사용하면 1차원 배열, 2개 사용하면 2차원 배열, 3개의 사용하면 3차원 배열이라 함 [그림 7-1] 크기가 n인 배열 arr [그림 7-2] 배열이름과 첨자

5 1차원 배열 첨자를 하나만 사용하는 배열로 같은 데이터 형의 변수가 일직선으로 이루어짐 배열의 크기
1차원 배열 arr[i:n]의 크기 (i는 첫 번째 요소의 첨자고, n은 마지막 요소의 첨자) 1차원 배열 arr[1:10]의 크기는 로 10이 된다. [그림 7-3] 1차원 배열의 표현

6 1차원 배열 arr[i]의 주소 1차원 배열 arr[n]에서 첫 번째 요소의 첨자가 a이고 시작 주소가 base, 요소의 크기가 size라 할 때 arr[i]의 주소 arr[5]의 주소 (arr[0]의 시작 주소는 200이고, 각 요소의 크기는 4바이트라고 가정) 시작 주소가 200이므로 base는 200이고, i는 5, 배열의 첨자가 0으로 시작되므로 a는 0, 요소의 크기인 size는 4 [그림 7-4] 1차원 배열 요소의 주소

7 다차원 배열 2차원 배열 첨자 두 개를 사용하는 배열로, 같은 데이터형의 변수가 행(row)과 열(column)을 나타내는데, 첫 번째 첨자는 행을, 두 번째 첨자는 열을 나타냄 2차원 배열 arr[i:n][j:m]의 크기 (i와 j는 첫 번째 요소의 행과 열의 첨자고, n과 m은 마지막 요소의 행과 열의 첨자) 2차원 배열 arr[1:3][1:2]의 크기는 i와 j가 1이고, n이 3, m이 2이므로 배열의 크기는 6이 됨 [그림 7-5] 2차원 배열의 표현

8 저장 방식은 행 중심 저장 방식과 열 중심 저장 방식
[그림 7-6] 2차원 배열의 두 가지 저장 방식

9 2차원 배열 arr[n][m]에서 arr[i][j]의 주소 (첫 번째 요소의 행과 열의 첨자가 a이고 시작 주소가 base, 요소의 크기가 size라 할 때)
2차원 배열 요소의 주소 [그림 7-7] 2차원 배열 요소의 주소

10 a[2][0]의 주소 (배열은 a[3][2]이므로 n이 3, m이 2, 행과 열의 첨자는 0, 시작 주소는 200, 각 요소의 크기는 4)
행(m) 중심 저장 방식의 a[2][0] 주소 열(n) 중심 저장 방식의 a[2][0] 주소 arr[i:n][j:m]의 크기 (i와 j는 첫 번째 요소의 행과 열의 첨자고, n과 m은 마지막 요소의 행과 열의 첨자)

11 선형 리스트 구현하는 방법 : 연속 리스트와 연결 리스트 연속 리스트의 예 데이터 6 삽입
어떤 순서에 의해 나열된 데이터가 여러 개인 구조 구현하는 방법 : 연속 리스트와 연결 리스트 연속 리스트의 예 데이터 6 삽입 [그림 7-8] 연속 리스트의 예 [그림 7-9] 데이터 6 삽입

12 데이터 5 삭제 연속 리스트의 삽입과 삭제 동작에는 데이터를 옮기는 시간이 필요 [그림 7-10] 데이터 5 삭제

13 연결 리스트 노드 연결 리스트 예 각 데이터들을 포인터로 연결하여 관리하는 구조
 각 노드는 데이터를 저장하는 데이터 영역과 다음 데이터가 저장된 노드를 가리키는 포인터 영역으로 구성 각 노드들은 주기억장치의 어느 위치에 저장되든 상관없고, 단지 각 노드들이 포인터에 의해 연결되어 있기만 하면 됨 연결 리스트 예 [그림 7-11] 노드의 구조 [그림 7-12] 연결 리스트의 예

14 데이터 영역에 두 개의 데이터가 있는 연결 리스트
시작위치 [그림 7-13] 데이터 영역에 두 개의 데이터가 있는 연결 리스트

15 단순 연결 리스트 각 노드에 하나의 포인터 영역을 갖고 있는 연결 리스트
데이터 삽입 - 데이터 1인 노드와 데이터 3인 노드 사이에 데이터 2를 삽입하는 과정 ① 데이터 2를 저장할 노드를 생성하고, 데이터 영역에 2를 저장한다.

16 ② 데이터 1인 노드의 포인터 영역이 가리키는 곳(데이터 3인 노드)을 새롭게 생성된 데이터 2인 노드의 포인터 영역이 가리키게 한다. 그러면 데이터 2인 노드가 데이터 3인 노드를 가리키게 된다. ③ 데이터 1인 노드의 포인터 영역이 새롭게 생성된 데이터 2인 노드를 가리키게 한다. 결국 데이터 2의 삽입 동작이 완료된다.

17 데이터 삭제 데이터 3인 노드를 삭제하는 과정 ① 데이터 3인 노드의 포인터 영역이 가리키는 곳(데이터 5인 노드)을 바로 앞 노드(데이터 1인 노드)의 포인터 영역이 가리키게 함 ② 사용하지 않는 노드는 주기억장치에서 삭제

18 원형 연결 리스트 단순 연결 리스트는 임의의 노드에서부터 이전에 위치한 노드에 접근할 수 없고, 다시 헤드 포인터로부터 시작해야 하는 문제점 마지막 노드의 포인터 영역이 첫 번째 노드를 가리킨다. 원형 연결 리스트의 예 [그림 7-14] 원형 연결 리스트

19 이중 연결 리스트 단순 연결 리스트에서는 각 노드가 다음 노드를 가리키고 있으나 이전 노드를 가리키지 않아 이전 노드로 접근할 수가 없는 제한점 각 노드에 다음 노드를 가리키는 포인터 영역만이 아니라 이전 노드를 가리키는 포인터 영역이 있음 이중 연결 리스트의 노드 이중 연결 리스트의 예 [그림 7-15] 이중 연결 리스트의 노드 [그림 7-16] 이중 연결 리스트

20 데이터 삽입 데이터 1인 노드와 데이터 3인 노드 사이에 데이터 2를 삽입
① 데이터 2를 저장할 노드를 생성하고, 데이터 영역에 2를 저장

21 ② 데이터 1인 노드의 다음 노드 포인터 영역이 가리키는 곳(데이터 3인 노드)을 새롭게 생성된 데이터 2인 노드의 다음 노드 포인터 영역이 가리키게 함

22 ③ 새롭게 생성된 데이터 2인 노드의 이전 노드 포인터 영역이 데이터 1인 노드를 가리키게 함

23 ④ 데이터 3인 노드의 이전 노드 포인터 영역이 새롭게 생성된 데이터 2인 노드를 가리키게 함

24 ⑤ 데이터 1인 노드의 다음 노드 포인터 영역이 새롭게 생성된 데이터 2인 노드를 가리키게 함

25 데이터 삭제 데이터 3인 노드를 삭제 ① 데이터 3인 노드의 다음 노드 포인터 영역이 가리키는 곳을 데이터 1인 노드의 다음 노드 포인터 영역이 가리키게 함

26 ② 데이터 3인 노드의 이전 노드 포인터 영역이 가리키는 곳을 데이터 5인 노드의 이전 노드 포인터 영역이 가리키게 함
③ 데이터 3인 노드를 주기억장치에서 삭제

27 이중 원형 연결 리스트 이중 연결 리스트의 첫 번째 노드의 이전 노드 포인터 영역이 마지막 노드를 가리키게 하고, 마지막 노드의 다음 노드 포인터 영역이 첫 번째 노드를 가리키도록 구성 이중 원형 연결 리스트의 예 [그림 7-17] 이중 원형 연결 리스트

28 스택 데이터의 삽입과 삭제가 한쪽 방향에서만 일어나는 구조
가장 나중에 삽입된 데이터가 가장 먼저 삭제되므로 후입 선출(LIFO : Last-In First-Out)이라고도 함 [그림 7-18] 동전 케이스 [그림 7-19] 스텍 구조

29 배열로 구현한 스택 top은 데이터 삽입과 삭제가 이루어지는 배열의 첨자. 초기 상태의 top은 0 데이터 삽입
스택에 데이터 10을 삽입 [그림 7-20] 배열로 구현한 스텍 구조 [그림 7-21] 스택에 10을 삽입

30 4개의 데이터를 추가로 삽입하면 다음과 같이 스택이 가득 차게 되고, top은 5가 됨 : 더 이상 데이터를 삽입할 수 없음
[그림 7-22] 스택이 가득 참

31 데이터 삭제 데이터 삭제는 top을 1 감소시키기만 하면 됨
사실 stack[1]에 저장된 20은 지워지지는 않았지만, 이 상태에서 새로운 데이터를 삽입하면 stack[1]에 저장되어 20이 지워지게 된다. [그림 7-23] 테이터 삭제 [그림 7-24] 데이터 삭제 후

32 또 다시 데이터를 삭제하면 다음과 같이 top이 0이 됨 : 더 이상 데이터를 삭제할 수 없음
[그림 7-25] 스택이 비어 있음

33 연결 리스트로 구현한 스택 데이터 삽입 데이터 30을 삽입
① 데이터 30을 저장할 노드를 생성하고, 데이터 30을 데이터 영역에 저장 ② 새롭게 생성된 데이터 30인 노드의 포인터 영역이 top이 가리키는 곳(데이터 20인 노드)을 가리키게 함

34 ③ top이 새롭게 생성된 데이터 30인 노드를 가리키게 함

35 데이터 삭제 ① top이 가리키는 노드의 포인터 영역이 가리키는 곳을 10를 가리키게 함
② 데이터 20인 노드를 주기억장치에서 삭제

36 큐 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조
가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO : First-In First-Out)이라고도 함 [그림 7-27] 마트의 계산대 [그림7-28] 큐 구조

37 배열로 구현한 큐 front는 첫 번째 데이터가 저장된 배열의 첨자고, rear는 새로운 데이터가 삽입될 배열의 첨자 (초기 상태이므로 front와 rear는 0) 데이터 삽입 데이터 10을 삽입 [그림 7-29] 배열로 구현한 큐 구조 [그림 7-30] 큐에 10을 삽입

38 계속해서 4개의 데이터를 삽입하면 다음과 같이 큐가 가득 차게 되고, rear는 5 : 더 이상 데이터를 삽입할 수 없음
[그림 7-31] 큐가 가득 참

39 데이터 삭제 데이터 삭제 전 front를 1 증가 : front를 1 증가시켜 front는 1이 된다
[그림 7-32] 데이터 삭제 전 [그림 7-33] 데이터 삭제 후 [그림 7-34] 큐가 비어 있음

40 원형 큐 큐의 앞부분이 비어있음에도 rear가 큐의 크기와 같아 데이터를 삽입할 수 없는 문제점 [그림 7-35] 삽입 불가
[그림 7-36] 앞으로 이동

41 연결 리스트로 구현한 큐 문제점을 해결하는 가장 바람직한 방법 중 하나가 원형 큐 front는 가장 먼저 삽입된 노드를 가리킴
처음과 끝을 연결한 구조로, 마지막 공간이 다음 큐의 시작점이 된다. 연결 리스트로 구현한 큐 front는 가장 먼저 삽입된 노드를 가리킴 [그림 7-37] 원형 큐 [그림 7-38] 연결 리스트로 구현한 큐 구조

42 데이터 삽입 ① 데이터 30을 저장할 노드를 생성하고, 데이터 30을 데이터 영역에 저장하고, 포인터 영역에 NULL을 저장
② 연결 리스트의 마지막 노드(데이터 20인 노드)의 포인터 영역이 새롭게 생성된 데이터 30인 노드를 가리키게 함

43 데이터 삭제 ① front가 가리키는 노드의 포인터 영역이 가리키는 곳을 20를 가리키게 함
② 데이터 10인 노드를 주기억장치에서 삭제

44 트리(tree) 구조 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합 대학의 조직도 [그림 7-39] J 대학의 조직도

45 트리 구조로 나타낸 대학의 조직도 원을 ‘노드(node)’ 노드와 노드를 연결하는 선을 ‘링크(link)’
가장 위에 위치한 노드를 ‘루트 노드(root node)’ 윤리교육과, 국어교육과 노드와 같이 마지막에 위치한 노드를 ‘단말 노드(terminal node)’ 또는 ‘리프 노드(leaf node)’ [그림 7-40] J 대학 조직도에 대한 트리 구조

46 트리 구조로 나타낸 대학의 조직도 [그림 7-41] 트리

47 트리 구조로 나타낸 대학의 조직도 트리에서 임의의 노드를 선택하면 이 노드와 이 노드 아래에 있는 노드들은 다시 트리 구조가 된다. 이런 구조를 ‘서브 트리(subtree)’라 함 임의의 노드의 조상과 자손을 지칭할 수 있는데, 임의의 노드 바로 위에 있는 노드를 ‘부모 노드(parent node)’라 하고, 바로 아래에 있는 노드를 ‘자식 노드(children node)’라 함 노드 B의 부모 노드는 노드 A고, 노드 B의 자식 노드는 노드 E, 노드 F 그리고 노드 G다. 그리고 같은 부모 노드를 가지는 노드들을 ‘형제 노드(sibling node)’라 함 루트 노드에서 임의의 노드까지 방문한 노드의 수를 ‘레벨(level)’이라 함 트리의 최대 레벨을 ‘깊이(depth)’라 함

48 이진 트리 모든 노드들의 자식 노드가 2개 이하인 트리
서브 트리가 두 개 이하기 때문에 서브 트리는 왼쪽 서브 트리와 오른쪽 서브 트리로 구분 완전 이진 트리(complete binary tree) : 단말 노드를 제외한 나머지 노드가 두 개의 자식 노드를 가지고 있는 트리 [그림 7-43] 완전 이진 트리 [그림 7-42] 이진 트리

49 포화(정) 이진 트리(full binary tree) : 모든 노드가 채워진 이진 트리
[그림 7-44] 포화 이진 트리

50 이진 트리의 표현 배열이나 연결 리스트를 이용해서 구현할 수 있음 연결 리스트로 구현한 이진 트리의 각 노드
[그림 7-45] 이진 트리의 노드 [그림 7-46] 이진 트리

51 이진 트리의 표현 배열이나 연결 리스트를 이용해서 구현할 수 있음 연결 리스트로 구현한 이진 트리의 각 노드
[그림 7-47] 연결 리스트로 나타낸 이진 트리

52 이진 트리의 순회 순회하는 방법 전위 순회 동작 과정 이진 트리의 모든 노드를 특정한 순서대로 한 번씩 방문하는 것
전위(preorder) 순회 중위(inorder) 순회 후위(postorder) 순회 전위 순회 동작 과정 ① 순회는 루트 노드부터 시작하므로 루트 노드 A를 가장 먼저 방문

53 ② 루트 노드 A의 왼쪽 서브 트리를 방문해야 한다. 그러므로 A 노드의 왼쪽 서브 트리에서 노드인 B를 방문
③ 노드 B의 왼쪽 서브 트리를 방문해야 한다. 그러므로 노드 B의 왼쪽 서브 트리에서 D 노드를 방문

54 ④ 노드 B의 왼쪽 서브 트리에 대한 방문이 끝났으므로 노드 B의 오른쪽 서브. 트리를 방문한다
④ 노드 B의 왼쪽 서브 트리에 대한 방문이 끝났으므로 노드 B의 오른쪽 서브 트리를 방문한다. 그러므로 노드 B의 오른쪽 서브 트리의 노드인 E 방문 ⑤ 노드 E의 왼쪽 서브 트리에서 노드인 F를 방문

55 ⑥ 루트 노드 A의 왼쪽 서브 트리에 대한 모든 방문이 끝났으므로 노드 A의오른쪽 서브 트리를 방문해야 한다
⑥ 루트 노드 A의 왼쪽 서브 트리에 대한 모든 방문이 끝났으므로 노드 A의오른쪽 서브 트리를 방문해야 한다. 그러므로 노드 A의 오른쪽 서브 트리 에서 노드인 C를 방문. 모든 노드의 방문이 완료된다.

56 중위 순회 동작 과정 ② 노드 B의 왼쪽 서브 트리를 방문. 그러므로 노드 B의 왼쪽 서브 트리의 노드 D를 방문
① 루트 노드의 왼쪽 서브 트리를 방문

57 ③ 노드 B의 왼쪽 서브 트리에 대한 방문이 끝났으므로 루트 노드인 B 방문
④ 노드 B의 오른쪽 서브 트리를 방문. 노드 B의 오른쪽 서브 트리의 루트 노드는 E

58 ⑤ 노드 E의 왼쪽 서브 트리를 방문해야 하므로 노드 F를 방문
⑥  노드 E의 왼쪽 서브 트리에 대한 방문이 끝났으므로 루트 노드인 E를 방문

59 ⑦ 노드 A의 왼쪽 서브 트리에 대한 방문이 모두 끝났으므로 노드 A를 방문
그러므로 노드 C를 방문. 모든 노드의 방문이 완료

60 후위 순회 동작 과정 ① 노드 A의 왼쪽 서브 트리를 방문
② 노드 B의 왼쪽 서브 트리를 방문한다. 그러므로 노드 B의 왼쪽 서브 트리의 노드 D를 방문

61 ③ 노드 B의 왼쪽 서브 트리에 대한 방문이 끝났으므로 노드 B의 오른쪽 서브 트리를 방문
③ 노드 B의 왼쪽 서브 트리에 대한 방문이 끝났으므로 노드 B의 오른쪽 서브 트리를 방문. 노드 B의 오른쪽 서브 트리의 루트 노드는 E ④ 노드 E의 왼쪽 서브 트리를 방문해야 하므로 노드 F를 방문

62 ⑤ 노드 E의 왼쪽 서브 트리에 대한 방문이 끝났으므로 오른쪽 서브 트리를 방문해야 하는데 없으므로 노드 E를 방문
⑥ 노드 B 의 왼쪽 서브 트리와 오른쪽 서브 트리에 대한 방문이 끝났으므로 노드 B를 방문

63 ⑦ 노드 A의 왼쪽 서브 트리에 대한 방문이 끝났으므로 오른쪽 서브 트리 방문. 그러므로 노드 C를 방문
⑧ 노드 A의 왼쪽 서브 트리와 오른쪽 서브 트리에 대한 방문이 끝났으므로 노드 A를 방문. 모든 노드의 방문이 완료

64 이진 탐색 트리 데이터의 삽입, 삭제, 검색 등이 자주 발생하는 경우에 효율적인 구조
같은 데이터를 갖는 노드는 없어야 하며, 왼쪽 서브 트리에 있는 모든 데이터는 현재 노드의 데이터보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 데이터는 현재 노드의 데이터보다 크다. [그림 7-48] 이진 탐색 트리

65 데이터 삽입 데이터가 9인 노드를 삽입 ① 삽입할 위치를 루트 노드부터 찾아가는데, 삽입할 노드의 데이터가 비교하는 노드의 데이터보다 작으면 왼쪽 서브 트리로 진행하고, 크면 오른쪽 서브 트리로 진행 ② 단말 노드의 데이터 8보다 삽입할 노드의 데이터 9가 크므로 단말 노드의 오른쪽 자식 노드로 삽입. 만약 삽입할 노드의 데이터가 작으면 왼쪽 자식 노드로 삽입

66 데이터 삭제 삭제할 노드가 단말 노드인 경우 삭제될 노드를 가리키는 링크를 제거 삭제할 노드의 오른쪽 자식 노드가 없는 경우
삭제되는 노드의 부모 노드가 삭제되는 노드의 왼쪽 자식 노드를 가리키게 함

67 삭제할 노드의 오른쪽 자식 노드는 있으나 오른쪽 자식 노드의 왼쪽 자식 노드가 없는 경우
부모 노드(A)가 삭제될 노드(B)의 오른쪽 자식 노드(C)를 가리키게 하고, 삭제될 노드의 왼쪽 자식 노드(D)를 삭제될 노드의 오른쪽 자식 노드(C)의 왼쪽 자식 노드로 둠

68 그 외의 경우 오른쪽 자식 노드도 있고, 오른쪽 자식 노드의 왼쪽 자식 노드도 있는 경우로, 이런 노드를 삭제할 때는 삭제될 노드(A)의 오른쪽 서브 트리에서 가장 작은 키를 갖는 노드(B)를 삭제할 노드의 위치로 옮기고 옮길 노드(B)의 오른쪽 자식 노드(C)가 있으면 이 노드(C)를 옮길 노드(B)의 부모 노드(D)의 왼쪽 자식 노드로 둠

69 그 외의 경우 옮길 노드의 오른쪽 자식 노드가 있는 경우로, 데이터 3인 노드를 삭제하려면 오른쪽 서브 트리에서 가장 작은 키를 가진 데이터 4인 노드가 데이터 3인 노드의 위치로 옮기고, 데이터 4인 노드의 오른쪽 자식 노드(데이터 5인 노드)가 있으므로 이를 데이터 4인 노드의 부모 노드인 데이터 6인 노드의 왼쪽 자식 노드로 둠

70