2020q1 Homework3 (quiz3)

contributed by < jwang0306 >

作業要求

測驗一： XOR Linked List

題目的敘述有一段 insert_node 的程式碼：

void insert_node(list **l, int d) {
    list *tmp = malloc(sizeof(list));
    tmp->data = d;

    if (!(*l)) {
        tmp->addr = NULL;
    } else {
        (*l)->addr = XOR(tmp, (*l)->addr);
        tmp->addr = *l;
    }
    *l = tmp;
}

上課時我被問到這個是插在 list 的頭還是尾巴，印象中我只有回答其中一個，但是後來仔細思忖，答案是頭尾都可以，端看參數 list **l 給的是頭還是尾。

已知 XOR 的運算特性：

• $A\oplus 0=A$
• $(A\oplus B)\oplus B=A$

走訪 list 的方式為當前節點與前一個節點取 XOR ，假設節點 1, 2, 3, 4 ，當前節點在 1 ：

       1    2    3    4
data  HAT  CAT  EAT  BAT

• 要走到 2 的話，就是 link(1) XOR 0 = (0 XOR 2) XOR 0 = 2 （根據特性二）
• 要插入一個 FAT 到尾巴的話，如果 list 為空，直接 *l = tmp ，前後都沒人因此 addr 為 NULL
• 如果 list 不為空
  • 我們希望插入後的 l 其位置為 link(4) XOR 0 ，因此取 XOR(tmp, (*l)->addr); ， 0 XOR link(4) = link(4) （根據特性一），然後將其更新為 l 的當前 addr ，這樣就清出了一個新的空間
  • 最後再把 tmp 放進去
  • 插在頭也是一樣的

解釋下方 XOR linked list 排序實作的原理

list *sort(list *start)
{
    if (!start || !start->addr)
        return start;

    /* split the list recursively */
    list *left = start, *right = start->addr;
    left->addr = NULL;
    right->addr = XOR(right->addr, left);

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

    /* merge the list recursively */
    for (list *merge = NULL; left || right;) {
        if (!right || (left && left->data < right->data)) {
            list *next = left->addr;
            if (next)
                next->addr = XOR(left, next->addr);

            if (!merge) {
                start = merge = left;
                merge->addr = NULL;
            } else {
                merge->addr = XOR(merge->addr, left);
                left->addr = merge;
                merge = left;
            }
            left = next;
        } else {
            list *next = right->addr;
            if (next)
                next->addr = XOR(right, next->addr);

            if (!merge) {
                start = merge = right;
                merge->addr = merge;
            } else {
                merge->addr = XOR(merge->addr, right);
                right->addr = RR2;
                merge = right;
            }
            right = next;
        }
    }

    return start;
}

上述的 XOR linked-list 用了類似 merge sort 的手法，不斷地切割 list ，最後拼裝起來：

• 先讓 next 走向下一個節點
• 首次進入迴圈， merge 為空，因此根據大小設定為 left 或 right ，addr 為 NULL
• 否則將 left 接上（假設為 left ）， 與上述走訪的概念一樣， merge->addr = XOR(merge->addr, left); (merge 就像上方 insert_node 的 l) ，並將 left->addr 更新為 0 XOR mege 也就是 merge （根據特性一），最後將 left 放進 merge