2020q3 Homework1 (quiz1)

contributed by < jeremy3951 >

加入日期:2020/9/15

延伸問題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

`find_entry`:

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

`remove_entry`:

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

`swap_pair`:

此function的功能是把linked list中的兩個點為一數作交換.

我當時的疑問：BB1為何要走兩格?
tmp是負責紀錄第一個點,node是負責紀錄第二個點,node交換完後會變第一個點,所以要走兩格到第三個點去做接下來的交換.

After *node = (*node)->next

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

After (*node)->next = tmp;

`reverse` :

此function的功能是把lined list倒序

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

After head->next = cursor;cursor = head

After head = next
`

next再往下走

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

`print_list`:

用current指標走訪整個linked list並且output value.

延伸問題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語言：指標篇

看了這篇文章之後一開始還不太了解意思,不過透過實作+紙筆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.

延伸問題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.重複做一樣的事這兩個特性下去想的.

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

實作 Fisher–Yates shuffle

延伸問題4：
針對singlly-linked list的節點,實作 Fisher–Yates shuffle ,你應該盡量降低記憶體的使用量;

此演算法一開始是用另一個陣列來裝亂數值,又或者把亂數值裝在陣列後面,如下圖

不過用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:

node1指向node3：

把node2指向head：

再隨機選下一個數…

心得：

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

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

2020q3 Homework1 (quiz1)

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

add_entry:

find_entry:

remove_entry:

swap_pair:

reverse :

print_list:

swap_pair 改寫:

reverse 改寫: