2019q3 Homework4 (quiz4)

contributed by < uccuser159 >

測驗 1

考慮一個單向 linked list:

typedef struct __list {
    int data;
    struct __list *next;
} list;

在不存在環狀結構的狀況下，以下函式能夠對 linked list 元素從小到大排序:

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    LL0;

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                LL1;
            } else {
                LL2;
                merge = merge->next;
            }
            LL3;
        } else {
            if (!merge) {
                LL4;
            } else {
                LL5;
                merge = merge->next;
            }
            LL6;
        }
    }
    return start;
}

請補完程式碼。

思考

    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    LL0;
    
    left = sort(left);
    right = sort(right);

由上面程式可知，left 與 right 會不斷經過遞迴將 linked list 做切割，為了要比較大小，left = sort(left)用來抓出第一個元素，將left->next = NULL。

利用 sort(right) 遞迴到最後的部分，直到 right->next == NULL，所以 sort(right) 最後指向 3 這個 node，再一路遞迴 start 回去。

利用 *merge 來建立 node 之間的連結

if (!right || (left && left->data < right->data)) {
   if (!merge) {
        LL1;
   } else {
        LL2;
        merge = merge->next;
   }
   LL3;
} else {
    if (!merge) {
        LL4;
    } else {
        LL5;
        merge = merge->next;
    }
    LL6;
}

以此範例

• if (!merge) 為第一次要做 merge 的元素，所以 LL4 為start=merge=right
• 接著要讓 right 更新跑下一個 node 來判定與left之間的大小，LL6 為right=right->next
• 因為right==NULL或是left與right都有指向某 node 但left->data比較小（此處範例為right==NULL的狀況），則left 指向 merge ，因為不是第一次做 merge 的元素，跑到 else 判斷，所以 LL2 為 merge->next = left (因為有start=merge的操作)

相反的狀況可以推回 LL1 為 start=merge=left；LL3 為 left=left->next；LL5 為merge->next = right

• 延伸問題

說好的進度呢？