# 2020q3 Homework1 (quiz1)
contributed by < `chi-ming5566` >
---
## 程式運作
以 `add_entry()`, `find_entry()`, `remove_entry()`, `swap_pair()`, `reverse()`, `print_list()` 等函式所組成
---
### `add_entry()`
```cpp=
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;
AA1;
while (*indirect)
indirect = &(*indirect)->next;
AA2;
}
```
* 答案
* AA1為 `(a) assert(new_node)`
* AA2為 `(b) *indirect = new_node`
* 說明
* `*head`會指向 linked list 的尾端，在其插入一個 value 為 `new_value` 的 node。
* `**indirect` 是用來尋找 linked list (**head) 的尾端，而當 `*indirect` 找到尾端時， `*indirect == NULL`，就會將 `new_node` 插入linked list。
* 而 `assert` 是要確保 `new_node` 會正確分配記憶體，於是建立第一個 node，所以會直接跳到第 11 行，將 `indirect` 所存放的 value 當作 adrress，並且更改此 address 存放的 value，將該 value 改為 new_node 的 value。
---
### `find_entry()`
```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;
}
```
* 說明
* 用 for 迴圈找到`*head` 後，傳回存放的值為 `value` 的 node，用於刪除某一個 node。
---
### `remove_entry()`
```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);
}
```
* 說明
* 在 linked list 中找到 `**head`找到 node `*head` 然後刪除。
* 需要變更的 pointer 只有指向 `entry` 的 pointer，因此以 `**indirect` 存放此 pointer 的 address。
* 最後將此 `*indirect` 指向 `entry->next`，就不會有其他 pointer 指向該處。
* 以作業為例:
```cpp=
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);
```
先執行到第10行，接著將 `head` 的 address與要刪除的 node 的 address 當作參數，一起傳入`remove_entry()`。
```graphviz
digraph a{
node [shape=record];
rankdir=LR
entry [label="{<addr>(entry)|<ref>}"]
head [label="{<addr>(main_head)|}"];
a [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
b [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
c [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
d [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
e [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
f [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
head->a:addr;
a:ref->b:addr;
entry:ref->b:addr;
b:ref->c:addr;
c:ref->d:addr;
d:ref->e:addr;
e:ref->f:addr;
}
```
---
```cpp=
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
```
`head` 的 value 是 `main` 的 `head` 的 address
`indirect` 存放 `head` 存放的 value
```graphviz
digraph a{
node [shape=record];
rankdir=LR
a [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
b [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
c [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
d [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
e [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
f [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
a:ref->b:addr;
b:ref->c:addr;
c:ref->d:addr;
d:ref->e:addr;
e:ref->f:addr;
now_head [label="{<addr>(head)|<data>}"]
head [label="{<addr>(main_head)|<data>}"];
now_head:data->head:addr;
head:data->a:addr;
indirect [label="{<addr>(indirect)|<data>}"];
indirect:data->head:addr;
entry [label="{<addr>(entry)|<data>}"];
entry:data->b:addr;
}
```
---
```cpp=
*indirect = entry->next;
```
讓 `*indirect` 所存放的值換為 `entry->next`，如此便可以達到刪除的目的
```graphviz
digraph a{
node [shape=record];
rankdir=LR
a [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
b [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
c [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
d [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
e [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
f [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
a:ref->c:addr [color=red];
b:ref->c:addr;
c:ref->d:addr;
d:ref->e:addr;
e:ref->f:addr;
main_head [label="{<addr>(main_head)|<data>}"];
main_head->a:addr;
head [label="{<addr>(head)|<data>}"];
head:data->main_head:addr;
indirect [label="{<addr>(indirect)|<data>}"];
indirect:data->a:next_addr;
entry [label="{<addr>(entry)|<data>}"];
entry:data->b:addr;
}
```
---
### `swap_pair()`
```cpp=
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1) {
node_t *tmp = *node;
BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
目的：交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
```graphviz
digraph swap{
node [shape="record"]
rankdir=LR;
A [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
//B [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
C [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
D [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
E [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
//F [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
A:ref->C:addr;
//B:ref->C:addr;
C:ref->D:addr;
D:ref->E:addr;
//E:ref->F:addr;
main_head [label="{<addr>(main_head)|<data>}"];
main_head->A:addr;
//head [label="{<addr>(head)|<data>}"];
//head:data->main_head:addr;
//indirect [label="{<addr>(indirect)|<data>}"];
//indirect:data->A:next_addr;
//entry [label="{<addr>(entry)|<data>}"];
}
```
Sign in with Wallet
Connect another wallet