# 2020q3 Homework1 (quiz1)
contributed by <`solnone`>
[2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
## 1. 解釋上述程式運作原理，搭配 [Graphviz](https://graphviz.org/)，比照 [Linked List 練習題](https://hackmd.io/@sysprog/linked-list-quiz) 在 HackMD 筆記上視覺化展現
```cpp=
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct __node {
int value;
struct __node *next;
} node_t;
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
/* AA1: a */
assert(new_node);
new_node->value = new_value;
new_node->next = NULL;
while (*indirect)
indirect = &(*indirect)->next;
/* AA2: b */
*indirect = new_node;
}
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next;
/* BB1: e */ node = &(*node)->next->next) {
node_t *tmp = *node;
/* BB2: c */
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
/* CCC: b */
head->next = cursor;
cursor = head;
head = next;
}
return cursor;
}
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
int main(int argc, char const *argv[])
{
node_t *head = NULL;
print_list(head);
add_entry(&head, 72);
add_entry(&head, 101);
add_entry(&head, 108);
add_entry(&head, 109);
add_entry(&head, 110);
add_entry(&head, 111);
print_list(head);
node_t *entry = find_entry(head, 101);
remove_entry(&head, entry);
entry = find_entry(head, 111);
remove_entry(&head, entry);
print_list(head);
/* swap pair.
* See https://leetcode.com/problems/swap-nodes-in-pairs/
*/
head = swap_pair(head);
print_list(head);
head = reverse(head);
print_list(head);
return 0;
}
```
### node_t
```graphviz
digraph node_t {
rankdir=LR;
node [shape=Mrecord, color=black];
node_t [label="{ <data> value | <ref> *next }"];
}
```
### add_entry
加入第二筆資料時追蹤 add_entry
```cpp
add_entry(&head, 72);
add_entry(&head, 101);
```
傳入 main function 的 head 位址 &(main.head)
```cpp
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
/* AA1: a */
assert(new_node);
new_node->value = new_value;
new_node->next = NULL;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; head; indirect;
node [shape=record, color=forestgreen]; address_of_head [label="main.head", fontcolor=blue]; new_node;
node [shape=Mrecord, color=black]; first [label="{ <data> 72 | <ref> }"]; new [label="{ <data> 101 | <ref> }"];
node [shape=none]; null [label="NULL"];
address_of_head -> first [arrowhead=vee, arrowtail=dot, dir=both];
head -> address_of_head [arrowhead=vee, arrowtail=crow, dir=both];
indirect -> address_of_head [arrowhead=vee, arrowtail=crow, dir=both];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
new_node -> new [arrowhead=vee, arrowtail=dot, dir=both];
new:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```cpp
while (*indirect)
indirect = &(*indirect)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; head; indirect;
node [shape=record, color=forestgreen]; address_of_head [label="main.head", fontcolor=blue]; new_node;
node [shape=Mrecord, color=black]; first [label="{ <data> 72 | <ref> }"]; new [label="{ <data> 101 | <ref> }"];
node [shape=none]; null [label="NULL"];
address_of_head -> first [arrowhead=vee, arrowtail=dot, dir=both];
head -> address_of_head [arrowhead=vee, arrowtail=crow, dir=both];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
new_node -> new [arrowhead=vee, arrowtail=dot, dir=both];
new:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
indirect -> first:ref [arrowhead=vee, arrowtail=crow, dir=both, color=red];
}
```
```cpp
*indirect = new_node;
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; head; indirect;
node [shape=record, color=forestgreen]; address_of_head [label="main.head", fontcolor=blue]; new_node;
node [shape=Mrecord, color=black]; first [label="{ <data> 72 | <ref> }"]; new [label="{ <data> 101 | <ref> }"];
node [shape=none]; null [label="NULL"];
address_of_head -> first [arrowhead=vee, arrowtail=dot, dir=both];
head -> address_of_head [arrowhead=vee, arrowtail=crow, dir=both];
indirect -> first:ref [arrowhead=vee, arrowtail=crow, dir=both];
new_node -> new [arrowhead=vee, arrowtail=dot, dir=both];
new:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
first:ref:c -> new [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
### swap_pair
```cpp
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; ...; ...) {
node_t *tmp = *node;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record, color=forestgreen]; head; tmp;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> first [arrowhead=vee, arrowtail=dot, dir=both];
n -> head [arrowhead=vee, arrowtail=crow, dir=both];
first:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
tmp -> first [arrowhead=vee, arrowtail=dot, dir=both];
}
```
```cpp
*node = (*node)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record, color=forestgreen]; head; tmp;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
n -> head [arrowhead=vee, arrowtail=crow, dir=both];
first:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
tmp -> first [arrowhead=vee, arrowtail=dot, dir=both];
head -> second [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
tmp->next = (*node)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record, color=forestgreen]; head; tmp;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
n -> head [arrowhead=vee, arrowtail=crow, dir=both];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
tmp -> first [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
(*node)->next = tmp;
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record, color=forestgreen]; head; tmp;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
n -> head [arrowhead=vee, arrowtail=crow, dir=both];
first:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
tmp -> first [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
for (...; *node && (*node)->next; node = &(*node)->next->next) {
node_t *tmp = *node;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record, color=forestgreen]; head; tmp;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n -> first:ref [arrowhead=vee, arrowtail=crow, dir=both, color=red];
tmp -> third [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
*node = (*node)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record, color=forestgreen]; head; tmp;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n -> first:ref [arrowhead=vee, arrowtail=crow, dir=both];
tmp -> third [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
tmp->next = (*node)->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record, color=forestgreen]; head; tmp;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n -> first:ref [arrowhead=vee, arrowtail=crow, dir=both];
tmp -> third [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
(*node)->next = tmp;
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record, color=forestgreen]; head; tmp;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n -> first:ref [arrowhead=vee, arrowtail=crow, dir=both];
tmp -> third [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
for (...; *node && (*node)->next; node = &(*node)->next->next) {
...
}
return head;
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=indigo]; n [label="node"];
node [shape=record]; head;
node [shape=Mrecord, color=black];
first [label="{ <data> 72 | <ref> }"];
second [label="{ <data> 108 | <ref> }"];
third [label="{ <data> 109 | <ref> }"];
fourth [label="{ <data> 110 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
first:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n -> third:ref [arrowhead=vee, arrowtail=crow, dir=both, color=red];
}
```
### reverse
```cpp
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> first [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> null [arrowhead=vee, arrowtail=dot, dir=both];
}
```
Round 1
```cpp
while (head) {
node_t *next = head->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> first [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> null [arrowhead=vee, arrowtail=dot, dir=both];
next -> second [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
head->next = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> first [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> null [arrowhead=vee, arrowtail=dot, dir=both];
next -> second [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
cursor = head;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
head -> first [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
next -> second [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> first [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
head = next;
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
next -> second [arrowhead=vee, arrowtail=dot, dir=both];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> first [arrowhead=vee, arrowtail=dot, dir=both];
head -> second [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
Round 2
```cpp
while (head) {
node_t *next = head->next;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> first [arrowhead=vee, arrowtail=dot, dir=both];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
next -> third [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
head->next = cursor;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> first [arrowhead=vee, arrowtail=dot, dir=both];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
next -> third [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
cursor = head;
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head -> second [arrowhead=vee, arrowtail=dot, dir=both];
next -> third [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> second [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
head = next;
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
next -> third [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> second [arrowhead=vee, arrowtail=dot, dir=both];
head -> third [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
Round 3 ...
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
third:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
next -> fourth [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> third [arrowhead=vee, arrowtail=dot, dir=both];
head -> fourth [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
Round 4 ...
```graphviz
digraph linkedlist {
rankdir=LR;
node [shape=record, color=forestgreen]; head; cursor; next;
node [shape=Mrecord, color=black];
first [label="{ <data> 108 | <ref> }"];
second [label="{ <data> 72 | <ref> }"];
third [label="{ <data> 110 | <ref> }"];
fourth [label="{ <data> 109 | <ref> }"];
node [shape=none]; null [label="NULL"];
third:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
fourth:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
next -> null [arrowhead=vee, arrowtail=dot, dir=both];
second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> fourth [arrowhead=vee, arrowtail=dot, dir=both];
head -> null [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
return cursor;
}
```
## 2. 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標
### swap_pair
```cpp
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
```cpp
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;
}
```
## 3. 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive
```cpp
node_t *rev_recursive(node_t *node, node_t *cursor)
{
node_t *next = node->next;
node->next = cursor;
return (next) ? rev_recursive(next, node) : node;
}
void reverse(node_t **head)
{
if (*head)
*head = rev_recursive(*head, NULL);
}
```
## 4. 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，你應該儘量降低記憶體的使用量
```cpp
#include <time.h>
size_t list_size(node_t *head)
{
size_t i = 0;
for (; head; i++)
head = head->next;
return i;
}
void push_node(node_t **indirect, node_t *node)
{
node->next = *indirect;
*indirect = node;
}
node_t *pop_node_by_pseudo_index(node_t *pseudo, size_t index)
{
for (; index; index--)
pseudo = pseudo->next;
node_t *cursor = pseudo;
pseudo = pseudo->next;
cursor->next = pseudo->next;
pseudo->next = NULL;
return pseudo;
}
void shuffle(node_t **head)
{
size_t size = list_size(*head);
if (size < 2)
return;
node_t pseudo = {.next = *head};
*head = NULL;
for (size_t i = size; 0 < i; i--) {
size_t roll = rand() % i;
push_node(head, pop_node_by_pseudo_index(&pseudo, roll));
}
}
int main(int argc, char const *argv[])
{
srand((unsigned) time(NULL));
...
shuffle(&head);
print_list(head);
return 0;
}
```
## Reference
* [2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
* [Graphviz](https://graphviz.org/)
* [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs)
* [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
Sign in with Wallet
Connect another wallet