Try   HackMD

2020q1 第 1 週測驗題

目的: 檢驗學員對 linked list 的認知

作答表單


測驗 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;
}

請補完程式碼。

作答區

LL0 = (a)

  • (a) left->next = NULL
  • (b) right->next = NULL
  • (c) left = left->next
  • (d) left = right->next

LL1 = (e)

  • (a) start = left
  • (b) start = right
  • (c) merge = left
  • (d) merge = right
  • (e) start = merge = left
  • (f) start = merge = right

LL2 = (a)

  • (a) merge->next = left
  • (b) merge->next = right

LL3 = (a)

  • (a) left = left->next
  • (b) right = right->next
  • (c) left = right->next
  • (d) right = left->next

LL4 = (f)

  • (a) start = left
  • (b) start = right
  • (c) merge = left
  • (d) merge = right
  • (e) start = merge = left
  • (f) start = merge = right

LL5 = (b)

  • (a) merge->next = left
  • (b) merge->next = right

LL6 = (b)

  • (a) left = left->next
  • (b) right = right->next
  • (c) left = right->next
  • (d) right = left->next

延伸問題:

  1. 解釋上述程式運作原理;
  2. 指出程式改進空間,特別是考慮到 Optimizing merge sort;
  3. 將上述 singly-linked list 擴充為 circular doubly-linked list 並重新實作對應的 sort;
  4. 依循 Linux 核心 include/linux/list.h 程式碼的方式,改寫上述排序程式;
  5. 嘗試將原本遞迴的程式改寫為 iterative 版本;
  1. merge sort
  2. 切區塊的方式可以改進,不知是否能切中間點