2020q3 Homework1 (quiz1)

contributed by < ccs100203 >

tags: linux2020

程式運作原理

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

1. 一開始會有一個 node 為 pointer to pointer，然後 for 會判斷說這一個跟下一個是不是 NULL，不是的話就可以做 swap，每一次做完就讓 node 往後指兩個。
2. 先用一個 tmp 指向 *node 指的地方

3. 將 *node 指向 *node->next

4. 將 tmp->next 接上 (*node)->next

5. 最後再把 (*node)->next 往前接回 tmp

6. 讓 node 往後指到下兩個，node = &(*node)->next->next

更改為 pointer to pointer

swap_pair

將 head 直接取代掉原本的 node，因為 node 做的事情就是一直去找後兩個 pointer，所以當我傳 pointer to pointer 的 head 時，就可以用他來達成這項功能

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

reverse

將最後的 head 重新指向 cursor 指的地方就好了，因為照著原本的邏輯跑，cursor 在最後會指向一開始的尾巴，也就是 reverse 過後新的起點，而 head 則會跑去指向 NULL，這時候只要把 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;
}

更改 reverse 為 recursive version

目前是做出最直觀的寫法，就是直接把原本 iterate 的版本套下去改成遞迴，還在思索有沒有更好的寫法，因為一直 call function 成本不低

void rev_recursive(node_t **head, node_t *cursor){
    if(*head){
        node_t *next = (*head)->next;
        (*head)->next = cursor; 
        cursor = *head;
        *head = next;
        rev_recursive(head, cursor);
    }else{
        *head = cursor;
    }
}

void reverse(node_t **head)
{
    rev_recursive(head, NULL);    
}

Fisher–Yates shuffle

Modern method

先計算出 size，直觀的從大到小跑迴圈，在每一次的範圍內做 random，並且將得到的數字按照順序跟 size~1 的值做交換
因為交換的順序是從最後面到前面，不斷的交換數值，比起 array 用 singly-linked list 不是很有效率，但目前還沒想到解法

void shuffle(node_t *head)
{
    srand(time(NULL));
    int size = 0;
    for(node_t *tmp = head; tmp!=NULL; tmp=tmp->next)
        size++;
    for(int i=size; i>1; i--){
        int num = rand() % i;
        node_t *tmpA = head, *tmpB = head;
        for(int j=0; j<num; ++j)
            tmpA = tmpA->next;
        for(int j=0; j<i-1; ++j)
            tmpB = tmpB->next;
        
        int val = tmpA->value;
        tmpA->value = tmpB->value;
        tmpB->value = val;
    }
}