이진탐색트리에 노드를 삽입/삭제/중위순회로 출력하는 코드입니다! 중요하게 봐야 할 곳은, 1. 아직 트리가 만들어지지 않았을 때 노드를 삽입하는 경우 2. 트리 삭제 시 노드를 찾았는데, 1.자식이 0개라면 node를 지운 후 해당 node를 nullpointer로 바꿔준다. 2.왼쪽 자식만 있다면 왼쪽 자식을 해당 노드로 바꿔준 후 찾았던 걸 삭제한다. 3.오른쪽 자식만 있다면 오른쪽 자식을 해당 노드로 바꿔준 후 찾았던 걸 삭제한다. 4.왼쪽 오른쪽 자식 둘 다 있다면 왼쪽 노드 중에서 가장 큰 값을 찾아서 그 노드로 바꿔준다. 3. 노드의 왼쪽 자식/오른쪽 자식으로 이동할 때 pointer 값!! (null pointer도 잘 생각해주자) main.cpp 파일 #include "binarysearc..
KAU/C++ 자료구조
순회방법 L: 왼쪽 이동 V: 노드 방문 (데이터 출력) R: 오른쪽 이동 재귀함수를 이용 순서만 주의하자! inorder(중위순회): LVR if (currentNode){ Inorder(currentNode -> leftChild); Visit(currentNode); Inorder(currentNode -> rightChild); } preorder(전위순회): VLR if (currentNode){ Visit(currentNode); Preorder(currentNode -> leftChild); Visit(currentNode); Preorder(currentNode -> rightChild); } postorder(후위순회): LRV if (currentNode){ Visit(currentNo..
들어만 봤던 Linked List를 드디어 보게 되었다!! 개인적으로 C++에서 가장 매력적으로 다가온 TOOL array의 한계를 해결할 수 있는 Linked List 데이터 입력 시 주소가 순차적이지 않아 요소를 메모리의 어느 곳에나 둘 수 있음 (크기를 동적으로 할당 가능) 연결리스트 구현에서 유념해야 할 것 1. 연결리스트의 연결을 끊지 않게 주의하자. 2. 연결리스트에서 next link의 pointer를 지정할 때 아예 노드의 저장소 자체를 변화시키지 않도록 주의하자. 1번은 그냥 실수를 안 하면 되는 문제이고, 2번의 경우 개념에서 헷갈릴 수 있다. class ChainNode { friend class Chain; public: ChainNode (int element=0, ChainNod..
Template을 쓰는 가장 강력한 이유는 바로 '어떠한 타입으로도 인스턴스화 가능'하다는 것이다. 인스턴스를 가장 잘 설명하는 예시는 Bag a; Bag r; 우리는 Bag을 이용해 형 객체뿐만 아니라 형 객체도 만들 수 있다! PPT 템플릿 왜 갖다 쓰는지 생각해봐라 누군가가 템플릿으로 만들어주거나 만든 템플릿을 잘 활용할 수 있다면 나는 그저 선언하고 사용하는 것만으로도 설계 구조까지 통째로 가져다 재사용할 수 있다는 장점이 있다. Template을 이용해 Stack 구현하기 코드에서 집중적으로 볼 것 Template이 어떻게 쓰였는가? Push와 Pop에는 각각 ++, --연산자가 다르게(전위,후위) 쓰였음을 주의하자. #include #include #define SIZE 10 using nam..
희소행렬 전치 시간복잡도 O(Col X Terms) #include #define MAX_TERMS 101 typedef struct { int row; int col; int value; } element; typedef struct SparseMatrix { element data[MAX_TERMS]; int rows; // 행의 개수 int cols; // 열의 개수 int terms; // 항의 개수 } SparseMatrix; SparseMatrix matrix_transpose2(SparseMatrix a) { SparseMatrix b; int bindex; // 행렬 b에서 현재 저장 위치 b.rows = a.rows; b.cols = a.cols; b.terms = a.terms; if ..
오버로딩 구현 방법? C=A.add(B) 이런 함수를 만들어보고 싶었다...!!🤔
#include using namespace std; void swap(int& a, int& b) { int temp = a; a = b; b = temp; } void Permutations(char* a, const int k, const int m) { if (k == m) { //순열 출력 for (int i = 0; i
*자주하는 실수 cout이나 cin 같은 거 쓸 때 맨 위에다가 이거 넣는 거 잊지 말자!! #include using namespace std; if 다음에 (조건문) 조건문은 괄호로 감싸주자!! 이원탐색 #include using namespace std; int BinarySearch(int* a, const int x, const int n) { int left = 0; int right = n - 1; while (left a[middle]) left = middle + 1; else return middle;//찾았다. } //없다 return -1; } int main() { int List[] = { 1,2,3,4,5,7,9,10 }; cout
#include using namespace std; void swap(int& a,int& b) { int temp = a; a = b; b = temp; } int main() { int a[10] = { 1,10,5,8,7,6,4,3,2,9 }; for (int i = 0; i < 10; i++) { int j = i; for (int k = i + 1; k < 10; k++) if (a[k] < a[j]) { j = k; } swap(a[i], a[j]); } for (int i = 0; i < 10; i++) { cout
뭐든 기초를 확고히 하자. 자료구조가 바로 그 기초의 근간!! 알고리즘 실력을 늘릴 수 있을 것 같은 과목이다.. 프로그래밍 언어를 접하고 코드를 기술하기 이전에 꼭 알고 넘어가야 하는 기초가 있다. 시스템 생명주기 요구사항 모든 경우에 대한 입력과 출력을 정밀하게 기술한다. 분석 문제를 작은 단위로 나누어 상향식/하향식 접근 방법으로 세분화한다. 설계 objects와 operations를 나누는 관점에서 시스템에 접근한다. 다르게 표현하면 objects는 과목, 학생, 교수이고 operations는 삽입, 삭제 등이 될 수 있다. 설계 시 구현(implementation)을 위한 결정 사항들, 예를 들어 트리를 쓸지, 전화번호 데이터도 포함시킬지 등은 가능한 뒤로 미룸으로써 선택한 언어의 범주 내에서 ..
class와 queue 개념을 활용하여 카드를 정렬하는 알고리즘 학교 과제로 해결했던 카드 정렬 알고리즘에서 원형큐를 잘 이해해버린 것 같다! 평소 python에서 쓰던 .popleft() .append .pop(3) 이런 함수들을 내가 구현해버린 기분.. 😋 queue.h #include using namespace std; class CircularQueue { private: int queue[6] = {}; int front; //front = 0 으로 초기화 int rear; //rear는 꼬리로 배열이 차있는 영역까지라고 생각하면 된다 int maxQueueSize; public: CircularQueue(int); void isEmpty(); void isFull(); void enQueue..
