# 2020q3 Homework1 (quiz1)
contribted by < `joe-U16` >
###### tags: `sysprog2020`
:::warning
由於對Git 的不熟悉，導致有兩個帳號commit 這個作業，但這兩個帳號都是我的。
Github 上commit 的有 \<papd32> \<joe-U16>
:::
Directory:
[toc]
## Node示意圖
* 單個節點
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ node name | value | <ref> }"]
a:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
* linked list，各節點名稱分別為a b c d，value 為 1 2 3 4
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <value> 1 | <ref> }"];
b [label="{ <data> b | <value> 2 | <ref> }"];
c [label="{ <data> c | <value> 3 | <ref> }"];
d [label="{ <data> d | <value> 4 | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
## Q1
考慮一個單向 linked list，其結構定義為:
```cpp=
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:
* ```add_entry```: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
* ```remove_entry```: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
* ```swap_pair```: 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 ```1->2->3->4```，則該回傳 ```2->1->4->3```
* ```reverse```: 將給定的 linked list 其內節點予以反向，即 ```1->2->3->4```，則該回傳 ```4->3->2->1```
### <font color=#4588C1>add_entry</font>
```cpp=
#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));
new_node->value = new_value;
new_node->next = NULL;
assert(new_node); \\AA1
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node; \\AA2
}
```
* ==#13==幫new_node配置大小為```node_t```的記憶體
* ==#14==把new_value assign 給 new_node->value
* ==#15==new_node->next 指向 NULL
* ==#17==用[assert](https://pubs.opengroup.org/onlinepubs/9699919799/)判斷new_node 這個pointer variable的記憶體有沒有配置成功
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ new_node | new_value | <ref> }"]
a:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
* ==#18==因為前面有```node_t **indirect = head;```，所以會從```head```開始，當```*indrect```還有東西，就持續前進
1. 最初狀態
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <value> 1 | <ref> }"];
b [label="{ <data> b | <value> 2 | <ref> }"];
c [label="{ <data> c | <value> 3 | <ref> }"];
d [label="{ <data> d | <value> 4 | <ref> }"];
indirect [label="{ indirect | <value> | <ref> }"];
new_node [label="{ <data> new_node | <value> new_value| <ref>}"]
valindirect [label="{ <data>*indirect | <value> | <ref> }"];
head [label="{ <data> *head | <value> | <ref> }"];
valhead [label="{ *head | <value> | <ref> }"];
head -> valhead:value [arrowhead=ornomal]
new_node:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
valindirect -> a:value [arrowhead=onormal]
indirect -> valindirect:value [arrowhead=onormal]
valhead->a:value [arrowhead=onormal]
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
2. 經過一次while迴圈，執行```indirect = new_node;```後
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <value> 1 | <ref> }"];
b [label="{ <data> b | <value> 2 | <ref> }"];
c [label="{ <data> c | <value> 3 | <ref> }"];
d [label="{ <data> d | <value> 4 | <ref> }"];
indirect [label="{ indirect | <value> | <ref> }"];
new_node [label="{ <data> new_node | <value> new_value| <ref>}"]
valindirect [label="{ <data>*indirect | <value> | <ref> }"];
head [label="{ <data> *head | <value> | <ref> }"];
valhead [label="{ *head | <value> | <ref> }"];
head -> valhead:value [arrowhead=ornomal]
new_node:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
valindirect -> b:value [arrowhead=onormal]
indirect -> valindirect:value [arrowhead=onormal]
valhead->a:value [arrowhead=onormal]
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
3. 重複直到 *indirect is null
---
* ==#20==```*indirect = new_node; \\AA2```
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <value> 1 | <ref> }"];
b [label="{ <data> b | <value> 2 | <ref> }"];
c [label="{ <data> c | <value> 3 | <ref> }"];
d [label="{ <data> d | <value> 4 | <ref> }"];
sizeof [label="{ <data> | <value> | <ref> }"];
indirect [label="{ indirect | <value> | <ref> }"];
new_node [label="{ <data> new_node | <value> new_value| <ref>}"]
valindirect [label="{ <data>*indirect | <value> | <ref> }"];
head [label="{ <data> *head | <value> | <ref> }"];
valhead [label="{ *head | <value> | <ref> }"];
head -> valhead:value [arrowhead=ornomal]
new_node:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
new_node -> sizeof [arrowhead=onormal]
valindirect -> sizeof:value [arrowhead=onormal]
indirect -> valindirect:value [arrowhead=onormal]
valhead->a:value [arrowhead=onormal]
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
---
### <font color="#4588C1">find_entry</font>
```cpp=
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
```
* ==#3==current 這個pointer variable跟head存相同位址。
* ==#4==current有東西且current->value不等於value時，current移動到下一個位址
1. 初始狀態，current和head相同位址
```graphviz
digraph indirect{
rankdir=LR
node [shape=record];
{rank=same}
a [label="{<data> | <value> | <ref>}"];
b [label="{<data> | <value> | <ref>}"];
head [label="{<data> head | <value> | <ref>}"];
head -> a:value [arrowhead=ornomal]
current [label="{<data> current | <value> | <ref>}"];
current -> a:value [arrowhead=onormal]
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
2. current前進一格，判斷這個位子的value有沒有一樣，沒有的話繼續前進。 ==這邊假設在這裡找到value。==
```graphviz
digraph indirect{
rankdir=LR
node [shape=record];
nodea [label="{<A> | <value> | <ref>}"];
nodeb [label="{<C> | <value> value | <ref>}"];
head [label="{<data> head | <value> | <ref>}"];
head -> nodea:value [arrowhead=onormal]
current [label="{<data> current | <value> | <ref>}"];
current -> nodeb:value [arrowhead=onormal]
nodea:ref:c -> nodeb:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
3. 跳脫迴圈，回傳current 這個pointer variable
### <font color="#4588C1">remove_entry</font>
```cpp=
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
1. 初始狀態
* 假設entry在C節點
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
head[shape=plaintext]
indirect[shape=plaintext];
NULL[shape=plaintext];
n[shape=plaintext,label="entry"]
{
rank=same
indirect->head->A
}
{
rank=same
n->C
}
A->B->C->D->NULL
}
```
2. ==#5==一直前進下一個位址，直到找到entry;
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
head[shape=plaintext]
indirect[shape=plaintext];
NULL[shape=plaintext];
n[shape=plaintext,label="entry(*indirect)"]
{
rank=same
head->A
}
{
rank=same
indirect->n->C
}
A->B->C->D->NULL
}
```
3. ==#8==跳脫迴圈，```*indirect = entry->next``` *indirect會存entry的下一個位址，而entry最後釋放
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
head[shape=plaintext]
indirect[shape=plaintext];
NULL[shape=plaintext];
m[shape=plaintext,label="*indirect"]
{
rank=same
head->A
}
{
rank=same
indirect->m->D
}
A->B->C->D->NULL
}
```
<!--
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <value> | <ref> }"];
b [label="{ <data> b | <value> | <ref> }"];
c [label="{ <data> c | <value> | <ref> }"];
entry [label="{ <data> entry | <value> | <ref> }"];
entry->b:value [arrowhead=onormal]
headptr [label="{<headptr> headptr||}"]
currentptr [label="{<currentptr> currentptr||}"]
current [label="{ <data> current | <value> | <ref> }"];
current -> a:value [arrowhead=onormal]
head [label="{ <data> head | <value> | <ref> }"];
head -> a:value [arrowhead=onormal]
currentptr ->current:value [arrowhead=onormal]
headptr ->head:value:n [arrowhead=onormal]
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <value> | <ref> }"];
b [label="{ <data> b | <value> | <ref> }"];
c [label="{ <data> c | <value> | <ref> }"];
entry [label="{ <data> entry | <value> | <ref> }"];
entry->b:value [arrowhead=onormal]
headptr [label="{<headptr> headptr||}"]
currentptr [label="{<currentptr> currentptr||}"]
head [label="{ <data> head | <value> | <ref> }"];
head -> a:value [arrowhead=onormal]
current [label="{ <data> current | <value> | <ref> }"];
current -> b:value [arrowhead=onormal]
currentptr ->current:value [arrowhead=onormal]
headptr ->head:value:n [arrowhead=onormal]
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c ->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
3. 跳脫迴圈，*current存 entry下一個位址。
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <value> | <ref> }"];
b [label="{ <data> b | <value> | <ref> }"];
c [label="{ <data> c | <value> | <ref> }"];
entry [label="{ <data> entry | <value> | <ref> }"];
entry->b:value [arrowhead=onormal]
headptr [label="{<headptr> headptr||}"]
currentptr [label="{<currentptr> currentptr||}"]
head [label="{ <data> head | <value> | <ref> }"];
head -> a:value [arrowhead=onormal]
current [label="{ <data> current | <value> | <ref> }"];
current -> c:value [arrowhead=onormal]
currentptr ->current:value [arrowhead=onormal]
headptr ->head:value:n [arrowhead=onormal]
a:ref:c -> b:data; b:ref:c ->c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
//b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c ->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
-->
4. 釋放entry;
### <font color="#4588C1">swap_pair</font>
```cpp=
node_t *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;
}
return head;
}
```
* 一開始node存head的address，只要目前這個位址和下個位址有值就持續執行
1. ```node_t *tmp = *node;```
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->b:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head [label="{<data> *node | <value> | <ref>}"];
node1 [label="{<data> node | <value> | <ref>}"];
tmp [label="{<data> tmp | <value> | <ref>}"];
head->a:value [arrowhead=onormal]
node1->head:value [arrowhead=onormal]
tmp->a:value [arrowhead=onormal]
}
```
2. ```*node = (*node)->next;```
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->b:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head [label="{<data> *node | <value> | <ref>}"];
node1 [label="{<data> node | <value> | <ref>}"];
tmp [label="{<data> tmp | <value> | <ref>}"];
head->b:value [arrowhead=onormal]
node1->head:value [arrowhead=onormal]
tmp->a:value [arrowhead=onormal]
}
```
3. ```tmp->next = (*node)->next```
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head [label="{<data> *node | <value> | <ref>}"];
node1 [label="{<data> node | <value> | <ref>}"];
tmp [label="{<data> tmp | <value> | <ref>}"];
head->b:value [arrowhead=onormal]
node1->head:value [arrowhead=onormal]
tmp:n->a:value [arrowhead=onormal]
}
```
4. ```(*node)->next = tmp;```
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->a:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head [label="{<data> *node | <value> | <ref>}"];
node1 [label="{<data> node | <value> | <ref>}"];
tmp [label="{<data> tmp | <value> | <ref>}"];
head->b:value [arrowhead=onormal]
node1->head:value [arrowhead=onormal]
tmp:n->a:value [arrowhead=onormal]
}
```
* node 前進兩格
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->a:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head [label="{<data> *node | <value> | <ref>}"];
node1 [label="{<data> node | <value> | <ref>}"];
tmp [label="{<data> tmp | <value> | <ref>}"];
head->c:value [arrowhead=onormal]
node1->head:value [arrowhead=onormal]
tmp:n->a:value [arrowhead=onormal]
}
```
### <font color="#4588C1">*reverse(node_t *head)</font>
```cpp=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor;
cursor=head;
head = next;
}
return cursor;
}
```
* ==#3==當head不為NULL時，重複1 2 3 4
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->b:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n [label="{NULL}"]
head [label="{<data> head | <value> | <ref>}"];
head->a:value [arrowhead=onormal]
cursor [label="{<data> cursor | <value> | <ref>}"];
cursor->n
}
```
1. ```node_t *next = head->next;```
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->b:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n [label="{NULL}"]
cursor [label="{<data> cursor | <value> | <ref>}"];
cursor->n [arrowhead=normal]
head [label="{<data> head | <value> | <ref>}"];
head->a:value [arrowhead=onormal]
next [label="{<data> next | <value> | <ref>}"];
next->b:value [arrowhead=onormal]
}
```
2. ```head->next = cursor;```
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->n:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n [label="{NULL}"]
cursor [label="{<data> cursor | <value> | <ref>}"];
cursor->n [arrowhead=onormal]
head [label="{<data> head | <value> | <ref>}"];
head->a:value [arrowhead=onormal]
next [label="{<data> next | <value> | <ref>}"];
next->b:value [arrowhead=onormal]
}
```
3. ```cursor=head;```
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->n:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n [label="{NULL}"]
cursor [label="{<data> cursor | <value> | <ref>}"];
cursor->a [arrowhead=onormal]
head [label="{<data> head | <value> | <ref>}"];
head->a:value [arrowhead=onormal]
next [label="{<data> next | <value> | <ref>}"];
next->b:value [arrowhead=onormal]
}
```
4. ```head = next```
```graphviz
digraph indirect{
node [shape=record];
rankdir=LR
a [label="{<data> a | <value> | <ref>}"];
b [label="{<data> b | <value> | <ref>}"];
c [label="{<data> c | <value> | <ref>}"];
d [label="{<data> d | <value> | <ref>}"];
a:ref:c->n:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c->c:data:c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c->d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
n [label="{NULL}"]
cursor [label="{<data> cursor | <value> | <ref>}"];
cursor->a [arrowhead=onormal]
head [label="{<data> head | <value> | <ref>}"];
head->b:value [arrowhead=onormal]
next [label="{<data> next | <value> | <ref>}"];
next->b:value [arrowhead=onormal]
}
```
* 利用三個指標重複動作，最後將linked list 反轉。
## Q2 利用指標的指標改寫swap_pair、reverse避免回傳指標
* swap_pair
```cpp=
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
```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;
}
```
## Q3 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive
* 初始狀態為
```graphviz
digraph name{
node [shape=box]
null [shape=plaintext]
{
rank=same
a->b->c->d->null
}
}
```
* 使用遞迴:step1
```graphviz
digraph name{
node [shape=box]
null [shape=plaintext]
{
rank=same
cur [width=4]
cur->a
a->null
}
}
```
* step2
```graphviz
digraph name{
node [shape=box]
null [shape=plaintext]
{
rank=same
cur [width=3.5]
cur->b->a
a->null
}
}
```
* 持續直到結束就完成啦
```cpp=
node_t *rev_reverse(node_t *head, node_t **pos)
{
if(head->next) {
node_t *tmp = rev_reverse(head->next, pos);
tmp->next = head;
head->next = NULL;
return head;
}
*pos = head;
return head;
}
void reverse(node_t **head)
{
if (!*head || !(*head)->next)
return;
node_t **pos;
pos = head;
rev_reverse(*head, pos);
head = pos;
}
```
## Q4 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle)，你應該儘量降低記憶體的使用量;
```cpp=
void find_pos(node_t **tmp, uint16_t pos)
{
for (pos--;pos;pos--) {
*tmp = (*tmp)->next;
}
}
void shuffle(node_t **head)
{
uint16_t count = 0;
for (node_t *current = *head; current; current = current->next) {
count += 1;
}
if (count == 1)
return;
node_t *tail = NULL;
node_t *cursor = *head;
node_t *tmp = *head;
uint16_t pos = rand() % count;
if (pos == 0) {
tail = cursor;
cursor = cursor->next;
count -= 1;
} else {
find_pos(&tmp, pos);
node_t *target = tmp->next;
tmp->next = target->next;
target->next = cursor;
tail = target;
count -= 1;
}
*head = tail;
for (count--; count; count--) {
tmp = cursor;
uint16_t pos = rand() % count;
if (pos == 0) {
tail = cursor;
cursor = cursor->next;
continue;
}
find_pos(&tmp, pos);
node_t *target = tmp->next;
tmp->next = target->next;
target->next = cursor;
tail->next = target;
tail = tail->next;
}
}
```
<!--
```graphviz
digraph circle{
a -> b;
b -> c;
c -> a;
a -> b
}
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 12 | <ref> }", width=1.2]
b [label="{ <data> 99 | <ref> }"]
c [label="{ <data> 37 | <ref> }"]
d [shape=box];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> e [arrowhead=vee]
}
```
```graphviz
digraph indirect{
node [shape=record];
{rank=same; structa, structb}
structa [label="<A> | |<ref>"]
structb [label="<B> | |<ref>"]
head [label="<head> head||"]
current [label="<current> current ||"]
//structa:ref -> :B:nw
head -> structa [arrowhead=onormal]
current -> structb [arrowhead=onormal]
}
```
```graphviz
digraph indirect{
node [shape=record];
{rank=same; structa, structc}
structp [label="p|<p>&A"]
structptr [label="<name_ptr> prtA | <ptr> &A"]
structa [label="<A> A|1"];
structc [label="<C> B|3"];
structp:ptr->structptr:A:nw
structptr:ptr -> structa:A:nw
}
```
-->
Sign in with Wallet
Connect another wallet