더여니의 갓생 일기

2. void MinHeap ::: Push(const T& e) { if(heapSize == capacity) { Change1D(heap, capacity, 2*capacity); capacity *= 2; } int currentNode = ++heapSize; //데이터가 들어갈 위치 : heapSize + 1 while (currentNode !=1 && heap[currentNode/2] > e) { heap[currentNode] = heap[currentNode/2]; currentNode /= 2; } heap[currentNode] = e; } void MinHeap :: Pop() { if(IsEmpty()) throw "Heap is empty."; heap[1]. ~T(); //..

1. 스레드 이진 트리에서 노드 s의 왼쪽 자식으로 새로운 노드 l을 삽입하는 C++ 함수를 작성하라. s의 왼쪽 서브트리는 l의 왼쪽 서브트리가 된다. void ThreadTree :: Insertleft(ThreadedNode *s, ThreadedNode *r) { r->leftChild = s->leftChild; r->leftThread = s->leftThread; r->rightChild = s; r->rightThread = true; s->leftChild = r; s->leftThread = false; if(!r->leftThread) { ThreadedNode *temp = InorderSucc(r); temp->leftChild = r; } } 2. 스레드 이진 트리에 대한 C++..

1. 이진 트리에서 리프 노드의 수를 계산하는 C++ 함수를 작성하라. 이 함수의 계산 시간은 얼마인가? int get_leaf_count(TreeNode *ptr) { int count = 0; if(ptr != NULL) { if(ptr->leftChild == NULL && ptr->rightChild == NULL) return 1; else count = get_leaf_count(ptr->leftChild) + get_leaf_count(ptr->rightChild); } return count; } 2. 이진 트리에 있는 모든 노드의 왼쪽 자식과 오른쪽 자식을 교환하는 C++ 함수 SwapTree()를 작성하라. TreeNode* Tree :: SwapTree(TreeNode *origNod..

- 이중 연결 리스트 #include using namespace std; class DblList; class DblListNode { friend class DblList; private: int data; DblListNode* left, * right; public: DblListNode(int element, DblListNode* lNode = NULL, DblListNode* rNode = NULL) { data = element; left = lNode; right = rNode; } }; class DblList { private: DblListNode* head; DblListNode* tail; int size; public: explicit DblList(int element) { ..

#include using namespace std; class Matrix; struct Triple { int row; int col; int val; }; class MatrixNode { private: MatrixNode* right; //행 MatrixNode* down; //열 bool isHead; union { MatrixNode* next; Triple triple; //row, col, val }; public: MatrixNode() { //디폴트 생성자 } MatrixNode(bool b, Triple* t) { isHead = b; if (isHead) right = down = next = this; else triple = *t; } friend class Matrix; fr..

#include #include using namespace std; enum Boolean { FALSE, TRUE }; class ListNode { friend void equivalence(); private: int data; ListNode* link; ListNode(int); }; typedef ListNode* ListNodePtr; //new를 사용하여 포인터 배열을 만들 수 있음 ListNode::ListNode(int n) { data = n; link = 0; //linked list init }; void equivalence() { ifstream fin("input.dat", ios::in); //입력파일 "input.dat" if (!fin) { cerr size; //배열..

문제들 종합 : 다항식 덧셈, 뺄셈, 곱셈 구현 #include using namespace std; template class Chain; template class ChainNode { private: T data; ChainNode* link; public: ChainNode(T element = 0, ChainNode* next = NULL) { data = element; link = next; } T getData() { return data; } ChainNode* Link() { return link; } friend class Chain; template friend ostream& operatorlink = temp; //x가 temp를 가르키도록 return x->link; //위치를..

1. 연결 스택을 위한 완전한 C++ 템플릿 클래스를 작성하고 테스트하라. #include using namespace std; template class LinkedStack; template class ChainNode { public: ChainNode(T element = 0, ChainNode* next = NULL) { data = element; link = next; } friend class LinkedStack; template friend ostream& operator

1. 연산자 link = x->link; } delete x; } void InsertBack(const T& e) { if (first) { last->link = new ChainNode(e); last = last->link; } else first = last = new ChainNode(e); } void Concatenate(Chain& b) { if (first) { last->link = b.first; last = b.last; } else { first = b.first; last = b.last; } b.first = b.last = 0; } void Reverse() { ChainNode* current = first, * previous = 0; while (current) { C..

다음 연습문제들은 모두 4.2.4.절의 정의들을 기반으로 하고 있다. 모든 함수들은 클래스 Chain의 멤버 함수로 구현되는데, 그래서 이들은 ChainNode의 데이타 멤버들에 접근할 수 있다고 가정한다. 1. 체인에 있는 노드의 수를 계산하는 C++ 함수 length를 작성하라. 이 함수의 시간 복잡도는 얼마인가? * 시간 복잡도 : O(n) * 참고 : https://jaimemin.tistory.com/159 2. x를 체인에 있는 임의의 노드를 지시하는 포인터라고 하자. 체인으로부터 이것을 삭제하는 C++ 함수를 작성하라. 만일 x == first라고 하면, first는 체인에서 새로 첫 번째가 된 노드를 가리키도록 반드시 재설정 되어야 한다. 이 함수의 시간 복잡도는 얼마인가? * 시간 복잡도..