본문 바로가기

Data Structure7

이진트리 2015. 8. 5.
트리(Tree) 트리(Tree) 트리 - 나무와 유사하게 계층적 구조를 띄고 있는 자료구조- 주된 목적은 탐색이며, 의사 결정, 파일 시스템, DBMS 등 다양한 곳에서 응용됨 트리의 구조 - 뿌리(Root), 가지(Branch), 잎(Leaf, 단말 - Terminal) 세가지 요소로 이루어져 있다. - 뿌리(Root) 노드 : A- 가지(Branch) 노드 : B, C, D, E, F, G- 잎(Leaf), 단말(Terminal) 노드 : I, J, K, L- B와 C는 형제 노드, D와 E는 B의 자식 노드, A는 B의 부모 노드 트리의 용어 - 경로(Path) : 한 노드에서부터 다른 노드까지 이르는 길 사이에 놓여있는 노드들의 순서- 길이(Length) : 경로가 가지는 속성, 출발 노드에서 목적지 노드까지 거.. 2015. 7. 29.
이중 연결 리스트(Doubly Linked List) 이중 연결 리스트(Doubly Linked List) 2015. 7. 26.
단순 연결 리스트(Simple Linked List) 단순 연결 리스트(Simple Linked List) 연결 리스트 - 어떤 데이터를 저장할 때 다음 자료가 있는 위치를 포함시키는 방식으로 자료를 저장- 동적 할당을 이용하여 필요할 때마다 길이를 늘리고 줄일 수 있다.(메모리 관리 용이) 2015. 7. 26.
큐(Queue) 큐 한쪽 끝에서는 삽입 작업이 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어지는 자료구조. 스택과 마찬가지로 배열과 리스트로 구현이 가능하다.시간 순서대로 쌓이며 가장 먼저 삽입된 자료가 가장 먼저 삭제되는선입선출(FIFO : First In Fist Out)의 구조를 갖는다. Insert : 새로운 데이터를 삽입하는 작업(rear 에서 발생)Remove : 데이터를 제거하는 작업(front 에서 발생Peek : front가 가리키는 데이터를 읽는 작업 1. 큐 - 배열 형태 rear 위치에 데이터가 삽입된 후 rear++front 위치에 있는 데이터를 삭제한 후 front++ 삽입, 삭제가 반복될 수록 rear와 front가 계속 증가하기 때문에 이미 꺼낸 데이터가 들어있던 배열의 인덱스를 사용할 수 .. 2015. 7. 8.
스택(Stack) 스택 같은 구조와 크기의 자료를 top이라고 정한 한 곳에만 쌓을 수 있고 top으로만 접근하도록 만든 자료구조 배열과 리스트로 구현이 가능하다. 시간순서에 따라 자료가 쌓이고 삭제 시에는 가장 마지막에 삽입한 자료가 가장 먼저 삭제되는 후입선출(LIFO : Last In First Out)의 구조를 갖는다. 연산 Push : 스택안에 데이터를 집어 넣는 작업 Pop : 스택안의 데이터를 꺼내는 작업 Peek : top이 가리키는 데이터를 읽는 작업 구조 1. 스택 - 배열 형태 2. 스택 - 리스트 형태 장점 : 메모리의 낭비를 막을 수 있고 Stack Full의 한계를 벗어날 수 있다. 데이터의 추가와 삭제가 헤더부분에서 일어나기 때문에 위치를 찾기 위한 추가 연산이 필요하지 않다. 구현 실행코드 /.. 2015. 7. 8.
728x90

티스토리툴바