CS/자료구조

Programming Exercise: Lab #6

arsenic-dev 2025. 6. 2. 03:01

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

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