2020q3 Homework1 (quiz1)

contributed by <haoyu0970624763>

延伸問題一:程式運作原理

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]

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

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

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

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

迴圈下一層

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

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 表當前節點的下一個節點

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

概念如下

執行 head->next = cursor;

執行 cursor = head; 與 head = next;

執行迴圈下一層

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

同樣的邏輯繼續下去即可求的反的 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