# 2020q3 Homework1 (quiz1)
contributed by < `CW-B-W` >
[github](https://github.com/CW-B-W/sysprog2020q3-quiz1)

###### tags: `sysprog2020`

## Outline
[TOC]

## 測驗`1`
### add_entry
* AA1 = `assert(new_node)`...為什麼題目裡不是放在 `malloc(...)`的 下一行???
* AA2 = `*indirect = new_node`。indirect 指向的物件型態並不是 `node_t` (不是直接指向一個 node_t)；而是指向 `node_t*`，
也就是指向某個 `node->next` "這個變數的值"。故修改 `*indirect` 會直接改到某個 `node->next` 的值

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));

    assert(new_node); // AA1 ??
    
    new_node->value = new_value;
    new_node->next = NULL;

    while (*indirect)
        indirect = &(*indirect)->next;
    *indirect = new_node; //AA2
}

### swap_pair
* BB1 = `node = &(*node)->next->next` 將 node 更新為後兩個 node
* BB2 = `*node = (*node)->next` 將 head 或是 某個 node 的 next 變數設定為 其指向的 node 的下一個 node

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

### reverse
* CCC = `head->next = cursor; cursor = head`，原來有兩條程式碼...。
* 程式原理
* Init: 先假裝整個 新list 沒有 node
* Loop: 用類似 `add_entry` 的方式，將 原本list 的 head 當成 新node 從 head 插入，並且將 原本list `remove_entry`
* 使用 cursor 代表 新list 的 head
* 使用 next 代表被 原本list `remove_entry` 的 node
* 將 next 插入 新list 的 head (cursor)

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        head->next = cursor;
        cursor = head
        head = next;
    }
    return cursor;
}

## 延伸問題
### 1. Graphviz
待續

### 2. 修改 swap_pair & reverse 成不用回傳指標
#### swap_pair
* 直接將原本 `node_t *head` 改成 `node_t **head` ，並對應更新即可

void swap_pair(node_t **head)
{
    for (node_t **node = head; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
}

#### reverse
* 直接將原本 `node_t *head` 改成 `node_t **head` ，並對應更新即可

void reverse(node_t **head)
{
    node_t *cursor = NULL;
    while (*head) {
        node_t *next = (*head)->next;
        (*head)->next = cursor;
        cursor = *head;
        *head = next;
    }
    *head = cursor;
}

### 3. 遞迴版 reverse
* rev_resursive
* 固定回傳 reverse 之後的 head
* 每個 node 自己爲自己做 reverse

static node_t *rev_resursive(node_t *node)
{
    if (!node->next)
        return node;
    node_t *new_head = rev_resursive(node->next);
    node->next->next = node;
    return new_head;
}

void reverse_recursive(node_t **head)
{
    node_t *old_head = *head;
    *head = rev_resursive(*head);
    old_head->next = nullptr;
}

### 4. Fisher-Yates Shuffle
* 從 head 開始，依序遍歷每個 node。造訪某個 node 時，產生一亂數值為`0 ~ 此 node 後的節點個數+1`，以此亂數值決定要與後面第幾個節點交換
* 亂數值 = 0，不交換
* 亂數值 = 1，需特別處理交換
* line12~14 特別針對此情形
* 亂數值 > 1，直接將兩節點對應的 next 交換
* 一共換兩對邊
* 指到這兩個節點的 next
* 這兩個節點指出的 next

static void swap(node_t **v1, node_t **v2)
{
    node_t *tmp = *v1;
    *v1 = *v2;
    *v2 = tmp;
}

static void swap_node(node_t **n1_ind, node_t **n2_ind)
{
    if (n1_ind == n2_ind)
        return;
    if ((*n1_ind)->next == *n2_ind) {
        swap(&(*n1_ind), &(*n2_ind)->next);
        swap(&(*n1_ind), &(*n2_ind));
    } else {
        swap(&(*n1_ind), &(*n2_ind));
        swap(&(*n1_ind)->next, &(*n2_ind)->next);
    }
}

void fisher_yates_shuffle(node_t **head)
{
    int list_len = 0;
    node_t *cur = *head;
    while (cur) {
        list_len += 1;
        cur = cur->next;
    }

    while (--list_len) {
        int random_step = rand() % (list_len+1);
        if (random_step > 0) {
            node_t **node = head;
            while (random_step--) {
                node = &(*node)->next;
            }
            swap_node(head, node);
        }
        head = &(*head)->next;
    }
}