2024q1 Homework5 (assessment)

contributed by < YeeeLiang >

<因為自動飲料機而延畢的那一年> 讀後感想

愛因斯坦曾說，「如果給我一小時解決問題，而且那是足以改變人生的重大問題的話，我會花五十五分鐘去確認我是否問了正確的問題。」

要先問對問題，才能解決問題

「設定問題」在建立達成目標所需之手段的過程中，位於最上游。如果這裡就找錯問題，後續的解決方案和方案執行，也會環環相扣地錯下去。於是付出的勞力無法換來成果，變成白忙一場。

「問題」就是「落差」

「現狀」和「目標」的落差。目的地與現在地之間的差距，就是所謂的「問題」。將目前狀態和理想狀態加以「比較」的時候，問題才會顯現出來。

我們在朝著什麼目標邁進？

經驗豐富的管理顧問對經營者進行訪談時，會接二連三地拋出許多問題，像是「為何要將營業額設定成經營指標？」「為何光一個經營企劃部門就要有這麼多員工？」「在這個時間點進行業務員強化的企圖是什麼？」「你們如何向開發部門反饋消費者的意見？」

到底是哪來這麼多問題可以問的？因為管理顧問腦中已事先建構出企業的理想形象，並以該形象為基準，與客戶企業的現狀加以比較。透過比較發現落差，進而得到「認知」。問題不是憑空出現，而是先有比較對象當作基準，透過比較才能找出來的。

因此我認為，解決或問對的問題前需要先累積一定的經驗與知識。

問題討論

問題一：無法意會 Merge Sort 的頭跟尾兩兩合併，想請老師再說明一次。

資料參考：你所不知道的 C 語言: linked list 和非連續記憶體

頭跟尾兩兩合併：

從固定第一條串列改成頭跟尾兩兩合併，直到剩一條為止，比起前一方法的每次都用愈來愈長的串列跟另一條串列合併，頭尾合併在多數的情況下兩條串列的長度比較平均，合併會比較快。

當合併完頭尾後，偶數長度會少一半，奇數長度則為 (listsSize + 1) / 2，奇數更新的方式也可以用在偶數長度上。

TODO: 解釋 remove_list_node 的 indirect pointer 運作原理

搭配案例來說明

"Indirect pointer" 意味著使用指向指標的指標，這使得能夠修改指標所指向的內容，而不是僅僅修改指標本身。

remove_list_node 函式用於從鏈結串列中刪除節點。當我們使用 indirect pointer (間接指標) 的時候，實際上是通過指向指向節點的指標來進行操作。這樣做的好處是，我們可以直接存取到我們想要修改的指標，而不需要逐一走訪每個節點。尤其是當操作的節點數量非常大時，這樣做可以提高效率。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

如上圖，如果我們想要刪除節點 3，我們可以使用 indirect pointer。將 indirect pointer 指向指向節點 3 的指標。通過這種方式，直接存取並修改指向節點 3 的指標，從而刪除節點 3，而無需逐一走訪每個節點。因此，時間的複雜度為 O(1)。

總的來說，使用 indirect pointer 可以提高在鏈結串列中進行刪除操作的效率，特別是當我們需要頻繁地刪除節點時。

實作程式碼如下，原有三個節點存在，利用 indirect pointer 的方法將第二個節點刪除。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct List {
    Node *head;
} List;

void remove_list_node(List *list, Node *target)
{
    Node **indirect = &list->head;
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
    free(target); 
}

void print_list(List *list) {
    Node *current = list->head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    List list;
    list.head = (Node*)malloc(sizeof(Node));
    list.head->data = 1;
    list.head->next = (Node*)malloc(sizeof(Node));
    list.head->next->data = 2;
    list.head->next->next = (Node*)malloc(sizeof(Node));
    list.head->next->next->data = 3;
    list.head->next->next->next = NULL;

    printf("Original list: ");
    print_list(&list);
    
    remove_list_node(&list, list.head->next);
    
    printf("List after removal: ");
    print_list(&list);
    
    Node *current = list.head;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
    
    return 0;
}

這段程式碼在一開始定義了兩個結構，Node 表示鏈結串列中的節點，包含一個整數和指向下一個節點的指標；List 表示整個鏈結串列，包含一個指向鏈結串列 Head 的指標。

然後，用 remove_list_node 函式從鏈結串列中移除指定的節點。該函式接受兩個參數，一個是指向鏈結串列的指標，另一個是要被移除的節點的指標。在函式內部，我們使用了一個間接指標 indirect，這個指標指向將要更新的地方。然後，逐一走訪鏈結串列，直到找到指向要刪除節點的指標，然後更新這個指標，跳過該節點，並釋放其佔用的記憶體。

最後，使用 GDB 進行 debug 及運行程式碼。

~$ ./a.out

可得到下面的結果：

Original list: 1 2 3
List after removal: 1 3

問題二：Merge Sort 其中之一的 Divide and Conquer 的程式碼，為什麼是listsSize - m，而不是 listsSize - m/2 呢?

在你所不知道的 C 語言: linked list 和非連續記憶體文中，Divide and Conquer 的這段程式碼~~看不太懂~~：

誠實面對自己

    int m = listsSize >> 1;
    struct ListNode *left = mergeKLists(lists, m);
    struct ListNode *right = mergeKLists(lists + m, listsSize - m);

    return mergeTwoLists(left, right);

Divide and Conquer 是計算出中間位置ｎ，然後將 lists 陣列分為兩部分：lists[0] 到 lists[ｎ-1] 是左半部分，lists[ｎ] 到 lists[listsSize] 是右半部分。在使用遞迴呼叫 mergeKLists 函式，對左右兩部分進行合併，分別得到左半部分和右半部分的合併結果。

但是為什麼上面的程式碼是listsSize - m，而不是listsSize - m/2呢? 如下：

    int m = listsSize >> 1;
    struct ListNode *left = mergeKLists(lists, m);
-   struct ListNode *right = mergeKLists(lists + m, listsSize - m);
+   struct ListNode *right = mergeKLists(lists + m, listsSize-(m/2));

    return mergeTwoLists(left, right);

TODO: 重作第一次作業，彙整其他學員的成果 (挑出優秀的學員成果、重現實驗、檢驗出處 [數學推導]，並修正錯誤)，著重在程式開發的技巧 (e.g., indirect pointer, git commit message 的撰寫, 排序演算法的調整, 排序的 stability)

我選擇了 25077667 以及 vax-r 這兩位同學的 lab0 實作筆記作為參考，在25077667同學的筆記加入了很多創新的想法並改寫了原本作業給的程式碼；而vax-r同學的筆記則是整理的相當清晰易懂。

lab0 的作業要求是實作 a chain of circular queues，這並非是單純一個 queue，而是被鏈結串列所串連在一起的多個環狀佇列。如圖：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

`q_new()`

使用 calloc 函式來分配記憶體，確保新的佇列 head 節點 new_qhead 被初始化為零，並分配足夠大小以容納 struct list_head 的資料。當分配失敗時（new_qhead 為 NULL），函式返回 NULL，無法創建新的佇列。假若一切順利，函式則返回指向新佇列 head 節點的指標。

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *new_qhead = calloc(1, sizeof(struct list_head));
    if (!new_qhead)
        return NULL;
    INIT_LIST_HEAD(new_qhead);
    return new_qhead;
}

進一步探討 malloc 與 calloc 的差異為何？malloc 函式（memory allocation）用於分配指定大小的記憶體區塊，並返回一個指向該記憶體區塊起始位置的指標。但malloc分配的記憶體中的內容是未初始化的，意旨它們的值可能是隨機的或者舊的內容。而calloc 函式（contiguous allocation）將分配的每一位元組初始化為零。因此可預知malloc 的效能比 calloc 快，因為 calloc 需要額外的時間來初始化記憶體，但內容相對的不安全。

`q_insert_head()`

這個函式的目的是將一個新的 element 插入到佇列的 head。在這裡使用了Linux核心的連結串列結構 struct list_head *head，將 head 指向佇列的 head。

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_ele = malloc(sizeof(element_t));
    if (!new_ele)
        return false;
    INIT_LIST_HEAD(&new_ele->list);
    new_ele->value = strdup(s);
    if (!new_ele->value) {
        free(new_ele);
        return false;
    }
    list_add_tail(&new_ele->list, head);
    return true;
}

`q_size()`

計算佇列中 element 數量的函式。使用 list_for_each 逐一走訪佇列。每走完一次，就將 size 變數加一，以計算佇列中的element 數量。

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int size = 0;
    struct list_head *cur;
    list_for_each (cur, head)
        size++;
    return size;
}

`q_delete_mid()`

刪除佇列中中間的節點。使用 struct list_head *head 指向佇列的 head 節點的指標。使用兩個指標 first 和 second 來尋找中間節點。通過從佇列的兩端同時向中間移動，直到 first 和 second 相遇或者相鄰。

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *first = head->next;
    struct list_head *second = head->prev;
    while((first != second) && (first->next != second)) {
        first = first->next;
        second = second->prev;
    }
    element_t *node = list_entry(first, element_t, list);
    list_del(first);
    free(node->value);
    free(node);
    return true;
}

`q_delete_dup()`

刪除佇列中所有具有重複字串的節點。以下程式碼主要運用了雙重循環來處理重複節點的刪除操作，並且在操作過程中釋放了相關的記憶體。

在循環中，首先檢查是否存在重複節點。條件 &tmp->list != head && !strcmp(cur->value, tmp->value) 確保 tmp 不是頭節點並且 cur 和 tmp 的值相同。
如果有重複，則刪除 cur 節點，並釋放其內存。設置 dup = true; 表示有重複節點被處理。
如果前一個節點已經有重複節點被刪除（即 dup == true），則直接刪除 cur 節點，並重置 dup = false;。

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    bool dup = false;
    element_t *cur, *tmp;
    list_for_each_entry_safe (cur, tmp, head, list) {
        if (&tmp->list != head && !strcmp(cur->value, tmp->value)) {
            list_del(&cur->list);
            free(cur->value);
            free(cur);
            dup = true;
        } else if (dup) {
            list_del(&cur->list);
            free(cur->value);
            free(cur);
            dup = false;
        }
    }
    return true;
}

`q_swap`

透過雙向鏈節串列（double linked list）的資料結構來實現交換每兩個相鄰節點的功能。在每次迴圈中，first 和 second 分別指向相鄰的兩個節點。如果 second 指向的是 head，則跳出迴圈，避免處理最後一對可能是奇數個節點的情況。

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *first, *second;
    list_for_each_safe (first, second, head) {
    if (second == head)
        break;
        first->prev->next = second;
        second->prev = first->prev;
        first->next = second->next;
        first->prev = second;
        second->next->prev = first;
        second->next = first;
    }
}

`q_reverseK`

將鏈節串列每 k 個節點進行一次反轉。這裡使用了 q_size 函式來計算鏈節串列的節點總數，然後將其除以 k，得到需要進行反轉的次數 times，每次反轉都處理 k 個節點。

tail 是一個指向 struct list_head 的指標，用於在每個迭代中找到反轉的結束點。tmp 是一個新的空鏈節串列，用來暫時存放反轉後的 k 個節點。

new_head 是最終結果的新鏈節串列的頭。使用 list_for_each 來逐一走訪鏈節串列，直到找到第 k 個節點（即 tail），或者是逐一走訪完整個鏈節串列。確保 tail 指向每次反轉的結束位置。

接著使用 list_cut_position 將從 head 到 tail->prev 的節點切下來，並將它們放入 tmp 鏈節串列中。然後使用 q_reverse 函式來反轉 tmp 鏈節串列中的節點。

最後使用 list_splice_tail_init 將 tmp 鏈節串列中的節點接入 new_head 鏈節串列的尾部，並且初始化 tmp 鏈節串列以便下一次使用。

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    if (!head)
        return;

    int times = q_size(head) / k;
    struct list_head *tail;

    LIST_HEAD(tmp);
    LIST_HEAD(new_head);

    for (int i=0; i < times; i++) {
        int j = 0;
        list_for_each(tail, head) {
            if (j >= k)
                break;
            j++;
        }
        list_cut_position(&tmp, head, tail->prev);
        q_reverse(&tmp);
        list_splice_tail_init(&tmp, &new_head);
    }
    list_splice_init(&new_head, head);
}

2024q1 Homework5 (assessment)

<因為自動飲料機而延畢的那一年> 讀後感想

問題討論

頭跟尾兩兩合併：

q_new()

q_insert_head()

q_size()

q_delete_mid()

q_delete_dup()

q_swap

q_reverseK

Read more

2024q1Homework1 (lab0)

2024q1 Homework2 (quiz1+2)