독서/C언어로 쉽게 풀어쓴 자료구조9 [CDS] chapter 8 : 트리 1. 트리 기본트리는 한 개 이상의 노드로 이루어진 유한 집합으로, 계층적인 자료를 표현하는데 적합한 자료구조이다. 항목들이 순차적으로 저장되는 선형 자료구조는 각 항목간의 관계를 표현하기 어려워 더이상 적합하지 않게 된다.트리 자료구조와 관련된 용어는 위 그림으로 정리하면 된다. 위 그림에 더하여, 노드의 차수는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다는 것만 추가적으로 정리하자.(더하여, 책에서는 루트의 레벨을 1로 놓고 트리의 높이 등을 계산하고 있다는 점이 위 그림의 표현과 차이점이다)2. 이진트리(1) 정의 이진 트리는 모든 노드가 2개의 서브 트리를 가지고 있는 트리로, 가장 많이 쓰이는 트리라고 한다. 여기서 서브 트리는 공집합일 수 있기 때문에 모든 노드의 차수는 2 이하가 된.. 2025. 3. 5. [CDS] chapter 7 : 연결리스트 ② 1. 특수한 연결 리스트(1) 원형 연결 리스트원형 연결 리스트(Circular Linked List)는 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드의 주소가 되는 리스트이다. 따라서 원형 연결 리스트에서는 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 연결 리스트에서 노드의 삭제 또는 삽입을 수행하려면 항상 선행 노드를 가리키는 포인터가 필요하기 때문에, 단순 연결 리스트에 비해 노드의 삽입, 삭제가 용이할 것이다.이러한 원형 리스트의 한 변형된 형태로, head 포인터가 리스트의 마지막 노드를 가리키도록 구성할 수 있다. 이 경우 리스트 끝의 노드를 삽입, 삭제할 때 유용할 것이다. 단순 연결 리스트에서는 이 끝 노드에 찾아가는 데에 길이에 비례한 시간이 소요될 것이지만 원형 연결.. 2025. 2. 12. [CDS] chapter 6 : 연결리스트 ① 1. 리스트의 개념리스트는 대표적인 선형 자료구조, 즉 연속적으로 데이터가 나열되는 자료구조이다. 이러한 선형 자료구조는 데이터에 순서가 있다는 점이 가장 핵심적인 특징이다 (집합과 구별되는 특징이다). 즉, 선형 자료구조에서는 데이터 간에 '앞'과 '뒤'라는 개념이 존재하며, 이 순서는 데이터가 추가되거나 삭제됨에 따라 바뀔 수 있다. 이러한 특징 때문에 선형 자료구조는 데이터를 순차적으로 접근하거나, 데이터 사이에 새로운 데이터를 삽입하거나, 특정 위치의 데이터를 삭제하는 작업을 수행하기에 적합하다. 선형자료구조인 리스트를 구현하는 대표적인 두가지 방법은 배열과 연결리스트인데, 이하에서 살펴보자.2. 배열(array)과 연결리스트(linked list)(1) 개념배열은 크기가 정해져 있는 정적(sta.. 2025. 1. 27. [CDS] chapter 5 : 큐 1. 큐 기본큐(queue)란, 데이터를 입력된 순서대로 나열한 형태의 자료구조이다. 큐 또한 스택과 마찬가지로 데이터가 연속적으로 연결되어 있는 모양의 선형 자료구조이기에 일종의 리스트라고 할 수 있다. 다만 큐는 데이터의 삽입이 한쪽 끝(큐의 rear)에서 이루어지고, 삭제는 반대쪽 끝(큐의 front)에서만 이루어진다는 점에서 리스트나 스택과 차별된다.큐의 구조상 큐에서 빼올 수 있는 데이터는 가장 먼저 들어온 데이터이다. 즉, 큐는 선입선출(FIFO, First-In-First-Out) 구조이다. 이러한 특성에서, 큐는 다음과 같은 분야에서 활용될 수 있다.프린터 작업 관리프로세스 스케쥴링웹 서버의 요청 처리BFS 알고리즘2. 유형(1) 일반 큐일반 큐(선형 큐)는 1차원 배열을 활용하여 가장 간.. 2025. 1. 11. [CDS] chapter 4 : 스택 1. 스택 기본스택(stack)이란, 이름에서 알 수 있듯이 데이터를 차곡차곡 쌓아올린 형태의 자료구조이다. 스택은 선형자료구조로 데이터가 연속적으로 연결되어 있는 모양이기에 일종의 리스트라고 할 수 있다. 그러나 스택은 데이터의 삽입 및 삭제가 한쪽 끝(스택의 top이라고 한다)에서만 이루어진다는 점에서 리스트와 차별된다.스택은 구조상 데이터가 입력순서대로 쌓여있기 때문에 스택에서 빼올 수 있는 데이터는 가장 위에 있는 마지막에 넣어준 데이터이다. 즉, 후입선출(LIFO, Last-In-First-Out) 구조이다. 스택은 다음과 같은 분야에서 활용될 수 있다.웹 브라우저의 뒤로가기 기능수식 계산 - 후위 표기법문서 편집기에서 되돌리기 기능함수 호출 - 복귀할 주소를 기억하는데 사용DFS 알고리즘2. .. 2025. 1. 4. 이전 1 2 다음
