자료구조7 [C++] 이진트리 코드 구현 방법 binary tree ▣ 트리 ● 트리의 특징 검색이 편리하다. 논리적 계층을 이루고 있다. 계급적 특성을 가진다. ● 트리의 구조 ▷ 노드 트리의 항목으로 트리에 저장되는 데이터들을 말한다. ▷ 부모노드-자식노드 상하 계층구조로 이루어지고 직접 연결된 노드 관계를 가진다. 상위계층 - 부모노드, 하위계층 - 자식노드 ▷ 루트노드 트리에서 최상위 노드 ▷ 서브트리 부모노드 삭제하면 생기는 트리들 ▷ 리프노드 트리의 맨 아래에 위치한, 자신의 서브트리가 없는 노드 ● 차수 루트노드의 진입차수 = 0 리프노드의 진출차수 = 0 루트노드 외의 모든 노드의 진입차수 = 1 ● 레벨 노드의 레벨: 루트부터 해당 노드까지 이어지는 간선의 길이 루트노드의 레벨 = 0 ● 높이 트리의 높이 = 루트로부터 가장 멀리 있는 노드까지 이어진 간.. 2020. 9. 21. [C++] 원형 연결 리스트 코드 구현 방법 Circular linked list ▣ 연결리스트 종류 ● 단순 연결 리스트 (Simply linked list) ▷ 하나의 링크만 있고, 각각 노드의 링크는 후행 노드만을 가리키는 구조다. 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 있다. 자세한 코드 구현 방법 등 단순 연결 리스트 관련 포스트는 아래 링크를 참고하세요. 2020/09/10 - [Programming/Data Structure] - [C++] 연결리스트 Linked list 코드 구현 방법 [C++] 연결리스트 Linked list 코드 구현 방법 리스트가 뭘까? 리스트는 '일정한 순서'의 나열로 어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다. 리스트의 순서는 데이터가 저장되는 .. 2020. 9. 11. [C++] 이중연결리스트 코드 구현 방법 Doubly linked list 이 포스트에서는 이중연결 리스트를 C++ 코드로 구현하는 방법을 다룬다. ▣ 연결리스트 종류 ● 단순 연결 리스트 (Simply linked list) ▷ 하나의 링크만 있고, 각각 노드의 링크는 후행 노드만을 가리키는 구조다. 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 있다. 자세한 내용은 아래 포스트를 참고하세요. 2020/09/10 - [Programming/Data Structure] - [C++] 연결리스트 Linked list 코드 구현 방법 [C++] 연결리스트 Linked list 코드 구현 방법 리스트가 뭘까? 리스트는 '일정한 순서'의 나열로 어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다. 리스.. 2020. 9. 10. [C++] 연결리스트 Linked list 코드 구현 방법 이 포스트에서는 단일연결 리스트를 C++ 코드로 구현하는 방법을 다룬다. 리스트가 뭘까? 리스트는 '일정한 순서'의 나열로 어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다. 리스트의 순서는 데이터가 저장되는 물리적 위치와 상관없이 사람들의 머릿속에 인식되는 논리적인 순서, 혹은 리스트에 나타나는 원소들간의 의미적인 순서를 의미한다. 그럼 배열과 리스트의 차이는? 배열은 인덱스로 표현되는 '순서'가 배열 원소의 메모리 공간에서 물리적 의미를 의미하는 데 반해서, 리스트의 '순서' 개념은 어떤 정의에 의해 결정된 '논리적인 순서'다. 원소들의 물리적인 저장 순서나 위치와 무관하게 원소들 간의 논리적인 순서만 유지한다. 리스트의 구현 방법에는 두 가지가 있다. 1) 포인터를 이용한 방법, 2) 배열을 .. 2020. 9. 10. [C++] 큐 Queue 구현 방법 코드 큐 Queue 는 먼저 줄 선 사람이 맛집 먼저 들어가고 늦게 온 사람이 늦게 들어가는 원리의 자료구조이다. 다르게 말하면, 한 쪽 끝(rear)에선 삽입만 하고, 다른 한 쪽 끝(front)에선 삭제만 하는 사람으로 따지면 마치 입(음식 삽입)과 응꼬(음식 배출) 같다고 보면 된다. 먼저 들어간 음식이 지금 뱃속 어디에 있는지는 확인할 수 없다. Queue는 컴퓨터에서 CPU 관리 방법에 사용되는 자료구조다. CPU는 스케줄링할 때 FCFS(First come first served) 방식으로 먼저 Ready Queue에 도착한 프로그램 또는 작업 순서대로 CPU가 할당받아 일을 한다. 이제는 진짜 코드를 짜야 할 시간이다. 처음에 rear와 queue가 -1이 되게 설정해서 queue가 비어있는 상태.. 2020. 9. 9. [C++] 정수형 스택 STACK 구현 코드 (with 후위계산법) 위와 같은 stack 을 코드로 구현해 볼 거다. 정수만 들어가는 stack을 intStack 클래스로 정의한다. 필요한 멤버함수가 들어 있는 intStack 클래스를 intStack.h 헤더파일에 정의해준다. #pragma once #include using namespace std; typedef int element; constexpr auto STACK_SIZE = 5; class intStack { element top; element buf[STACK_SIZE]; public: intStack() : top(-1) { cout 2020. 9. 9. 이전 1 2 다음 반응형
