# 2020q3 Homework1 (quiz1)
contributed by <[haoyu0970624763](https://github.com/haoyu0970624763/sysprog21-quiz1)>

延伸問題一:程式運作原理
===
## 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;
    
    /* AA1 = "assert(new_node)" */
    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;
    /* AA2 = "*indirect = new_node" */
    *indirect = new_node;
}

` 功能：新增節點在 list 最後面 `

#### **運作原理解說**
1. 動態新增新的 node，將參數 `new_value` 賦值給
`new_node->value`， `new_node->next` 指向 `NULL`
2. 檢查剛剛動態新增的 node 是否成功
3. 將新節點插入到 list 最尾端

`AA1` 跟 `AA2` 選項很少,很好判斷

## find_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

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

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

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

`功能：刪除特定節點並釋放空間`

## swap_pair

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

`功能：交換 list 中第 i 個節點跟第 i+1 節點的位置（i屬於奇數）`

#### ***運作原理解說***

4-5 行

`node` 為指向 `＆head` 的 pointer
`tmp` 先紀錄 node pointer 指向的位址 , 也就是`&list[i]`

digraph graphname{
    node[shape=box]
    rankdir = LR
    {
        A[label="node"]
        B[label="tmp"]
        C[label="head"]   
    } 
    {
        D[label="list[i]"]
        E[label="list[i+1]"]
        F[label=""]
    }
    D->E->F
    {
        rank=same
        B->D   
    }
    {
        rank=same
        A->C->D
    }     
}

第 8 行 `tmp->next = (*node)->next ;`
由於函式為 swap_pair , 所以 `tmp->next` 應為 `list[i+1]->next`
因此我們可判斷 `BB2` 為 `*node = (*node)->next;`

執行完 `*node = (*node)->next;`

digraph graphname{
    node[shape=box]
    rankdir = LR
    {
        A[label="node"] 
    }
    {
        B[label="tmp"] 
        C[label="head"] 
    } 
    {
        D[label="list[i]"]
        E[label="list[i+1]"]
        F[label=""]
    }
    D->E->F
    {
        rank=same
        B->D   
    }
    {
        rank=same
        A->C->E  
    }
}

執行完 `tmp->next = (*node)->next;`

digraph graphname{
    node[shape=box]
    rankdir = LR
    {  
        A[label="node"]
        B[label="head"]
        C[label="list[i+1]"]  
    } 
    {
        rank=same
        A->B->C
    }     
}

digraph graphname{
    node[shape=box]
    rankdir = LR
    {
        B[label="tmp"] 
    } 
    {
        D[label="list[i]"]
        E[label=""]
    }
    D->E
    {
        rank=same
        B->D   
    }
}

執行完 `(*node)->next = tmp;`

digraph graphname{
    node[shape=box]
    rankdir = LR
    {
        A[label="node"]
        B[label="tmp"]
        C[label="head"]   
    } 
    {
        D[label="list[i+1]"]
        E[label="list[i]"]
        F[label=""]
    }
    D->E->F
    {
        rank=same
        B->E  
    }
    {
        rank=same
        A->C->D
    }     
}

**迴圈下一層**

已經換完前面兩個 , node 變數應跳到 list 中 , 指向後兩個成員的位址 , 進行下一次的 swap
所以 `BB1`為 `node = &((*node)->next->next)`

digraph graphname{
    node[shape=box]
    rankdir = LR
    {
        A[label="node"]
        C[label="head"]   
    } 
    {
        D[label="list[i+1]"]
        E[label="list[i]"]
        F[label=""]
    }
    D->E->F

    {
        rank=same
        C->D
    }     
    {
        rank=same
        A->F  
    }
}

## reverse

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

`功能：把 list 反過來連接`

#### ***運作原理解說***

`head` 表走訪 list 過程中的當前節點 , 從 list 最前端開始
`cursor` 表示上次走訪的節點
`next` 表當前節點的下一個節點

digraph {
    node[shape=box]
    rankdir = LR
    { 
        A[label="node1"]
        B[label="node2"]
        C[label="node3"]
    }
    {
        cursor[shape=none]
        cursor->NULL
        A->B->C
    }
    { 
        rank=same;
        head[shape=none]
        head->A 
    } 
    { 
        rank=same;
        next[shape=none]
        next->B
    }  
}

從第 8 行 `head = next;`
我們可以推斷出 CCC 應將上次走訪的節點串接在當前節點後面,還有更新上次走訪的節點以利用在下次迴圈中
所以 `CCC` = `head->next = cursor; cursor = head;`

概念如下

執行 `head->next = cursor;`

digraph {
    node[shape=box]
    rankdir = LR
    {       
        A[label="node1"]
    }
    { 
        A->NULL
    }
    { 
        rank=same;
        D[shape=none,label="head"]
        D->A
    }  
}

digraph {
    node[shape=box]
    rankdir = LR
    {       
        A[label="node2"]
        B[label="node3"]
    }
    A->B
    { 
        rank=same;
        D[shape=none,label="next"]
        D->A
    }  
}

執行 `cursor = head;` 與 `head = next;`

digraph {
        node[shape=box]

         rankdir = LR
        { 
            
            A[label="node1"]
            B[label="node2"]
            C[label="node3"]
        }
        {
            
            A->NULL
            B->C
        
        }
       
        { 
            rank=same;
            D[shape=none,label="cursor"]
            D->A
            
            
        } 
         { 
            rank=same;
            next[shape=none,label="next & head "]
            next->B
        } 
        
}

執行迴圈下一層

digraph {
    node[shape=box]
    rankdir = LR
    {  
        A[label="node1"]
        B[label="node2"]
        C[label="node3"]
    }
    { 
        A->NULL
        B->C
    }
    { 
        rank=same;
        D[shape=none,label="cursor"]
        D->A    
    } 
    { 
        rank=same;
        head[shape=none]
        head->B
    } 
    { 
        rank=same;
        next[shape=none]
        next->C
    }   
}

執行第二次的 `head->next = cursor;`

digraph {
    node[shape=box]
    rankdir = LR
    { 
        A[label="node1"]
        B[label="node2"]
        C[label="node3"]
    }
    {  
        B->A->NULL
        C
    } 
    { 
        rank=same;
        D[shape=none,label="cursor"]
        D->A        
    } 
    { 
        rank=same;
        head[shape=none]
        head->B
    } 
    { 
        rank=same;
        next[shape=none]
        next->C
    } 
}

:::warning
**同樣的邏輯繼續下去即可求的反的 list**
:::
## print_list

void print_list(node_t *head)
{
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}

`功能：印出節點的值`

延伸問題二：指標的指標改寫
===

## swap_pair

原本的 `swap_pair` 中的 `head` 在函式內部採用 **call by value** , 改動 `head` 時 , 實際上不會改動到原本的`head` , 是更改複製出來的 `head`

可以用**call by reference** 的方式來避免此狀況
下面是改寫的程式碼

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

透過 **call by reference** 取代原本 **call by value** 的參數傳遞方式

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

延伸問題三：recursive_reverse
===
將上面的 reverse 函式的概念用遞迴的方式加以實做

void recursive_reverse_step(node_t *curr, node_t *prev, node_t **head)
{ 
    /* next represent the element behind the current element in the list 
     * if next equal to NULL , then the element we traced is last in the list 
     */
    node_t *next = curr->next;
    if (!next) {        
        *head = curr;
        return; 
    }
    /*  prev represent the previous recursive function parameter curr
     *  it should be linked behind the current element 
     */ 
    curr->next = prev;    
    
    recursive_rev_step(next, curr, head);
} 

void recursive_reverse(node_t **head)
{
    if (!head)
        return;

    recursive_reverse_step(*head, NULL, head);
}

延伸問題三： Fisher–Yates shuffle
===

void shuffle(node_t **head) {
  srand(time(NULL));

  /* Trace the length of the linked list */
  int len = 0;
  node_t **indirect = head;
  while (*indirect) {
    len++;
    indirect = &(*indirect)->next;
  }

  /* Append shuffling result to another linked list */
  node_t *new = NULL;
  node_t **new_head = &new;

  while (len) {
    int random = rand() % len;
    indirect = head;

    while (random--)
      indirect = &(*indirect)->next;

    /* tmp means the node we randomly chosen */
    node_t *tmp = *indirect;
    /* Shift the element behind tmp to the position of tmp */
    *indirect = (*indirect)->next;
    /* put the node we chosen to the head of new list */
    tmp->next = *new_head;

    *new_head = tmp;
    len--;
  }

  *head = *new_head;
}

* Step1 : 首先，先走訪整個原始的 linked list，算出原本的 linked list 有多長
* Step2 : 根據 舊linked list 長度生成一個不大於串列長度之隨機亂數並找到相對應節點
* Step3 : 將對應節點從舊 linked list 刪除 , 並將其新增至新的 linked list 的最前面 (也可以選擇新增至串列的最後面,但需要額外紀錄最後面的節點 )
* 回到 stpe2