CH06)자료구조.hwp

Transcription

1 자료구조 (Data Structure) ) 자료구조의정의 프로그램에서사용하기위한자료를저장매체에저장하는방법및각자료간의관계, 처리방법을분석하는이론 자료의표현과연산의기초과학이다. 일련의자료들을조직화, 구조화시킨다. 모든자료구조에대하여연산처리가가능하다. 구현된자료구조에따라프로그램실행시간이다르다. 2) 자료구조의목적 ( 이유 ) 실제적으로물리적인저장장치는일정한규칙으로하나의선형형태로존재하기때문에그특성에맞게적절한형태로 자료를저장배치하여원하는데이터의검색및관리를보다효율적으로운영하기위해서사용된다. 3) 자료구조의이용에따른분류 자료를어떻게기억장치에저장할것인가? 어떤순서로정리할것인가? 기록된자료에서원하는것을어떻게찾아낼것인가? 기록된자료에색인을이용한검색방법을구현할수있는가? 파일편성 : 데이터를기억장치에저장할때파일구조 정렬 : 기억장치내의데이터를일정순서로나열 검색 : 기억장치에서원하는데이터를찾는다. 인덱스 : 파일에서특정데이터를빠르게찾기위한색인 4) 자료구조의분류 선형구조 ( 순차리스트 ) 리스트 배열 선형리스트 연결리스트 스택 큐 데크 포인트사용 : 연결리스트 미사용 : 선형리스트, 배열, 스택, 큐, 데크 비선형구조 ( 비순차리스트 ) 트리 그래프 선형구조 : 배열 (Array) ) 배열의개념 배열은동일한크기와형식으로구성된연속적인기억공간을의미한다. 2) 배열의종류 차원배열 [ ]

2 배열요소 A() A(2) A(3) A(4) -> (Data) A B C D 22차원배열 A(,) A(2,) A(,2) A(2,2) A(,3) A(2,3) A(,4) A(2,4) A(N,M) 의배열 - 행우선기준의위치찾기 : (i-)n + j - 열우선기준의위치찾기 : (j-)m + I A(3,) A(3,2) A(3,3) A(3,4) A(4,) A(4,2) A(4,3) A(4,4) [i 는행, j 는열 ] 33차원배열 3차원배열의주소 : A(L,M,N) 에서 A(i,j,k) 의주소 행우선 : α+(i-)mn + (j-)n + (k-) 열우선 : α+(k-)lm + (j-)l + (i-) 4배열의응용 스트링 (String) : 연속적인저장공간에기억된문자열 희소행렬 (Sparse Matrix) : 각원소의값이 "0" 인항들이많은행렬 선형구조 : 스택 (Stack) ) 스택의주요특성 리스트의한쪽으로만삽입과삭제가이루어진다. 후입선출방식 (LIFO: Last In First Out) 스택포인터 : 마지막데이터의기억공간을가르킨다. 스택의활용도 부프로그램호출시복귀주소저장 함수호출의제어순서 인터럽트발생후복귀주소 후위표기법 (Postfix Notation) 으로표현된산술식을연산 0주소지정방식명령어의저장 재귀 (Recursive) 프로그램순서제어 컴파일러를이용한프로그램언어번역 스택의모양과구현 삽입 (PUSH) 5 삭제 (PUSH) if top n then overflow else top = top + stack(top) 삽입 이미자 최불암 이순재 Top(Stack Pointer) Bottom if top 0 then underflow else 삭제 stack(top) top = top- [ 2 ]

3 선형구조 : 큐 (Queue) ) 큐의주요특성 한쪽에는반드시삽입, 또다른한쪽에는반드시삭제가이루어진다 선입선출 (FIFO: First In First Out) 큐의구조는삽입 (rear) 과삭제 (front) 시앞으로만이동하기때문에한번사용한기억공간은사용할수없다. 환형큐 ( 원형 ) 로보완 큐의활용도 운영체제의운영스케줄링 키보드입력버퍼 스풀 (spool) 기능운용 큐의모양과구현 삭제 (DROP) 이순재 최불암 이미자 삽입 (PUSH) Frot Pointer( 삭제 ) Rear Pointer( 삽입 ) if rear = n then overflow else rear = rear + Queue(rear) 삽입 if front = rear then underflow else front = front + 삭제 Queue(front) 선형구조 : 데크 (Deque: Double Ended Queue) ) 데크의주요특성 스택과큐의장점을조합한구조로삽입및삭제가모두일어난다. 삽입과삭제가양쪽모두일어나므로포인터 ( 지시부분 ) 는두개다. 출력 입력입력 출력 입력은한쪽에서출력은양쪽에서일어나는입력제한 (Scroll) 출력 입력 출력 출력은한쪽에서입력은양쪽에서일어나는출력제한 (Shelf) 입력 입력 출력 선형구조 : 리스트 (List) ) 선형리스트 (Linear) 배열과같이데이터가차례차례자료의빈공간없이연속적인기억장소에저장되는리스트 연접리스트 (Dense List) 또는축자구조 (Sequential List) 라고도한다. 주요특징 [ 3 ]

4 가장간단한자료구조이며접근속도가빠르다. 중간에자료삽입시에는반드시연속된빈공간이있어야한다. 기억장소의밀집도가가장높다 ( 연속적인저장 ) 자료의삽입과삭제시자료의이동이요구되므로작업이불편하다. ( 중간이꽉차있음 ) n개의자료가있을때 - 삽입시평균이동횟수 = (n + ) / 2 - 삭제시평균이동횟수 = (n - ) / 2 2) 연결리스트 (Linked) 데이터의저장순서는상관없지만자료항목의순서에따라각노드에포인터를두어서로연결시키는자료구조 포인터는프론트포인터 ( 처음위치 ) 와널포인터 ( 마지막노드, 자료없음 ) 가있다. 노드는데이터부분과다음의노드를나타내는포인터로구성된기억공간이다. 주요특징 노드의삽입및삭제가용이 연속적인저장공간이없어도저장가능 ( 메모리와에독립적 ) 연결을위한포인터 ( 링크 ) 부분이요구되며그에따른기억공간의증가 ( 효율이적음 / 접근속도저하 ) 희소행렬 ( 중복값 ) 을이와같이표현하면자원이절약됨 비선형구조 : 트리 (Tree) 트리의전체구성 근 (Root) 노드 A LEVEL 노드 B C D LEVEL 2 E F G H I J LEVEL 3 K L N LEVEL 4 ) 트리구조관련용어 정점 ( 노드 ) 과선분 ( 가지 ) 을이용한사이클이이루어지지않는형태로조직도, 연산수식의자료표현 노드 : 트리의기본요소이며자료항목및다른항목과의연결가지를합친전체 근 (Root) 노드 : 트리구조상의가장최상위노드 노드디그리 (Degree)( 노드차수 ): 각노드에서뻗어나온가지수 단말노드 (Terminal)( 잎 [leaf] 노드 ): 자식이없는노드 ( 디그리가 0이다.) 비단말노드 (Non-terminal): 자식이하나이상인노드 조상노드 (Ancestors: 임의의노드에서근노드까지경로중에있는노드 자식노드 (Son): 임의의노드의하위 ( 다음 ) 노드 부모노드 (Parent): 임의의노드상위 ( 이전 ) 노드 형제노드 (Brother): 동일한부모를가지는노드 깊이 (Depth): 트리가가지는최대레벨 트리의디그리 ( 트리의차수 ) : 노드의디그리중에서제일많은노드의수 2) 트리의종류 이진트리 (Binary tree) [ 4 ]

5 모든노드의차수가 2 이하인트리 2포화이진트리 (Full binary tree, 정이진트리 ) 깊이가 n일경우, n번째레벨의노드의수가 2n-개이고, 트리의전체노드수가 2n-개인트리 마지막레벨까지꽉채워진트리를말한다. A B C D E F G 3 전이진트리 (Complete binary tree) 깊이가 n 일때, n- 레벨까지정이진트리로된트리 4K 진트리 모든노드의차수가 K 이하인트리 5 사향이진트리 (Skewed binary tree) 왼쪽이나오른쪽으로만치우쳐진트리 A B C 6 스레드 (Threaded) 이진트리 이진트리에서발생하는널링크부분을트리운행에필요한다른노드의포인터 ( 다른노드를가르키는지시자 ) 로사용되 는형태를가진다. 3) 트리 (Tree) 의이진트리로의변환 형제노드끼리연결하고, 연결한부분중기존의가지는삭제한다. 트리를이진트리로변환하는이유는널링크점유율이적기때문이다. 4) 이진트리 (Tree) 의메모리표현 배열에표현하는방법 : 엑세스가효율적이지만사향이진인경우공간낭비가심하다 링크를이용하는방법 : 노드의삽입, 삭제가쉽고, 기억공간을절약하지만속도가저하된다. 5) 트리운행의규칙 근노드의위치분석 - PreOrder에서근노드는제일왼쪽에위치한다. - InOrder에서근노드는양쪽의하위노드개수의중간에위치한다. - PostOrder에서근노드는제일오른쪽에위치한다. - 하위의노드운행시에는하위노드의입장에서 ROOT가된다. Preorder 운행 ROOT -> LEFT -> RIGHT 순의운행이다. Inorder 운행 LEFT -> ROOT -> RIGHT 순의운행이다. Postorder 운행 LEFT -> RIGHT -> ROOT 순의운행이다. [ 5 ]

6 6) 수식표기법 산술식을계산하기위해서기억공간에기억시키는방법으로이진트리구조사용한다. 이진트리의각운행법 (PreOrder, Inorder, PostOrder) 으로운행을하게되면그운행방법에따라전위 (Prefix 폴리쉬 ), 중위 (Infix), 후위 (Postfix 역폴리쉬 ) 표기법이된다. Infix는연산의스택구조에맞는 Prefix또는 Postfix로바꾸어처리한다. 수식표기법모양 M + Prefix( 전위표기법 ): +MN Infix( 중위표기법 ): M+N N Postfix( 후위표기법 ): MN+ 비선형구조 : 그래프 (Graph) ) 그래프의기본개념 그래프는정점V(Vertex) 와간선 (Edge) 의두집합으로이루어진구조이다. 망 (Network), 이항관계, 연립방적식, 무향선분해법에사용된다. 트리는사이클이없는그래프이고, 그래프는사이클이있다. 2) 그래프의종류 무방향그래프 : 정점들의쌍의순서가없는그래프 방향그래프 : 간선들의방향을표시하는그래프 2 3 3) 그래프의관련용어 Loop 한정점에서다시자신에게이어지는간선집합 2차수 (Degree) 무방향그래프 : 한정점에연결된간선의수 방향그래프 - 진입차수 (Indegree): 한정점에도찰하는방향간선의수 - 진출차수 (Outdegree): 한정점에서출발하는방향간선의수 - 차수 = 진입차수 + 진출차수 3 경로 (Path) [ 6 ]

7 경로길이 : 경로상에있는간선의수 단순경로 : 모든간선이서로다를때의경로로같은간선을두번이상지나지않는다. 기본경로 : 한경로상에있는모든정점이유일할때경로로같은정점을두번이상지나지않는다. 사이클 : 같은정점에서시작과끝이이루어지는경로 최대사이클 : 사이클을이루는경로중최대경로길이 4) 그래프의표현법 방향그래프에서 관계를나타내는행렬의원소를 라할때, 방향간선이있으면행렬의 = 이고없으면 =0 으로행렬 ( 배열 ) 에표기한다. 방향그래프의변형모양 무방향그래프에서 와 가서로인접하면 = 이고인접하지않으면 =0 으로표현한다. 무방향그래프의변형모양 ) 최소비용신장트리 (MST, Minimum-Cost Spanning Tree) 그래프상에서최소비용으로모든정점을방문하는방법으로각선에기술된값이가장적은간선을연결하여만든다. 비용이가장적은순서대로선택 선택된간선이 Cycle 을형성하면제외한다 ) 임계경로 (Critical Path) 작업의시작에서종료될때까지가장긴경로 [ 7 ]