sysprog2020
homework
contributed by <JKChun
>
add_entry
新增節點,當 linked list 沒有內容時,必須由開發者更新指向開頭的指標。因此實際得到 reference,而非 copy
head
和一個整數型別的變數new_value
indirect
,並指派 head
給indirect
malloc
分配記憶體空間給 new_node,並指派 new value
以及指向 NULL
assert(new_node)
確定 new_node 有成功建立indriect
指向 linked_list
最後一個節點的 next
*indirect = new_node
最後將 new_node 指派給 next
,讓 new_node 變成 linked_list
的最後一個 noderemove_entry
移除指定節點,指向開頭的指標可能因此變更,所以需要用到 a pointer to a pointer (指標的指標)
indirect
,並指派 head
給 indirect
indirect
指向 entry node
前一個 node 的 next
indirect
更改 entry node
前一個 node 的 next
,讓它直接指向 entry node
的下一個 nodefree
釋放 entry 占用的記憶體swap_pair
交換一對相鄰的節點,給定 1->2->3->4,則該回傳 2->1->4->3
linked list
裡的 node 按照順序兩兩一組,把順序反過來,所以 for 迴圈
的判斷條件很簡單,就是沒有成對的 node 就跳出迴圈for 迴圈
裡先額外建一個 temp
指標node_t *tmp = *node;
*node = (*node)->next; (#BB2)
tmp->next = (*node)->next;
(*node)->next = tmp;
node = &(*node)->next->next (#BB1)
**node
指向第一個 node 的 next ,這樣做的話,假如有第四個 node ,就可以像上面操作 *head
一樣,讓 head node 的 next 可以指向第四個 nodefor 迴圈
並回傳 head
reverse
將給定的 linked list 其內節點予以反向,即 1->2->3->4,則該回傳 4->3->2->1
node_t *cursor = NULL;
node_t *next = head->next;
head->next = cursor; cursor = head; (#CCC)
head = next;
cursor
指向 *head 指向的 node
在反轉後要指向的地方,拿上面舉例,head->node_2->node_3
,在反轉後 head node
應該要指向 NULL ,所以一開始 cursor
為指向 NULL 的 pointer ,接著讓 head->next = cursor
,再讓 cursor
指向 head node
,因為 head node
是下一個 node node_2
要指向的 node*head
指向 自己原本指向的 node
再下一個順位的 node 也就是 node_2
*head
指向 NULL ,然後回傳 cursor
結束swap_pair
和 reverse
函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry,需要額外做 head = … 的更新,請用指標的指標來改寫,並避免回傳指標;
swap_pair
recursive function 裡的:
是用來找到指向 linked list
最後一個 node 的指標並不停的回傳,到最後的 reverse function
更新 head 指標
假設有3個 node ,程式會呼叫3次 recursive function
讓 C 指向 B,B 指向 NULL
,回傳 C node 的指標讓 B 指向 A,A 指向 NULL
,回傳 C node 的指標最後的 reverse function
更新 head 指標
針對 singly-linked list 的節點,實作 Fisher–Yates shuffle,你應該儘量降低記憶體的使用量;