<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>

Transcription

1 한국방송통신대학교컴퓨터과학과 2 학년자료구조 제 1 장기본개념 자료와정보 3 알고리즘 4 자료 data : 현실세계에서관찰이나측정을통해수집된값 value 이나사실 fact 특정한일을수행하는명령어들의유한집합 정보 information : 자료를처리 / 추출 process 해서얻어진유용한결과 입 출 력 : 외부에서제공되는자료가있을수있다력 : 적어도한가지결과를생성한다 I = P( D ) 명확성 : 각명령들은모호하지않아야한다 유한성 : 한정된수의단계뒤에는반드시종료한다 유효성 : 반드시실행가능해야한다

2 자료구조의범위 5 추상자료형 6 크고복잡한문제를단순화시켜쉽게해결하기위한방법 자료추상화 (Data Abstraction) 처리할자료, 연산, 자료형에대한추상화표현 자료 : 프로그램의처리대상이되는모든것을의미 연산 : 어떤일을처리하는과정. 연산자에의해수행 자료형 : 처리할자료의집합과자료에대해수행할연산자의집합 추상자료형 7 순환알고리즘 8 추상자료형 (ADT, Abstract Data Type) 자기자신을호출하여순환수행되는것 자료와연산자의특성을논리적으로추상화하여정의한자료형 함수에서실행해야하는작업의특성에따라일반적인호출방식보다재귀호출방식을사용하여함수를만들면프로그램의크기를줄이고간단하게작성 분할정복 divide and conquer : 어떤복잡한문제를직접간단하게풀수있는작은문제로분할하여해결 대표적인순환알고리즘 하노이탑 / 팩토리얼계산 / 피보나치순열

3 순환알고리즘 9 알고리즘의성능분석 10 재귀호출의예 ) factorial n 에대한 factorial : 1 부터 n 까지의모든자연수를곱하여구하는연산 동일한작업을수행하는여러알고리즘이있을경우, 가능한한적은메모리공간과적은실행시간을필요로하는알고리즘이바람직 fact(n) { if( n<=1 ) then return 1 else return ( n * fact( n-1 ) ) 공간복잡도 space complexity Sp = 고정공간 Sc + 가변공간 Se 시간복잡도 time complexity Tp = 컴파일시간 Tc + 실행시간 Te 연산시간의크기순서 빠름 / 좋음 느림 / 나쁨 제 2 장배열과레코드

4 배열 array 같은자료형을가진자료들을나열하여메모리에연속으로저장하여만든자료들의그룹 인덱스와값 <idex, value> 의쌍으로구성된집합 인덱스를이용하여원하는원소에직접접근가능 13 2 차원배열의표현 Array[m][n] m 은행 row / n 은열 column 행우선 row major order Array[i][j] 의상대적위치계산 Array[0][0] 의위치 + i*n + j 14 int a[2][3] 배열에서 a[1][1] a[0][0] 이 1000번지이고 int는 4byte일때, 행우선위치 : *3*4 + 1*4 = 1016번지 열우선위치 : *2*4 + 1*4 = 1012번지 2 차원배열의표현 15 다차원배열의표현 모든다차원배열은 1 차원배열로저장 16

5 순서리스트 17 배열을이용한다항식 18 원소들의순열 sequence, 원소들을일렬로정렬해놓은것 다항식의표현 각항의지수와계수의쌍에대한선형리스트 retrieve(l, i) : 리스트 L 의 i 번째원소를검색 예 ) A(x)=4x 3 +3x 2 +2 p1= (3,4, 2,3, 0,2) replace(l, x, y) : 리스트 L의원소 x를새로운원소 y로대체한다 delete(l, x) : 공백이아닌리스트 L로부터원소 x를제거한다 1 차원배열을이용한순차자료구조표현 차수가 n 인다항식을 (n+1) 개의원소를가지는 1 차원배열로표현 insert(l, i, x) : 새로운원소 x 를리스트 L 의지정된위치 i 에삽입한다 희소다항식 x 은메모리공간낭비 배열을이용한다항식 19 행렬의순차자료구조표현 20 2 차원배열을이용한순차자료구조표현 2 차원배열사용 다항식의각항에대한 < 지수, 계수 > 의쌍을 2 차원배열에저장 m n 행렬을 m 행 n 열의 2 차원배열로표현 예 ) B(x)=3x x + 4 의 2 차원배열표현 1 차원배열을사용하는방법보다메모리사용공간량감소 공간복잡도감소 프로그램성능향상!

6 희소행렬에대한 2 차원배열표현 희소행렬 B는배열의원소 56개중에서실제사용하는것은 0이아닌원소를저장하는 10개뿐이므로 46개의메모리공간낭비 희소행렬인경우에는 0이아닌원소만추출하여 < 행번호, 열번호, 원소 > 쌍으로배열에저장 제 3 장스택과큐 스택 Stack 23 스택추상자료형 24 접시를쌓듯이자료를차곡차곡쌓아올린형태의자료구조 스택에저장된원소는 top으로정한곳에서만접근가능 top 의위치에서만원소를삽입하므로, 먼저삽입한원소는밑에쌓이고, 나중에삽입한원소는위에쌓이는구조 마지막에삽입 (Last-In) 한원소는맨위에쌓여있다가가장먼저삭제 (First-Out) 됨 후입선출구조 (LIFO, Last-In-First-Out) ADT Stack 데이터 : 0 개이상의원소를가진유한순서리스트연산 : S Stack; item Element; createstack(s) ::= // 공백스택 S 를생성하는연산 isfull(s):: // 스택 S 가가득찼는지확인하는연산 push(s, item) ::= // 스택 S 의 top 에 item( 원소 ) 을삽입하는연산 isempty(s) ::= // 스택 S 가공백인지아닌지를확인하는연산 pop(s) ::= // 스택 S 의 top 에있는 item( 원소 ) 을스택 S 에서 // 삭제하고반환하는연산 End Stack

7 스택구조 25 스택에원소삽입 / 삭제 26 스택에서의삽입연산 void push( int *top, element item ) { if( *top >= MAX_STACK_SIZE - 1 ) { return stackfull( ); stack[ ++(*top) ] = item; 스택에서의삭제연산 element pop( int *top ) { if( *top = -1 ) { return stackempty( ); return stack[ (*top)-- ]; 스택의응용 : 역순문자열만들기 27 스택의응용 : 시스템스택 28

8 스택의응용 : 수식의괄호검사 29 스택의응용 : 수식의괄호검사 30 수식에포함되어있는괄호는가장마지막에열린괄호를가장먼저닫아주어야하는후입선출구조로구성되어있으므로, 후입선출구조의스택을이용하여괄호를검사 수식을왼쪽에서오른쪽으로하나씩읽으면서괄호검사 1 왼쪽괄호를만나면스택에 push 2 오른쪽괄호를만나면스택을 pop 하여마지막에 저장한괄호와같은종류인지를확인 수식의표기법 31 중위표기식의전위표기식변환방법 32 전위표기법 (prefix notation) 연산자를피연산자를앞에표기하는방법 예 ) +AB 1 수식의각연산자에대해서우선순위에따라괄호를사용하여다시표현한다 2 각연산자를그에대응하는왼쪽괄호의앞으로이동시킨다 중위표기법 (infix notation) 3 괄호를제거한다 연산자를피연산자의가운데표기하는방법 예 ) A+B 후위표기법 (postfix notation) 연산자를피연산자뒤에표기하는방법 예 ) AB+

9 중위표기식의후위표기식변환방법 33 스택을사용하여중위표기식을후위표기식으로변환 34 1 수식의각연산자에대해서우선순위에따라괄호를사용하여다시표현한다 2 각연산자를그에대응하는오른쪽괄호의뒤로이동시킨다 3 괄호를제거한다 ⑴ 왼쪽괄호를만나면무시하고다음문자를읽는다 ⑵ 피연산자를만나면출력한다 ⑶ 연산자를만나면스택에 push한다 ⑷ 오른쪽괄호를만나면스택을 pop하여출력한다 ⑸ 수식이끝나면, 스택이공백이될때까지 pop 하여출력한다 스택을사용하여중위표기식을후위표기식으로변환 35 큐 Queue 36 큐는한쪽에서는삽입만하고, 다른 ( 반대편 ) 에서는삭제만할수있는구조 삽입한순서대로원소가나열되어가장먼저삽입 (First-In) 한원소는맨앞에있다가가장먼저삭제 (First-Out) 된다 선입선출구조 (FIFO, First-In-First-Out) 선착순서브 (FCFS, First-Come-First-Serve)

10 큐추상자료형 37 선형큐 38 ADT Queue 데이터 : 0 개이상의원소를가진유한순서리스트연산 : Q Queue; item Element; createqueue() = // 공백큐를생성하는연산 isfull(q) ::= // 큐가가득찼는지확인하는연산 enqueue(q, item) = // 큐의 rear 에 item( 원소 ) 을삽입하는연산 isempty(q) = // 큐가공백인지아닌지를확인하는연산 dequeue(q) = // 큐의 front 에있는 item( 원소 ) 을큐에서 End Queue 1 차원배열을이용한큐 큐의크기 = 배열의크기 변수 front : 저장된첫번째원소의인덱스저장 변수 rear : 저장된마지막원소의인덱스저장 상태표현 초기상태 : front = rear = -1 공백상태 : front = rear 포화상태 : rear = n-1 (n : 배열의크기, n-1 : 배열의마지막인덱스 ) 큐구조 39 원형큐 40 선형큐의잘못된포화상태인식 큐에서삽입과삭제를반복하면서아래와같은상태일경우, 앞부분에빈자리가있지만 rear=n-1 상태이므로포화상태로인식하고더이상의삽입을수행하지않는다 1 차원배열을사용하면서논리적으로배열의처음과끝이연결되어있다고가정하고사용 원형큐

11 원형큐의구조 41 선형큐에원소삽입 / 삭제 42 front 와 rear 의위치가배열의마지막인덱스 n-1 에서논리적인다음자리인인덱스 0 번으로이동하기위해서나머지연산자 mod 를사용 3 4 = 0 3 ( 몫 =0, 나머지 =3) 3 mod 4 = 3 삽입위치 삭제위치 선형큐 rear = rear + 1 front = front + 1 원형큐 rear = (rear+1) mod n front = (front+1) mod n 사용조건 : 공백상태와포화상태구분을쉽게하기위해서 front 가있는자리는사용하지않고항상빈자리로둔다. 선형큐에서의삽입연산 void enqueue( int *rear, element item ) { if( *rear = MAX_QUEUE_SIZE - 1 ) { return isfull( ); queue[ ++( *rear ) ] = item; 선형큐에서의삭제연산 element dequeue( int *front, int rear ) { if( *front = rear ) { return isempty( ); return queue[ ++( *front ) ]; 원형큐에원소삽입 / 삭제 43 데크 Double Ended Queue 44 원형큐에서의삽입연산 void enqueue( int front, int *rear, element item ) { *rear = ( *rear + 1 ) % Queue_size; if( front = *rear ) { return isfull( ); queue[ ++( *rear ) ] = item; 스택과큐의동작을복합시킨방식으로수행하는선형리스트 원형큐에서의삭제연산 element dequeue( int *front, int rear ) { if( *front = rear ) { return isempty( ); *front = ( *front + 1 ) % Queue_size; return queue[ *front ]; 스크롤 Scroll : 한쪽으로삽입, 양쪽으로삭제 셸프 Shelf : 양쪽으로삽입, 한쪽으로삭제

12 45 배열을이용한순차표현 46 제 4 장연결리스트 장점 표현이간단, 원소의접근이빠르다 순차자료구조의문제점 리스트원소의순서가연속적인물리적주소로표현되기때문에, 원소를삽입하기위해서는 : 해당원소의위치뒤에있는모든원소를뒤로물리가나, 원소를삭제하기위해서는 : 앞으로당겨야만한다 정적구조인배열의적정크기를결정하기어렵다 : 오버플로문제발생, 과다한메모리할당으로저장공간의낭비와비효율 연결자료구조 (Linked Data Structure) 47 연결리스트의노드 48 자료의논리적인순서와물리적인순서가일치하지않는자료구조 각원소에저장되어있는다음원소의주소에의해순서가연결되는방식 물리적인순서를맞추기위한오버헤드가발생하지않음 여러개의작은공간을연결하여하나의전체자료구조를표현 크기변경이유연하고더효율적으로메모리를사용 연결자료구조에서하나의원소를표현하기위한단위구조 struct list_node { char data[10]; struct list_node *link; ; Struct list_node *p; 원소의값을저장 저장할원소의형태에따라서하나이상의필드로구성 데이터필드 (data field) 연결리스트 리스트를연결자료구조로표현한구조 연결하는방식에따라단순연결리스트와원형연결리스트, 이중연결리스트, 이중원형연결리스트 링크필드 (link field) 다음노드의주소를저장 포인터변수를사용하여주소값을저장

13 단순연결리스트에노드삽입 49 단순연결리스트에노드삽입 50 typedef struct list_node *list_pointer; typedef struct list_node { int data; list_pointer link; void insert( list_pointer t, list_pointer x, int y ) { list_node i; i = ( list_pointer )malloc( sizeof( list_node ) ); i->data = y; i->link = NULL; if( *t==null ) { *t=i; else { i->link = x->link; x->link = i; 단순연결리스트에노드삭제 51 단순연결리스트에노드삭제 52 typedef struct list_node *list_pointer; typedef struct list_node { int data; list_pointer link; void delete( list_pointer x, list_pointer y, list_pointer t ) { if( *y == NULL ) { t = t->link; else { y->link = x->link; free(x);

14 단순연결리스트노드출력 53 원형연결리스트 circular linked list 54 typedef struct list_node *list_pointer; typedef struct list_node { int data; list_pointer link; void print( list_pointer t ) { list_pointer p; p = t; while(p) { printf( %d, p->data ); p = p->link; 단순연결리스트에서마지막노드가리스트의첫번째노드를가리키게하여리스트의구조를원형으로만든연결리스트 원형연결리스트삽입 55 원형연결리스트삭제 56

15 이중연결리스트 doubly linked list 57 이중연결리스트에서노드삭제 58 양쪽방향으로순회할수있도록노드를연결한리스트 이중연결리스트의노드구조 두개의링크필드와한개의데이터필드로구성 llink(left link) 필드 : 왼쪽노드와연결하는포인터 rlink(right link) 필드 : 오른쪽노드와연결하는포인터 typedef struct list_node *list_pointer; typedef struct list_node { char data; struct list_node *rlink; struct list_node *llink; ; void ddelete( list_pointer x, list_pointer L ) { if( x==l ) { retrun no_more_nodes( ); x->llink->rlink = x->rlink; x->rlink->llink = x->llink; free(x); 이중연결리스트에서노드삭제 59 이중연결리스트에서노드삽입 60 typedef struct list_node *list_pointer; typedef struct list_node { char data; struct list_node *rlink; struct list_node *llink; ; void dinsert( list_pointer p, list_pointer x ) { p->llink = x; p->rlink = x->rlink; x->rlink->llink = p; x->rlink = p;

16 이중연결리스트에서노드삽입 61 다항식의연결자료구조표현 62 x 1. p- >llink=x p 2. p->rlink=x- >rlink 4. X- >rlink=p p 3. X->rlink->llink->p 다항식의덧셈연산 63 다항식의덧셈연산 64 덧셈 A +B =C 를단순연결리스트자료구조를사용하여연산 다항식 A 와 B, C 의항을지시하기위해서세개의포인터를사용 포인터 p : 다항식 A 에서비교할항을지시 포인터 q : 다항식 B 에서비교할항을지시 포인터 r : 덧셈연산결과만들어지는다항식 C 의항을지시

17 다항식의덧셈연산 65 다항식의덧셈연산 트리의예 68 제 5 장트리

18 트리에서사용하는용어 노드 (node) : 트리의원소 트리 A 의노드 : A, B, C, D, E, F, G, H, I, J, K, L 루트노드 (root node) : 트리의시작노드 트리 A 의루트노드 : A 간선 (edge) : 노드를연결하는선. 부모노드와자식노드를연결 차수 (degree) 노드의차수 : 노드에연결된자식노드의수 A의차수 =3, B의차수 =2, C의차수 =1 트리의차수 : 트리에있는노드의차수중에서가장큰값 트리 A의차수 =3 단말노드 ( 리프노드 ) : 차수가 0인노드. 자식노드가없는노드 69 트리에서사용하는용어 형제노드 (sibling node) : 같은부모노드의자식노드들 B, C, D 는형제노드 조상노드 : 간선을따라루트노드까지이르는경로에있는모든노드들 K 의조상노드 : F, B, A 서브트리 (subtree) : 부노노드와연결된간선을끊었을때생성되는트리 각노드는자식노드의개수만큼서브트리를가진다 자손노드 : 서브트리에있는하위레벨의노드들 B 의자손노드 : E, F, K, L 70 이진트리 트리의노드구조를일정하게정의하여트리의구현과연산이쉽도록정의한트리 이진트리의모든노드는왼쪽자식노드와오른쪽자식노드만을가진다 공백노드도자식노드로취급한다 0 노드의차수 2 71 포화이진트리 Full Binary Tree 모든레벨에노드가포화상태로차있는이진트리 루트를 1번으로정해진위치에대한노드번호를가짐 72

19 완전이진트리 Complete Binary Tree 73 순차자료구조를이용한이진트리구현 74 포화이진트리의노드번호 1 번부터 n 번까지빈자리가없는이진트리 이진트리의 1 차원배열에서의인덱스관계 이진트리의순차자료구조표현의단점 75 완전이진트리의단순연결리스트표현 76 편향이진트리의경우에사용하지않는배열원소에대한메모리공간낭비발생 트리의원소삽입 / 삭제에대한배열의크기변경어려움

20 전위순회 77 중위순회 78 A-B-D-H-E-I-J-C-F-G-K H-D-B-I-E-J-A-F-C-G-K - * A B / C D A * B C / D 후위순회 79 이진탐색트리 binary search tree 80 H-D-I-J-E-B-F-K-G-C-A 이진트리에탐색을위한조건을추가하여정의한자료구조 이진탐색트리의정의 ⑴ 모든원소는서로다른유일한키를갖는다 ⑵ 왼쪽서브트리에있는원소의키들은그루트의키보다작다 ⑶ 오른쪽서브트리에있는원소의키들은그루트의키보다크다 ⑷ 왼쪽서브트리와오른쪽서브트리도이진탐색트리이다 A B * C D / -

21 히프 heap 81 순차자료구조를이용한히프의구현 82 완전이진트리에있는노드중에서킷값이가장큰노드나킷값이가장작은노드를찾기위해서만든자료구조 부모노드와자식노드를찾기쉬운 1 차원배열의순차자료구조이용 1 차원배열을이용한히프의표현예 최대히프 (max heap) 킷값이가장큰노드를찾기위한완전이진트리 { 부모노드의킷값 자식노드의킷값 루트노드 : 킷값이가장큰노드 최소히프 (min heap) 킷값이가장작은노드를찾기위한완전이진트리 { 부모노드의킷값 자식노드의킷값 루트노드 : 킷값이가장작은노드 히프에자료삽입 83 히프에자료삽입 84

22 히프자료삭제 제 6 장그래프 그래프 graph 87 무방향그래프 undirected graph 88 선형자료구조나트리자료구조로표현하기어려운多 : 多의관계를가지는원소들을표현하기위한자료구조 두정점을연결하는간선의방향이없는그래프 정점 V i 와정점V j 을연결하는간선을 ( V i, V j ) 로표현 ( V i, V j ) 와 ( V j, V i ) 는같은간선을의미한다. 그래프 G 객체를나타내는정점 (vertex) 과객체를연결하는간선 (edge) 의집합 G = (V, E) V 는그래프에있는정점들의집합 E 는정점을연결하는간선들의집합 V(G1)={A, B, C, D E(G1)={(A,B), (A,D), (B,C), (B,D), (C D) V(G2)={A, B,C E(G2)={(A,B), (A,C), (B C)

23 방향그래프 directed graph 89 그래프의구현 : 인접행렬 90 간선이방향을가지고있는그래프 정점 V i 에서정점 V j 를연결하는간선즉, V i V j 를 < V i, V j > 로표현 V i 를꼬리 (tail), V j 를머리 (head) 라고한다. < V i, V j > 와 < V j, V i > 는서로다른간선을의미한다. E(G3)={<A,B>, <A,D>, <B,C>, <B,D>, <C,D> E(G4)={<A,B>, <A,C>, <B,A>, <B,C> 그래프의구현 : 인접행렬 91 그래프의구현 : 인접리스트 92

24 그래프의구현 : 인접리스트 93 깊이우선탐색 depth first search : DFS 94 시작정점의한방향으로갈수있는경로가있는곳까지깊이탐색해가다가더이상갈곳이없게되면, 가장마지막에만났던갈림길간선이있는정점으로되돌아와서다른방향의간선으로탐색을계속반복하여결국모든정점을방문하는순회방법 가장마지막에만났던갈림길간선의정점으로가장먼저되돌아가서다시깊이우선탐색을반복해야하므로후입선출구조의스택사용 위아래위아래 깊이우선탐색 95 깊이우선탐색 96

25 깊이우선탐색 97 너비우선탐색 breadth first search : BFS 98 시작정점으로부터인접한정점들을모두차례로방문하고나서, 방문했던정점을시작으로하여다시인접한정점들을차례로방문하는방식 가까운정점들을먼저방문하고멀리있는정점들은나중에방문하는순회방법 인접한정점들에대해서차례로다시너비우선탐색을반복해야하므로선입선출의구조를갖는큐를사용 좌에서우로좌에서우로 너비우선탐색 99 너비우선탐색 100

26 너비우선탐색 101 최소비용신장트리 102 무방향가중치그래프에서신장트리를구성하는간선들의가중치합이최소인신장트리 가중치그래프의간선에주어진가중치 비용이나거리, 시간을의미하는값 최소비용신장트리를만드는알고리즘 Kruskal 알고리즘 : 여기저기 Prime 알고리즘 : 이어가기 Kruskal 알고리즘 103 Kruskal 알고리즘 104

27 Prime 알고리즘 105 Prime 알고리즘 106