경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.
Exercise #1
Problems
- Implement the SORTED LIST using doubly linked structure.
- 1) insertItem(item): Insert the item to the proper position in the list.
- 2) removeItem(item): Delete "item" in the list
- Deallocate (delete) the deleted item.
template <class ItemType>
void DoubleSortedType<ItemType>::insertItem(ItemType item)
{
NodeType<ItemType>* newNode = new NodeType<ItemType>;
NodeType<ItemType>* tempPtr = listData;
newNode->value = item;
if (listData == nullptr) {
newNode->back = nullptr;
newNode->next = nullptr;
listData = newNode;
length++;
return;
}
while (tempPtr != nullptr) {
if ((tempPtr->value) > item) {
break;
}
else {
tempPtr = tempPtr->next;
}
}
if (tempPtr == listData) {
newNode->back = nullptr;
newNode->next = listData;
listData->back = newNode;
listData = newNode;
length++;
return;
}
if (tempPtr == nullptr) {
NodeType<ItemType>* tail = listData;
while (tail->next != nullptr)
tail = tail->next;
newNode->back = tail;
newNode->next = nullptr;
tail->next = newNode;
length++;
return;
}
newNode->back = tempPtr->back;
newNode->next = tempPtr;
(tempPtr->back)->next = newNode;
tempPtr->back = newNode;
length++;
}
▶ InsertItem()
template <class ItemType>
void DoubleSortedType<ItemType>::removeItem(ItemType item)
{
NodeType<ItemType>* tempPtr = listData;
NodeType<ItemType>* deallocPtr;
while (tempPtr != nullptr) {
if ((tempPtr->value) == item) {
break;
}
else {
tempPtr = tempPtr->next;
}
}
if (tempPtr == nullptr) {
return;
}
deallocPtr = tempPtr;
if (tempPtr == listData) {
listData = tempPtr->next;
delete deallocPtr;
if (listData != nullptr) {
listData->back = nullptr;
}
length--;
return;
}
if (tempPtr->next == nullptr) {
tempPtr->back->next = nullptr;
delete deallocPtr;
length--;
return;
}
tempPtr->back->next = tempPtr->next;
tempPtr->next->back = tempPtr->back;
delete deallocPtr;
length--;
return;
}
▶ removeItem()
Exercise #2
Problems
- Implement recursive functions findItemRecur(), MinLoc(), and Sort().
- 1) findItemRecur() recursively finds "item" in the list.
- It returns "true" when the "item" exists, otherwise returns "false"
- findItemRecur() is "recursive function" and findItemRecursive() is the entry function.
- 2) MinLoc(location, MinPtr) recursively finds the MIN value of the list.
- 3) Sort(location) recursively finds the MIN value and sorts the list (must use "MinLoc")
- Call MinLoc() -> It returns the pointer to the MIN value.
- Then, swap "location" and MIN value.
- Recursively call sort() with updated "location"
- Call MinLoc() -> It returns the pointer to the MIN value (the rest of the list).
- Swap "location" and MINPtr.
- REPEAT! (Recursion)
template <class ItemType>
bool UnsortedType<ItemType>::findItemRecur(NodeType<ItemType>* location, ItemType& item){
if (location == nullptr) { // Base case: End of list
return false;
}
if (location->value == item) { // Base case: Item found
return true;
}
return findItemRecur(location->next, item); // Recursive case
}
▶ findItemRecur()
- Time Complexity: O(N)
template <class ItemType>
NodeType<ItemType>* UnsortedType<ItemType>::MinLoc(NodeType<ItemType>* location, NodeType<ItemType>* minPtr) {
if (location == nullptr) { // Base case: End of list
return minPtr;
}
if (location->value < minPtr->value) { // Update minPtr if a smaller value is found
minPtr = location;
}
return MinLoc(location->next, minPtr); // Recursive case
}
▶ minLoc()
template <class ItemType>
void UnsortedType<ItemType>::sort(NodeType<ItemType>* location) {
if (location == nullptr || location->next == nullptr) { // Base case
return;
}
NodeType<ItemType>* minPtr = MinLoc(location, location);
ItemType temp = location->value;
location->value = minPtr->value;
minPtr->value = temp;
sort(location->next);
}
▶ Sort()
Exercise #3
Problems
- Implement FibonacciMemoization() which calculates the Fibonacci series.
- improve given NaiveFibonacci()
- Let's make a matrix that stores the intermediate results. (Memoization)
- Step0: Initialize the matrix with -1.
- Step1: When it calculates each item, store it in the matrix.
- Step2: When the function is invoked, it searches the matrix first!
▶ memoization
int FibonacciMemoization(int n) {
recurFuncCountMemoization ++; // <- Do NOT edit nor move this instruction
if (n == 0 || n == 1) { // Base case: n이 0 또는 1인 경우
memoization[n] = 1;
return 1;
}
if (memoization[n] == -1) {
// 값이 저장되어 있지 않으면 재귀적으로 계산하여 저장
memoization[n] = FibonacciMemoization(n - 1) + FibonacciMemoization(n - 2);
}
// 메모이제이션 배열에 저장된 값 반환
return memoization[n];
}
▶ FibonacciMemoization()
- Time Complexity: O(N)
'CS > 자료구조' 카테고리의 다른 글
Programming Exercise: Lab #7 (1) | 2025.06.08 |
---|---|
Chapter 8: Tree (2) | 2025.06.08 |
Chapter 7: Recursion (0) | 2025.06.02 |
Programming Exercise: Lab #5 (0) | 2025.05.20 |
Chapter 6: Linked Structures (2) (5) | 2025.05.20 |