# 2020q3 Homework1(quiz1)
contributed by <`StevenChen8759`>

> 相關連結：
> [2020秋季進階電腦系統理論與實作 quiz1 作業說明](https://hackmd.io/@sysprog/rJ7WDWNVv)
> [2020秋季進階電腦系統理論與實作 quiz1 作業繳交區](https://hackmd.io/@sysprog/2020-homework1)
> [2020秋季進階電腦系統理論與實作 quiz1 GitHub]()
> [color=green]

## :chains: 程式運作原理分析

### :bulb: `add_entry()` 分析

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

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

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

* 指標的指標 `indirect` 開始時指向 `head`，而傳入的 `head` 指向串列頭，參考下圖:
* 接著我們看到上列程式的 `while` 迴圈，當 `indirect` 指向的位址非 `NULL` 時，串列會改指向下一個節點指標的位址，操作原理如下:
* 對 `indirect` 進行**取值運算**後，將得到串列頭的記憶體位址，相當於原呼叫函式的 `head` 指標。
* 透過 `indirect member access operator` ，即 `->` 運算子，取出 `list` 結構中的 `next` 欄位。
* 最後，透過**取址運算子**將 `(*indirect)->next` 的記憶體位址，指派給指標的指標 `indirect`，下次執行欲存取下一節點位址時，只需將 `indirect` 作取值運算，即可得到下一節點的記憶體位址，並做出對應的運算。
* 參考 [GNU C Reference Manual - Operator Precedence](https://www.gnu.org/software/gnu-c-manual/gnu-c-manual.html#Operator-Precedence) 的部分，因為 *Member Access Operator* `->` 的優先權高於*Address Operator* `&` ，因此 `&((*indirect)->next)` 陳述式可簡化成上列 `&(*indirect)->next` 並維持效果不變。
* 上述 `while` 迴圈執行到跳離時，`indirect` 指標會指向串列最後一個節點的 `next` 欄位，修改該欄位值指向新插入的節點，即完成 `add_entry()` 函式，參考下列執行結果：

* 值得一提的是，上述的 assert 的執行時機不佳，參考 [manual of malloc()]() 可知在記憶體配置失敗時，`malloc()` 會回傳 `NULL`，因此程式應在 `malloc()` 完成後直接執行 `assert()`，以避免接續的記憶體操作錯誤。參考下列較佳實現：

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

    node_t *new_node = malloc(sizeof(node_t));
    assert(new_node);
    
    new_node->value = new_value;
    new_node->next = NULL;
    
    while (*indirect)
        indirect = &(*indirect)->next;
    *indirect = new_node;
}

### :bulb: `remove_entry()` 分析

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}

* `remove_entry()` 函式相對來說就直覺不少，直接透過 `for-loop` 走訪節點上的每一個元素，若有符合的直接 return 該節點位址，否則持續走訪至串列尾，若元素不存在 List 中即回傳 `NULL`。

### :bulb: `find_entry()` 分析

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

* 使用的 `indirect` 指標操作移動元素方法與 `add_entry()` 相同，主要差在判斷式在找到相應 entry 時即跳離迴圈。
* 跳離迴圈後， 即可透過 `indirect` 指標的指標操作 `next` 欄位，使其指向 `entry` 的下一節點，並呼叫 `free()` 釋放記憶體空間。
* 最終刪除 entry 的執行結果如下：

### :bulb: `swap_pair()` 分析

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

* 比對參考輸出，`swap_pair()` 函式會交換相鄰的兩個節點。
* 接著我們觀察 for-loop 的行為，此迴圈從串列頭開始走訪，在現時節點與現時下一節點皆非空值時才會持續執行，且迴圈在每一個 iteration 會移至下兩個節點，以繼續進行 swap_pair 操作。
* 以下操作運用了指標的指標，將 List 中的元素兩兩互換，流程如下：
* 下一個 Iteration 仍執行相同操作，僅指標指向位置不同。

### :bulb: `reverse()` 分析

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

* 此處的實現與 [lab0 中的 reverse 實現](https://hackmd.io/@StevenHHChen/2020q3_lab0#-%E7%A8%8B%E5%BC%8F%E5%8A%9F%E8%83%BD%E6%A6%82%E8%A6%81)大致上相同，各指標對應如下:

| lab0 reverse | quiz1 reverse |
| -------- | -------- |
| prev | cursor |
| curr | head |
| nex | next |
* 此處的實現會在執行結束時回傳 reverse 後串列的 head 記憶體位址，以供 caller 更新 head 值。

## :hammer_and_wrench: 指定函式改寫

### :bulb: `swap_pair()` 的改寫實現 - 指標的指標

void swap_pair_ptp(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;
    }
}

* 新的 `swap_pair_ptp()` 實現在更改成指標的指標操作後，在函式内的第一個 iteration，呼叫者的 head 指標即順著 swap 的操作修改成指向第二個節點，故不需再回傳新的 head 指標值。

### :bulb: `reverse()` 的改寫實現 - 指標的指標

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

* 透過指標的指標操作，僅需改變函式內的陳述式即可，並在迴圈結束後直接指派新的 head 值，即可避免回傳指標。
### :bulb: `reverse()` 的改寫實現 - 遞迴方法

node_t* rec_reverse(node_t **head, node_t *maniptr){

    node_t *curr = maniptr, *prev;
    if (curr->next)
        prev = rec_reverse(head, curr->next);

    if (curr->next != NULL){
        node_t *temp = curr->next;
        curr->next = temp->next;
        temp->next = curr;
    }
    else *head = curr;

    return curr;
}

* 程式設計的思路流程：
* 透過遞迴走訪至最後一個節點，並指派新的 `head` 指標。
* 遞迴函式開始回傳，透過回傳位址的操作，逐一進行各節點指向 swap ，達成串列反轉的功能。
* TODO: 現行實現包含了兩個輸入引數 (Argument)，可思考減少成一個輸入引數的實現，使程式功能更精簡優雅。

## :radio_button: List 節點實作 `Fisher-Yates Shuffle`
* TODO