contributed by < shauming1020
>
homework
解釋上述程式運作原理,搭配 Graphviz,比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
新增節點,當 linked list 沒有內容時,必須由開發者更新指向開頭的指標。因此實際得到 reference,而非 copy
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;
示意流程
#10 condition: while (*indirect)
#11 indirect = &(*indirect)->next
#12 *indirect = new_node
搜尋節點,成功則回傳找到的目標節點,否則回傳 NULL
#4 condition: current && current->value != value
移除指定節點,指向開頭的指標可能因此變更,所以需要用到 a pointer to a pointer (指標的指標)
#5 condition: while ((*indirect) != entry)
#6 indirect = &(*indirect)->next
#8 *indirect = entry->next
#9 free(entry)
交換一對相鄰的節點,取自 LeetCode: Swap Nodes in Pairs,給定 1->2->3->4,則該回傳 2->1->4->3
#3 condition: if *node && (*node)->next
#4 node_t *tmp = *node
#5 *node = (*node)->next
#6 tmp->next = (*node)->next
#7 (*node)->next = tmp
node = &(*node)->next->next
將給定的 linked list 其內節點予以反向,即 1->2->3->4,則該回傳 4->3->2->1
#5 node_t *next = head->next;
#6 head->next = cursor
#6 cursor = head
#7 head = next
函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry,需要額外做 head = … 的更新,請用指標的指標來改寫,並避免回傳指標;
#5 node_t *next = (*node)->next
#6 (*node)->next = cursor; cursor = *node;
#7 *node = next
#5 node_t *next = (*node)->next
#6 (*node)->next = cursor
#6 cursor = *node
#7 *node = next
#9 *node = cursor
以遞迴改寫上述的 reverse,注意,你可能因此需要建立新的函式,如 rev_resersive,隨後在 reverse 函式中呼叫 rev_resersive;
針對 singly-linked list 的節點,實作 Fisher–Yates shuffle,你應該儘量降低記憶體的使用量;
The modern algorithm
假設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 |
… |
生成 n 個值為 {1, …, n} 升冪排列的 list node
交換兩 node_t 的值
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)
#5 condition: for (int i = n-1; i > 0; i--)
#11 int j = rand() % (i+1)
#14 for (;j && (*pick); j--, pick = &(*pick)->next);
#17 swap_value(start, pick)
#20 start = &(*start)->next
#20 pick = start