Kstone's DevSpire

트리(Tree)란?이번 포스트부터 알아볼 자료구조는 트리이다. 트리는 하나의 뿌리에서 데이터가 가지처럼 뻗어나가는 형식으로,그 형태 때문에 트리라는 이름이 붙었다. 그림으로 알 수 있는 중요한 정보는, 모든 노드는 부모를 하나만 갖는다는 것이다.이제 그 정의와 트리에서 자주 사용하는 용어에 대해 알아보자. 트리란, 하나 혹은 그 이상 노드들의 유한한 집합을 의미한다. 트리 구조에서는 루트라는 특별한 노드가 존재하고,루트를 기준으로 배타적인 좌우측 집합을 잘라내면 그 모습도 트리와 똑같다는 특징이 있다. 트리의 분할도 트리란 뜻이다.노드(Node) : 데이터와 함께 다른 노드로의 브랜치를 갖고 있는 요소노드의 차수(Degree of node) : 노드에 연결된 자녀 노드의 개수리프 노드(leaf, Term..

연결 리스트를 통한 스택과 큐 구상연결 리스트를 통해서도 스택과 큐를 구상해볼 수 있다.기존 배열로 구현하던 스택과 큐의 각 인덱스를 그냥 연결 리스트의 노드로 바꾸어 연결해주면 된다.스택의 경우는 LIFO 이므로, 새로운 노드가 항상 연결 리스트의 맨 앞에 삽입되면 된다.또 담긴 데이터를 제거할 경우에도, 연결 리스트의 맨 앞 노드의 링크를 제거해주고, top을 나타내는 포인터를 수정해준다.맨 처음의 빈 스택 상태를 링크가 0인 노드로 지정해주면, 예외 없이 스택을 구현하고 사용할 수 있다.큐의 경우는 FIFO 이므로, 새로운 노드는 리스트의 맨 뒤에 삽입되어야 한다.데이터를 삭제할 때는 리스트의 맨 앞 노드의 링크를 제거해주면 된다.기존 배열에서와 마찬가지로, front와 rear 포인터를 사용해 현..

연결 리스트(Linked List)란?연결 리스트 또한 자료구조의 일종으로, 배열과 달리 포인터를 사용해 다음 인덱스를 가리키는 형태의 자료구조이다.배열은 순차적인 메모리 구조를 가지고 있어 다음 인덱스가 메모리주소가 1차이가 나는 반면,연결 리스트로 자료구조를 채택하면 메모리 주소가 큰 폭으로 차이나게 된다. 연결 리스트는 각 요소가어디에나 위치할 수 있기 때문이다. 단순히 포인터로 연결만 하면 되기 때문에, 위치 자체는 중요하지 않다.더불어 배열 기반인 자료구조에 비해 데이터의 삽입/삭제 비용이 비교적 작다는 장점이 있기도 하다. 연결 리스트의 각 데이터 저장 단위를 노드라고 부르며, 노드에는 실제 데이터와 다음 데이터로 가는 포인터가 담겨있다.그리고 한 가지 중요한 사실은, 항상 마지막 노드의 포인..

C++에서의 상속이란?이미 C++에 대해 공부했다면 상속이라는 개념에 대해서 배웠을 것이다.여기서는 그 의미를 자료구조에 관련지어서 확장하고자 한다.상속은, ADT 간의 서브타입 관계를 표현하기 위해 존재하는 기능이라고 할 수 있다.여기서 서브타입이란, super type에서도 작동할 수 있게끔 만들어진 그 하위 유형들을 이야기 한다.즉, 다이어그램으로 생각해보면 슈퍼타입이 더 큰 원이고, 그 원 안에 서브타입들이 존재하는 형태이다.여기까지 들으면 기존에 알았던 상속과 개념이 같은 것을 깨달았을 것이다. 그럼 됐다. 기본적으로 이런 관계에 있는 두 ADT를 IS-A relationship을 가진다고 부른다.chair : subtype of furniture ( IS-A )lion : subtype of ..

C++의 템플릿 기능C++에는 클래스와 함수의 재사용에 큰 도움을 주는 템플릿이라는 기능이 있다.간단하게 설명하면, 우리는 보통 함수를 정의할 때 함수에 사용되는 매개변수의 자료형을 설정해준다.정수형 값인 매개변수면 int로 선언해야하고, 실수형이면 double 이나 float으로 선언해야 한다.그러나 템플릿 기능을 사용하면, 해당 매개변수의 타입을 '모호하게' 설정하여 아무 값이나 유연하게 작동한다.선택정렬의 두 가지 코드를 보며 비교해보자.void SelectionSort(int *a, const int n) { for(int i=0; i 위의 코드가 우리가 아는 일반적인 함수의 정의와 선언이다. 매개변수의 자료형을 미리 지정해주는 모습이다.그러나 템플릿을 사용한 밑의 코드를 보면,templat..