더여니의 갓생 일기

#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..

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

4. 다음의 쌍 각각에 대하여 IS-A 관계로 연결되는지 여부를 말하고 그 이유를 밝혀라, (a) 직사각형과 사다리꼴 둘 중의 하나를 어느 것의 서브 타입이라고 할 수 없음 (b) 직사각형과 원 둘 중의 하나를 어느 것의 서브 타입이라고 할 수 없음 (c) 사자와 호랑이 둘 중의 하나를 어느 것의 서브 타입이라고 할 수 없음 (d) 스택과 순서 리스트 스택이 정렬되어 있으면 순서 리스트라고 할 수 있으므로 IS-A 관계 (e) 큐와 순서 리스트 큐가 정렬되어 있으면 순서 리스트라고 할 수 있으므로 IS-A 관계

2. 클래스 Queue에 큐의 크기와 원소 수를 반환하는 함수를 추가하라. 3. 클래스 Queue에 큐를 두 개의 큐로 분할하는 함수를 추가하라. 첫 번째 큐는 처음부터 시작해서 하나 건너 원소를 포함하고 두 번째 큐는 나머지 원소를 포함한다. 큐 원소의 상대적 순서는 변하지 않는다. 이 함수의 복잡도는 어떻게 되는가? #include #include using namespace std; template class Queue { private: T* queue; T* division1; T* division2; int front, rear, capacity; public: Queue(int queueCapacity = 10) : capacity(queueCapacity) { if (capacity < 1..

1. 다음과 같은 함수를 첨가해서 스택 ADT를 확장하라: 스택을 출력하는 함수, 스택을 두 개의 스택으로 분할해서 하나는 밑으로부터 반을, 또 다른 하나는 나머지 원소를 포함하는 함수, 두 개의 함수를 하나로 합병하여 두 번째 스택에 있는 모든 원소를 첫 번째 스택의 톱에 설치하는 함수. 이 새로운 함수의 C++ 코드를 작성하라. #include #include using namespace std; template class Stack { private: T* stack; int top; int capacity; public: Stack(int stackCapacity = 10) : capacity(stackCapacity) { if (capacity < 1) throw "Stack capacity m..