Try   HackMD

2020q3 Homework1 (quiz1)

contributed by < shauming1020 >

tags: homework

Q1. 解釋程式運作原理

解釋上述程式運作原理,搭配 Graphviz,比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;







structs



node1

value

next

node name



ptr1

pointer_name

&node



ptr1:value->node1:value





pptr1

pointer to pointer_name

Address



pptr1:value->node1:value





pptr1:value->node1:next





pptr1:value->ptr1:name






add_entry

新增節點,當 linked list 沒有內容時,必須由開發者更新指向開頭的指標。因此實際得到 reference,而非 copy

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; assert(new_node); // AA1 while (*indirect) indirect = &(*indirect)->next; *indirect = new_node; // AA2 }
  • AA1 檢查是否成功 malloc 空間給 new_node 指向

ISO/IEC 9899:TC3 規格書 p.169 提到 assert

if expression (which shall have a scalar type) is false (that is, compares equal to 0),
the assert macro writes information about the particular call that failed on the standard error stream in an implementation-defined format.165).
It then calls the abort function.

  • AA2 當 *indirect 取值為 NULL 時,表 indirect 正指向尾端節點的 next,因此要讓尾端節點指向 新節點的位址,故選 *indirect = new_node;

  • 示意流程







structs



node1

1

&node2

node1



node2

2

NULL

node2



node1:next->node2:value





node3

new_value

NULL

node3



ptr1

head

&node1



ptr1:value->node1:value





ptr2

new_node

&node3



ptr2:value->node3:value





pptr1

indirect

&head



pptr1:value->ptr1:name





#10 condition: while (*indirect)

  • 從 indirect 所存位址取值不為 NULL 時,表尚未走訪到尾端節點

#11 indirect = &(*indirect)->next







structs



node1

1

&node2

node1



node2

2

NULL

node2



node1:next->node2:value





node3

new_value

NULL

node3



ptr1

head

&node1



ptr1:value->node1:value





ptr2

new_node

&node3



ptr2:value->node3:value





pptr1

indirect

&(node1.next)



pptr1:value->node1:next





  • 取的值為 NULL 時,表走訪到尾端節點的 next






structs



node1

1

&node2

node1



node2

2

NULL

node2



node1:next->node2:value





node3

new_value

NULL

node3



ptr1

head

&node1



ptr1:value->node1:value





ptr2

new_node

&node3



ptr2:value->node3:value





pptr1

indirect

&(node2.next)



pptr1:value->node2:next





#12 *indirect = new_node

  • 讓他的 next 指向 new_node (即 &node3)






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

new_value

NULL

node3



node2:next->node3:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

new_node

&node3



ptr2:value->node3:value





pptr1

indirect

&(node2.next)



pptr1:value->node2:next






find_entry

搜尋節點,成功則回傳找到的目標節點,否則回傳 NULL

node_t *find_entry(node_t *head, int value) { node_t *current = head; for (; current && current->value != value; current = current->next) /* interate */; return current; }

#4 condition: current && current->value != value

  • 若 current 未指向 NULL 且 current 的 value 不為目標值,則往 next 繼續走訪
  • 當找到目標值,表 current 指向目標節點位址,回傳 current,否則回傳 NULL

remove_entry

移除指定節點,指向開頭的指標可能因此變更,所以需要用到 a pointer to a pointer (指標的指標)

void remove_entry(node_t **head, node_t *entry) { node_t **indirect = head; while ((*indirect) != entry) indirect = &(*indirect)->next; *indirect = entry->next; free(entry); }
  • 示意流程






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

NULL

node3



node2:next->node3:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

entry

&node3



ptr2:value->node3:value





pptr1

indirect

&head



pptr1:value->ptr1





#5 condition: while ((*indirect) != entry)

  • 當 *indirect 與 entry 指向不同的節點位址時

#6 indirect = &(*indirect)->next

  • 則往下繼續遍歷,直到 *indirect 恰指向目標節點的位址






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

NULL

node3



node2:next->node3:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

entry

&node3



ptr2:value->node3:value





pptr1

indirect

&(node2.next)



pptr1:value->node2:next





#8 *indirect = entry->next

  • 讓 *indirect 指向 entry 的 next






structs



node1

1

&node2

node1



node2

2

NULL

node2



node1:next->node2:value





node3

3

NULL

node3



ptr1

head

&node1



ptr1:value->node1:value





ptr2

entry

&node3



ptr2:value->node3:value





pptr1

indirect

&(node2.next)



pptr1:value->node2:next





#9 free(entry)

  • 釋放 entry 所指向 heap 的空間

swap_pair

交換一對相鄰的節點,取自 LeetCode: Swap Nodes in Pairs,給定 1->2->3->4,則該回傳 2->1->4->3

node_t *swap_pair(node_t *head) { for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) { // BB1 node_t *tmp = *node; *node = (*node)->next; // BB2 tmp->next = (*node)->next; (*node)->next = tmp; } return head; }
  • BB1 解讀成 node = &(((*node)->next)->next),完成一對的交換後,將 *node 往下走訪兩節點
  • BB2 *node 為新一對當中的開頭者,因此要先讓 *node 往下一個節點去抓新的開頭
  • 示意流程






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





pptr1

node

&head



pptr1:value->ptr1





#3 condition: if *node && (*node)->next

  • 判斷當前與下一個指向是否為空,若非空則可以進行成對的交換

#4 node_t *tmp = *node

  • 讓一個 tmp 指標指向與 *node 相同的位址






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

tmp

&node1



ptr2:value->node1:value





pptr1

node

&head



pptr1:value->ptr1





#5 *node = (*node)->next

  • (*node)->next 為 &node2 指派給 *node,即讓 *node,也就是 head 往下走訪一個節點
  • 往下個節點抓新對的開頭






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

tmp

&node1



ptr2:value->node1:value





pptr1

node

&head



pptr1:value->ptr1:name





#6 tmp->next = (*node)->next

  • 這時 (*node)->next 為 &node3,指派到 tmp->next,也就讓 (*node) 的下一個節點成為 tmp 的下一個節點






structs



node1

1

&node3

node1



node3

3

&node4

node3



node1:next->node3:value





node2

2

&node3

node2



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

tmp

&node1



ptr2:value->node1:value





pptr1

node

&head



pptr1:value->ptr1:name





#7 (*node)->next = tmp

  • 將 tmp 的值指派到 (*node)->next,也就是 (*node)->next 的值改為 tmp 所存的節點位址






structs



node1

1

&node3

node1



node3

3

&node4

node3



node1:next->node3:value





node2

2

&node1

node2



node2:next->node1:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

tmp

&node1



ptr2:value->node1:value





pptr1

node

&head



pptr1:value->ptr1:name





node = &(*node)->next->next

  • &(*node)->next->next 解讀成 &(((*node)->next)->next)
  • 因此先得到 (*node)->next) 的值 &node1
  • 再將 node1->next 的位址指派給 node






structs



node1

1

&node3

node1



node3

3

&node4

node3



node1:next->node3:value





node2

2

&node1

node2



node2:next->node1:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

tmp

&node1



ptr2:value->node1:value





pptr1

node

&(node1.next)



pptr1:value->node1:next





  • 執行直到跳出迴圈 ,最後回傳 head






structs



node1

1

&node4

node1



node4

4

&node3

node4



node1:next->node4:value





node2

2

&node1

node2



node2:next->node1:value





node3

3

NULL

node3



node4:next->node3:value





ptr1

head

&node2



ptr1:value->node2:value





pptr1

node

&(node3.next)



pptr1:value->node3:next






reverse

將給定的 linked list 其內節點予以反向,即 1->2->3->4,則該回傳 4->3->2->1

node_t *reverse(node_t *head) { node_t *cursor = NULL; while (head) { node_t *next = head->next; head->next = cursor; cursor = head; // CCC head = next; } return cursor; }
  • 從最後 return cursor 得知,cursor 是新 list 的 head,因此 head->next = cursor 是讓舊的 head 去指向新的 head (i.e. cursor),再透過 cursor = head 讓 cursor 移動到新接上來的節點上,達到反向的效果
  • 示意流程






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

cursor

NULL



#5 node_t *next = head->next;

  • head->next 取值 &node2,指派到 next






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

cursor

NULL



ptr3

next

&node2



ptr3:value->node2:value





#6 head->next = cursor

  • 將 cursor 值 NULL,指派到 head->next






structs



node1

1

NULL

node1



node2

2

&node3

node2



node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

cursor

NULL



ptr3

next

&node2



ptr3:value->node2:value





#6 cursor = head

  • 將 head 值 &node1,指派給 cursor






structs



node1

1

NULL

node1



node2

2

&node3

node2



node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

cursor

&node1



ptr2:value->node1:value





ptr3

next

&node2



ptr3:value->node2:value





#7 head = next

  • 將 next 值 &node2,指派給 head






structs



node1

1

NULL

node1



node2

2

&node3

node2



node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

cursor

&node1



ptr2:value->node1:value





ptr3

next

&node2



ptr3:value->node2:value





  • 直到 head 值為 NULL,跳出迴圈並回傳 cursor,即成為新的 head






structs



node1

1

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

4

&node3

node4



node4:next->node3:value





ptr1

head

NULL



ptr2

cursor

&node4



ptr2:value->node4:value






Q2. 請用指標的指標來改寫,並避免回傳指標

函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry,需要額外做 head = 的更新,請用指標的指標來改寫,並避免回傳指標;

1. 改寫 swap_pair

void swap_pair_v2(node_t **node) { for (; *node && (*node)->next; node = &(*node)->next->next) { node_t *tmp = *node; *node = (*node)->next; tmp->next = (*node)->next; (*node)->next = tmp; } } ... swap_pair_v2(&head);
  • 原來的程式碼輸入 node_t *head 後再調用 node_t **node = &head 去進行操作,最後回傳 head 指標
  • 因為 call-by-value,執行函式呼叫後會宣告一個 node_t *head 與輸入的指標指向相同的節點,函式內是對該 head 進行操作,因此實際上並沒有更動到原先輸入的指標,故最後還要回傳完成操作後的 head
  • 參考 你所不知道的C語言:指標篇
  • 而一開始若把 &head 當作引數輸入給 node_t **node,則會直接對原 head 操作

2. 改寫 reverse

void reverse_v2(node_t **node) { node_t *cursor = NULL; while (*node) { node_t *next = (*node)->next; (*node)->next = cursor; cursor = *node; *node = next; } *node = cursor; } ... reverse_v2(&head);
  • 原理與上述相同,而最後操作完 head 會指向 NULL,因此要讓 head 重新指向新的 head (i.e. cursor)
  • 示意流程






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

cursor

NULL



pptr1

node

&head



pptr1:value->ptr1:name





#5 node_t *next = (*node)->next







structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

cursor

NULL



ptr3

next

&node2



ptr3:value->node2:value





pptr1

node

&head



pptr1:value->ptr1:name





#6 (*node)->next = cursor; cursor = *node;







structs



node1

1

NULL

node1



node2

2

&node3

node2



node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





ptr2

cursor

&node1



ptr2:value->node1:value





ptr3

next

&node2



ptr3:value->node2:value





pptr1

node

&head



pptr1:value->ptr1:name





#7 *node = next







structs



node1

1

NULL

node1



node2

2

&node3

node2



node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

cursor

&node1



ptr2:value->node1:value





ptr3

next

&node2



ptr3:value->node2:value





pptr1

node

&head



pptr1:value->ptr1:name





  • 下個迴圈
    #5 node_t *next = (*node)->next






structs



node1

1

NULL

node1



node2

2

&node3

node2



node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

cursor

&node1



ptr2:value->node1:value





ptr3

next

&node3



ptr3:value->node3:value





pptr1

node

&head



pptr1:value->ptr1:name





#6 (*node)->next = cursor







structs



node1

1

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node4

node3



node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

cursor

&node1



ptr2:value->node1:value





ptr3

next

&node3



ptr3:value->node3:value





pptr1

node

&head



pptr1:value->ptr1:name





#6 cursor = *node







structs



node1

1

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node4

node3



node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node2



ptr1:value->node2:value





ptr2

cursor

&node2



ptr2:value->node2:value





ptr3

next

&node3



ptr3:value->node3:value





pptr1

node

&head



pptr1:value->ptr1:name





#7 *node = next







structs



node1

1

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node4

node3



node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node3



ptr1:value->node3:value





ptr2

cursor

&node2



ptr2:value->node2:value





ptr3

next

&node3



ptr3:value->node3:value





pptr1

node

&head



pptr1:value->ptr1:name





  • 依序做下去直到跳出迴圈






structs



node1

1

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

4

&node3

node4



node4:next->node3:value





ptr1

head

NULL



ptr2

cursor

&node4



ptr2:value->node4:value





pptr1

node

&head



pptr1:value->ptr1:name





#9 *node = cursor

  • 最後要將 cursor 值指派給 *node






structs



node1

1

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

4

&node3

node4



node4:next->node3:value





ptr1

head

&node4



ptr1:value->node4:value





ptr2

cursor

&node4



ptr2:value->node4:value





pptr1

node

&head



pptr1:value->ptr1:name






Q3. 以遞迴改寫上述的 reverse

以遞迴改寫上述的 reverse,注意,你可能因此需要建立新的函式,如 rev_resersive,隨後在 reverse 函式中呼叫 rev_resersive;

node_t *rev_resersive(node_t **node, node_t **cursor) { if (*node) { node_t *next = (*node)->next; (*node)->next = *cursor; *cursor = *node; *node = next; *cursor = rev_resersive(node, cursor); } return *cursor; } void reverse_v3(node_t **node) { node_t *cursor = NULL; *node = rev_resersive(node, &cursor); } ... reverse_v3(&head);
  • 將 while 迴圈內會重複執行的程式部份改用遞迴方式呼叫執行,最後在回傳 cursor 即可

Q4. Fisher–Yates shuffle

針對 singly-linked list 的節點,實作 Fisher–Yates shuffle,你應該儘量降低記憶體的使用量;

The modern algorithm

-- To shuffle an array a of n elements (indices 0..n-1):
** for i from n−1 downto 1 do **
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

假設rand()時間複雜度為O(1)
採用array實作時間複雜度為O(n),但需要一額外與數組大小相同的空間,用來存放隨機取出的值,因此空間複雜度為O(2n)


Range Roll Scratch Result
1 2 3 4 5 6 7 8
1–8 6 1 2 3 4 5 8 7 6
1–7 2 1 7 3 4 5 8 2 6
1-6 6 1 7 3 4 5 8 2 6

實作

create_list

生成 n 個值為 {1, , n} 升冪排列的 list node

void create_list(node_t **node, int n) { for (int i = 1; !(*node) && i <= n; node = &(*node)->next, i++) { node_t *new_node = malloc(sizeof(node_t)); new_node->value = i; new_node->next = NULL; *node = new_node; } }
  • n = 4






structs



node1

1

&node2

node1



node2

2

&node3

node2



node1:next->node2:value





node3

3

&node4

node3



node2:next->node3:value





node4

4

NULL

node4



node3:next->node4:value





ptr1

head

&node1



ptr1:value->node1:value





pptr1

node

&head



pptr1:value->ptr1:name





swap_value

交換兩 node_t 的值

void swap_value(node_t **a, node_t **b) { int tmp = (*a)->value; (*a)->value = (*b)->value; (*b)->value = tmp; }

FYshuffle

void FYshuffle (node_t **head, int n) { srand(time(NULL)); reverse(head); node_t **start = head; node_t **pick = head; for (int i = n-1; i > 0; i--) { // select a random index from 0 to i int j = rand() % (i+1); // shift pick to this index for (;j && (*pick); j--, pick = &(*pick)->next); // swap the pick value with start value. swap_value(start, pick); // update the start and pick start = &(*start)->next; pick = start; } }
Range Roll Scratch
1 2 3 4 5 6 7 8
reverse - 8 7 6 5 4 3 2 1
1–8 3 [6] 7 8 5 4 3 2 1
1–7 6 [6 2] 8 5 4 3 7 1
1-6 6 [6 2 1] 5 4 3 7 8
1-5 0 [6 2 1 5] 4 3 7 8

#4 reverse(head)

  • 演算法會從數組尾端往前取值,但作業要求是單向的list,因此需先對 list 反向






structs



node1

1

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

4

&node3

node4



node4:next->node3:value





ptr1

head

&node4



ptr1:value->node4:value





pptr1

head

&head



pptr1:value->ptr1:name





pptr2

start

&head



pptr2:value->ptr1:name





pptr3

pick

&head



pptr3:value->ptr1:name





#5 condition: for (int i = n-1; i > 0; i--)

#11 int j = rand() % (i+1)

  • 從 [0, i] 隨機取出一個值,i + 1 為當前可取的 list 長度,且會逐漸縮短

#14 for (;j && (*pick); j--, pick = &(*pick)->next);

  • 移動 pick 使其指向目標 node
  • 假設 j = 3,則將 pick 往 next 移動 3 次
  • 若 j = 0,則不需要移動 pick






structs



node1

1

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

4

&node3

node4



node4:next->node3:value





ptr1

head

&node4



ptr1:value->node4:value





pptr1

head

&head



pptr1:value->ptr1:name





pptr2

start

&head



pptr2:value->ptr1:name





pptr3

pick

&(node2.next)



pptr3:value->node2:next





#17 swap_value(start, pick)







structs



node1

4

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

1

&node3

node4



node4:next->node3:value





ptr1

head

&node4



ptr1:value->node4:value





pptr1

head

&head



pptr1:value->ptr1:name





pptr2

start

&head



pptr2:value->ptr1:name





pptr3

pick

&(node2.next)



pptr3:value->node2:next





#20 start = &(*start)->next







structs



node1

4

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

1

&node3

node4



node4:next->node3:value





ptr1

head

&node4



ptr1:value->node4:value





pptr1

head

&head



pptr1:value->ptr1:name





pptr2

start

&(node4.next)



pptr2:value->node4:next





pptr3

pick

&(node2.next)



pptr3:value->node2:next





#20 pick = start







structs



node1

4

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

1

&node3

node4



node4:next->node3:value





ptr1

head

&node4



ptr1:value->node4:value





pptr1

head

&head



pptr1:value->ptr1:name





pptr2

start

&(node4.next)



pptr2:value->node4:next





pptr3

pick

&(node4.next)



pptr3:value->node4:next





  • 假設每回都取到自己,即 j = 0
  • 執行完 n - 1 個 iteration,此例 n = 4,故 start 會移動 3 次






structs



node1

4

NULL

node1



node2

2

&node1

node2



node2:next->node1:value





node3

3

&node2

node3



node3:next->node2:value





node4

1

&node3

node4



node4:next->node3:value





ptr1

head

&node4



ptr1:value->node4:value





pptr1

head

&head



pptr1:value->ptr1:name





pptr2

start

&(node2.next)



pptr2:value->node2:next





pptr3

pick

&(node2.next)



pptr3:value->node2:next





分析

  • 假設 rand() 為
    O(1)
    和 reverse() 為
    O(n)
  • 時間複雜度
    • Worst Case : 每次取到最遠的值做交換,每回移動 pick
      O(n)
      ,共 n 回,
      O(n2)
    • Best Case : 每次取到最近的值交換,每回移動 pick
      O(1)
      ,共 n 回,
      O(n)
    • Average Case :
      O
      ((
      n2
      +
      n
      ) / 2) =
      O(n2)
  • 空間複雜度
    • 只使用 n 個 node 和 3 個 pointer to pointer 變數,故
      O(n)

完整測試程式碼如下

#include <stdio.h> #include <stdlib.h> #include <time.h> typedef struct __node { int value; struct __node *next; } node_t; void create_list(node_t **node, int n) { for (int i = 1; !(*node) && i <= n; node = &(*node)->next, i++) { node_t *new_node = malloc(sizeof(node_t)); new_node->value = i; new_node->next = NULL; *node = new_node; } } 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; } void swap_value(node_t **a, node_t **b) { int tmp = (*a)->value; (*a)->value = (*b)->value; (*b)->value = tmp; } void FYshuffle (node_t **head, int n) { srand(time(NULL)); reverse(head); printf("reverse as initial ... "); print_list(*head); node_t **start = head; node_t **pick = head; for (int i = n-1; i > 0; i--) { // select a random index from 0 to i int j = rand() % (i+1); // shift pick to this index for (;j && (*pick); j--, pick = &(*pick)->next); printf("[iter %d] start at %d ,and swap with %d ... ", n-i, (*start)->value, (*pick)->value); // swap the pick value with start value. swap_value(start, pick); print_list(*head); // update the start and pick start = &(*start)->next; pick = start; } printf("[final] start at %d \n", (*start)->value); } void print_list(node_t *head) { for (node_t *current = head; current; current = current->next) printf("%d ", current->value); printf("\n"); } int main() { int len = 8; node_t *head = NULL; create_list(&head, len); printf("before shuffle "); print_list(head); FYshuffle(&head, len); printf("after shuffle "); print_list(head); }
before shuffle 1 2 3 4 5 6 7 8 
reverse as initial ... 8 7 6 5 4 3 2 1 
[iter 1] start at 8 ,and swap with 8 ... 8 7 6 5 4 3 2 1 
[iter 2] start at 7 ,and swap with 4 ... 8 4 6 5 7 3 2 1 
[iter 3] start at 6 ,and swap with 3 ... 8 4 3 5 7 6 2 1 
[iter 4] start at 5 ,and swap with 6 ... 8 4 3 6 7 5 2 1 
[iter 5] start at 7 ,and swap with 5 ... 8 4 3 6 5 7 2 1 
[iter 6] start at 7 ,and swap with 7 ... 8 4 3 6 5 7 2 1 
[iter 7] start at 2 ,and swap with 1 ... 8 4 3 6 5 7 1 2 
[final] start at 2 
after shuffle 8 4 3 6 5 7 1 2