Algorithm (알고리즘)/자료구조 썸네일형 리스트형 C++ 배열로 구현한 최대 힙 (Array MaxHeap C++ ) 배열로 구현한 최대힙 구현의 편의상 1번째 인덱스부터 사용함, 삭제된 인덱스 값은 0 maxheap:: 자식관계와 상관없이 부모노드가 자식노드보다 큰 구조 (완전 이진트리) 힙생성(heapify)의 시간복잡도:: O(logN) 트리의 높이에 따라 /* 자료구조 최대힙 구현(배열) - 2019/12/29 xtar.tistory */ #include using namespace std; //최대힙 메소드 void Make_MaxHeap(int arr[],int size) { int cnt = 0; for (int i = 0; i < size; i++) { int child = i; int parent = child / 2; while (arr[parent]1) { auto a = arr[parent]; ar.. 더보기 C++ 스택을 이용한 트리 전위순회 (Tree C++ with Stack) 재귀함수를 사용하지 않고 STL 스택으로 트리 전위 순회하기 *재귀함수의 이해 /* 자료구조 이진트리 스택으로 구현 (재귀 사용 x) - 2019/12/29 xtar.tistory */ #include #include using namespace std; template class Node { T vaule; Node* left; Node* right; Node* root; public: Node() : vaule(0), left(nullptr), right(nullptr), root(nullptr) {}; Node(T _value) :vaule(_value), right(nullptr), root(nullptr) {}; Node(T _value, Node* _left, Node* _right) : va.. 더보기 C++ 이진 탐색 트리 구현 ( Binary Search Tree C++) bst 트리:: 루트노드의 왼쪽노드는 루트노드 보다 작은 값 오른쪽노드는 루트노드 보다 큰 값으로 정렬 삽입,삭제,검색의 시간복잡도:: 평균 O(logN) , 최악 O(N) /* BST(Binary Search Tree) 이진탐색트리 구현 - 2019/12/28 xtar.tistory */ #include using namespace std; template struct Node { Node* left; Node* right; T value; }; template class BinarySearchTree { public: BinarySearchTree() :root(nullptr) {}; ~BinarySearchTree() {}; void AddNode(T _value); bool SearchValue(.. 더보기 C++ 포인터를 이용한 트리 구현 (Pointer Binary Tree C++) 정렬되지 않은 일반적인 이진트리 구현한 함수(다형성을 위해 템플릿 사용) void Preorder(Node* node); 전위 순회:: root->left->rigth 순서대로 출력 void Inorder(Node* node); 중위 순회:: left->root->rigth 순서대로 출력 void Postorder(Node* node); 후위 순회:: left->right->root 순서대로 출력 void SetLeft(Node* node); 왼쪽자식 노드에 node 연걸 void SetRight(Node* node); 오른쪽자식 노드에 node 연결 /* 포인터를 이용해 실제 사용되는 자료구조 이진트리 동일하게 구현 - 2019/12/24 xtar.tistory */ #include using name.. 더보기 C++ 링크드 리스트를 이용한 큐 구현 (Single Linked List Queue C++) FILO(LILO)구조 구현한 함수(다형성을 위해 템플릿 사용) void Enqueue(T _value); T Dequeue(); 가장 먼져 들어간 값을 반환하고 큐에서 지움 bool empty(); 비어있는지 확인하는 함수 /* 싱글링크드 리스트를 이용해 실제 사용되는 자료구조 큐와 동일하게 구현 - 2019/12/23 xtar.tistory */ #include using namespace std; template class Node { public: T value; Node* next; Node() :value(0), next(nullptr) {}; ~Node() {}; }; template class Queue { public: Queue() :head(nullptr), tail(nullptr),.. 더보기 C++ 링크드 리스트를 이용한 스택 구현 (Single Linked List Stack C++) LIFO(FILO) 구조 STL의 STACK의 지원 함수:: PUSH- 스택에 값을 넣음 POP- 최근에 넣은 값을 리턴하고 삭제 TOP- 가장 최근값을 리턴 EMPTY - STACK이 비어있다면 TRUE 출력 /* 싱글링크드 리스트를 이용해 실제 사용되는 stl(standard template library) 스택과 동일하게 구현 - 2019/05/18 xtar.tistory */ #include using namespace std; template class Node { public: T value; Node* next = nullptr; Node() {}; ~Node() {}; }; template class Stack { private: Node* head; Node* tail; public: S.. 더보기 C++ 싱글 링크드 리스트 구현 (Singly Linked List C++) 싱글 링크드 리스트는 단일 방향으로 한 노드는 값과 다음 노드를 가리키는 주소를 가지고 있다. 싱글 링크드의 제일 앞에 있는 값을 Front 또는 Head라고 함 싱글 링크드의 제일 뒤에 있는 값을 Back 또는 Tail이라고 함 node->value 현재의 노드가 저장한 값 node->next 다음 노드를 가리키는 주소 싱글 링크드 리스트에서 노드가 삭제될 때 전 노드는 삭제되는 노드의 다음 값만 가리키면 된다. 그 후 삭제될 노드는 delete를 이용해 동적 할당을 해제해 준다. 싱글 링크드 리스트에서 노드가 중간에 삽입될떄 새로 들어오는 노드는 기존에 있던 자리의 노드가 가리킨 앞의 노드를 가리키고 기존의 노드는 새로 들어온 노드를 가리키면 된다. (빨간색: 새로운 노드, 파란색: 기존 노드, 초록.. 더보기 이전 1 다음
