# 2020q3 Homework1 (quiz1)

contributed by < `jeremy3951` >

加入日期:2020/9/15

:::success
延伸問題1：
解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
:::

###### tags: `(2020q3)進階電腦系統理論與實作`

## `add_entry`:

在`add_entry(&head,72)`這個指令中可以看到第一個引數是head的位址,相對的,在此function中第一個input就是要用**的形式來接值.
- 新增一個indirect來紀錄head（拿來移動的）
- 接下來三行所描述的就是新增一個node並將pointer指向NULL
- AA1: `assert(new_node)` assert function用來確定此new node是否有成功建立.
- while迴圈：
`*indirect` : 代表head的位址
`*indirect->next` : head下一個點的記憶體位址
`indirect = &(*indirect)->next` : 把裝著上述(裝著head下一個點的記憶體位址)的記憶體位址取出,並寫回`indirect`

digraph struct{
        
        indirect[shape=plaintext,fontcolor=red]
        head[shape=plaintext,fontcolor=red]
        NULL[shape=plaintext,fontcolor=black]
        rankdir = "LR"
        
        subgraph struct1{
        
            node1 [
            shape = record
            label = " value|*next"
            ]
        }
        
        indirect->head->node1
        node1->NULL
        
        }   

## `find_entry`:
根據指標指到的點比較value值，若比較到一樣的value則跳出for迴圈並return當下的點的位址

## `remove_entry`:
跟add很像,但是要刪除節點前要先找到該節點！
`*indirect = entry->next`這行把entry指向的點寫入`*indirect`中以代替它.

## `swap_pair`:
:::warning
此function的功能是把linked list中的兩個點為一數作交換.
:::
我當時的疑問：BB1為何要走兩格?
tmp是負責紀錄第一個點,node是負責紀錄第二個點,node交換完後會變第一個點,所以要走兩格到第三個點去做接下來的交換.

digraph struct{
    node_[shape=plaintext,fontcolor=red]
    tmp[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    
    rankdir = LR;
    {
    rank = "same";
    node_->tmp->node1
    }
    node1->node2->node3->NULL
}

After `*node = (*node)->next`

digraph struct{
    node_[shape=plaintext,fontcolor=red]
    tmp[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    
    rankdir = LR;
    {
    rank = "same";
    tmp->node1
    }
    {
    rank = "same";
    node_->node2
    }
    node1->node2->node3->NULL
}

After `tmp->next = (*node)->next;`

digraph struct{
    node_[shape=plaintext,fontcolor=red]
    tmp[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    
    rankdir = LR;
    {
    rank = "same";
    tmp->node1
    }
    {
    rank = "same";
    node_->node2->node3
    }
    node1->node3->NULL
}

After `(*node)->next = tmp;`

digraph struct{
    node_[shape=plaintext,fontcolor=red]
    tmp[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    
    rankdir = LR;
    {
    rank = "same";
    tmp->node1
    }
    {
    rank = "same";
    node_->node2->node1
    }
    node1->node3->NULL
}

## `reverse` :
:::warning
此function的功能是把lined list倒序
:::

`head` :當下的點
`cursor` :倒序中的下一點(等等要被head指向的點)
`next` :原序中的下一點

digraph struct{
    rankdir = LR;
    head[shape=plaintext,fontcolor=red]
    cursor[shape=plaintext,fontcolor=red]
    next[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    NULL1[shape=plaintext,fontcolor=black]
    
    {
    rank = "same";
    head->node1
    }
    {
    rank = "same";
    next->node2
    }
    cursor->NULL1
    node1->node2->node3->NULL
}

After `head->next = cursor;cursor = head`

digraph struct{
    head[shape=plaintext,fontcolor=red]
    cursor[shape=plaintext,fontcolor=red]
    next[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    NULL1[shape=plaintext,fontcolor=black]
    rankdir = LR;
    
    {
    head->node1
    next->node2
    cursor->node1
    }
    node1->NULL1
    node2->node3->NULL
}

After `head = next`
`

digraph struct{
    head[shape=plaintext,fontcolor=red]
    cursor[shape=plaintext,fontcolor=red]
    next[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    NULL1[shape=plaintext,fontcolor=black]
    rankdir = LR;
    
    {
    head->node2
    next->node2
    cursor->node1->NULL1
    }
    node2->node3->NULL
}

next再往下走

digraph struct{
    head[shape=plaintext,fontcolor=red]
    cursor[shape=plaintext,fontcolor=red]
    next[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    NULL1[shape=plaintext,fontcolor=black]
    rankdir = LR;
    
    {
    head->node2
    next->node3
    cursor->node1->NULL1
    }
    node2->node3->NULL
}

再回到第一張圖重複執行直到head==NULL,最後再return cursor當作head即可.

## `print_list`:
用current指標走訪整個linked list並且output value.

:::success
延伸問題2：
函式`swap_pair`和`reverse`對於指標的操作方式顯然異於`add_entry`及
`remove_entry`,需要額外做`head = ...`的更新,請用指標的指標來改寫.並避免回傳指標;
:::
## `swap_pair` 改寫:

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

參考:[你所不知道的c語言：指標篇](https://hackmd.io/@sysprog/c-pointer?type=view#%E6%B2%92%E6%9C%89%E3%80%8C%E9%9B%99%E6%8C%87%E6%A8%99%E3%80%8D%E5%8F%AA%E6%9C%89%E3%80%8C%E6%8C%87%E6%A8%99%E7%9A%84%E6%8C%87%E6%A8%99%E3%80%8D)

看了這篇文章之後一開始還不太了解意思,不過透過實作+紙筆trace後,我才了解到為何改成指標的指標後就不用再return head了.
這是原本的swap但是我拿掉了 return head 跑出來的結果.
再執行一次:
看到這邊我發現,`swap_pair(head)`是第一個點,經過轉換後變成了第二個點,可是第一個點就沒有被指到,所以在print_list的時候總是從第二個點開始印,這也是為何原本的function要 return head 的原因.
最重要的是 : **head裡面的記憶體位置一直沒被改變！！**
一直都是指向value=72的這個點,所以一開始要用head的記憶體位址來當作input,然後當執行完`*node = (*node)->next;`時,head的內容的被改成第二個點也就是等等swap完後的第一個點,這樣就能達到目的了.

## `reverse` 改寫:

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

當while迴圈執行完後,`*head`會指向NULL,所以最後一行把真正的head位址寫入`*head`.

跟`swap_pair`的問題很類似, 如果沒有`return cursor`的話會只印出一個點(72),因為head沒有被改變,所以依然指向72.

:::success
延伸問題3：
以遞迴改寫上述的`reverse`,注意,你可能因此需要建立新的函式,如`rev_recursive`,隨後在`reverse`函式中呼叫`rev_recursive`;
:::

node_t *rev_recursive(node_t **head ,node_t *cursor){
    if((*head)->next!=NULL){
        node_t *next = (*head)->next;
        (*head)->next = cursor; 
        cursor = *head;
        *head = next;
        
        rev_recursive(&next , cursor);
    }
    else{
        (*head)->next = cursor;
        return *head;
    }
}

此function的使用方式： `head = rev_recursive(&head,NULL)`
解釋： 把reverse想成recursive的模式,我是由1.傳值2.重複做一樣的事這兩個特性下去想的.

digraph struct{
    head[shape=plaintext,fontcolor=red]
    cursor[shape=plaintext,fontcolor=red]
    next[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    rankdir = LR;
    {
    rank = "same";
    head->node1
    }
    {
    rank = "same";
    next->node2
    }
    {
    rank = "same";
    cursor->NULL
    }
    node1->node2->node3->NULL
}

透過觀察我發現cursor,head,next會很有規律的往右邊移動,這部份就是遞迴的部份.
再來就是傳值,cursor無法藉由head找到(如下圖),只有next可以,所以我把這兩個值(head,cursor)當引數傳遞.

digraph struct{
    head[shape=plaintext,fontcolor=red]
    cursor[shape=plaintext,fontcolor=red]
    next[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    rankdir = LR;
    head->node2
    {
    rank = "same";
    next->node2
    }
    {
    rank = "same";
    cursor->node1->NULL
    }
    node2->node3->NULL
}

## 實作 Fisher–Yates shuffle
:::success
延伸問題4：
針對`singlly-linked list`的節點,實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) ,你應該盡量降低記憶體的使用量;
:::
此演算法一開始是用另一個陣列來裝亂數值,又或者把亂數值裝在陣列後面,如下圖

digraph struct{
    rankdir=LR;
    box[shape=record];
 box[label="{<value> 1| <next>2|<next> 3|<next>|<next>|<next>}"];
}

不過用linked list的方法,可以省去裝亂數的記憶體空間.

linked list的方法:

void ran(node_t **current,int num){
    srand(time(NULL));
    for(int i=0;i<num;i++){
    
    int ra = rand()%num;         //ra means the (ra+1)th number 
    node_t *head = *current;    // head  
    node_t *pre = NULL;       //before the current
    
    if(ra!=0){
    while(ra!=0){   
        pre = *current;
        *current = (*current)->next;
        ra--;
    }                       //走到要被置換的點
    pre->next = (*current)->next;
    (*current)->next = head;
    }
    }
}

- (ra+1) : 第幾個數字要被換到最前面
- head : 永遠指著第一個點
- current : 當下要被置換的點
- pre : 被置換的點的前一個點

使用：

    node_t *head = NULL; 
    int num;
    scanf("%d",&num);
    
    for(int i =1;i<=num;i++){
        add_entry(&head, i); 
    }
    ran(&head,num);

觀念：

從linked list中隨機選一個數字(1 ~ n),將此數字移到最前面當作head,再從剩下的list中(2 ~ n)再隨機選一個數字,再移到最前面,以此類推.
假設選到第二個node:

digraph struct{
    head[shape=plaintext,fontcolor=red]
    current[shape=plaintext,fontcolor=red]
    pre[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    rankdir = LR;
    {
    rank = "same";
    head->node1
    }
    {
    rank = "same";
    pre->node1
    }
    {
    rank = "same";
    current->node2
    }
    node1->node2->node3->NULL
}

node1指向node3：

digraph struct{
    head[shape=plaintext,fontcolor=red]
    current[shape=plaintext,fontcolor=red]
    pre[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    rankdir = LR;
    {
    rank = "same";
    head->node1
    }
    {
    rank = "same";
    pre->node1
    }
    {
    rank = "same";
    current->node2
    }
    node1->node3->NULL
    node2->node3
}

把node2指向head：

digraph struct{
    head[shape=plaintext,fontcolor=red]
    current[shape=plaintext,fontcolor=red]
    pre[shape=plaintext,fontcolor=red]
    NULL[shape=plaintext,fontcolor=black]
    rankdir = LR;
    {
    rank = "same";
    head->node2
    }
    {
    rank = "same";
    pre->node2
    }
    {
    rank = "same";
    current->node2
    }
    node2->node1->node3->NULL
    
}

再隨機選下一個數.....

## 心得：
這份作業對我而言是很好的鍛鍊也是一個大挑戰,linked list我一直都沒真正的實作過,都是紙上談兵而已,對於指標的概念也是非常模糊...

透過實作這次的作業以及和朋友激烈的討論,我才發現我原本的某些觀念是不對的(我以前跟本沒發現自己的bug),甚至有些非常基本的觀念我也是到現在才知道,雖然才寫完這份作業,但我感覺到很充實！