자료구조론

본문내용

먼저 삽입된 요소가 먼저 삭제되는 성질을 가지고 있으며, 간단히 FIFO(First In First Out) 구조라고도 한다.
삽입 : Enqueue = ADD Queue = ADD = INSERT
삭제 : Dequeue = DELETE Queue = DELETE = REMOVE
구현법 : 배열 , 연결 리스트 등이 있다.
※ 환형큐일때에는 Front는 실제 시작되는 데이터의 1칸 앞을 가리키게 되어 있다.
( Queue 가 Empty 일 때 Front 와 Rear 이 같으므로 .. Full 일 때 달리 나타내주기 위해서 )
데이터를 삽입하는 알고리즘 ( 단 n 은 환형큐의 사이즈이다. )
Enqueue
rear <- ( rear + 1 ) mod n;
if front == rear then call Stack_Full(이 프로시져 안에서 rear--; 가 필요하다 )
Q(rear) <- item;
end Enqueue
데이터를 삭제하는 알고리즘 ( 단 n 은 환형큐의 사이즈이다. )
Dequeue
if front == rear then call Stack_Empty
front = (front - 1) mod n
item <- Q(front)
end Dequeue
예제 )
Queue
Data
A
B
C
D
E
설 명
Rear
Front
실제 Data는 ABCD가 들어 있고 Front는 실제 데이터 한칸 앞을 가르키기 때문에 E는 쓰레기값일 뿐이다.
Front
Rear
Front == Rear 이므로 Empty 이다.
※ 데크 - 한쪽은 입력, 한쪽은 출력을 받는 큐와는 달리 양쪽모두로 입출력이 가능한 구조이다.
3. 비선형구조
3.1 트리 (Tree)
노드들 중에 하나를 root라고 하고, 다른 노드들은 여러개의 트리로 나누어질 수 있을 때 이를 트리라고 한다. 이 때 나누어지는 여러 트리를 부분트리라고 한다.
트리의 용어
① 노드(node) : 트리 구성 요소 (기억 단위)
: 트리구조에서 자료의 상하위 개념을 나타내는 위치
② 근 노드(Root node)
: 트리구조에서 가장 위에 있는 노드 (레벨이 제일 높은 노드)
③ 단노드(terminal node) 또는 잎사귀 노드( leaf node )
: 근노드의 다른 한쪽 끝에 있는 노드.
④ 간노드(Non-terminal Node) 또는 가지 노드(Branch node)
: degree(차수)가 0이 아닌 노드
⑤ 차수 (degree) : 각 노드가 가지고 있는 가지 수.
: 임의의 노드에서 subtree 수.
⑥ 가지((Branch) 또는 호(arc)
: node와 node를 연결해 주는 선.
⑦ 경로(path) : 노드를 찾아가는 길.
⑧ 부트리(subtree) : 부분적인 하나의 트리 구조를 이루는 부분적인 트리 구조
: 근노드 제거시 생기는 트리
⑨ 자노드(children node 또는 son node)
: 한 노드 바로 밑에 연결되어 있는 노드.
⑩ 부모노드(parent 또는 father node), 부노드
: 임의의 노드에 연결된 전 레벨의 노드(이전 레벨의 노드).
⑪ 형제 노드(brother 또는 sibling) 또는 제노드 또는 쌍둥이 노드(twin)
: 하나의 부모 노드에 연결되어 잇는 자노드들.
⑫ 트리의 깊이(depth), 또는 높이(height)
: 근 노드에서 어떤 노드까지의 레벨의 수
: 트리의 계층(level)값과 같은 값을 가짐.
⑬ 레벨 (level) : 근 노드의 레벨을 1, 임의의 노드 레벨을 K이라 하면 자노드의
레벨은 K+1
: 근 노드를 레벨 1로 하고 순차적으로 부여된 값.
3.1.2 트리의 표현
3.1.3 이진 트리
하나의 근 노드와 왼쪽 부트리, 그리고 오른쪽 부트리 라고 부르는 두개의 분리된 이진 트리로 구성되어 있거나 혹은 부분 트리가 없는 상태로 되어 있는 노드들이 유한 개로 모여서 된 집합체를 의미
이진 트리의 종류
Left Skewed 트리
Right Skewed 트리
Complete Binary 트리
Full Binary 트리
3.2 그래프 (Graph)
각각의 단위 정보를 링크로 연결하여 구조화시킨 자료 구조를 그래프라 한다.
그래프는 1736년 수학자 오일러(euler)가 동부 프러시아(koenigsberg)에 있는 kneiphof라는 2개의 섬과 n개의 다리 문제를 해결하는데 처음 사용된 것으로 전해진다. 유명한 철학자 칸트가 여생을 보낸 Koenigsberg에는 Pregal강이 Kneiphof 섬 주위를 흐른다. 이 강은 4개의 지역과 접해 있다. 각 지역은 A~D로 표시되어 있으며 이들 지역은 a~g의 7개의 다리로 연결되어 있다. 이 섬과 다리 문제에서 섬을 정점(vertex)으로 놓고, 다리를 연결선(edge)으로 나타내어, 오일러는 그래프를 사용하여 모든 다리를 한번씩만 거쳐서 원래의 위치로 되돌아 올 수 없다는 것을 증명하였다. 이것을 '한붓그리기에 관한 오일러의 정리' 라 한다.
3.2.2 그래프의 표현방법
1) 인접 행렬
2) 인접 리스트
3) 역인접 리스트
4) 인접 다중 리스트
3.2.3 그래프의 운행
1) 깊이 우선 검색(DFS : Depth First Search)
: 무방향 그래프에서 어떤 정점에 대하여 검색이 끝나면 인접한 정점 중 검색하지
않은 정점을 찾아가 다시 검색하는 방법.
2) 너비 우선 검색(BFS : Breadth First Search)
: 무방향성 그래프에서 어떤 정점을 검색하고 그 정점에 인접한 모든 정점들을
검색한 후 이 정점에 인접한 모든 정점들을 검색하는 방법으로 Queue를 이용
3.2.4 가중치 그래프
Kruscal 알고리즘 : 네트워크 G의 모든 연결선에 대하여 가중치별로 오름차순으로 정렬한 후 최소 가중치의 연결선부터 순서대로 생성 트리에 연결할 것인가의 여부를 결정해 나가는 알고리즘
① 가중치가 작은 것에서부터 큰 순으로 차례차례 선택한 연결선을 생성 트리에 연결하여 사이클이 형성되면 제거하고, 만일 사이클이 형성되지 않으면 생성 트리의 연결선으로 선택해 나감
② 모든 연결선에 앞의 과정을 반복하여 적용하면 최소 생성 트리가 형성됨

키워드

자료구조,   알고리즘,   자료구조론