bdfgdfg

트리 앞서 배운 자료구조들(리스트,스택,큐,덱등)은 모두 선형 자료구조이다. 이번에 배울 트리는 비선형 자료구조. 트리는 계층적 관계를 표현하는 자료구조이다. 트리와 관련된 용어를 정의해본다. 1. 노드 : node - 트리의 구성요소에 해당하는 A,B,C,D,E,F등 2. 간선 : edge - 노드와 노드를 연결하는 선 3. 루트 노드 : root node - 트리 구조에서 최상위에 존재하는 노드 (위 그림에선 A노드) 4. 단말 노드 : terminal node - 아래로 또 다른 노드가 연결되어 있지 않은 E,F,C,D와 같은 노드. (다른말로 리프(leaf)노드라고도 함) 5. 내부 노드 : internal node - 단말 노드를 제외한 모든 노드로 A, B와 같은 노드. (비단말 노드라고도 불..

큐(Queue) 스택이 가장 나중에 저장된 값을 먼저 뽑아오는 후입선출(LIFO)의 구조였다면 큐는 가장 먼저 저장된 값을 먼저 뽑아오는 선입선출(FIFO)의 구조이다. 큐를 배열기반으로 구현했을때 선입선출의 구조가 되기 위해서는 1. 데이터가 들어갈(enqueue) 인덱스값을 기억할 rear변수. 2. 데이터를 뽑아(dequeue)올 인덱스값을 기억할 front변수. 처음 FR이 0번째 인덱스를 가리킬때 데이터가 들어오면 R이 가리키는 인덱스에 요소를 집어넣고 한칸 오른쪽으로 옮긴다. 그리고 데이터를 뽑아올땐 F가 가리키는 인덱스에 요소를 빼오고 한칸 오른쪽으로 옮긴다. 이것이 배열기반 큐의 구조. 하지만 이렇게 단순히 끝낼수는 없는게 위의 그림과 같이 분명히 배열에 데이터를 저장할 공간이 남아있지만 ..

스택 LIFO(Last In First Out). 후입 선출방식의 자료구조이다. 앞서 재귀함수를 공부할 때도 자기 자신을 호출하면서 빠져나올 땐 역순으로 빠져나오는 스택의 방식. 간단하게 설명하면 쌓여있는 상자를 생각하면 쉽다. 상자를 밑에서부터 위로 하나하나 차곡차곡 쌓고 뺄 때는 위에서부터 아래로 하나하나씩 뺀다. 이것이 스택의 구조 간단하니 바로 코드를 통해 확인한다. #pragma once template class Stack { public: Stack(); ~Stack(); inline T GetTop() const; inline bool Push(const T& item); inline bool Pop(); inline bool Empty() const; private: enum { MAX ..

원형 연결리스트 원형 연결리스트는 기존의 연결리스트에서 맨 마지막 노드가 첫 번째 노드를 가리키는 형태를 이루는게 원형 연결리스트. 원형 연결리스트는 꼬리(마지막노드)포인터 변수가 따로 없더라도 맨 마지막에 노드를 추가할 수 있다. 다만 헤드보단 꼬리 포인터변수를 통해 원형 연결리스트를 구현하는것이 훨씬 간단하다. 앞서 단순 연결리스트를 구현할때 변경되는것은 앞(머리) 뒤(꼬리)쪽에도 추가할 수 있게 기능을 추가하고 탐색의 경우 원형으로 계속 돌 수 있는 형태이니 다음 노드의 nullptr을 저장하지 않게만 하면 된다. 양방향 연결리스트 단순 연결리스트는 노드가 내 다음에 존재하는 노드만을 가리켰다면 양방향 연결리스트는 내 다음 노드뿐만 아니라 내 이전의 노드도 가리킨다. (노드 클래스에 포인터변수 한개..