더여니의 갓생 일기

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

1. 다음 식들을 후위 표기 형태로 변환하라. (a) A * B * C (b) -A + B - C + D (c) A * -B + C (d) (A + B) * D + E / (F + A * D ) + C (e) A && B || C || !(E > F) (f) !(A && !(B D))) || (C 후위의 3번 ~ 연습문제는 2회독 때 도전 !

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

1,2,3,4,5번 문제 전체 코드 //String.h의 헤더파일 #ifndef String #include using namespace std; class String { private: char* str; int len; int* f; public: String(char* init, int m) :len(m) { str = new char[m + 1]; f = new int[m]; for (int i = 0; i < m; i++) str[i] = init[i]; str[m] = '\0'; //문자열의 끝은 항상 널이다 FailureFunction(); } ~String() { if (str != NULL) { delete[]str; str = NULL; } if (f != NULL) { delete[..

* 논리회로는 진도가 쑥쑥 나가는데 자료구조는 느린 게 개탄스럽다 .. ㅜ ㅜ

1. [프로그래밍 과제] 다차원 배열이 C++에서 표준 데이타 객체로 제공될지라도 때로는 다차원 배열을 위해 클래스를 정의할 필요가 있다. 이 정의는 다음과 같은 보다 견고한 클래스를 표현한다. (a) 범위 검사를 수행한다. (b) 각 차원의 인덱스 집합으로 0부터 시작하는 연속적인 정수들로 구성되는 것을 요구하지 않는다. (c) 배열 지정을 허용한다. (d) 배열의 초기화를 다른 배열을 사용하여 할 수 있다. (e) 실행 시에 배열의 각 차원의 범위를 선택한다. (f) 배열의 범위와 크기를 동적으로 변경할 수 있다. (g) 배열의 크기를 판단할 수 있는 방법을 제공한다. 실수 원소를 저장하고 위에 명기된 기능들을 제공하는 클래스 mdArray를 구현하라. 이를 위해 동적으로 생성되는 1차원 배열인 원소..

1. 이 절에서 사용된 표현에서 임의의 원소 A[i][j]를 찾아 그 값을 변경하는 데 소요되는 시간은 얼마나 되는가? - 일반적인 방법 : O(cols*rows) - 빠른 전치 행렬 : O(cols+terms) 3. 희소 행렬을 읽고 출력하는 C++ 함수를 작성하라. 이것은 를 다중화해서 구현되어야 한다. 입출력 형식을 설계해야 하지만 내부 표현은 이 절에서 사용된 0이 아닌 원소들의 1차원 배열을 사용하여야 한다. 이 함수들의 연산 시간을 분석하라. *SparseMatrix 코드의 일부분 발췌 * 전체 코드는 첨부파일에 4. RowSize와 RowStart를 저장하기 위해 두 개의 배열을 사용하지 않고 단지 하나의 배열만을 사용하도록 FastTranspose 함수를 다시 작성하라. //변경 전 // ..

2. //출력 결과 * a,b배열을 랜덤으로 생성한 뒤, 오름차순 정렬하고 두 배열에 같은 값이 있는지 확인 후 길이 비교하여 -1, 0, 1 출력 되도록 클래스 생성 *참고 : https://jaimemin.tistory.com/138 3. 함수 Add를 수정해서 실행을 끝내기 전에 c.termArray의 크기를 c.terms로 줄일 수 있도록 하라. 이 수정으로 데이타 멤버 capactiy를 사용하지 않아도 되는가? * 추가된 부분이 c.termArray의 크기를 c.terms로 줄이는 부분. * 참고 : https://jaimemin.tistory.com/138 * 사실 이해 안 됏음 ㅜ.. 4. 이 절에서 표현한 방식의 다항식을 입력하고 출력하는 C++ 함수를 작성하라. 이 함수는 >> 연산자를 ..