# 2020q3 Homework1 (quiz1)
contributed by < `nelsonlai1` >
## 1
:::info
1.解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現
:::
### **add_entry** :
```c=
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);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
}
```
一開始在初始化`new_node`，分配記憶體空間，assign值以及next。
`assert(new_node)`用來確保malloc成功。
```graphviz
digraph linkedlist {
rankdir=LR;
node[shape=box];
struct5 [label="new_node"]
struct0 [label= "indirect(head)", color=blue];
struct1 [label= "1(*indirect)"];
struct2 [label= "NULL"];
struct3 [label= "NULL"];
struct4 [label= "2"];
{
rank="same";
struct0 -> struct1 [color=blue]
}
struct1 -> struct4
struct4 -> struct2
struct5 -> struct3
}
```
當`*indirect`存在時不斷向後指直到遇到NULL
```graphviz
digraph linkedlist {
rankdir=LR;
node[shape=box];
struct5 [label="new_node"]
struct0 [label= "indirect", color=blue];
struct6 [label= "head", color=blue];
struct1 [label= "1"];
struct2 [label= "NULL"];
struct3 [label= "NULL"];
struct4 [label= "2(*indirect)"];
{
rank="same";
struct0 -> struct4 [color=blue]
}
{
rank="same";
struct6 -> struct1 [color=blue]
}
struct1 -> struct4
struct4 -> struct2
struct5 -> struct3
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node[shape=box];
struct5 [label="new_node"]
struct0 [label= "indirect", color=blue];
struct6 [label= "head", color=blue];
struct1 [label= "1"];
struct2 [label= "*indirect(NULL)"];
struct3 [label= "NULL"];
struct4 [label= "2"];
{
rank="same";
struct0 -> struct2 [color=blue]
}
{
rank="same";
struct6 -> struct1 [color=blue]
}
struct1 -> struct4
struct4 -> struct2
struct5 -> struct3
}
```
將該node改為new_node
```graphviz
digraph linkedlist {
rankdir=LR;
node[shape=box];
struct5 [label="new_node"]
struct0 [label= "indirect", color=blue];
struct6 [label= "head", color=blue];
struct1 [label= "1"];
struct3 [label= "NULL"];
struct4 [label= "2"];
{
rank="same";
struct0 -> struct5 [color=blue]
}
{
rank="same";
struct6 -> struct1 [color=blue]
}
struct1 -> struct4
struct4 -> struct5
struct5 -> struct3
}
```
### **find_entry** :
```c=
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
```
從頭開始檢查`value`是不是要搜尋的，如果不是就繼續往下找，直到找到或是指到NULL為止。
### **remove entry** :
```c=
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
`*indirect`不為`entry`時，`indirect`一直往後移
```graphviz
digraph linkedlist {
rankdir=LR;
node[shape=box];
struct0 [label= "indirect(head)", color = blue];
struct1 [label= ""];
struct2 [label= ""];
struct3 [label= "entry"];
struct4 [label= "e_next"];
{
rank="same";
struct0 -> struct1 [color=blue]
}
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node[shape=box];
struct0 [label= "indirect", color = blue];
struct5 [label= "head", color = blue];
struct1 [label= ""];
struct2 [label= ""];
struct3 [label= "entry"];
struct4 [label= "e_next"];
{
rank="same";
struct0 -> struct2 [color=blue]
}
{
rank="same";
struct5 -> struct1 [color=blue]
}
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
}
```
```graphviz
digraph linkedlist {
rankdir=LR;
node[shape=box];
struct0 [label= "indirect", color = blue];
struct5 [label= "head", color = blue];
struct1 [label= ""];
struct2 [label= ""];
struct3 [label= "entry"];
struct4 [label= "e_next"];
{
rank="same";
struct0 -> struct3 [color=blue]
}
{
rank="same";
struct5 -> struct1 [color=blue]
}
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
}
```
當`*indirect`為`entry`，將`*indirect`改為`entry->next`(圖中用e_next代稱)，最後將`entry`釋放掉
```graphviz
digraph linkedlist {
rankdir=LR;
node[shape=box];
struct0 [label= "indirect", color = blue];
struct5 [label= "head", color = blue];
struct1 [label= ""];
struct2 [label= ""];
struct3 [label= "entry"];
struct4 [label= "e_next"];
{
rank="same";
struct0 -> struct4 [color=blue]
}
{
rank="same";
struct5 -> struct1 [color=blue]
}
struct1 -> struct2
struct2 -> struct4
}
```
### **swap_pair** :
```c=
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;
}
```
for迴圈的判斷為先檢查前兩項node是否存在，如果有的話做完迴圈內的指令後，將移往第三、四項，以此類推直到最後一項或NULL為止。
```graphviz
digraph linkedlist {
rankdir = LR
node[shape = box]
struct0 [label = "node", color = blue]
struct1 [label = "1(head)(*node)(tmp)"]
struct2 [label = "2"]
struct3 [label = "3"]
struct4 [label = "4"]
{
rank="same";
struct0 -> struct1[color=blue]
}
struct1 -> struct2 -> struct3 ->struct4
}
```
*node = (*node)->next;
```graphviz
digraph linkedlist {
rankdir = LR
node[shape = box]
struct0 [label = "node", color = blue]
struct1 [label = "1(tmp)"]
struct2 [label = "2(head)(*node)"]
struct3 [label = "3"]
struct4 [label = "4"]
{
rank="same";
struct0 -> struct2[color=blue]
}
struct1 -> struct2 -> struct3 ->struct4
}
```
tmp->next = (*node)->next;
```graphviz
digraph linkedlist {
rankdir = LR
node[shape = box]
struct0 [label = "node", color = blue]
struct1 [label = "1(tmp)"]
struct2 [label = "2(head)(*node)"]
struct3 [label = "3"]
struct4 [label = "4"]
{
rank="same";
struct0 -> struct2[color=blue]
}
struct1 -> struct3
struct2 -> struct3 ->struct4
}
```
(*node)->next = tmp;
```graphviz
digraph linkedlist {
rankdir = LR
node[shape = box]
struct0 [label = "node", color = blue]
struct1 [label = "1(tmp)"]
struct2 [label = "2(head)(*node)"]
struct3 [label = "3"]
struct4 [label = "4"]
{
rank="same";
struct0 -> struct2[color=blue]
}
struct2 -> struct1
struct1 -> struct3 ->struct4
}
```
node = &(*node)->next->next
```graphviz
digraph linkedlist {
rankdir = LR
node[shape = box]
struct0 [label = "node", color = blue]
struct1 [label = "1(tmp)"]
struct2 [label = "2(head)"]
struct3 [label = "3(*node)"]
struct4 [label = "4"]
{
rank="same";
struct0 -> struct3[color=blue]
}
struct2 -> struct1
struct1 -> struct3 ->struct4
}
```
### **reverse** :
```c=
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;
}
```
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "cursor(NULL)"]
struct1 [label = "1(head)"]
struct2 [label = "2"]
struct3 [label = "3"]
struct1 -> struct2 -> struct3 -> NULL
}
```
node_t *next = head->next;
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "cursor(NULL)"]
struct1 [label = "1(head)"]
struct2 [label = "2(next)"]
struct3 [label = "3"]
struct1 -> struct2 -> struct3 -> NULL
}
```
head->next = cursor;
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "cursor(NULL)"]
struct1 [label = "1(head)"]
struct2 [label = "2(next)"]
struct3 [label = "3"]
struct1 -> struct0
struct2 -> struct3 -> NULL
}
```
cursor = head;
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1(head)(cursor)"]
struct2 [label = "2(next)"]
struct3 [label = "3"]
struct1 -> struct0
struct2 -> struct3 -> NULL
}
```
head = next;
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1(cursor)"]
struct2 [label = "2(next)(head)"]
struct3 [label = "3"]
struct1 -> struct0
struct2 -> struct3 -> NULL
}
```
next loop
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1(cursor)"]
struct2 [label = "2(head)"]
struct3 [label = "3(next)"]
struct1 -> struct0
struct2 -> struct3 -> NULL
}
```
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1(cursor)"]
struct2 [label = "2(head)"]
struct3 [label = "3(next)"]
struct1 -> struct0
struct2 -> struct1
struct3 -> NULL
}
```
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1"]
struct2 [label = "2(head)(cursor)"]
struct3 [label = "3(next)"]
struct1 -> struct0
struct2 -> struct1
struct3 -> NULL
}
```
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1"]
struct2 [label = "2(cursor)"]
struct3 [label = "3(next)(head)"]
struct1 -> struct0
struct2 -> struct1
struct3 -> NULL
}
```
next loop
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1"]
struct2 [label = "2(cursor)"]
struct3 [label = "3(head)"]
struct4 [label = "NULL(next)"]
struct1 -> struct0
struct2 -> struct1
struct3 -> struct4
}
```
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1"]
struct2 [label = "2(cursor)"]
struct3 [label = "3(head)"]
struct4 [label = "NULL(next)"]
struct1 -> struct0
struct2 -> struct1
struct3 -> struct2
}
```
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1"]
struct2 [label = "2"]
struct3 [label = "3(head)(cursor)"]
struct4 [label = "NULL(next)"]
struct1 -> struct0
struct2 -> struct1
struct3 -> struct2
}
```
```graphviz
digraph linkedlist {
rankdir = LR
node [shape = box]
struct0 [label = "NULL"]
struct1 [label = "1"]
struct2 [label = "2"]
struct3 [label = "3(cursor)"]
struct4 [label = "NULL(next)(head)"]
struct1 -> struct0
struct2 -> struct1
struct3 -> struct2
}
```
最後再return cursor作為head
## 2
:::info
2.函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標
:::
```c=
void swap_mod(node_t **head)
{
for (; *head && (*head)->next; head = &(*head)->next->next) {
node_t *indirect = *head;
*head = (*head)->next;
indirect->next = (*head)->next;
(*head)->next = indirect;
}
}
```
```c=
void reverse_mod(node_t **head)
{
node_t *cursor = NULL;
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
}
*head = cursor;
}
```
這部分有點像照樣造句，第一個將node改成head，第二個將head改成＊head
## 3
:::info
3.以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive
:::
```c=
node_t *rev_recursive(node_t *head, node_t *cursor)
{
if(!head)
return cursor;
node_t *next = head->next;
head->next = cursor;
cursor = head;
head = next;
return rev_recursive(head, cursor);
}
```
在main中呼叫 `head = rev_recursive(head, NULL);`
這裡其實就是將原本的loop改成recursive，而因為`head`, `cursor`兩個node都需要隨時更新，所以需要引用這兩個變數。
## 4
:::info
4.針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，你應該儘量降低記憶體的使用量
:::
這裡實作的方法為wiki中提到的modern method，也就是先從範圍(=list size)中選一個數，與範圍中最後一個交換。接著將範圍減一，重複動作直到完成。
```c=
void shuffle(node_t **head)
{
srand(time(NULL));
int size = 0;
node_t *count = *head;
while (count) {
size++;
count = count->next;
}
while (size > 1) {
node_t *swap, *swap_prev, *tail, *tail_prev;
int ran = rand() % size + 1;
printf("%d\n", ran);
if (ran == size) {
size--;
continue;
}
swap = tail = *head;
for (int i = 0; i < size - 1; i++) {
tail_prev = tail;
tail = tail->next;
}
for (int j = 0; j < ran - 1; j++) {
swap_prev = swap;
swap = swap->next;
}
if (ran == size - 1) {
swap->next = tail->next;
tail->next = swap;
} else {
node_t *tmp_next = swap->next;
swap->next = tail->next;
tail->next = tmp_next;
tail_prev->next = swap;
}
if (ran > 1)
swap_prev->next = tail;
else
*head = tail;
size--;
}
}
```
一開始先利用`count`來算出list的大小當作範圍。
當範圍等於0或1不必交換所以while回圈內的判斷為`size > 1`，而另四個node分別是`swap`, `swap_prev`, `tail`, `tail_prev`分別為要交換的node, 最後一項node以及它們的前一項node。
當隨機選到的數與範圍一樣大時也不用交換，所以將範圍減一後continue。
當選到的數與最後一項node相鄰時，在執行`tail->next` = `tmp_next`(此時為`tail`)，以及`tail_prev(此時為swap)->next` = `swap`時會出錯，所以這裡額外判斷操作。
最後判斷選到的數是否為第一個數，來決定更新`*head`或是`swap_prev->next`。
Sign in with Wallet
Connect another wallet