Chapter 08. 이진 트리의 구현
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이제 이진 트리를 직접 구현해 볼 차례입니다. 그런데 이진 트리는 재귀적인 특성을 지니고 있습니다. 이런 재귀적인 특성 때문에 이진 트리와 관련된 일부 연산은 재귀 호출의 형태를 띱니다. 따라서 여러분은 재귀적인 사고에, 그리고 재귀 함수의 정의에 어느 정도 익숙한 상태여야 합니다. 이진 트리 역시 배열 기반으로도, 그리고 연결 리스트를 기반으로도 구현이 가능합니다. 하지만 트리를 표현하기에는 연결 리스트가 더 유연하기 때문에 앞으로 대부분의 트리는 연결 리스트를 기반으로 구현하게 됩니다. 하지만 이진 트리라면, 특히 매우 빈번한 ..
Chapter 08. 트리의 개요
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 지금부터 배우게 될 트리는 고급 자료구조로 구분이 됩니다. 그리고 앞서 설명한 선형 자료구조들과 달리 비선형 자료구조이기 때문에 어렵게 느껴질 수 있습니다. 자료구조라고 하면 보통은 데이터를 저장하고 정리하고 꺼내는 것이 전부인 것으로 생각하기 쉽습니다. 물론 지금까지 배운 리스트, 스택, 큐, 덱의 경우는 그래 왔습니다. 하지만 이를 트리에 대해서도 동일하게 생각하면 안 됩니다. 트리는 단순히 데이터를 저장하고 꺼내는 자료구조가 아닙니다. 트리는 계층적 관계를 표현하는 자료구조입니다. 때문에 나중에 보게 될 트리의 ADT를 볼 때..
덱을 이해하고 있다면 덱을 큐처럼 사용할 수 있다는 사실을 알고 있을 것입니다. 따라서 덱을 이용해서 큐를 구현해 보기로 합니다. 다음 두 파일을 만들어서 덱을 기반으로 하여 큐를 구현해 봅니다. DequeBaseQueue.h 큐의 구현을 위한 헤더 파일 DequeBaseQueue.c 큐를 구현하고 있는 소스 파일 큐의 구현에 사용되는 덱의 헤더 파일과 소스 파일은 앞서 양방향 연결 리스트 기반으로 정의했던 것을 사용합니다. 그리고 큐의 헤더 파일에는 다음 함수들이 선언되어야 합니다. void QueueInit(Queue* pq); //큐의 초기화 int QIsEmpty(Queue* pq); //큐가 비어 있는지 확인 void Enqueue(Queue* pq, Data data); //큐에 데이터 저장 ..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 양방향 연결 리스트, 스택, 큐를 제대로 이해하고 있다면 덱을 이해하는 것은 껌입니다. 덱에 대해 한 줄로 설명하자면 다음과 같습니다. "덱은 데이터를 앞으로도 뒤로도 입력 가능하며, 앞으로도 뒤로도 출력이 가능한 큐 혹은 스택 혹은 두 개 모두와 같다" 스택은 데이터를 앞으로 넣었으면 앞으로 빼야 하는 것이 특징입니다. 반면 큐는 데이터를 앞으로 넣었으면 뒤로 빼야 하는 것이 특징입니다. 그런데 덱은 데이터를 앞으로 넣었으면 앞으로도 뒤로도 뺄 수 있고, 이는 데이터를 뒤에서 넣었을 때도 마찬가지라는 특징을 가지고 있습니다. 덱의..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 큐는 운영체제 및 네트워크와 관련된 소프트웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조입니다. 그리고 '큐잉 이론'이라는 학문에서는 수학적으로 모델링 된 결과의 확인을 위해서 특정 현상을 '시뮬레이션'하게 되는데, 이때에도 큐는 중요한 역할을 담당합니다. 따라서 우리도 시뮬레이션이라는 주제를 통해서 큐가 활용되는 형태를 적절한 범위 내에서 확인하고자 합니다. 시뮬레이션을 구현해 보기 위해 이와 관련한 상황을 예로 들겠습니다. 어느 햄버거 가게의 점장은 주문된 음식이 포장돼 나오기를 기다리는 손님들을 위해 대기실을 만들려고 합..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이번에는 연결 리스트를 기반으로 하는 큐를 구현해 보겠습니다. 큐는 데이터를 저장하는 위치와 데이터를 가져오는 위치가 다르다는 특징을 가지고 있습니다. 이를 연결 리스트 기반으로 구현하면, 꼬리로 데이터를 저장하면서, 머리로 데이터를 가져올 것이라는 것을 쉽게 생각해 볼 수 있습니다. 그럼 바로 연결 리스트 기반 큐의 헤더 파일을 정의해 보겠습니다. 앞서 정의했던 큐의 ADT를 바탕으로 직접 헤더 파일을 정의해 보는 것도 좋습니다. //LBQueue.h 헤더 파일로 저장 #ifndef LB_QUEUE_H #define LB_QUEU..